Parsing GIF Raster Data - LZW

Question

I've been trying to decompress GIF's in PHP and seem to have everything except the LZW decompression down. I have saved an image that is shown: sample image

This image is 3 x 5 like this:

Blue  Black Black
Black Blue  Black
Black Black Black
White White White
White White White

I decided to go through manually in Binary and parse this file. The result of manual parsing is below. I am still stuck as to how to decode the raster data here. Can someone break down how the raster data becomes the image? I've been able to break down one image, but nothing else (not this image). I have posted my understanding of how this should break down, but I am obviously doing it wrong.

01000111 G
01001001 I
01000110 F
00111000 8
00111001 9
01100001 a

Screen Descriptor
WIDTH
00000011 3
00000000

00000101 5
00000000

10010001 GCM (1), CR (001), BPP (001), CD = 2, COLORS = 4

00000000 BGCOLOR Index

00000000 Aspect Ratio

GCM
BLUE
00110101 | 53
00000000 | 0
11000001 | 193

WHITE
11111111 | 255
11111111 | 255
11111111 | 255

BLACK
00000000 | 0
00000000 | 0
00000000 | 0

00000000 | 0
00000000 | 0
00000000 | 0

Extension
00100001 | 21
Function Code
11111001 | F9
Length
00000100 | 4
00000000
00000000
00000000
00000000
Terminator
00000000

Local Descriptor
00101100 Header
XPOS
00000000 | 0
00000000

YPOS
00000000 | 0
00000000

Width
00000011 | 3
00000000

Height
00000101 | 5
00000000

Flags
00000000 (LCM = 0, Interlaced = 0, Sorted = 0, Reserved = 0, Pixel Bits = 0)

RASTER DATA
Initial Code Size
00000010 | 2
Length
00000101 | 5

Data
10000100
01101110
00100111
11000001
01011101

Terminator
00000000

00111011 | ;
00000000

My Attempt

Initial Code Size = 3 Read 2 bits at a time

10
00
Append last bit to first (010)
String becomes 010 or 2. 2 would be color # 3 or BLACK

At this point, I am already wrong. The first color should be blue.

Resources I have been using:

http://www.daubnet.com/en/file-format-gif http://en.wikipedia.org/wiki/Graphics_Interchange_Format http://www.w3.org/Graphics/GIF/spec-gif87.txt

I need to be able to dynamically convert GIF to a printer image format (PCX / GRF) I already know how to do those conversions, but not from GIF. — teynon, Jan 07 '13 at 20:51
As an alternative, I would also want to point out that imagemagick is quite powerful, and will likely do this for you too :) Interesting question though — Evert, Jan 07 '13 at 21:07
imagemagick doesn't support GRF, which is really my end goal here. GRF is, I believe, a Zebra printer format. — teynon, Jan 07 '13 at 21:12
I don't have it with me at the moment, but it looks like this one: http://www.barcodegiant.com/zebra/part-2844-20300-0001.htm?aw&adtype=pla&gclid=CMG71d6g3LQCFS-RPAodMlkADA The code being sent to the printer is in ZPL2 — teynon, Jan 09 '13 at 21:50

score 17 · Accepted Answer · answered Jan 10 '13 at 00:42

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.

This is what I was looking for. I had the decompression right in one of my attempts except for the lsb thing. I saw in the specs the little endian byte order, but I didn't see that applying to the raster data for some reason. (18 hours before I can award bounty) — teynon, Jan 10 '13 at 01:29

score 2 · Answer 2 · answered May 08 '17 at 14:00

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

answered May 08 '17 at 14:00

Thomas Levesque

286,951
70
623
758

score 1 · Answer 3 · edited May 23 '17 at 12:02

1

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.

edited May 23 '17 at 12:02

Community

1
1

answered Jan 09 '13 at 22:53

Mechanical snail

29,755
14
88
113

The point of the bounty is how to do the decompression. I've looked through source files including the one you've mentioned and I still have trouble doing the decompression. Regardless of optimization, etc, none of these responses answer the actual question. – teynon Jan 09 '13 at 23:12
@Tom: You haven't explained *why* you need to do the decompression yourself. – Mechanical snail Jan 09 '13 at 23:15
2

The reason why doesn't matter. I'd like to know how it's done. – teynon Jan 09 '13 at 23:17
@Tom: I think you were splitting the byte-string into LZW codes incorrectly. Adding as a separate answer since it's a different method. – Mechanical snail Jan 10 '13 at 00:40

score 0 · Answer 4 · answered Jan 07 '13 at 20:57

0

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?

answered Jan 07 '13 at 20:57

Ilmari Karonen

49,047
9
93
153

I could parse it by walking through each pixel after parsing it with PHP's GD, but this adds additional overhead. I also would like to know how to do it so I can use it later. Everything I see written on the web is missing small key points in their explanations and some are inconsistent. – teynon Jan 07 '13 at 21:00
2

It might still be about as fast as doing the LZW decompression by hand in PHP. Also, I believe some of the other PHP image manipulation extensions provide better access to the raster data. – Ilmari Karonen Jan 07 '13 at 21:27

score 0 · Answer 5 · answered Feb 03 '14 at 16:18

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.