Draco uses asymmetric numeral systems (ANS) for its entropy coding. Lists of non-negative integers, such as attribute corrections and compressed indices, go through a symbol decoder built on rANS; single flags, such as seam and crease bits, go through a binary decoder, rABS. Both read their buffers backwards, from the last byte to the first.
Symbol decoding
Wherever the bitstream holds “symbols”, it starts with one byte:
| Field | Type | Meaning |
|---|---|---|
scheme | UI8 | 0 TAGGED_SYMBOLS, 1 RAW_SYMBOLS |
Raw symbols
| Field | Type | Meaning |
|---|---|---|
max_bit_length | UI8 | Bits in the largest symbol |
num_symbols_ | varUI32 | Size of the symbol alphabet, 0 to n − 1 |
| Probability table | See below | A probability for each symbol |
size | varUI64 | Size of the coded data |
buffer | UI8[size] | The rANS-coded symbols |
The precision depends on the largest symbol:
rans_precision_bits = 3 × max_bit_length ÷ 2, kept between
12 and 20; the precision is 2 to that power, and the decoder’s lower bound,
l_rans_base, is four times the precision. Every symbol read is one value.
Tagged symbols
| Field | Type | Meaning |
|---|---|---|
num_symbols_ | varUI32 | Size of the tag alphabet |
| Probability table | See below | A probability for each tag |
size | varUI64 | Size of the coded tags |
encoded_data | UI8[size] | The rANS-coded tags |
| Values | f[tag] each | The values themselves, in a bit stream |
Tagged coding works one whole value at a time, such as the three components of a
position. Each rANS symbol is a tag giving a bit length; then each component of the
value is read as that many bits (f[tag]), and after each value
the bit reader moves on to a whole byte. It uses the fixed constants
TAGGED_RANS_BASE 16384 and TAGGED_RANS_PRECISION 4096.
Probability tables
A table gives each symbol a probability, as a fraction of the precision. It is read
symbol by symbol, starting with one byte, prob_data:
| Low 2 bits (token) | Meaning |
|---|---|
| 0, 1 or 2 | The probability’s low 6 bits are prob_data >> 2; then token more bytes follow, each adding 8 higher bits (the first at bit 6, the next at bit 14) |
| 3 | A run of zeros: this symbol and the next prob_data >> 2 symbols all have probability 0 |
The decoder then lays the symbols out in order: each symbol’s cumulative probability is the sum of those before it, and a look-up table maps every slot from 0 to the precision to the symbol that covers it.
rANS decoder
To start, the decoder reads its initial state from the end of the buffer. The top two bits of the last byte say how many bytes the state takes:
| Top 2 bits of the last byte | State bytes | State |
|---|---|---|
| 0 | 1 | Last byte & 0x3F |
| 1 | 2 | Last 2 bytes, little-endian, & 0x3FFF |
| 2 | 3 | Last 3 bytes, little-endian, & 0x3FFFFF |
| 3 | 4 | Last 4 bytes, little-endian, & 0x3FFFFFFF |
The lower bound is added to the state, and the read position is set to just before those bytes. To read a symbol:
- While the state is below the lower bound and bytes remain, multiply the state by
256 (
IO_BASE) and add the next byte, moving backwards. - Divide the state by the precision: quotient q, remainder r.
- The symbol is the one whose slot covers r.
- The new state is q × probability + r − cumulative probability.
For coded data other than symbols (the seam, crease, orientation and start face bits)
the lower bound is L_RANS_BASE, 4096.
rABS binary decoder
Flags are coded with rABS. Each such buffer is preceded in the bitstream by
prob_zero, a byte giving the probability of a 0 out of 256, then its size
(varUI32) and its bytes. The state starts as for rANS. To read a bit with
p = 256 − prob_zero:
- If the state is below 4096 (
rabs_l_base), multiply it by 256 and add the next byte, moving backwards. - Divide the state x by 256: quotient q, remainder r.
- The bit is 1 when r < p. Then the new state is q × p + r; otherwise it is x − q × p − p.
The specification also lists rabs_ans_p10_precision, 1024, which no
decoding step uses.