Parsing GIF Raster Data - LZW

Question 1

GIF parser

You said you want to write your own GIF parser in order to understand how it works. I suggest you look at the source code of any of the libraries containing GIF readers, such as the de-facto reference implementation GIFLIB. The relevant source file is dgif_lib.c; start at slurp for decoding, or jump to the LZW decompression implementation.

Here's how your image decodes.

I think the issue was that you were splitting the input bytes into LZW codes incorrectly.

Number of colors is (0b001 + 1) * 2 = 4.

Code size starts at 2 + 1 = 3 bits.

So the initial dictionary is

000 = color 0 = [blue]
001 = color 1 = [white]
010 = color 2 = [black]
011 = color 3 = [black]
100 = clear dictionary
101 = end of data

Now, GIF packs LZW codes into bytes in LSB-first order. Accordingly, the first code is stored as the 3 least-significant bits of the first byte; the second code as the next 3 bits; and so on. In your example (first byte: 0x84 = 10000100), the first 2 codes are thus 100 (clear) and 000 (blue). The whole thing

01011101 11000001 00100111 01101110 10000100

is split into codes (switches to 4-bit groups after reading the highest 3-bit code, 111) as

0101 1101 1100 0001 0010 0111 0110 111 010 000 100

This decodes to:

     last
code code
 100      clear dictionary
 000      output [blue] (1st pixel)
 010  000 new code in table:
              output 010 = [black]
              add 110 = old + 1st byte of new = [blue black] to table
 111  010 new code not in table:
              output last string followed by copy of first byte, [black black]
              add 111 = [black black] to table
              111 is largest possible 3-bit code, so switch to 4 bits
0110 0111 new code in table:
              output 0110 = [blue black]
              add 1000 = old + 1st byte of new = [black black blue] to table
0111 0110 new code in table:
              output 0111 = [black black]
              add 1001 = old + 1st byte of new = [blue black black] to table
...

So the output starts (wrapping to 3 columns):

blue  black black
black blue  black
black black ...

which is what you wanted.

Question 2

This site is an excellent resource about the GIF format, and offers a great explanation of the LZW compression and decompression process:

http://www.matthewflickinger.com/lab/whatsinagif/index.html

Question 3

Solution without writing your own GIF reader

For uses other than your own edification, try this.

A few notes

Your GIF file is GIF89a. You linked to the GIF87a specification; the 89a specification is here.
You're seem to be concerned that using a library to parse the image will hurt performance. This makes no sense. The libraries are generally implemented in optimized C; your hand-rolled solution would be written in PHP, an interpreted language.
You mentioned PCX, which libraries like imagemagick do support.

Or just use PNG

According to the ZPL 2 programming manual, PNG is supported. For example, the ~DY (Download Graphics) command takes a b (format) parameter, for which P (PNG) is an option, besides the default GRF. See also Printing PNG images to a zebra network printer.

There are lots of libraries for converting GIF to PNG. You could use ImageMagick (PHP binding), or just use the PHP functions imagecreatefromgif and imagepng.

Question 4

I can't help you with the LZW decoding, but wouldn't it be easier to just use a library function like imagecreatefromgif() from the PHP GD extension to parse the GIF file and extract the image data, which you can then convert to your target format?

Question 5

It is good you want to know how to do LZW without using libraries written by someone else. LZW does not decode images pixel by pixel. It looks for repeat blocks in the data stream, saves them in a dictionary and refers back to them. If 100 pixels are repeated somewhere only one code is used to reproduce that 100 pixels instead of 100 as with bitmap (BMP) images. This is why GIF is great for diagrams where you might have many series of 100 white pixels followed by a few black ones to draw a line. On the other hand, it is lousy for photographs because there are very few long repeats and GIF is generally restricted to 256 colours unless you use some complicated tricks.

The codes used in the compressed file are longer than the colour codes for each pixel in the original image. It is only because long repeat blocks are common in diagrams that massive compression is possible.