I’ve wasted enough time on AVC decoder for On2 family so while it’s not working properly for those special cases I’m moving to VP7 regardless.

For those who don’t know (or forgot; or never had a reason to care) On2 AAC is AAC-LC rip-off with some creative reconstruction modes added to the usual long/short windows. I’ve failed to understand how it works before and I fail to understand how it works still. But at least some details are a bit clearer now that I’ve analysed the whole codec from scratch with less guesswork.

The codec has three IDs that it recognizes: 0x500, 0x501 and 0x1234. First two are different only in the aspect that one handles singular packets and another one handles several packets glued together prefixed with size. The last ID is simply recognized but it does not have any special handling.

The tricky part is some special modes that do some heavy processing of data. For most modes you invoke IMDCT and that’s all, here you do some QMF-like filtering (probably for transients extraction), then you perform RDFT (previously I thought it was plain FFT but after long investigation it turned out to be RDFT after all) on quarters, merge those quarters using filters that look like convolution filters for four sub-bands, perform RDFT again on the whole block and add some transients. And after that you still may need to reverse the data before using permuted window for overlap-add operation. In other words it’s not fun and I lack education for recognizing all those algorithms used, why they’re used and where it goes wrong.

So hopefully I’ll return to it some day to fix it for good but now VP7 awaits (so I can at least formally declare Duck codecs family done and move to implementing missing bits in the framework itself).

When I think I’ve learned enough about Dingo Pictures there’s something new appears. From Toys review I’ve learned that Roswitha Haas also published a book (or maybe several) that are directly related to the subject at hoof. And of course being curious I’ve decided to buy it.

Amazon mentions two other books—an adaptation of Land Before Time and Jimmy Button but I dared not to buy them (one has definitely nothing to do with Dingo Pictures and I fear to find out that the first one is not about Tio).

Anyway, let’s look at the alternative version of King of the Animals Part 2 (spoiler: it’s still much better than Disney remake).

First let’s mention some technical technical details: this book was released by Unipart in 1999, the same year as King of the Animals Part 2 but it had completely different artists (from Bayreuth even, while the publisher is located in Hessen not far from Dingo studio) with a bit different style as well. The same publisher printed children book adaptations of Disney stories too. But who cares about that, let’s look at the pictures!

If you wonder who is that magnificent warthog crocodile on the cover, that’s Dundee. If you wonder why he does not look like himself in the movie it’s because for some reason they’ve decided to cast warthog Bobo as Kemo’s friend (no idea why, artistic license?).

The story is still largely the same: there’s this king of the animals (aka lion), he has a son Kemo, there’s that black panther with his own son Pino and minions.

And there are diamonds. My God!

Pity they could not have a climactic fight here but here’s the best shot at it:

The ending is significantly different from the movie though and I’m not going to spoil it.

Overall, this was an interesting experience and while I’m not going to research it further I still hope more books might re-appear in the future.

While it’s summer and I’d rather travel around (or suffer from heat when I can’t), there has been some progress on NihAV. Now I can decode VP5 and VP6 files. Reconstruction still sucks because it takes a lot of effort to make perfect reconstruction and I’m too lazy to do that when simple demonstration that the decoder works would suffice.

Anyway, now I can decode both VP5 and VP6 files including interlaced ones. Interlacing in VP5/6 is done in very simple way like many other codecs: there’s a bit for each macroblock telling whether macroblock should be output in interlaced form or not.

Of course this being VPx family, they had to do it with some creativity. First you decode base interlaced bit probability, which is stored as 8-bit value while all other bit probabilities are stored in 7 bits. Then you derive actual probability for interlaced bit and decode it before any other macroblock information (including macroblock type—it’s that important). Probability is derived by companding base probability depending on whether last macroblock was interlaced (then probability is halved) or not (then it’s remapped to fit 128-255 range)—except for the first macroblock in a row which would use the base probability without modifications. And for VP6 you also have to use different starting scan order (band assignment for each coefficient, now it’s shuffled). This is so trivial that one would wonder why this has not been done in libavcodec decoder yet.

There are three possible things to do next: polish current implementation, move to AVC (On2 AVC that is) or move to AVC (Duck VP7 which is AVC ripoff). But probably I’ll simply keep doing nothing instead.

… gibt’s gar viele Haltstatione,
Kowelenz, Bingen, Bad Kreuznach, Lautre und Waldfischbach.

Ehm, sorry, wrong federal land for that song.

I think I can call my hobby project of travelling on all rail lines in Rheinland-Pfalz that are still in service complete.

Well, actually there are two tracks that I have not visited: couple of kilometres (about three) north from Unkel to the land border (when I went there the trains were going just to Unkel because of road works and I see no point of revisiting it again) and Zellertalbahn (Monsheim-Münchweiler, that one has been closed for at least this and last year and I’m not sure it will open next year—if it does I’ll go there); same for draisine-only tracks—I’m not a cyclist. Anyway, let’s start with the overview of Palatinate railway network.

Rheinland-Pfalz is divided into two parts by the river so the rail network looks like two nets connected in several points (essentially near Koblenz and somewhat Mainz). There is one and a half high-speed train lines (one going from Frankfurt Airport to Airport Köln/Bonn and something going from Mannheim via Kaiserslautern to Saarbrücken and Paris but it’s definitely not a high speed line). The right bank network consists essentially of a railway along the Rhine and several lines that connect neighbouring federal lands (Hessen and Nordrhein-Westfallen) including the high-speed one. The left bank network has several lines that form a very good connectivity: railways on the Rhine side go all way from Lauterbourg to Ludwigshafen to Mainz to Koblenz to Bonn, there’s an East-West line connecting Mannheim to Saarbrücken via Neustadt and Kaiserslautern, there’s another East-West line connecting Koblenz to Trier and Luxembourg, there’s yet another line connecting Mainz to Idar-Oberstein and Saarbrücken, there’s West border line going from Saarbrücken to Trier and Bonn, there’s North-South line going from Bingen to Kaiserslautern and Pirmasens (consisting of several railways actually), there’s a line Worms-Bingen, there are some lines connecting Karlsruhe and Wörth to Neustadt, Pirmasens and Saarbrücken, and there are still more. There are some local lines that branch from those and have a terminus in some small place you’ve never heard of. And there are some museum lines as well. Here is the official map from Deutsche Bahn for regional lines operated on regular basis (so no high-speed or museum lines there). As for special lines I can name semi-museum line from Linz (not on Danube) to Kalenborn, museum lines Kuckucksbähnel (from Neustadt to Elmstein), Brohltalbahn (Brohl-Engeln, it has the slowest express I’ve ever seen) and narrow-gauge museum Stumpfwaldbahn (which kinda duplicates Ramsen-Eiswoog part of regular line).

My tickets from museum lines (maybe I should start collecting them).

It would take too long to describe all of the lines so I’ll just talk about some peculiarities. First of all, it’s scenic and you have a lot of scenery kinds to choose from: there is the largest forest in Germany, there are nice mountains with different geology, there’s Middle Rhine with castles at every mountain, there are fields and even former volcanic area.

Second, Rheinland-Pfalz probably has more abandoned and dismantled railways than those in service. Just look at the list in German Wickedpedia—it looks like most current branches were part of longer railways that were closed later and many branches are remains of much longer railways.

Third, Rheinland-Pfalz is weird. Southern part of it is quite French to the point that you can see both TER and TGV trains there and stops are sometimes announced in French too. But in the very Eastern part of Rheinland-Pfalz you have Girod and in Northern part there’s Monreal. In Eifel. Why not have normal German names like Vogelweh, Geilhausen or Waldfischbach? And there’s weird RB90 route (Limburg an der Lahn—Siegen) that usually does not go all the way so you have to transfer in Westerburg from RB90 to RB90. But the real something is track numbering on the stations. I’m not talking about train arriving to “Gleis Ost” which is the only track here, I’m talking about numbers. Normally you number your tracks from one and sequentially above, maybe reserving ten-something or hundred-something for some auxiliary tracks but that’s not enough for Rheinland-Pfalz and Saarland. Few examples: on route Saarbrücken-Lebach Merchweiler has tracks 20 and 30, Gennweiler has tracks 40 and 50 while Illingen has tracks 41 and 51; Betzdorf has tracks 101-106 and 112 and neighbouring stations have tracks 40x (on two different stations), 50x and 60x.

