Deflate algorithm on an example of PNG format

As part of the next laboratory work, my colleagues and I were faced with the task of parsing the hexadecimal dump of the PNG file . According to the RFC 2083 standard, the PNG format stores pixel data compressed by the Deflate algorithm . Therefore, when parsing the dump, we needed to decompress the compressed data using the Inflate algorithm.

The analysis is carried out on the following 4x4 pixel image:



Data streams compressed using Deflate standard RFC 1951 are stored in PNG in zlib format of RFC 1950 standard , we will use this standard for parsing. The zlib header defines Deflate settings. It has the following structure:

1 byte		1 byte			4 bytes
CMF		Flg			Dictid
4 bits	4 bits	2 bits	1 bit	5 bit
Cinfo	CM	FLEVEL	Fdict	Fcheck

More about fields:

• CMF (Compression method and flags). This byte is divided into 2 cells with 4 bits each: CM (Compression method), CINFO (Compression info).
• CM (Compression method). This field defines the compression method used in the file. CM = 8 means Deflate is used with window sizes up to 32 kilobytes.
• CINFO (Compression info). When CM = 8, CINFO is the base 2 logarithm that sets the window size to minus 8 (CINFO = 7, sets the window size to 32 kilobytes).
• FLG (Flags). This byte is divided into parts as follows: FCHECK, FDICT, FLEVEL.
• FCHECK (check bits for CMF and FLG). Consider the value of the expression sum = (CMF * 256 + FLG) as a sixteen-bit unsigned integer. This field complements FLG so that sum is a multiple of 31.
• FDICT (Preset dictionary). If this flag is set, then the DICT dictionary descriptor immediately follows the FLG byte. The unpacker can use the value of this field to determine the dictionary used during compression.
• FLEVEL (Compression level). This field is used by special compression algorithms. Deflate (CM = 8): 0 - the fastest compression, 1 - fast compression, 2 - default compression, 3 - maximum compression (most slowly). The value of this field is not taken into account when unpacking. Used to indicate whether additional compression makes sense.

After DICT (if FDICT is installed), there is a stream of compressed data, the length of which for PNG depends on the CHUNK_LENGTH field of the IDAT structure. At the end of the zlib batch is the ADLER-32 checksum calculated from the uncompressed data using the Adler-32 algorithm.

In our case, the zlib header looks like this:

78 DA	0111	1000	eleven	0	11010
	Window size = 32K	Compression method = Deflate	Compression level = fastest	Dictionary is used = false	Check bits

From the header we find out that the dictionary is not used (FDICT = 0).

Compressed data for our picture:

63 F8 3F 93 E1 3F 03 C3 CC FF 20 1A C8 00 22 24 0E 58 12 85 33 D3 F8 3F 03 32 07 44 03 00 AA 05 23 77 The

bits are then read continuously by bytes. In the byte, we go from the last bit to the first (for example, in the data stream 2 bytes go sequentially: 63 F8 (0b01100011 0b11111000), then you should get the following bit sequence: 1100011000011111).

The first bit in the read sequence is the BFINAL flag, indicating whether this piece of data is the last. The next 2 BTYPE bits indicate the type of compression: 00 - without compression, 01 - compression with fixed Huffman codes, 10 - compression with dynamic Huffman codes, 11 - the value is reserved.

Table for fixed Huffman codes:

Unpacked value	Number of bits	Codes	base
0 - 143	8	From 00110000 to 10111111	00110000
144 - 255	9	From 110010000 to 111111111	110010000
256 - 279	7	From 0000000 to 0010111	0000000
280 - 287	8	11000000 to 11000111	11000000

Offset table:

Codes	Add. bits	Distance	Codes	Add. bits	Distance	Codes	Add. bits	Distance
0	0	1	10	4	33 - 48	20	9	1025 - 1536
1	0	2	eleven	4	49 - 64	21	9	1537 2048
2	0	3	12	5	65 - 96	22	10	2049 - 3072
3	0	4	thirteen	5	97 - 128	23	10	3073 - 4096
4	1	5, 6	14	6	129 - 192	24	eleven	4097 - 6144
5	1	7, 8	fifteen	6	193 - 256	25	eleven	6145 - 8192
6	2	9 - 12	16	7	257 - 384	26	12	8193 - 12288
7	2	13 - 16	17	7	385 - 512	27	12	12289 - 16384
8	3	17-24	18	8	513 - 768	28	thirteen	16385 - 24576
9	3	25 - 32	19	8	769 - 1024	29th	thirteen	24577 - 32768

Length table:

Codes	Add. Bits	Length	Codes	Add. Bits	Length	Codes	Add. Bits	Length
257	0	3	267	1	15, 16	277	4	67 - 82
258	0	4	268	1	17, 18	278	4	83 - 98
259	0	5	269	2	19 - 22	279	4	99 - 114
260	0	6	270	2	23 - 26	280	4	115 - 130
261	0	7	271	2	27 - 30	281	5	131 - 162
262	0	8	272	2	31 - 34	282	5	163 - 194
263	0	9	273	3	35 - 42	283	5	195 - 226
264	0	10	274	3	43 - 50	284	5	227 - 257
265	1	11, 12	275	3	51 - 58	285	0	258
266	1	13, 14	276	3	59 - 66

