Cheating the LZW

Originally published on: Fri, 24 Apr 2009 00:10:27 +0000

In the early days of the web, many web pages sported hit-counters that would generate a graphical meter indicating the number of visitors who had viewed the page.

I thought that it would be a nice thing to have on my own site, so I set out to build my own.

I had decided to try using Perl to build my counter as it had become my language of choice when developing other CGI's.

Some of the popular hit-counters would accept libraries of JPEG's or GIF's representing various kinds of digits and would then use the GD graphics library to fuse the appropriate digit images together into a single image.

I opted to take a different route.

I had decided to use the GIF format for the output image. I wanted a lossless format that could represent a small, monochrome bitmap containing six eight-by-sixteen-pixel characters.

If one has a binary character-set available, building a raw bitmap of a stream of digits is relatively painless. A monochrome bitmap eight by sixteen by two (colors) by 6 (characters) can be represented in 768 bits ( 96 bytes ) uncompressed. That's pretty tiny!

Unfortunately, the GIF format did not permit a flag to indicate that the bitmap image would be an uncompressed bitmap.

So, I was going to have to employ the LZW compression algorithm on this tiny blob of data. ...or WAS I ?

The LZW algorithm uses a protocol of sorts that must be observed by both the compressor and the decompressor. An initial code-size must be agreed upon by both prior to compression or decompression. This code-size value indicates the bit-width for each code in the I/O stream. ( Like many compression algorithms, the LZW leverages variable-length bit I/O. )

The code-size must allow for two codes; clear and end-of-input.

I decided on a code-size of three bits and allowed the LZW special characters to push the code-size up to four bits ... which is easier to handle in bit-shift operations. The clear-code would become eight and the EOI code would be nine as three bits can represent the numbers zero through seven.

For each bit in the generated bitmap, I wrote both a nybble with a value representing a single pixlel, ...a one or a zero followed by a nybble representing the clear-code.

The bit-image was emitted without any true compression. In fact, using the LZW as a protocol, the stream of raw data grew in size ( four bits to represent a monochrome pixel instead of one plus an extra four bits for each clear code. ) This process uses a byte to represent a single pixel when both nybbles are coupled.

At the end of stream, I needed to emit the EOI character, so I simple wrote a byte with the value 9*16, shifting the nine four pixels to the left so that the decompressor would stop processing the bitmap.

The Perl code below illustrates this technique by creating a GIF file named number.gif with the digits "123456" represented as a bitmapped image.

You might change the value of $count to something other than "123456", but it must be six characters in length and must be comprised of all digits.

The generated image is always 805 bytes in size. 768 bytes for the bitmap, one for the EOI code, and thirty-six bytes for the GIF header and footer.

Unless otherwise noted, all code and text entries are Copyright ©2009 by James K. Lawless

Save to StumbleUpon
Digg it
Save to Reddit
Share on Facebook
Share on Twitter
More bookmarks