Video2NAND - The Fine Details

In the previous post I’ve outlined how logic gates can be emulated in the VP8 video codec. That explanation simplified and skimmed over a lot of details. In this post we will address most of the major un-truths and talk detail about VP8 in more detail.

As a video codec, VP8 defines a serialized data format and a decoding procedure which turns that serialized data into a sequence of video frames. That serialized data can be thought of as some “coded video structure” - an abstract model that the decoder can turn into a video. We’ll ignore the many clever compression schemes involved in serializing that model into a byte stream, and instead stick only to the higher level concepts.

For the complete details, I recommend reading RFC 6386 which describes the whole VP8 data format and decoding procedure.

The Coded Video Structure

A video is composed of a sequence of frames. Each frame is a two-dimensional grid of pixels, composed of three separate planes: the luma plane, and the two chroma planes. The luma plane controls the brightness, and the chroma planes control the hue. These planes do not all have the same size, with the chroma planes being half the width and height of the luma plane. Each pixel value in the frame is defined by its corresponding luma pixel, and the chroma pixels corresponding to the 2x2 block it is in.

Each plane is encoded totally separately from the others. There are some difference between the luma plane and the chroma planes, but overall they are encoded very similarly.

A frame is encoded as an array of macroblocks. A macroblock is a square array of pixels whose luma dimensions are 16x16 and whose chroma dimensions are 8x8.

These macroblocks are serialized and decoded row by row, from the top-left down to the bottom-right.

The pixel values in each plane in each macroblock are computed by summing two two-dimensional arrays: the prediction and the residue. With the final value being clamped in the range [0, 255].

value = prediction + residue

Each macroblock has a prediction mode for each plane. That prediction mode defines how to calculate prediction as a function of previously decoded macroblocks. In the case of key-frames these prediction modes are constrained to predictions that depend soley macroblocks in the same frame, whereas inter-frames have prediction modes which depend on macroblocks from previous frames.

In addition to the prediction mode, each macroblock plane has an encoded residue in the byte stream. The way that residue is encoded is somewhat complex, but after performing all the transformations required to decode it, its simply a two-dimensional array of signed integers.

Back to Digital Logic

Now that we understand VP8 a little better, we can clear up some potential questions from the original post.

Logic Cells

Our circuits were built out of so-called “blocks”. These blocks are in fact the luma plane macroblocks. We don’t care about the values in the chroma planes, and define a logic block to be “truth-y” if all the luma values in that macroblock are 255, and “false-y” if all the luma values in that macroblock are 0. Completely white or completely black, respectively.

Constant Values

All macroblocks have both a prediction and residue component. The prediction component prevents us from directly setting the macroblock’s values independently of the values of other macroblocks. Thankfully, the residue values can be very large, as opposed to the prediction which is in the range [0, 255]. Since we only care about encoding 255 or 0, we can use very large residue values to force a 255, or very negative residues to force a 0.

residue ≥ 255 ⇒ prediction + residue ≥ 255 ⇒ value = 255

residue ≤ -255 ⇒ prediction + residue ≤ 0 ⇒ value = 0