Understanding the Internals of Kanzi's CM (Context Mixing) Entropy Codec

Kanzi's CM codec combines a binary arithmetic coder with a two-stage context-mixing predictor that uses 256×257 and 512×17 count tables to generate 12-bit probability estimates for high-efficiency entropy encoding.

The CM (Context Mixing) entropy codec in the flanglet/kanzi-cpp repository represents a sophisticated approach to binary arithmetic coding that achieves superior compression by mixing multiple probability contexts. This codec implements a context-mixing predictor that maintains dynamic statistical models to estimate the probability of each incoming bit. Understanding the internals of Kanzi's CM entropy codec requires examining the interaction between the predictor's two-level count tables and the range coding implementation in the binary entropy encoder and decoder.

The Context-Mixing Predictor Architecture

The CMPredictor class defined in src/entropy/CMPredictor.hpp serves as the statistical modeling engine for the CM codec. Unlike simple adaptive models, this predictor employs a two-stage probability estimation system that combines multiple contexts to predict whether the next bit will be 0 or 1.

Two-Stage Probability Model

The predictor maintains two distinct counter tables that capture different aspects of the input data's statistical properties:

First stage (_counter1): A 256×257 integer array that captures the probability of a bit given the recent 8-bit context (_c1) and the previous context (_c2). This table tracks statistics for 256 possible byte contexts plus one extra slot for aggregate counts.

int _counter1[256][257];

Second stage (_counter2): A 512×17 table that refines estimates based on a run-mask (_runMask) and coarse probability buckets. The 512 rows accommodate the run-mask bit (0x100) combined with context information, while 17 columns represent discretized probability ranges.

int _counter2[512][17];

The probability calculation in get() mixes these contexts using weighted averaging:

_pc1   = _counter1[_ctx];
int p  = (13 * (_pc1[256] + _pc1[_c1]) + 6 * _pc1[_c2]) >> 5;   // mix of three contexts
_pc2   = &_counter2[_ctx | _runMask][p >> 12];                // coarse bucket
return (p + p + 3 * (_pc2[0] + _pc2[1]) + 64) >> 7;          // scaled to [0..4095]

This returns a 12-bit probability value (0-4095) representing the likelihood that the next bit is 1, which the arithmetic coder uses to split the encoding interval.

Dynamic Context Handling and Run Detection

The predictor maintains a dynamic context (_ctx) that updates after every encoded or decoded symbol. The context evolution follows a binary tree structure:

if (bit == 0)  _ctx += _ctx;        // left-shift, keep 0
else           _ctx += (_ctx + 1);  // left-shift and add 1

When _ctx exceeds 255, the predictor performs a rollover operation: the most recent byte becomes _c1, the previous byte becomes _c2, and _ctx restarts at 1. This mechanism allows the model to track byte-level patterns while maintaining bit-level granularity.

The predictor also detects runs of identical bytes using a run-mask flag (0x100 when _c1 == _c2). This signals the second stage to adapt faster when processing repetitive data sequences, improving compression for homogeneous content.

Binary Arithmetic Coding Implementation

The CM codec wraps the predictor within a binary arithmetic coding framework implemented in src/entropy/BinaryEntropyEncoder.hpp and src/entropy/BinaryEntropyDecoder.hpp. These classes perform the actual bitstream encoding and decoding using the probabilities generated by CMPredictor.

Range Encoding in BinaryEntropyEncoder

The encoder implements classic range coding by maintaining a numerical interval [low, high] that narrows according to the predicted probability. The encoding logic in the encodeBit() method follows this pattern:

const uint64 mid = _low + ((((_high - _low) >> 4) * uint64(pred)) >> 8);
(bit != 0) ? _high = mid : _low = mid + 1;   // split interval
_predictor->update(bit != 0);
if (((_low ^ _high) >> 24) == 0)           // top 32 bits equal?
    flush();                               // output them

The pred value defaults to 2048 (representing 0.5 probability) when no predictor is provided, but typically receives the 12-bit value from CMPredictor::get(). The flush() method emits the common leading bits of _low and _high to the OutputBitStream whenever the top 32 bits match, ensuring efficient output buffering.

