Kostya's Boring Codec World

I’ve added another bunch of formats to na_game_tool, including both old video formats and game archive support to extract some of those (and other) formats from.

For example, I’ve finally added an extractor for Conquest Earth WAD with its 16-bit FLH (a variant of FLI with RNC compression; it has been supported since version 0.2.0) but there are other variants that justify this post title:

• Alien Virus animation—almost standard FLI with changed tag and some jitter in subchunk sizes (i.e. they may be a byte too short or a byte too long compared to the chunk size);
• Bureau 13—here it is a super-format with chunks comprising FLI headers, FLI chunks or PCM audio—and it may be several FLIs with different resolution too. And it is put into its own archive format (which I also added an extractor for);
• C13 for Hammer of the Gods—at first I thought it’s just yet another hack of the format but after looking closer at the data I realised it’s merely LZSS-compressed. Essentially I just hacked my FLI decoder to decompress data first and operate on decoded data instead of file in this case;
• Stargunner FLC—like other files in the game archive it was compressed using byte-pair encoding (and it may be the only case of such method being used for compression in the wild). In this case file is split into small chunks and unused byte values are used to code pairs (of used byte values or other pairs). Adding support for it was as trivial as in the previous case, but the fun thing here is that after I figured out the decompression algorithm I found out that it’s been known and supported by various extraction tools, it’s just discmaster picked up the laziest one.

Beside that I’ve REd HUF format from Johnny Bazookatone which employs RLE compression and then further compresses video frame data with global Huffman codes. And I’ve also added support for Goosebumps: Escape from Horrorland archive among other things. The curious thing about it is that such archives contain .gvd files which are essentially remuxed AVIs, so my plug-in reconstructs AVI from them by default (but this can be disabled if you prefer the original files instead). Almost all of the files use Indeo 3 but a couple of them seem to use their own codec with no decoder available so here’s that.

In general I still have at least four original formats to add (plus HNM6 and some extractors) but there seems to be enough candidate games to RE for it to be feasible.

P.S. I also looked at SMV format from AGON: The Lost Sword of Toledo but after looking at the binary specification and discovering MPEG-4 ASP decoder there (also if you remove the SMV header it can be played as an elementary MPEG-4 ASP stream) I lost any interest. Maybe Paul will have some interest supporting it in librempeg, maybe not—and I definitely don’t want to mess with such format (the same applies to KSV as well).

Last time I talked about MVI formats, mentioning that I had one more equally German MVI format. Well, the official specification uses CauseWay DOS extender which compresses executables (and I still haven’t found a way to make DosBox debugger dump loaded 32-bit segments, otherwise I would’ve REd a bunch of Psygnosis formats too). Luckily the demo version did not use it and I was able to find how it is coded. Apparently they employed some non-standard LZW which for some reason shuffled low codes, so 0/1/2 are used as special signals—dictionary bump (followed by byte aligning for some reason; other implementations bump dictionary size implicitly and do not insert bits), dictionary reset and EOF correspondingly—while codes 3..257 are used to code bytes. Beside that it’s nothing special: intra frames are (optionally) LZW-compressed, inter frames consist of pixels and mask telling where on frame to update those pixels (both parts with optional LZW compression).

Speaking of LZW, there was this FLK format (apparently Italian) that also employed LZW to compress pixel data along with the command stream with rather simple commands like “repeat pixel N times, skip next M pixels, copy following P pixels” and additionally “restore Q pixels of the background”. As you can guess, the format is used for animations overlaid on something else in addition to video clips. In case of the latter command stream may be absent and you simply put decompressed pixels into a new frame.

Other codecs are Ascon SKS (which is essentially a collection of JPEGs with swapped chroma planes; I did it mostly as a test of JPEG decoder module that I plan to use in other decoders) and Interactive Pictures VID (which I encountered in .evd, .fvd and .gvd files—for files with English version of the video, French version, and general version without speech). This one is curious not only because its binary specification for some reason contains compression for it (which I encountered first) but for the format features itself. Images are split into 8×8 blocks that may be coded raw, with 2-16 colours and a pattern, and a custom-scan RLE I remember seeing in Bink (and XCF but like Bink there are 16 patterns here as well and not just four). Probably nobody cares about it but it was fun to discover.

