Kostya's Boring Codec World

So I’ve finally implemented NeXT Micro Wavelet decoder (and updated git bundles on the site while at it) and the codec turned out to be even more interesting than on the first glance.

The codec itself consists of three distinct phases: using delta prediction along with wavelet transform, packing results into 16-bit opcodes, and further packing the opcodes with Huffman or LZSS compression. There’s also a raw mode which simply transmits 8-bit deltas so it’s not particularly interesting.

First stage is probably where the codec name comes from: it works on 2×2 pixel blocks that get transformed into the difference from the previous block means (for each component) plus vertical and horizontal differences between block pixels (the same pair is used for all block components). In other words, not exactly full wavelet transform but not exactly no wavelet transform either.

Then the deltas get quantised to a small set of pre-defined values (13 values for red and blue, 15 values for green, 5 values for horizontal and vertical differences) and get packed into a single 16-bit value (that’s merely 63375 combinations out of 65536 possible, which leaves room for special opcodes). Normally one opcode represents a set of packed deltas but in theory it can hold “skip next N blocks” opcodes though I’ve not encountered a file with those.

After we got those opcodes it’s time to pack them (or write them as is). It can be done either with static Huffman coding or with LZSS that operates on 16-bit symbols. Huffman tree definitions are stored in the codec extradata after the main decoder configuration (which deserves its own mention and should get it below) and usually define about two thousand most common symbols, the rest are accessible via the special escape symbol.

Since I’ve mentioned decoder configuration, it needs to be described for being rather special too. First of all, it is not stored in the usual place (codec descriptor atom) but rather in the user data atom on the top level of track atoms. I actually had to modify a demuxer to handle it properly (and discoverd this fact by chance while looking at the end of MOV file and seeing it being suspiciously similar to the file with the default Huffman tree definition). This decoder configuration actually consists of two parts: fixed-size decoder state (essentially RAM data dumped into the file) and Huffman tree definitions. And the decoder configuration is flexible. Remember what I said above about the delta packing into 16-bit symbols? Well, it’s extensible—you can have different number of quantisation levels and delta values to be defined for each component, I simply decided not to support such rich features and stick to the hard-coded delta sets and packing scheme.

Overall, this codec reminded me about Duck TrueMotion 1 for some reason, maybe because of its custom delta tables. All things considered, that’s probably the most exotic codec I’ve ever worked on since it combines both unconventional coding methods (micro wavelets packing into mini-words) and the fact it comes from the rather obscure OS (at least it was ordinary M68K code). I probably had encountered and shall encounter more of crazy coding approaches but it’s not likely to be this combination of obscure technical approach and the obscure platform. As always, I’ll be glad to be proven wrong.

Some time ago I mentioned that I’d stumbled upon a QuickTime sample encoded on NeXT using MicroWavelet codec which was used only there. I also expressed a regret of it being completely lost to time. And what do you know, it’s yet another situation where I’d be glad to be proven wrong—and I was (and I am).

Apparently had I looked around for a bit longer, I would’ve discovered more samples and a decoder to boot. Apparently that decoder was a part of NeXTTime and not QuickTime, which is a completely different thing. And NeXTTime including that decoder could be found on OpenStep 4.x in particular.

While I have not written a decoder for it yet, I’ve figured out enough details to talk about it.

First of all, it’s a sort of several loosely-tied codecs (and I’m yet to figure out what makes it choose which decoding path to take). One of them is a simple wavelet codec with 8-bit coefficients and no additional compression, others are delta coding plus zero-run compression plus optional compression of that data. Optional compression may be either static Huffman coding (with trees stored in a separate file bundled with the decoder—a bit like ClearVideo did it) and an individual tree selected per frame, or it may be LZSS.

It’s nothing outstanding but still it’s a rather curious codec from a rather curious obscure platform (Display PostScript anyone?). And as a final fun fact, it’s internally called “harsh” with the functions being named e.g. harsh_decode_skip. Hopefully implementing a decoder for it would be mild and agreeable despite the naming.

While the weather is stewing here and there’s no desire to do anything, I suppose this is a good occasion to talk about two formats with the same extension that I’m not going to support.

