Today’s project involved transitioning from a passthrough codec to one that does some minimal amount of coding. This version determines the number of unique colors that a frame uses, codes the palette, and codes the palette indices using the minimum number of of bits necessary. For example, if there are 16 unique colors, only 4 bits are needed to code each pixel. If there are 18 colors, 5 bits are needed. Both of these are common situations for my basic test case:

The Adventures of Lolo, NES

According to my AVI frame-tallying tool:

Assuming 60 frames/sec:
  952 video frames, 0m15s running time, 30263114 total video bytes
  2017540 avg video bytes/sec, 31788 avg video bytes/frame
  min video frame = 5 bytes, max video frame = 35905 bytes

This compression scheme is all keyframes so far. While 30 MB is better than 218 MB, which is the original size of the movie, this is far from an optimal coding. The best compression at this point comes from single-color frames. The next phase is to try some different compression techniques and see which one yields the best nominal result.

At first I was planning to conduct a survey of binary disassemblers just to find one that could disassemble a Linux ELF binary and show the machine instructions in Intel format instead of AT&T format. However, a little man page perusal revealed that the standard objdump utility– part of the GNU binutils suite– knows how to disassemble into this syntax. For the curious, the extra command line parameter that will do this is ‘-M intel’. There it is! No more ugly AT&T ASM syntax.

Just a little FYI.

I got the basic codec infrastructure working correctly tonight. This is simply an FFmpeg module that “codes” the raw RGBA32 data by passing it through untouched and “decodes” it by doing the same. Hey, it still felt like a major achievement.

Next goal is a basic palette coding model.

I decided it is time to stop talking about what I going do and start talking about how I am going to do it. I want to try my hand at creating a new video codec. This is my first attempt at such a feat. I need to write both the encoder and decoder simultaneously. I need to develop some idea about which coding theories I wish to test and how I will go about testing them. I need test vectors for encoding.

But first and foremost, I need a name for this new codec. I have decided on “Palettized Animation Video Codec.” That is what its name shall be unless someone can come up with a better name. The fourcc shall be ‘PAVC’ which is yet unclaimed (although ‘PDVC’ is claimed according to fourcc.org). Since this is an article about PAVC, I need to lead in with some cool shots of old video games, if only as a reminder of this endeavor’s challenge:

Crystalis, NES Widely regarded as the finest video game ever produced

Solar Jetman, NES Perhaps the toughest Nintendo game to get the hang of

Read the rest of this entry »

Originally, I was building this hypothetical video codec around old 8-bit NES videos. However, my Old Skool gaming colleague, Trixter, suggested that I think more generally and design the codec around video output from 1st and 2st generation gaming consoles. For reference, these generations are defined as:

• 1st-generation: Atari 2600/5200/7800, Intellivision, Colecovision, Nintendo Entertainment System, Sega Master System, etc. 1976-1988
• 2nd-generation: Sega Genesis/CD/32X, Super NES, TurboGrafx-16, Neo Geo. 1989-1993

Writing about this codec idea is so much fun because I get to use colorful video game screenshots. For example:

U.N. Squadron, Super Nintendo

Golden Axe, Sega Genesis

Read the rest of this entry »

[a continuation of Custom NES Video Codec]

Data compression is all about analyzing the nominal characteristics of a particular type of data and understanding how that data can best be coded using the least amount of information. Let’s look at some of the characteristics of NES video:

Fun NES Screenshots:
Battletoads	Blaster Master

Read the rest of this entry »

Thanks for Benjamin Larsson for advising me on how to make a proper graph using Graphviz (specify a graph of type ‘prof’ vs. ‘unix’). Thus, here are some nice (and big) graphs based on the call/ret experiment at this point:

• wmv2init() callgraph
• wmv2packet() frame #0 decode callgraph
• wmv2packet() frame #18 decode callgraph

See this post (“Refining The call/ret Monitor”) for details on how the graph data is generated.

And as a bonus, I put the toolset to work analyzing Linspire’s WMV3/WMV9 decoding module. Here are some call graphs (I used the teaser trailer from Halo 2, hence the “halo2″ in the filenames):

• wmv3init() callgraph; I like the way the graph expresses countless functions invoking wmvMalloc() which simply calls malloc()
• wmv3packet() frame #0 decode callgraph; note that this is just a plain, black I-frame and does not exercise a lot of the logic in the module; let’s start small

Reverse engineering is, of course, a tedious, time-consuming, and error-prone task. It requires a lot of concentration that I either do not have or do not care to invest in the RE task. That is why so many of my RE experiments are geared toward automating the task as much as possible. To that end, I am optimistic about this call/ret monitoring experiment since it yields such a good high-level overview of an algorithm contained in a binary (with debug symbols). But it can use some improvement(s):

Read the rest of this entry »

compn has put together a nice inventory of Java-based multimedia formats, including some reverse engineering efforts. And I quote:

Read the rest of this entry »

In the grand tradition of arms races, I like to give equal time to counter-reverse engineering techniques. Colin Hill suggested an interesting way to cause trouble for my call/ret monitoring solution. Make functions that start with a long sequence of NOPs. Instead of calling the actual start address, load the starting address into a register and add a random number to the base address that still points into the NOP range. This would pollute the address space range in the output.

For die-hard, old school reverse engineers, this would also have the effect of creating paranoia of self-modifying code.