QfG5: resource formats

November 23rd, 2023

There are sixteen formats known:

  • 0 – MDL (model format);
  • 1 – ANM (model animation);
  • 2 – ROM (room parameters, always two integers and floats);
  • 3 – NOD (room background palette);
  • 4 – IMG (room background image);
  • 5 – ZZZ (depth buffer for room background);
  • 6 – GRA (sprites);
  • 7 – QGM (message format);
  • 8 – FTR (some room data);
  • 9 – WAV (effects and music);
  • 10 – RGD (region data);
  • 11 – MOV (intro and cutscenes);
  • 12 – QGF (font files);
  • 13 – STR (some room data);
  • 14 – AUD (speech audio, still in WAV format);
  • 15 – SNC (lipsync data to accompany speech).

I’ll try to document all these formats (except for AUD, MOV and WAV).

QfG: SPK format

November 22nd, 2023

SPK is the archive format used for storing most of the game resources. There are four known archives: CDA.SPK which seems to contain speech (and lip synchronisation data), CDN.SPK probably with scene-specific data, HDN.SPK contains game music plus world map and some other files, HDNW.SPK contains mostly 3D models and animations (plus some QGF files).

Read the rest of this entry »

QfG5 engine: a brief overview

November 21st, 2023

So while I have no real breakthroughs, here is some information about the engine in general.

Quest for Glory V seems to be a 2.5D engine (some 3D objects interacting essentially in circular rooms using static background images) rendering output in 15-bit RGB (while using floats internally and paletted assets). The engine logic is hardcoded, partly inside the executable, partly inside dynamically loaded room modules (in Windows or Mac native format). From what I’ve already seen, there are several global objects responsible for various parts of game engine, including the main engine class with around 160 callable methods; room class takes a pointer to it and provides around ten methods that can be invoked by the engine (and which in their turn may invoke engine methods for various actions). So it’s about a megabyte of engine code and over four megabytes of code in room modules. At least I don’t need to decompile them all at once.

The game data is organised in stand-alone files and SPK archives. Cutscenes are Cinepak in MOV (though IIRC my official pirate copy re-compressed them to use SVQ1 instead), audio is MS ADPCM in WAV. Overall there are fifteen resource types known (audio, lipsync data, text messages, panorama background and its palette, 3D models and its textures, GUI decals and so on). Most of the files are contained in SPK archives which are essentially slightly hacked ZIP archives with initial header replaces with custom index per resource type and each PK entry has numbers changed so it won’t be detected as a ZIP archive without header (at least there’s no compression employed as far as I can tell).

So overall I just need to discover how the main engine loop works, what are all those file formats and reconstruct the room logic. That should take a long time (supposing I don’t give up earlier). Either way I’m doing it mostly to pass time and to find out how far I can get REing something more complex than a codec.

A new project

November 21st, 2023

As I mentioned previously, NihAV is feature complete so while I may still return to improve it, it is not likely that there will be much work to to be done there. That is why I decided to try my hoof at something different—trying to reverse engineer (and maybe re-create) a game engine. I’ve chosen Quest for Glory V for this task as I still have interest in that game and fine folks from ScummVM are not likely to work on it (as it’s a hardcoded engine, more about it later). I fully understand that I may fail as my knowledge about game engines is about zero and having about five megabytes of code to decompile may be too much so I may give up out of boredom as well. In either case it’s not a big loss.

I’m not sure if I’ll ever release the final code (if there is any final code) but at least I will try to document the formats and inner engine working for the posterity. Otherwise it will be about as bad as with the modding community: I’ve seen people making better 3D models for the game and even patching the game logic to do but there is almost no public information about the formats (except for the trivial ones) let alone about something more serious. I know Mike suggested Xentax Wiki once as a better place for such work but I can’t find it so I’ll just keep blogging here.

Money and Multimedia

November 14th, 2023

Inspired by recent events.

It is no secret that sometimes (or rather often, I’d say) political and business considerations prevail over technical ones. The persistent rumour said that MP3 format was not so bad originally but during the standardisation phase it had been changed to contain QMF in addition to MDCT because a certain company still help a patent on it. We have a couple of video codec standards developed not for any technical merit but rather for trying to create a patent-free formats (and failing at that). We see how many modern formats (not just audio or video, but streaming protocols as well) are essentially “one of everything” because each company tries to put its own technology there (probably for patent considerations)—and then even more companies appear with a claim to own a patent on the same technology (some of them form a patent pool, some act on their own). And of course we see Nokia (not the dead phone company and not the tyre producing one either) trying to become the SCO of this decade.

