Kostya's Boring Codec World

So Ukraine is still holding against self-proclaimed second army of the world (though by this time it has earned the title of the most atrocious and hateful military force in the world, the title that had to be taken from the SS troops). And while I can’t stop worrying about my relatives, home city and home country in general, I still need something to distract me at least for a while.

While watching some video about video games, I spotted something surprising in it: a cutscene in Callahan’s Crosstime Saloon. While I worked on supporting Q video format in Legend Entertainment games I remember seeing just one video from that game (the animated title). So I tracked a full CD version of the game and discovered some surprising things about it.

First of all, it turned out to be version 7 of the format (and I’ve seen only versions 3-5 before). Second, it turned out to be mostly the same as version 5 but with F8 opcode in use. This opcode turned out to be used for compact representation of the colours where a code either introduces a cache of up to 15 colours or reuses some previous table and then tile colours are stored in a nibble. Third, beside cutscenes there are a couple of videos of some lady with a small child that look like a home video sneaked in by some developer.

There’s still a lot of work to be done to support it properly (because of the various quirks of the format) but I’ve managed to decode all of the videos from the game already, some of them even without artefacts. This is a pointless but fun distraction after all.

As some of you might know, I had an interest for various game formats for decades (and that’s one of the reasons that brought me into opensource multimedia). And those formats include videos from LucasArts games as well. Actually SMUSH is not an ordinary video format but rather a sub-engine where both audio and video are objects (background, sprites, main audio, sound effects) that should be composed into final audiovisual experience. INSANE is the next iteration of the engine that became simpler (coding full frames, only one object per frame, just one codec, 16-bit video instead of paletted one) but it shares a lot in common with its predecessor.

As expected, the main source of information about those come from ScummVM (and one of their developers made smushplay to play the files in stand-alone matter). There’s a personal story related to that: one Cyril Zorin meddled with some formats from LucasArts games and wanted to add INSANE support (for Grim Fandango but it’s the same for all other games using SNM format) in FFmpeg, sadly he could not stomach review process there (which is hard to blame him for) and abandoned it; some time later I picked it up, added support for SMUSH codecs 37 and 47 (the ones used in adventure games) and got it committed; years later Paul B. Mahol (of future Bink2 decoder fame) added VIMA audio support to it.

Yet there are more games out there and some of them use different codecs, for which details were not previously known. So I decided to finally reverse engineer them to see how the development went. My implementation in NihAV is far from being perfect (there are many issues with transparency and coordinates) but it can decode all files I could encounter with very few exceptions.

So, let’s look at the codecs used for image coding. Audio is rather boring: there’s very old PCM format in SAUD chunks, scaled PCM audio in IACT chunks and VIMA is IMA ADPCM with 2-7 bits per step.
(more…)

There’s this game (or interactive movie rather) called Flash Traffic: City of Angels from Tsunami media that had two editions: DOS one that used BFI videos and DOS edition that relied on special MPEG accelerator for its MPEG-1 videos.

The Multimedia Mike had some interest in it so I decided to look what’s so special about those MPEG videos and why they can’t be played (they produce a lot of garbage if played with the usual players).

Those files seem to be intended for playback only on the special hardware, namely RealMagic card (I’d rather have MPEGMagic card for hardware-accelerated playback of RealVideo thank you very much) that has a special driver for interfacing it (RMDEV.SYS and FMPDRV.EXE). The game engine simply invokes FMPDRV.EXE for MPEG playback and there’s no software playback (considering how powerful machines were back in the day, playing back 352×240 MPEG-1 videos on them was next to impossible, hence the need for special cards offloading the work).

So I had to look inside in faint hope to see what can go wrong.

First of all, I don’t have MPEG-1 specifications and I don’t want to pay ISO hundreds of francs for a copy (and I could not find them online). So I downloaded ITU H.222.0 and H.262 standards (that correspond to MPEG-2 systems and video standards but are free) and used them as the reference (H.262 even lists the changes from MPEG-1 video). Then I tried to hack a simple raw stream demuxer, packetiser and video decoder in NihAV to see what goes there.

The container format seems to be the standard MPEG PS so demuxing was not a big problem. Video has some problems though. The first sign is framerate code: by the standard it should be 1-8, in that video it’s 12. In libavcodec this code maps to an unofficial 12fps mode introduced by libmpeg3 but the file obviously predates that library by many years (and avconv reports 13.3 fps anyway for some reason). Also by analysing group start timecode and GOP structure it seems that the real framerate is standard 30fps. Thus my conclusion is that those files were coded in slightly wrong way and marked with an invalid framerate code to make sure that compliant players won’t try to play them (and only the special videocards will). And considering that even I-frames can’t be always decoded properly, the encoder they used probably was not compliant either.

It is rather hard to find out what’s wrong with the bitstream so I’m not going to continue the efforts but at least I checked it out and verified that the files are not fully compliant and can be decoded correctly only by chance.