In addition to that I’ve implemented support for a couple of well-known formats, namely HNM5 (aka UBB2—UBB is apparently the same but lacks headers) and RoQ. The former is a typical French format (you can tell it by the fact it uses crazy motion compensation modes with mirroring and transposing), I implemented it mostly for completeness sake (so I have support for all HNM flavours in my tool, all is left is HNM6). The latter has the same rationale as when I looked at it four years ago: its support in libavformat/libavcodec sucks i.e. it’s adequate for videos intended for id Tech 4 engine but not for the original Trilobyte games (not handling JPEG-compressed frames and not descending into 0x1030 chunk are two most glaring deficiencies). Plus there is a can of worms related to the fact that audio in Trilobyte games uses unsigned predictor while id Tech games use signed predictor and to the fact that for some files you need to scale motion vector twice (and for some files it should be done on a picture scaled twice vertically). I try my best to detect such situations but they do not offer work correctly (and if you wonder, in games engine may have a hard-coded list of files that should be treated differently).

And that is actually not all! I’m still working on supporting some game archives as well (for example, the majority of RoQ files I encountered were hidden in .gjd archives, same as VDX files). One interesting example is Escal compressor. One funny aspect of it is that it is employed in Pumuckl Klabauterjagd, a game for about 8-year olds, while the rest of titles using it are definitely 18+. From technical point it’s interesting as it seems to be inspired by the dynamic variant of deflate with some simplifications: instead of blocks you have codebook definition valid only for the next specified amount of symbols (which are still combined literals and copy symbols, with their codebook coded using code lengths packed with another codebook). Overall it’s distinct enough but the source of inspiration is obvious too.

Overall it means I have only four more original decoders to create plus some of the archive formats to support (like Coktel Vision STK/STK2 as well as the previously mentioned extractor/converter for Monty Python & the Quest for Holy Grail). Probably it will be the last release too as I’m not sure I’ll have enough game formats for another release. Well, there’s also na_eofdec which should get more Amiga formats before 0.1.0 release. And in theory there are console formats if Paul has not written decoders for them all…

While I suffer from thermal throttling, I don’t have much progress to report. Mostly I did some quality of life fixes for NihAV. For example, BaidUTube decided to switch AAC streams to HE-AACv2 in some cases, so I spent some time debugging and fixing SBR decoder in order to get rid of annoying chirps.

But finally I decided to be more systematic and tried to compile a list of known FMV (and FMV-ish) games and what formats they use. In the end I got a list of about four hundred known games, though of course I did not look at all of them: some games are not easy to find, others are console games which I’d rather not touch. SEGA formats are more conventional (often it’s just Cinepak or TrueMotion in AVI), while 3DO or CD-i is something too exotic and for Playstation you have better luck with librempeg.

Anyway, while compiling this list I discovered that PMM format is used in three games, so I decided to implement it at last. It is supposed to contain rather simple quadtree-based video coding with 15-bit pixels that may be updated per-component, and audio may be coded with one of several simple compression ways. Unfortunately format description in The Wiki was somewhat lacking and did not describe audio type 3, so I had to look at the binary specification.

Audio compression type 3 turned out to be real DPCM (while type 2 is not DPCM but rather 16-to-8 bit mapping scheme a la A-/μ-law). It codes packets of 16 bytes where the first byte is delta shift and the rest are 4-bit signed delta values.

The format itself turned out to be more curious than expected as it may be in either endianness (which affects not merely chunk sizes but header fields and code bits of the video data as well). And to push it further, it apparently also code frames as raw palettised data (using SEGA Saturn palette format).

But that’s not all, Area 51 game actually uses YUV colourspace for some of its videos so sometimes you get BGR555 and sometimes it’s YUV555—with YUV to RGB conversion coefficients sometimes transmitted in a special chunk. I suppose it improves compression ratio a bit.

In conclusion I say the usual thing: looking at those old formats is usually more interesting than looking at the new ones. Back in the day developers had fewer opportunities to borrow ideas from the standard formats (except for FLI of course) and threw different crazy ideas in order to see what sticks. For instance, some French codecs liked to perform motion compensation tied to affine transform (i.e. rotating and/or mirroring that block); some codecs used RLE operating on pairs of bytes or copying backwards; some codecs stopped at coding block with two colours, while others used several or even put those colour combinations into a frame-level codebook. Even those two codecs (Reaper and Xilam DERF) that would look like ordinary JPEG clones used an interesting mix of bytes and nibbles to code coefficients without wasting too much space or resorting to Huffman coding. And nowadays people are lazily waiting for H.267 (and if anybody would use H.266 for real) and AV2 (which should’ve been released about four years ago). No wonder people have little interest in multimedia.

P.S. It’s not likely that I’ll work on supporting another game format soon. Even disregarding the heat wave, I have other things I’d rather work on (and maybe there will be something to report eventually).

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.