You know, the modern patent system was formed with the intent of sustaining development of new inventions: an inventor brings benefit to society with new inventions, society repays by granting that inventor a protection on exclusive rights for those inventions allowing to get profit from them. In theory a mutually beneficial scheme but people always find a way to game system and here we are. IMO the best patch to the legal system would be to strip those abusing their rights of that right, be it copyright (material part), industrial property rights or anything else. But as an optimist I expect the legions of lawyers to find a workaround for it rather fast.

Anyway, I wanted to demonstrate how political and financial interests spoiled already undead (I’ll elaborate below why I think so) project. And how a certain Frenchman paved a road with good intentions there. Of course I’m talking about FFmpeg (or jbmpeg as I name it after the current most influential person).
Read the rest of this entry »

NihAV: nothing left to do

November 11th, 2023

If anybody read my previous posts, he might’ve picked a notion about me complaining that there’s nothing left to do for NihAV and it is really a problem I have.

Since the (re)start of the project in 2017 it grew from a small package that could only read bits and bytes to a collection of crates supporting various multimedia formats and a set of tools to use them. I had two principal goals: to experiments with the framework design and learn how various multimedia concepts are implemented and also (ideally) make an independent converter and player so I don’t have to rely on the external projects for most of my multimedia needs.
Read the rest of this entry »

A look at Winnov WINX

November 3rd, 2023

It is really a coincidence that about a week after I looked at their Pyramid codec I got reminded that there’s another codec of theirs exists, probably related to the WNV1 codec I REd back in 2005.

So apparently the codec codes YUY2 in 8×8 blocks. Each block is prefixed with a bit telling whether it’s a coded or skipped block. Coded block have additional 4-bit mode that seems to determine which quantisation they’ll use. The data is packed as deltas to the previously decoded value (per-component) using static codebook with values in -7..7 range (plus scaling by shifting left). There’s also an escape value in case raw value should be read instead. Overall it feels like Winnov Video 1 coding.

In other words, nothing remarkable but still a bit more advanced than usual DPCM-based intermediate codecs.

A look at Winnov Pyramid codec

October 27th, 2023

Since I still have nothing better to do, I decided to take a look at some old codec. Apparently I tried looking at it before and abandoned it because Ghidra cannot disassemble its code properly let alone decompile. I think this is a recurring theme with the old 16-bit code, especially the one reading data using non-standard segments.

So I located Sourcer, the best disassembler of the era (that seems to be abandonware nowadays but I cannot swear on that) and used it to disassemble the binary, referring to Ghidra database to locate the functions I should care about. It is not that much fun to translate assembly by hand but at least there was not that much of it.

The codec itself turned out to be a moderately complex DPCM codec compressing 7-bit YUV 4:1:1 data using per-frame codebook and not so trivial delta compression. Codebooks contain pair of delta values calculated depending on number of bits per delta. The data is coded per plane with prediction running continuously for all pixels in the plane:

  // before decoding data
  (delta0, delta1) = get_code();
  pprev = 64;
  prev = 64 + delta0;
  pdelta = delta1;
  for each pixel pair {
    (delta0, delta1) = get_code();
    delta = ((prev + delta0 - pprev) >> 3) + pdelta;
    pix0 = clip_uint8((prev + delta) * 2);
    pix1 = clip_uint8((prev - delta) * 2);
    pprev = prev;
    prev += delta0;
    pdelta = delta1;
  }

Normally such codecs would not bother to generate a codebook for the specific delta size or use something more complex than pix = prev + delta; so this was a rather interesting codec to look at. Hopefully there will be more of interesting formats to study even if sometimes I get the feeling that all undiscovered formats are either trivial or rip-offs of some standard.

Looking at Motion Pixels

October 24th, 2023

There is this very Sirius (or Sirius Publishing, more precisely) family of video codecs (plus one container format) apparently developed by two guys (who like to spam their name even in junk sections of AVI files). Also initially it had its own container format but later they’ve started to target AVI.

Another peculiarity of this format is that initially it targeted games but later was also used as a crappy Video CD alternative.

Back in the day Gregory Montoir REd the original game format for one of the game engine re-implementations he’s famous for and donated the code to FFmpeg as well. Since that time I was curious whether that code can be adapted to play MVI1 and MVI2 as well but the codec itself turned me off.

The codec itself is perverted, both in code and interface. Also it’s inherently interlaced. Normally video codecs in AVI can be recognized by their FOURCC and pass additional configuration parameters in the additional header data. Here they decided to use half of FOURCC to pass configuration flags to the codec and use stream handler FOURCC (that most apps ignore) to tell their decoder should be used to handle it. This alone would make me want to not support it ever, but the binary specification is worse.

Looks like the code consists mostly of handwritten assembly because I don’t know which compiler may generate this madness. There are many versions of the codecs, most of them are 16-bit and the 32-bit version is no better. For starters, it uses segments.

