GoKawiilVideo2NAND
July 11, 2026
Much has been written about turning NAND gates into computers, yet 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.
You can also read this follow-up post which describes some glossed over details.
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
... continue reading