Understanding ANS0, ANS1, and Range Entropy Codecs in Kanzi

ANS0 and ANS1 use Asymmetric Numeral Systems with 15-bit states and support Order-0 or Order-1 context modeling, while the Range codec uses classic 60-bit interval arithmetic coding limited to Order-0, trading speed for slightly better compression on small blocks.

The kanzi-cpp compression library provides three static entropy codec options selectable via the -e flag or C++ API. Understanding the differences between ANS0, ANS1, and Range entropy codecs in Kanzi allows you to optimize the trade-off between compression speed and ratio based on your data characteristics.

Core Architectural Differences

State Representation and Precision

ANS codecs maintain a single integer state of 15 bits per stream, defined by ANS_TOP = 1<<15 in src/entropy/ANSRangeEncoder.hpp. Final states serialize as four 32-bit words. In contrast, the Range codec manages two 60-bit registers (low and high) using TOP_RANGE = 0x0FFFFFFFFFFFFFFF, flushing output in 28-bit batches as implemented in src/entropy/RangeEncoder.hpp. This architectural divergence in state width directly impacts memory usage and probability precision.

Encoding Direction and Parallelism

ANS encodes symbols in reverse order (byte-reversed), enabling the implementation in ANSRangeEncoder::encodeChunk to process four symbols in parallel using independent states (st0 through st3). The Range coder processes symbols sequentially forward through RangeEncoder::encode, requiring expensive 64-bit renormalisation loops after each symbol update that limit instruction-level parallelism.

Feature Comparison: ANS vs Range

Context modeling represents the primary functional distinction. ANS supports both Order-0 (ANS0) and Order-1 (ANS1) modes, where Order-1 maintains separate frequency tables for each possible previous byte (dim = 255*order + 1) as calculated in src/entropy/ANSRangeEncoder.cpp. The Range codec lacks this capability, operating strictly in Order-0 mode.

Compression performance varies by block size. ANS generally delivers superior throughput by avoiding renormalisation overhead and leveraging vectorized loops. The Range codec achieves marginally higher compression ratios on very small blocks due to finer probability granularity (60-bit precision versus 15-bit), though this advantage diminishes with larger block sizes.

Both codecs rebuild static frequency tables per chunk via ANSRangeEncoder::rebuildStatistics and RangeEncoder::encode, resetting internal state after configurable block sizes (default 16KB for ANS).

How to Select and Use Entropy Codecs

Command Line Selection

Specify the entropy codec using the -e or --entropy option parsed in src/app/Kanzi.cpp (lines 50-53).

# Order-0 ANS (fastest, good general compression)

kanzi -c -i input.dat -o output.knz -e ANS0 -b 4m

# Order-1 ANS (better compression on structured data)

kanzi -c -i input.dat -o output.knz -e ANS1 -b 4m

# Range coder (higher ratio on very small blocks)

kanzi -c -i input.dat -o output.knz -e RANGE -b 4m

C++ API Implementation

The EntropyEncoderFactory class maps string names to implementation constants. Instantiate encoders using EntropyEncoderFactory::newEncoder as defined in src/entropy/EntropyEncoderFactory.hpp.

#include "entropy/EntropyEncoderFactory.hpp"
#include "io/OutputBitStream.hpp"

// Create Order-0 ANS encoder
kanzi::OutputBitStream obs(outStream);
kanzi::EntropyEncoder* enc = 
    kanzi::EntropyEncoderFactory::newEncoder(
        obs, 
        ctx, 
        kanzi::EntropyEncoderFactory::ANS0_TYPE
    );

// For Order-1: use ANS1_TYPE
// For Range: use RANGE_TYPE

Decoders auto-detect the codec type from the bitstream header via EntropyEncoderFactory::newDecoder (also in src/entropy/EntropyEncoderFactory.hpp), requiring no manual selection during decompression.

Summary

• ANS0 and ANS1 utilize 15-bit ANS states with reverse encoding; ANS0 provides Order-0 modeling while ANS1 implements Order-1 context
• Range employs 60-bit interval arithmetic, supports Order-0 only, and excels on small blocks
• ANS offers superior speed through parallel state processing (st0..st3) in ANSRangeEncoder::encodeChunk
• Select codecs via command line (-e ANS0|ANS1|RANGE) or API (EntropyEncoderFactory::newEncoder)
• Both systems rebuild statistics per chunk, maintaining stateless operation across block boundaries

Frequently Asked Questions

What is the difference between ANS0 and ANS1 in Kanzi?

ANS0 uses Order-0 context modeling where symbols encode independently, while ANS1 implements Order-1 context where probabilities depend on the previous byte. In src/entropy/ANSRangeEncoder.cpp, Order-1 allocates dim = 256 separate frequency tables indexed by the prior byte value, versus a single global table for ANS0. ANS1 typically achieves better compression on structured text but requires additional memory and processing overhead.

When should I use RANGE instead of ANS codecs?

Use RANGE when compressing very small blocks where the 60-bit precision of TOP_RANGE provides measurable compression gains over ANS's 15-bit state limitation. For larger files or latency-critical applications, ANS0 or ANS1 generally outperform RANGE due to parallel state processing and the absence of expensive renormalisation loops found in RangeEncoder::encode.

How does the performance compare between ANS and Range coders?

ANS codecs typically run faster because they avoid the 64-bit renormalisation loops required by the Range implementation and can process four symbols simultaneously using states st0 through st3. The Range coder's sequential interval shrinking demands more CPU cycles per symbol but delivers marginally better compression ratios when processing tiny input blocks under 1KB.

Can I use Order-1 context modeling with the Range codec?

No. According to src/entropy/RangeEncoder.hpp, the Range implementation only supports Order-0 entropy coding. If your data benefits from Order-1 context (where symbol probabilities vary based on the preceding byte), you must use ANS1 via the command line flag -e ANS1 or the constant EntropyEncoderFactory::ANS1_TYPE in the C++ API.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}