The first TWV format comes from Reality Pump games like Knightshift and World War III: Black Gold. It is not a particularly complex codec but the fact that it’s simplified version of interlaced MPEG-2 or MPEG-4 with an additional layer of headerless deflate compression makes me not want to work on it at all.

The other TWV format comes from Québec and I’ve encountered it in Le Logiciel de Finances Personnel and (mostly with TMV extension) in the game Music Chase. I’ve written about it some time ago, essentially it is QuickTime MOV format with the annoying quirks like all values being little-endian, some additional fields inserted (I suspect that 1-byte version field and 3-byte flags field combination got expanded into two 4-byte fields), and it also uses custom handlers for both audio and video tracks (yes, even pure audio files contain a video track with dummy 17-byte frames). I tried to read the binary specification for the video decompressor but quickly got lost in code for Windows 3.x that Ghidra refused to decompile. The same applies to their special BMP compression (in TBP files).

Hopefully somebody else can fare better but I don’t expect to see these formats supported even in librempeg.

While discmaster is stagnating (you know whom to thank for the shortages of HDDs as well as RAM), I still look through stuff there in hopes to find something interesting. Occasionally I manage to stumble upon something special indeed.

This time it was navigable movies bundled with QuickTime 1.5 or so. Apparently the idea behind them is that all frames are actually tiles of a much larger picture that user can navigate without exhausting all RAM trying to decode it as one contiguous image. If you thought about ISO H.EIC (aka HEIF or AVIf depending on intraframe codec employed) you may be right, but also it got re-branded (and maybe enhanced a bit?) some time later as QT-VR (sometimes I think no matter how stupid modern multimedia idea is, it’s been implemented in QuickTime a couple decades ago).

Anyway, out of four such movies, one was recognised and converted by discmaster software, two were playable (with my player) after I hacked file type tag to be MooV instead of APPL, the last one could not be decoded at all because it was of an unknown type.

Luckily for me resource data of that movie contained the decoder in m68k binary format (sometimes I think no matter how stupid modern multimedia idea is, it’s been implemented in QuickTime a couple decades ago—or did I say that already?). And just by looking at the frame contents I knew it was worth REing as I could spot YUV codebook right at the beginning and it was definitely not Cinepak (or Compact Video as it was known back then). The name was “CDROM Video codec” with tag cdvc but that didn’t tell me much. The file was created in 1992 while Wickedpedia claims that SuperMac Compact Video was added to QT around that time as well.

Anyway, let’s move to the format details. The codec starts with 24-byte header followed by YUV or (theoretically) RGB24 codebook, the another 24-byte header (containing frame dimensions among other things) and finally data. Frame is split into 4×4 blocks and first there is an opcode sent containing block type and number of blocks (minus one) of that type. Blocks are known to have three types: 4 vectors per blocks, 1 vector per block (scaled 2x), or simply skip.

The concepts of codebook-based coding are the same as in Cinepak, even YUV conversion formula is almost the same (with simplified coefficients using multiplication/division by two only). The main difference is using just one codebook for everything and coding format—while Cinepak uses separate bit masks for block types, this codec uses opcodes (which is common for other fruity codecs). So this makes me wonder where this codec comes from and how it is related to Compact Video. Was it some kind of predecessor? Was it developed by Malus as a competition or based on the licensed technology? Why was it abandoned?

Even if I ended up with more questions, it was still a fun way to spend a Sunday weekend (the rest of Sunday was spent travelling to/from Lower Ulm and it’s a differently fun way to spend Sundays; but that’s not the point here). Who knows, with a new search approach I may be able to uncover a couple more of ancient codecs to look at.

P.S. Another fun codec for very early QuickTime was SIVQ (that’s how it was called, I’ve failed to find anything but the decoder for it). It was simply 128-entry 2×2 codebook (in RGB24 format) followed by codebook indices. Probably the name stands for “SImple Vector Quantisation”. That makes it the third proper VQ codec in QT (SMC is a slightly different beast; and RPZA is the first texture codec instead).

