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 »

rv4enc: probably done

May 13th, 2023

In one of the previous posts I said that this encoder will likely keep me occupied for a long time. Considering how bad was that estimation I must be a programmer.

Anyway, there were four main issues to be resolved: compatibility with the reference player, B-frame selection and performing motion estimation for interpolated macroblocks in them, and rate control.

I gave up on the compatibility. The reference player is unwieldy and I’d rather not run it at all let alone debug it. Nowadays the majority of players use my decoder anyway and the produced videos seem to play fine with it.

The question of motion vector search for interpolated macroblocks was discusses in the previous post. The solution is there but it slows down encoding by several times. As a side note, by omitting intra 4×4 mode in B-frames I’ve got a significant speed-up (ten to thirty percent depending on quantiser) so I decided to keep it this way by default.

The last two issues were resolved with the same trick: estimating frame complexity. This is done in a relatively simple way: calculate SATD (sum of absolute values of Hadamard-transformed block) of the differences between current and some previous frame with motion compensation applied. For speed reasons you can downsample those frames and use a simpler motion search (like with pixel-precision only). And then you can use calculated value to estimate some frame properties.

For example, if the difference between frames 0 and 1 is about the same as the difference between frames 1 and 2 then frame 1 should probably be coded as B-frame. I’ve implemented it as a simple dynamic frame selector that allows one B-frame between reference frames (it can be extended to allow several B-frames but I didn’t bother) and it improved coding compared to the fixed frame order.

Additionally there seems to be a correlation between frame complexity and output frame size (also depending on the quantiser of course). So I reworked rate control system to rely on those factors to select the quantiser for I- and P-frames (adjusting them if the predicted and the actual sizes differ too much). B-frames simply use P-frame quantiser plus constant offset. The system seems to work rather well except that it tends to assign too high quantisers for some frames, resulting in rather crisp I-frame followed by more and more blurry frames.

I suppose I’ll play with it for a week or two, hopefully improving it a bit, and then I shall commit it and move to something else.

P.S. the main goal of NihAV is to provide me with a playground for learning and testing new ideas. If it becomes useful beside that, that’s a bonus (for example, I’m mostly using nihav-sndplay to play audio nowadays). So RealVideo 4 encoder has served its purpose by allowing me to play more with various concepts related to B-frames and rate control (plus there were some other tricks). Even if its output makes RealPlayer hang, even if it’s slow—that does not matter much as I’m not going to use it myself and nobody else is going to use it either (VP6 encoder had some initial burst of interest from some people but none afterwards, and nobody cares about RV4 from the start).

Now the challenge is to find myself an interesting task, because most of the tasks I can think about involve improving some encoder or decoder or—shudder—writing a MOV/MP4 muxer. Oh well, I hope I’ll come with something regardless.

rv4enc: B-frame experiments

May 6th, 2023

As I mentioned in the previous post, one of the problems is to find a good motion vector for B-frame interpolated macroblock. Since I had nothing better to do I’ve decided to try motion vector search in the same style as the usual motion estimation: start from the candidate motion vector pair and try adjusting both vectors using diamond pattern (since it’s the simplest one).

The results are not exciting: while it slightly improves PSNR and reduces file size (on lower quantisers), encoding time explodes. My 17-second 320×240 test clip encoded with quant=16 and two B-frames between I/P-frames takes 40 seconds without that option and 136 seconds with it. And while average PSNR improves from 38.0446 to 38.0521, the size decreases from 1511843 bytes to 1507224.

That’s the law of diminishing returns in action. Of course it can be made significantly faster by e.g. using pre-interpolated set of reference frames but why bother in this case? I’ve put this under an option (i.e. be satisfied with the initial guess or try to search for a better pair of motion vectors) but I doubt anybody will ever use it (the same applies to the whole encoder as well).

rv4enc: somewhat working

May 3rd, 2023

I’ve finally managed to implement more or less working RealVideo 4 encoder with all the main features (yeah, I’m also surprised that I’ve got to this stage this fast). As usual, it’s small details that will take a lot of time to make them decent let alone good.

So, what can my encoder actually do now? It can encode video with I/P/B-frames using provided order, it can encode all possible macroblock types and has some kind of rate control.

What it does not have then? First of all, I don’t know yet how it would fare with the original RealPlayer (I also need to modify RMVB muxer to output improper B-frame timestamps and maybe write the additional streaming-related information). Then there’s a question of having a proper rate control. And finally there are a lot of questions related to B-frames.

