Re: [pdf-devel] Bug in LZW filter?

[Aleksander Morgado]

> >> @@ -419,7 +421,7 @@
> >>            lzw_buffer_put_code (&st->buffer, st->string.prefix);
> >>            st->string.prefix = st->string.suffix;
> >>
> >> -          if (st->buffer.maxval - st->early_change == st->dict.size)
> >> +          if (st->buffer.maxval - st->early_change + 2 == st->dict.size)
> >>              {
> >>                if (!lzw_buffer_inc_bitsize (&st->buffer))
> >>                  {
> 
> I found a very good explanation for a "+1" at this place (a second +1 is
> of course still missing).
> 
> As stated in ISO32000 bitsize increase shall happen after inserting
> table entry 511. This is what we do. But the algorithm steps in ISO32000
> are:
> 1) Accumulate longest input sequence
> 2) Emmit Code
> 3) Create new table entry
> 
> We actually do:
> 1)
> 3)
> 2)
> 
> This is why we are one output code too early.
> 
> Maybe it is worth to restructure the LZW encoder to 1),2),3). I know
> that this would need some extra cycles for looking up and additional
> inserting (instead of doing it with one call of lzw_dict_add). But maybe
> we are able to testify the testdata and get a correct and easy to
> maintain algorithm. If you wish, I will do this.
> 
> By the way: all descriptions I found explain LZW with order 1),2),3).
> 

If that is the case, then it's probably much better to reorder the
filter to work with that order, documenting each step in the source
code.

-- 
Aleksander

signature.asc
Description: This is a digitally signed message part