GIF without LZW
Oleg Pilipenko
compression. Can anyone tell more details about ways to have GIF files
without LZW?
Oleg
Tom Lane
It's quite easy to create "uncompressed GIF" files --- you just write
out a primitive LZW code for each source pixel, and never generate
any multiple-symbol LZW codes. A standard GIF decoder reading your
output will faithfully build an LZW string table on the basis of the
symbol pairings that appear, but it will not notice that you never
ask it to fetch anything from the table.
You do want to generate a CLEAR code every so often to prevent the
decoder from ratcheting up the code size --- bad enough to have to
emit N+1 bits for every N-bit pixel, you don't wanna have to emit
more than N+1 bits per pixel. But this is merely a matter of
counting emitted symbols and can hardly be thought to violate
any patent.
(I should mention that Unisys have been heard to claim that people
owe them royalties even on this uncompressed form of GIF. There is
only one word for that, and it is "barratry". If Unisys threatens
to sue you on that basis, get a good lawyer who will work for a
percentage of the proceeds, and countersue for every cent they're
worth. AFAIK Unisys have never yet been foolish enough to do
more than bluster about it.)
A number of people have thought about methods that would be
slightly smarter than this, yet not the same as LZW, while
still producing data that would be readable by a standard GIF
decoder. In particular, it's not hard to see how to produce
a rough approximation of run-length encoding using about
sqrt(N) GIF symbols for a run of N identical pixel values.
The question you have to ask yourself here is at what point
do you stop having an absolutely watertight defense against
any possible claim of patent infringement from Unisys? The
above non-compressed-GIF method produces a file that is always
*bigger* than plain raw data, by a factor (N+1)/N for N-bit
pixels, so it is unlikely that even the most technically
illiterate judge or jury would find that it violates a data
compression patent --- so unlikely that you'd have an excellent
chance of collecting on a countersuit alleging barratry, should
Unisys actually be so foolish as to try to press the issue.
But if you do RLE, you face the prospect of explaining to that
same illiterate jury the difference between RLE and LZW. The
facts and the law are still clearly on your side, but it's no
longer a case of "first down and one inch to go". You might face
some out-of-pocket legal costs before being vindicated. So
the risk level is a tad higher.
You can find code for producing the plain uncompressed variant
of GIF in many places. There's at least one freeware version
of RLE GIF out there too, but I forget where (I think it's
called "miGIF" if that helps).
None of this says much about the decompression side of things.
A useful decompressor can't restrict itself to handling only
these non-LZW variants; you pretty much have to decode all
valid GIFs that come your way. There is a school of thought
that claims Unisys' patent doesn't apply to a program that
provides only LZW decompression services without LZW compression
services; but I find the argument very shaky.
AFAIK none of these issues have been proven or refuted by any
actual court cases. And IANAL ... if you have real money at
stake, spend some of it on advice from a real lawyer.
regards, tom lane
Oleg Pilipenko
> It's quite easy to create "uncompressed GIF" files --- you just write
> out a primitive LZW code for each source pixel, and never generate
> any multiple-symbol LZW codes. A standard GIF decoder reading your
> output will faithfully build an LZW string table on the basis of the
> symbol pairings that appear, but it will not notice that you never
> ask it to fetch anything from the table.
>
> You do want to generate a CLEAR code every so often to prevent the
> decoder from ratcheting up the code size --- bad enough to have to
> emit N+1 bits for every N-bit pixel, you don't wanna have to emit
> more than N+1 bits per pixel. But this is merely a matter of
> counting emitted symbols and can hardly be thought to violate
> any patent.
How often?
> The question you have to ask yourself here is at what point
> do you stop having an absolutely watertight defense against
> any possible claim of patent infringement from Unisys? The
> above non-compressed-GIF method produces a file that is always
> *bigger* than plain raw data, by a factor (N+1)/N for N-bit
> pixels, so it is unlikely that even the most technically
> illiterate judge or jury would find that it violates a data
> compression patent --- so unlikely that you'd have an excellent
> chance of collecting on a countersuit alleging barratry, should
> Unisys actually be so foolish as to try to press the issue.
So, for B/W image (1bpp) the output stream (it is hard to call it
"compressed"!) will contain binary 00 for each black pixel and 01 for each
white one. In that case it will never need a clear code (100) and will need
EOF code (101) once. Am I right?
> AFAIK none of these issues have been proven or refuted by any
> actual court cases. And IANAL ... if you have real money at
> stake, spend some of it on advice from a real lawyer.
If I had real money at stake, I would rather pay ransom to the Unisys.
Thanks for the reply!
Oleg
Tom Lane
>> You do want to generate a CLEAR code every so often to prevent the
>> decoder from ratcheting up the code size --- bad enough to have to
>> emit N+1 bits for every N-bit pixel, you don't wanna have to emit
>> more than N+1 bits per pixel.
> How often?
It's something like every 2^N symbols, plus or minus one maybe...
check one of the programs that do it already, or work it out
for yourself.
> So, for B/W image (1bpp) the output stream (it is hard to call it
> "compressed"!) will contain binary 00 for each black pixel and 01 for each
> white one.
Right ...
> In that case it will never need a clear code (100) and will need
> EOF code (101) once. Am I right?
No. In the first place, the clear and EOF codes would be 10 and 11;
in the second, you'd have to emit a clear code every couple of symbols
to keep the decoder from ratcheting up the code size. Low bit depth
is the worst case for this technique. With 8-bit pixels you only
have to emit a clear every 256-or-so symbols, which is tolerable, but
the lower the declared data depth, the more often you have to do it.
For 1-bit data, it might be that you'd be better off letting the
code size ratchet up (costing another bit per pixel) one or two
times before you issue a clear. I haven't done the arithmetic to
see which way ends up being the fewest bits. It's going to be
darn expensive in any case, though.
BTW, I seem to recall that the minimum initial bit depth in GIF is
3 not 2, so that black and white would be 000 and 001, with
CLEAR and EOF 100 and 101. Too lazy to go reread the spec right
now, however.
regards, tom lane