Currently my rate control is implemented as a system that keeps statistics on how large is on average an encoded frame for a given frame type and quantiser and tries to find the best fitting quantiser. If there’s still no statistics (or not enough of it) I resort to a simpler quantiser guessing, adjusting quantiser depending on how different are the projected and actual frame sizes. Of course it can be tuned to behave better (the question is how though). And I’m not going to touch the two-pass encoding (theoretically it’s rather simple—you log various encoder information in the first pass and use it to select quantisers better in the second part; in practice it means messing with text data and doing additional guesstimates, so pass).

With B-frames there are two main issues to deal with: which frames to select and how to perform motion estimation. I read the first can be achieved by performing motion compensation against neighbouring frames and calculating SATD (often done on scaled-down frames to be faster). The second question is how to search for a bidirectional block vectors. Currently I have a very simple approach: I search for a forward and backward motion vectors independently and check which combination of them works the best. I suspect there may be an approach specifically for weighted bi-directional search but I could not find anything (and I’m not desperate enough to dive into the codebase of MPEG-4 ASP/AVC encoders).

And finally there’s the whole question of quality. I suspect that my encoder is far from being good because it should not merely transform-quantise-code blocks but also perform some masking (i.e. set some higher-frequency coefficients to zero instead of hoping that they’ll be quantised to zero).

So this will be long and boring work…

A quick look at a watery game video format

April 24th, 2023

As you can guess, my work on Real Video 4 encoder goes so well that I’d rather look at virtually anything else.

Probably some of you are aware of Tex Murphy game series (maybe not even just Mike) and I got reminded of an existence of The Pandora Directive game that supposedly has a lot of videos in it, so I downloaded a demo and decided to explore it a bit.

Game data is packed into extremely simple archive format (just the number of offsets and the offsets) so you need to know what archives to look into (hint: the larger ones).

So what about videos? They start with H2O magic (hence me calling it a watery format) and contain video frames and audio data (in an embedded WAV file). The video compression is both nothing special and somewhat original: it’s Huffman-compressed RLE. Video frame can contain several chunks, first there’s a Huffman tree description, then palette data and finally there’s compressed RLE data. The originality lies in the details: Huffman coding is often used to code single bytes while here single symbol represents both run length and value (also IIUC zero value signals skips), additionally the data is stored as the list of symbols for each codeword length. I don’t think I’ve seen anywhere neither RLE+Huffman used in such manner nor such tree description format.

This was a fun distraction even if I don’t care about the game series (I tried playing their other games like Countdown and Amazon: Guardians of Eden but the interface was too clunky and the action sequences were too annoying). It’s always nice to see some originality in video coding even if it is nothing advanced.

rv4enc: limping forward

April 18th, 2023

So far there’s not much to write about: I’ve dealt with the second most annoying thing (writing coefficients) and now my encoder can produce a valid stream of I- and P-frames. Probably it’s a good place to define a road map though.

First of all, there’s still the most annoying thing pending—in-loop filtering. And I can’t reuse that much code from the decoder since it was written back in the day when my knowledge of Rust was even less than now, so I have to partly rewrite some of the parts to make them fit my current approaches to the interfaces (that means a lot of DSP functions among other things). At least it can be disabled for now but I’ll have to return to it sooner or later.

Then there’s 4×4 intra prediction mode still waiting to be implemented. Again, I know how to pick the good enough prediction modes, it’s context-dependent coding of those modes that is going to be annoying.

Another thing missing is estimating the number of bits required to encode a single block. There are about five codebooks involved and those are selected depending on macroblock type, quantiser, coefficient block type (luma, chroma or luma DCs) and the global set index. I guess I’ll resort to gathering statistics for all possible coding modes and seeing if I can make some heuristic estimation out of it. And there’s still a task of selecting the best coding set for a slice…

After all that it will be mostly B-frame related things left to implement. I also need to make sure the muxer will write them out properly (for historical reasons in that case it mangles the timestamp to be last frame timestamp plus one). That’s not counting all possible enhancements like deciding the frame type for coding. Most likely I’ll be annoyed by it and keep the fixed coding order instead.

There are too many things to do and considering my pace it may keep me busy for a good part of the year—I mean a large part of a calender year, the current date is still February 24.

Starting yet another failure of an encoder

April 6th, 2023

As anybody could’ve guessed from Cook encoder, I’d not want to stop on that and do some video encoder to accompany it. So here I declare that I’m starting working on RealVideo 4 encoder (again, making it public should prevent me from chickening out).