And finally some words about special railways there:

• Linz-Kalenborn is a private railway that is (as usual) a remaining part of a longer line that connected Linz with a line to Altenkirchen (and that’s a popular place to dismantle tracks—track Siershahn-Altenkirchen is for freight traffic only, track Siershahn-Engers is not in use even for museum rides, track Bendorf-Siershahn is both). They have rail bus operating there regularly on weekends and holidays. The most important thing for somebody is that they have a stop at the local brewery.
• Kuckucksbähnel is a museum line that runs not so often but it’s a steam train and nice forest. Definitely worth a ride;
• Stumpfwaldbahn is a narrow-gauge railway that runs about every hour between Eiswoog and Ramsen, usually with diesel locomotive but sometimes they have steam train. It’s nice but nothing special considering scenery;
• Brohltalbahn is operated one to three times a day at weekend and on holidays, usually with a pair of diesel locomotives but sometimes they have steam train as well. It’s remarkable for two things: going to Vulkanpark Brohltal (the area of former volcanic activity) and having the slowest express train (Vulkan Express as they call it covers ~17km in one and a half hours). Still worth checking out;
• There was a special rail bus going from Karlsruhe via Landau to Dahn and Bundenthal-Rumsbach but looks like it’s handled by Deutsche Bahn now.

There is a lot that can be told about Rheinland-Pfalz and its railways but I hope that this short review gave you at least an idea of what to expect there.

Recently I’ve been contacted by some guy working on a mod campaign for Heroes of Might and Magic III. The question was about the encoder for videos there. And since the original one is not likely to exist, I just wrote a simple one that would take PGMYUV image sequence and encode it. Here’s the gzipped source.

It took a couple of evenings to do that mostly because I still have weak symptoms of creeping perfectionism (thankfully it’s treated with my laziness). BIKb does not have Huffman-coded bundles, so the simplest straightforward encoding would be: write block type bundle (13-bit size and 4-bit elements), write empty other bundles, write several bundles containing pixels and you’re done. There’s a proper approach: write a full-featured encoder that takes input in several formats and that encodes using all possible features selecting the best quality for the target bitrate. There’s a hacky approach—translate later versions of Bink into BIKb (and then you remember that it has different motion compensation scheme so this approach won’t work). I’ve chosen something simple yet with some effectiveness: write an encoder that employs only vector quantisation and motion compensation for non-overlapped blocks plus add a quality setting so users can play with output size/quality if they really need it.

So how does the block encoding work? Block truncation coding, the fast and good way to quantise block into two colours (many video codecs back in the day used it and only some dared to use vector quantisation for more than two different values per block). Essentially you just calculate average pixel value and select two values depending on how many pixels in the block are larger than average and by how much they deviate. And here’s where quality parameter comes into play: depending on it encoder sets the threshold above which block is coded as is (aka full mode) instead as two colours and pattern in which they occur (of course if it’s a solid-colour fill it’s always coded as such). As I said, it’s simple but quite effective. Motion compensation is currently lossless i.e. encoder will try to find only the block that matches exactly (again, it can be improved but that would only lead to longer implementation times and even longer debugging times). This makes me appreciate the work on Smacker and Bink 1 video codecs and encoders for them even more.

Overall, it was a nice diversion from implementing Duck decoders for NihAV but I should probably return to it. The sooner it’s done the sooner I can move to something more exciting like finally experimenting with vector quantisation, or trying to write a player, or something else entirely. I avoid making plans but there are many possibilities at hoof so I just need to pick one.

Dedicated to Peter Ross, who wrote an opensource VP4 decoder (that is not committed to CEmpeg yet at the time of the writing).

The codecs from VP3 to VP6 form a single codec family that is united not merely by the design but even by the header—every frame in this codec (sub)family has the same header format. And the leaked VP6 format specification still calls the version field there Vp3VersionNo (versions 0-2 used by VP3, 3 is used by VP4, 5 is for VP5 and 6-8 is for VP6). VP7 changed the both the coding principles to mimic H.264 and the header format too. And you can call it the golden age for Duck because it’s when it gained popularity with VP3 donated to open-source community (and xiphed to Theora which was the only patent-free(ish) opensource video codec with decent performance back then) to its greatest success found in VP6, employed both in games and in Flash video (remember when BaidUTube still used .flv with VP6 and N*llyMos*r ADPCM or Speex?). And today, having gathered enough material, I want to give an overview of these codecs. Oh, and NihAV can decode VP30 and VP31 now.

VP3

It is hard to say how this codec was designed but looks like it was mostly good for network transmission with the risk of packet loss (but then why it does not have CRCs?) and for doing stuff not like other codecs do.

Overall format can be described as being very weird variation on progressive JPEG. Image (all three planes) is represented as a sequence of 32×32 pixel super-blocks (part of super-block outside plane boundaries is not coded), each of them contains 4×4 macroblocks, each of those contains usual 8×8 blocks. The block metadata (coding type and motion vectors) are coded as single chunks of data for all blocks before coefficients. Coefficients are also coded in sequence: DCs for all blocks first, then 1st AC for all blocks (where present), then 2nd AC … up to the 63rd AC. There are two kinds of frames—intra and inter. Inter-frames can use either previous frame or last intra frame (called golden frame) as the reference (VP6 finally allowed any inter-frame to become new golden frame but let’s talk about it later).

As you can see, it’s robust against truncated frames but I cannot imagine such scenario being important for the codec not used in video calls (and that was VP7—way later than VP3). Also that new block ordering required a new way to walk them so there are no jumps between last block in current super-block and first block in next super-block. Hence the Hilbert curve suitable for macroblocks and blocks alike.

IMO codec was designed not for efficiency but rather for being sufficiently different from the rest. And while I don’t like the result, I must admit that at least it’s quite original in some parts and I appreciate the variety.

Anyway, beside golden frames, peculiar block walk pattern and data partitioning the other notable thing is block coefficients coding. While the method remains the same (you need to code sparse array essentially), instead of using the standard run-length codebook VP3 uses semi-fixed scheme with entries grouped in categories (fixed number of end-of-block flags, longer amount of EOB flags, fixed coefficient, small coefficient in fixed range, zero run of one plus small coefficient and such). In result you need to read one of 32 possible tokens using one of several codebooks and then unpack token by following the fixed scheme. For the reference, H.263 coefficients codebook contains over hundred entries (and still need escape values handling).

Now let’s review VP3 flavours.

VP30 is obviously the zeroth version (it does not even have a version in the header and stores dimensions in macroblocks there instead). Block coded flags are coded hierarchically: first there are a bit-run coded flags for super-blocks whether they contain coded macroblocks, then for all non-empty super-blocks there are bit-run coded flags for macroblock that contain coded blocks, and finally there are bit-run coded flags for blocks in coded macroblocks (obviously in intra frames all block are coded and are of intra type so such metadata is not present).

After that you have macroblock types (just for coded macroblocks of course) which is read with a fixed codebook. There are seven macroblock types: intra, skip, copy with MV, copy using motion vector from last inter block, four MVs per macroblock, copy from golden frame from the same position, copy from golden frame using MV. The WTFiest moment for me is that uncoded intra block in VP3 (which may happen only in inter frame) actually means skipped block.

After that you have motion vector information for the macroblocks that require it using fixed coding scheme for motion vector components. As you can see above, the only kind of MV prediction is re-using motion vector from last inter block with coded MV (VP5 will improve this).

