Kostya's Boring Codec World

As I’m still working on my game tool, I decided to implement video format from the Jack Orlando game. So now na_game_tool has AVX support and I’d like to say something about the format.

The format is a rather weird mix of different things. It starts with a fixed-size audio block and that size depends on whether it’s 8-bit PCM or IMA ADPCM (with stereo samples packed into interleaved 32-bit words), it seems to have block structure where an arbitrary chunk of data is stored as 32-bit size plus block data which includes video data with accidental headers. Yes, the file internally may have several FLX animations with different framerates too, so e.g. a 16-fps piece of animation may be followed by 10- or 24-fps animation. And audio stream is global even if it’s stored in small chunks inside FLX (since you have several seconds of pre-roll audio in the beginning). Oh, and palette data may be stored as RGB565 or RGB24 (which you’re supposed to understand from palette chunk size). Video compression is simple but somewhat weird too, as RLE is used to optionally compress data before it gets decoded.

In either case weird does not mean bad and in my line of hobby an interesting codec is worth more than a popular one.

P.S. And there’s even weirder format known as Knowledge Adventure MOV. I gave up on REing it but apparently video there is split into tiles (4×2 or 2×1 pixels apparently) and frame data is those tile indices that may be stored uncompressed, RLE compressed or, apparently, using an arithmetic coder with static frequencies stored in the file header. The difficulty comes from self-modifying code and not the cute kind that simply modifies couple of instruction constant arguments but one that substitutes function call address with a pointer to a special memory buffer allocated in a context and filled elsewhere. In theory it can be figured out without much hassle with, say, a built-in DosBox debugger but I’m not inclined to do that (at least not now).

Back in the day I wrote a bit about this format and since it’s rather interesting I decided to implement its support in my game tool.

Eventually I got it working except on two files that seem to have certain frame data unpacked incorrectly (it’s the feature that makes this format interesting in the first place—per-group order-1 Huffman coding). And for every file decoding seems to go past the data boundaries at the end so I insert some additional zeroes at the end of packed data to make it work (another fun fact – apparently last eight bytes of both opcode and colour parts of inter frame seems to be always unused). And it seems audio data is always coded as silence. The actual cutscenes do not make much sense either as it’s usually a static cartoon image superimposed over a 3D rendering of some lady in a tower-like structure (the game does not deserve any associations with Sierra titles so I’m not using other words to describe it). Sometimes her lips are moving (if you can notice it behind the other image), quite often they do not:

All in all, this is a rather weird format for a seemingly weird game but I don’t regret wasting time on implementing a decoder for it.

While I’m still looking for a solution on encoding video files with large differences with TrueMotion, I distract myself with other things.

Occasionally I look at dexvert unsupported formats to see if there’s any new discovery documented there in video formats. This time it was something called VPX1.

I managed to locate the sample files (multi-megabytes ones starting with “VPX1 video interflow packing exalter video/audio codec written by…” so there’s no doubt about it) and an accompanying program for playing them (fittingly named encode.exe). The executable turned out to be rather unusable since it invokes DPMI to switch to 32-bit mode and I could not make Ghidra decompile parts of the file in 386 assembly instead of 16-bit one (and I did not want to bother to decompile it as a raw binary either). Luckily the format was easy to figure out even without the binary specification.

Essentially the format is plain chunk format complicated by the fact that half of the chunks do not have size field (for palette chunk it’s always 768 bytes, for tile type chunk it’s width*height/128 bytes). The header seems to contain video dimensions (always 320×240?), FPS and audio sampling rate. Then various chunks follow: COLS (palette), SOUN (PCM audio), CODE (tile types) and VIDE (tile colours). Since CODE is always followed by VIDE chunk and there seem to be a correlation between the number of non-zero entries in the former and the size of the latter, I decided that it’s most likely a tile map and colours for it—and it turned out to be so.

Initially I thought it was a simple bit map (600 bytes for 320×240 image can describe a bit map for 4×4 tiles) but there was no correlation between the number of bits set and bytes in tile colours chunk. I looked harder at the tile types and noticed that it forms a sane 20×30 picture so it must be 16×8 tiles. After some more studying the data I noticed that nibbles make more sense, and indeed only nibbles 0, 1, 2 and 4 were encountered in the tile types. So it’s most likely 8×8 tiles. After gathering statistics on nibbles and comparing it to tile colours chunk size I concluded that type 2 corresponds to 32 colours, type 4 corresponds to 1 colour and type 1 corresponds to 16 colours. Then it was easy to presume that type 4 is single-colour tile, type 1 is downscaled tile and type 2 is a tile type with doubling in one dimension. It turned out that type 2 tile repeats each pixel twice and also uses interlacing (probably so video can be decoded downscaled on really slow machines). And that was it.

