Kostya's Boring Codec World

So NihAV finally got Discworld Noir BMV support and I’ve tested it on all samples from the game to see if it works correctly. Here’s a sample frame:

(I still remember the song Samael plays there and have it somewhere ripped in its full MPEG audio layer II glory).

Now I want to talk about the format since it’s quite different from anything else. BMV used in Discworld II was simple but with two quirks: it employed integer coding using variable amount of nibbles (that were read as bytes but a nibble could be saved and used later) and it could decode frame either from the beginning to end or from end to beginning (reading frame data from the end too!). DW3 BMV is even stranger and let’s start with audio part. Audio codec is very simple: you have 41-byte block with one byte signalling which quantised values tables should be used for both channels and 32 indices for each channel packed into 16-bit words. The main peculiarity is that data is aligned to 16-bit and mode byte can be either in the beginning or at the end of the block. That’s a bit unusual but not strange. Well, it turns out it aligns for the absolute position in a file so my demuxer has to signal whether audio data was at even or odd position. And video is even stranger.

As I wrote previously, video codec is 16-bit now and still employs nibble variable integer coding and copy/repeat/new pixels mode. Luckily there is no backwards decoding mode yet the codec is tricky without it. First of all, where previously there were just three plain modes now we have combinations of those with bytes or nibbles signalling what should be done (i.e. copy/repeat/put new pixels fixed amount of times and then do the other operation another fixed amount of times). And they have different meaning depending on what was the last operation (copy/repeat/put for fixed amount or with arbitrary large one). And if there’s a nibble left unread after last operation or not. But that’s not all! While previously reading new pixels meant just reading a byte, 16-bit pixels can be compressed a bit more. In result we read 1-3 bytes per pixel: first read index byte, remap it, if it’s in range 00..F7 then return pixel in an array, if it’s in range F8..FE then read another byte and use it as an index in one of seven secondary “palettes”; if it’s FF then simply read explicit 2-byte value from the stream. The reference simply used an array pointing to the various functions performing this. And of course palettes can be updated in the beginning of each frame.

Surprisingly, decoder implementation takes about 28kB with a quarter of it being tables. That’s for both audio and video decoder. This is on par with other game decoders (GDV, Smacker and VMD) and feels significantly smaller than the reference (which is about 30kB in a stripped assembled .o file and over 200kB as assembly).

Overall it was hard to comprehend and tricky to debug too. Nevertheless now it’s over and I can probably move to TrueMotion 2X. Or whatever I decide to do when I’m bored enough.

I’ve made some significant progress on REing Discworld Noir BMV.

First, I put opcodes meaning into table (it’s probably the only case when I had to use spreadsheet for REing) to figure out the meaning.

Normal mode of operation have these opcodes:

• 00**00*0 — perform extra-long copy;
• 00**00*1 — perform extra-long invoking of pixel functions;
• 00**xxx0 — copy xxx-1 pixels;
• 00**xxx1 — invoke pixel function xxx-1 times;
• xxxx000y — copy xxxx+3+y pixels;
• xxxx001y — invoke pixel function xxxx+3+y times;<
• xxx0yyy0 — copy yyy-1 pixels and then invoke pixel function xxx-3 times;
• xxx0yyy1 — invoke pixel function yyy-1 times and then repeat last value xxx-3 times;
• xxx1yyy0 — copy yyy-1 pixels and then repeat last value xxx-3 times;
• xxx1yyy1 — invoke pixel function yyy-1 times and then copy xxx-3 pixels.

Then depending on last operation performed mode is changed to: something special for 00****** opcodes, no change for repeat, “after copy mode” and “after pixel func mode” for obvious cases.

After copy mode opcodes:

• xxxxxxx0 — invoke normal mode opcode xxxxxxx1;
• 00**00** — extended repeat;
• 00**xxx1 — repeat last value xxx-1 times;
• xxxx00y1 — repeat last value xxxx+3+y times;
• xxx0yyy0 — repeat last value yyy-1 times and copy xxxx-3 pixels;
• xxx0yyy1 — repeat last value yyy-1 times and copy xxxx-3 pixels;
• xxx1yyy1 — repeat last value yyy-1 times and invoke pixels function xxxx-3 times.

After pixel function mode is simple: xxxxxxx0 opcode is after copy mode xxxxxxx1 opcode and xxxxxxx1 opcode is normal mode xxxxxxx0 opcode.

The special modes may have secondary opcodes that usually boil down to the same thing: either do some more of the same and proceed normally or calculate next opcode instead of reading it from the stream.

And now the second thing: I’ve managed to rip the relevant code from the disassembly, fix it for NASM to handle plus added some fixed to make it possible to invoke externally and linked it against my own small program that parses BMV file, decodes the first video frame and dumps it into file. That approach works so I have something to test my new implementation against. Also since NASM makes all labels visible it’s easy to make debugger report each opcode as it gets called.

To summarise, I have good understanding of the algorithm and I have a working binary specification. This should be enough to finish it soon (unless I get distracted by something else of course).

Codecs are sometimes named after really ridiculous things. Actimagine has named it after nerve agent. Or Panasonic VCR tape format that’s only Wickedpedia has heard about. But I bet on nerve agent (if you didn’t have to study chemical warfare weapons at school then you’re not born in the USSR and be thankful for that).

First of all, I don’t know much about VX except that it was used on game consoles. Also judging by the code it was intended to be used with really low resolutions because it had stride hardcoded to 256 from what I’ve seen.

It reminds me of Mobiclip HD somewhat. I’m too lazy to investigate all details (because I only have an ARM disassembly of some binary with some helpful comments) but here’s what I could find after spending an hour or two on it.

Video codec employs exp-Golomb codes for most things — signed and unsigned ones, bitreader limits them to 16 bits at most. Again, there’s not much I can say about overall structure except that it looks like simplified H.264/H.265 (though it was obviously well before H.265 times) — there is spatial prediction (four modes only: horizontal/vertical, DC and plane) and there’s macroblock subdivision too (into square blocks only, possible sizes are 4×4, 8×8 or 16×16). It still looks like there’s one motion vector per macroblock with motion vector deltas for subblocks.

Again, noone cares.

For no particular reason I’ve decided to look at it and the codec is quite interesting despite being of somewhat WTFy design.

First, it uses 6 buffers so motion compensation can reference any of them while decoding (except that buffer 0 is the current frame and it’s a skip block).

Second, it seems to operate on 16×16 macroblocks that can be split further into smaller subblocks or encoded as the whole. Yes, it’s essentially a quadtree. And motion coefficients seem to be read in the beginning for all macroblocks and then deltas from overall macroblock value are coded for all subblocks when they occur.

Third, it seems to have halfpel motion compensation and some very simple transform that depends on block size and number of coefficients coded. While it’s no DCT I’ve seen that it decodes (last, skip, level) triplets, unquantises them and calls transform function depending on the transform size and position of last nonzero coefficient. And I’m not completely sure but looks like some kind of spatial prediction like H.264 is invoked too.

Truly there are interesting codecs no-one cares about (including me).