CODEWITHSUNDEEP
algorithmgif
Dennis Munsie
Dennis Munsie

Reputation: 1211

Why does the GIF spec require at least 2-bits for the initial LZW code size?

I've been trying to figure out why the GIF89a spec requires that the initial LZW code size to be at least 2-bits, even when encoding 1-bit images (B&W). In appendix F of the spec, it says the following:

ESTABLISH CODE SIZE

The first byte of the Compressed Data stream is a value indicating the minimum number of bits required to represent the set of actual pixel values. Normally this will be the same as the number of color bits. Because of some algorithmic constraints however, black & white images which have one color bit must be indicated as having a code size of 2.

I'm curious as to what these algorithmic constraints are. What would possibly prevent the variant of LZW used in GIF from using a code size of 1? Was this just a limitation of the early encoders or decoders? Or is there some weird edge case that can manifest itself in with just the right combination of bits? Or is there something completely different going on here?

Upvotes: 3

Views: 212

Answers (2)

Egor Skriptunoff
Egor Skriptunoff

Reputation: 23737

This limitation gets rid of one if in implementation (with codesize==1 the first vocabulary phrase code would have width==codesize+2, in all other cases width==codesize+1).
The drawback is very small decreasing in compression ratio for 2-color pictures.

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308158

In addition to the codes for 0 and 1, you also have a clear code and an end of information code.

Quoting from the spec:

The output codes are of variable length, starting at +1 bits per code, up to 12 bits per code. This defines a maximum code value of 4095 (0xFFF). Whenever the LZW code value would exceed the current code length, the code length is increased by one.

If you start with a code size of 1, the code size needs to be increased immediately by this rule.

Upvotes: 1

Related Questions