Okay, cool. So, hi, everyone. I'm Tibu. It's an honor to be here for the third year in
Phas Dam. And this is going to be a technical talk on sharing interest in tips on codec
development. So, the basis of this work is my work that has been going on for 12 years already
on Edge 264, which I will call Edge here. It's an AVC video decoder with a permissive license.
And to me, it has been research on improving performance and size of the decoder by trying
unusual tricks. And thanks to that, it has been come about 15% faster and 4 times lighter than the
state of the art, which is a good achievement, I think. During the past year, I worked towards
release with new things in bold. And the major thing is Netflix joined to support this work. So,
huge thanks to them. It has been a huge boost in motivation. And now I'm steadily steadily
progressing towards release. Without further introduction, let's go over a quick overview of AVC.
So, AVC is the 20 years old codec. And the basic structure is 6 code modules and your data comes
as an coded bit stream goes out as frames. And we're going to focus on the the two first blocks
that is headers and slices parsing the parsing side of the codec. And I'm going to present two
main things, the use of YAML as a format for logging output and the optimization of the
Quebec arithmetic and coder. This is going to be technical. Okay, first YAML, YAML, come on please.
YAML is a data serialization format that is a standard way to convert a language object
in your program in your program into text and back. And in retrospect, that has been one of my best
design choices in the past few years. And I will describe here the choice and what it enabled
in my code base. Okay, now to the meet. Edge in edge I log everything I parse. So, everything
every symbol that I get from the bit stream I log it. And since AVC or H364 is a sequence of units,
my log is going to be an array of objects of YAML objects. And here is an example of the log
output of a sequence parameter set. With YAML, I get these, I get readability, thanks to
having a slim syntax, thanks to syntax coloring in the editor, and thanks to the availability of
comments, which for example Jason doesn't have. So, I can add extra information like the fact
that seven corresponds to a sequence parameter set or that a line was actually inferred, not present
in the bit stream, but inferred by other sequences. I get also compactness by the use of a recursive
format. If you compare that to CSV, that would make many more lines. So, here I can actually
put more symbols into a single line and thanks to the availability of inline structures that YAML
allows. And I also get scriptability by design that is the ability to load your YAML directly
into a programming language without having to parse it before. Okay, with that. So, once you have
the ability to easily feed the log to a program, the next step is re-encoding.
That is converting our YAML back to the original video. This is a good way to check that our
logging is complete. That is that the log represents the whole video and that you're not missing any output.
And I'm going to share three key tips that I think will help you if you want to go the same route.
The first is to use Python or a high level English and I'm serious with that. Python is
excellent for prototyping algorithm and I have been genuinely surprised that it hasn't been used
more to design encoders, especially in initial encoders when you care more about compression than
performance. The second tip is to output context three units. That is, units usually depend on
the previous symbols that you get in other units. Here, you include everything into a single unit
so that the re-encoding becomes easier. For example, here, instead of opening just a frame number,
I output the frame number and the number of bits that were used to encode the data,
or to decode the data so that when re-encoding, I just need to output for bits and not look at
previous units to know how many bits I used to encode this. At this point, if I compare
this script gen ABC with a library that does about the same, I converted from 9,000 lines of code
in C to 500 lines of code in Python. That's almost a 20 times reduction. So pretty good and especially
it's better for maintenance because this script is just a side thing. I won't go back to that.
And the last key tip is that Python has actually built in support for bit buffers.
Integer in Python are infinite so basically you can use them as bit buffers by using a single
set bit and pushing the set bit when you insert new values into the buffer.
I'm putting these operations, these five key operations as reference if you need to use them in
your projects and you may come back to the PDF later of the presentation if you want.
Okay, next step. Once we have the ability to encode, to re-encode a YAML back to a video,
we can create custom test bit strings to stress the decoder. My goal here is to catch up after
FFMPEG and OpenH364 over decades of field testing and field availability. Edge is quite recent
and I don't have the same feedback from a field. And my key tip here has been to search for
shell clauses in the spec that like a thousand or so. For example here, a sequence parameter
set with that particular value of sequence parameter set ID should be shall be available to the
decoding process prior to its activation. That means that whenever you get a sequence,
whenever you reference a sequence parameter set, it has to exist before you reference it.
So for testing, it means that I should create a bit string that contains a unit referencing a unit
that does not exist. Okay, that's a tricky thing. But basically I read the spec, I read the
shell clauses and I create, I imagine bit strings that should fail. And then I convert that into a
YAML and into a test bit string. The good thing with these custom tests is that they can be
included into public repositories that my own repository since I created them. So I own them.
And also since these bit strings are much smaller than conformance bit strings,
they are much faster to run as tests. So the automated tests are much faster and I don't need
to include the conformance bit strings into the public repository.
The last key point is data analysis. Thanks to YAML, I can write scripts in Python again
to generate visualizations. And this is an ongoing work to design multi-threaded scheduler.
The code samples are available in the repository to reference receipt. I'm not going to go with them.
Okay, midway. Now Quebec. First question, who among you is familiar or has heard about Quebec?
I guess not being able. Okay. Okay. Quebec is a layer of compression on H264 ADC that takes the input
bit stream and a context and yields bits one by one. You ask it. I want one bit of a motion vector
or I want one bit of an IDCT coefficient and it gives you this bit. It's a very low-level
compression thing. This is a screenshot of edge showing how bad it is on performance. It's about
half of the performance goes just to Quebec. It's almost impossible to vectorize the serial process
love it. And it has been reused in HVC and VVC. So everything that I'm presenting here will
matter to these phones too. Okay, let's first describe a theoretical arithmetic decoder.
A theoretical arithmetic decoder has one state that is a floating point, the offset. It's a
floating point with infinite precision that is loaded from the bit stream. And for each request
of one bit, you would fetch a probability threshold that is given by the symbol you want to decode.
You will compare the offset with this threshold and basically rescale the slice that was selected
into 0 and so basically scale the offset with the range so that it becomes 0 and again.
So here we're in 0 than 1 than 1. So the bit style returned only going to be 0, 1 and 1.
This is a really quick crash course on arithmetic decoding but I encourage you to look at Wikipedia
if you want to learn more. Quebec does the same but with integers, 9 bit integers. The offset
and the range are both on 9 bits. And the rescale happens only when the range has less than 9 bits.
So the Quebec state is on two integers, the offset and the range. The working is the same
when you get the 0 value, you get down but you don't scale up. You only scale up when you need
to have enough precision in the range. Here at the last stage, one range becomes lower than
lower than 9 bits so lower than 256. You scale it up so you multiply range and offset by 2
and take a bit from the bit stream to the offset. That's how we actually reload into the offset.
This is the original algorithm that is implemented in OpenH261 and that explains quite
the lack of performance when you compare it with FFMB.
Now the optimization. If instead you want it to load 10 bits from both offset and range.
So you load 10 bits from offset and the range you shift it up by 1 bit. All the results
would be the same. It would function the same but in the end at the third stage
you would have enough precision in the range so you would not need to rescale. You would not need
to rescale. So that space one renormalization trip to memory and the key tip is here. To do the same
on size T integers or basically machine wide integers and taking here 64 bit machines you would
initially load 64 bits into offset from memory from the bit stream and shift the range by 55 bits.
The extra bits, the extra bits. Then you do your operations and at each renormalization when
range and offset become lower than 9 bits you would refill both with 56 bits or 7 bytes.
This has a advantage that it trades less frequent renormalizations with a new counting of extra bits
and it goes well with extra loads wide loads that I presented last year. Now the wide loads go
well with unifying undefined escaping that I presented last year. For those who followed. The second
trick here that ffmpec doesn't have and I'm really proud of that is to mention is to observe
that range belongs to 256, 511. That means that range is 9th bit is set. So you can use this bit
to count the extra bits and with this it spares the use of an extra variable or an extra
set bit. Second one, second one is awesome but even harder to understand. Okay bypass. In
Quebec bypass is the mode for symbols that Quebec cannot compress basically for which 0 and 1 are
equi probable. In ABC there are always used in loops of many bypass bits because they are used
exclusively for idc t coefficients for long idc t coefficients and for long motion vectors. So
there are both long and very rare. Here we are going to assume that the offset and the range
have enough bits so that we normally to renormalize in between. What we would do is we compare
offset with half the range then output a value. Then we compare offset with one fourth the range
then we are output a value and then we compare offset with one eighth the other range and the
bit sequence that you get is 001. If just to try out we map out all possible values of the offset
the offset that the offset could take. We notice that all bypass results would follow
progression from 0 to 7 left to right. That means to get the same results as many
calls of bypass you could actually just divide the offset by one eighth of the range and doing
this division would yield all three bypass bits instead of having to go through three calls of
get bypass. And the trick is here. In Quebec to get end bypass bits you first ensure that the
offset and the range have both at a more than n extra bits. Then you would shift down the range
by the number of bits you want. You divide the offset by the range. You get n bypass bits and the
remainder of the division is going to be the new offset. Then you feel to return n consumed bits.
For example if the bypass bits were used in a VLC code you would multiply back the end
consumed bit by range at then to the offset and then shift range up by m bits.
OK this trick has no impact in edge. It's just really cool actually because it's really
used in a Vc. The performance is going to be a bit worse for tiny batches because Dave has a
high cost but this technique has a constant cost so it's really good for very complex streams.
However this stream should be way more useful for HVC and VVC that use bypass bits a way more.
I'm on time. Thank you for attention. Now I'm going to be a bit faster working on this
thanks to Netflix and my ETA for releasing about two years I think. Thank you for attention.