Deflate Compression#

Supported Compressed Data Formats#

The Deflate standard organizes the compressed data into a series of “blocks”. Each block is defined by one of the three types:

  • Stored Block: The input data is stored in an uncompressed form.

  • Fixed Block: The input data is compressed with a fixed Huffman table defined by the standard. The fixed Huffman table is usually suboptimal, but in this case the compressed stream doesn’t need to include a set of Huffman codes.

  • Dynamic Block: The input data is compressed with a Huffman table that is optimized for that particular block. This results in a more efficient code, but requires two passes: one pass to analyze the data and gather its statistics, with which an optimal Huffman table can be generated, and another pass to compress the data with the optimal Huffman table.

Intel® Query Processing Library (Intel® QPL) includes a fourth type called Static Block, where the input data is compressed with a user-defined Huffman table which can differ from block to block. A static block, from the point of view of the Deflate standard, is a dynamic block. However, for static blocks, the Huffman tables are determined ahead of time and do not depend on the input data. Note that the compression can happen in one pass with a static block because the Huffman Table is provided by the application. The application is responsible for providing a suitable Huffman table for the data; otherwise, the compression ratio may be low.

Intel QPL provides another compression mode called Canned, which, like static compression, compresses the input data with a user-defined Huffman table. But it does not write the 3-bit Deflate header and the Huffman table to the output stream. This mode is useful when compressing many small buffers all with the same Huffman table. It offers the compression speed of static compression, with a better compression ratio (since it saves the bits used for the header and the Huffman table), and a faster decompression speed (since the same Huffman table does not need to be parsed multiple times).

Job Structure Settings#

This section introduces the basic settings of the job structure for Deflate compression jobs using different available modes. In the code snippets below, it is assumed that a single job is used, for details on how to divide workload into multiple jobs submissions, refer to Compression and Decompression across Multiple Jobs.

Warning

The compression mode cannot be changed across related jobs. For example, it is not supported to start a sequence of jobs using Dynamic Compression and then switch to Static Compression halfway through the sequence.

Compression Level#

The job->level field selects a compression level from the qpl_compression_levels enumeration. Higher levels generally trade compression speed for a better compression ratio. Levels qpl_level_0 through qpl_level_9 are accepted, along with the aliases qpl_default_level and qpl_fast_level (both equal to qpl_level_1) and qpl_high_level (equal to qpl_level_7).

A requested level that exceeds what the execution path supports is automatically saturated to the highest supported level, so the same code runs correctly on any hardware:

Supported compression levels by execution path#

Execution path

Behavior

Software (ISA-L)

two operating points: levels 0-1 map to qpl_default_level (fast), levels 2-9 map to qpl_high_level (highest ratio ISA-L provides)

Hardware, Intel® In-Memory Analytics Accelerator (Intel® IAA) 3.0

levels 0-7 native; levels 8-9 saturate to level 7

Hardware, Intel® IAA 2.0 and earlier

default level only; every level behaves as qpl_default_level

On Intel® IAA 3.0, qpl_level_0 is a compatibility level; its compression ratio is comparable to the higher levels. On the software path qpl_level_0 behaves the same as qpl_default_level and still produces compressed (non-stored) output.

Note

The level does not affect the compressed data format: a stream produced at any level can be decompressed by any Deflate-compliant decompressor, on any path.

Long-Match Hint#

Setting the QPL_FLAG_LONG_MATCH_HINT flag on a compression job hints the compressor to search for 4-byte (long) matches instead of the standard 3-byte match. This may improve the compression ratio, but the improvement is not guaranteed and depends on the input.

job->op    = qpl_op_compress;
job->flags = QPL_FLAG_FIRST | QPL_FLAG_LAST | QPL_FLAG_LONG_MATCH_HINT;

The hint is available only on Intel® IAA 3.0 and later. On earlier hardware generations and on the software path the flag is silently ignored, so the same code runs correctly everywhere. Like the compression level, the hint does not affect the compressed data format.

Fixed Blocks#

The job structure for fixed compression can be set using:

job->op            = qpl_op_compress;
job->level         = qpl_default_level;   // see Compression Level above
job->next_in_ptr   = <input_buffer>;
job->available_in  = <input_size>;
job->next_out_ptr  = <output_buffer>;
job->available_out = <output_size>;
job->flags         = QPL_FLAG_FIRST | QPL_FLAG_LAST;
job->huffman_table = NULL;

