File Rans.h

↰ Parent directory (ADS/compression)

The range variant of the asymmetric numeral systems of Duda (rANS), the entropy coder of order 0 of the fast compressors, beyond the arithmetic code of the notes [see File ArithmeticCoding.h]: it reaches the size of the arithmetic code, within a fraction of a percent of :math:` n H_0 ` [see File Entropy.h], at the speed of a table of Huffman.

Definition (ADS/compression/Rans.h)

Detailed Description

The state is an integer x, and a symbol s of frequency :math:` f_s ` and cumulative frequency :math:` c_s ` over a total :math:` M = 2^{12} ` moves it to :math:` C( s , x ) = M lfloor x / f_s rfloor + c_s + x bmod f_s , which grows x by a factor :math: M / f_s , i.e., by :math: log_2 ( M / f_s ) ` bits, the information of s; the decoder inverts it, :math:` s ` being the symbol whose range :math:` [ c_s , c_s + f_s ) ` holds :math:` x bmod M ` (a table of M entries) and :math:` x = f_s lfloor x / M rfloor + x bmod M - c_s . The state is kept in :math: [ 2^{16} , 2^{32} ) ` by moving 16 bits at a time to the stream (renormalization), at most once per symbol; the decoder reads them back in the opposite order, so that the encoder works from the last symbol to the first. Unlike the arithmetic coder, which narrows an interval and emits its common bits, the state needs one multiplication per symbol and no division in the decoder, and its renormalization has no carry.

Four states take the symbols in turn, so that four chains of dependences overlap in the pipeline of the processor (the interleaving of Giesen); they share one stream. The frequencies are scaled to M with each byte of the string kept at 1 at least, which costs a fraction of a percent on a string of bytes; the tabled variant [see File Tans.h] makes the state transitions a lookup and needs no multiplication, at the price of a table per alphabet built in the encoder too.

The format: the size n in 8 bytes, the 256 frequencies scaled to M in 2 bytes each, the four final states in 4 bytes each, the stream of 16 bits words, and 8 bytes of 0; the integers are little-endian.

The contracts [see File Contract.h]: ransDecompress() gets the output of ransCompress(), whose header (the frequencies sum to M, the states and the stream are in range) it checks; the audit of ransCompress() is that the output decompresses to the input. The functions are defined in Rans.tpp.

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

  1. Giesen, Interleaved entropy coders, arXiv:1402.3392, 2014

  1. Granlund, P. L. Montgomery, Division by invariant integers using multiplication, Proc. ACM PLDI 1994, 61-72, 1994, doi:10.1145/178243.178249

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions