[Ffmpeg-devel] lzw compression in tiff encoder (qualification task for GSoC)

[Bartlomiej Wolowiec]

Hi
On Friday 06 April 2007 18:17, Michael Niedermayer wrote:
> Hi
>
> On Fri, Apr 06, 2007 at 03:28:32PM +0200, Bartlomiej Wolowiec wrote:
> > Hi,
> > As a supplement to my qualification task for GSoC I implemented LZW
> > compressor. I think that my code is fast, universal and it can be easily
> > used in other encoders. My implementation use hash table with simple hash
> > function (I've used LZW prefix code and xor to calculate new hash value).
> > So, I'm sending two files: one with lzw encoder (lzw.patch) and one with
> > patch to tiffenc.c (tifflzw.patch).
>
> [...]
>
> > +/** LZW encode state */
> > +typedef struct LZWEncodeState {
> > +    int clear_code;         ///< Value of clear code
> > +    int end_code;           ///< Value of end code
> > +    Code *tab;              ///< Hash table
> > +    int tabsize;            ///< Number of values in hash table
> > +    int bits;               ///< Actual bits code
> > +    int bufsize;            ///< Size of output buffer
> > +    PutBitContext pb;       ///< Put bit context for output
> >
> > +    int maxbits;            ///< Max bits code
>
> isnt this always 12? and does the code support larger values at all?

Currently is is used only with 12, larger values hardly are used (if there is 
such a need, just the #define should be enlarged). But, I think, that 10 and 
11 bits codes are used.

> > +    int maxcode;            ///< Max value of code
> > +    int output_bytes;       ///< Number of written bytes
> > +    int last_code;          ///< Value of last output code or -1
> > +}LZWEncodeState;
>
> i would prefer if this struct would not be vissible to the user so that
> we can change it without breaking compatibilitym that is either
> malloc() it in ff_lzw_encode_init() or like the libavutil/md5.c code
> have a global constant size of the struct

ok

> [...]
>
> > +/**
> > + * Write one code to stream
> > + * @param s LZW state
> > + * @param c code to write
> > + */
> > +static inline void writeCode(LZWEncodeState * s, int c)
> > +{
> > +    assert(0 <= c && c < 1 << s->bits);
> > +    put_bits(&s->pb, s->bits, c);
> > +}
>
> useless wraper function around put_bits()

Now it's just wraper for put_bits, but various formats differently use lzw 
(e.g. gif).

> [...]
>
> > +
> > +/**
> > + * Add block to LZW code table
> > + * @param s LZW state
> > + * @param c Last character in block
> > + * @param hash_prefix LZW code for prefix
> > + */
> > +static inline void addCode(LZWEncodeState * s, uint8_t c, int
> > hash_prefix) +{
> > +    int hash_code = hash(hash_prefix, c);
> > +    int hash_offset = hashOffset(hash_code);
> > +
> > +    while (s->tab[hash_code].hash_prefix != -2) {
> > +        hash_code = hashNext(hash_code, hash_offset);
> > +    }
>
> hmm it seems to me that addCode() is only reached if findCode() failed to
> find a match but then findCode() already found the next free spot in the
> table so the above seems redundant?

corrected.

> > +
> > +    s->tab[hash_code].code = s->tabsize;
> > +    s->tab[hash_code].suffix = c;
> > +    s->tab[hash_code].hash_prefix = hash_prefix;
> > +
> > +    s->tabsize++;
> > +
> >
> > +    checkSpecialCode(s);
>
> is there any case where this is needed here?

I've changed the code, to use always 256 and 257 values.

> > +    if (s->tabsize >= 1 << s->bits)
> > +        s->bits++;
> > +}
> > +
> > +/**
> > + * Clear LZW code table
> > + * @param s LZW state
> > + */
> > +static inline void clearTable(LZWEncodeState * s)
> > +{
> > +    int i, h;
> > +
> > +    s->bits = 9;
> > +    for (i = 0; i < LZW_HASH_SIZE; i++) {
> > +        s->tab[i].hash_prefix = -2;
>
> please use #defines instead of -1 / -2

ok

Best Regards,
Bartek
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tifflzw.patch
Type: text/x-diff
Size: 3190 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070406/0ea31a1a/attachment.patch>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lzw.patch
Type: text/x-diff
Size: 8696 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070406/0ea31a1a/attachment-0001.patch>