Kostya's Boring Codec World

I’ve been working on TM encoder then and now and finally I have some things to say about it.

First of all, general state of the things: the encoder works and produces valid output for both methods 1 and 3 (the encoding is still not perfect but hopefully it can be fixed), it still lacks audio encoding (I need to add WAV reading support to the encoder and extend my decoder to test the output).

Second, I also decided to add an auto-selection option which allows encoder to decide whether to use method 1 or method 3 for the frame. It simply decides which one to use depending on the percentage of most common pair and the number of unique pairs present in total. It does not seem to have any practical use but it may be handy to test decoders that expect only one coding method to be present in the stream.

And now let’s move to the most interesting thing in all this format (at least to me): codebook generation. TrueMotion (1 and 2X) is a rare example of a codec using Tunstall coding (the only other known codec is CRI P256), essentially an inverse Huffman coding where a fixed-length code corresponds to a sequence of symbols.

The original codebook construction goes something like this: add all symbols to the codebook, while the space allows replace most probable entry with new strings using this old entry as a prefix. E.g. for {0 1 2} alphabet (with 0 being the most probable symbol) and size 8 codebook initially you’ll have just the same {0 1 2}, then {00 01 02 1 2} and finally {000 001 002 01 02 1 2} (and you can add another code there to make it full).

Of course it’s rather impractical in this form as not all sequences will be encountered in the data and you still need to code smaller sequences (e.g. how would you code exactly four zeroes with the above codebook?). Thus I decided to do it a bit differently: I only add new sequences without deleting old ones and I also keep a (limited) statistics on the sequences encountered (from two to twelve symbols) so first I add all encountered pairs of symbols, then select most commonly occurring sequence and add all known children of it (i.e. those with an additional pair of symbols at the end), mark it as ineligible candidate for the following search and repeat the process again until the codebook is full. If somebody cares about implementation details, I used a trie for holding such information as it’s easy to implement and understand; and during update process I keep a list of trie nodes for the previously encountered sequences up to maximum depth so I can update all those sub-sequence statistics in one pass over input.

Does it make a difference? Indeed it does. I took the original LOGO.DUK (the only video with a different codebook), decoded it and re-compressed using the default codebook all other videos are using as well as the using the one generated specifically for it. Here are the results:

• original .duk size—2818868 bytes;
• re-compressed file size—2838062 bytes;
• re-compressed with file-specific codebook—2578010 bytes.

That’s using the same method 3 as the original file. With method 1 file sizes with the standard or custom codebook are 2622758 and 2490058 bytes respectively.

As you can see, the difference is noticeable. Of course it requires two passes over input and many megabytes of memory to store the sequence statistics, but the results may be worth it. In theory the compression may be improved even further if you know how to generate a codebook that allows splitting frame data into unique chunks but that sounds a lot like an NP-hard problem to me.

Anyway, I got what I wanted from it so it just requires some bugfixing, audio encoding support, polishing and documenting. After that I can dump its source code for all zero users and forget about Duck codecs until something even more exotic manages to re-surface.

After some trial I decided to release what I’ve done and probably not return to it ever again.

Currently my encoder can encode 15-bit TrueMotion 1 format with different block sizes. It’s probably not very adjustable but there’s not that much to adjust really. I’ll talk why I gave up on 24-bit mode (again!) below, for the other options here’s a condensed version: it does not matter. I’ve tried encoding files with an alternative delta set and it resulted in significantly worse picture quality (but at least encoded frames were usually larger as well); as I mentioned in the previous post, only the first codebook makes sense for 15-bit data (as other two codebooks waste space on coding delta value 7 which is not used in 15-bit mode). Inter mode uses simple skip block as I didn’t bother to think about the possible threshold but it works good enough anyway. In theory I could calculate gradients to determine what sub-block sizes to use for each frame (as I did in Indeo 3 encoder) but again, I decided not to bother.

