Skip to content

Latest commit

 

History

History
418 lines (326 loc) · 22.2 KB

codec-algorithm.md

File metadata and controls

418 lines (326 loc) · 22.2 KB

Indeo 3 Video Codec — Technical Algorithm Reference

Indeo 3 (IV32) is an inter-frame video codec using planar 7-bit YVU 4:1:0 color, binary-tree-based spatial partitioning, motion compensation, and vector-quantized delta coding of pixel blocks.

Indeo 3 is a Video for Windows (VFW) / ICM (Installable Compression Manager) codec, identified by the FourCC IV32. It is invoked through the standard ICM decompression interface (ICM_DECOMPRESS): the host application supplies one raw compressed frame buffer per call and receives a decoded image back; the codec itself does not parse the surrounding AVI container (RIFF chunks, index, audio interleaving) — only the per-frame payload described below.


1. Color model

  • Three planes: Y (luma, full resolution), V and U (chroma, 4:1:0 subsampled — 1/4 resolution on each axis).
  • Samples are 7-bit (range 0–127), not 8-bit. All arithmetic on sample values happens in this 7-bit domain; only the final RGB conversion step expands to 8-bit output.
  • Two frame buffers exist per plane (double buffering). A frame header bit selects which buffer is the decode target ("current") and which is the prediction source ("reference") for this frame — buffer selection is signaled explicitly per frame, not implied by parity.

2. Frame container layout

[ 16-byte frame header ][ 48-byte bitstream header ][ Y plane data ][ V plane data ][ U plane data ]

2.1 Frame header (16 bytes)

Offset Field Type Meaning
12 os_data_size u32 Declared total size of the frame payload (header validation only).

2.2 Bitstream header (48 bytes, immediately follows the frame header)

Offset Field Type Meaning
0 dec_version u16 Must equal 0x0020.
2 frame_flags u16 Bit 9 = active buffer selector (0/1) for this frame.
4 data_size_bits u32 Payload size in bits. Value 128 marks a null frame: no pixel data follows: the decoder simply re-outputs the previous frame and copies current→reference.
8 cb_offset u8 Uniform offset applied to every VQ codebook index decoded this frame.
12 height u16 Frame height in pixels.
14 width u16 Frame width in pixels.
16 y_offset u32 Byte offset (relative to the start of the bitstream header) of the Y plane data.
20 v_offset u32 Byte offset of the V plane data.
24 u_offset u32 Byte offset of the U plane data.
32 alt_quant[16] u8×16 Per-format-index codebook-pair selector, used only by cell modes 1 and 4 (see §5.4).

Plane sizes are not stored explicitly: each plane's end is the nearest following offset among the other two plane offsets (or the end of the frame payload if it is the last of the three). This assumes planes are laid out contiguously and non-overlapping.

2.3 Per-plane payload prefix

Each of the three plane payloads (Y, V, U) begins with its own motion-vector table:

[ u32 num_vectors ][ num_vectors × (int8 dy, int8 dx) ][ tree + cell bitstream ]

num_vectors is capped at 256 — a direct consequence of the inter-leaf encoding in §3.1, which selects a motion vector by reading a single byte (0–255) as its table index: a table larger than 256 entries could never be addressed. If num_vectors is 0 but the tree still encodes an inter leaf, that leaf is treated as intra (no motion) rather than as a stream error.

3. Binary tree structure

Each plane is decoded independently, walking its own 2-bit-node binary tree over the payload that follows the motion vector table. Coordinates are expressed in 4×4-pixel block units; the root node covers the whole plane (width/4 × height/4 blocks).

Two bitstreams share the same underlying byte buffer:

  • A tree bit-reader, consuming 2 bits per node, MSB-first.
  • A cell byte pointer, advanced whenever a leaf consumes raw bytes (a motion-vector index, or VQ cell payload bytes).

