File Tans.h

↰ Parent directory (ADS/compression)

The tabled variant of the asymmetric numeral systems of Duda (tANS), the entropy coder of order 0 of Zstandard (RFC 8878), beside the range variant [see File Rans.h]: the transitions of the state are read from tables, so that a symbol costs a lookup, a shift and an addition, and no multiplication.

Definition (ADS/compression/Tans.h)

Detailed Description

With :math:` L = 2^R ` states, R = 11, and the frequencies :math:` f_s ` of the bytes scaled to sum to L (each byte of the string kept at 1 at least [see File Rans.h]), the L states are dealt to the symbols, :math:` f_s ` each, by the step :math:` L / 2 + L / 8 + 3 ` modulo L, which visits them all (it is odd) and spreads the states of a symbol over the table. The decoder in the state :math:` x in [ 0 , L ) ` of the symbol s, its i-th one, emits s and moves to :math:`[ x’ = ( ( f_s + i ) 2^{b} - L ) + r , qquad

b = R - lfloor log_2 ( f_s + i ) rfloor , ` r the next b bits of the stream; the encoder in the state :math:` X in [ L , 2 L ) ` emits the low k bits of X, k the number that brings :math:` X / 2^k ` into :math:` [ f_s , 2 f_s ) ` (one of two values, found by one addition and a shift), and moves to L plus the state of the :math:` ( X / 2^k - f_s ) -th place of s. A symbol costs about :math: log_2 ( L / f_s ) ` bits, and the code comes within a fraction of a percent of :math:` n H_0 ` [see File Entropy.h] for :math:` L ` a few times the alphabet (Duda; Dube and Yokoo for the analysis of the spread).

The string is cut in two halves, each with a stream of bits of its own and four states that take its symbols in turn; a stream is written forward from the low bit of a word and read backward from its end, 4 symbols of 11 bits at most between two loads of the reader, and the two halves are decoded together, so that their chains of dependences overlap. The encoder works from the last symbol to the first, so that the decoder, which reads the stream from its end, meets the bits in the order of the symbols.

The format: the size n in 8 bytes, the 256 scaled frequencies in 2 bytes each, the bits of the two streams in 8 bytes each, the streams (the 4 final states of the encoder at the end of each, R bits each) and 8 bytes of 0; the integers are little-endian.

The contracts [see File Contract.h]: tansDecompress() gets the output of tansCompress(), whose header (the frequencies sum to L, the bits of the stream fit in the input) it checks; the audit of tansCompress() is that the output decompresses to the input. The functions are defined in Tans.tpp.

  1. Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv:1311.2540, 2013

  1. Duda, K. Tahboub, N. J. Gadgil, E. J. Delp, The use of asymmetric numeral systems as an accurate replacement for Huffman coding, Proc. 31st Picture Coding Symposium (PCS 2015), 65-69, 2015, doi:10.1109/PCS.2015.7170048

  1. Dube, H. Yokoo, Fast construction of almost optimal symbol distributions for asymmetric numeral systems, Proc. IEEE ISIT 2019, 1682-1686, 2019, doi:10.1109/ISIT.2019.8849430

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/compression/Rans.h (File Rans.h)

  • ADS/compression/impl/Tans.tpp

  • array

  • bit

  • cstddef

  • cstdint

  • span

  • vector

Namespaces

Functions