Since apparently discmaster.textfiles.com ran out of space (because storage is not cheap now thanks to “AI” companies), I have no new formats to be distracted with and have to resort to looking at the old ones.

As we all know, A**le single-handedly invented multimedia and the existence of IFF ANIM (that pre-dates it by a couple of years) should not confuse you. From what I could find, the earliest QuickTime samples can be found on Apple Reference & Presentation Library 8 CD-ROM that was intended for demonstration but not for the consumers. That disc actually contains three flavours of QT MOV: ordinary MOVs that can be decoded without problems, slightly older MOV that looks almost the same but has slightly different format (and features version -1 both in the header and in the metadata strings) and some extremely old files that do not correspond to the usual MOV structure. Those apparently come from the alpha version of QuickTime around year 1990 when it was still known by its code-name after USian artist of Ukrainian origin.

The first glaring difference is that atoms are not strictly nested but may contain some data beforehand. Essentially all atoms that normally have special header atoms have it before the rest. So instead of (pardon my S-expressions)

(moov (mvhd (trak tkhd (mdia mdhd (minf …))))

there is

(moov [moov header data] (trak [trak header data] (mdia [mdia header data] [all codec description data])))

Data structure is flatter too. In release QT version data for the individual tracks is grouped into chunks, so the header describes both the chunks and what tracks use what chunks (and what are frame sizes in the chunk). Here frames are stored as (offset, size) pairs.

From the accompanying decoder I can see it supported raw video, RLE and motion JPEG at the time—fancy vector quantisation codecs came later.

I hope to support it one day but there’s no hurry. Currently I’m more or less done improving NihAV tools and want to add some practical demuxers, muxers (and maybe even impractical encoders like for Indeo 4 or RedHat Ultimotion). And there’s na_eofdec still waiting to collect enough supported formats for its first release (tangential fun fact: recently I’ve added support for Electric Image format there which is mostly a simple RLE but its frames apparently have timestamps in floating-point format like 0.266 or 0.5).

P.S. I’ve also discovered MoviePak QT codec which looks like JPEG variant. Maybe one day when I’ll have nothing better to do I’ll look closer at it, but for now I have no desire to reverse engineer M68k code in unknown format.

Since I’ve done looking at game formats for a while (I’ve updated na_game_tool 0.5.0 release with the fixed extraction of old-style Cryo Interactive archives BTW), I decided to look at my backlog of unsupported (either mis-detected as audio-only or not detected at all) MOV files from discmaster instead. Of course the majority of them are files missing their resource fork (and majority of the rest are poorly-recognised data+resource forks in MacBinary II format; that reminds me I should improve support for it), and majority of the rest are files that I support already (like Duck Truemotion 1 or Eidos Escape codecs). And a good deal of the rest are Flash in MOV (not going to touch it). And yet there are a couple of files worth talking about.

• 911602.MOV—remarkable for having JPEG frame embedded in QuickDraw stream. It made me finally write a decoder for it (but without JPEG support, maybe one day…);
• a couple of .flm files turned out to have obfuscated moov atom (with something almost, but not quite, entirely unlike TEA if you care). Not something I’d like to support;
• La88110mN1Hz2_20-07.mov—it turned out to be raw YUV420 codec;
• Omni_324.mov—compressed apparently by MicroWavelet on NeXT. Intriguing but I doubt anything else can be found about that codec;
• Music Chase .tmv—a very weird little-endian MOV format with custom video codec (I think I mentioned it before but I haven’t progressed since);
• there was one Flip4Mac-produced sample (which name eludes me), but considering that it stores ASF packets inside MOV it’s not something anybody is eager to support;
• some undecodeable SVQ3 files—apparently they are encrypted;
• and finally there are some QT Sprite files, which seem to be (often deflate-compressed) frames containing several atoms with commands and occasionally image data as well. Sounds too hairy to support but again, maybe one day…

With AVI situation is somewhat better, there are some poorly formatted and encrypted/obfuscated files as well (plus damaged files from AOL archives that start at random position, so contents may be AVI file with some additional garbage in the beginning or missing few dozens kilobytes of initial data). Beside that I’ll probably implement PDQ2 decoder just for completeness sake. Eventually.