Zlib compressed data

Zlib compression is commonly used in file formats. The zlib compressed data format, as defined in RFC1950, allows for multiple techniques but only the Deflate compression method, a variation of LZ77, is used.

Overview

Zlib compressed data consist of:

• data header
• compressed data
• Adler-32 checksum of the uncompressed data

Characteristics

Data header

The data header is 2 or 6 bytes in size and consist of:

The check bits value must be such that when the first 2 bytes are represented as a 16-bit unsigned integer in big-endian byte order the value is a multiple of 31, such that:

((first * 256) + second) % 31 = 0

Compression method

Note that RFC1950 only defines 8 as a valid compression method.

Compression information

The value of the compression information is dependent on the compression method.

Compression information - compression method 8 (Deflate)

For compression method 8 (Deflate) the compression information contains the base-2 logarithm of the LZ77 window size minus 8.

To determine the corresponding window size:

1 << (7 + 8)

E.g. a compression information value of 7 indicates a 32768 bytes window size. Values larger than 7 are not allowed according to RFC1950 and thus the maximum window size is 32768 bytes.

Compression level

Compressed data

Deflate compressed data

The deflate compressed data consists of one or more deflate compressed blocks. Each block consists of:

• block header
• block data

Note that a block can reference uncompressed data that is stored in a previous block.

Block header

The block header is 3 bits in size and consists of:

Block types

Uncompressed block data

The uncompressed block data is of variable size and consists of:

The uncompressed data size can range between 0 and 65535 bytes.

Huffman compressed block data

The uncompressed block data is of variable size and consists of:

• Optional dynamic Huffman table
• Encoded bit-stream
• End-of-stream (or end-of-block or end-of-data) marker

Dynamic Huffman table

The dynamic Huffman table consists of:

A single code size value is 3 bits of size. A value of 0 means the code size is not used in the Huffman encoding of the literal and distance codes.

The codes size values are stored in the following sequence:

16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

The first value applies to a code size of 16, the second to 17, etc. Code sizes that are not stored default to 0.

The code size values are used to construct the code sizes Huffman table. This must be a complete Huffman table which is used to decode the literal and distance codes. The corresponding codes size Huffman encoding is defined as:

Both the literal and distance Huffman codes are stored Huffman encoded using the code sizes Huffman table. Code sizes that are not stored default to 0. The code size for the literal code 256 (end-of-block) should be set and thus not 0.

Encoded bit-stream

The encoded bit-stream is stored in 8-bit integers, where bit values are stored back-to-front. So that 3 least-significant bits (LSB) would represent a 3-bit value at the start of the -stream. Note that the LSB of the 3-bit value is the LSB of the byte value.

Deflate uses a Huffman tree of 288 Huffman codes (or symbols) where the values:

• 0 - 255; represent the literal byte values: 0 - 255
• 256: represents the end of (compressed) stream (or block)
• 257 - 285 (combined with extra-bits): represent a (size, offset) tuple (or match length) of 3 - 258 bytes
• 286, 287: are not used (reserved) and their use is considered illegal although the values are still part of the tree

This document refers to this Huffman tree as the literals Huffman tree.

The bits in the encoded bit-stream correspond to values in the literals Huffman tree. If a symbol is found that represents a compression size and offset tuple (or match length code) the bits following the literals symbol contains a distance (Huffman) code. The match length coedes might require additional (or extra) bits to store the length (or size).

The distances Huffman tree contains space for 32 symbols. See section Distance codes. The distance code might require additional (or extra) bits to store the distance.

Literal codes

The literal codes consist of:

Distance codes

The distance codes consist of:

TODO: complete this section

Additional bits

The additional bits are stored in big-endian (MSB first) and indicate the index into the corresponding array of size values (or base size + additional size).

TODO: complete this section

Decompression

The decompression in pseudo code:

if block_header.type == HUFFMANN_FIXED:
{
    initialize the fixed Huffman trees
}

do
{
    read block_header from input stream

    if( block_header.type == UNCOMPRESSED )
    {
        align with next byte
        read and check block_header.size and block_header.size_copy
        read data of block_header.size
    }
    else
    {
        if( block_header.type == HUFFMANN_DYNAMIC )
        {
            read the dynamic Huffman trees (see subsection below)
        }
        loop (until end of block code recognized)
        {
            decode literal/length value from input stream
            if( value < 256 )
            {
                copy value (literal byte) to output stream
            }
            else if value = end of block (256)
            {
                 break from loop
             }
             else (value = 257..285)
             {
                 decode distance from input stream

                 move backwards distance bytes in the output
                 stream, and copy length bytes from this
                 position to the output stream.
            }
        }
    }
}
while( block_header.last_block_flag == 0 );

Adler-32 checksum

Zlib provides a highly optimized version of the algorithm provided below.

uint32_t adler32(
          uint8_t *buffer,
          size_t buffer_size,
          uint32_t previous_key )
{
    size_t buffer_iterator = 0;
    uint32_t lower_word    = previous_key & 0xffff;
    uint32_t upper_word    = ( previous_key >> 16 ) & 0xffff;

    for( buffer_iterator = 0;
         buffer_iterator < buffer_size;
         buffer_iterator++ )
    {
        lower_word += buffer[ buffer_iterator ];
        upper_word += lower_word;

        if( ( buffer_iterator != 0 )
         && ( ( buffer_iterator % 0x15b0 == 0 )
          ||  ( buffer_iterator == buffer_size - 1 ) ) )
        {
            lower_word = lower_word % 0xfff1;
            upper_word = upper_word % 0xfff1;
        }
    }
    return( ( upper_word << 16 ) | lower_word );
}

References

• RFC1950 - ZLIB Compressed Data Format Specification
• RFC1951 - DEFLATE Compressed Data Format Specification