Yearly Archives: 2006

Brute Force Puzzles

Cliff Pickover continues his torment of humanity with six puzzles each week (Saturday and Sunday are combined) with his 2006 day-by-day calendar:


Cliff Pickover's Instrument of Terror

As a good number of his puzzles can be solved by brute forcing through the entire solution space, modern computing technology can assist us greatly in mitigating Pickover’s reign of terror. Such is the case with the January 19 puzzle. The actual puzzle is explained a bit more “colorfully”. I’ll distill the mathematical principles. There is a grid of 8 squares laid out as a 4×2 matrix:

  1 2 3 4
  5 6 7 8

You have to place 8 letters in the 4 squares: (B G I O R T V Y) obeying the following rules: Neither R nor I can occupy square 1 or 5; neither V nor T can occupy squares 1..4. Y is left of R, V is left of T, R is above I, and O and B are on odd quares. I took the “p is left of q” type rules to mean that p to directly to the left of q.

Anyway, I deductively came up with a solution. But it seemed there might be more solutions. Sure enough, the official solution was different but challenged the reader to find out how many solutions there are. Fine! I will. Read on to find the solutions and the program to figure it out…

Continue reading →

NES Compression

For budding computer geeks like myself, volume 20/January 1991 issue of Nintendo Power magazine (Mega Man III cover) was of particular interest. In this issue, the editors attempted to shed some light on the technical matters driving the 8-bit Nintendo Entertainment System and give insufferable know-it-alls further opportunity to truly know it all.


8-bit Nintendo Entertainment System

I still recall the puerile, simplistic explanation for compression using a metaphor every Nintendo nerd could relate to: Tetris! I still think about this article sometimes and wonder what compression method they used and for which games. In fact, I located the relevant article section and scanned it for your enjoyment/edification:


NES Compression
Click for larger image

I came across this document describing a compression algorithm used for a Zelda game on the Super NES, the direct successor to the NES, both market-wise and on a technical level. It seems that the scheme is largely a flexible RLE scheme which allows for decoding single- or double-byte runs (output 5 instances of byte 0x56 vs. output 5 instances of 0x56 0x42); decoding runs of an incrementing byte (e.g., output a sequence of 4 incrementing bytes starting with 0xA2: 0xA2 0xA3 0xA4 0xA5); and even using into the encoded buffer as a dictionary and copying runs from a specified index.

8088 Corruption Data Format

By now, Trixter is gaining more fame due to his 8088 Corruption video thanks to a Digg mention. Since Alex more or less dared me to create Unix playback software for this format I downloaded the package and examined the 8088_COR.DAT file. It’s pretty straightforward: There are 0x7D0 bytes before the start of what looks like unsigned, 8-bit PCM data (you can tell because it is all 0x80 values, silence on a scale of 0x00..0xFF). There are 0x2DF PCM bytes before the non-PCM bytes start up again.

Let’s look at these numbers: 0x2DF = 735. I recognize this thanks to the Wing Commander III MVE format. 735 happens to be the quotient of 22050/30. The 8088 Corruption page mentions 30 frames/second in the first place.

What about the 0x7D0 number? That’s an even 2000 in decimal. 2000 = 80 x 25, the size of the standard text mode, in cells, of the old IBM 8088 machines. However, the first frame is entirely a sequence of 0xDB 0x10 byte pairs. My guess is that the video is actually using 40×25 text mode which makes for 1000 cells. Each cell is represented by an attribute byte (defines foreground color, background color, and flashing) and the actual extended ASCII character (0..255).

This strikes me as a classic vector quantizer problem– all the brainpower/horsepower goes into the compression side; the decompression is trivial. I can understand why Trixter claims the compressor is so complex.

Anyway, you want to write a program to interpret the data file? If my guesses are correct, the video will be rendered as 40×25 8×8-pixel cells, or 320×200 pixels. Find a table of all of the ASCII characters. Find another table of all the attributes. Load 2000 bytes from the data file. Render the data based on the attribute and character tables. Load the next 735 bytes. Play them back as mono, 8-bit, unsigned PCM data. Repeat until EOF.

As a means of validation, the size of a single frame should divide evenly into the total size of the Corruption data file which is 9268915 bytes. One frame is 2000 + 735 = 2735 bytes. 9268915 bytes / 2735 bytes/frame = 3389 frames. 3389 frames / 30 frames/sec = ~113 sec.

Hey, Jim: Do I have that all correct? :)

More on this topic:

MultimediaWiki Documentation

No matter how ambitious I get I can not stay ahead of the rest of the multimedia hacking community. I thought it was a lofty goal when I set out the re-categorize and expand upon a bunch of the information maintained at the FOURCC list using a Wiki. But I got suggestions to go further and incorporate the technical documents into the Wiki as well so that anyone can edit them.

And so it begins: I have entered the first few tech docs into Wiki format:

Much more to come.