These two views of the same buffer are kept in sync via deferred resynchronization: byte advances made by the cell pointer are only folded back into the tree bit-reader's position at the next node boundary that falls on an exact byte boundary (bit-reader has 0 buffered bits). This reflects that the tree and the per-cell payload are two interleaved views over one physical byte stream, not two independent streams.

Splitting a cell along either axis follows a fixed size-halving rule (in block units):

split_size(n) = 1                          if n <= 2
              = ((n + 2) >> 2) << 1        otherwise

which gives the size of the first (top or left) partition; the second gets the remainder. A split whose result is degenerate (<= 0 or >= n) is either dropped (cell size already 1) or treated as a stream error otherwise.

Additionally, a horizontal split (dividing width) never crosses a strip boundary: the plane is processed in vertical strips of a fixed reference width — 160 pixels for luma, 40 pixels for chroma (40 and 10 in 4-pixel block units respectively) — regardless of the plane's actual width. If a cell's width exceeds one strip, it is first split at the 1- or 2-strip boundary before any deeper subdivision is applied.

3.1 Level 1 — motion/partition tree

Each 2-bit code at this level means:

Code Meaning
0 Horizontal split — divide the cell's height into top/bottom using the size rule above.
1 Vertical split — divide the cell's width into left/right, respecting the strip boundary.
2 Intra leaf — descend into the level-2 (VQ) tree with no motion vector.
3 Inter leaf — read one byte from the cell byte pointer as an index into the motion-vector table for this plane; descend into the level-2 tree using that vector's (dy, dx) offset.

3.2 Level 2 — VQ tree

Same split codes (0/1) and rule as level 1. Leaf codes:

Code Meaning
2 VQ-NULL leaf: reads one additional mandatory 2-bit subcode (valid values 0/1; ≥2 is a stream error) whose value is otherwise unused, then simply copies the cell's pixels from the reference buffer at the motion-vector offset. Only legal on inter cells (an intra cell cannot be VQ-NULL). The 2-bit subcode read is mandatory bitstream bookkeeping — omitting it desynchronizes every subsequent tree node.
3 VQ-DATA leaf: the cell carries an explicit payload of coded pixel data, decoded per §4. The leaf reports how many bytes it consumed, which advances the cell byte pointer accordingly.

4. Cell payload decoding

4.1 Format byte

The first byte of a VQ-DATA cell's payload is:

mode = byte >> 4          (0-15)
idx  = byte & 0x0F         (0-15)
requant_idx = (idx >= 8) ? (idx & 7) : none

requant_idx being present selects which requantization table applies (§5.3), but does not by itself mean every predictor read in this cell gets requantized — see §5.3 for the exact (narrower) condition under which the table is actually used.

4.2 Mode collapsing

The 4-bit mode field has 16 possible values; several alias to the same underlying geometry ("base mode"):

mode base mode Notes
0, 1, 2 itself Basic VQ, no zoom.
3, 4 itself Vertical zoom (each coded line expands to 2 output rows, §4.4).
6 2 Inter variant of basic VQ.
10 itself Horizontal + vertical zoom; special 2-row-per-line reconstruction (§4.5).
11 itself Vertical zoom, alternate-buffer inter variant.
12 11 Same geometry as 11.
13 11 (approximate) No-requant fallback dispatch.
14 itself Vertical zoom, intra only.
15 2 (approximate) No-requant default dispatch.

Any other mode value is a stream error.

4.3 Null-data cells (format byte only)

If requant_idx is present and base mode is not one of {0,1,3,4,10,11}, the cell carries no VQ payload at all: it is filled directly — inter cells copy from the reference buffer at the motion vector offset; intra cells fill from the row-above predictor — and the format byte is the only byte consumed for that cell. The requantization table is not applied here (it only ever applies in the narrower case described in §5.3); despite requant_idx being present, this path always uses the raw predictor/reference value unmodified.

4.4 Block geometry

