Kostya's Boring Codec World

So, what’s been added since previous report?

• Road Avenger BIN—as mentioned in an update to the previous post, done;
• Reaper FMV (from Rollcage game)—decoding works fine but the reconstruction does not because of imperfect IDCT implementation on my side (and the fact they don’t use any kind of clipping to make sure the result will stay in range all while employing different tricks like converting double to int by adding a large constant, storing the result as double and read the second half of it as an integer). Overall, I decided not to count it and threw in a couple of easily REd formats described in the next entry;
• a pair of other BIN formats from Data East—they’re the same as Road Avenger BIN but not even compressed;
• Ecco the Dolphin LMS—another raw-tile Sega CD console format except that tile data is arranged more curiously there (128×128 frame is split into 128×32 strips consisting of 8×8 tiles that are arranged in columns). Also it seems to use implicit grey-scale palette (unless there are some external palettes hidden elsewhere), at least watching those documentaries in this way is fine;
• Interplay M95—it’s been described on The Wiki since 2006 (not by me of course) but nobody bothered to implement a decoder for it until now;
• Psygnosis SMV (from WipEout game)—I looked at it back in the day but of course it’s been on The Wiki since 2012. Codec 2 was not described completely right there (partition codebooks are stored in the end, after block indices and not before; and it was not immediately clear that block palettes are stored in global frame order and not in partition coding order) but nothing that a bit of debugging can’t fix.

In either case I’ve filled self-imposed quota of a dozen of originally REd formats and started to pick other formats to support (three done, about nine to go). I have noted about three formats worth supporting and if I can’t find more good candidates—well, maybe there are some more low-hanging Sega CD formats…

And as usual, for more supported console formats, both simpler and much more complex, there’s always librempeg (and that’s not talking about other things it offers like the countless audio and video filters).

P.S. Since I don’t want to do a separate rant, I’ll mention some tangentially related things here.

First, a search for more SMV samples on discmaster returned no unknown real SMV samples but some PMV samples with .smv extension including one that could not be decoded (because of zero root chunk length—I’ve fixed that) and a couple that had nothing wrong with them but were not detected as Zork PMV at all for some reason.

Second, I actually used discmaster to check if there are some interesting ARMovie files. Sadly it still lack an option for omitting supported files so I searched for acornReplayAudio files and filtered out the sources containing actual ARMovie files without video track (somehow I don’t want to check all of ~6000 files so if one or two files coming from same CD are audio-only I excluded it from the further search). After all this winnowing I’ve found two samples with Eidos Escape 102 codec. It’s simple and I’ve REd it some time ago so finally I’ve managed to write a decoder for it. At least I don’t have to search for the samples by the magic string like I did back in the day… Sadly there’s no good way to detect old TCA format so I’m not even going to attempt looking for it.

Short summary for Paul: nothing interesting. I write it as a report of done work and to provide some clues for somebody looking for ancient formats.

After I did EGG format support, I remembered that samples.mplayerhq.hu had a directory dedicated to that and some other game formats (from Smacker to Bink 2), so I decided to look at it and see if I can support some of those. Spoiler alert: there were low-hanging fruits there.

What got supported:

• ICOM video—this one is used in their Sherlock Holmes Consulting Detective series. Initial frame is unpacked, the rest are coded as sequences of skip and masked updates. I’ve managed to RE it from the sample files only, it’s that simple!
• Klondike Moon VID—also raw first frame plus simple RLE for the following frames, and I’ve also managed to RE it from the samples;
• Maelstrom ANM—this one uses RLE for both intra and inter frames;
• Manic Karts AMF—simple RLE with a special large value skip or run modes that encode skip/run length in the way known as Xiph lacing;
• The Amazing Spider-Man vs The Kingpin BIN (Sega Saturn game)—again, I’ve REd it from the two known sample files despite this being a console game. I had some vague ideas about how the console works and indeed it proved to be raw data for tiles/palette/scroll planes (even if it was send as a partial update in some cases) that I simply had to assemble correctly. Just reading some console specifications of its video system was enough.

