Various Video Codecs « Kostya's Boring Codec World

Archive for the ‘Various Video Codecs’ Category

Indeo 3: cell coding

Monday, January 30th, 2023

So we partitioned out the frame and now have to code the cell data. How to pick the best parameters in this case?

The patent suggest calculating vertical and horizontal differences (i.e. differences between top-bottom and left-right neighbours) and depending on how large they are select one of the modes. Codebook selection is not reviewed at all. The reference encoder calculates those differences and uses them to set both cell coding mode and select codebook. I.e. if both differences are large use mode 0 (fine-grained coding), if only one difference is large use mode 3 or 11, otherwise use mode 10. And a ratio of the differences is clipped, multiplied by a magic factor, then by a rate control factor and used as an index in a special magic table to select codebook.

Since my goal is to learn something new instead of simply replicating something existing, I took a completely different approach (that should contain less magic). Mode selection is done by comparing differences and amending it if I decide to use two codebooks. I used the fact that first eight codebooks mostly have differences in form kN+1 and the next eight codebooks have differences in form kM. So I simply calculate for each codebook how many delta values are represented best with those formulas and select the best fitting one. Also I calculate it separately for the even and odd lines (the histograms can be merged later to give a total statistics) so I can select the appropriate codebook or codebook pair for the coding mode. Maybe I’ll have to adjust the scheme for the rate control but it’ll happen later. Side note: Indeo 3 specifies a per-frame set of 16 codebook pairs that all cells should use and global codebook index offset so single-codebook modes may use additional 5 codebooks; the set seems to be static and has regular structure and I’m not sure that global codebook index offset is ever used.

That’s it. The rest of the things should be rather trivial: I’ve written how to perform motion search before, rate/quality control has never been great in the original codec (maybe I’ll report how I did it when I get to it), zero run compression is nothing special either. There’s not much to write until I fix some bugs, improve compression, introduce rate control and validate it against the reference decoder. And that will take a long time…

Posted in indeo3encfail | Comments Closed

Indeo 3: splitting the frame

Saturday, January 28th, 2023

As mentioned in the previous post, Indeo 3 splits frame into cells using binary trees and they’re coded using one of several possible modes. In reality it’s more complex: there’s a primary tree that splits frame into regions and tells how to code them (intra or inter) and those regions themselves can be split using another binary tree to tell which coding method to use (or to skip decoding it entirely). See, it had tree coding, prediction units and coding units two decades before H.265! And slices as well: it divides data into strips 160 pixels wide too.

Splitting the frame optimally is practically impossible task (because of its combinatorial complexity). In reality though it’s much simpler: first we split plane into 160-pixel wide (or 40-pixel wide for chroma) strips then split them along the largest dimension until we get cells of maximum acceptable size (which seems to be 767 pixels but the encoder seems to handle up to 2048 pixels in a coded cell). Then it’s up to a secondary cell coding.

From what I could gather in the encoder, it also tries to split secondary cells if they’re above the limit but it’s the same value used in the reference encoder even if it could be set separately.

Since my goal is to learn something new instead of re-creating something existing, I use a different approach: initial mode is selected by the relation between horizontal and vertical differences (if both are too high I try to split the cell and try again). Similarly for inter mode I first try to see whether the cell can be coded as inter (and if splitting it will make at least one of the sub-cells code as inter) and if not then I resort to intra coding.

There is probably a better way than brute force to find out the optimal splitting but for lack of it a simple heuristic should do.

Cell coding mode and codebook selection is a topic best left for the next time.

Posted in indeo3encfail | 2 Comments »

Indeo 3 overview

Friday, January 27th, 2023

The overall idea behind this codec is simple: a frame is split into cells of variable size (the patent says “a roughly regular grid of cells”) using a binary tree, each cell can then either be coded in intra mode (differences to the previous line) or inter mode (differences to some region in the previous frame). Coding is done by splitting cell into 4×4, 4×8, 8×8 or 8×4 blocks and using one or two of 21 codebook to code pairs of differences (with some tricks to compress small differences and zero runs even further).

