File HuffmanCoder.h

↰ Parent directory (ADS/compression)

The code of Huffman of a string of bytes as the fast coders do it, beyond the canonical code of the notes [see File CanonicalHuffman.h], which decodes a bit at a time on a map of the symbols:

Definition (ADS/compression/HuffmanCoder.h)

Detailed Description

  • the lengths are the optimal ones of at most 11 bits, by the package-merge of Larmore and Hirschberg, in :math:` O( sigma L ) ` steps (the code of Huffman itself when its lengths fit), so that the decoding table, :math:` 2^{11} ` entries of 2 bytes, stays in the cache of level 1;

  • the code is canonical, and the preamble is the lengths of the 256 bytes, 4 bits each;

  • the codewords are written from the least significant bit of a word of 64 bits (the bits of a codeword turned around, so that the code stays prefix-free in the order of reading), 4 of them joined by shifts and written at once, whole bytes at a time;

  • the decoder peeks at W bits and finds in a table of :math:` 2^W ` entries of 32 bits the symbols whose codes fit whole in them, up to 3 in the low 24 bits, then their bits in 4 and their number in 2, so that a lookup costs two shifts and a mask and no branch (it decodes :math:` min( 3 , lfloor W / barell rfloor ) ` symbols or so for an average length :math:` barell ); W = 12 from :math: 2^{18} ` bytes on (a table of 16 KB, more symbols a lookup) and 11 below (half the table to build); 4 lookups of 12 bits at most fit in the bits of a word after a refill, so that a load serves 4 lookups;

  • the string is cut in four streams, decoded together, so that the four chains of dependences (a lookup gives the length, which gives the next lookup) overlap in the pipeline of the processor.

These are the decoders by tables of Moffat and Turpin, with the interleaved streams of Zstandard; the speed comes from the table and from the streams, the size of the code is that of Huffman, within one bit per byte of the entropy, :math:` H_0 le barell < H_0 + 1 ` [see File Entropy.h] (the limit of 11 bits costs a fraction of a percent on a text of bytes, the optimum under it being found exactly). A string of one distinct byte is written as that byte.

The format: the size n in 8 bytes, the longest length (0 for one distinct byte, which follows), the 128 bytes of the lengths, the sizes of the first three streams in 4 bytes each, the four streams, and 8 bytes of 0 that let a decoder load a word anywhere in its stream; the integers are little-endian.

The contracts [see File Contract.h]: huffmanDecompress() gets the output of huffmanCompress(), whose header (the lengths satisfy the inequality of Kraft, the sizes of the streams fit in the input) it checks; the audit of huffmanCompress() is that the output decompresses to the input. The functions are defined in HuffmanCoder.tpp.

  1. Collet, M. Kucherawy, Zstandard Compression and the ‘application/zstd’ Media Type, RFC 8878, 2021, doi:10.17487/RFC8878

    1. Larmore, D. S. Hirschberg, A fast algorithm for optimal length-limited Huffman codes, Journal of the ACM 37(3), 464-473, 1990, doi:10.1145/79147.79150

  1. Moffat, A. Turpin, On the implementation of minimum redundancy prefix codes, IEEE Transactions on Communications 45(10), 1200-1207, 1997, doi:10.1109/26.634683

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions