EBCOT Tier-1 & MQ Arithmetic Decoder

Overview

Embedded Block Coding with Optimal Truncation (EBCOT) is the entropy coding engine at the heart of JPEG2000. It operates independently on small code blocks (typically 64×64 or 32×32 wavelet coefficients), encoding them bit-plane by bit-plane from the most significant bit down. This bit-plane structure is what enables JPEG2000’s progressive quality refinement: each additional bit-plane improves the reconstructed image, and the encoder can truncate any code block at any bit-plane to hit a target bitrate.

EBCOT has two tiers. Tier-2 handles packet formation and rate control—deciding how many coding passes to include for each code block. Tier-1 is the actual entropy coding engine that compresses wavelet coefficients within each code block using the MQ arithmetic coder. The decoder reverses this process: Tier-2 unpacks packets to determine which coding passes are present, then Tier-1 decodes those passes using the MQ decoder to reconstruct the wavelet coefficient magnitudes and signs.

The MQ coder is a context-adaptive binary arithmetic coder descended from the QM coder used in JBIG. It maintains a probability estimate for each of 19 coding contexts, updating them after every decoded bit. The codec library implements the full Tier-1 decoder in Zig, including all three coding pass types (significance, refinement, cleanup) and the MQ state machine with its 47-entry probability estimation table.

Core Concepts

Code Blocks and Bit-Planes

Each subband produced by the DWT is partitioned into rectangular code blocks. A code block is the fundamental unit of entropy coding—each is encoded independently, enabling parallel encoding/decoding and fine-grained rate control. The wavelet coefficients within a code block are encoded bit-plane by bit-plane, starting from the most significant non-zero bit-plane (determined by the largest coefficient magnitude in the block).

Three Coding Passes

Within each bit-plane (except the first), EBCOT applies three coding passes in a fixed order. Each pass visits coefficients in a specific stripe-based scan pattern (4 rows at a time, column by column within each stripe):

1. Significance Propagation Pass (SPP): Visits coefficients that are not yet significant but have at least one significant neighbor. These coefficients are the most likely to become significant at this bit-plane. The current bit is coded with the MQ coder using a context derived from the neighbor significance pattern.
2. Magnitude Refinement Pass (MRP): Visits coefficients that became significant in a previous bit-plane. Each coefficient’s current bit is coded using one of three refinement contexts based on whether this is the first refinement and the neighbor pattern.
3. Cleanup Pass (CLP): Visits all remaining coefficients not covered by SPP or MRP. This is the only pass present in the first (most significant) bit-plane. The cleanup pass uses run-length coding when four consecutive coefficients in a column are all insignificant with no significant neighbors.

The MQ Arithmetic Coder

The MQ coder is a binary arithmetic coder that maintains a probability interval [0, 1) and narrows it with each decoded bit. It uses a finite-state machine with 47 states to estimate the probability of the Most Probable Symbol (MPS) for each context. After each decoded bit, the context’s state transitions to a new state that reflects the updated probability estimate.

The MQ decoder maintains three registers: the code register C (the current position in the interval), the interval width A, and the count of available bits CT. Decoding a bit involves comparing the interval width against the probability estimate (Qe value) for the current context, deciding whether the decoded symbol is the MPS or the Less Probable Symbol (LPS), updating the interval, and transitioning the context state.

Tag Trees

Before decoding a code block’s coding passes, the decoder must know which passes are included in the current packet. JPEG2000 uses tag trees to efficiently code the inclusion information and the number of leading zero bit-planes for each code block. A tag tree is a binary tree where each node represents the minimum value of its children. The tree is coded top-down, and each node’s value constrains its children, enabling early termination.

How It Works

The Tier-1 decoding pipeline processes each code block independently. For each code block, the decoder initializes the MQ coder with the code block’s bitstream, then executes the coding passes in order: cleanup pass for the first bit-plane, then significance/refinement/cleanup for each subsequent bit-plane, stopping when the allocated coding passes are exhausted.

1. Initialize MQ state: Set all 19 contexts to state 0 (uniform probability), reset A and C registers.
2. Decode tag trees: Determine inclusion and zero bit-plane information for each code block.
3. For each coding pass: Execute the pass (SPP, MRP, or CLP) using the MQ coder.
4. Handle bypass mode: If enabled, some passes use raw bit coding instead of MQ.
5. Handle reset mode: If enabled, reset MQ contexts between coding passes.
6. Check segmentation symbol: If enabled, verify the 4-bit segmentation marker at the end of each pass.

const MQDecoder = struct {
    c: u32,           // Code register (bit buffer)
    a: u32,           // Interval width
    ct: u8,           // Counter of available bits
    data: []const u8, // Compressed data
    pos: usize,       // Current byte position

    // 19 coding contexts, each with state index and MPS value
    contexts: [19]Context,

    const Context = struct {
        state: u6,   // Index into Qe table (0..46)
        mps: u1,     // Most probable symbol
    };

    pub fn init(data: []const u8) MQDecoder {
        var mq = MQDecoder{
            .c = 0,
            .a = 0x8000,
            .ct = 0,
            .data = data,
            .pos = 0,
            .contexts = [_]Context{.{ .state = 0, .mps = 0 }} ** 19,
        };
        // Initialize: read first bytes into C register
        mq.byteIn();
        mq.c <<= mq.ct;
        mq.byteIn();
        mq.c <<= 7;
        mq.ct -= 7;
        mq.a = 0x8000;
        return mq;
    }

    pub fn decode(self: *MQDecoder, ctx_idx: u5) u1 {
        const ctx = &self.contexts[ctx_idx];
        const qe = QE_TABLE[ctx.state];
        var d: u1 = undefined;

        self.a -= qe.value;

        if ((self.c >> 16) < self.a) {
            // MPS path
            if (self.a < 0x8000) {
                d = if (self.a < qe.value) 1 - ctx.mps else ctx.mps;
                if (self.a < qe.value) {
                    ctx.state = qe.lps_next;
                    if (qe.switch_flag) ctx.mps ^= 1;
                } else {
                    ctx.state = qe.mps_next;
                }
                self.renormalize();
            } else {
                d = ctx.mps;
            }
        } else {
            // LPS path
            self.c -= @as(u32, self.a) << 16;
            d = if (self.a < qe.value) ctx.mps else 1 - ctx.mps;
            if (self.a >= qe.value) {
                ctx.state = qe.lps_next;
                if (qe.switch_flag) ctx.mps ^= 1;
            } else {
                ctx.state = qe.mps_next;
            }
            self.a = qe.value;
            self.renormalize();
        }

        return d;
    }
};

// Significance Propagation Pass
fn sigPropPass(
    mq: *MQDecoder,
    coeffs: *CodeBlockState,
    bit_plane: u5,
) void {
    const height = coeffs.height;
    const width = coeffs.width;
    const stripe_height: u32 = 4;

    var y: u32 = 0;
    while (y < height) : (y += stripe_height) {
        const sh = @min(stripe_height, height - y);
        var x: u32 = 0;
        while (x < width) : (x += 1) {
            var j: u32 = 0;
            while (j < sh) : (j += 1) {
                const row = y + j;
                if (coeffs.isSignificant(x, row)) continue;
                if (!coeffs.hasSignificantNeighbor(x, row)) continue;

                // Decode significance bit
                const ctx = coeffs.sigContext(x, row);
                const sig = mq.decode(ctx);

                if (sig == 1) {
                    // Decode sign bit
                    const sign_ctx = coeffs.signContext(x, row);
                    const sign_bit = mq.decode(sign_ctx.ctx);
                    const sign = sign_bit ^ sign_ctx.prediction;

                    coeffs.setSignificant(x, row, bit_plane, sign);
                }
            }
        }
    }
}

Practical Applications

Quality-Scalable Streaming

Because EBCOT codes bit-planes independently, a JPEG2000 server can stream coding passes incrementally. The client receives the most significant bit-planes first and can display a coarse version of the image immediately. As more passes arrive, the image quality improves smoothly. This is fundamentally different from progressive JPEG, which sends DCT coefficients in a fixed order—JPEG2000’s rate allocation optimizes which code blocks benefit most from additional passes.

Digital Cinema (DCI)

The Digital Cinema Initiative specifies JPEG2000 for theatrical distribution. A 4K frame at 24 fps generates enormous data volumes. EBCOT’s independent code block processing enables massively parallel hardware decoders where each code block is assigned to a separate processing element. The MQ coder’s simple state machine maps efficiently to FPGA and ASIC implementations.

Embedded PDF Images in Document Pipelines

The codec library’s decoder processes JP2 images embedded in PDF documents. Many scanned documents and government archives use JPEG2000 for its lossless capability and superior compression of text-heavy content. The EBCOT decoder must handle the full range of coding options: bypass mode (where some passes skip the MQ coder for speed), predictable termination (for error resilience), and segmentation symbols (for decoder synchronization verification).

Implementation Patterns

Lookup-Table-Driven Context Formation

