encoding.info
You are hereSourcePredictionTransformEntropy codingFiltersFramesDecisionsRate controlPerceptionQualityBitstreamSettingsEncoder map
Page 6 of 6 in Entropy coding

Estimating bit cost before coding

Entropy coding · implementation · added 2026-11-14

In Brief:
x264 needs a bit count for every candidate it compares, and gets it without writing the candidate: it adds up codeword lengths for one coder and table prices for the other. On this page's example the table's total landed within 5 bits of the coder's own arithmetic, out of about 840.

x264 compares candidates by reconstruction-based rate-distortion cost, which needs a bit count for each one, and it does not write the candidates to find out. For ordinary syntax of its variable-length coder it adds up exact codeword lengths. For decisions of its arithmetic coder it usually adds up fractional prices from a table, in units of 1/256 bit, using a copy of the coder's contexts. Its decision routines also use shortcuts and penalties.

Where the counting happens

rd_cost_mb reconstructs a macroblock, measures its error, and then counts bits one of three ways. A skipped macroblock is given a fixed price of one bit. With the arithmetic coder, COPY_CABAC copies the context bytes and macroblock_size_cabac runs on the copy. With the variable-length coder, macroblock_size_cavlc runs.

Neither is written separately: rdo.c includes the writers themselves, cavlc.c and cabac.c, a second time, with each write call redefined to add to a counter. Most of the count therefore walks the same decisions as the writer. Some branches are taken only when counting: one prices a partition without all of its syntax, and another adds a 2,000-bit penalty where a level would overflow.

Compare the estimate with interval narrowing

The demo carries x264's own tables. It takes the cat's flags from the first page of this unit, row by row, all in one context, and keeps two tallies. A flag is a symbol with two possible values: there is one per pixel, zero where the pixel equals the pixel to its left and nonzero where it differs.

Table estimate is what x264_cabac_size_decision does: add the table's price for the flag in the context's current state, then advance the state. Interval cost measures how much the chosen intervals shrink under x264's rules for splitting its range, in bits:

interval cost =
  shifts + log2(510 / range)

The range starts at 510, and the shifts are the doublings that bring it back up after a split. Interval cost is not a count of output bits: the demo writes nothing and ends no stream. The plot shows the estimate minus the interval cost; below zero, the estimate is the smaller. Starting state is what the context expects before the first flag.

1024
← 1: the first flag1,024: the whole cat →
Table estimate
Interval cost
Estimate − interval
Implied zero chance
Simplified demo: the four tables are x264's, copied from its source, and the two tallies follow its code. Both are in bits. The flags are this course's, not H.264 syntax, and an encoder would spread them over many contexts. Nothing is written: the low end of the interval, the bytes, the carry and the bits that end a slice are left out, so neither tally is the size of a stream. Implied zero chance is 2 to the power of minus the table's price for a zero in the current state. It is a probability worked back from a rounded price, not one x264 stores, and not exactly the share the next split gives a zero. The demo uses the price lookup that advances the state; x264 also has one that does not. x264's own output position comes from its bytes and its queue, not from this formula. The three starting states are the demo's; a slice starts each context from its tables. The first pixel of the cat differs from mid-gray, so the first flag is a nonzero.

Measured on these 1,024 flags:

The table prices a decision from the context's state alone. The split that sets the interval cost also depends on the range, through a table with four columns. x264's own comment calls the estimate not exactly the same.

The prices

Every entry adds to one counter. For the arithmetic coder the unit is 1/256 bit.

What is pricedAdded
A decision in a contextx264_cabac_entropy[state ^ value]
An even-odds decision256
A terminal decision7
A skipped macroblock, in rd_cost_mb1 bit
A variable-length codewordIts length in bits

A decision in a context is priced from the table and advances the context. An even-odds decision is one bit and touches no context. The terminal decision, x264_cabac_encode_terminal_c, gives the other outcome 2 of a range of at least 256 when written and is a fixed 7 when counted. In rd_cost_mb the count becomes the rate term with lambda, which x264 stores multiplied by 256:

arithmetic coder:
  (count × lambda + 32768) >> 16
variable-length coder:
  (bits × lambda + 128) >> 8

Sources

Read 2026-11-14 and 2026-11-15, at the commits linked.