Re: MMX speedup for Floyd Steinberg error diffusion

rep_movsd wrote:
On May 13, 11:07 am, Terje Mathisen <spamt...@xxxxxxxxxx> wrote:
Novosad, Stephan R. wrote:
Terje wrote:
> To do a mathematically perfect job I would start with a 5:5:5 (32 K) or
> 4:4:4 (4 K) table, with each entry being the start of a list of all the
> possible palette entries for that entry:

I tried to implement that, but I just cant get how to initialize the
lists...

Can you explain how?

OK, here's the brute force way:

1. For each 4:4:4 (or 5:5:5) table entry calculate the closest palette color, assuming all the truncated bits are zero.

2. Do the same assuming 1111 bits got truncated.

You need to repeat this operation 8 times, for each possible combination of 0000/1111 on each of the three color axes.

On each iteration you note which entry was closest, most of the time this will be the same palette color, which should be written to the lookup table.

If, otoh, you end up with two or more candidates depending upon the value of the truncated bits, then you know that for this lookup value you need to check them all.

BTW, there's at least one possible bug here: If you have three palette colors _very_ close to each other along at least one color axis, then it is possible that the setup algorithm shown above would only locate the two outliers and not the one in the middle of them!

A q&d workaround would be to always generate a search list if multiple palette colors show a distance that's less than the truncated lookup table bits.

The next problem is how to make this usefully fast:

Instead of iterating multiple times over the entire lookup table, we can (as another poster suggested?) start by inserting each pal color into the proper lookup table slot (noting any collisions!), then for each of them fill the surrounding slots at distance 1, then 2, then 3, stopping as soon as you hit a previously filled entry (and change that entry to a list). This breaks if multiple pal colors map to the same initial lookup table slot, since you won't do any filling of the combined colors.

Terje
--
- <Terje.Mathisen@xxxxxxxxxxxxx>
"almost all programming can be viewed as an exercise in caching"

.

Relevant Pages

  • On-disk indexing for "Project Ideas" page
    ... The kernel usually does the lookup by starting at the beginning ... of the directory and going through, comparing each entry in turn. ... name cache described in Section 6.6. ...
    (freebsd-current)
  • Re: [BUG] Something goes wrong with timer statistics.
    ... into the list to avoid a race with the fastpath lookup. ... can still point into the entries array. ... initialization of a new entry is finished upon insertion of that entry. ...
    (Linux-Kernel)
  • Re: RegExp split for Spell Check
    ... 1,000 entries which is 999 more than it has to look up. ... the trivial matter of reporting success in an appropriate form. ... the last lookup, as a check. ... The lookup time is pretty standard and testing with a 215,000 entry dictionary bears that out for me. ...
    (comp.lang.javascript)
  • Re: is vlookup with an inverted start point possible?
    ... Valko" wrote: ... The way that LOOKUP works is if the lookup_value is greater than all the ... Microsoft Excel MVP ... most recent entry. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: [BUG] Something goes wrong with timer statistics.
    ... into the list to avoid a race with the fastpath lookup. ... can still point into the entries array. ... initialization of a new entry is finished upon insertion of that entry. ...
    (Linux-Kernel)