Archive for September, 2024

Announcing na_game_tool 0.2.0

Saturday, September 14th, 2024

As hinted in my previous posts, I’ve released na_game_tool version 0.2.0. Of course it is available at its dedicated page (and now there’s a link to that page in the “Multimedia Projects” link category). Here I’d like to talk about what’s changed in it and in NihAV.

Probably the most important part is a support of a dozen new video formats—that’s the main task the tool should do after all. I’m not going to duplicate the changelog already presented at its page so those zero people who care may look there. But in the same time it’s worth nothing that I’ve move support for three obscure formats from NihAV (i.e. adapted the code from there and removed it from nihav-game crate). After all, I added support for some game formats there in the first place because I had no other place for that but I did that mainly to test whether I understood their workings right. Now as na_game_tool exists it’s much more appropriate place for such experiments. Maybe I’ll move more formats in the future but not those I care about (like Smacker or VMD) and I might still add new ones like game-specific AVI codec (like IPMA or KMVC).

Now I want to talk about less important technical details. One of the improvements I’m proud about is adding a better detection using regular expression on filename. It is described in a post about Nova Logic FMV formats and it solves a rather annoying problem of certain formats having different flavours that are impossible to detect from the file contents but the naming helps distinguish those.

Also I’ve fixed all spotted bugs in AVI output and added OpenDML support for writing large AVIs. This was needed because some Arxel Tribe games have 24-bit videos in 800×450 resolution and over a minute long so decoded raw AVIs exceed 2GB in certain cases (and intro and advertisement videos from Ur-Quan Masters approached 1GB limit, ending results in ~1.4GB AVI). Additionally I’ve added BMP format for image sequence writer (I don’t think anybody will use it but maybe it’ll come in handy one day for analysing frame palettes).

Having said that, I put the project on pause. As mentioned in the post dedicated to the first release of the tool, my intent is to make releases when it accumulates support for at least a dozen new formats (the ones moved from NihAV do not really count)—and I don’t expect to encounter enough games with undiscovered video formats in the near future. Not that I’d refuse to work on it if it’s not too annoying (see my previous post on Psygnosis games for an example of those) but it may take a year or more to collect enough formats (plus some time to reverse engineer them), so I’d rather concentrate on other things like documenting already implemented formats.

Posted in Game Video, NihAV | 4 Comments »

A look on some of Psygnosis formats

Thursday, September 12th, 2024

This British company had developed quite an amount of good games itself and published even more. As I mentioned in one of my previous posts, I’d like to take a look at some of those (after both seeing their games mentioned in dexvert unsupported formats and realizing that I’ve unknowingly added support for some other games to na_game_tool already). Though I’ve REd the most important format of them all, BMV, long time ago from ScummVM code (their code is still slightly prettied direct conversion of assembly into C++).

Alien Breed

Since this game comes from a wormy developer, its ANM files for the PC version in reality are mere AVIs using KMVC. They don’t play with my old decoder so I’ll have to look what’s different in that version.

Chronicles of the Sword

