So, holy everyone. My name is Tibur Afayak. This is an honor to be here for the second
time as a speaker and for them. I'm here to share with you some more innovations in H264
and video decoding in general. A bit about me first, I'm a PhD, I have a PhD in a human
computer interaction and software engineering. Also, background in algorithmics and
competitive programming. I worked on the architectures of graphical user interfaces in
the past. I do a lot of code golfing on my spare time. I'm really passionate about
software architectures and simplifying things in general. So, the base of this talk is my
work that has been going on for 10 years. On the edge to 64, which I will call edge in this
talk. This is decoder for AVC, that supports progressive high and MVC 3D profiles. In
bold, I'm displaying things that were added last year. So, I've worked on SSH2 and ARM64 supports,
which are now complete. They won't evolve. It's just like it's fully optimized for them.
It's supposed to be in those and Linux, but at the moment, it needs CI, continuously integration
because it keeps breaking when I add things on my Mac. So, I need to work on that. Multi-threading
was also implemented. It was super hard. It's still unsatisfactory at the moment, because
it's not really my priority. I just added so that I could see how the API would change because
of multi-threading, but it would change, of course. It will improve. With multi-view support,
now we have a funpag. Hopefully, I will actually add it this year. That's a mood. So,
this is the right time to add it into a funpag. Okay, first, some benchmarks. So, I did
this benchmark last week. It's currently about 10% faster than a funpag. Both on Intel
and ARM chips on my Raspberry. I just bought a Raspberry because it's cheaper. The code size
is actually what's important. It's four times lighter than all of the state of the art.
And the last year, it was a three times code gap. Now, it's a four times code gap, because
I added now ARM support from other decoders. And the binary size includes all the X86 micro
levels, macro architectural levels, and the debug. So, that's why it's two times lighter,
only, but it becomes six times lighter if you remove all this and compile it natively for
your chip.
So, no, thank you for your attention. This was from last year. So, last year, I actually presented
nine techniques, which I encourage you to watch if you haven't already. Overall, I've been
really satisfied with them from last year. Except for one, which is the use of global
register rivals for the context pointer. It's required patching all of the function definitions
and calls with a macro. But the benefit vanished over the years, probably due to higher
register pressure. So, today I'm going to present a five new techniques, more techniques. And
first of all, a question, who among you worked already on video or audio codecs, just to
know, okay, that's a third of the room. This talk will be much, we've talked much to people
who have worked on codecs, but it might also also people who worked on multi architecture
Cindi programming. Let's go first to an introduction on AVC. So, AVC is a video format that
segments your image into 16 by 16 blocks called macro blocks, that it gives you, that it gives
to you in zigzag order. So, in a framescan order, and then each macro block is further segmented
into eight or four blocks. And your code base is going to be split roughly into six parts,
which I won't enable it here, but which you can get for reference. Let's go for the first.
So, the first technique, I'm sharing these techniques here as I think they are interesting to
know, and also that they are different than the usual things you will see in code bases on our codecs.
So, that's why I'm sharing them here. The first thing is piston bitstream reader. In AVC,
you will usually get a sequence of bytes from the memory. And you want to extract a number of bits
each time from the byte stream that are going to be your symbols that you are going to fetch,
one by one. And the spec says that you always start from the most significant bit inside each byte
to the 2DSD. So, the multi byte order will be big engine. So, you always have to convert your
little engine words to big engine. Then the most common codes that are found in AVC are called
exponential gum codes. These codes and code the size of the code in the number of zeros.
For example, the first one is here. The size of the code in the number of zeros. And then you have
the code itself in bits plus one. So, the first one is going to be 14. Then if you still have
always exponential gum codes, it's going to be 144. Then 85. With exponential gum code,
the maximum bit length of any exponential gum codes code is going to be 63 bits that matters
for our bitstream reader. And the maximum number of zeros that you may have is 31. And what I
describe as a bitstream reader essentially boils down to two functions. One that shows you
shows you the next bits that are in your bitstream that you need to consume. And one that allows you
to consume the bits that you the number of bits you want to consume. So, or to discard them.
So, that you may move on to the next bits. Now for the technique itself. I'm going to give you
a quick overview of some approaches you may try or have tried. They are not complete,
but they are meant that are just what I could enumerate. For each approach, I will give the number
of bits that you get when you show bits. That is the working number of bits that you have access to.
And the number of reads and writes each time you call the function show bits. So, basically the
number of reads per code read. The first series of techniques use direct reads to memory either
an aligned or aligned. They incur always a big engine conversion. And they are branchless. So,
they are branchless in in in the sense that every show bits doesn't incur a test. It just updates
the memory pointer. So, the variables you have to date there are the byte pointer, the byte
pointer to memory. And the shift a bit shift to actually realign the value in a bit position.
The problem here is that we have a read dependency that is you have to first fetch your
pointer then to read from that pointer. And you have a direct memory dependency between two reads,
which is awful on every CPU. The second series of techniques are going to be single cache.
So, you have a cache where you store your bits and that you refill sometimes when you don't have
any enough bits. You have to maintain two variables, one for the cache and one for the bit shift
to count the number of bits that are available in your cache or remain. It introduces a
refill test each time you you call your show function. And the bits depend on the refill size.
So, it really depends on the implementation. And you also have a variant that updates the cache
itself each time you show, which has a shorter dependency. So, it trades a right for shorter dependency
and that's usually a good thing. And this is the approach the last approach the last variant is used
in FFNPEG and in H264 FFNPEG and in David the 81 decoder. The last series used two cache, two
hashes, wider cache and trade a slower shift that is a double shift for more rights and and more
rights to have a bigger available number of bits. And my design is going to be a double cache
without a shift count and so I replace the shift count with a set bit at the end of the cache
to mark the end of the bits available. So, it's roughly equivalent to the one that FFNPEG and
David use but with a bigger number of bits however you get a slower shift. So, it's a trade
it's not going to be perfect. The additional design choices that you may have are whether you
refill before or after a show showing bits and if you in line or not your show bits. So, to describe
this technique, let's say you have your two caches. I set them as 32 bits because otherwise it's
too large to display. Let's say we have bits. In bold we have the in black bowl we have the bits
they actually bit from the by the by the stream and in the red one is the set bit. When showing bits
everything is already in the most in the MSB cache. So, we just return this variable. Then to
discard the bits you actually shift both caches to the down and you do so on and on until the
second cache is 0. So, to test for refill you actually test that the second cache is 0. If it is
then it's easy. You just mark the position of the piston bit which I call piston bit. You remove
it. You call your refill function insert the bits inside both caches shifted and then you
re-insert the piston bit. The training bit is essentially a piston that pushes the bits to be
consumed which is why I call it piston bit. It might already exist this technique. I haven't seen
it anywhere in any other code base but I'm not inventing things. I just rediscovering things that
probably already exist. Note that the refills here are reduced size now. So, here each refill is
going to be wide. It's going to be either 32 bits on 32 bit machines or 64 bits on 64 bit machines.
And note also that the refill test is cheap. It's just testing for 0. So, you don't need to compute
the number of remaining bits with the counterling 0 which is good. The second technique goes
as to that is now that we have wide refills we can talk about unescaping. Actually ABC
make contain escape sequences which are 0, 0, 3. This sequence must be trimmed every time
you parse by removing the byte 3 before parsing. It prevents sequences 0, 0, 0, 0 and 0, 0, 1
to appear anywhere inside the sequence because they are commonly used as millimeters in transport streams.
Usually what they call this do is that they scan beforehand and make an unescaping
if the buffer contains escape sequences. But now with wide refills,
CD becomes viable because we have 8 bytes to escape. So, we can escape these 8 bytes in
parallel all at once. And since these are wide we can actually unescaping them on the fly.
We don't need to actually manage a buffer or store anything beforehand or even scan the
stream beforehand. We just can escape these bytes on the fly. And since this is a good example
of an algorithm that we call first matching condition in CD, I'm going to detail it here
because I think it's like classical algorithm that anybody has to know and that's used a lot
in the whole code base. So, first matching condition.
The process takes a memory pointer as input, your byte pointer, byte stream pointer,
and I'll put the 64-bit value in the end. I've put it in the non-gray is the 64-bit value
that you want to extract in the end. What you would do is first load 16 bytes out of memory,
two bytes ahead of the pointer because the two bytes before make contain the start of an escape
sequence that algorithm is going to make your first byte being escaped. It's possible.
If we get too close to the end of the buffer, we actually read up to an aligned boundary rather than
up to the end itself because there is a very unlikely case of a tiny buffer where reading 16 bytes
before the end of the buffer could make you read before the, could make you cross a page
boundary and trigger a secult. So, reading up to an aligned boundary avoids that risk because
pages always have a bigger alignment so you're sure you're not going to go into a secult.
So, once we have our vector, we compare it to 0 and 3 to make mask masks of the positions of 0s
and 3s in the, in the vector, then we combine them, shift and combine them to form a byte mask
of the positions where we are going to delete the number 3, the byte 3.
We convert that mask into a bit mask using a move mask on Intel and the narrowing right shift on
arm that was published two or three years ago by Google engineers. I encourage you to google that
if you're interested, which is faster than the equivalent move mask and it's important because
here this code is actually critical in the code. Once you have your bit mask, you would iterate
on set bits masking only the first 8 bits because these are the bytes we're going to extract
we're going to want to extract and for each position we're going to shuffle the vector
to remove the byte and this is a shuffle on a mask that is selected by an array basically.
And as you can see the first shuffle made the another 3 appear as in the bit mask so we are also
and in the end, once our bit mask is 0, we have our vector, we just, we just, we just,
is it this? Nope, yeah. We just extract this value and give it to the reflection function.
Is it good to form? Third technique. Okay, this is probably what you will be most interested in.
It is the multi-actualist in the programming. What I mean is programming in C for both
SSE, Intel, SSE and ARM, Neon. As a reminder, Edge uses both Vector, GCC Vector,
its extensions in addition to Vector, Inferencing. The reason for that is basically Vector extensions
replace all of the arithmetic instructions and element accesses with just array accesses and
plus operators from C. So it helps your code being more compact. I use the type S, I use the
unions for Vector, Kable, arrays and I shortened, from last year I shortened all of the
Intel intrinsic into aliases because they are unreadable and hard to type on, you know, just
typing the, and the underscore is annoying. So I replaced all of them and as a bonus,
it facilitated the transition to ARM because I already had aliases to all of the macros,
to all of the intrinsic. Who among you is a second last question already worked with ARM,
ARM code, just know. Okay, quite not many, but still. So a bit, one more disclaimer is here,
I make a difference between multi-architecture and portable. This is not portable code.
I'm here, I'm working on multi-architecture code that is code that is going to yield the best
possible code for both Intel and ARM. It is not going to compile for risk 5 or for other
architectures, not now. My goal is only to have the best possible code and restricting the number of
CPUs helps you have actually better performance on these architectures. Last year I actually
talked against using shuffle Vector, convective vector element wise and reduce
built-ins from clong, and I did not really explain why. So now I actually describe it a bit more.
I think these extensions are designed so that they work on most of the most number of architectures
possible. But behind the scene, they actually make it worth as a bigger number of instructions,
and that's not what I want. I want to have the best possible code. So usually I try to avoid them
because I'm not always sure that they're going to translate it to one instruction.
So their philosophy is more as portable and my code is designed to be multi-architecture. It's
kind of a different philosophy. So here I'm going to describe the workflow, how I did to add
neon support on top code, SSE, intrinsic. I think this workflow is reproducible and I'm going to describe
it this way. So the first thing you would do is to write unit tests. That's essential. You don't
want to debug afterwards. You want to have something that works right when you when you code it
that is correct. So you want to write unit tests using your existing code. So you create test
cases. You run your existing code on these test cases. Pick the results and serialize these results
so that you can match your future code against these tests. Then that's not avoidable. You have
to write the best possible neon code in intrinsic. You don't write something that is in between.
You have to write the best possible code in assembly. You can't go around that. Then once you
have your best code in neon and SSE, then you can work into actually merging the codes together
to make your code a shorter. So what I do usually is I will find aliases whenever I find otherwise
I fall back to if else blocks, pre-processor blocks and that accounts for about 20% of the
signal code. Which is not that much. The code base is still quite small. If you're interested,
you can look inside the code base at five finds internally in trying to residual and debug.
Now let's go through what went right and what went wrong. The good aliases for instructions
that essentially is the same in ARM and Intel. There are instructions that are closed,
but not exactly the same. And for these, I created semantic variations. That is, I created
functions, like I duplicate the function with semantic variations. For example, typically
example is the blend. In SSE, you have a blend instruction that operates on the most significant
bit of a vector to select based on both on the two other vectors. On ARM, it's called bit
select. It's based on the mask, not the most significant bit. So I created actually two functions,
if else based on the most significant bit or if else based on mask. Same goes for the shuffle instructions
because the semantics are very different. On ARM, the shuffle instruction, if you give it a negative
or an out of bounds, if you give it an out of bound positive value, it will return zero.
If you give it an out of bound value that is positive, it will do a, it will end. So it will
give you a value value not zero. Polyfields. For key ARM instructions that are absent in SSE,
I created Polyfields. So for example, the duplicate of the broadcast in Intel is going to be
set plus shuffle. Polyfields the other way around. So missing SSE instructions are going to be
compiled into set of instructions for ARM. And I created specialize the helper functions for code
that is very redundant. For example, loading a four form matrix. Basically, I have a function
for that, or for the multiply add shift write and a pack to eight, which is very common.
Now what went wrong? GCC and Clung do not model multiple latency instructions. So basically,
what I understand is that in GCC and Clung for what it have tested so far, any instruction
is going to be modeled as having a single latency, but ARM has instructions that have several
multiple latency in SSE. What I mean is for example, you have an instruction that is
MLA is multiply accumulate. It's going to be a multiplication and then an addition to another vector.
The multiplication is going to be like four cycles. The addition is going to be one cycle,
but GCC and Clung will think it's four cycles overall, but actually inside the macro code,
it's modeled as two separate instructions somehow. So it has two latencies, and the compiler
is not understanding that. So that's actually a big, big, big problem, and that probably
be accounts for the fact that the code is not so fast, so much faster than FFA in practice.
Other problem, Clung splits a accumulating intrinsic instead of merely generating them.
Boo, Clung. Boo. It thinks it's clever, so it's just splitting my multiply accumulate,
and then I have to work afterwards to make it generate multiply accumulate the way I want.
Boo. Now, running intrinsic in ARM, they return to 64-bit vectors, whereas the instructions
actually return to wide vectors. So the upper part is going to be zero, but the API doesn't show
it that. So you can't expect that, and that's a problem. The across vector intrinsic, for example,
add all the elements in a vector, return to int, whereas the instructions actually return to
wide vector. So that's huge problem. I usually just ignore that. And between ARM and Intel,
the instructions for shifting by element and multiplying by element are widely incompatible,
so that will lead us to the ugly. The workarounds. Okay, first one is to use inline SM,
in a macro, of course, to force the use of multiply of MLA, or to make a vector return to a vector
that is proper. Another one, this one is ugly, but I prefer this, is to rely on
that code elimination from the compiler to ensure that one of the instructions is not going to
be compiled actually. So I said that the variable shift is different between, okay,
the variable shift is different between Intel and ARM. So I implement on the bottom different
shift instructions. And on the top, the computed variable shift is different between the two,
but it's in common code. And whenever I go here, this makes WD64 going to be used, and the other
one is going to be unused. The compiler detects that and removes that, removes that altogether.
It doesn't, I disable the unused warning. Come on, I mean, we know what we're doing here. We're
grown-ups. Address calculation. This one is annoying. GCC loan do not model multiple agencies.
So they won't generate post-index for reads and writes that are going to be spaced by less than a few
cycles apart. So in practice that tend to generate a lot of pointer arithmetic, where you don't
want that. That's a problem. Because binary size is crucial, especially if you want to fit that
in L1 cache and L1 cache is scarce. My solution is to compute a set of variables beforehand,
and then reach all of the needed addresses in gray, like gray, with the only offset addressing
from Intel and ARM. And since Intel and ARM addressing modes differ, we are going to
track them with macros. Intel is amazing on that part, I must admit it's real cool. Intel can
add a register times 1, 2, 4, and 8, and an immediate. So in yellow, it makes all of the addresses
reachable from one single address plus addressing, plus offset addressing. So with five variables,
with just five pre-computated variables, the three pointers plus two strides, we can reach
all of the necessary addresses, which is a trick from the fifth and peg, of course. In ARM, it's harder.
ARM only supports only immediate or offset from a register, not both. And worse, some instructions
from like load with duplication cannot offset. So we cannot offset without post-post index,
but we can't use that, so we don't have access to that. So sometimes we have to actually offset
the pointers one by two the left. So here we have like 10 or so, I think 14, 14 variables,
but ARM has 32 registers, so that's fine, of course. So I'm not really completely satisfied with that,
but at least macrowing of the addresses, keeps track of all the pointer uses in the code,
so I may change that in the future. Forst technique, I'm quite okay late, but that's really fine.
This is an architectural pattern. It's called the structure of array pattern.
You usually see as array of structures or structures of our structure of array. This is an architectural
pattern that is used in optimization to vectorize the operations on arrays of structures.
So what you do is to convert arrays of structures into individual arrays for each of the fields.
In the decoder, in edge, it's used for frames lists, for frame buffers, and the list of tasks,
so to formality threading. What you do typically is you explode your arrays into independent arrays.
And in the code, it makes you replace loops on structures with vector operations.
That's going to make your code both shorter and more compact, shorter in binary and also in code.
It's going to make it more compact. And I've put three examples here to find an anti-frame buffer out of
the mask of reference slides that I showed earlier. Reference flags out to flags. These are 32 bit masks.
To find an anti-frame buffer, you just count the training zeros on the combination of reference
flags and out to flags. So find me a frame that is not a reference and not waiting to be output.
Then I combine them and then I count leading zeros to find the first anti-frame buffer.
To count the number of pending frames, the frame that I have, the output flag bit set,
I just do a per count. That's one liner awesome. And then to loop through reference frames,
it's a classical looping through set bits.
This pattern has advantages that is, it makes you have less allocation and thus less
memory fragmentation of your inventory, less my locks and so on. But it also gives you smaller code
and binary overall. So that's much easier, especially when you want to work on your frame
buffer and all these operations, which then when you work on big code, especially in this part
on the frame buffer management, you want to have things that are short because it's usually very
hard to work on. The problem with that is that the code is a bit less intuitive. You have to know
binary operations and it leads to catch pollution and fall sharing in multi-threading. So you have to
be careful in how you manage this. And five minutes left, that's perfect for the last technique.
The last technique here is some code from a fempegg, about error checking. So when you read
symbols from memory, from your by-stream, from your by-stream, these are the first two function
calls. You're going to call a function, get you a new column, the 31, then you get your value,
and then you're going to test your value against conditions and then fail. Typically, error
checking works with go-to's or return. You get your value, test whether it's right or wrong,
and then fail with either go-to return. But the problem is that it needs code to bubble up the errors
from if your code is in sub-functions. It makes many exit paths that you may want to test if you
want your code to be robust. And in the critical code, it acts as noise for the branch predictor,
because these tests are going to be just passing tests most of the time. So better than having
them passing all the time is not having them all together. In general, error reporting is a
graze on. We report errors where they appear in the code, but we never really know how to make
them useful, how to make useful messages. So usually they are very factual, like I showed earlier,
legal bit data value, that's very factual. But here we can actually separate the different users
that are going to be interested in our code. First there is the viewers, the people who actually
review your stream, they just don't care about error messages, they don't want to see them,
you know your code, your decoder actually works or not, if it doesn't work, well reboot, restart,
or go to another player. Media players are going to be interested if you're misusing their
API. Otherwise, they don't really care about the message beneath, because it's not going to change
that your stream is not going to work anyway. And the code and code developers, people who
develop encoders and test their by stream with your decoder are going to be interested in everything,
of course. Here I make a distinction to simplify things between a validator and a passer.
A validator is going to check if a stream is valid, otherwise it's going to help you fix the
stream. And the passer is going to try to decode the stream, if it's valid, if it's not valid,
runaway crying and that's fine. But here if we drop the responsibility to validate the stream
and if we stick only to encoder users or media players, we can relax the error reporting
to actually say we're not going to be interested in where we find errors, but if we find an error.
And on top of that fortunately, check some of the stream. Also, ensure we actually rarely see
a runaway stream. I hope I'm right, please correct me if I'm wrong. I'm not really a
demoxer developer. And a good thing with with AVC is the variable variable and
codes are very sensitive to disynchronization. That is the first line we actually had three
exponential common codes. And the second line, if we discard the first, just one bit, if we
just discard one one bit or if it turns it into a one, it's going to disynchronize so
move the reader pointer by wild amount. So in the end, any error that appears in the stream,
you're going to see it at the end of the stream by an offset in the read pointer. So what I do
is for each input, I just clomp the values to the expected range. And I don't care anymore.
I just clomp the value so that actually the rest of the code is going to be robust because I know
that the value is still valid. And at the end, I just for I check for this synchronization of the
bit stream pointer. And these are actually the values that I should expect on MSBLS and LSB.
It has to be one on top, which is the RBSP training bit in AVC. If you know the spec.
The impact on that is that there are no branches inside the parsing code anymore, except for refill.
But the refill is inside the function so it's not going to act as a noise for the branch predictor.
We check for unsupported stuff also once for errors and unsported stuff once at the end of the process.
There are less exit paths to test and to care about. So it may make the code more robust to errors.
And good thing inside the slides parsing code is that the return values are not used anymore for errors.
So you can use them to return something else, which is always good.
Now the roadmap for release, these are the things that I have to work this year. Hopefully MVC
support for H264 is going to be added this year. I will have one more content for one more presentation
next year. It will be hopefully about optimizing Quebec, Quebec, which is the arithmetic decoder.
I have lots on that. It's going to be awesome and optimization for caches and profiling.
With this, I would like to thank you for your attention. Here are some key resources that you may
want to read if you're interested in working on that. And I'm also looking for jobs, so please
reach me by mail if you want. If you have a job. Thank you.
Questions?
I got it. It was too intense.
Yes?
When you detect errors in the stream, you would just hope for the best.
When I detect code in the non-destructive questions.
Yes. So the question is, when I detect errors in the stream, do I do nothing or do I do I continue
do I continue decoding? So there are two things here. First is to know where the weather is
in the stream. And second thing is falling back to clean image. So if we
when we pass, we don't detect errors. We only detect errors in the end. So for example, if we pass a
header, the header might eventually decoding to something that is just not valid, but we don't care,
because we then check if there is an error. And then we know that the pass that the header that we
decoded is wrong. And the second thing, I don't know if answer your question for that.
And the second thing is that for frames, if in the end, I finish decoding in frame and I
realize that it went wrong. I actually go back to the entire frame, compute a probability for each
block, macro block, that it contained the error. And then I reconstruct the pixels based on that
probability. So I actually do a weighing between the predicted, a predicted for back and the thing
that was decoding. And hopefully, if anyone from a 5MP is here, I would really like to have an API
that allows me to call a 5MP. I say, these pixels are wrong. Please replace them. I don't know if
there is, I hopefully. That's it. Yeah, a concealment. Is there an API to actually tap into this
concealment from outside? Okay. Yeah. I can do that from the codec itself, but the thing that I don't
want is, so the question is, no, is it a question? That concealment is usually done from the codec
itself. My problem is that good concealment, usually you look at the state of the art and you
want to implement things like with image processing and complex image processing. I'm not going
to want to implement that, especially since the state of the art is going to evolve. So I would
really like to have something that is DFFM packaging that I can tap into to do an error concealment.
I don't know if I'm clear. I believe that the permissive of a big issue is to use a better
default color for the frames that are empty. So when you corrupt the reference, you can hear it out
as such, and you're right. Yeah. And you're not that, it was the less costly and
visually affected. Yeah. But I know it from hardware hardware tells you which macro
block art parameters and amount of corruption, and you get to decide if you copy a reference frame
over that block, or you can do that. Okay, that's perfect. Thank you for saying that because
I'm actually doing the same thing also. Yeah. Yeah.
So as soon as those those starts all the way to the end when you start a point. For example,
when you allocate a frame, when you start playing a frame, you take a look at the references.
And the reference reference goes not exist. You'll make one up and note that's how the
And that does.
It usually takes the blind color to use as a missing reference.
And it's only because it does the best critical.
So it's very interlead with a way to go in.
We have tried in the past actually recently over the past year
to export much of the interaction
and our Americans people call it the introation.
But the look that's at the end.
I think it's so built and chill.
And so it's the fundamental defaulting that it's part of the track.
Yeah, and I do the same actually.
And that's because actually looked at the FFM pack
when I saw Scott.
Let's do the same.
Well, if you really think you can do a better job
and you just want to replace individual pixels.
You just do the filter.
Yeah.
Any other questions?
We don't have something.
Perfect.
Thank you.