GDEFLATE bitstream specification

2.1. DEFLATE64 extensions

GDeflate directly integrates DEFLATE64 extensions (which were not originally included in RFC 1951), allowing longer copies with distance references spanning a range of up to 64KB. These extensions comprise the following modifications: first, length code 285 is re-purposed to represent an LZ copy of length in the range between 3 and 65538 bytes. 16 extra bits of unencoded length value follow this code. Second, two previously unused distance codes 30 and 31 are now used to represent look back distances of up to 65536 bytes. They are followed with 14 extra bits of unencoded distance value, specifying distances in the range of 32769 to 49152 and 49153 to 65536 bytes, respectively.¶

For completeness, modified tables of length and distance codes are included below. Changes relative to the original tables (refer to section 3.2.5 in RFC 1951) are highlighted:¶

Length codes:¶

Distance codes:¶

2.2. Formatting of non-compressed blocks

GDeflate also changes formatting of non-compressed blocks (BTYPE=00, refer to section 3.2.4 in RFC 1951). In the original DEFLATE algorithm, non-compressed blocks start with a block-specific header specifying their length in bytes as a 16 bit value, followed by its one's complement. The header is also specified to start on a byte-aligned boundary. In GDeflate, the one's complement of length is dropped from the header and the header is no longer required to be byte-aligned. As a result, data across all blocks, compressed or non-compressed, forms one contiguous bit stream. This streamlines SIMD decoding of the entire bit stream, as will be explained later.¶

5.1. Sub-streams and ordering of symbols

To enable parallel parsing of the bit stream, GDeflate splits the original sequence of variable-length codes into 32 independent sub-streams. Each sub-stream is assigned to a fixed SIMD lane, so all lanes in the SIMD group can collectively parse all 32 sub-streams in parallel. Each iteration of the parsing process is referred to as "SIMD round". At each SIMD round, 32 codes from 32 sub-streams are decoded into symbols, with one code processed in each lane (with some exceptions detailed in the following sections).¶

Within a SIMD round, decoded symbols follow the SIMD lane order. For example, symbols corresponding to entropy-coded data within compressed blocks (literal bytes and LZ copies) which are processed within the same round always map to a contiguous range of memory addresses in the output buffer: this allows all decoded symbols to be written as a dense SIMD memory write (assuming each SIMD lane computes its output pointer accordingly). Once a SIMD round is complete, the SIMD group proceeds to the next round, decoding the next group of 32 symbols from 32 sub-streams, advancing its input and output pointers. Thus, across SIMD rounds, corresponding groups of 32 symbols follow sequentially.¶

5.2. Packing of variable-length codes within sub-streams

To enable concurrent processing of sub-streams, GDeflate packs the variable-length codes, comprising individual sub-streams into a set of naturally aligned 32 bit words, which can be directly addressed by the SIMD group. As a result, the bit stream is always accessed at word granularity: at each SIMD round, at most a single aligned 32 bit word is read from each sub-stream (therefore, at most 32 memory reads can be performed during a round across all lanes). These reads are done on as-needed basis: each lane keeps track of the number of bits it is yet to decode from the previous SIMD round, and when that number drops below a threshold, a memory read on the current SIMD round is scheduled. The bits returned by the new memory read are appended to the bits remaining to be decoded in that lane, so that the lane can proceed to decoding a symbol. Once a symbol is decoded, its corresponding code is consumed, reducing the number of bits available for decoding on the next round, which will eventually trigger another memory read in one of the subsequent rounds.¶

In GDeflate, the longest possible code contains 31 bits: 15 bits of the worst-case Huffman code (per DEFLATE spec) plus maximum of 16 extra bits (this could happen for the length symbol of a long LZ copy). Consequently, the memory read threshold in GDeflate is set to 32 bits (rounding up). This ensures that at any time during parsing, at least 32 bits of the sub-stream data are immediately available for decoding in each lane, and hence at least one symbol per lane can be fully decoded on each SIMD round.¶

Note that as a result of this packing, variable-length codes may be split across words. However, no variable-length code (including any extra bits it may require) can span more than 2 words, so reading a single word always adds enough data to guarantee that at least 1 symbol can be decoded per lane.¶

It is expected that implementations will maintain this per lane state in a pair of 32 bit registers and a counter variable tracking how many bits are currently valid. When the number of valid bits in the state variable drops below 32, a new 32 bit word is read from memory and appended to the state variable. Corresponding memory addresses for these reads can be computed by cooperative data-parallel operations across the SIMD group, such as prefix sums. Bits consumed during decoding can be removed from the state variable by shifting the register pair down.¶

The following pseudocode illustrates the process of reading the bitstream:¶

// For each SIMD lane in parallel ...

uint64_t bitBuffer; // State variable
uint     bitCount;  // Number of valid bits in the state variable

bool isRefillRequired = bitCount < 32;  // Generate refill predicate
                                        // for this lane

uint32_t refillMask = vote(isRefillRequired);   // Collect refill
    // predicates across all lanes into a mask

// Compute this lane's offset as a prefix sum over refill mask
uint localOffset = countbits(refillMask & ((1 << lane) - 1));