When unpacking, data can be represented by two types: a fixed value and the length of the reverse bias.

The data that we read must be converted to fixed values. The translation formula is presented below:

lit value = data - base + left bound, where
lit value is a fixed value,
base is a column from table 1,
left bound is a left number from a column of unpacked values ​​from table 1.

When reading data, we can unambiguously determine to which interval of fixed values ​​from table 1 it corresponds to the fact that the prefixes of each interval are different.

For example, let's choose 2 bytes F8 and 3F from our sequence. The sequence of bits that turned out to be 000 1111111111100. Let the current read position be 4, then read 7 bits (the minimum number of bits), we get the prefix 1111111, which corresponds to the interval 2. From this it turns out that the length of the read code is 9.

0b111111111 = 0d511

Using the formula above, we get that the number that was encoded is 255 = 511 - 400 (0b110010000) + 144.

Consider the case when instead of a fixed value, the data stream contains information about the length and reverse bias, i.e. the read value falls into the 3rd interval. In our version, this will be a subsequence:

20 1A C8 ( 0000010 0 01011000 00010011).

We read the first 7 bits (0b0000010), which fall into the interval 3. By the formula, translate into a number. This will be the number 257 = 1 - 0 + 256. Next, we use table 3. The code 257 means that the number of additional bits that must be counted is 0. And the length along the third column is 3. If there are additional bits, then they are read in the reverse order . These bits determine the number we add to the length.

Next, read 5 bits (0b00101 = 0d5), which determine the reverse bias. In our case, this is the number 5. From table 2 it is clear that we need to read 1 additional bit. We read it in the reverse order. It turned out 1 (0d1). We add this number to the minimum distance from column 3. And it follows that our reverse bias is 7 + 1 = 8.

What does this mean? For example, we counted 9 values: 0 255 153 0 255 0 0 153 255. The return distance shows how many values ​​we need to shift back in this stream, that is, we will be at the second value - 255. The length, which is equal to 3, indicates that we need to take 3 values ​​from the data stream, starting from the value on which we stand, ie 255 153 0. If the length is greater than the offset, then we return to the starting position and read again in the original order until we count the number of values ​​equal to the length. Suppose we have a length of 7, and the reverse bias is 2. We are shifted by 2 values, i.e. our position on the penultimate number is 153. The sequence that turned out is 153 255 153 255 153 255 153. Ultimately, when the unpacker reads the next fixed value, equal to zero,

Full dump analysis:

01100011 FINAL CHUNK, FIXED HUFFMAN 11111000 48 - 48 + 0 = 0 - FILTER: NONE 00111111 511 - 400 + 144 = 255 10010011 409 - 400 + 144 = 153 11100001 48 - 48 + 0 = 0 00111111 511 - 400 + 144 = 255 00000011 48 - 48 + 0 = 0 11000011 48 - 48 + 0 = 0 11001100 409 - 400 + 144 = 153 11111111 511 - 400 + 144 = 255 00100000 2 - 0 + 256 = 258 LENGTH = 4 00011010 5 DISTANCE = 7 + 1 = 8 11001000 1 - 0 + 256 = 257 LENGTH = 3 00000000 6 DISTANCE = 9 + 0 = 9 00100001 1 - 0 + 256 = 257 LENGTH = 3, 2 DISTANCE = 3 00100100 9 - 0 + 256 = 265 LENGTH = 11 + 0 = 11 00001110 7 DISTANCE = 13 + 0 = 13 01011000 3 - 0 + 256 = 259 LENGTH = 5 00010010 9 DISTANCE = 25 + 4 = 29 10000101 10 - 0 + 256 = 266 LENGTH = 13 + 0 = 13 00110011 7 DISTANCE = 13 + 0 = 13 11010011 409 - 400 + 144 = 153 11111000 99 - 48 + 0 = 51 00111111 511 - 400 + 144 = 255 00000011 48 - 48 + 0 = 0 00110010 9 - 0 + 256 = 265 LENGTH = 11 + 1 = 12 00000111 7 DISTANCE = 13 + 0 = 13 01000100 2 - 0 + 256 = 258 LENGTH = 4 00000011 5 DISTANCE = 7 + 1 = 8 00000000 0 - 0 + 256 = 256 END 10101010 ADLER 00000101 ADLER 00100011 ADLER 01110111 ADLER

0 255 153 0 255 0 0 153 255 255 153 0 255 255 0 0 255 0 0 0 153 255 255 153 0 255 255 0 0 255 255 153 0 255 0 255 153 0 255 255 0 0 255 255 153 0 255 0 153 51 255 0 255 0 0 255 255 153 0 255 0 153 51 255 255 153 0 255

The search for similar materials ultimately led to standards. We hope that this article will already help those in need in their own endeavors in their native and understandable Russian language.

Source image