Gif inside

Have you ever wondered how gifs are arranged? In this article we will try to deal with the internal structure of the GIF format and the LZW compression method.

GIF structure

A GIF file consists of a fixed area at the beginning of the file, followed by a variable number of blocks, and the file ends with an image terminator.

The main characteristics of the format GIF:
')

The image in GIF format is stored line by line, only the format with an indexed color palette is supported;
Supports 256-color palette;
This format allows you to store multiple images in a single file;
GIF supports animated images;

Such images are a sequence of several static frames, as well as information about how long each frame should be shown on the screen. The animation can be made cyclic, then after the last frame, the first frame will start playing, and so on.
Supports "transparency";

One of the colors in the palette can be declared "transparent." In this case, in programs that support GIF transparency (for example, most modern browsers), the background will be visible through pixels that are colored with a “transparent” color. GIF animation can use transparency in order not to save the next frame as a whole, but only changes relative to the previous one.
A universal lossless LZW compression algorithm is used.

Example parsing

Consider parsing a dump of an animated GIF image of 4x4 pixels, consisting of two frames. And here are the frames themselves, increased tenfold.

Source image

Headline

At the beginning of each GIF file is a header. It consists of the text "GIF87a" or "GIF89a", depending on the version. In the GIF87a format, the variable region contains only image descriptions, and in the GIF89a format, it can also include extension blocks.

Logical Screen Descriptor

[04 00] [04 00] - the width and height of the virtual screen in pixels
[A2] -
(1) - M flag using global color table. If 1, then the global color table is present in the file.
(010) = 2 - CR flag. The number of bits of color resolution = CR + 1.
(0) - flag S (sorting flag). If 1, then the colors in the global color map are sorted in descending order of importance.
(010) = 2 - PIXEL flag. The size of the overall color table. Number of entries in the global color table: 2 ^ (N + 1).
[00] - Background color index.
[00] - Aspect ratio. The default is 1: 1.

Global color chart

[0A B2 5D] -

[C8 A6 2D] -

[F3 ED 63] -

[BA 60 A5] -

[00 80 C8] -

[F1 60 22] -

[00 00 00] -

[FF FF FF] -

After the global color table is the variable part of the GIF. The file contains a sequence of blocks, which are identified by a 1-byte code at the beginning of the block.

Block codes:
0x21 - Expansion
0x2 - Image block
0x3B - Completing a GIF File

Expansion unit

Expansion codes:
0x1 - plain text extension
0xF9 - graphics control extension
0xFE - comment extension
0xFF - program extension

[FF] - extension code. In our case, we have an extension of the program.
[0B] - the size of the next block in bytes.
[4E 45 54 53 43 41 50 45] - (NETSCAPE) The identifier of the application to which this extension belongs.
[32 2E 30] - (2.0) application code. With it, the application checks if this extension really belongs to it.
[03] - the size of the next block in bytes.
[01] - fixed value.
[00 00] - the value is 0..65535. Unsigned little-endian integer. Determines how many times the loop should repeat.
For 0 - infinite.
[00] - the end of the block.

[F9] - extension code (graphics control extension).
[04] - the size of the next block in bytes.
[04] -
(000) - reserved. It is recommended to fill with zeros.
(001) - processing method. Determines what to do after display.
0 - no processing will be applied to the image
1 - the picture will remain unchanged
2 - the picture is wiped by background
3 - the image under the picture will be restored
4-7 - not defined
(0) - user input flag. If 1, then to continue processing the image requires the reaction of the user.
(0) - flag color transparency. Indicates whether any color will be used as transparent.
[32 00] - time delay in animation. = 50/100 seconds = 0.5 s
[00] is the index of the color of transparency.
[00] - the end of the block.

Image block

[00 00] [00 00] is the row and column number. Defines the coordinates of the upper left corner of the logical screen. (0, 0).
[04 00] [04 00] - width and height of the image in pixels.
[00] -
(0) - flag of using local color table
(0) - flag interlaced. Indicates the order in which the image pixels are read.
0 - in rows from left to right, top to bottom
1 - order: 0th. 8th, 16th ... 4th, 12th, 24th ...
(0) - sorting flag of the local color table. If 1, then the colors in the local color map are sorted in descending order of importance.
(00) - reserved.
(000) - PIXEL flag. The size of the local color table, if any.

