Conquering yet another game format

June 18th, 2023

Sometimes I watch reviews of various old video games (usually of adventure type but not necessarily). This time it was Conquest Earth RTS from 1997 and the reviewer said magic words: “I was not able to extract or play videos with anything”. Okay, you got my attention.

I could find some .rpl files there using Escape 124 codec (yes, Eidos was the publisher, how could you tell?), some standalone .flh files and some flicN.wad archives. Despite the name, the archives turned out to have a footer, i.e. all metadata is stored at the end for a change. The video files seem to be some .flc but mostly .flh.

As one could reasonably expect, it turned out to be yet another hack of the old venerable FLIC format, now with RNCv2 compression. I did not look further to find out whether it’s raw frame or RLE-compressed data there but it does not matter much as the main features are already discovered.

There are many various FLIC extensions, like high(er)-bitdepth video, custom RLE coding schemes and even audio support. And that’s not counting the fun things like FLIC-in-AVI or FLIC-in-AVI. But I leave documenting all those format variations to The Multimedia Mike, gaming and documenting FLIC are his passions.

One last experiment with Cinepak encoder

June 17th, 2023

I’ve remembered that back in the day there was an encoder for RoQ format (the format that uses a codebook with 2×2 YUV vectors, what a coincidence!) called Switchblade and it was using NeuQuant before it was integrated into FFmpeg where it started to use ELBG. So I decided to give it a try.

If you have forgotten, NeuQuant is an application of Kohonen neural network to the task of generating palette for an image. I’ve implemented that kind already so I tried my hoof at adapting it for a larger vector size. Good thing: it works and it’s reasonably fast (2-3 times slower than median cut, faster than partitioned ELBG—and that’s the code that uses doubles for the majority of its calculations). Bad thing: the result quality is mediocre. The results obviously can be improved by adjusting various factors (wait, am I talking about neural network or string theory?) and changing the pseudo-random order in which the candidates are sampled but I don’t feel enthusiastic about tweaking all those parameters and see which ones work good for the widest selection of video sequences.

So I’m drawing a line here. It was a quick and failed experiment, I should find something better to do.

Yet another MOV quirk

June 15th, 2023

Since I had nothing better to do I was browsing FMV games at archive.org and in one of them I found rather peculiar sample: avconv has wrong palette for the first half of it and nihav-tool has wrong palette in the second half of the clip. And I thought that MOV is not supposed to have palette changes at all.

It turned out they used a multiple sample descriptors trick: it’s possible to provide several codec descriptions for one track and use one or another for different frames. That file has two descriptors for the video track with different palettes. Mystery solved.

And it also solved another mystery with a different file from that game where some frames are not decoded properly. It turned out that it also has two sample descriptors for the video track: one is A**le Graphics and another one is Cinepak.

Back in the day I ranted that MOV is too flexible and this proves once again how true that is. Good thing I don’t have to care about supporting such files properly.

NihAV: another step to being self-sufficient

June 13th, 2023

I’ve mentioned previously that I played with my H.264 decoder trying to make it multi-threaded. Now I went a bit further and plugged it into my video player. So now instead of hopelessly lagging on 720p video it can play it in real time just fine—so after improving my player even further (and enabling assembly optimisations when Rust compiler is good enough for that) I can use it to play most of the videos I care about without resorting to the external decoders or players. And in theory using it more will lead to fixing and polishing it more thus forming a stable loop.

Anyway, the code is not public yet as I hacked this new encoder in a separate crate and I still need to merge it back and clean up a bit, but I’d like to describe the interfaces and my reasons behind them.

So, multi-threaded decoder has a separate interface (for obvious reasons). I thought about writing a wrapper for single-threaded decoders to behave like multi-threaded ones but decided against it (at least for now). NADecoderMT has the following methods:

  • init()—initialises the decoder. One of the parameters is number of threads to use. IMO it’s the caller that decides how many threads it can spare as the decoder does not know what will be done in parallel (maybe there’s another multi-threaded decoder or two are running);
  • can_take_input()—queries if the decoder is ready to queue the next frame for decoding. Of course you can call queue_pkt() and check if it accepted the input but it may not always be desired (e.g. if we need to retrieve an input packet and then hold it waiting until the decoder is ready to accept it);
  • queue_pkt()—tries to queue the next frame for decoding;
  • has_output()—checks if the decoder has produced some frames for the output. Since get_frame() is waiting for a frame to be decoded this function is necessary unless you want to block the thread calling the decoder;
  • get_frame()—waits until at least one frame is decoded and returns it (or a special error if there are no frames to be decoded);
  • flush()—stops decoding all frames and clears the state (e.g. after seek).