if (isRefillRequired) { // On a refill ...
    // ... Append new bits to the state variable
    bitBuffer |= (uint64_t)input[localOffset] << bitCount;
    bitCount += 32; // ... Track the number of valid bits available
}

// Lane 0 advances shared input pointer
if (lane == 0) input += countbits(refillMask);

// Proceed to decoding variable-length codes contained in
// LSBs of bitBuffer

5.3. Initial decoder state and formatting of the final bit stream

At the start of decoding, state variables in all SIMD lanes are initialized to contain 0 bits. Therefore, the first SIMD round of decoding always loads 32 consecutive words from the input stream, effectively initializing state variables of all 32 sub-streams. As a result, any valid GDeflate bit stream cannot be smaller than 4 * 32 = 128 bytes. Subsequent rounds will load variable number of words from the input, depending on the rate at which each SIMD lane consumes codes from the sub-stream it is responsible for.¶

The final bit stream comprises words from the 32 sub-stream interleaved in the order in which they are read during decoding. Note that this reordering/interleaving applies end-to-end across all blocks in the bit stream, disregarding block boundaries. Effectively, GDeflate treats the entire bit stream as a contiguous sequence of variable-length codes, permuted and packed into sub-streams as described above. Words residing at the very end of the bit stream may not be fully packed with variable-length codes, which means leaving some available bits unused. This tail effect represents certain small overhead introduced by the SIMD-oriented rearrangement of data in the bit stream.¶

5.4. Parsing example

To illustrate the parsing process, consider the following bit stream layout. The numbers indicate byte addresses of corresponding 32 bit words in the bit stream. Letters represent variable-length codes packed within their respective words. Note that some codes are split across two words - this is indicated with a dot to the left or to the right of the corresponding letter. The sets of 32b words loaded on each SIMD round are shown underneath the boxes.¶

0       4       8       12     124     128
+-------+-------+-------+-     -+-------+
|A,B,C. | D,E.  |F,G,H,I|  ...  | J,K.  |
+-------+-------+-------+-     -+-------+
|<----------- SIMD round 0 ------------>|


128     132     136     252     256     K      K+4     K+8
+-------+-------+-     -+-------+-    -+-------+-------+-------+
|  .C,L |.E,M,N |  ...  | .K,O  |  ... | X,Y.  |   Z.  |  .W   |
+-------+-------+-     -+-------+-    -+-------+-------+-------+
|<------- SIMD round 1 -------->|      |<--- SIMD round N ---->|

On the very first SIMD round, the decoder loads the initial set of 32 words from the input stream, at contiguous memory addresses spanning the first 128 bytes. This initializes per-lane state variables in each SIMD lane with 32 bits of input data, which contain packed variable-length codes. On this first round, the SIMD group processes codes A,D,F...J (in that order) which all come from 32 separate sub-streams. Processed codes are removed from their respective per-lane state variables. At that point, the number of valid bits available for decoding in each lane drops below 32, and hence on the second round each lane loads another 4-byte word of input, which reside at addresses 128 through 252 in the input stream, appending loaded bits to the valid bits remaining from the first round. On the second round, codes B,E,G...K from the 32 sub-streams are processed by the SIMD group. Note that code E was split across two words, residing at byte addresses 4 and 132. On the second round, all bits of E become available in the lane #1's state variable, hence it can be fully decoded on that round. The same situation applies to code K, split across words at addresses 124 and 252. At the end of the second round, the codes were processed in the following order: A,D,F...J,B,E,G...K.¶

The decoding process continues, however on subsequent rounds the SIMD group will likely be loading fewer than 32 words of input. In our example, on round N the SIMD group loads only 3 additional words, at byte addresses K through K+8. Which lanes perform these loads is a function of the number of valid bits remaining in per-lane state from previous rounds, which is in turn a function of how many variable-length codes were packed in the corresponding sub-stream processed by that lane so far. In essence, each sub-stream is represented by a chain of 32b words scattered in the input stream. All lanes in the SIMD group collectively traverse 32 such sub-streams, cooperatively computing memory addresses for each lane from round to round.¶

8.1. Code lengths for the huffman trees alphabet

In blocks compressed with dynamic huffman codes, the header is followed by an array of up to 19 three bit values, specifying code lengths for the code length alphabet used to describe the huffman trees. Each code length value gets assigned to a separate sub-stream, and hence SIMD lane, therefore all code length values are processed within a single SIMD round. At least 32 - 19 = 13 SIMD lanes remain inactive in this round and do not modify their state variables. The actual number of sub-streams used (and hence the number of SIMD lanes that participate in this round) is specified in the header (value of field HCLEN + 4). Each active lane decodes a fixed-length 3 bit code on this round before the SIMD groups proceeds to the next section.¶

8.2. Huffman trees meta-data

Block-specific huffman trees represented in the form of compressed arrays of code length values for literal/length and distance tables are encoded next in the bitstream. There can be up to 318 symbols in this section (up to 286 literal/length symbols plus up to 32 distance symbols), encoded with variable-length codes. These codes are evenly distributed across 32 sub-streams and require up to 10 (corresponding to the maximum of 318 symbols) SIMD rounds to process. The ordering of symbols in this section follows the rules described in section 5: each SIMD round processes a group of 32 consecutive symbols, with groups ordered sequentially as they are processed.¶