Overall, it is a simple format but it’s somewhat curious too.

P.S. There’s also DLT format in the same game which has similarly lengthy text header, some table (probably with line offsets for the next image start) and paletted data in copy/skip format (palette is not present in the file). It’s 16-bit number of 32-bit words to skip/zero followed by 16-bit number of 32-bit words to copy followed by the 32-bits to be copied, repeat until the end. Width is presumed to be 640 pixels.

P.P.S. I wonder if it deserves a support via stand-alone library named libvpx1 or libvpx and if this name is acceptable for Linux distributions.

Since I’m still not in the mood to do something serious, I decided to play some adventure games from Legend Entertainment (you know, parser-based, mostly with EGA graphics). And some of their VGA games like Companions of Xanth or Eric the Unready contain full-screen cutscenes in unknown format. The earlier released Gateway II used the standard FLIC for many of those, SVGA games switched to .Q format—but nothing obvious for these ones. Blackstone Chronicles used QuickTime and thus is not interesting.

So I decided to look what ScummVM source code has to say about it (unrelated fun fact: it’s the only open-source project I donated some money to). Of course there’s a fork with some halfway done support of later Legend Entertainment adventure games, including its picture format support (no such luck for EGA-only games, it seems).

Apparently .PIC files are more a collection of sprites and even full backgrounds. Depending on the game one file may contain all room backgrounds, or just single area backgrounds plus related animations (e.g. flowing water or burning torches), or it may be character sprites, or—as one should expect—a cutscene.

Frames in .PIC may be full frames or delta frames. In the later case they only update a part of the screen (either by replacing an area or XORing it). The more interesting thing is how frame data is compressed. The reference code is reverse-engineered and not so informative, so it took some time to understand it. First apparently there are tables and code used to generate new tables, which turned out to be exactly what I suspected them to be—Huffman codebooks. After a bit more messing with the algorithm, it turned out to be yet another LZ77-based compressor with static codebooks and rather complicated coding that reminds me of deflate… Of course I got suspicious at this stage (it looked a bit more complex than in-house developed compression schemes for game engines usually are) and indeed, it turned out to be Pkware Data Compression Library. And I could’ve found that out simply by looking into strings in one of the overlay files. Oh well…

At least it’s yet another puzzle with formats solved. Also it’s the second time I recently encounter animation format using DCL for compression (previously it was Gold Disk animation). Which makes me wonder what other common LZ77 flavours were used in the animation and video formats. deflate (along with newer contenders like LZO, FLZ and such) is very common in screen-recording codecs. LZS was used in Sierra games .RBT, I vaguely remember RNC ProPack being used by some video format. Nightlong on Amiga used PowerPacker. Did anything use LZX (it came from Amiga before being bought by M$ so maybe it had a chance there)? LZRW? Homebrew schemes are dime a dozen (like all those LZSS variations), I wonder more about the (de facto) standard compression libraries being used in video compression. Anyway, I’ll document them as I encounter them 😉

In order to distract myself from the thoughts why most politicians have their heads so deep in their asses that French ones out of all people seem to be the bravest, and what can I do to help destroying russia beside regular donations, here’s a post about completely unrelated REing work.

Since I had nothing better to do, I looked at the format use in Azrael’s Tear game and re-visited Talisman game. And while one of them is a 3D game from a British developer and another one is a 2D game from a German one, the cutscene formats used there have more in common than one would suspect (and their design distinguishes them from the majority of the formats).

It is common for various game formats to represent frames as small blocks with motion compensation or raw data, but I can’t remember any other such format that would use data compression on container level instead of it being a part of e.g. video data compression (of course there’s Ogg Matroska that implements such feature, but beside it I can’t think of any format doing that). In both of these formats (with not so creative extensions ANI and MOV) static Huffman compression is employed to compress several chunks of different data type. In ANI (used in Talisman game) data is split into groups of frames that start with a chunk defining which one of the predefined Huffman trees should be used to pack them all and to what symbols the codes should be assigned. In MOV (used in the other game, naturally) audio and video frame blocks are grouped into larger chunks and those chunks may be optionally compressed using static Huffman tree transmitted in the beginning of chunk payload.

ANI format features another peculiarity: there are other codecs that use motion compensation plus rotation (like formats from Cryo Interactive IIRC) but I can’t think about any other format that performs motion compensation and replaces one of the pixels in a block with a new value. Of course it is not a revolutionary idea but I haven’t seen it implemented like that before.

And that’s why I like those old game formats: they may be not the most effective ones but they contain more originality than the modern formats. The main problem is finding such a format—there are too many games released (which are also sometimes too hard to find) and the majority of them uses FLIC or Smacker anyway (or Cinepak in AVI or MOV for newer ones). But sometimes I encounter a mention of a game in some review and get lucky. I hope such finds happen more often though…