Coefficients are coded using three codebooks (one for DCs, one for intra block ACs and one for inter block ACs) with codebook set selected from one of five possible depending on quantiser. DC prediction is simple: just add last DC from the block of the same type (intra for intra, any inter for inter block). Also it has been using bit-exact DCT that remained until VP7 decided to switch to H.264-like transforms.

Loop filter seems to be the same and survives even in VP8 (under the name of simple loop filter) but it’s not used on output picture since VP4…

Fun fact: VP30 decoder was written in C++ and binary VP31 (and maybe even VP4) decoder still contains it along with C code for decoding VP31.

And as I’ve mentioned in the beginning, NihAV can decode it now while libavcodec/vp3.c still can’t.

VP31 is a small improvement on the above and it’s the version people know the most (if you include Theora based on it). Block coding information is now coded in following layers: first it codes information for partially-coded super-blocks, then it classifies the rest into fully coded/uncoded super-blocks and finally it signals which blocks in partially coded super-blocks are actually coded.

Macroblock types are coded using either raw indices or unary coding plus one of the predefined sets of values (or a custom one).

Motion vectors now can be decoded using fixed coding scheme (slightly different one) or raw 5-bit value plus sign (even for zeroes). Also now there’s an inter block type that uses second last MV.

Coefficients are now coded using a set of five codebooks (DC, ACs 1-5, ACs 6-14, ACs 15-27 and ACs 28-63) for luma and for chroma. Codebooks are selected from a set of sixteen using two indices read from bitstream for DCs and (after DCs are decoded) two indices read from bitstream for ACs. DC prediction is now complex and uses weighted DCs from neighbours depending which of them of the same kind are available (intra, last frame reference or golden frame reference).

And there is an elusive VP33 (aka VP3 version 2) which has some leftover code in the VP31 opensource dump including the tables and block coded flags.

While most of the code is the same there are two main changes: block coded flags is completely different now and there’s now a completely new set of tables. Block coded flags are decoded on macroblock basis: first you decode flags denoting fully coded macroblocks, then you decode flags for partially coded macroblocks and finally you decode coded block pattern using previously decoded block pattern and 3-5 bits of data. The rest goes exactly as VP31.

Either this was an experimental codec or simply a leftover they forgot to remove but while binary VP3 decoder supports it, there’s nothing known about any samples or means to encode them. Call it Bink-d of VP codecs.

VP4

Now enters VP4. Essentially it’s VP33 with some tweaks and some changes in frame reconstruction. The main differences are motion vector coding scheme (it’s more complex now) and the fact that loop filter is not applied to the decoded frame but used on motion block source instead (i.e. it copies block from source frame to the temporary buffer and if it contains edge pixels then it applies loop filter on it). The same scheme was employed in VP5 and VP6 as well. Also now it stores table indices before all coefficients (instead of DC luma table index, DC chroma table index, all DCs, AC luma tables index, AC chroma tables index, AC1, AC2, …) and has some more information in the frame header but that’s all I can think of. Also DC prediction has been changed once again (seems to be simply an average of neighbouring DCs from the same kind blocks).

The only fun facts about it is that some of its code is already present in opensource VP31 dump (being mostly VP33) and that binary VP4 decoder contains code and tables for bilinear and bicubic motion interpolation employed in VP5/6. I’m yet to look at VP5 and VP6 binary specifications so I don’t know whether they contain hints on VP7 but that seems unlikely.

VP5

This is a codec that radically changed two things: data is now coded using their bool coder (a variant of arithmetic coder for coding bits that uses fixed probabilities instead of an adaptive model) that is used to decode bits for values and codes in fixed Huffman trees (also that means that now there are twelve DCT token categories instead of 32 like before). This scheme will survive until VP9 and has some chances to reappear in AV2 (just a guess—we know who develops it and nothing else beside that fact).

In result the codec could return to having ordinary 16×16 macroblocks without super-blocks (and code blocks instead of coefficient slice). Also now motion vector prediction relies on using so-called nearest and near MVs that come from neighbour blocks visited in certain order.

The only major drawback I can name is that now inter frames may rely on previous ones since they can transmit probability updates and thus dropped frame will result in complete garbage instead of damaged frame converging back to normal image.

VP6

And now VP5 can be tweaked for performance. So the notable changes include: signalling that this inter frame is a new golden frame and new data coding and partitioning modes. Now if you want to have lower latency you can split your data into two parts and start decoding coefficients as soon as you decode corresponding macroblock information. Or if you really care about speed you can switch to old way of coding by constructing Huffman trees from model probabilities and having special handling for zero/EOB runs. Also now there’s an interlaced mode and alpha support. No wonder the codec was popular on the Web until H.264 came to power.

From VP30 to VP6.2 it was a steady evolution of the codec (beside brief return from bool coding for Huffman trees in VP6) with most concepts remaining the same and the biggest changes being between VP4 and VP5—new bool coder, qpel MC and switch from super-blocks to ordinary macroblocks (and new MV prediction scheme to some extent). But other things like data partitioning, DCT tokens, DCT itself and loop filter remained the same. The same way VP6 into VP7 change will involve changing of coding blocks into 4×4 ones, new transforms and spatial prediction, but many other things like bool coder or MC interpolation still remain there.

Maybe I’ll revisit it later if I ever get to VP7 decoder but for now this should give you an idea how Duck codecs changed over the time and why it ended like that (maybe one day somebody will manage to answer a question “Why platypus? Just why?”). Meanwhile I’m looking sideways for AV2 aka VP11 and its possible collision course with H.266 aka VVC.

As I’ve mentioned in the previous post, I’ve finally tried rust-clippy to see what issues and suggestions it will have on my code. The results are not disappointing if you take the tool name seriously.

The output (at least in my case) can be divided into four categories: actual bugs spotted, useful suggestions, (mostly) useless suggestions and counterproductive suggestions.

Let’s start with actual bugs spotted. It spotted two cases when condition has identical code in both branches. So I had to remove such useless condition in one case and fix the data source taken in another. Also an error on casting pointer to several-byte buffer as pointer to integer. Depending on stack alignment and CPU architecture this may result in a buggy load so better fix it (but then this issue will be mentioned again when we get to the third category).

Useful suggestions were much more plentiful. I started developing NihAV in Rust a bit more than two years ago and the language has changed quite a bit since then so some parts of code were a bit outdated (e.g. nowadays you can simply write Struct { field1, field2 } if you initialise it from field1 and field2 variables and have the same fields; previously you had to write Struct { field1: field1, field2: field2 }). Plus of course there are features I did not know about either because they were introduced later or I simply did not think about it being possible. Here are some examples I encountered:

• you can use vec![elem; size] to create vector of fixed size filled with element (previously I invoked Vec::with_capacity() and then vec.resize() which is more error-prone);
• now you can write ranges as start..=end instead of start..end+1 (IIRC this was still an unstable feature when I learned about it so no wonder I forgot about it);
• println!() is equivalent to println!("") (and guess who uses it for debugging);
• now instead of old way to increment pointer ptr.offset(size as isize) you can simply write ptr.add(size);
• there’s slice.swap(idx1, idx2) for the cases when you need to swap two values in an array;
• it also recognizes some standard constants and suggests to use those instead;
• it spotted useless casts too (e.g. when I cast u32 to u32);
• passing the reference to Vec when passing the reference to slice would work as good (and even save some MiNicycles on access); same for borrowing Box.

There were some stylistic suggestions that I found good (replacing some indexed loops with loops on iterators and copying slice with a call instead of loop) but mostly they belong to the next category, useless suggestions.

Yes, that’s where rust-clippy starts to live up to its name. Most of its suggestions were in the format “hey, you’re trying to use clear imperative programming to do the work that can be expressed with iterators in 10x text”. I understand that it’s more to the Rust style and it helps to prevent errors in some cases, but when it suggests to replace simple loop like for i in 3..7 { dst[i] = src[3 - i]; } with something that won’t fit onto single like I say it’s too much. Or how it suggested to change simple mem::transmute::<&mut $inttype, &mut [u8; $size]>(&mut buf) into &mut *(&mut buf as *mut $inttype as *mut [u8; $size]) (sure, it does the same but I find the former easier to comprehend).

