Entropy‐Coder‐Internals

Entropy Coder Internals: Asymmetric Numeral Systems Architecture

The Entropy Coder is the core compression engine of SpaceEntropyCompression (SEC). SEC employs Asymmetric Numeral Systems (ANS)—specifically Range ANS (rANS) for high-throughput compute tiers and Table ANS (tANS) for constrained edge deployments.

ANS achieves near-optimal Shannon entropy compression ratios while executing at speeds comparable to Huffman decoding, providing the computational foundation for real-time spatial decompression.

---

1. Why ANS: Theoretical & Performance Comparison

In spatial coordinate and curvature field compression, entropy coding occupies a substantial fraction of CPU cycles during decompression. The table below compares entropy coding paradigms:

Metric	Huffman Coding	Arithmetic Coding (CABAC)	Range ANS (rANS)	Table ANS (tANS)
Compression Ratio	Sub-optimal (integer bits only)	Near-optimal (fractional bits)	Near-optimal (fractional bits)	Near-optimal (fractional bits)
Decoding Complexity	Low (LUT / Tree walk)	High (Multiplications & Divs)	Low (Single mult/shift)	Lowest (Single table lookup)
Throughput (MB/s/core)	$\sim 400 - 800$	$\sim 50 - 150$	$1,200 - 2,500$	$1,800 - 3,200$
State Representation	None (Prefix code)	Bounded Interval $[L, R)$	Single Scalar Integer $x$	Finite State Machine (FSM)
Hardware Suitability	General	Poor (High latency branches)	SIMD / Vector friendly	Tier 0 Edge / Microcontrollers

---

2. Range ANS (rANS) Mathematical Formulation

In rANS, an entire sequence of symbols is represented by a single positive integer state $x \in [L, bL - 1]$, where $L = 2^{16}$ (or $2^{31}$) and $b = 2$.

Symbol Encoding Function

Given symbol $s$ with probability $p_s = f_s / M$, cumulative frequency $c_s = \sum_{k < s} f_k$, and total frequency count $M = 2^{12}$:

$$C(s, x) = \left\lfloor \frac{x}{f_s} \right\rfloor \cdot M + c_s + (x \pmod{f_s})$$

Before applying $C(s, x)$, the state $x$ is renormalized by streaming out lower bits if $x \ge 2L \cdot \frac{f_s}{M}$.

Symbol Decoding Function

Decoding extracts symbol $s$ and updates state $x$ in reverse:

1. Slot Lookup: Find symbol $s$ matching slot $\text{slot} = x \pmod M$.
2. State Inversion: $$x' = f_s \cdot \left\lfloor \frac{x}{M} \right\rfloor + (\text{slot} - c_s)$$
3. State Renormalization: While $x' < L$, pull the next 16-bit word from the bitstream: $$x = (x' \ll 16) \mid \text{ReadWord}()$$

---

3. Branchless 4-Way Interleaved rANS Decoding Kernel

To maximize CPU instruction-level parallelism (ILP) and saturate modern superscalar pipelines, SEC interleaves 4 independent rANS states within a single bitstream chunk. This hides memory load latency and achieves $> 2 \text{ GB/s}$ decompression per core:

// 4-way interleaved branchless rANS decoding loop (x86_64 / ARM64)
struct RansDecState {
    uint32_t state[4];
    const uint16_t* ptr;
};

inline void rans_decode_4way(RansDecState& dec, uint32_t* out_symbols, const RansLUT& lut) {
    #pragma unroll(4)
    for (int i = 0; i < 4; ++i) {
        uint32_t x = dec.state[i];
        uint32_t slot = x & (RANS_SCALE - 1);
        
        // Fast symbol lookup via precomputed LUT
        SymbolEntry entry = lut.entries[slot];
        out_symbols[i] = entry.symbol;
        
        // Invert state without branching
        uint32_t x_next = entry.freq * (x >> RANS_SCALE_BITS) + (slot - entry.cum_freq);
        
        // Branchless renormalization
        bool renormalize = (x_next < RANS_L);
        uint32_t new_word = renormalize ? *dec.ptr++ : 0;
        dec.state[i] = renormalize ? ((x_next << 16) | new_word) : x_next;
    }
}

---

4. Table ANS (tANS) for Tier 0 Embedded Systems

For memory-constrained microcontrollers and edge chips without hardware dividers (Tier 0), SEC implements tANS. In tANS, the encoding/decoding operations are pre-compiled into a compact Finite State Machine:

+-----------------------------------------------------------------+
|                       Current State (u8/u16)                    |
+-----------------------------------------------------------------+
                                │
                                ▼
+-----------------------------------------------------------------+
|                 Precomputed Decoding Table Lookup               |
|      struct StateEntry { uint8_t symbol; uint8_t nb_bits;       |
|                          uint16_t new_state_base; };            |
+-----------------------------------------------------------------+
                                │
                                ▼
+-----------------------------------------------------------------+
|   Symbol Emitted | Consume nb_bits from Stream | Next State Set |
+-----------------------------------------------------------------+

Resource Profile (Tier 0):

• FSM Table Size: 512 entries $\times$ 4 bytes = 2 KB (fits directly into L1 instruction/data cache).
• Zero Heap: Static allocation; no division or modulo operations in the critical loop.
• Deterministic Execution Time: Exactly constant clock cycles per decoded symbol.

---

5. Context-Adaptive Probability Modeling for Spatial Deltas

Spatial residuals along Hilbert curves do not follow a uniform distribution; they follow sharp, zero-centered Laplacian distributions:

$$P(\Delta x) = \frac{1}{2b} \exp\left( - \frac{|\Delta x|}{b} \right)$$

SEC dynamically switches probability distribution tables based on spatial context:

• Context 0 (Void / Isotropic): Extreme concentration at $\Delta = 0$ (very low entropy, $\approx 0.8$ bits/coord).
• Context 1 (Low Curvature): Moderate dispersion ($1.5 - 3.2$ bits/coord).
• Context 2 (Matter Compression Well): High variance ($4.5 - 7.8$ bits/coord).

Context tables are quantized to powers of two ($M = 4096$) and normalized using integer arithmetic, preventing cross-platform rounding discrepancies.