Bink-b: Encoder

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.

11 Responses to “Bink-b: Encoder”

  1. Paul says:

    So you did bink-b decoder? How so?

  2. Kostya says:

    I don’t understand the question.

    If you mean decoder then it was the usual way—looked at the binary specification, wrote a patch. It was not perfect so the work was finished by Peter Ross (IIRC it was related to the motion compensation which is performed on partially updated frame). That is mentioned in;a=commit;h=e00f41d5742b3a0dc1877b030f4f6f58c19b7bbd

    If you meant encoder then I wrote what for (I still have good memories of HoMM 3 after all and it was an interesting task too) and how it was done (it’s trivial and you have the source to look up the details).

    And if you meant can it really encode BIKb videos then I’d say the output works fine with libavcodec decoder and the guy who asked for this encoder says it works for him too.

  3. Peter says:

    This is cool, because there was never a public bink-b decoder.

  4. Peter says:

    *encoder (these words are too similar)

  5. Kostya says:

    I made such mistake countless times too. And the only advantage of my current encoder that it’s public (at least it’s not in high demand like ProRes back in the day).

  6. Marcus says:

    Hey Kostya, kinda off topic, but I’m wondering how AVCodec/NihAV manage registering all of the available codecs?

    Do you use a callback? is there a global array hidden somewhere?

  7. Kostya says:

    IIRC libavcodec has a single list of codec that is filled once.

    NihAV has NIHed approach of course: there’s a “registered codecs” (or demuxers) entity that contains a list of corresponding info structures used later to instantiate decoder/demuxer. And each crate has an internal array of all codecs it can offer (which is filled depending on what codecs are enabled in that crate) plus a public function that adds them to the registered list with name like duck_register_all_codecs(). There’s also nihav-allstuff crate that wraps all known functions for registering de{coders,muxers} into two functions.

    So if you want to use a decoder you do it like this:

     let mut registry = RegisteredDecoders::new();
     nihav_register_all_codecs(&mut registry);
     let mut decoder = registry.find_decoder("bink").unwrap();

    This way you can control which codecs are registered, you can even add your own decoders without having to modify the library and the crate tests can work with crate-specific set of decoders and common code without an additional hassle.

  8. somero says:

    Please! Have you ever made or may be still planning to make an ENcoder capable to create KB2j-files? Or maybe you know where I can get it (for non-commercial usage of course)?

  9. Kostya says:

    For multitude of reasons—no.

    First of all, I still have to figure out the details to get proper reconstruction of KB2j files.

    Second, it’s a way more complex codec than the very first version.

    Third, as far as I know RAD ships the encoder to its customers and only to them (they are not obliged to release the decoder for free but they still do). So you cannot get the official encoder and I’d not write one even if I could for both moral and legal reasons.

  10. somero says:

    Ok. Thanx for you answer.
    May you share your current knowing of KB2j-files (structure, frame signatures)?
    I want just SLIGHTLY modify ONE specific file.
    And encoder is needed only for this. I’d be glad to give someone my decoded-by-oficial-RADtools-and-modifyed-in-VirtualDub AVI-file to encode it in Bink2(KB2j), but don’t know whom to ask.
    P.P.S. Desired modification is a simple duplicating a frame (keyframe or 1st or 2nd or 3rd after it) during some time, and replacing by this sequence the original sequence in file. That’s all. Can you help me? Please.

  11. Kostya says:

    Well, that depends on how lucky you are with the file. I’ve checked and Bink2 have varying number of keyframes. Some can have just one, another can have much more and that depends on scene change as they’re not forced at equal intervals.

    So if you’re lucky and that’s really a keyframe (so you don’t have to re-encode it) you can disassemble stream into frames (the container format is documented at, replace video frame data and reassemble again. Encoding a dummy repeat frame is way trickier.