Another peculiarity of this decoder interface is that it operates on pairs of a frame and its sequential number. The reason is simple: you get decoded frames out of order so you need to distinguish them somehow (and in case of a decoding error we need to know which frame caused it).

This also leads to a special frame reorder mechanism for such codecs. I’ve created MTFrameReorderer that requires you to “register” frame for decoding (providing you with an ID that is fed to the decoder along with frame data) and to “unregister” frame on error (that’s one of the places where returned frame ID comes in handy). Unfortunately it’s not possible to create a generic reorderer that would a) work completely codec-agnostic b) not require a whole file (or an indefinitely long sequence of frames) to be buffered before output and c) produce monotone increasing sequence of frames. Considering how H.264 has no real concept of frames and can build a pyramid of referenced frames adding layer by layer (and mind you, some frames may have an error during decoding and thus not present in output). I simply gave up and made a heuristic that checks if we have enough initial frames decoded and outputs some of them if it’s possible. At least it seems to work rather fine on the conformance suite (except for a couple of specially crafter files but oh well).

Maybe in the future I’ll try more multi-threaded decoders but for now even one decoder is enough, especially such practical one. Still, I need to find something more interesting to do.

Further Cinepak experiments

June 5th, 2023

For having nothing better to do I kept experimenting with Cinepak encoder.

I considered implementing some variant of codebook decomposition scheme suggested by Tomas in the comments to the previous post but I’m still not sure if I should bother even if it looks promising. So I tried the old thresholds-based scheme instead.

And what do you know, it speeds things up considerably: my usual test sample gets encoded in 27-35 seconds (depending on thresholds) instead of 44 seconds in the usual mode. But since I don’t know what would be good thresholds I did the opposite and added a refinement mode: after deciding which codebook to use for which block I re-generate codebook using only those blocks that belong to it. Of course it increases processing time, for example that file it takes 75 seconds to encode with refinement—which is still 70% more time but still less than double (for comparison, in full ELBG mode it’s an increase from about 160 seconds to 270 seconds).

So by rough estimate selecting only relevant blocks for codebook generation shaves 20-40% off the encoding time. And splitting data into partitions and generating a codebook by parts made the process about three times faster. I suspect that with a proper approach to clustering vector quantisation can be made two-three times faster but I don’t think I want to experiment with that. I should call it a day and move to something else instead.

Quick experiments with Cinepak encoder vector quantisation

June 3rd, 2023

Out of curiosity I decided to check how partitioning input before creating a codebook affects encoding speed. So I’ve added a mode to Cinepak encoder that partitions vectors by luma variance and creates a part of common codebook just for them. The other two modes are median cut (the simplest one but also with mediocre output) and ELBG (that uses median cut to create the initial codebook—also if it’s not full that means we have all possible entries and do not need to perform ELBG at all).

Here are rough results on encoding several different files (and using different number of strips): median cut worked for 11-14 seconds, ELBG took 110-160 seconds, new mode (I decided to call it fast) takes 43-62 seconds. I think even such approximate numbers speak for themselves. Also there’s an interesting side effect: because of the partitioning it tends to produce smaller codebooks overall.

And while we’re speaking about quantisation results, here’s the first frame of waterfall sample encoded in different modes:

median cut

fast

full ELBG

As you can see, median cut produces not so good images but maybe those artefacts will make people think about the original Cinepak more. Fast mode is much nicer but it still has some artefacts (just look at the left edge of the waterfall) but if you don’t pay too much attention it’s not much worse than full ELBG.

Are there ways to improve it even further? Definitely. For starters, the original encoder exploits the previous codebook to create a new one while my encoder always generates a new codebook from scratch (in theory I can skip median cut stage for inter strips but I suspect that ELBG will work much longer in this case). The second way is to fasten up the ELBG itself. From what I could see it spends most of the time determining to which cluster each of the points belong. By having some smarter structure (something like k-d tree and some caching to skip recalculating certain clusters altogether) it should be possible to speed it up in several times. Unfortunately in this case I value clarity more so I’ll leave it as is.