Computing the significance context from 8 neighbors for every coefficient is expensive if done with branching logic. The standard approach uses a precomputed lookup table indexed by the neighbor significance bitmask. The table maps each of the 256 possible neighbor patterns to one of the 9 significance contexts, taking into account the subband orientation (HL, LH, HH, or LL).

// Neighbor significance bitmask layout:
//   bit 0: north    bit 1: south
//   bit 2: east     bit 3: west
//   bit 4: NE       bit 5: NW
//   bit 6: SE       bit 7: SW

// Context lookup table for HL subband
const HL_SIG_CTX: [256]u5 = blk: {
    var table: [256]u5 = undefined;
    for (0..256) |pattern| {
        const h = popcount(pattern & 0x0C);  // east + west
        const v = popcount(pattern & 0x03);  // north + south
        const d = popcount(pattern & 0xF0);  // diagonals

        table[pattern] = if (h == 2) 8
            else if (h == 1) (if (v >= 1) 7 else if (d >= 1) 6 else 5)
            else if (v == 2) 4
            else if (v == 1) 3
            else if (d >= 2) 2
            else if (d == 1) 1
            else 0;
    }
    break :blk table;
};

Bypass (Raw) Coding Mode

For lower bit-planes where the MQ coder’s overhead exceeds its compression benefit, JPEG2000 supports bypass mode. In bypass mode, significance propagation and magnitude refinement passes emit raw bits instead of arithmetic-coded bits. The decoder switches between MQ decoding and raw bit reading based on the coding pass type and the bypass flag from the COD marker.

fn decodeCodingPass(
    mq: *MQDecoder,
    raw: *RawBitReader,
    coeffs: *CodeBlockState,
    pass_type: PassType,
    bit_plane: u5,
    bypass: bool,
) void {
    switch (pass_type) {
        .significance => {
            if (bypass and bit_plane < first_bypass_plane) {
                sigPropPassRaw(raw, coeffs, bit_plane);
            } else {
                sigPropPass(mq, coeffs, bit_plane);
            }
        },
        .refinement => {
            if (bypass and bit_plane < first_bypass_plane) {
                magRefPassRaw(raw, coeffs, bit_plane);
            } else {
                magRefPass(mq, coeffs, bit_plane);
            }
        },
        .cleanup => {
            // Cleanup pass always uses MQ coder
            cleanupPass(mq, coeffs, bit_plane);
        },
    }
}

Segmentation Symbol Verification

When the segmentation symbol flag is set in the COD marker, the encoder appends a 4-bit pattern (1010) at the end of each cleanup pass, coded with a dedicated context. The decoder verifies this pattern after decoding the cleanup pass. A mismatch indicates bitstream corruption or a decoder bug—a critical debugging tool during development.

fn verifySegmentationSymbol(mq: *MQDecoder) !void {
    // Context 18 is reserved for the segmentation symbol
    const seg_ctx: u5 = 18;

    var symbol: u4 = 0;
    symbol |= @as(u4, mq.decode(seg_ctx)) << 3;
    symbol |= @as(u4, mq.decode(seg_ctx)) << 2;
    symbol |= @as(u4, mq.decode(seg_ctx)) << 1;
    symbol |= @as(u4, mq.decode(seg_ctx));

    if (symbol != 0b1010) {
        return error.SegmentationSymbolMismatch;
    }
}

Common Pitfalls

• MQ byte-stuffing confusion: The MQ bitstream uses byte-stuffing to prevent marker emulation: after any byte with value 0xFF, the next byte has its MSB set to 0, so only 7 bits are data. The byteIn() function must check the previous byte and adjust the bit count accordingly. Missing this produces garbage after the first 0xFF byte in the data.
• Wrong scan order: The stripe-based scan visits coefficients in 4-row stripes, column by column within each stripe. Scanning row-by-row or in full columns produces different context states and completely wrong coefficient values. The scan order is fixed by the standard and cannot be changed.
• Context index mapping errors: JPEG2000 uses 19 contexts (0–18) with specific assignments: 0–8 for significance, 9–13 for sign, 14–16 for refinement, 17 for run-length, 18 for uniform/segmentation. Using the wrong context index corrupts the probability estimates for all subsequent bits in that context.
• Forgetting to reset contexts between passes: When the COD marker sets the reset flag, all MQ contexts must be reset to state 0 between coding passes. Failing to reset causes probability estimates to carry over from one pass to the next, producing subtle artifacts that worsen over multiple bit-planes.
• Sign context prediction not XORed: The sign decoding uses a predicted sign value based on the signs of significant neighbors. The decoded bit must be XORed with this prediction to get the actual sign. Forgetting the XOR produces images with random sign inversions that appear as pepper noise.