When encoding completes, the remaining interval bits are written out in the destructor via dispose().

Deterministic Decoding in BinaryEntropyDecoder

The decoder mirrors the encoder's logic to ensure exact reconstruction. It maintains the same _low and _high interval boundaries plus a _current value representing the encoded bitstream position:

const uint64 split = ((((_high - _low) >> 4) * uint64(pred)) >> 8) + _low;
if (split >= _current) {          // current code lies in the upper sub-interval
    bit = 1;
    _high = split;
    _predictor->update(1);
}
else {
    bit = 0;
    _low = split + 1;
    _predictor->update(0);
}
if (((_low ^ _high) >> 24) == 0)  // need more bits?
    read();                       // read next 32 bits from the stream

The decoder reads additional input bits whenever the interval requires refinement (when the top 32 bits of _low and _high diverge). Both encoder and decoder call update() on the predictor to maintain synchronized model state, ensuring deterministic reconstruction of the original data.

Factory Integration and API Usage

The CM codec integrates into Kanzi's architecture through factory classes that instantiate the appropriate encoder/decoder pairs. In src/entropy/EntropyEncoderFactory.hpp, the CM_TYPE case creates a binary entropy encoder paired with a fresh context-mixing predictor:

case CM_TYPE:
    return new BinaryEntropyEncoder(obs, new CMPredictor());

Similarly, src/entropy/EntropyDecoderFactory.hpp handles the decoding side:

case CM_TYPE:
    return new BinaryEntropyDecoder(ibs, new CMPredictor());

These factories are invoked from the high-level API (src/api/Compressor.hpp and src/api/Decompressor.hpp) when users specify entropy = "CM" in the compression parameters.

Code Examples

High-Level C++ API

The following example demonstrates end-to-end compression using the CM codec through Kanzi's public API:

#include "kanzi/Compressor.hpp"
#include "kanzi/Decompressor.hpp"

int main() {
    // --- Compression -------------------------------------------------
    kanzi::Compressor comp;
    kanzi::cData params = {};
    strcpy(params.transform, "NONE");   // no transform, only entropy
    strcpy(params.entropy,  "CM");     // select Context Mixing
    params.blockSize = 1<<20;          // 1 MiB blocks
    params.jobs      = 1;             // single-threaded

    FILE* dst = fopen("data.kanzi", "wb");
    comp.initCompressor(&params, dst, nullptr);

    const unsigned char src[] = "Hello Kanzi CM!";
    size_t outSize = 0;
    comp.compress(nullptr, src, sizeof(src)-1, &outSize);
    comp.disposeCompressor(nullptr, &outSize);
    fclose(dst);

    // --- Decompression ------------------------------------------------
    kanzi::Decompressor decomp;
    kanzi::cData dparams = {};
    strcpy(dparams.transform, "NONE");
    strcpy(dparams.entropy,  "CM");
    FILE* srcFile = fopen("data.kanzi", "rb");
    decomp.initDecompressor(&dparams, srcFile, nullptr);

    unsigned char out[64];
    size_t decoded = 0;
    decomp.decompress(nullptr, out, outSize, &decoded);
    decomp.disposeDecompressor(nullptr);
    fclose(srcFile);
}

Setting entropy = "CM" triggers the context-mixing predictor and binary arithmetic coder pipeline for maximum compression efficiency on binary data.

Manual Encoder/Decoder Instantiation

For custom pipelines or educational purposes, you can instantiate the encoder and decoder directly without the high-level compressor:

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