h_zoom = 1 if base_mode == 10 else 0
v_zoom = 1 if base_mode in {3,4,10,11,14} else 0

block_width  = 4 << h_zoom     // 4 or 8 px
block_height = 4 << v_zoom     // 4 or 8 px
line_step    = 1 << v_zoom     // rows of actual image per coded line
coded_lines_per_block = 4

The cell is walked in block_width × block_height blocks. Within each block, up to 4 coded lines are read; each coded line covers line_step real image rows.

4.5 Codebook line selection

  • For base modes 1 and 4: the codebook line alternates between two indices per coded line (even/odd), derived by splitting the byte alt_quant[idx] into its high and low nibbles, each independently offset by cb_offset (see §2.2 and §5.4).
  • All other modes: a single codebook line for every coded line in the cell, derived directly from idx (no nibble split), offset by cb_offset.

An index that, after applying cb_offset, falls outside the valid codebook table range is a stream error.

4.6 Per-line symbol (code) interpretation

Each coded line reads one byte, code, interpreted as follows:

  • code < 0xF8 — a valid VQ symbol:
    • Direct single-byte indexing: for base modes 3/4 with requantization active, the same codebook entry index (code itself) is applied uniformly to all 4 pixels of the coded unit — no second byte is read. A further packed sub-path applies specifically to inter cells of width ≤ 4 in this configuration: a 4-byte codebook entry is added, as a single packed 32-bit integer, to both rows of a row pair simultaneously. If the resulting bottom-row 32-bit sum has its sign bit set (an overflow condition on the packed add), one additional stream byte is consumed as a correction-entry index; bytes 2–3 of that entry are added to the low 16 bits of both rows with a 0x80008000 sign-bit fixup applied before and after the correction. This packed-sum + carry-correction scheme is understood to extend, in the general case, across chains of up to 8 rows with a new control byte per row-pair rather than a single fixed application per cell — the simplified single-application model reproduces the correct output in the overwhelming majority of cases but is a known approximation of the full mechanism.
    • DYAD: if code is less than the codebook line's dyad count, code itself is the second (low) index and one additional byte is read as the first (high) index — both index the codebook line directly, with no range restriction on the second byte.
    • QUAD: otherwise, code - dyad_count is divided by the codebook line's quad exponent to produce two indices (quotient, remainder), each clamped to the dyad-count range; the two indices are swapped for codebook lines belonging to the second (high) table group.
    • The two resulting codebook entries (each 4 signed byte deltas) are added to the predictor according to the layout rules in §5.
  • 0xFB — variable-length run: the following byte encodes a repeat count (low 5 bits, minus 1 already-consumed block) and a "skip" flag (bit 5). Subsequent repeated blocks do not re-read a code byte; they are filled by reference copy (inter) or requantized predictor (intra), i.e. an implicit zero delta.
  • 0xF9 / 0xFA — short run: fills one block the same way as 0xFB's repeat action (0xF9 additionally arms a 1-block repeat + skip flag for the following block). Valid at any coded-line position, not only line 0.
  • 0xFC–0xFF — intra-block line run: line_count = 257 - code - current_line (clamped to the remaining lines in the block); fills that many coded lines with the requantized predictor (implicit zero delta), advancing the line counter without consuming further data bytes. 0xFC additionally arms a full-block repeat for the following block.
  • 0xF8 — unassigned escape value; not observed to occur in practice.

4.7 Delta application — independent per-byte masking

Deltas are 7-bit signed values added to 7-bit predictor samples with independent masking per byte lane — this is not an ordinary wide integer add: carry must not propagate between adjacent byte lanes packed into a 16- or 32-bit word (e.g. adding 0xCACA to 0x4040 byte-lane- wise must yield 0x0A0A, not 0x0B0A, because a wide add would carry from the low lane into the high lane). Each lane is computed as (base_byte + delta_byte) & 0x7F independently, then repacked to the original width.

