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

[Georg Gottleuber]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

On 11.10.2011 23:16, Aleksander Morgado wrote:
>> [2]:
>> @@ -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).

Regards,
Georg
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.17 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk6pFP4ACgkQ5sLITM1qIaKvPgCfdjqpz5cYpHRetko0cdu6vIY1
cy4AoILBeBJ/bV63PaoPioucvauthvx7
=qukW
-----END PGP SIGNATURE-----