P.S. I may also try to see how using thresholds and block variance to decide its coding mode affects the speed and quality (as in this case we first decide how to code blocks and then form codebooks for them instead of forming codebooks first and then deciding which mode suits the current block better; and in this case we’ll have smaller sets to make codebooks from too). But I may do something different instead. Or nothing at all.

NihAV experiments: multi-threaded decoder

June 1st, 2023

In my efforts to have an independent player (that relies on third-party libraries merely for doing input and output while the demuxing and decoding is done purely by NihAV) I had to explore the way of writing a multi-threaded H.264 decoder. And while it’s not working perfectly it’s a good proof of a concept. Here I’ll describe how I hacked my existing decoder to support multi-threading.
Read the rest of this entry »

A quick glance at the original Cinepak encoder

May 26th, 2023

Since I don’t have anything to do with NihAV at the time (beside two major tasks that always make me think about doing anything else but them) I decided to look at what tricks did the original Cinepak encoder have.

Apparently it has essentially three settings: interval between key frames (with maximum and minimum values), temporal/spatial quality (for deciding which kinds of coding should be used) and neighbour radius (probably for merging close enough values before actual codebook is calculated).

Skip blocks are decided by sum of squared differences being smaller than the threshold (calculated from the time quality); V1/V4 coding is decided by calculating sum of 2×2 sub-block variances and comparing it against the threshold (calculated from spatial quality).

Codebook creation is done by grouping all blocks into five bins (by logarithm of the variance) and trying to calculate a smaller codebook for each bin independently (so together they’ll make up the full 256-entry codebook).

Overall even if I’m not going to copy that approach it was still interesting to look at.

On the origins of ruscism

May 17th, 2023

A couple of weeks ago Ukrainian parliament has finally recognized this term on the official level and listed several telltale signs of it. But in my opinion they can be boiled down to two main actions: disregarding the laws, agreements and traditions (if some suckers believe in those—then it’s just easier to swindle them) and constantly lying, often in an unconvincing way and usually by attributing own deficiencies to somebody else. They’ve been behaving like that throughout their history (which is partly stolen and partly fictitious), the wars just make it more visible. So, why russians behave like that?

Fascism and Nazism grow to power using the support of the second-worst kind of people: people who feel offended or wronged and do not think for themselves. That sort of folks would never blame themselves for their own faults and will gladly follow a leader who has simple answers to questions like who’s guilty and what to do (those answers are usually “that certain group of people” and “unite around me and do what I tell”). In case of ruscism, I believe it’s not merely an ideology that unites the nation but rather the idea that defines this entity (you’ll see why I don’t consider them a nation soon).

One researcher described russians as a dynamic community where everybody can belong to it or fall from it depending on circumstances (or rather benefits it gives: if I need something from you then you’re my brother, if you need something from me then I don’t know you). From this a rather obvious conclusion follows: russians have failed to develop as a nation—even small tribes usually have clear definition of who belongs to them and who are outsiders—and it must be something immaterial uniting them (i.e. an idea). Nations have not merely clearly defined rules of belonging but also clearly defined territory (no matter if it’s the historical settlement are or pieces of land wrestled from somebody else)—russians claim that russia has no borders and that any territory where a russian has been is a part of russia (IIRC just last year some russian dropped a piece of dirt on Dubai beach and claimed that now it’s all russian soil; I’ve encountered many more examples where common russians believed that some place is russian because they’ve been there).

If you look at the real russian history, it starts with the principality of Suzdal, created on the territories inhabited mostly by Finnic and Ugrian people, conquered by the Golden Horde and after its fall proclaiming itself a legitimate successor and capturing other lands (usually not inhabited by Slavic people either) and yet they tried to turn this multi-ethnic mix into “russians”, partially succeeding at that. Last year the russian führer made a speech that he belongs to all nationalities living in russia—what has not been said is that all those nations are russian only as long as they’re going to war, if they try to move to moscow they’ll be greeted with the traditional “go back to your shithole you non-russian hick” (but if they die at war they’ll be called as “true russian heroes” anyway).