The patent describes thirteen different modes, the decoders I know about support only some of those:

mode 0—code 4×4 blocks using a single codebook;
mode 1—code 4×4 blocks using two different codebooks for even and odd lines;
mode 2—code 4×4 blocks using two different codebooks but the second one is used only for the second line (no known decoder supports that mode);
mode 3—code 4×8 block using a single codebook by coding differences to the even lines and interpolating the odd ones;
mode 4—the same as mode 3 but with two codebooks;
mode 5—very similar to mode 3 but with a possibility to add a correction to the interpolated lines (since it involves writing single bits that no other part of the codec does, no known implementation supports it);
mode 6—like mode 5 but with two codebooks (and equally unsupported by anything known);
mode 7—code 4×4 blocks with bit flags for telling which dyad to code (no known decoder supports this);
mode 8—the same as mode 7 but with two codebooks (of course it’s unsupported);
mode 9—the same as mode 7 but with the second codebook specially for the second line (equally unsupported);
mode 10—code 8×8 block using a single codebook by either duplicating pixels on even lines and interpolating odd lines (for intra) or scaling each delta for 2×2 block (in inter mode);
mode 11—code 4×8 (inter only) block using corrector repeated for each odd line;
mode 12—mode 11 with two codebooks (only VfW version supports it).

Considering the internal implementation details (e.g. using arrays for opcode handling or not), I’d say that QuickTime and XAnim versions of the decoder are based on the same porting kit code supplied by Intel while Video for Windows version uses the different codebase (it’s not just an encoder being present and mode 12 support, it’s also the way how many tables are generated in runtime while they are static in other decoders, not using the opcode tables and other minor things).

But before we start to code cells we need to perform the initial frame splitting and the next post should be about that.

Posted in indeo3encfail, Various Video Codecs | Comments Closed

Starting yet another useless encoder

Thursday, January 26th, 2023

Even before I started to write my series of posts on FFhistory, I had another work in progress already which I’m now making public in order not to chicken out (as I did several times already). I’m talking about Indeo 3 encoder.

Why Indeo 3 of all possible things? It’s both not your conventional DCT-based codec and it’s widespread enough to be of some limited use for me (being present in AVI, MOV and VMD containers, only Cinepak is more ubiquitous). I’m not as good as Mike Melanson but I’m willing to try my hoof at it.

The funny thing is, there’s an opensource decoder for it and even a decent description in US patent 5,386,232 from 1995 (so it’s expired already and anybody can write an encoder for it). The problem is that those two sources don’t match between each other and somewhat disagree with the official binary specification (I’m pretty sure that both Indeo3 decoders were REd from XAnim module). And Ghidra does not like VfW binary (maybe it’ll like the version inside QT6 better) so I can’t easily refer to it either.

Anyway, I attempted and gave up writing an encoder for Indeo 3 several times because of its perceived combinatoric complexity. First you need to split frame recursively into blocks—how to select them? Then you need to select one of the coding modes (again, how?) and codebooks (same question). Trying to think of a reasonable way to implement it all made me shudder and give up until I finally read the format description and persisted enough to write at least something working (side note: I also have the same problem with TrueMotion 1 encoder which I also want to write one day, hopefully it’ll be easier now).

Also I tried to look into the encoder implementation and found it as a bunch of magic numbers at work. I’m not joking, during initialisation it seems to set several dozens of various integers and floats and use them for various coding decisions (at least what I could understand from it is that codebook selection is kinda tied to the internal quantiser parameter which is calculated depending on bitrate/quality—and various magic numbers).

So I want to document how this codec works, what differs in the different descriptions of it and how my encoder decides what to use in different situations. This should amount to another dozen of posts that nobody will read.

Posted in indeo3encfail, NihAV | Comments Closed

Looking again at LSVX

Tuesday, November 29th, 2022

Recently Paul B. Mahol asked me to take a look at LSVX codec (aka Lightning Strike Video Codec from Espre). Since the guy is working on Bink2 decoder for all of us, he deserves some respect. So here’s what I found.