int main() {
    kanzi::OutputBitStream out(/*...*/);
    kanzi::Context ctx;                       // shared context (required for some codecs)
    kanzi::EntropyEncoder* enc = kanzi::EntropyEncoderFactory::newEncoder(out, ctx,
                                         kanzi::EntropyEncoderFactory::CM_TYPE);
    // Encode bits one by one
    enc->encodeBit(1, enc->getPredictor()->get()); // get() returns prob of 1
    enc->encodeBit(0);
    // ...

    enc->dispose();               // flush final bits
    delete enc;                   // free predictor as well

    // Decoder counterpart
    kanzi::InputBitStream in(/*...*/);
    kanzi::EntropyDecoder* dec = kanzi::EntropyDecoderFactory::newDecoder(in, ctx,
                                         kanzi::EntropyDecoderFactory::CM_TYPE);
    int bit = dec->decodeBit();   // uses same predictor internally
    // ...
    delete dec;
}

This approach provides direct access to the binary arithmetic coding primitives while maintaining the sophisticated probability estimation of the CM predictor.

C API Integration

Legacy projects can access the CM codec through Kanzi's C API, which forwards to the same underlying factories:

#include "kanzi.h"

int main() {
    struct cData p = {0};
    strcpy(p.transform, "NONE");
    strcpy(p.entropy,   "CM");
    p.blockSize = 1<<20;
    p.jobs = 1;

    struct cContext* ctx = NULL;
    FILE* dst = fopen("out.kzi", "wb");
    initCompressor(&p, dst, &ctx);

    const unsigned char data[] = "binary data...";
    size_t outSize = 0;
    compress(ctx, data, sizeof(data)-1, &outSize);
    disposeCompressor(&ctx, &outSize);
    fclose(dst);
}

The C API provides the same predictor-based compression behavior as the C++ interface.

Summary

• CMPredictor implements a two-stage context-mixing model using _counter1[256][257] for byte contexts and _counter2[512][17] for run-aware probability refinement.
• The predictor generates 12-bit probability estimates (0-4095) by mixing three contexts: aggregate counts, recent byte context (_c1), and previous byte context (_c2).
• BinaryEntropyEncoder and BinaryEntropyDecoder implement range coding that narrows the interval [low, high] based on predictor probabilities, flushing output when the top 32 bits align.
• Context synchronization between encoder and decoder occurs through identical update() calls on the predictor, ensuring deterministic reconstruction.
• The factory pattern in EntropyEncoderFactory and EntropyDecoderFactory maps CM_TYPE to the binary arithmetic coder paired with a fresh CMPredictor instance.

Frequently Asked Questions

How does the CMPredictor generate probability estimates?

The predictor generates estimates by consulting two levels of count tables. First, it calculates an intermediate probability p using weighted contributions from _counter1 entries representing the aggregate count, the current byte context (_c1), and the previous byte context (_c2). Then it refines this estimate using _counter2, which considers the run-mask state and coarse probability buckets. The final result is scaled to a 12-bit value (0-4095) representing the probability that the next bit is 1.

What is the difference between _counter1 and _counter2 in the predictor?

_counter1 is a 256×257 table that models bit probabilities based on byte-level contexts, tracking statistics for 256 possible byte values plus an aggregate column. _counter2 is a 512×17 table that provides secondary adaptation based on whether the current context represents a run of identical bytes (using the run-mask bit) and the coarse probability bucket of the initial estimate. This two-stage design allows the model to capture both standard byte contexts and repetitive data patterns efficiently.

How does the binary arithmetic coder handle interval scaling?

The coder scales the interval [_low, _high] by multiplying the range (_high - _low) with the 12-bit probability estimate, then shifting right by 12 bits (implemented as >> 4 followed by >> 8 for precision). This produces a split point mid that divides the interval proportionally to the probability of a 1 bit. When the top 32 bits of _low and _high become identical, the common bits are flushed to the output stream, and the interval is renormalized by reading more input bits (in the decoder) or shifting the boundaries (in the encoder).

When should I use CM versus other entropy codecs in Kanzi?

Use the CM codec when compressing data with complex contextual patterns where bit probabilities depend heavily on recent history, such as text or structured binary formats. The context-mixing predictor excels at capturing correlations between consecutive bytes. For simple stationary sources or when encoding speed is critical, simpler entropy codecs like Huffman or ANS might be preferable, as CM's two-stage prediction involves more computation per bit encoded.

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