What I looked at but haven’t REd (yet?):

• Knowledge Adventure Movie—I looked at it some time ago and it’s not a format I’m eager to revisit;
• Road Avenger BIN—this format seems to compress tile data with some custom LZ77-based compressor with a signature “sarc20“. I’ve managed to locate the bit in the binary specification responsible for the unpacking but no references to what and how it’s used. Nevertheless I hope to finish REing it with my new knowledge Update: done. It’s simply one plane with tiles coded and palette transmitted before the compressed data;
• Rollcage Ripper FMV—I REd it long time ago, I just need to locate my notes and finish it. Update: it’s in progress, decoding works, reconstruction is far from good though;
• Rocketz VQM—I failed to find the code responsible for the decoding (and Ghidra decompiler refuses to work on many functions there), and DosBox debugger reports that these files are read in 16kB chunks, so no luck on guessing their internal structure. Maybe one day…

In either case that makes it ten original formats added since version 0.3 and about ninety in total. Two more originally REd formats and another dozen of formats REd and documented by others (those are easier to come by) and my goal for the next release is complete.

As I’m still in a search for formats to implement in na_game_tool for 0.4.0 release, one game brought two formats at one—and both start with a letter I had only one or two formats before.

I’m talking about ID4 or Independence Day. Its Sega Saturn port uses EGG format which has not been REd before. But first I was able to locate PC version of the game with its animations in YQS format, so I started with it.

It turned out to be a very curious format, with YUV frame coded per plane using quadtree and two separate streams for pixel values and for control bits, eight streams in total (there’s IMA ADPCM audio as well and fixed-size vector codebook for luma). Essentially plane is split into 8×8 (luma) or 4×4 (chroma) blocks which may be skipped entirely (if the control bit is not set), filled with single value obtained from the stream (again, if the next control bit is not set) or split into four sub-blocks with the similar approach. 2×2 chroma blocks may be skipped, filled or coded raw; 2×2 luma blocks additionally may use input pixel value as a codebook index and use that 2×2 vector (flipped or not, depending on control bits).

After that I actually looked at EGG. It had similar structure but with some changes: frames are always 20kB and do not contain audio, values are big-endian and bitstream format for 2×2 luma blocks differs. I still had to resort to the binary specification for it though—loaded CPE file in Ghidra as raw SH-2 binary, located animation names and started attempts to disassemble data around them. Eventually I got the function that looked very similar to the one in PC version (except that it decoded just luma instead of doing all three components and converting macroblock to RGB). Thus I got a working decoder for this format as well.

That’s how I got two more formats supported, which makes it almost 42% of my goal. The problem is still mostly to locate the formats that can be supported (most of the ones I haven’t implemented need a lot of work to unpack the binary specification). In either case I’m in no hurry and it was nice to learn more about old formats.

It’s been some time since na_game_tool release and I’ve finally started working on adding new formats for it again (for v0.4 the goal is to have a hundred of supported formats including a dozen of fresh ones, currently it has only about eighty). And since newly added formats are somewhat remarkable, I decided to talk about them.

Spidy Ani from Imperium Galactica. The name sounded vaguely familiar and indeed I’ve encountered it before. I did not bother to support old sprite format since they are just animations for which you need to know the background image and palette. Version 2 contains both palette and (optionally) audio, making its support much more reasonable. As for the compression, it actually keeps the old RLE method and introduces a new one (where low values mean copy length instead of a literal) plus it adds optional LZSS compression. The best part is that it’s not been reverse engineered by somebody else but it has been documented (in open-ig wiki) as well.

Shadowcaster cutscenes. This is a format used by a game published by Origin, it turned out to be RLE optionally further compressed by LZSS (I shan’t blame you if you see some similarities here). The main difference is that the format contains commands for e.g. playing an external XMI track (or stop playing it). And instead of one palette it can store several and switch between them arbitrarily.