Also now I have even less desire to play with MPEG formats but I’ve never been a big fan of them anyway.

Recently The (Multimedia) Mike contacted me and asked if I can look what’s wrong with Clandestiny videos. I did.

First of all it’s worth mentioning that the format obviously originates from Trilobyte as it’d been used in its games years before Quake III was released, it has more features and the decoder in open-sourced Q3 engine still calls it trFMV.

Then I should mention that RoQ support in Libav is not great (and in FFmpeg it’s exactly the same) as the demuxer lacks support for some packet types (like 0x1030 used to signal that it’s a good time to prefetch data), there’s no support for JPEG frames and it goes crazy on files extracted from Clandestiny demo because of all that.

Thus I decided to quickly hack my own decoder for it based on the original description by Dr. Tim Ferguson (yet another forgotten researcher who REd several VQ-based video formats) and played with it to see what’s going wrong.

And it seems the problem was mostly in motion compensation. In some conditions you should double the motion vectors (I think it’s when the first chunk size is zero instead of minus one); also some files have alpha information in the codebook (this is detected by video properties chunk argument being set to one) as it’s apparent from ScummVM code. In either case it’s just the minor details that make things complicated (and I was lucky not to encounter interlaced mode files).

It was a nice distraction but I guess it’s time to do something else.

As I said in the previous post, I was looking at PACo format with an enhanced RLE compression. It turned out to be even more curious than I expected.

Beside the normal RLE mode it has pair and quad RLE (where you repeat two or four pixels) and long operation mode where you can do single/pair/quad RLE, copy or skip using 12-bit number. But it turns out it also has a compact RLE mode that works on a single line using a set of 16 colours and putting operation code, length and colour index into a single nibble instead of a byte (and it also has its own long mode where lengths are using a whole byte!).

That’s the variety I miss in modern video codecs.

I was asked to look at this format used at least in Iron Helix game and it’s a somewhat interesting format.

It turned out to come from Macintosh. There are two small signs hinting on it: big-endian numbers inside the file and the fact it uses default QuickTime palette.

The container is simple but functional: there’s a header containing frame sizes among other thing, frame consisting of several records (usually it’s just video data and frame data end marker; the first frame has initalisation data chunk as well). Frames can have one of two compression methods and coded area size and offset.

Compression is just a slightly advanced RLE: codes 0x01–0x7F mean copying data, codes 0x80–0xFD are used to signal runs, code 0x00 is used to code long operations, code 0xFE is used to signal skips, code 0xFF is used for either runs of pairs or quads of pixels (depending on the run length). Each line is coded independently (i.e. runs or copies can’t go past the current line end). So what’s the tricky part there?

That’s compression method 1 and it works quite well. Compression method 2 is essentially the same but it codes lines in interlaced manner for which I haven’t managed to get a good picture in all cases yet (it seems to code more lines than declared sometimes and interlacing seems to be dependent on both decoded are position and height). But hopefully it won’t take long and I can document it in The Wiki.

You may remember Tsunami Media as a company founded by ex-Sierra people that released a couple of games and ceased its existence.

MobyGames lists the following titles (characteristic is mine):

