-----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-----