I can salvage up some parts from my VP7 encoder but there are several things that make it different enough from it (beside the bitstream coding): slices and B-frames. Historically RealMedia packets are limited to 64kB and they should not contain partial slices (grouping several slices or even frames in the packet is fine though), so the frame should be split during coding. And while Duck codecs re-invent B-frames to make them still be coded in sequence, RealVideo 4 has honest B-frames that should be reordered before encoding.

So while the core is pretty straightforward (try different coding modes for each macroblock, pick the best one, write bitstream), it gives me enough opportunity to try different aspects of H.264 encoding that I had no reason to care about previously. Maybe I’ll try to see if automatic frame type selection makes sense, maybe I’ll experiment with more advanced motion search algorithms, maybe I’ll try better heuristics for e.g. quantiser selection.

There should be a lot to keep me occupied (but I expect to spend even more time on evading that task for the lack of inspiration or a sheer amount of work to do demotivating me).

Staying neutral

March 31st, 2023

I hate these filthy Neutrals, Kif. With enemies, you know where they stand but with Neutrals, who knows? It sickens me.

Back in the day this quote from Futurama could be seen only at its face value: something only a paranoid jingoistic moron would say. Nowadays we see how the organisations and countries with neutral status use it mostly as an excuse to avoid responsibility for their acts.

Let’s start with various international organisations. Various international sports federations and the IOC say they’re outside politics and welcome money participants from all countries. All while forgetting that accepting participants from the countries that violate their principles of fair sportsmanship is going against those principles (“to oppose any political or commercial abuse of sport” from the Olympic Charter sounds especially ironic). And we have the ICRC that is in theory should act as a neutral mediator between fighting parties. In practice it has destroyed its reputation by not willing to organise anything for Ukraine (I can understand that they could not organise green corridors for Ukrainians because russians were against that but not performing their duties by visiting Ukrainian POWs in russia and essentially participating in war crimes by supporting russian deportation centres—that I cannot neither understand nor forgive). I suspect than in both cases corruption is at play: a dictatorship can always offer money or “gifts” that law-abiding democratic countries can’t.

And of course there’s Useless Nations organisation (still officially called United Nations by mistake). Considering how russia ignores its General Assembly decisions without any repercussions one should wonder about its usefulness already. And then they (as well as certain other international organisations “for all good against everything bad”) release reports blaming both parties: russia for aggression and Ukraine for defending itself. Including the latest scandal with russian “orthodox” church (FSB patriarchy)—it does not matter that in every church and monastery in Ukraine they occupy (in both senses) there were found stashes of russian propaganda, weapons and often russian agents in hiding; it does not matter how the church officials and lower clergy still repeat russian propaganda theses and act against Ukraine—the church is obviously a neutral organisation and should be treated as such.

On the same note, even individuals who repeat the same things about how both parties are wrong and you should stay neutral invoke only disgust in me. In the best case they’re idiots who listen to russian propaganda, in the worst case they’re narcissists who believe only they can be right and the rest of the world is stupid and wrong (place the current Pope into a category you see fit).

Now to the countries with neutral or “neutral” status. Often such country stays neutral because it is too small and cannot afford to anger its neighbours. The classic example of that would be Switzerland (just ignore its army regularly invading Liechtenstein during trainings), Sweden or Israel. Finland remained neutral for a sadder reason: it found out how useless were those alliances for defending it against Soviet aggression (similarly there was a joke in the beginning on 2022 that if russia would invade Poland or Estonia then NATO would react by excluding that country from the alliance). And we also see “neutral” Hungary and China. Let’s take a closer look at all those countries.

Switzerland started out as a small poor country that had fears of being invaded by its stronger neighbours—which happened only once, in Napoleon times (and because of their connections Swiss ended up with more territory when the war was over; those who try to mention Austrian invasion should look first who those Habsburgs were). Nevertheless they decided to remain heavily armed neutrals so that they don’t get involved in wars themselves and when an invader comes a good deal of the population will fight those armies in the mountains (having mountains is a good bonus to defence indeed). That’s why they have the law against transferring their weapons and munitions to the countries in the state of war (I can respect that. Update: after reading this article I’m inclined to re-evaluate their neutrality as to “do whatever we want as long as it does not anger powerful countries much”). In the same time they used their neutral status to conduct unscrupulous trade with all countries of the world (especially during WWII) and to get a reputation of a banking safe haven. But thanks to the pressure from the USA and various data leaks from its own banks it is no longer so. Hopefully in the future the country will survive and prosper on its high-tech chocolate industry and other respectable businesses instead of keeping stolen goods and money from dictators all around the world (just see this list to understand why one of their major banks went belly-up and may take another one with it).