• Ringworld: Revenge of the Patriarch—an adventure game based on Ringworld novel by Larry Niven. ScummVM supports its but I played it long before that.
• Wacky Funsters! The Geekwad’s Guide to Gaming—a collection of arcade games with wacky design (I’ve only played its sequel though).
• Protostar: War on the Frontier—a reportedly good strategy game inspired by the same source as Star Control II so they share a lot of game design (and yes, they have a common ancestor so it’s not a rip-off. I’ve never played it myself but what I saw looks interesting.
• Blue Force—Police Quest in anything but name. ScummVM supports it but again, I played it long before that.
• The Geekwad: Games of the Galaxy—another collection of standard arcade games but with wacky design. I especially liked quizzes there.
• Flash Traffic: City of Angels—one of the first interactive movies. The Mike has blogged about it.
• Return to Ringworld—a sequel to the Ringworld obviously. ScummVM supports it (so I can re-play it and check whether that empty platform where you seek for the details is really that horrible).
• Man Enough—FMV dating game.
• Silent Steel—yet another interactive movie.
• Free Enterprise—some business simulator.

As you can see, some of the adventure games are supported by ScummVM already but FMV-based ones are not which makes me wonder why.

Man Enough uses the same engine as the previous games (I checked personally. FMV sections there turned out to be animations in the same format as in Ringworld II (I hacked a quick RLB extractor and animation decoder to check that). Side note: whoever added a support for the engine was tired (for a very good reason given below) and hadn’t recognized that it uses LZW compression (so the decompressor is still slightly beautified REd code). Also in this game you have RLBs with elements following each other and those aligned to 16-byte boundaries. So maybe it’d be better just to check if you have first entry right after the library header or not (they all have TMI- header so you can’t mistake it for anything else).

Flash Traffic is special since while it uses the same engine it has all resources stored separately instead of a single library archiving them all. Additionally while TMI format they use is the same, the compression is different. Here you have LZ77-like method which can copy verbatim, copy 32-bit words from already decoded area, fill region with repeating pattern of two bytes, or simply zero region. I have a working implementation for it so I can unpack various resources from the game just fine (but beside BFI or MPEG files that have been supported since long time why should I bother?).

Silent Steel is their newer FMV game that’s mostly just one large MPEG video file and some logic around it (that’s why there was an interactive DVD re-release of the game later).

And now here’s the most important reason why Flash Traffic and Man Enough are not supported up to this day: Tsunami Media hardcoded game logic into the binaries, so while for SCI or SCUMM games you can write a virtual machine and interpret original bytecodes, here you need to decompile game logic from the DOS executable (it’s not an easy task even today) and re-implement it yourself. That’s why tsage engine in ScummVM is full of ${game_name}/${game_name}_scenesN.cpp files for each of the three games it supports. I’m pretty sure the developers won’t refuse somebody else’s contribution for the other tsage games support so you’re welcome to try.

In my previous post I said I was looking at them and while some details were unknown, I got some understanding.

But it turns out The Multimedia Mike despite what he claims still hasn’t lost the knack for REing codecs—first you need to look if somebody else has done it already. And indeed, somebody else has spent two years on reverse engineering the codec. So all that was left to me was to improve its description it (which I did).

The video compression there is quite curious. Huffman-coded data chunks are not that rare (Truemotion 2 had them, for example). Huffman-coded data chunks where one chunk has tree description coded in the beginning that is used for several other chunks is more interesting. But the transforms was the juiciest part there. It turns out you have several modes of operation: fill block, raw block, smoothed DC block (that one uses DCs from neighbour blocks on all sides to create a smooth transition between them all) and the actual Adaptive Orthogonal Transform that represents block as 1-5 patterns (scaled), selected from single matrix. It reminds me a bit about SVQ1 where you had a block constructed from 2D patterns of varying size. But even more it reminds me of Matching Pursuit experimental video codec from Berkley University that also performed partial transform and selected only some bases from a large set (does anybody remember this codec at all?).

Nightlong FMV is a bit different. The format is simple but FMV2 has packed frames and there was no code for handling it in 68k version of the binary. Nevertheless I could unpack it simply by dumping frame data and extracting it with unar (PowerPacker is a strange compression format BTW, it starts reading data from the end of buffer and outputs data starting from the end as well). The unpacked data turned out to use the same format except that the frame size is now full 640×360 instead of 320×180 trying to look like twice as large. I documented it as well.

P.S. I still have some stuff to look at but more suggestions are always welcome.

In a recent post I asked for some stuff to RE and I got some (but more pointers are welcome).

Among those two there was H4M format for Gamecube (kudos to The Mike for providing me with the samples) and FMV format (yes, that’s the extension as well) for Nightlong game on Amiga. This finally gave me a chance to look at how Ghidra 10.0.1 fares with such exotic executables.

First I had to install special loaders for the executable formats (and hack their manifests to claim it’s for 10.0.1 and not 10.0) and also ISA support for special PPC extensions for Gamecube PowerPC CPU. After that it was just loading binaries and analysing them. And there’s nothing else to write about it, it just works.

Now some words about the formats. I’ve not fully REd them (and I don’t know how much time it’ll take either, it all depends on weather and mood) but there are some things I can say about them already.

FMV is a fixed 320×180 paletted video with 4×4 tiles. The compression is very simple: you can either have a raw 4×4 tile, sub-divided 4×4 tile where you can have only some pixels in 2×2 block updated, or skip command (for a single block or for rows). There is also fmv2 where each frame seems to be further (or instead?) compressed with PowerPacker (at least that’s how I interpret frame data starting with PP20).

H4M seems to be a rather advanced format. From what I see it has small frames combined in large blocks with each block having a previous block size stored as well (for seeking backwards like FLV, I suppose). Audio codec looks like a typical speech codec on console. Video codec looks interesting: it has B-frames for starters and it’s definitely not a H.264 rip-off. From what I could gather, it codes several data sources in the frame (i.e. each kind of data is stored separately and not interleaved with the rest of data), some of those data sources contain Huffman-packed data, others are used just to read plain bits and bytes (yes, I saw only functions that read single bit or eight bits, nothing else). Then the data from those sources is used to code coefficients and zero runs for the whole planes (I’m not sure yet if it has blocks at all).

I’ve looked just at I-frame decoding, no reconstruction or P/B-frame decoding yet, but what I’ve seen already makes it a very interesting codec to examine. I was asked to look at it many years ago but I declined that request since I had little experience with both PowerPC assembly and the executable format Gamecube uses (the only time when I looked at PowerPC assembly was Fruity Intermediate Codec and even then IIRC I finished REing it only after x86 binary became available). Now thanks to Ghidra with its decompiler and enthusiasts providing support for such fringe formats I can look at such formats too.