Now, here are the reasons why 24-bit mode is much harder. For 15-bit mode you can easily calculate deltas for each (decorrelated) component independently rather easily—and the coding method allows selecting deltas in fine-grained way too. In 24-bit mode you have chroma delta pair that updates red and blue components and luma delta pair that updates red component with one value and green and blue components together with another value. In theory decorrelating just green and blue components should help but there we hit another issue: the amount of possible deltas is good enough to represent different delta values occurring during the prediction stage. Essentially you can’t process each component independently and should rather apply deltas as 32-bit values to the 32-bit pixel value, then unpack it and see that the individual components aren’t far enough from the desired ones. It is not that hard to implement but it essentially means writing a second TrueMotion 1 encoder that processes 24-bit data in an entirely different way. Considering its limited use and the fact that it shrinks down horizontal resolution in two times—the coduck (that’s their very original name for it) always processes blocks of two 32-bit words but now those are two 24-bit pixels instead of four 15-bit ones. In either case, even if I see how it should be solved I’m not going to actually do it.

I need to find myself a better task to undertake.

Back in February I wrote about my failed attempt to write TrueMotion 1 encoder. And since I was bored and really had nothing better to do, I tried my hoof at it again.

Last time it was 24-bit encoding, now I tried to approach 15-bit encoding instead and got some results. I guess the moral of the story is that you should not overthink it and use the simplest approach to coding.
(more…)

So, my attempt to write a semi-decent TrueMotion 1 encoder has failed (mostly because I’m too annoyed to continue it). Here I’ll describe how the codec works and what I’ve implemented.

In essence, Horizons Technology PVEZ is a rather simple delta-compression based codec that codes RGB15 (or ARGB20) and RGB24 using prediction from three neighbours and Tunstall codes (I’m aware only of one other codec, CRI P256, that employs it). For convenience there are three possible fixed sets of deltas and three fixed codebooks as well. Videos from (3DO version IIRC) Star Control II: The Ur-Quan Masters used custom codebooks (data for cutscenes was stored in several files and one of them was the codebook specification), and later TM2X allowed using per-frame custom codebooks and deltas but nobody remembers it. The second revision of the codec (do not confuse it with TrueMotion 2 though) introduced inter frames where some of the 2×4 blocks could be marked as skipped.

Initially I had no idea on how to do it properly so I tried brute forcing it by creating a search tree limited to maximum of 256 nodes at each level but as you can expect it took about a minute to encode two frames in VGA resolution. Thus I decided to look at the codebook closer and eventually found out that it’s a prefix one (i.e. for each chain of codes there’s its non-empty prefix in the codebook as well) so I can use greedy approach by simply accumulating codes in a sequence and writing codebook entry ID when the sequence can’t be extended further (or when adding the next code forms a sequence not in the codebook). Which leaves the question of deltas.

There are two kinds of deltas there, both occurring in pairs: C-deltas that update red and blue components (depending on coding parameters there may be 1-4 deltas per 2×4 block of pixels) and Y-deltas that update all pixel components (and for all pixels as well). The problem here was to keep deltas in order so they produce sane pixel values (i.e. without wraparounds) and that’s where I failed. I used the same approach as the decoders and grouped delta pairs into single value. The problem is that I could not keep the result value from causing overflows even if I tried all possible deltas and did not check C-deltas result (as Y-deltas are added immediately after that). And I also made a mistake of using pixel value with its components stored separately (the deltas apparently exploit carries and subtracting with borrows for higher components). I suppose I’d have better luck if I use 32-bit pixel value (converting it to bytes for checking the differences and such) and if I use individual deltas and probably with a trellis search for 4-8 deltas to make sure the result does not deviate much from the original pixel values…—but I was annoyed enough at this point so I simply gave up. And that is before getting to the stage when I have to figure out how to select delta values set (probably just calculate the deltas for the whole frame and see what set fits there the best), what codebook to pick and how to control bitrate (by zeroing small deltas?).

Oh well, I’m sure I’ll find something else to work at.

P.S. I’ve also tried to look at the reference encoder but CODUCK.DLL was not merely a horrible pun but an obfuscated (you were supposed to pay for the encoder and use serial numbers and such after all) 16-bit code that made Ghidra decompiler commit suicide so I gave up on it as well.

P.P.S. I might return to it one day but it seems unlikely as this codec is not that interesting or useful for me.