Video2NAND | Shared Object

Video2NAND

July 11, 2026

Much has been written about turning NAND gates into computers, but knowledge of how to build these NAND gates is not as common. You may think that it’s in the realm of transistors and electrical engineering, but we’ll explore a much more exotic substrate: the video codec.

Specifically, we’ll talk about the VP8 video codec and how to abuse its prediction mechanisms to simulate combinatorial logic. Our goal is to build up a set of composable “gadgets” which can construct arbitrary logic circuits.

A Tiny Bit About Video Codecs

Video codecs are standards which describe a method of encoding a video (a series of images) into some bitstream, and how to decode that bitstream back into the original video. Instead of prescribing exactly how to encode a video, they usually define a general structure and some set of primitives which can be used to encode the video. As such, different video encoder implementations (or even the same encoder with different settings) may encode the same video differently, but all decoders are expected to be able to reconstruct the video regardless.

We will not explain the whole inner-workings of VP8, our video codec of choice, and instead focus on a subset relevant to our purposes. Furthermore, the following explanations are not entirely accurate, in an attempt to simplify the prerequisite knowledge to its essence. If you are interested in learning more about video codecs, I’d recommend reading the Theora spec, which is surprisingly readable.

In a sense, a video is just a series of images. In video codec jargon, these images are called “frames” where each frame is grid of pixels. Frames are generally divided into to two kinds: key-frames and inter-frames.

A frame divided into 8x8 blocks of pixels

Key-frames are frames which are encoded independently of other frames. All data required to reconstruct the image is contained within the representing frame. The pixel data may be encoded directly into the frame, or predicate using intra-frame prediction. Intra-frame prediction allows the encoder to state that a certain block of the image can be predicted from another nearby block.

Since VP8 decodes these blocks row-by-row, from the top-left down to the bottom-right, the intra-frame prediction primitives it offers allow predicting a block using the row above it, the column to the left of it, and the top-left pixel between them.

top left

top[0]

top[1]

top[2]

top[3]

left[0]

left[1]

left[2]

left[3]

A block and the pixels it uses for prediction

Inter-frames are frames which exploit the fact that subsequent frames don’t change much, and allow predicting blocks of pixels based on previously decoded frames. They offer the same encoding primitives as key-frames, as well as allowing inter-frame prediction: describing a block by referencing a block from a previous frame.

We will build our combinatorial circuits purely using key-frames. Partly because the semantics of combinatorial-vs-sequential logic map well to key-frames-vs-inter-frames, and partly because the extra challenge of a limited toolkit is more interesting.

Wires and Gates

Combinatorial circuits are built up out of inputs, outputs, wires and gates. In our case, instead of electrical current representing True and False, each block in the frame will either be completely white (all pixel values set to 255) or completely black (all pixels values set to 0), respectively.

And we’ll model wires going right or down using H_PRED and V_PRED prediction modes. H_PRED stands for “horizontal prediction”, and means that every pixel value in the block is predicted by copying the value of the pixel to the left of it. Similarly, V_PRED stands for “vertical prediction”, and copies the value from above instead.

H_PRED

V_PRED

Drawing the frame as a grid of blocks:

Wiring example

Inputs will be represented as non-predicted blocks, set to a constant value of either completely white or completely black. Outputs are simply labeled wire blocks:

OUT

Inputs and outputs

At this point, only logic gates are left. In order for our system to be functionally complete, meaning it can describe any truth-table, it is enough to construct two gates: NOT and AND. We could have chosen a different functionally complete set of gates, such as just a NAND, but as we’ll see these gates are trivial to construct.

Both gates will gate constructions will use the TM_PRED prediction mode. It stands for “True Motion prediction”, and is only slightly more complex than the prediction modes we’ve seen so far. In a TM_PRED block, the value of each pixel is computed as the sum of the corresponding pixel in the above row and the corresponding pixel in the left column, minus the value of the top-left pixel. So for a pixel with row i and column j, the value will be left[i] + top[j] - top_left.

top...