Editing LZMA (section)

===Range coding of integers ===

The range decoder also provides the bit-tree, reverse bit-tree and fixed probability integer decoding facilities, which are used to decode integers, and generalize the single-bit decoding described above.
To decode unsigned integers less than ''limit'', an array of {{math|(''limit'' − 1)}} 11-bit probability variables is provided, which are conceptually arranged as the internal nodes of a complete binary tree with ''limit'' leaves.

Non-reverse bit-tree decoding works by keeping a pointer to the tree of variables, which starts at the root. As long as the pointer does not point to a leaf, a bit is decoded using the variable indicated by the pointer, and the pointer is moved to either the left or right children depending on whether the bit is 0 or 1; when the pointer points to a leaf, the number associated with the leaf is returned.

Non-reverse bit-tree decoding thus happens from most significant to least significant bit, stopping when only one value in the valid range is possible (this conceptually allows to have range sizes that are not powers of two, even though LZMA does not make use of this).

Reverse bit-tree decoding instead decodes from least significant bit to most significant bits, and thus only supports ranges that are powers of two, and always decodes the same number of bits. It is equivalent to performing non-reverse bittree decoding with a power of two ''limit'', and reversing the last {{math|log{{sub|2}}(''limit'')}} bits of the result.

In the {{mono|rc_bittree}} function in the Linux kernel, integers are actually returned in the {{math|[''limit'', 2 × ''limit'')}} range (with ''limit'' added to the conceptual value), and the variable at index 0 in the array is unused, while the one at index 1 is the root, and the left and right children indices are computed as 2''i'' and 2''i'' + 1. The {{mono|rc_bittree_reverse}} function instead adds integers in the {{math|[0, ''limit'')}} range to a caller-provided variable, where ''limit'' is implicitly represented by its logarithm, and has its own independent implementation for efficiency reasons.

Fixed probability integer decoding simply performs fixed probability bit decoding repeatedly, reading bits from the most to the least significant.