Finite state machines and CABAC

During CABAC binarization, the coefficients in each DCT block are converted to binary symbols which are arithmetically coded into the bitstream. Each symbol has a specific context, the choice of which is calculated through a simple algorithm. This context-choice, of course, has to be the same on encoding and decoding. One can calculate this context for each coefficient--or one can make a finite state machine using a set of states and a transition tables, so that given the current context, the next context can be calculated using merely an array lookup.

This improves performance both in CABAC encoding and CABAC decoding. Note the similarities between the two diffs--despite the fact that one is in x264 and designed for encoding, and the other is in ffmpeg and designed for decoding, they are practically the same code. This is true of most of the CABAC code; in fact, most of x264's CABAC binarization code is simply the code from ffmpeg, except reversed. Original credit for the finite state machine code goes to Loren Merritt, who wrote it to speed up the calculation of CABAC states in x264's trellis quantization algorithm.