Not so many people remember DOS times and its memory models, even fewer remember them fondly. And almost nobody remembers that in 32-bit mode you can also use FS and GS registers to have custom addressing modes. Well, this codec uses them: it sets FS to the context pointer so context fields are accessed as mov EAX, dword ptr[1A8h] while global variables are accessed as mov EAX, dword ptr GS:[SYM] and of course no decompiler likes that. I was able to work around it in Ghidra by creating a new segment starting from zero but it’s still annoying.

Another thing is (ab)using registers to the full extent. Functions pass their parameters implicitly in the registers, using stack only to save those values before a loop or form a list of rectangles to process. And of course it uses this annoying (for the decompiler) feature as using the same register for two loop counter (e.g. top byte for the outer loop and low byte for the inner loop). As the result Ghidra can’t decompile it properly or even ignores whole blocks of the code because to its belief they can’t be invoked—and it’s still better than decompiling 16-bit version of MVI1 which made decompiler commit suicide. As the result some functions are easier to hand-translate from the assembly.

In either case looks like despite all the improvements it remains about the same as the initial version: data is coded as 5-bit YUV internally and stored using Huffman codes, quantisation and change maps (rectangles that tell which areas to update/fill). MVI2 can use ten different frame decoding modes that differ in how the deltas are coded but essentially it remains the same. They have not even gotten to introducing a proper motion compensation it seems.

So, now I’ve had a good long look at the codec, found nothing interesting there that was not known before and can forget about it. If only there was something more interesting to look at…

HW accel for NihAV player: fully done

October 21st, 2023

As mentioned in the previous post, I’ve managed to make hardware acceleration work with my video player and there was only some polishing left to be done. Now that part is complete as well.

The worst part was forking cros-libva crate. Again, I could do without that but it was too annoying. For starters, it had rather useless dependencies for error handling for the cases that either are too unlikely to happen (e.g. destroying some buffer/config failed) or rather unhelpful (i.e. it may return a detailed error when opening a device has failed but for the rest of operations it’s rather unhelpful “VA-API error N” with an optional error explanation if libva bothered to provide it). I’ve switched it to enums because e.g. VAError::UnsupportedEntrypoint is easier to handle and understand when you actually care about return error codes.

The other annoying part was all the bindgen-produced enumerations (and flags). For example, surface allocation is done with:

display.create_surfaces(
                bindings::constants::VA_RT_FORMAT_YUV420,
                None, width, height,
                Some(UsageHint::USAGE_HINT_DECODER), 1)

In my slightly cleaned version it now looks like this:

display.create_surfaces(
                RTFormat::YUV420,
                None, width, height,
                Some(UsageHint::Decoder.into()), 1)

In addition to less typing it gives better argument type check: in some places you use both VA_RT_FORMAT_ and VA_FOURCC_ values and they are quite easy to mix up (because they describe about the same thing and stored as 32-bit integer). VAFourcc and RTFormat are distinct enough even if they get cast back to u32 internally.

And finally, I don’t like libva init info being printed every time a new display is created (which happens every time when new H.264 file is played in my case) so I added a version of the function that does not print it at all.

But if you wonder why fork it instead of improving the upstream, beside the obvious considerations (I forked off version 0.0.3, they’re working on 0.0.5 already with many underlying thing being different already), there’s also CONTRIBUTING.md that outright tells you to sign Contributor License Agreement (no thanks) that would also require to use their account (which was so inconvenient for me that I’ve moved from it over a year ago). At least the license does not forbid creating your own fork—which I did, mentioning the original authorship and source in two or three places and preserving the original 3-clause BSD license.

But enough about it, there’s another fun thing left to be discussed. After I’ve completed the work I also tried it on my other laptop (also with Intel® “I can’t believe it’s not GPU”, half a decade newer but still with slim chances to get hardware-accelerated decoding via Vulkan API on Linux in the near future). Surprisingly the decoding was slower than software decoder again but for a different reason this time.

Apparently accessing decoded surfaces is slow and it’s better to leave processing and displaying them to GPU as well (or offload them into main memory in advance) but that would require too many changes in my player/decoder design. Also Rust could not optimise chroma deinterleaving code for chroma (in NV12 to planar YUV conversion) and loads/stores data byte-by-byte which is extremely slow on my newer laptop. Thus I quickly wrote a simply SSE assembly to deinterleave data reading 32 bytes at once and it works many times faster. So it’s good enough and I’m drawing a line.

So while this has been rather useful experience, it was not that fun and I’d rather not return to it. I should probably go and reverse engineer some obscure codec instead, I haven’t done that for long enough.