4.8 Output layout per mode

  • Basic modes (not 3/4/10, or 3/4 without requantization): for block width ≤ 4, deltas are applied as packed 16-bit pair additions (first codebook entry for the first 2 columns, second entry for the next 2); for block width > 4, the pattern expands across repeated rows using an offset into the 4-byte entry per row — except modes 10/11 inter, where the 4-byte entry encodes a spatial left/right pair rather than a temporal row pair, so no per-row offset is applied.
  • Mode 10 intra: each coded line reconstructs two output rows. The bottom row receives the coded delta directly. The top row is the average of the coded value with the actual row-above output sample at that exact column (not a replicated/approximated value) — except at the very top edge of the image, where it is a direct replication of the coded value instead. Averaging against anything other than the true per-column row-above sample (e.g. a value replicated across the block from only 2 of its 4 columns) produces visibly wrong pixels at odd-numbered columns specifically, since such a replication pattern only ever supplies correct values at even columns. The delta computation itself (not the averaging) does use a replicated predictor in one specific case: the first block of a cell, where the base value added to the coded delta is built by replicating two of the four sampled predictor columns rather than reading all four independently — this replication is confined to that delta-base computation and never feeds the top-row average. Each 8-pixel-wide block is split into two independent 4-pixel groups, each applying only the first two bytes of its own codebook entry (the other two bytes of each entry are unused in this mode). Using all four bytes of the entry directly produces substantially worse results, so this two-independent-groups model is the current best approximation, but it can still leave a faint one-pixel-wide seam at the boundary between the two 4-pixel groups in some cells. Closing this fully would require modeling the group boundary as part of a wider row-chain structure rather than two independent halves (see the packed row-pair note above), which is a structural change to the decoding loop, not a formula fix.
  • Modes 3/4 intra: same two-row pattern as mode 10 (bottom = coded, top = average), but with 2-byte deltas per column pair rather than 4-byte entries.
  • Modes 3/4 inter with requantization: the packed row-pair scheme described in §4.6.

4.9 Run-length fills for mode 10 intra

Mode 10 intra handles all run-length fill codes (0xFB, 0xF9/0xFA, 0xFC–0xFF) differently from other modes: each filled "line" still produces two output rows using the same top-row-as-average logic as the data-carrying path (§4.8), rather than a flat uniform fill. The very first block of a cell uses the same replicated-predictor special case noted above.

5. Fixed decoder tables

5.1 VQ delta codebook

A fixed set of 24 codebook "lines", each with up to 256 entries of 4 signed byte deltas. Entries beyond a line's natural size are zero-filled — this is legitimate (high QUAD indices that decode to "no change"), not a data error.

5.2 Dyad-count / quad-exponent tables

Per codebook line, two small fixed tables give (a) how many low symbol values are direct DYAD codes versus (b) the divisor used to split a QUAD symbol into two sub-indices. These values differ across the 24 codebook lines and are intrinsic to the codebook's construction, not derived from stream data.

5.3 Requantization tables

8 fixed lookup tables of 128 entries each, selected by requant_idx and indexed by a 7-bit sample value. Each implements a step-quantization function (distinct step sizes and offsets per table).

