GIF (Graphics Interchange Format) is an image compression format for paletted still and animated images. It is specified in the GIF89a specification.
Consider test/data/bricks-nodither.gif.
offset xoffset ASCII hex binary 000000 0x0000 G 0x47 0b_0100_0111 000001 0x0001 I 0x49 0b_0100_1001 000002 0x0002 F 0x46 0b_0100_0110 000003 0x0003 8 0x38 0b_0011_1000 000004 0x0004 9 0x39 0b_0011_1001 000005 0x0005 a 0x61 0b_0110_0001 000006 0x0006 . 0xA0 0b_1010_0000 000007 0x0007 . 0x00 0b_0000_0000 000008 0x0008 x 0x78 0b_0111_1000 etc 014230 0x3796 . 0xD3 0b_1101_0011 014231 0x3797 . 0x02 0b_0000_0010 014232 0x3798 . 0x06 0b_0000_0110 014233 0x3799 . 0x04 0b_0000_0100 014234 0x379A . 0x00 0b_0000_0000 014235 0x379B ; 0x3B 0b_0011_1011
Starting at the top, a magic identifier, either “GIF87a” or “GIF89a”. In theory, some decoders can only handle the 1987 flavor. In practice, support for the 1989 flavor is ubiquitous. Anyway, the magic ID is:
offset xoffset ASCII hex binary 000000 0x0000 G 0x47 0b_0100_0111 000001 0x0001 I 0x49 0b_0100_1001 000002 0x0002 F 0x46 0b_0100_0110 000003 0x0003 8 0x38 0b_0011_1000 000004 0x0004 9 0x39 0b_0011_1001 000005 0x0005 a 0x61 0b_0110_0001
The Logical Screen Descriptor is at least 7 bytes long:
offset xoffset ASCII hex binary 000006 0x0006 . 0xA0 0b_1010_0000 000007 0x0007 . 0x00 0b_0000_0000 000008 0x0008 x 0x78 0b_0111_1000 000009 0x0009 . 0x00 0b_0000_0000 000010 0x000A . 0xF7 0b_1111_0111 000011 0x000B . 0x00 0b_0000_0000 000012 0x000C . 0x00 0b_0000_0000
The image size is 0x00A0 by 0x0078 pixels, or 160 by 120. The fifth byte is flags, the sixth is the background color index, the seventh is ignored.
The high bit (0x80) and low three bits (0x07) of the flags indicate that we have a GCT (Global Color Table) and that it contains 1<<(7+1), or 256, elements. Global means that it applies to each frame in the possibly animated image unless a per-frame Local Color Table overrides it, and Color Table means a palette of up to 256 RGB (Red, Green, Blue) triples. That GCT follows immediately:
offset xoffset ASCII hex binary 000013 0x000D . 0x01 0b_0000_0001 000014 0x000E . 0x03 0b_0000_0011 000015 0x000F . 0x04 0b_0000_0100 000016 0x0010 . 0x00 0b_0000_0000 000017 0x0011 . 0x0C 0b_0000_1100 000018 0x0012 . 0x03 0b_0000_0011 etc 000250 0x00FA . 0x01 0b_0000_0001 000251 0x00FB $ 0x24 0b_0010_0100 000252 0x00FC c 0x63 0b_0110_0011 etc 000673 0x02A1 . 0x0F 0b_0000_1111 000674 0x02A2 . 0xA7 0b_1010_0111 000675 0x02A3 . 0xF6 0b_1111_0110 etc 000778 0x030A . 0x9F 0b_1001_1111 000779 0x030B . 0xB8 0b_1011_1000 000780 0x030C . 0xCD 0b_1100_1101
Thus, color 0 in the palette is the RGB triple {0x01, 0x03, 0x04}, color 1 is {0x00, 0x0C, 0x03}, etc, color 79 is {0x01, 0x24, 0x63}, etc, color 220 is {0x0F, 0xA7, 0xF6}, etc, color 255 is {0x9F, 0xB8, 0xCD}.
For this particular GIF, next comes an Extension Introducer byte (0x21) for a GCE (Graphic Control Extension) (0xF9), followed by one or more data blocks:
offset xoffset ASCII hex binary 000781 0x030D ! 0x21 0b_0010_0001 000782 0x030E . 0xF9 0b_1111_1001 000783 0x030F . 0x04 0b_0000_0100 000784 0x0310 . 0x00 0b_0000_0000 000785 0x0311 . 0x00 0b_0000_0000 000786 0x0312 . 0x00 0b_0000_0000 000787 0x0313 . 0x00 0b_0000_0000 000788 0x0314 . 0x00 0b_0000_0000
The first block has 0x04 payload bytes. After those four bytes, the second block has 0x00 payload bytes, which marks the end of the data blocks. The payload bytes are flags, animation timing and transparency information that, for this simple, opaque, single-frame image, happen to be all zero.
Image Descriptors form the bulk of a GIF image. A still image will have one Image Descriptor. An animated image will have many. Image Descriptors begin with an 0x2C byte, followed by at least nine more bytes for the {left, top, width, height} of this frame relative to the overall (potentially animated) image, plus a flags byte:
offset xoffset ASCII hex binary 000789 0x0315 , 0x2C 0b_0010_1100 000790 0x0316 . 0x00 0b_0000_0000 000791 0x0317 . 0x00 0b_0000_0000 000792 0x0318 . 0x00 0b_0000_0000 000793 0x0319 . 0x00 0b_0000_0000 000794 0x031A . 0xA0 0b_1010_0000 000795 0x031B . 0x00 0b_0000_0000 000796 0x031C x 0x78 0b_0111_1000 000797 0x031D . 0x00 0b_0000_0000 000798 0x031E . 0x00 0b_0000_0000
The frame‘s origin is {0x0000, 0x0000} and its extent is {0x00A0, 0x0078}. The flags byte indicates a non-interlaced frame and that no LCT (Local Color Table) overrides the GCT. After the (lack of) LCT comes the LZW (Lempel Ziv Welch) compression’s log2(literal_width), discussed further below.
offset xoffset ASCII hex binary 000799 0x031F . 0x08 0b_0000_1000
Pixel data from the bulk of an Image Descriptor. Just like the GCE format, the payload is framed as a sequence of blocks, each block starting with a single byte count of the remaining bytes in the block, and the final block containing only a 0x00 byte.
offset xoffset ASCII hex binary 000800 0x0320 . 0xFE 0b_1111_1110 000801 0x0321 . 0x00 0b_0000_0000 000802 0x0322 . 0xB9 0b_1011_1001 000803 0x0323 . 0x09 0b_0000_1001 000804 0x0324 . 0x14 0b_0001_0100 000805 0x0325 . 0x98 0b_1001_1000 etc 001053 0x041D 6 0x36 0b_0011_0110 001054 0x041E . 0x1E 0b_0001_1110 001055 0x041F . 0xFE 0b_1111_1110 001056 0x0420 J 0x4A 0b_0100_1010 001057 0x0421 . 0xA4 0b_1010_0100 etc 001308 0x051C . 0x1F 0b_0001_1111 001309 0x051D . 0x81 0b_1000_0001 001310 0x051E . 0xFE 0b_1111_1110 001311 0x051F 5 0x35 0b_0011_0101 001312 0x0520 ] 0x5D 0b_0101_1101 etc etc etc 013803 0x35EB n 0x6E 0b_0110_1110 013804 0x35EC . 0xD7 0b_1101_0111 013805 0x35ED . 0xFE 0b_1111_1110 013806 0x35EE . 0x17 0b_0001_0111 013807 0x35EF . 0xB4 0b_1011_0100 etc 014058 0x36EA . 0xDB 0b_1101_1011 014059 0x36EB g 0x67 0b_0110_0111 014060 0x36EC . 0xAD 0b_1010_1101 014061 0x36ED . 0x81 0b_1000_0001 014062 0x36EE . 0xD6 0b_1101_0110 etc 014232 0x3798 . 0x06 0b_0000_0110 014233 0x3799 . 0x04 0b_0000_0100 014234 0x379A . 0x00 0b_0000_0000
The specification allows for the block count to be 0xFF, but for whatever reason, the ImageMagick encoder and its command-line convert tool generated slightly shorter blocks, with lengths 0xFE, 0xFE, 0xFE, ..., 0xFE, 0xAD, 0x00.
The payload wrapped by these block counts are LZW compressed, discussed below.
The final byte is 0x3B.
offset xoffset ASCII hex binary 014235 0x379B ; 0x3B 0b_0011_1011
See std/lzw/README.md for a description of LZW: a general purpose compression algorithm. Below is a detailed decoding of the LZW data from the Wire Format Worked Example, deconstructed above.
It is not an official format, but the test/data/bricks-nodither.indexes.giflzw file contains the extracted “Pixel Data” payload from test/data/bricks-nodither.gif, preceded by the one byte log2(literal_width). Deriving a separate file, as a separate, contiguous stream, makes it easier to discuss the LZW compression format.
offset xoffset ASCII hex binary
000000 0x0000 . 0x08 0b_0000_1000
000001 0x0001 . 0x00 0b_0000_0000
000002 0x0002 . 0xB9 0b_1011_1001
000003 0x0003 . 0x09 0b_0000_1001
000004 0x0004 . 0x14 0b_0001_0100
000005 0x0005 . 0x98 0b_1001_1000
000006 0x0006 . 0xAD 0b_1010_1101
000007 0x0007 ^ 0x5E 0b_0101_1110
000008 0x0008 > 0x3E 0b_0011_1110
000009 0x0009 { 0x7B 0b_0111_1011
000010 0x000A . 0xDF 0b_1101_1111
000011 0x000B . 0xB8 0b_1011_1000
000012 0x000C } 0x7D 0b_0111_1101
000013 0x000D . 0xC9 0b_1100_1001
000014 0x000E . 0xA1 0b_1010_0001
000015 0x000F . 0xA3 0b_1010_0011
000016 0x0010 a 0x61 0b_0110_0001
000017 0x0011 . 0xC3 0b_1100_0011
000018 0x0012 0 0x30 0b_0011_0000
etc
000253 0x00FD 6 0x36 0b_0011_0110
000254 0x00FE . 0x1E 0b_0001_1110
000255 0x00FF J 0x4A 0b_0100_1010
000256 0x0100 . 0xA4 0b_1010_0100
etc
000507 0x01FB . 0x1F 0b_0001_1111
000508 0x01FC . 0x81 0b_1000_0001
000509 0x01FD 5 0x35 0b_0011_0101
000510 0x01FE ] 0x5D 0b_0101_1101
etc
etc
etc
012953 0x3299 n 0x6E 0b_0110_1110
012954 0x329A . 0xD7 0b_1101_0111
012955 0x329B . 0x17 0b_0001_0111
012956 0x329C . 0xB4 0b_1011_0100
etc
013207 0x3397 . 0xDB 0b_1101_1011
013208 0x3398 g 0x67 0b_0110_0111
013209 0x3399 . 0x81 0b_1000_0001
013210 0x339A . 0xD6 0b_1101_0110
etc
013380 0x3444 . 0x06 0b_0000_0110
013381 0x3445 . 0x04 0b_0000_0100
LZW consists of a sequence of code values, in the range [0, max] inclusive. Each code decodes to either a literal value (one byte), a back-reference (multiple bytes), a ‘clear code’ (discussed below), or indicates the end of the data stream.
The first 1<<l2lw codes are literal codes, where l2lw is the log2(literal_width) mentioned above. For GIF's flavor of LZW, valid l2lw values are between 2 and 8 inclusive.
For example, if l2lw == 8, then the first 256 codes are literal codes: the 0 code decodes one 0x00 byte, the 1 code decodes one 0x01 byte, etc. The next code (256) is the clear code and the next code after that (257) is the end code. Any code higher than that denotes a back-reference, but any code above the current max value is invalid.
max's initial value is the same as the end code, and it increases by 1 with each code consumed, up until max == 4095. A clear code resets max to its initial value, and clears the meaning of higher back-reference codes.
Codes take up a variable number of bits in the input stream, the width, depending on max. For example, if max is in the range [256, 511] then the next code takes 9 bits, if max is in the range [512, 1023] then width == 10, and so on. For GIF, when a code spans multiple bytes, codes are formed Least Significant Bits first. For the test/data/bricks-nodither.indexes.giflzw example, l2lw == 8 and so width starts at 9 bits. Printing the bits on byte boundaries give:
offset xoffset ASCII hex binary
000001 0x0001 . 0x00 0b_0000_0000
000002 0x0002 . 0xB9 0b_1011_1001
000003 0x0003 . 0x09 0b_0000_1001
000004 0x0004 . 0x14 0b_0001_0100
000005 0x0005 . 0x98 0b_1001_1000
000006 0x0006 . 0xAD 0b_1010_1101
000007 0x0007 ^ 0x5E 0b_0101_1110
000008 0x0008 > 0x3E 0b_0011_1110
000009 0x0009 { 0x7B 0b_0111_1011
000010 0x000A . 0xDF 0b_1101_1111
000011 0x000B . 0xB8 0b_1011_1000
000012 0x000C } 0x7D 0b_0111_1101
000013 0x000D . 0xC9 0b_1100_1001
000014 0x000E . 0xA1 0b_1010_0001
000015 0x000F . 0xA3 0b_1010_0011
000016 0x0010 a 0x61 0b_0110_0001
000017 0x0011 . 0xC3 0b_1100_0011
000018 0x0012 0 0x30 0b_0011_0000
etc
000147 0x0093 > 0x3E 0b_0011_1110
000148 0x0094 . 0xC4 0b_1100_0100
etc
000286 0x011E _ 0x5F 0b_0101_1111
000287 0x011F . 0xEA 0b_1110_1010
000288 0x0120 . 0x9C 0b_1001_1100
000289 0x0121 . 0xFC 0b_1111_1100
000290 0x0122 . 0xD4 0b_1101_0100
000291 0x0123 . 0xA4 0b_1010_0100
etc
005407 0x151F . 0xBB 0b_1011_1011
005408 0x1520 . 0xFB 0b_1111_1011
005409 0x1521 . 0x00 0b_0000_0000
005410 0x1522 . 0xE1 0b_1110_0001
005411 0x1523 . 0xA1 0b_1010_0001
005412 0x1524 . 0xC3 0b_1100_0011
005413 0x1525 @ 0x40 0b_0100_0000
etc
013378 0x3442 . 0xD3 0b_1101_0011
013379 0x3443 . 0x02 0b_0000_0010
013380 0x3444 . 0x06 0b_0000_0110
013381 0x3445 . 0x04 0b_0000_0100
and on code boundaries give:
binary width code 0b_...._...._...._...1_0000_0000 9 0x0100 0b_...._...._...._..01_1011_100. 9 0x00DC 0b_...._...._...._.100_0000_10.. 9 0x0102 0b_...._...._...._1000_0001_0... 9 0x0102 0b_...._...._...0_1101_1001_.... 9 0x00D9 0b_...._...._..01_1110_101._.... 9 0x00F5 0b_...._...._.011_1110_01.._.... 9 0x00F9 0b_...._...._0111_1011_0..._.... 9 0x00F6 0b_...._...._...._...0_1101_1111 9 0x00DF 0b_...._...._...._..01_1011_100. 9 0x00DC 0b_...._...._...._.001_0111_11.. 9 0x005F 0b_...._...._...._0001_1100_1... 9 0x0039 0b_...._...._...0_0011_1010_.... 9 0x003A 0b_...._...._..10_0001_101._.... 9 0x010D 0b_...._...._.100_0011_01.._.... 9 0x010D 0b_...._...._0011_0000_1..._.... 9 0x0061 etc 0b_...._...._...._.100_0011_11.. 9 0x010F etc 0b_...._...._.110_1010_01.._.... 9 0x01A9 0b_...._...._1001_1100_1..._.... 9 0x0139 0b_...._...._...._..00_1111_1100 10 0x00FC (implicit width increase) 0b_...._...._...._0100_1101_01.. 10 0x0135 etc 0b_...._...._1111_1011_1011_.... 12 0x0FBB 0b_...._...._...._0001_0000_0000 12 0x0100 (code == 0x0100 means clear) 0b_...._...._...0_0001_1110_.... 9 0x001E (explicit width reset) 0b_...._...._..00_0011_101._.... 9 0x001D 0b_...._...._.100_0000_11.._.... 9 0x0103 etc 0b_...._..10_0000_0010_11.._.... 12 0x080B 0b_...._...._..00_0100_0000_01.. 12 0x0101
The implicit width increase is because max ticked over from 0x01FF to 0x200. Processing these codes give:
code meaning max output 0x0100 clear 0x0101 . 0x00DC literal 0x0101 0xDC 0x0102 back-ref 0x0102 0xDC 0xDC 0x0102 back-ref 0x0103 0xDC 0xDC 0x00D9 literal 0x0104 0xD9 0x00F5 literal 0x0105 0xF5 0x00F9 literal 0x0106 0xF9 0x00F6 literal 0x0107 0xF6 0x00DF literal 0x0108 0xDF 0x00DC literal 0x0109 0xDC 0x005F literal 0x010A 0x5F 0x0039 literal 0x010B 0x39 0x003A literal 0x010C 0x3A 0x010D back-ref 0x010D 0x3A 0x3A 0x010D back-ref 0x010E 0x3A 0x3A 0x0061 literal 0x010F 0x61 etc 0x010F back-ref 0x0182 0x3A 0x3A 0x61 etc 0x01A9 back-ref 0x01FE 0xFB 0xFB 0xFB 0xFB 0x0139 back-ref 0x01FF 0xFB 0xFC 0x00FC literal 0x0200 0xFC 0x0135 back-ref 0x0201 0xFA 0xFA etc 0x0FBB back-ref 0x0FFF 0xC1 0xC1 0xC1 0xC1 0xC1 0xC1 0xDF 0x0100 clear 0x0FFF . 0x001E literal 0x0101 0x1E 0x001D literal 0x0102 0x1D 0x0103 back-ref 0x0103 0x1D 0x1D etc 0x080B back-ref 0x0896 0x4F 0x4F 0x4F 0x4F 0x4F 0x0101 end 0x0897 .
The max column here is the max code allowed when processing that row's code. The initial clear code is redundant (as the initial value of max is already 0x0101 here), but some encoders produce them because the specification says that “encoders should output a Clear code as the first code of each image data stream”.
Other than clear and end codes, each code produces some output: a variable length prefix and a one byte suffix. For literal codes, the prefix is empty and the suffix is the literal.
When max is greater than the end code (e.g. greater than 0x0101), the row defines a new back-reference, and that definition persists up until the next clear code. For example, the third, fourth, fifth, etc. rows define what the 0x0102, 0x0103, 0x0104, etc. codes output. That code‘s output (prefix + suffix) is defined by the prefix being the previous row’s output and the suffix being the first byte of the current row's output.
For example, the 15th and 16th rows are:
code meaning max output 0x010D back-ref 0x010E 0x3A 0x3A 0x0061 literal 0x010F 0x61
which defines the 0x010F code to output “0x3A 0x3A 0x61”. Later on, an 0x010F code is encountered, and its output is exactly that.
A row's code can be the code that that row itself defines, in which case the prefix is the previous row and the suffix is the first byte of the previous row. Consider the opening few codes:
code meaning max output 0x0100 clear 0x0101 . 0x00DC literal 0x0101 0xDC 0x0102 back-ref 0x0102 0xDC 0xDC 0x0102 back-ref 0x0103 0xDC 0xDC 0x00D9 literal 0x0104 0xD9
The third row‘s code is 0x0102, which that row also defines. Its output is therefore the concatenation of “0xDC” and the first byte of “0xDC”, both of those strings being the previous row’s output. The fourth row executes the same 0x0102 code (and outputs “0xDC 0xDC” again) and defines the 0x0103 code. The next code is a literal 0xD9, and hence the decoded output starts with five 0xDC bytes and then an 0xD9.
It is also not an official format, but for reference, the test/data/bricks-nodither.indexes contains the decoded test/data/bricks-nodither.indexes.giflzw data:
offset xoffset ASCII hex binary 000000 0x0000 . 0xDC 0b_1101_1100 000001 0x0001 . 0xDC 0b_1101_1100 000002 0x0002 . 0xDC 0b_1101_1100 000003 0x0003 . 0xDC 0b_1101_1100 000004 0x0004 . 0xDC 0b_1101_1100 000005 0x0005 . 0xD9 0b_1101_1001 000006 0x0006 . 0xF5 0b_1111_0101 000007 0x0007 . 0xF9 0b_1111_1001 000008 0x0008 . 0xF6 0b_1111_0110 000009 0x0009 . 0xDF 0b_1101_1111 000010 0x000A . 0xDC 0b_1101_1100 000011 0x000B _ 0x5F 0b_0101_1111 000012 0x000C 9 0x39 0b_0011_1001 000013 0x000D : 0x3A 0b_0011_1010 000014 0x000E : 0x3A 0b_0011_1010 000015 0x000F : 0x3A 0b_0011_1010 000016 0x0010 : 0x3A 0b_0011_1010 000017 0x0011 : 0x3A 0b_0011_1010 000018 0x0012 a 0x61 0b_0110_0001 etc 019195 0x4AFB O 0x4F 0b_0100_1111 019196 0x4AFC O 0x4F 0b_0100_1111 019197 0x4AFD O 0x4F 0b_0100_1111 019198 0x4AFE O 0x4F 0b_0100_1111 019199 0x4AFF O 0x4F 0b_0100_1111
We have 19200 = 160 × 120 pixels. The top row starts with five pixels with RGB values indexed by 0xDC (or 220 in decimal, and recall that the GCT maps color 220 to {0x0F, 0xA7, 0xF6}), the bottom row ends with index 0x4F.
Indeed, opening test/data/bricks-nodither.gif in an image editor should verify that the top left pixel‘s RGB is {0x0F, 0xA7, 0xF6}, and likewise the bottom right pixel’s RGB is {0x01, 0x24, 0x63}.
See test/data/artificial/gif-*.commentary.txt