Similar story with X as u32 versus u32::from(X). I understand it helps catching the cases where X changes type and cannot be converted to destination type losslessly any more. But it breaks formatting and makes it unnatural (and close to C++) in the sense that previously the code was read like “calculate X and cast it to type” and now it’s “convert to type from calculated X”. And by breaking formatting I mean that I have a lot of code in form

    let a = br.read(4)? as usize;
    let b = br.read(6)?;
    let c = br.read_bool()?;
    let d = br.read(3)? as u64;

and by using u64::from(br.read(3)?) I’d break nice tabular form for no obvious merit.
di
Another cases is when rust-clippy suggests refactoring conditions. When I write

    if is_intra {
        if block.coded { do a }
        else { do b }
    } else {
        if block.coded { do c }
        else { do d }
    }

I format it this way because it reflects the logic of the code and I do not want to make it into } else if block.coded { do c } else { do d }. Similarly if I don’t join let a; if foo { do stuff; a = val; } else { a = val2; } into single let a = if foo { ... val } else { val2 }; it’s because I have enough code in that condition that I don’t want to indent it even further (sure, make fun of me because I worked in text mode and still don’t like lines longer than 80-100 characters).

There’s more like “you should implement Default trait for each structure with new() method” and “you should write constants like 0x00_0001” and “enums should not have different prefix in the name, you should consider removing Mode from Mode16k, Mode5_5k and Mode8k” but let’s move to counterproductive suggestions already.

First issue is that rust-clippy interacts with macros quite poorly. For example I have a macros that expands 4-byte array into 32-bit tag and it suggests using u32::from(arr[0]) instead of (arr[0] as u32) but if you do that it will have an error instead of warning because it can’t check types in macro. Also here’s one of the WTFiest examples: I have a macro for filter implementation that takes coefficients as arguments and calculates the value. It has a code -$c1 * $src[$off + 1] and when $c1=-1 you have a warning “about –x is double negation”. Actually I remember that example from Feuer’s C. Puzzle Book. where #define NEG(x) -x NEG(-x) expanded to –x (and thus I put all macro arguments into parentheses) but I expected Rust to handle that correctly (otherwise this WTF goes to linter). In either case -(-1) is what I meant in that case and that’s how it works.

And now the most infuriating example that the tool treats like a warning or an error depending on situation.

As I write video decoders, I have a need to apply a filter or transform on some data. And IMO this form:

    dst[off - 2 * step] = a;
    dst[off - 1 * step] = b;
    dst[off + 0 * step] = c;
    dst[off + 1 * step] = d;

I think this conveys the meaning and looks much better than

    dst[off - 2 * step] = a;
    dst[off - step] = b
    dst[off] = c;
    dst[off + step] = d;

with whatever spaces you insert there (and it’s not possible to use iterators here quite often too). But rust-clippy treats that as a warning if you’re multiplying by one, adding zero or constant multiplied by zero and gives outright error on variable multiplied by zero or an expression like N - N (which happens when you have constant base and one of the offsets equal to it).