It is hard to define the idea that unites them though. It is not a religion since the original pagan beliefs were replaced by the state-controlled Christian church (unlike many countries where the Church was an independent powerful player, in russia it was created by the state—two or three times even—always to serve the state interests). It is not the idea of exclusivity: such ideas are usually created to support the nation while in russia it’s mostly used to sacrifice russians for that very idea. There’s a difference “you’re the best so everything belongs to you, you just need to go and take it” and “you’re the best so keep living in shit until you’re sent to die for defending that belief somewhere abroad”. Sure, a deep spirituality of russian people is usually mentioned in connection to that but no concrete examples are ever given.

You know, there exists such thing as russian nationalists whose ideas can be boiled down to “russians are being offended; and usually it’s Britain that offends them by acting as a puppeteer of russian government since long ago”. Even funnier that until very recently they were prosecuted by the government—I suppose not for the incompatibility of views but rather because they formed those views independently instead of following the official guidelines.

I propose a different explanation: because of the vague dynamic community russians lost incentive to work themselves (a lot like with socialistic system: why bother if everybody around belong to the same community and you can benefit from them working while not benefiting from working hard yourself? See kulak for an example of russian peasants who worked slightly better than the rest and what happened to them; russian national symbol should’ve been a crab bucket instead), in the same time they believed they can take anything because they all belong to the same community. And the refusal offends them. The same story with them believing that whatever they sell or give as a gift still belongs to them (so they can always take it back or tell what you can do or not with it). That may also be the reason behind russians ignoring all kinds of agreements—they’ve been trained only to recognize “might makes right” rule. Yet it does not prevent them from trying to take what belongs to somebody else again and again (like Ukraine). Why don’t they stop attempts? Because they essentially live off selling natural resources (back in the day it was wax, fat and furs, nowadays it’s oil, gas and metals) and they need somebody to actually mine those resources (usually foreigners) and when the old sources get depleted of course they want to capture a new source of income.

Now consider what happens when such creature feels that everything should belong to it and denied those things, feels that others are more developed in many aspects (not just, say, advanced electronics, but having a functioning society too), feels that others have no respect for them (the archetypical question of a drunk russian is “do you respect me?” hints on it)? You’ll get a gamut of emotions, from the desire to present themselves as much better than in reality to drag others down by attributing them all your own bad features. That is how we get claims that Europe will freeze without russian gas (even in summer—they really claimed that), the claims about famous russian culture (it was created by a small strata of elites, often not of russian origin; for the most of russian population their own culture remained alien and forced from above; russians love to present exceptional cases as the general rule), the claims about Western level of quality of life (in moscow—do not look at the rural area that lacks gas, sewer system and roads) and evil godless Westerners want to occupy and destroy them (they’ve looked in the mirror while creating this lie).

And that’s how we get ruscism: psychological complexes of something not deserving to be called a nation, which realizes and resents that. Throw in their sociopathic disregard for honouring agreements (nothing demonstrates it better than the Budapest Memorandum but they’ve been inventing pretexts or outright violated international treaties for centuries) and the lack of thinking (critical or otherwise—there are countless examples that the discussions with common russians fail because those accept ideas selectively and refuse to see connections between different facts) and you get the perfect mix for disaster.

The sad thing is that all russians are infected by it in one form or another. Some may demand nuclear holocaust for all countries that do not ally with them, others merely cheer at the news of russian war criminals killing civilians. Some want russia to conquer the whole world (or at least restore its borders to the times of USSR or russian empire), others simply want russia to end war and not get punished for all its war crimes. Some want to destroy USA, others believe that USA will collapse soon anyway (and they all secretly want to move there regardless). Some hate all other nations, others don’t (but still despise Jews, people from Asia and Caucasus).

I think now it’s more or less clear what the idea unites russians and creates ruscism: russians are those who cast away thinking for a feeling of inferiority. Now, what to do with all that? The realistic way is demonstrated by the Ukrainian Army: over two hundred thousand russians will no longer force their opinions onto others. In theory occupation and re-education might work—it worked for Japan which behaved rather similarly in 20th century—but considering the sheer area of russia and the lack of interest I doubt that even China will attempt it. Meanwhile the best you can do is not to listen to russians at all and check the information you get. Keep thinking, that’s what distinguishes a normal human from russian.

rv4enc: magic numbers

May 16th, 2023

While there’s nothing much to write about the encoder itself (it should be released and forgotten soon), it’s worth recording down how some magic numbers in the code (those not coming from the specification) were obtained. Spoiler: it’s mostly statistics and gut feeling.
Read the rest of this entry »