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