So my experience with this linter was mostly negative—all those neat things were out-weighted by the sheer amount of useless warnings (and I don’t like to add dozens of #[allow(clippy::useless_warning)] to lib.rs for many modules) and some stuff that would simply break code clarity for no obvious benefit. Overall, it’s a nice tool and though I got something useful from it, it may be a beginner in the language aka ordinary M$ Office user who would benefit the most from it and it will mostly hinder people writing advanced code unless you turn off a lot of warnings and even some errors.

Since the clean-up work on NihAV is done and I progress with Truemotion VP3 decoder, it’s a good time to talk about what I’ve actually done—there’s even more material to write waiting in the queue.

The intent was to make all frame-related stuff thread-safe and improve efficiency a bit. In order to do the former I had to replace most of the references from Rc<RefCell<T>> to Arc<T> and while doing it I introduced aliases like type NAFrameRef = Arc<NAFrame> and .into_ref() methods to convert object into ref-counted version. This helped when I tried switching from one implementation of reference counter to another and will make it easy to switch again if I ever need that (hopefully not). Now about improved efficiency and how it’s related to the ref-counting.

There’s a straightforward way of dealing with frames: you allocate the picture, fill it, dispose, allocate a new one, etc etc. And there’s a more effective way: you allocate several pictures at once, select an unused one, fill, return to the pool when it’s not needed any more. That is where reference counting comes into play and where Rust default structures don’t help. Frame pool owns the reference and decoder gets a second copy. And Rust Arc is intended for single ownership: when you try to access the shared object it will simply clone it so you end up working with a copy (which defies the purpose). So I had to NIH my own NABufferRef<T> which keeps reference counts and still allows shared access even for writing (currently it does that in all cases but if I need to add some guards the API won’t have to be changed for that). The implementation is very simple: the structure contains a raw pointer to a structure that contains actual object and AtomicUsize counter. The whole implementation is ~2.2kB relying just on std crate.

And finally I’ve made a picture pool. The difference between picture and frame is all additional metadata picture should not care about (like timestamps, stream information and such). Because of the design decisions I have three different picture formats (implemented for 8-, 16- and 32-bit element sizes, Rust does not like aliasing after all), which means I need to provide decoder with all three picture pools because we can’t say in advance which one codec will use (if at all—the option to allocate new non-pooled pictures is still there). Also I want to keep those pools external in case the code around it wants to do keep more pictures in it (e.g. 2-3 pictures required by decoder and 25 pictures pre-buffered for the display). This resulted in a structure called NADecoderSupport that contains picture pools and may have something else added late. Of course people might argue that it’s much better to have AVCodecContext with a myriad of fields you can set directly or via utility functions but I’d rather not have one single structure. Though it might be a good place to put various decoder options there (so that decoder can ignore them at its leisure).

Since I said I did it to increase efficiency I should probably give some numbers too: RealVideo 3/4/6 decoders now use buffer pool (for three frames obviously) and reallocate it on format change. Decoding time got reduced by 4-5% from using the pool. Currently I don’t care about speed much but I may convert more decoders to it if the need arises.

In conclusion I want to say that even I did not enjoy doing that work much, it was needed and gave me some experience plus some improvements in code and design. So it was not a wasted effort.

P.S. I also installed rust-clippy since it’s in stable now and tried to fix errors and warnings it reported. But that is a story for another post.

Today I want to talk about local dynasty that was rather short-lived but left quite an impressive legacy.

So, about a thousand years ago in the South-Westernmost corner of Germany there was a noble lord by the name of Berthold who started a dynasty of Zähringen and his eldest son founded the line of margraves of Baden. And while the dynasty of Zähringen has only six rulers (Berthold, Berthold, Berthold, Konrad, Berthold and Berthold) it’s known for building and rebuilding a dozen of towns (yes, exactly twelve), some of which are important even to this day. Since I have nothing better to do at the weekends I decided to visit them all.

Berthold I founded Weilheim an der Teck, the only Zähringer town founded in Württemberg.

Berthold II is known for founding the Abbey of St. Peter (and a town forming near it), Freiburg (in Breisgau of course) and reforming a Swiss company Rheinfelden AG (though Swiss claim that AG stands for canton Aargau and not joint-stock company).

Berthold III and Konrad I somehow evaded the traditional duty and built nothing. Though Freiburg still honours Berthold III for developing Freiburg into proper city and not a mere settlement by the castle.

Berthold IV, son of Konrad I, decided to follow the suit of his grandfather and founded Freiburg (this time in Üechtland). He also rebuilt Murten, founded Burgdorf and Neuenburg (in Baden, don’t confuse it with Neuchâtel).

Berthold V probably remembered that his ancestors were margraves of Dietrichsbern (or Verona as locals call it) and decided to found his own Bern (in Üechtland). He also rebuilt and developed Thun (the castle he built there is still one the best places there), Bräunlingen and Villingen.

Since Berthold V had no offspring, the lands of duchy of Zähringen went to different other noble houses (including dukes of Fürstenberg who are famous for building a lot of castles in Czechia) and ended in hands of Swiss house of Habsburg (who, obviously, are famous for ruling Austria). Thus one can see former Austrian towns even on Rhine.

Fun fact: some of those places have suspiciously similar coats of arms (all images are from Wickedpedia).

Bern:
Neuenburg:
Karlsruhe:

Would you believe it has nothing to do with heraldic colours of Zähringen being red and yellow (also adopted by margraves of Baden, one of which founded Karlsruhe)?

Now, about the towns and my impressions on them.

• Weilheim an der Teck — as mentioned above, the only town not in Baden or Switzerland. Also one of two towns not having rail connection. It’s a nice place to visit nevertheless.
• St. Peter — a small town in Schwarzwald that grew around the abbey that gave it the name. The other town with no rail connection. Very picturesque. The abbey serves as final place for remains of many Zähringen.
• Freiburg — probably the best developed city of them all. It has university, industry, wonderful historical city centre, picturesque scenery around (still not good as St. Peter though). And it’s also officially the sunniest place in Germany. Definitive must see.
• Rheinfelden — a small Swiss company town on Rhine known for one of the oldest bridges over the Rhine and local brewery. A nice place to visit and you can go to German Rheinfelden on the other bank too (a lot like Laufenburg which is located nearby).
• Freiburg (i. Üe.) — a lot like Freiburg Senior but since it’s located essentially in Swiss Saarland it could not develop as much. But it’s claimed to have the most old houses in Switzerland so if you like old architecture then you should definitely visit it.
• Murten — a small but nice town near Lake Murten and not that far from Freiburg Jr. and Bern. Very impressive town walls that you can visit.
• Burgdorf — a small town near Bern with a castle and some historic buildings. Nice place overall.
• Neuenburg (am Rhein) — this one is a bit sad place. The plaque on one house tells that it was completely devastated in 1940 and it was built anew, there is almost nothing historic left there. Nevertheless it has a lot of flowers, sculptures (not as much as in Oslo thankfully) and fountains. So while it looks nice it’s sad when you know the history of this place is gone.
• Bern — de facto Swiss capital. Visit it if you can.
• Thun — a Swiss town a bit to the South from Bern. Nice historic buildings near the river but the Zähringen castle is still the best feature.
• Villingen — a very nice town in Schwarzwald. Definitely worth visiting.
• Bräunlingen — like smaller Villingen.

Another interesting thing is how much the founders are honoured in all those places. Most of them have Zähringerstraße or Zähringerplatz (and Zürich has both despite Berthold IV being just a vogt there). There are exceptions though: Freiburg in Breisgau has Zähringerstraße in a suburb called Zähringen and actual city has Bertoldstraße instead; Weilheim simply mentions that it’s one of Zähringerstädte and has their coat of arms near the church; Freiburg im Üechtland has its main bridge named after Zähringen; Thun and Murten do not seem to have any mentions. While many other places in Baden have Zähringerstraße (like Karlsruhe or Heidelberg) probably because of the relation to the house of Baden, I think they deserve recognition for building new towns. It’s a pity there were not so many nobles like them.

Since obviously I have nothing better to do, here’s a description of loop filter in Bink2 as much as I understand it (i.e. not much really).

First, the loop filter makes decision on two factors: motion vector difference between adjacent blocks is greater than two or it selects filter strength depending on number of coefficients coded in the block (that one I don’t remember seeing before). The filter is the same in all cases (inter/intra, luma/chroma, edge/inside macroblock), only the number of pixels filtered varies between zero and two on each side (more on that later). This is nice and elegant design IMO.

Second, filtering is done after each macroblock, horizontal edges first, vertical edges after that—but not necessarily for all macroblocks. Since BIKi or BIKj encoder can signal “do not deblock macroblocks in these rows and columns” by transmitting set of flags for columns and rows.

Third, in addition to normal filtering decoder can do something that I still don’t understand but it looks like whole-block overlapping in both directions (and it is performed in actual decoding but I don’t know what happens with the result of it).

And the filter itself is not that interesting (assuming we filter buf[0] buf[1] | buf[2] buf[3]:

    diff0 = buf[2] - buf[1] + 8 >> 4;
    diff1 = diff0 * 4 + 8 >> 4;
    if (left_strength >= 2)
        buf[0] = clip8(buf[0] + diff0);
    if (left_strength >= 1)
        buf[1] = clip8(buf[1] + diff1);
    if (right_strength >= 1)
        buf[2] = clip8(buf[2] - diff1);
    if (right_strength >= 2)
        buf[3] = clip8(buf[3] - diff0);

Strength is determined like this: 0 — more than 8 coefficients coded, 1 – MV difference or 4-7 coefficients coded, 2 — 1-3 coefficients coded, 3 — no coefficients coded.

Overall, the loop filter is nice and simple if you ignore the existence of some additional filter functions and very optimised implementation that is not that much fun to untangle.

Update: the alternative function seems to be some kind of block reconstruction based on DCs. In case it’s intra block with less than four coefficients coded it will take all neighbouring DCs, select those not differing by more than a frame-defined threshold and smooth the differences. I still don’t understand its purpose in full though.

I’m proud to say that NihAV got TrueMotion 2X support. For now only intra frames are supported but 75% of the samples I have (i.e. three samples) have just intra frames. At least I could check that it works as supposed.

First, here’s codec description after I managed to write a working decoder for it. TrueMotion 2X is another of those codecs that’s closer to TrueMotion 1 in design. It still uses the same variable-length codebook instead of Huffman coding (actually only version 5 of this codec uses bit reading for anything). It also uses “apply variable amount of deltas per block” approach but instead of old fixed scheme it now defines twenty-something coding approaches and tells decoder which ones to use in current frame. That is done because block size now can be variable too (but it’s always 8 in all files I’ve seen). And blocks are grouped in tiles (usually equivalent to one row of blocks but again, it may vary). The frame data obfuscation that XORs chunks inside the frame with a 32-bit key derived in a special way is not worth mentioning.

Second, the reference is quite peculiar too. It decodes frame data by filling an array of pointers to the functions that decode each line segment with proper mode, move to the next line and repeat. And those functions are in handwritten assembly—they use stack pointer register for decoder context pointer (that has original ESP saved somewhere inside), which also means they do not use stack space for anything and instead of returning they simply jump to the next routine until the final one restores the stack and returns properly. Thankfully Ghidra allows to assign context argument to ESP and while decompile still looks useless, assembly has proper references in the form mov EDX, dword ptr [ctx->luma_pred + ESP].

And finally, I could not check what binary specification really does because MPlayer could not run it. At first I tried running working combination of WMP+Win98 under OllyDbg in QEMU but it was painfully slow and even more painful to look at the memory state. In result I’ve managed to run TM2X decoder in MPlayer which then served as a good reference. The trick is that you should not try to run tm2X.dll (it’s really hopeless) but rather to take tm2Xdec.ax (or deceptively named tm20dec.ax from the same distribution that can handle TM2X unlike its earlier versions), patch one byte for check in DLL init and it works surprisingly well after that.

So what’s next? Probably I’ll just add missing features for the second TM2X sample (the other two samples are TM2A), maybe add Bink2 deblocking feature—since I’d rather have that decoder complete—and move to improving overall NihAV design. Frame management needs proper rework before I add more codecs—I want to change into a thread-safe version before I add more decoders. Plus I’ll need to add some missing bits for a player. There’s a lot of work still to do but I’m pleased that I still managed to do something.

So NihAV finally got Discworld Noir BMV support and I’ve tested it on all samples from the game to see if it works correctly. Here’s a sample frame:

(I still remember the song Samael plays there and have it somewhere ripped in its full MPEG audio layer II glory).

Now I want to talk about the format since it’s quite different from anything else. BMV used in Discworld II was simple but with two quirks: it employed integer coding using variable amount of nibbles (that were read as bytes but a nibble could be saved and used later) and it could decode frame either from the beginning to end or from end to beginning (reading frame data from the end too!). DW3 BMV is even stranger and let’s start with audio part. Audio codec is very simple: you have 41-byte block with one byte signalling which quantised values tables should be used for both channels and 32 indices for each channel packed into 16-bit words. The main peculiarity is that data is aligned to 16-bit and mode byte can be either in the beginning or at the end of the block. That’s a bit unusual but not strange. Well, it turns out it aligns for the absolute position in a file so my demuxer has to signal whether audio data was at even or odd position. And video is even stranger.

As I wrote previously, video codec is 16-bit now and still employs nibble variable integer coding and copy/repeat/new pixels mode. Luckily there is no backwards decoding mode yet the codec is tricky without it. First of all, where previously there were just three plain modes now we have combinations of those with bytes or nibbles signalling what should be done (i.e. copy/repeat/put new pixels fixed amount of times and then do the other operation another fixed amount of times). And they have different meaning depending on what was the last operation (copy/repeat/put for fixed amount or with arbitrary large one). And if there’s a nibble left unread after last operation or not. But that’s not all! While previously reading new pixels meant just reading a byte, 16-bit pixels can be compressed a bit more. In result we read 1-3 bytes per pixel: first read index byte, remap it, if it’s in range 00..F7 then return pixel in an array, if it’s in range F8..FE then read another byte and use it as an index in one of seven secondary “palettes”; if it’s FF then simply read explicit 2-byte value from the stream. The reference simply used an array pointing to the various functions performing this. And of course palettes can be updated in the beginning of each frame.

Surprisingly, decoder implementation takes about 28kB with a quarter of it being tables. That’s for both audio and video decoder. This is on par with other game decoders (GDV, Smacker and VMD) and feels significantly smaller than the reference (which is about 30kB in a stripped assembled .o file and over 200kB as assembly).

Overall it was hard to comprehend and tricky to debug too. Nevertheless now it’s over and I can probably move to TrueMotion 2X. Or whatever I decide to do when I’m bored enough.

I’ve made some significant progress on REing Discworld Noir BMV.

First, I put opcodes meaning into table (it’s probably the only case when I had to use spreadsheet for REing) to figure out the meaning.

Normal mode of operation have these opcodes:

• 00**00*0 — perform extra-long copy;
• 00**00*1 — perform extra-long invoking of pixel functions;
• 00**xxx0 — copy xxx-1 pixels;
• 00**xxx1 — invoke pixel function xxx-1 times;
• xxxx000y — copy xxxx+3+y pixels;
• xxxx001y — invoke pixel function xxxx+3+y times;<
• xxx0yyy0 — copy yyy-1 pixels and then invoke pixel function xxx-3 times;
• xxx0yyy1 — invoke pixel function yyy-1 times and then repeat last value xxx-3 times;
• xxx1yyy0 — copy yyy-1 pixels and then repeat last value xxx-3 times;
• xxx1yyy1 — invoke pixel function yyy-1 times and then copy xxx-3 pixels.

Then depending on last operation performed mode is changed to: something special for 00****** opcodes, no change for repeat, “after copy mode” and “after pixel func mode” for obvious cases.

After copy mode opcodes:

• xxxxxxx0 — invoke normal mode opcode xxxxxxx1;
• 00**00** — extended repeat;
• 00**xxx1 — repeat last value xxx-1 times;
• xxxx00y1 — repeat last value xxxx+3+y times;
• xxx0yyy0 — repeat last value yyy-1 times and copy xxxx-3 pixels;
• xxx0yyy1 — repeat last value yyy-1 times and copy xxxx-3 pixels;
• xxx1yyy1 — repeat last value yyy-1 times and invoke pixels function xxxx-3 times.

After pixel function mode is simple: xxxxxxx0 opcode is after copy mode xxxxxxx1 opcode and xxxxxxx1 opcode is normal mode xxxxxxx0 opcode.

The special modes may have secondary opcodes that usually boil down to the same thing: either do some more of the same and proceed normally or calculate next opcode instead of reading it from the stream.

And now the second thing: I’ve managed to rip the relevant code from the disassembly, fix it for NASM to handle plus added some fixed to make it possible to invoke externally and linked it against my own small program that parses BMV file, decodes the first video frame and dumps it into file. That approach works so I have something to test my new implementation against. Also since NASM makes all labels visible it’s easy to make debugger report each opcode as it gets called.

To summarise, I have good understanding of the algorithm and I have a working binary specification. This should be enough to finish it soon (unless I get distracted by something else of course).

As I’ve mentioned before, NihAV now can decode Bink2 files more or less decently. I don’t have many samples but I can decode all samples I could find from KB2f to KB2j quite well (the only exception is KB2a — there’s only one partial sample known with no indication which game uses it and no version of RAD tools understands it either).

I’ve omitted support for full-resolution Bink2 files (no samples) and reconstruction is not perfect because there’s an in-loop deblocking filter with some additional crazy functions invoked in some cases. It’s messy and does not affect actual bitstream decoding so I’m not going to work on it now. Maybe if I get some inspiration later…

Anyway, I moved to REing Discworld Noir BMV format instead. While the game is nice, it’s hard to run on any modern OS and there’s almost no hope for its engine being reimplemented. So maybe I’ll be able to re-watch cutscenes from it… I’ve figured out container and audio long time ago, video is not that easy. It seems to be an upgrade of Discworld II BMV that outputs 16-bit video but the way it’s implemented is baffling.

While locating the functions responsible for the decoding was easy, understanding them was hard. For the disassembler. No, the code was recognized fine but its flow makes even disassembler freak out. Here’s how it works:

1. The frame decoding function reads pixel values, fills certain arrays and patches functions that return pixel values (nice start, isn’t it?) and then the real frame decoding starts;
2. Frame decoding is done like a state machine (which complements coroutines used elsewhere in the engine) with several tables for handling 256 opcodes (or less in some cases);
3. In result you read byte, jump to one of the labels, perform the operation, read the next opcode, jump using the same or different table;
4. Except when it’s opcodes 00-3F, then you usually have to construct length word, perform some pixel output loop and then jump to another opcode handler which performs some operation and then jump to the address calculated by the previous operation;
5. Of course pixel functions are some permuted array of 256 pointers to the functions of three different kinds: return fixed value (set by the decoding function in the beginning), read byte and return pixel value from the corresponding array or read new pixel value from the stream;
6. And to make it all even better, all those operations are obviously not actual functions but small(er) chunks of assembly code that use fixed registers as arguments and they’re located both before and after decoding function “body”.

Anyway, I’ve made some progress and I reckon it will be possible to support this format in NihAV though maybe not soon enough.

After managing to decode the first frame of KB2g variant I had three options: try to decode the other frames, try to decode other variants or do nothing. While the third option is the most appealing and the first option is the most logical, I stuck with the second one. So now I can decode the first frame of KB2f variant of Bink2 as well. Unfortunately the only (partial) KB2a sample I know is not supported, probably it’s a beta version that was tried on one game like Bink version b. Beside a small surprise in one place bitstream decoding was rather simple. Inter-frame support should not be that hard but it might get messy because of the DC and MV prediction.

And while talking about REing Bink I should mention that I’ve tried Ghidra while doing KB2f work. It is a nice tool that sucks in some places (not having a good highlight for variables, decompiling SIMD code results in very questionable output, the system being Java-based and requiring recent JDK—that’s the worst issue really) it works and produces decent results (including the decompiler). Also since it has 16-bit decompiler support maybe I’ll manage to figure out how those clips in Monty Python & the Quest for the Holy Grail are stored.

I should start documenting it too.

Insignificant update: okay, now it decodes inter-frame data correctly too and the only thing left is to make it reconstruct them correctly. Also I’ve updated codec information on Multimedia Wiki. Actually now it works quite okay so I’m not going to pursue it further. I have no real interest in Bink2 decoding after all.

It took a long time but finally I can decode the first frame of Bink2 video (just KB2g flavour though but it’s a start).

At least the initial observations were correct: Bink2 codes data in 32×32 macroblocks, two codebooks for AC zero runs, one codebook for motion vector components, simple codes with unary prefix for the rest.

If you wonder why it took so long—that’s because I’m lazy and spend an hour or less a day on it. Also while the codec is simple in design it’s a bit complicated in implementation. While previous version related on format sub-version to decide which feature to use, Bink2 uses frame flags to decide which feature to use. For instance, flag 0x1000 signals that there are two bit arrays coded that tell when to read an additional flag during CBP decoding that tells which one of two codebooks should be used during AC decoding later. And flag 0x2000 essentially tells to use different bitstream decoding (like motion vectors decoding or block type decoding). Or the fact that it employs DC and MV prediction that usually has four cases (top-left macroblock, top block, left block, some block inside) plus WMV1-like handling of DC prediction in inter-frames (i.e. it calculated DC for inter blocks and uses them for prediction). And of course DC prediction for inter blocks works a bit different. Plus it tries to track internal state by packing all flags into 32-bit word and updating it for each block (two bits are for signalling top row, one—for macroblock being the leftmost one, some bits are copied from frame flags etc etc). So there’s a lot of nuances to take care of.

And that’s not counting the fact that current Bink2 player can’t decode versions prior to KB2g at all. Since I have some KB2f samples along with an old Bink player that can handle them, I guess I’ll support them eventually.

Okay, I’ve finally done all the low-hanging fruits and now the progress is blocked by the need of reverse engineering (namely, Bink 2, Discworld Noir BMV and TrueMotion 2X) so I don’t expect anything major happening to the project in near time.

Meanwhile it’s a good opportunity to talk about how NihAV is (mis)designed and how it should work in principle.

In principle there are three scenarios: playing the file, encoding raw input and transcoding. And first two can be considered to be transcoding with known raw inputs or outputs plus specific requirements to them.

So, what needs to be done if we want to transcode something into something else:

1. detect the input format and open it;
2. select input streams and open decoders for them;
3. create encoders for desired output;
4. negotiate formats between inputs and outputs (minding the possible other filters inside the pipeline);
5. read input, process, synchronise if required, feed to output.

If this sounds obvious—that’s because it is. If it sounds trivial then you miss wonderful complications that may occur at every stage.

Detecting input format may be not trivial because not all containers have proper markers and you can either rely on extension or try every possible demuxer to see if it works. NihAV allows flexibility in this choice: there is a standalone nihav_core::detect module that allows to probe file for known container format and it will return a most probable container name and score (either extension match or marker check match). This way you can find out format even if you don’t have demuxer registered for it. And if you’re desperate you can try opening that file with all registered demuxers to see which one fit (my tools won’t do that probably but it’s easy to do even with current API).

Then you have input streams. In some cases you have proper streams with packets, in other cases you have raw stream which you have to split into packets yourself. One solution would be to mark those streams as requiring parsing and automatically insert a parser as well. NihAV design (not yet implemented since I don’t need it yet) tells to report elementary stream as its own type and return data that should be parsed elsewhere. The same applies for files that are raw elementary streams. If you want to be able to decode /dev/random as MPEG Audio Layer I you should force the proper parser and decoder yourself.

Actual decoding should be done in traditional way: a packet goes it, a frame comes out (in the exceptional cases it should report DecoderError::TryAgain but it’s really for exceptional cases; previously I thought about inserting queues of packets/frames between processing units but finally decided against it). Decoders should do no reordering. If you wonder how the caller should be able to reconstruct the proper order, it’s simple enough. There is a global nihav_core::registry (as well as the format detection module it may be moved into separate crate in the future) that contains information about all known codecs. And knowing the codec information you can create a proper frame reshuffler (none for many formats, the one that reorders using frame type for I/P/B-frame codec and something more complex for codecs with pyramid referencing scheme like H.264 or H.EVC).

While I don’t have this functionality yet it’s not that bad since currently I simply output frames into single images and sleepsort works fine (i.e. if frame00004.ppm is created before frame000002.ppm it’s no big deal for image viewer).

Encoders are something I have not considered yet.

Format negotiation is currently implemented only for video frames in nihav_core::scale module. It works as I described it three years ago: converter adds necessary stages for frame unpacking, rescaling, format conversion and packing. Of course if some stage is not needed it’s not added. The only annoying thing is that internally I use typed frames, so frames with an array of bytes, an array of 16-bit ints and 32-bit ints should be handled separately. At least that means I internally always work with native-endian data and the actual converting is done only when the data is read or written. And of course this is mostly just proof of concept than fully-working solution but it can convert e.g. RGB565 into YUV410 while rescaling it too.

And it’s worth mentioning that another fun issue is timestamps and how to interpolate them when they are missing. Since there’s no good universal solution I’d not try to invent something complex either and I’ll probably stick to the laziest approach.

Overall, I intend to create nihav-pipeline crate (that’s a tentative name) for handling some of the middle-level stuff like frame reordering and timestamp related issues that can be served as a base for both transcoder (definitely not coming this year) and player (this one might actually appear this year). But for now nihav-tool that decodes files into sequences of images and wave files is enough for experiments. I care mostly about decoding after all.

As you can guess from the title NihAV got some support for Duck formats, namely TrueMotion 1 and TrueMotion RT. The implementation was rather straightforward except that it took some additional work to support 16-bit video buffers.

Of course I made sure my new TM1 decoder supports decoding sprites. Here’s an example of such sprite picture:

The hardest part was finding a sample.

I can’t sanely support transparency though since it uses 6-bit alpha with RGB555 image and while I can support such format quite easily I’d rather not.

If you wonder about the details of sprite support, it’s almost the same as ordinary inter-coded 16-bit TM1 with some nuances:

1. frame header has additional 16-bit fields for sprite position and size (and actual sprite size is used in the decoding—the result is supposed to be put over the destination picture);
2. sprite has twice as much mask bits as inter frame—two per 4×4 block (LSB first as usual). Bits 00 mean the next four pixels should be skipped (and predictor reset to zero), bits 01 mean it’s opaque sprite data and bits 10 mean it’s sprite data with transparency info present;
3. sprite data is decoded as standard 4×4 TM1 block data (i.e. on C delta per 4×4 block) except that in transparency mode it also reads transparency data after each pixel pair.

That information comes from our old trusty source of information called VPVision source code dump (which was used to understand TrueMotion 1, 2 and probably DK3/DK4 ADPCM (and maybe VP3 but I’m not sure at all). Also it turns out to contain TrueMotion RT encoder source code as well (which could be used to reconstruct the decoder but I forgot about it at the time and used the binary specification instead).

And now I’d like to talk about Duck codecs in general.

The codecs from this family can be divided into three groups:

1. The Age of Darkness: the original TrueMotion codec and its evolution plus related ADPCM codecs;
2. The Age of Enlightenment: game codecs evolving into more generic video codecs and using more mainstream codec design (DCT-based, many ideas borrowed from H.263 and H.264) plus AVC (that’s audio codec if you don’t remember);
3. The Age of EA Guardian: the codecs produced after Duck was bought by certain company.

The Age of Darkness codecs

Those codecs were used mostly in video games but TM1 was also licensed to Horizons Technology.

The idea behind TM1 is very simple: you split video into 4×4 blocks, predict each pixel from top and pack using quantised deltas and fixed codebook looking more like Tunstall codes (i.e. output code is always a fixed length of one byte but it may correspond to a variable length sequence of input codes). Also depending on quality frame blocks have different number of colour difference deltas per block (1, 2 or 4).

TrueMotion RT is an adaptation of TM1 for real-time video capturing (hence the name). In this case video is coded as planar YUV410 using fixed set of deltas with index taking 2, 3 or 4 bits. But the general coding idea (top and left prediction, delta quantisation and coding its index) remains the same. It uses the same frame header obfuscation so it’s probably an elder sibling of TrueMotion 2 (and its name is more like TrueMotion RT version 2.0 and not TrueMotion 2 RT but the details are unclear). There are different versions of the codec, for example Star Control II: The Ur-Quan Masters on 3DO used a special TM1 format split into several files: .hdr for global information (including quantised delta sets), .tbl with codebook definition, .duk with actual frame data and .frm with the frame offsets for .duk file. It’s a pity I can’t support it without very special handling.

TrueMotion 2 gets rid of single static codebook and packs appropriate data (deltas for different-resolution blocks, motion vector data, actual block types etc etc) in separate segments with their own Huffman codes. There are many improvements but the codec still operates on 4×4 blocks with horizontal and vertical prediction of each symbol.

There is not much known about TrueMotion 2X but so far it looks like maybe slightly improved TM2. Hopefully it will be clearer if I manage to implement a decoder for it.

And finally there were two simple ADPCM codecs accompanying video (usually TM2), there’s nothing much to say about those.

The Age of Enlightenment codecs

This was the age when Duck codecs became widely known and accepted, when various companies licensed them for their own needs and when it was really the golden age for them.

It all starts with TrueMotion VP3 that set the standard for the following codecs. It employed the a bit non-standard 8×8 DCT, referencing last intra frame as an alternative to referencing just the previous frame (later knows as golden frame), with various types of information grouped together instead of interleaving it all, and with coefficients coded as tokens (EOB, zero run, plus-minus one, plus-minus two, large coefficient token and such). The same approach would be used for subsequent codecs as well. Of course it briefly enjoyed the renaissance when Duck decided to put it into open-source and Xiph Theora was created on its base (and since there were no other free and open-source video codec alternatives it was destined to have popularity and success before something better comes).

TrueMotion VP4 was mostly the same but with different coding method for some data types. Maybe it was the first codec to move edge loop filtering from being performed on the frame to being performed on temporary block used in motion compensation but I’m not entirely sure.

TrueCast VP5 was the first in the series to employ their own version of static binary arithmetic coder mostly known as bool coder. That means that instead of updating bit probability after each decoding using that context as CABAC does, frame header encodes fixed probabilities (or just updates from the probabilities in the previous frame) and uses them for decoding.

VP6. Probably the most famous of them all since it was used in Flash videos. From technical point of view it’s just small improvement in some details over VP5. I suspect this was the first codec in the series that introduced selecting random frame as the next golden frame (previously it was just last intra frame, now any inter frame can signal that it should become golden).

VP7. This is the first installation in the series that was based on H.264 ideas like 4×4 transform and spatial prediction.

And of course there’s AVS, an audio codec inspired by AAC LC that accompanied some VP5-VP7 videos.

The Age of Guardian codecs

While the design direction has not changed much, the codecs themselves mostly belong to the niche provided by their current owner and hardly used anywhere else. For now we have VP8, VP9 and VP10 (aka AV1).

I hope there will be more to write about those after I write decoders for the rest of them and learn the shameful details of their design in the process.

I have not written anything about NihAV for the last two months. If you thought it’s because nothing was done you’d be mostly correct (but not in thinking about the project at all—this is pointless). And yet there has been some progress recently (but before that I spent a whole month not doing anything NihAV-related).

First thing, I’ve finally split NihAV into smaller crates. This was done in order to reduce compilation and testing time for separate components. It started to feel a lot like FFmpeg and Libav times except that I don’t have to rerun configure and recompile everything in case I want to add a new decoder. Now codecs reside in standalone crates that contain just relevant decoders and demuxers so “write code—fail to compile—fix—run tests” cycle goes faster now.

And here’s the new structure:

• nihav-core — the core. It contains the definitions for basic stuff like packets and video/audio buffers, I/O routines (byte- and bitreader), DSP and common video stuff for H.263-based decoders;
• nihav-commonfmt — for various common formats. Currently it has all leftover codecs I could not move elsewhere (and AVI demuxer). Maybe in the future it will grow too large so I’ll split out some groups like speech codecs into new crates;
• nihav-duck — for Duck game codecs up to VP7;
• nihav-game — for various game codecs and containers;
• nihav-indeo — for Indeo video and audio codecs;
• nihav-rad — for totally RAD formats like Smacker and Bink;
• nihav-realmedia — full RealMedia support (except for common decoders in nihav-commonfmt);
• and finally nihav-allstuff — the crate that binds them all so you don’t have to search for decoders in separate crates.

Of course there’s nihav-tool to perform the actual decoding and test whether the code works but it’s always been a standalone crate.

This split required some changes in the decoder and demuxer handling. Previously I could get away with one table where all decoders (or demuxers) were registered and then search for an appropriate decoder there. Now it is not possible since there are many crates with individual codecs enabled or disabled in configuration. In result I had to introduce a structure called RegisteredDecoders and have crate-specific function for registering all decoders featured in crate in it. And nihav_allstuff::nihav_register_all_codecs() simply invokes them all for convenience. It’s exactly the same with demuxers too.

N.B.: I should probably write a separate post on overall NihAV design, missing parts and excuses for certain decisions.

Second, as you could spot from the crate names above, instead of trying to make NihAV do something useful (you have rust-av for that though) I decided to focus more on supporting various game formats.

So far I want to support the following formats:

1. Sierra VMD (developed by Coktel Vision but I care more for Sierra games). Should be an easy one-shot;
2. Discworld II and Noir BMV. I have added support for DW2 BMV format already (and it took a day to reimplement). DW3 BMV format is almost the same, DW3 audio is known but video codec still requires some reverse engineering. Also fun fact—DW2 BMV video decoder is based on reverse engineered decoder from ScummVM where they did not understand how decoding lengths works and the code still looks like a beautified assembly. For libavcodec decoder I tried my best to simplify the code and give better names to the variables. And when implementing the decoder for nihav-game I found out that “read byte, advance pointer, output nibble and save another one for later” leads to the same results but with a much cleaner code;
3. RAD codecs. I’ve reimplemented Smacker and Bink formats support (the worst part was NIH-y implementations for DCT-II/DCT-III used in Bink audio decoder but that’s a tale for another time). Maybe now I’ll finally write a decoder for Bink2 video;
4. Duck codecs. Yes, they are game formats that also were tried as general codecs but with lesser success. There are many games using TrueMotion 1, there are many games using TrueMotion 2, there are some games using TrueMotion VP3 and VP6 in their cutscenes. And the only their codec that got widespread is VP6. I want to implement all the family of the codecs that Duck produced before dying ascending to the higher plane of existence. While most of them are supported there are still missing features like sprites in TrueMotion 1, interlaced mode in VP6 or TM2X entirely. It requires some REing of course but that’s the appeal.

After that it would be nice to work on actual player for the supported formats, which opens a new can of worms like proper frame reordering and format conversion, but I guess I’ll have to deal with that one day.

Anyway, back to doing nothing.

In order to celebrate the fact all important Dingo Pictures works were found (there might be more though) I decided to visit the birthplace of those masterpieces. You can find their address at the website or at Baidu Maps (with some reviews, mostly in English and Swedish).

Without further ado I present to you the studio:

Yes, this is really the place of people who gave us (or at least me) many hours of fun and joy.
Here’s a postbox with some familiar names if you don’t believe it.

And if you search local news you might learn that those people were local legends probably even before they were immortalised by cartoons. But before only the area around Frankfurt on Main knew about their talents and now the whole world does. And I’m grateful for having an opportunity to discover this whole new genre of German anime which would not be possible without them.