This is not a per-read predictor transform. It applies in exactly one place: when requant_idx is present, base mode is 0, 3, or 10, and the cell is not in the first row of blocks (cell_y > 0), the table is applied once, in place, to every sample of the row of output pixels directly above the cell (row[x] = table[requant_idx][row[x] & 0x7F] for x across the cell's width) — before the cell's own VQ data is decoded. This mutates the shared output buffer: the remapped row is what later cells reading that same row as their own row-above predictor will see. No other code path — not per-pixel predictor reads, not motion-compensated reference reads, not any mode outside {0,3,10} — ever applies this table.

5.4 alt_quant and cb_offset

cb_offset (from the bitstream header) is added uniformly to every codebook line index decoded in the frame. alt_quant[idx] (indexed by the format byte's low nibble, independent of cb_offset) is only consulted for cell modes 1 and 4: its high and low nibbles select two distinct codebook lines used alternately across coded lines (§4.5).

6. Chroma upsampling and RGB conversion

The three 7-bit planes (full-resolution Y; 4:1:0-subsampled V, U) are converted to full- resolution RGB output as a final post-processing pass.

6.1 Vertical chroma upsampling

For each output row (excluding the top two rows, see §6.3), a 2-tap blend is computed between two vertically-adjacent chroma rows using integer weight pairs (4,0), (3,1), (2,2), (1,3) selected cyclically by output-row parity:

blended(x) = (chroma_row0(x) * wa + chroma_row1(x) * wb + 2) >> 2

The bottom two rows of the image are a flat special case: weights (0,4) toward the last available chroma row (no true blend).

6.2 Horizontal chroma upsampling

Processed in fixed-width vertical strips of 160 pixels, not across the whole row at once — continuity between strips is handled explicitly (the last sample of one strip references the first sample of the next).

For all rows except the top edge: the first 2 pixels of every strip are a flat "lead-in" (no ramp); the remainder advances in 4-pixel blocks along a linear ramp expressed in quarter- sample precision (not rounded, not truncated to 8-bit) between the current and next chroma sample. For the top-edge rows (§6.3), the same ramp scheme applies but without the 2-pixel lead-in — each 4-pixel block starts directly at its chroma sample boundary.

6.3 Top-edge special case (rows 0 and 1)

The topmost two output rows bypass vertical blending entirely: they use the raw first chroma row with no vertical interpolation, combined with the no-lead-in horizontal ramp variant. This is a genuine asymmetry in the reference post-processing, not an approximation.

6.4 YUV → RGB conversion tables

Given a 7-bit luma sample y7 and two chroma quarter-sample indices jV, jU (each in the approximate range 0–511, i.e. "chroma-7-bit-value × 4 + fractional-quarter"):

tY = 149*y7 - 1160
R  = (tY + 51*jV - 13056) >> 6
G  = (tY + (0x1A00 - 26*jV) + ((0x1900 - 25*jU) >> 1)) >> 6
B  = (tY + (((-0x4000 + 0x40*jU) >> 1) + ((-0x4100 + 0x41*jU) >> 1))) >> 6

with the final result clamped to [0, 255] per channel. In standard YCbCr notation, at zero fractional phase this is equivalent to:

c  = (y7 << 1) - 16
cr = (v7 << 1) - 128
cb = (u7 << 1) - 128
R = (298*c + 408*cr + 128) >> 8
G = (298*c - 100*cb - 208*cr + 128) >> 8
B = (298*c + 516*cb + 128) >> 8

Note the R coefficient is 408, not the commonly cited 409.

7. Robustness and input validation

Every quantity in §§2–4 that is read from the bitstream and subsequently used as a memory offset, array index, or buffer length is bounds-checked before use, rather than trusted:

  • Frame/plane offsets (y_offset, v_offset, u_offset) are validated to fall strictly within the declared data region before any plane is parsed.
  • The motion-vector count is capped and the resulting table size checked against the remaining buffer before it is read.
  • Every tree-walk and cell-payload byte read checks the current position against the end of the buffer before dereferencing it; running out of input bytes is a decode error, not a read past the buffer.
  • Every codebook line index and requantization index, after applying the frame-wide offset, is checked against its table's valid range before indexing.
  • The binary tree walk uses a bounded explicit stack (not native call recursion) with an explicit overflow check before each push.
  • Every pixel write resulting from cell decoding is bounds-checked against the plane's actual width and height, independent of the geometric invariants that are expected to keep it in range by construction.

This discipline matters specifically for this codec: implementations of Indeo codecs from the 1990s are known to have shipped without equivalent validation, and malformed bitstreams could drive them to read or write outside of allocated buffers.


References