Dynamic Blocks#

The job structure for dynamic compression can be set using:

job->op            = qpl_op_compress;
job->level         = qpl_default_level;   // see Compression Level above
job->next_in_ptr   = <input_buffer>;
job->available_in  = <input_size>;
job->next_out_ptr  = <output_buffer>;
job->available_out = <output_size>;
job->flags         = QPL_FLAG_FIRST | QPL_FLAG_LAST | QPL_FLAG_DYNAMIC_HUFFMAN;
job->huffman_table = NULL;

Static Blocks and Canned Mode#

The job structure for static compression can be set using:

job->op            = qpl_op_compress;
job->level         = qpl_default_level;   // see Compression Level above
job->next_in_ptr   = <input_buffer>;
job->available_in  = <input_size>;
job->next_out_ptr  = <output_buffer>;
job->available_out = <output_size>;
job->flags         = QPL_FLAG_FIRST | QPL_FLAG_LAST;
job->huffman_table = huffman_table;

The job structure for canned compression can be set using:

job->op            = qpl_op_compress;
job->level         = qpl_default_level;   // see Compression Level above
job->next_in_ptr   = <input_buffer>;
job->available_in  = <input_size>;
job->next_out_ptr  = <output_buffer>;
job->available_out = <output_size>;
job->flags         = QPL_FLAG_FIRST | QPL_FLAG_LAST | QPL_FLAG_CANNED_MODE;
job->huffman_table = huffman_table;

The Huffman table object huffman_table can be allocated by qpl_deflate_huffman_table_create() and initialized with literal/length and distance histograms through qpl_huffman_table_init_with_histogram(). Refer to the Huffman Table Objects section for more information.

If the stream is compressed with multiple jobs, then in the middle of the stream, the application can specify a different Huffman table and use the QPL_FLAG_START_NEW_BLOCK flag. This will instruct the library to end the current block and to start a new block with the new table. The QPL_FLAG_START_NEW_BLOCK is not needed on the first job (i.e., this flag is implied when QPL_FLAG_FIRST is set).

If the QPL_FLAG_START_NEW_BLOCK flag is not used, then the table pointed to in the job structure must be the same as those used by the previous job. If the tables are changed without signaling the library with the appropriate flags, the resulting bit-stream will not be valid.

Attention

The current implementation does not support canned compression across multiple jobs, thus canned compression jobs must specify the flags QPL_FLAG_FIRST | QPL_FLAG_LAST.

Structure of Compressed Data#

Dynamic Blocks#

On the hardware_path, the data from one job will be compressed as a single dynamic block when the data is compressible, or as multiple stored blocks when the data is incompressible. The data from one job may be compressed as multiple dynamic blocks on the software path.

Static Blocks#

The structure of compressed data using static compression is similar to what was described in Fixed Blocks, except that there can be multiple static blocks between stored blocks due to the change of a Huffman table using QPL_FLAG_START_NEW_BLOCK.

Canned#

Canned compression only writes the body of one static block to the output buffer. If the input data is incompressible, even when the size of the output buffer is enough for a stored block, the library returns the QPL_STS_MORE_OUTPUT_NEEDED status.

Compression Output Overflow#

If the compressed output does not fit into the output buffer (e.g., a bad Huffman table is provided by the application, causing data to expand in a static compression), the library attempts to copy the input data into the output stream as a series of stored blocks. When the stored blocks fit into the output buffer, the library writes them to the output buffer and returns the successful QPL_STS_OK status. If the stored blocks do not fit, the library returns the QPL_STS_MORE_OUTPUT_NEEDED status and the compression fails.

Attention

Currently, Intel QPL does not have an API to return maximum compressed size for a given source size. To avoid getting QPL_STS_MORE_OUTPUT_NEEDED for incompressible source data, users are suggested to use an output buffer with a size slightly larger than the size of the input buffer so that it can accommodate the additional headers for stored blocks. This suggestion does not apply to canned compression (see Canned).

Compression Verification#

By default, the library will verify the correctness of the generated compressed bit stream. The library decompresses the resulting bit stream, and then checks that the CRC of the decompressed data matches the CRC of the original data. If the user does not want to pay the additional performance cost for verification, the step can be skipped with the QPL_FLAG_OMIT_VERIFY flag.

Attention

Currently verification is not performed for Huffman-only compression on the hardware path. For more information on Huffman-only, see Huffman-Only Compression and Decompression.