Fun thing is that most of the game resource files have .PC extension regardless of the type and content. But here I’ll talk about SEQ/*.PC of course.

Those files expose rudimentary chunk structure i.e. they have three short chunks with some basic metadata and frame sizes in the beginning but that’s all. The rest seems to be frame data starting with frame dimensions and image data size (if VGA palette follows it seems to be unaccounted for).

I’d like to take a closer look at it but it’s too annoying: the executable uses CauseWay DOS Extender with packed 32-bit part so I either need to learn how to dump it or RE the extender code to see how it unpacks the code (the trick I used for the next game didn’t work). In either case I’ll postpone it until I’m sufficiently bored and really out of ideas what to do.

Microcosm

This games uses the simplest yet still rather weird codec: scalable RLE.

What do I mean by that? It employs several methods of compression, all are rather simple variations on RLE, except that some have “masked update” opcode beside the usual run/copy/skip. That opcode is a bit mask telling which ones of the following 7 or 15 pixels should be updated with new values or left intact.

But you probably wondered more about the “scalable” part of the description. Well, that format actually codes four 80×200 images per frame (each one may use its own method) and then interleaves the columns. And if you’re not satisfied with the spatial scalability only, it has temporal scalability as well: every even frame is coded independently (i.e. frame 2 updates frame 0, frame 4 updates frame 2 while frame 3 updates frame 1 and so on).

Also it stores palette in BRG order for some reason, which I don’t remember seeing in any other codec—unlike 2-pixel RLE (IIRC I was surprised to see such approach in some ARMovie codecs but it turned out to be not that rare after all).

This format was surprisingly hard to reverse engineer not merely because of its five different coding methods but also because its binary specification is somewhat inaccessible. The executable uses Phar Lap DOS Extender with compressed extended part. I did not know how to approach it until eventually I managed to use dosbox-x debugging facilities and dump what turned out to be the unpacked 32-bit part, which I could later load in Ghidra as raw 32-bit binary and find proper decompression routines. No such luck with the previous game because it seems to load the code into XMS and I don’t know if it’s possible to dump that part of memory at all…

In either case this codec will be supported in na_game_tool 0.2.0 and I can finally start forgetting about it (but not before documenting it in The Wiki).

Novastorm

This game uses a rather curious approach to the video coding—it treats all blocks as being coded with 16 colours plus mask and during video decoding it updates current colours (often by reusing them from some previous block) and mask. And then the draw routine uses those per-block colours and mask to reconstruct it.

Of course you can have fewer colours but it’s an interesting approach. “You want fill block? Just replicate this colour sixteen times. You want two-colour block? Just copy/read two colour values and (optionally) update mask using just 1 bit per cell. And yes, some opcodes tell you to read the full mask for the block while others tell you to read first a mask that tells you for which block rows the mask is actually transmitted.

What about inter coding? The skip mode is simple: you have a fixed-size array of flags telling you which block is coded and for which operations should be skipped.

So it’s a bit hairy to implement and I left that for later.

WipEout

This one is somewhat funny—it uses IF chunked format (i.e. just two bytes per chunk name and 16-bit chunk size) and seems to pack frame data with an LZ77 algorithm before actual video decompression kicks in. The scheme seems to operate on nibbles as some of the opcodes are “fill 32-bit word of output with 0x44444444”, “XOR 32-bit word of output with 0x00F00000”, “replace top/bottom three nibbles of 32-bit word with 0x777” and so on. Also there’s a post-decoding image permutation step (and in case of one mode, it seems to use raw image that gets pre-permuted just to permute it back to the original state in the end; I haven’t looked too closely but it looks suspicious).

Another curious thing is that it has a table of 32-bit values transmitted at the beginning of each frame with several opcodes to copy that value to the output.

Overall, it’s an interesting codec and I’d like to have decoder for it implemented for the upcoming na_game_tool 0.2.0 release but it’s too hairy for that. So it also goes to my “what to do when I’m bored and can’t think of anything better to do” list.

As you can see, I have not done much but even a cursory glance at those formats show the variety of approaches to video coding that you cannot see in the modern codecs. And that’s why I like looking at old formats.

P.S. With the intended amount of decoders implemented I hope to finally release na_game_tool this weekend. There should be a follow-up post about it soon (and then probably just occasional rants for long time).

Posted in Game Video | 2 Comments »

On over- and under-engineered codecs

Tuesday, September 10th, 2024

Since my last post got many comments (more than one counts as many here) about various codecs, I feel I need to clarify my views on what I see as over-engineered codec as well as under-engineered codec.

First of all, let’s define what does not make a codec an over-engineered one. The sheer number of features alone does not qualify: the codec may need those to fulfill its role—e.g. Bink Video had many different coding modes but this was necessary for coding mixed content (e.g. sharp text and smooth 3D models in the same picture); and the features may have been accumulating over time—just look at those H.26x codecs that went a long way, adding features at each revision to improve compression in certain use cases. Similarly it’s not the codec complexity per se either: simple methods can’t always give you the compression you may need. So what is it then?

Engineering in essence is a craft of solving a certain class of problems using practical approaches. Yes, it’s a bit vague but it shows the attitude, like in the famous joke about three professionals in a burning hotel: an engineer sees a fire extinguisher and uses it to put out fire with the minimum effort, a physicist sees a fire extinguisher, isolates a burning patch with it and studies a process of burning for a while, a mathematician sees a fire extinguisher, says that there’s a solution and goes to sleep.

Anyway, I can define an over- or under-engineered codec by its design effectiveness i.e. the amount of features and complexity introduced in relation to the achieved result as well as the target goal. Of course there’s rarely a perfect codec so I’ll use a simpler metric: a codec with several useless features (i.e. those that can be thrown out without hurting compression ratio or speed) will be called over-engineered and a codec which can be drastically improved without changing its overall design will be called under-engineered. For example, an RLE scheme that allows run/copy length of zero can be somewhat improved but it’s fine per se (and the decoder for it may be a bit faster this way); an RLE scheme that uses zero value as an escape with real operation length in the following byte is under-engineered—now you can code longer runs but if you add a constant to it you can code even longer runs and not waste half of the length on coding what can be coded without an escape value already; and an RLE scheme that allows coding the same run or copy in three different ways is over-engineered.

And that’s exactly why XCF is the most over-engineered format I’ve even seen. Among other things it has three ways to encode source offset with two bytes: signed X/Y offsets, signed 16-bit offset from the current position or an unsigned 16-bit offset from the start. And the videos come in either 320×200 or 320×240 size, so unless you have some weird wrap-around video you don’t need all those addressing modes (and actually no video I’ve tried had some of those modes used). Also since the data is not compressed further you can’t claim it improves compression. Speaking of which, I suspect that wasting additional bits on coding all those modes for every block in every frame negates any potential compression gains from specific modes. There are other decision of dubious usefulness there: implicit MV offsets (so short MVs are now in range -4,-4..11,11 for 8×8 blocks and -6,-6..9,9 for 4×4 sub-blocks), randomly chosen data sources for each mode, dedicated mode 37 is absolutely the same as mode 24 (fill plus masked update) and so on.

Of course there are more over-engineered codecs out there, I pointed at Indeo 4 as a good candidate in the comments and probably lots of lossless audio codecs qualify too. But my intent was to show what is really an over-engineered codec and why I consider XCF to be the worst offender among game video codecs.

As for under-engineered codecs, for the reasons stated above it’s not merely a simple codec, it’s a codec where a passerby can point out on a thing that can be improved without changing the rest of the codec. IMO the most fitting example is Sonic—an experimental lossy/lossless audio codec based on Bonk. Back in the day when we at libav discussed removing it, I actually tried evaluating it and ended with encoded files larger than the original. And I have strong suspicion that simply reverting coding method to the original Bonk or selecting some other sane method for residue coding would improve it greatly—there’s a reason why everybody uses Rice codes instead of Elias Gamma’. Another example would be MP3—there’s a rumour that FhG wanted it to be purely DCT-based (as AAC) but for patent holder’s consideration it had to keep QMF, making the resulting codec more complex but less effective.

P.S. The same principles are applicable to virtually everything, from e.g. multimedia containers and to the real world devices like cars or computers, but I’ll leave exploring those to the others.

Posted in Useless Rants, Various Video Codecs | 3 Comments »

The most overengineered game codec

Saturday, September 7th, 2024

…as I’ve seen so far, of course, but the chances for it to keep this title are good.

I’m talking about XCF format (found in ACF files of Time Commando game developed by Adeline Software). For starters, the format allows various commands that are related to the engine (so XCF is used not merely for videos but also for the stage demo records containing e.g. commands to the camera and various other things.

But there’s nothing compared to the video codec design. The frame is split into three parts: fixed-size part with per-block 6-bit opcodes and two variable-length parts. I’d like to say that one contains colour values and another one stores masks and motion vectors, but in reality either kind of data may be read from either source and it’s not consistent even between modes (e.g. for four-colour pattern block both masks and colours are read from part 1 while for two-colour pattern block colours are read from part 2; it’s like they designed it on whatever registers were available in the decoding function at the moment). And for some reason they did not went further and left those frame parts uncompressed.

The real monstrosity though is the opcodes. As I’ve mentioned, they take six bits which means 64 different opcodes. And unlike many other codecs where you’d have half a dozen operations (copy from previous, fill with 1/2/16 colours and such) plus run count, here you have way more. Also it uses 8×8 block size which helps adding new modes. Here’s an abridged list:

  • raw block;
  • skip block;
  • motion block with one-byte motion vector (using nibbles for vector components), two-byte absolute offset, two-byte relative offset or two-byte motion vector;
  • motion block with each quarter using the same four modes;
  • single value fill block—and another mode for filling block quarters;
  • 2/4/8/16-colour pattern block;
  • 2/4/8-colour pattern block quarters;
  • special 4-colour pattern subblock coding mode where you can pick only one alternative option and only for half of the pixels;
  • block filled with mostly single colour except where mask tells to read a new value;
  • block with values coded as nibble-size differences to the base colour;
  • block coded as two base colours (high nibble only) plus low nibble of the current value;
  • block using RLE plus one of four scan modes (line scan, top-down scan, zigzag and inverted zigzag);
  • block using the same scan modes but sending only nibbles for the colour values (first nibble is for base colour high nibble, others are used to replace its low nibble).

And that’s not all, some modes (e.g. motion or fill) have refinement mode. E.g. opcodes 1-4 all mean skip block, but while opcode 1 means copy block from the same place in the previous frame and do nothing, opcode 2 means doing that and then replacing four pixels at arbitrary positions with new values, opcode 3 means the same but with eight pixels, and opcode 4 means using a mask telling which pixels should be replaced. It works the same way for other opcodes supporting it—first do the operation, then optionally update some of the pixels.

If you thought that peculiarities end there, you’d be wrong. Motion vectors are a displacement from the centre of the block instead of its top left corner as in any other video codec. And looks like while the format stored video dimensions, the decoder will work with any width as long as it’s 320 pixels.

I don’t envy future me who has to document it for The Wiki.

P.S. And what’s ironic is that the game was released between Little Big Adventure and its sequel, and while the former used custom format with FLI compression methods (and commands to play external audio), the latter switched to Smacker—a much simpler codec but apparently more effective.

P.P.S. After I reverse engineer a codec or two from games published by Psygnosis I should publish a new version of na_game_tool and switch to actually documenting all the formats it supports; and then do something completely different. At least the end is near.

Posted in Game Video | 8 Comments »