Castles 2 (CD version) greyscale video. This one is very special: the game has colour cutscenes in Interplay MVE format (usually with castles) but beside that it apparently has some greyscale animations lifted from public domain films. The files have .m extension and start with “BYON PIZZA” string, definitely not hinting at Byon Garrabrant, who was the lead programmer of that game.

It was extremely hard to read the binary specification for it as the executable stored that code and data in executable overlay. That means that it was in a special part of executable that gets loaded on demand, thus lacking proper references to the data and even functions. Luckily it turned out that I didn’t need it at all.

One of the sequences turned out to be just one black (or white) frame. Seeing that the frame was exactly 1/4th of raw image and filled with 0x40, I decided to calculate a histogram of some other (larger) frame. It turned out that indeed if you output values in 0x00-0x3F range as is and repeat 0x40-0x7F values four times you get exactly full image. Then by looking at the reconstructed image I understood that it codes data in 2×2 blocks (and in inverse mode so 0x00 means white and 0x3F means black). After that figuring out that codes 0x80-0xFF in subsequent frames are used to signal skips was trivial.

That was fun. Hopefully I’ll encounter more interesting formats in the future.

P.S. I’ve also added PI-Video decoding support to NihAV. The codec was used at least in one multimedia encyclopaedia and did some non-conventional things with LZW coding. I’m still not sure that it was a good idea because codec developer may be russian but since I could not find any information about him (or the companies involved beside them being Western European), I’m giving it the benefit of the doubt.

First of all, I’m happy to announce that I’ve finally managed to reverse engineer a format for game called Wing Nuts which means I’ve finally collected formats for the whole alphabet. So I want to implement another format that I’ve REd and I can finally release na_game_tool 0.3.0 in a week.

But what I really want to talk about is the game format itself. There are no real game videos but rather game engine data files containing various kind of data, including video frames. I could also extract PCM audio but I don’t know how to synchronise it properly so I ended up with a video-only decoder. MIDI data was yet another option that I ignored.

What is curious is the video compression format. While REing it I had constant thoughts like “hmm, it stores chunk type in a byte followed by 24-bit big-endian number, just like Cinepak” or “hmm, it uses 2×2 vectors and either scales them or combines four of them in a single 4×4 block, just like Cinepak” or “wait a minute, this bitstream format—chunk markers, flags and vectors—are exactly like Cinepak”. There are some differences from the usual Cinepak we all know though: it is a paletted format (with palette stored in a similar form before actual image data) and it has some additional chunks with codes 0x60-0x62 which seem to contain some auxiliary information used by the engine.

So seeing this shortly after CinEApak and knowing that SEGA company used slightly modified Cinepak format on its consoles, it makes me wonder is the codecs was more widely licensed and tweaked than we are aware of. That would make it even more like Duck TrueMotion (which was also widely used in game videos, on consoles as well, and with a special flavours used at least in one game).

So now there’s just one letter left, hopefully it won’t take that long to find a suitable format.

Meanwhile two formats for letter ‘o’ have been added, both formats are formally from Origin.

One is FLIC-in-IFF used to store intro and ending for Ultima VII (both parts). Actually there are also fonts and speech stored there but since you need external data (plus game engine) to combine them properly I ended up simply decoding animations from those archives.

Another one is equally flimsy—System Shock movies (which are predominantly just audio tracks used probably for audio logs; also the game reminds me of Paul for some reason). What’s remarkable is that it essentially combines two different coding methods for two sizes: VGA movies are RLE-coded, SVGA movies use 4×4 tile coding with additional Huffman coding of tokens. Essentially tiles are coded using tokens representing opcodes, which may refer to 4-16 colours from the global colour table or some other operation (e.g. “skip N blocks” or “repeat previous operation” or even “fill block with these two colours”); tokens are Huffman-coded, both colours and Huffman table may be transmitted at any time. Luckily I did not have to RE it from scratch as the engine code has been open-sourced some time ago.