Previously I took a glance on it, found that it’s based on tmndec 3.0, kinda the reference decoder for H.263 and concluded it is an ordinary H.263 rip-off and hadn’t looked further. It turned out to be more interesting though.

LSVX frames start with 5-byte header where the second byte tells the frame type (0x01, 0x08 and 0x09 are for normal frames, 0x05 is from skip frames; additionally if the first two bytes of the header are 0x78 0x01 then the header is followed by another eight bytes, usually with “lsvxv2.0” in them). Then almost normal H.263 stream follows—at least on a prolonged glance it seems to be the standard H.263 stream without any modifications of the headers (except maybe in motion vectors decoding). But there’s a catch! Key frames may have picture type 7 (reserved code in the standard) and then they’re coded with wavelets.

The wavelet coding is rather straightforward: you have a picture split into many bands, each of them is quantised and coded with a semi-adaptive binary coder. By that I mean that it uses models with fixed probabilities but it selects different context for different bits depending on previously decoded bits and in some cases the entier sets of probabilities may be switched mid-decoding. Beside that there are no special tricks like zero tree coding or fancy coefficient prediction.

Maybe I’ll write a decoder for it after all.

Posted in Various Video Codecs | 2 Comments »

Looking at KQ6 Mac videos

Friday, November 25th, 2022

The terrorist country proves that it is recognized as one and keeps targeting civilians instead of fighting a war. So nothing new but it would still be nice to see its demise soon. Meanwhile I keep doing small things to distract myself from all this.

Since I have nothing better to do, I watch reviews of various games including the ones I know well. And one of those reviews mentioned that Macintosh version of King’s Quest VI: Heir Today Gone Tomorrow had peculiar intro. Actually every version of the game has something peculiar about its intro: DOS version uses Sierra’s own RLE-based SEQ format, Windows version uses standard MS Video 1 in AVI (it was my first sample with palette change messages), Amiga version is a reimplementation by Revolution Software on their Virtual Theatre engine altogether (maybe ScummVM will support it one day for all three and a half fans waiting for that). So, what’s with Macintosh version?

First of all, the files are QuickTime movies in the original Macintosh format where frame data is stored in the data fork and movie header is stored inside the resource fork. Since not all modern OSes support such files natively (or conveniently), I’ve hacked a support for such movies in MacBinary format that keeps all forks in one file. And what do we have inside?

Inside the files are video streams packed with Cinepak. One of the peculiarities is that they have palette specified in video header in the format different from the conventional MOV color atom format, let alone the fact it should not be present at all. I understand that for Cinepak and even more for Indeo 3 (I really should write an encoder for it one day) it was common to provide a palette so they rendered their output for 256-colour mode but in that mode Cinepak simply coded palette indices and here we have YUV420 output and a palette as a recommendation.

Then there’s a fun case with tracks in KQ6Movie. I understand that they split video and coded it in several tracks so they could use different palettes (and framerates as it turns out) for different segments. And those tracks are not in order. Tracks 0 and 1 seem to be the very beginning, track 2 corresponds to a scene somewhere in the middle and track 3 is the last intro scene. Other ten tracks are not in order either. Maybe there is some information hidden in the header telling the order but I’m too lazy to find it out (let alone implement).

All in all, this was unexpectedly weird.

Posted in Game Video, Various Video Codecs | 4 Comments »

A quick look at PDQ2

Friday, October 21st, 2022

So there’s this new service discmaster.textfiles.com for searching for files from some old disks and discs at archive.org and out of curiosity I took a look at what it offers.

While it’s physically impossible to check all hundreds of millions of files it indexes (even just videos), I took a look at one rather curious category called aviAudio. There are about six hundred files of such type found so I decided to check them to see what kind of beast that is.

Some files turned out to exactly AVI audio files—AVI files with single stream that turns out to be audio (I don’t know why but this happens). The rest of the files were AVIs with unrecognized video track (just what I was hoping for!). One set of the samples come from some game with IPMA codec, other sources mostly feature Motion Pixels video (which is horrible both to RE and to support so I’d rather not touch it), one sample was special “codec” for some russian erotic game (which means complete garbage even by russian game standards) that is really just obfuscated Indeo 5. And finally there was a single PDQ2 sample (from some Incredible Hulk game demo from 1997).

