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

> Explore Kanzi's CM entropy codec internals. Learn how it uses a binary arithmetic coder and context mixing predictor with count tables for efficient data compression.

- Repository: [flanglet/kanzi-cpp](https://github.com/flanglet/kanzi-cpp)
- Tags: internals
- Published: 2026-03-02

---

**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`](https://github.com/flanglet/kanzi-cpp/blob/main/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.

```cpp
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.

```cpp
int _counter2[512][17];

```

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

```cpp
_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:

```cpp
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`](https://github.com/flanglet/kanzi-cpp/blob/main/src/entropy/BinaryEntropyEncoder.hpp) and [`src/entropy/BinaryEntropyDecoder.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/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:

```cpp
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:

```cpp
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`](https://github.com/flanglet/kanzi-cpp/blob/main/src/entropy/EntropyEncoderFactory.hpp), the `CM_TYPE` case creates a binary entropy encoder paired with a fresh context-mixing predictor:

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

```

Similarly, [`src/entropy/EntropyDecoderFactory.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/entropy/EntropyDecoderFactory.hpp) handles the decoding side:

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

```

These factories are invoked from the high-level API ([`src/api/Compressor.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/src/api/Compressor.hpp) and [`src/api/Decompressor.hpp`](https://github.com/flanglet/kanzi-cpp/blob/main/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:

```cpp
#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:

```cpp
#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:

```c
#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.