[03] - the minimum code size in LZW.
[08] - the size of the next block in bytes.
[08 0A D2 42 90 94 59 12] is a data block compressed with the LZW algorithm. Presented as a sequence of codes having a length [min. code size] + 1
[00] - the end of the data stream.

Parsing LZW algorithm

Frame 1

Dictionary / Code Table

The dictionary is initialized by the number of colors and the {clear} and {end} codes. We take the code with the length of the current size, we get its value from the dictionary. If the value is in the dictionary, then we get a ready color index for the current pixel and add the following value to the dictionary: the resulting previous + first of the current. If the dictionary does not yet have such a value, then add the previous + first of the previous one at this index. The first code must match the {clear} value, the last one - {end}

Solve the inverse problem. Take the original image data and encode it using the LZW algorithm. Under the source data we understand the sequence of color indices from the dictionary corresponding to each of the pixels. Piskels are viewed from top to bottom, from left to right.

Step	Action	Index stream	New Code Table Row	Code stream
one	Init	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		#eight
2	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		#eight
3	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 10 - 0 0	# 8 # 0
four	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0
five	Found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0
6	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0
7	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 11 - 0 0 0	# 8 # 0 # 10
eight	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10
9	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 12 - 0 2	# 8 # 0 # 10 # 0
ten	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0
eleven	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 13 - 2 2	# 8 # 0 # 10 # 0 # 2
12	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2
13	Found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2
14	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2
15	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 14 - 2 2 2	# 8 # 0 # 10 # 0 # 2 # 13
sixteen	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13
17	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 15 - 2 4	# 8 # 0 # 10 # 0 # 2 # 13 # 2
18	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2
nineteen	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 16 - 4 4	# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4
20	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4
21	Found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4
22	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4
23	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 17 - 4 4 4	# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16
24	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16
25	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 18 - 4 5	# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4
26	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4
27	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 19 - 5 5	# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4 # 5
28	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4 # 5
29	Found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4 # 5
thirty	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4 # 5
31	Not found	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5	# 20 –5 5 5	# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4 # 5 # 19
32	Read	0 0 0 0 2 2 2 2 4 4 4 4 5 5 5 5		# 8 # 0 # 10 # 0 # 2 # 13 # 2 # 4 # 16 # 4 # 5 # 19 # 5 # 9

Now compare the coding result with the compressed data stored in the dump. The GIF format in this block stores multibyte integers with the low byte in the first place (direct byte order).

[08 0A D2 42 90 94 59 12] is a data block compressed with the LZW algorithm.

We do the same with the second frame.

Frame 2

Dictionary / Code Table

Step	Action	Index stream	New Code Table Row	Code stream
one	Init	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		#eight
2	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		#eight
3	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 10 - 3 6	# 8 # 3
four	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3
five	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 11 - 6 1	# 8 # 3 # 6
6	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6
7	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 12 - 1 7	# 8 # 3 # 6 # 1
eight	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1
9	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 13 - 7 3	# 8 # 3 # 6 # 1 # 7
ten	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7
eleven	Found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7
12	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7
13	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 14 - 3 6 1	# 8 # 3 # 6 # 1 # 7 # 10
14	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10
15	Found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10
sixteen	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10
17	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 15 - 1 7 3	# 8 # 3 # 6 # 1 # 7 # 10 # 12
18	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12
nineteen	Found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12
20	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12
21	Found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12
22	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12
23	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 16 - 3 6 1 7	# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14
24	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14
25	Found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14
26	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14
27	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 17 - 7 3 6	# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14 # 13
28	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14 # 13
29	Found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14 # 13
thirty	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14 # 13
31	Not found	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7	# 18 - 6 1 7	# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14 # 13 # 11
32	Read	3 6 1 7 3 6 1 7 3 6 1 7 3 6 1 7		# 8 # 3 # 6 # 1 # 7 # 10 # 12 # 14 # 13 # 11 # 7 # 9