An interesting thing is that it’s a DOS game with built-in AVI demuxing and decoding of this codec. The codec turned out to be a lot like various lossless codecs (so its FOURCC probably stands for something like “pretty damn quick codec, version 2”). It splits video into 4×4 tiles and emits up to three streams stored one after another: tile opcode (copy previous tile, copy previous data with an arbitrary offset, skip tile, raw tile), variable offsets and tile pixels. Additionally frame data may be packed further with LZ77-based scheme. As I said, a rather familiar scheme for lossless video codecs and it makes me wonder whether it’s a codec developed specifically for the game(s) or it was borrowed from somewhere else.

Posted in Game Video, Various Video Codecs | Comments Closed

Looking at true IVF

Thursday, October 13th, 2022

So while russia demonstrates once again what a hysterical führer and his similarly minded generals would do, I’m trying to do something to distract myself from the thoughts about the losses Ukraine suffered in last couple of days (and previous couple hundreds of days too).

Accidentally I’ve managed to find a sample in IVF format—the original streaming format for Indeo codecs. Despite the expectations it was not a renamed AVI file which made it even more interesting. So I took Ghidra and binary specification and started implementing it.

The format by itself is rather simple and the only interesting thing is that it transmits video data in passes: first it’s just bare minimum keyframes and all other frames as drop frames, then some inter frames are sent, then more data is sent and more. Unfortunately there’s no obvious field to tell where each part starts so I simply assemble frames in memory (which is not effective but still better than the original creating temporary files for assembling fragments).

Then there was a problem with decoding them: my existing decoder expected a frame with sequential structure while in this case fragments are transmitted out of order. Normally you’d get all four bands for luma plane and then a band for each chroma planes but in this case it may be one or two bands for luma plane, then chroma plane bands, then some zero padding and then the rest of the bands for luma (if they were transmitted at all). In the reference implementation the demuxer seems to parse and re-assemble the frame while I ended up writing a slightly different decoder for this scalable mode. It seems to work fine so now NihAV support for Indeo family of formats is even more complete than ever.

P.S. The Wiki had only the entry for Duck test samples format (that has the same extension) so somebody had to correct that. Which also makes me think about things like Duck AVC, AVS being an FMV game format or Chinese non-Duck AVC rip-off, IEEE AAC and so on. This confusion deserves to be written about but don’t expect me to do that.

Posted in Various Video Codecs | 3 Comments »

German PEGs

Thursday, September 29th, 2022

Having said everything I could on the current political situation, I returned to looking at random codecs and I found one with a curious name.

The name is DPEG and it’s used in at least one random game I’ve never heard of. It turned out to be a rather simple tile-based codec with raw intra frames and inter frames that employ RLE and motion compensation.

So nothing interesting but then it struck me: wait a bit, I remember REing a codec with almost the same name, block-based RLE coding approach and also from a German company (a different one though).

And there’s this Fraunhofer society involved in MPEG Video and MPEG Audio (different branches though)…

So what’s the German fascination with naming codecs [A-Z]PEG and how many out of 22 possible codecs are really implemented?

Posted in Game Video, Useless Rants, Various Video Codecs | 4 Comments »

A Quick Look at AVS3

Monday, August 15th, 2022

The war has shifted to a terrorist operation against Ukrainian civilians (with no change for my home city, it gets several strikes from russian territory every day regardless) and instead of threatening the world with nuclear war russia threatens the world with nuclear terrorism using the captured Ukrainian nuclear power plant. So here’s yet another attempt to distract myself from thoughts about it.

It seems that AVS3 has been standardised already (and nobody cares). So out of idle curiosity I’ve downloaded the spec from avs.org.cn (in Chinese of course, and it requires you to fill some information but accepted any garbage). So let’s look at this completely original format that has not borrowed anything neither from H.266 nor from AV1.
(more…)

Posted in Various Video Codecs | 4 Comments »

Kostya's Boring Codec World