Just a couple more formats and I’ll be able to make 0.3.0 release at last.

And I’ve thought for another fun goal for 0.4.0: get a number of supported formats to a hundred (it would be better to hit some round number like 128 but that’s more of a milestone for the improbable 0.5.0 release). Currently I have 70-something formats listed and that will number will increase to 80 for the upcoming release for sure. Finding about eight extra formats to support is easier than finding twelve formats to RE. And to put things into perspective, librempeg lists about 270 video decoders (excluding raw formats and hardware accelerated decoding), some of them being equally incomplete, simple, or being a small variation of another decoder. So having a third of that number for game-only video formats (most of those being unique too) is a respectable feat IMO.

Finally I’m closer to the goal of having formats for every letter of alphabet supported in na_game_tool. Finally I’ve managed to add a format(s) starting with ‘y’.

First, I was able to locate an obscure game ported to Windows from SEGA Saturn called Yumimi Mix. The best part of is the first letter in its name and that it has some animation formats. Two and a half of them actually: there’s a companion game Dinosaur Island with its own cutscene format starting with ACUT magic, and there’s a sprite collection and animation format starting with ABLK magic that has two distinct coding modes (plus raw).

All these formats are based on the rather standard approaches used by the console: a scene is composed of (possibly several) overlaid sprites, each sprite is split into 8×8 block that belong to a global tile atlas. Both tile data and tile indices are compressed by some variants of RLE plus there are multiple palettes and commands to compose sprites and backgrounds and do some other stuff.

Since I’m not inclined to re-implement half of the game engine for that I simply ended up with a guesswork that gives acceptable results in many cases. Of course it’s far from perfect but it still better than something.

And then dexvert added MXV format to its list of unsupported formats. Since it’s used in Yo Matías game series (as well as some other games by Caimán), it was a perfect backup candidate. Of course it’s proper to call it simply mxv but I know what I’ll call it.

The format is rather simple: PCM audio and 8- or 16-bit intra frames with no/deflate/LZW compression. There’s a later iteration of the format using Vorbis audio but you should expect librempeg to support such format, not na_game_tool. So it took me just a day to RE and implement it compared to about ten day for the Yumimix formats (which are still rather incomplete).

All in all, it’s moving fine. I have some prospects on filling two other missing letters and probably by then I can finally make 0.3.0 release. Despite Paul’s suggestion I’m not going to hunt and/or invent formats with names starting with every combination of two letters of alphabet, but I’m not going to abandon the project for good either. It’s just without a clear (even if artificial) goal it’ll take more time to get enough formats for the next release.

Since last time I’ve added a couple more formats:

• finally did Dragon’s Lair (PC port) videos—it turned not as bad as I expected after Space Ace;
• Jazz Jackrabbit 2 videos (from the decompiled decoder in Jazz² Resurrection)
• finally implemented Xilam DERF format support (audio and video);
• ported FutureVision FCMP and FST decoders from main NihAV;
• freshly implemented scene format for Psychic Detective;
• and Cyclemania video support.

If you for some unfathomable reason wonder when it will be released, I can answer: not soon.

As I mentioned before, I intend to make a release with at least a dozen of new REd formats and I’m still far from that goal. Since version 0.2.5 I’ve added support for about fifteen formats but most of them don’t count: some formats were ported from NihAV, some were based on other sources (like game engines or—for some planned additions—entries in The Wiki not based on my research), some are of poor quality and don’t really count. This means only about half of those formats is eligible—and I don’t know where to find another half (and that’s not counting other things I’d like to work on).

And there’s another small but irritating detail: so far I’ve implemented decoders for all but three letters of alphabet. Formats with names starting at ‘o’, ‘w’ and ‘y’ are still missing. Of course I can easily fill the gaps by supporting Origin Xan, Westwood VQA (or CPS) and Psygnosis YOP but I’d prefer to have something original instead of well-known formats supported elsewhere.