GIF decoding

Last time we figured out how JPEG is organized ( JPEG decoding for dummies ). It is logical that the next format was GIF. By the way, it is much easier. It, unlike JPEG, can be decoded with only a pen with a piece of paper. At first, continuing the tradition, I wanted to encode Google's GIFF favicon, but then decided that it was better to paint the process of decoding the entire file on a small image. Without any "and then by analogy ...". I had to experiment for a long time, and the picture turned out to be clumsy, but quite visual for study.

So, we will pick this picture . See you :) Then it is increased 10 times:


Internals in a hex editor:

Headline

[47 49 46 38 37 61] GIF87a.
There may be GIF89a. These formats are distinguished by optional additional sections, which we will not consider, they are described in the specification.
')
Next is the section

Logical Screen Descriptor

The image is located in a logical screen and can be shifted relative to the upper left corner of this screen. All the files I viewed viewed the same size as the screen.

[04 00] [04 00] = 4x4 (logical screen sizes)
[91] = 10010001b
(1) = 1. A global color table is used.
(001) = 1. Color resolution. The number of colors is 2 ^{n + 1} , in our case 4.
(0) = 0. Colors are not sorted.
(001) = 1. Size of the color table. It takes 3 * 2 ^{n + 1} bytes. We have -12.
[00] = 0. Background color index. For transparency.
[00] = 0. Aspect ratio. (The vast majority of images have this byte 0, that is 1: 1. Otherwise, see the specification)

Next is the section

Global color table

We read 12 bytes, and form such a table:
R G B
[04 02 04] - almost black (this is how the encoder decided)
[FC FE FC] - almost white
[FC 02 04] - almost red
[00 00 00] - in our example is not used.

Following bytes [2C] , which means that the section began

Image Descriptor [2C]

[00 00] [00 00] = (0, 0). Coordinates of the upper left corner in a logical screen
[04 00] [04 00] = 4x4. Image size
[00] = 00000000.
(0) = 0. local color table is not used.
(0) = 0. Interlace is not used (if 1, then the row order is changed, see Spec. Appendix E)
(0) = 0. local color table is not sorted.
(00) = 0. Reserved
(000) = 0. color resolution of the local color table.

Further, there may be additional sections in the file (I wrote below how to define them), but we don’t have them, and we’ve almost gotten to the coded data, and we are separated from them.

2 more bytes

For compression, the Lempel-Ziv-Welch algorithm is used . Below I will describe his work in a nutshell.

[02] The minimum length of the LZW code in bits (+1).
[07] The length of the data section. You ask: “How! Immediately there is only one byte, that is, the maximum length of 255? ". True, but there are an unlimited number of such sections. If the file is not over yet, after the end of the section, the byte will again be encountered with the length of the next section. The code may be cut by this byte. You need to memorize it to calculate the location of the next one.

LZW encoded image data.

The LZW algorithm requires this initialized dictionary. We have 4 colors in the table, so we add 4 values ​​(they will be color indexes):
0: {0} (black)
1: {1} (white)
2: {2} (red)
3: {3} (not used in our example)

For the gif version of LZW, 2 more control codes are added to the end (values ​​can be not added, just reserve a place):
4: {clear}
5: {end}

We continue. The following 7 bytes: [84 62 18 2A 10 5D 00] . You need to translate them into a binary representation.

[84] 10000100
[62] 01100010
[18] 00011000
[2A] 00101010
[10] 00010000
[5D] 01011101
[00] 00000000

These are codes that are simply recorded in succession. But from right to left! Just count the number of bits to the right and take that number. And if the byte is over, then we add the number (with the remaining number of bits) from the second byte to the already partially received value in front. In practice, it will be clearer.
We learned that the minimum length of the LZW code in bits is 2. But we need to add another 1, i.e. 3. This means that the current size of the code is 3, and initially it will be read in so many bits.

Brief description of the algorithm:

1. We read the next code.
2. In the dictionary, under the number equal to the code, take a list of indexes. These are ready-made color indexes.
3. A list of indexes is added to the dictionary, taken from the dictionary at the previous stage with the first index added taken from the dictionary at the current stage.

(100) 4. In the dictionary number 4 is the clear code. So we initialize the dictionary, set the current code size to 3 (in our example, of course). In files it is more this code to meet often.
(000) 0. In the dictionary number 0, there is {0}, this is already a ready color index (upper left corner). We do not add anything to the dictionary.
(010) 2. In the dictionary number 2 is {2}. Add {0} + {2} = {0,2} with number 6 (hereinafter I will use a shorter record: 2: {2}, +6: {0,2})
(001) 1. In the dictionary number 1 is {1}. Add {2} + {1} = {2,1} with number 7 (+7: {2,1})

The dictionary has reached the limit for 3-bit codes. The current code size is increased by 1.
(0110) 6: {0,2} +8: {1,0}
(1000) 8: {1,0} +9: {0,2,1}
(0001) 1: {1} +10:{1,0,1}
(1010) 10:{1,0,1} +11:{1,1}
(0010) 2: {2} +12:{1,0,1,2}
(0000) 0: {0} +13:{2,0}
(0001) 1: {1} +14:{0,1}
(1101) 13:{2,0} +15:{1,2}

The dictionary has reached the limit for 4-bit codes. The current size of the code is increased by 1 (the length of the code increases to a maximum of 12! When the dictionary reaches size 4096, the code length remains equal to 12, and you do not need to add anything to the dictionary. Usually there is a clear code)
(00101) 5:{end} end

We write down the obtained indices from left to right, from top to bottom (considering the size of the 4x4 picture)
0210
2101
1012
0120

The picture is already guessed! It is already clear that it remains to see what color is behind each index and display it on the screen. And we still have 2 bytes:
[00] one more end.
[3B] exactly the end :)

Extensions

Between the Image Descriptor section and LZW encoded image data there can be several more sections. There is information about the animation, commentary, some application data, etc. They are determined by the marker [21] [XX]. Description see specification. I described only the very minimum, but the processing of additional sections is not a problem, besides, most can be safely skipped.

useful links

Algorithm of Lempel _ — _ Ziva _ — _ Welch
Graphics Interchange Format
GIF89a specification