And now to Israel. This is somehow an inverted Switzerland—a unitary state created more or less as a safe haven for a certain nation, it has constant tensions with its neighbours but remains neutral because it does not want its citizens (and potential ones) living in other countries to be harmed (a noble goal really). So in the beginning of the war they remained neutral because they did not want russia to get vengeful and supply a neighbouring terrorist state with something that will harm Israel. russia responded to this with various anti-Semitic statements and actions (read about the Sokhnut court case) and went to arm Iran anyway. Also it helps that the current government is very pro-russian and acts in rather russian ways (see their recent laws and the heavily-opposed legal reform; just another case why you should not have politicians serve indefinitely long terms). Here the neutral status is used to evade certain actions and also to evade responsibility for the other actions. Though the way it goes either the current government will be kicked out or they’ll lose international support.

Let’s move to really neutral countries like Sweden. In XX century it let Norway free after it decided to dissolve the union and the only war-like act during WWI was occupation of Åland that was more of a territorial dispute that was settled more or less peacefully (between Sweden and Finland, the other parties involved were not so nice). During WWII Sweden had to yield to pressure from Germany (like letting its troops pass through Northern Sweden—which those troops regretted doing) but in general it remained neutral because of its usefulness (like the iron ore and products from it) that would be lost in case of occupation. The current war made Sweden reconsider their position and it has finally applied for NATO membership.

And now for another NATO applicant, Finland. It has been suffering from the same problem as Ukraine—bordering with russia. In the first half of XX century it had been constantly struggling to keep its territory and sovereignty from Soviet Union (and the League of Nations proved out to be as useful as UN now, only Sweden and Norway helped it at that time plus some political manoeuvring). That’s why after 1945 it remained neutral but the recent events proved that if you border with russia and you’re not large enough then russia will try to occupy you. So Finland reconsidered its status as well.

Temporarily Occupied West Taiwan (or China for short) is a country that declares itself to be neutral while it semi-openly supports russia (and does not do that in the open because of the fear of sanctions). To which russia repays with its usual ingratitude: just three days after Xi Jinping visited it and had his roadmap for peace accepted there there’s a claim that they’ll go against it by threatening the world with their nukes and nuclear proliferation. This is a poster case of neutrality used as an excuse to do whatever they want since they’re not restricted by some political alliance.

And finally there’s a country that conveniently forgets about its treaties and alliances and proclaims itself neutral to do business with sanctioned countries. Of course I’m talking about Hungary. It’s the country that constantly blocks EU and NATO decisions either because it was paid for that (that’s why the amount of EU sanctions against russian oligarchs and entities is much lower than it should be) or because they want to have a bargaining chip (EU sanctions and other unanimous decisions again and blocking NATO membership for Finland, Sweden and Ukraine are good examples of that). And when I said they forget about previous treaties at their convenience I meant their claims about increasing trade with Iran (despite EU sanctions) or not honouring the indictments from the International Criminal Court because the (signed and ratified) Rome Statute “is not integrated into our legal system”. I believe somebody should help them become truly neutral by kicking them out from both EU and NATO. In the recent news though it’s reported that russia has added them to their list of unfriendly countries. Looks like there’s a common pattern in dealing with russia.

I probably should’ve mentioned Austria here as it was made a neutral country after 1945 but considering how it turned into serving russian interests I don’t see it showing any new aspects of “neutrality” and thus contributing to the discussion.

In conclusion I want to say that there are three different kinds of neutrality that different countries (organisations, people) often mix and pass for another kind: “don’t touch me” neutrality, “I can do whatever I want” neutrality and “you can’t make me do it” neutrality. The first kind is essentially a country staying aside and remaining not involved in any wars so that other countries do not have a reason to invade it either; sadly this works well only for countries with good defence (and not for Ukraine). The second kind is when you claim to be neutral in order not to have any restrictions on dealing with all other possible parties (it works only so well as you can withstand sanctions and pressure i.e. China has better chances doing that than Switzerland). The third kind is complementary to the second kind and the same reasoning applies.

So next time you hear claims about somebody or something staying neutral and not wanting to leave anybody or anything behind, ask yourself about the real goal of that neutrality (hint: there are dirty money involved quite often in this case).