Diary of an x264 Developer

Blog moved to multimedia.cx

2008-05-14T18:13:00.000-07:00

This blog has been moved to the multimedia.cx server and can now be found here.

Introducing Photon

2008-05-10T19:58:00.001-07:00

A few days ago I was somewhat bored; no particular good ideas for quick x264 improvements, no good games to play, and most of my finals out of the way. So I decided to make my own codec, called Photon.

The basic goal is to make a very fast MPEG-2-like format with better compression and speed than MPEG-2, but without the complexities of things like interlacing and B-frames. My eventual plans for Photon are a bit more fancy than what I have so far, of course; currently the encoder and decoder are intra-only, for example. And honestly, I'll be shocked if I manage to reach my goals; my main purpose in this is to learn how to write a codec and bitstream format from the ground up and experiment with all sorts of features in the process.

The main philosophy behind Photon is to keep everything as simple as possible; the fewer special cases needed, the better. As such, every macroblock is divided up into 8x8 blocks; 4 for luma and 2 for chroma (the codec uses YV12 colorspace). Every single 8x8 block, luma or chroma, is treated exactly the same with the exact same set of code; the bitstream does not even distinguish them. This makes it possible to have a single loop for decoding all of these blocks. For the transform, the H.264 transform/quant/zigzag process is used.

Preceding the blocks is a 6-bit element, with one bit for each block. For each block, its associated bit in the Coded Block Pattern (CBP) is set to 0 if there's nothing in the block and set to 1 if there is.

For each block with a CBP of 1:

1. A delta-quantizer element. Yes, that's right: each 8x8 block has its own quantizer! This increases the effectiveness of adaptive quantization. The delta-quantizer is done with respect to the same numbered block in the previous macroblock and is coded in unary with one bit for the sign (total bit cost: 1 bit to not code a delta quant, N+1 bits to code a delta quant, where N is the delta).
2. A transform element. Set to 0 if the block uses 4x4dct, set to 1 if the block uses 8x8dct.
3. A 4-bit CBP for the 4 4x4dct blocks, set in the same manner as the macroblock CBP. Omitted in the case of 8x8dct.
4. Residual for the 8x8 block, or for each 4x4 block with a CBP (in raster scan order) as follows:
a. The first coefficient in the block, coded as a signed exponential golomb code.
b. Is this the last coefficient? If so, a 1 is coded and the residual coding ends. Otherwise, a 0 is coded.
c. The run length of 0s until the next coefficient, coded as an unsigned exponential golomb code.
This loop repeats to code the entire block.

The macroblock itself has a 2-to-4-bit header specifying the luma and chroma prediction modes to use, and the frame has a header specifying the frametype and frame quantizer.

... and that's it. That's the whole thing, so far. Yes, the entropy coding is absurdly suboptimal and would benefit dramatically from custom variable-length codes instead of universal codes. Yes, I'm not using an ounce of assembly whatsoever and the encoding and decoding are far slower than they should be (decoding is still realtime for most sane resolutions though). But it works.

For those who want to see my hackneyed, half-copy-pasted-from-x264's-common-library code, the diff so far is here.

Variable length coding and you

2008-05-09T11:51:00.000-07:00

Let's say you want to write a number to a bitstream. The decoder is expecting a number, so it knows exactly what to look for. But how do you format this number?

You could write 16 bits no matter what, putting a max of 65535 on this number. This would also waste tons of bits though; what if the number you're writing here with your encoder is almost always 0, 1, or 2? Writing 16 bits would seem ridiculous, so it only makes sense to use a variable-length code (VLC). But how would the decoder know how *long* the code is? Here's a simple example:

5 -> 101
2 -> 10

Both will look the same to the decoder, since it doesn't know whether the code ends after the first bit, the second, the third, etc. But there's a solution to this problem; a common one lies in the form of exponential Golomb codes. Here's an example:

0 -> 1
2 -> 011
5 -> 00110
8 -> 0001001

The number of zeroes is the number of bits in the code, and a 1 is used to terminate the list of zeroes. This may seem inefficient, but in a sense one has no other choice but to have some sort of coding scheme like this. Of course, exponential golomb codes are only optimal in the case of a specific probability distribution; an optimal variable-length coding system has code lengths chosen based on the probability of each value. This is the primary reason why MPEG-4 Part 2 (Xvid/DivX) is superior to MPEG-2; the VLC tables were much better chosen.

Of course, the ideal system would be to allow custom VLC tables to be put in the header of the video file; its quite trivial to design a twopass encoder to create optimal VLC tables for a given video, or even a given frame. H.264 partially does away with this problem with CABAC; while there would be benefit to including a custom initial CABAC state, the cost of various CABAC modes adapts quickly to the video. Of course, this is not always the case; CABAC still relies on variable-length codes, because it converts numbers to series of binary digits, which are then written into the context-based arithmetic coder (the "binary" part of CABAC). One result of this is that even if one has a B-frame made up entirely of intra blocks, the arithmetic coder won't be able to completely adapt, and each block will still cost more bits; the variable-length coding for the macroblock type is not chosen in such a way that would allow such "complete" adaptation.

Test clips

2008-05-06T17:20:00.000-07:00

Many users have wondered what kind of test clips are used to test x264 during development. In this post, I will attempt to enlighten readers on my personal suite of test clips and why I chose each one.

My first test clip is a roughly 3600-frame-long segment from Pirates of the Carribean: The Curse of the Black Pearl. I often just use the first 500 or so frames of this. The primary reason this test clip was chosen was to serve as an "ordinary" standard-definition video with a reasonable amount of film grain and the same sort of imperfections that most DVD sources have. The clip can be downloaded here.

My second test clip is a section from Elephant's Dream, the free full-CGI short made in Blender and released by the Orange Open Movie Project studio. This sample is useful for a number of reasons: first, it is available in true lossless 1080p, so I can use a completely flawless source as input to the encoder. Second, of course, it is completely free. Finally, it serves as a good example of a CGI source for which to test x264 on. The full lossless original can be found in PNG sequence format here. If I need an extra HD CGI short, I usually use For the Birds or Lifted.

Next, I usually have an anime/cartoon source of some sort. I sometimes use the Flash version of the Azumanga Daioh OP, but this clip is often less useful than one would think; because its Flash, it is completely lossless. Most real anime/cartoon sources are either DVD or TV broadcast and are therefore far less clean than the above clip. Since x264 has to be able to deal with the flaws in its input, I usually use a fansub copy of the Haruhi ED sequence.

My penultimate test clip is from the VC-1 Blu-ray version of "300." This is a serious torture test for any video encoder; the artificial grain in this source is unbelievable and requires a ridiculously high bitrate to maintain at any resolution. This is also one of the main test clips I used in developing my film grain optimization. While I obviously can't upload the whole video nor even a reasonably sized segment of the source, a relatively high quality sample rip can be found here.

My final test clip is the ultimate torture test: a set of 640x480 videos that need over 4 megabits to avoid noticeable visual artifacts. These are lossless FRAPS captures of Touhou Project games, a series of "danmaku" vertical-scrolling shmups with a difficulty ranging from high to completely ridiculous. With this difficulty comes incredibly complex bullet patterns that make can make many video encoders completely choke; it is nearly impossible to effectively compress the sharp-edged bullets enough to reach the target bitrate without completely decimating the backgrounds. I have used these clips for a comparison between x264 and Elecard and a sample video for H.264-in-browser using Flash. I also have a short lossless clip available for those interested.

x264 development: a six month retrospective

2008-05-06T03:21:00.001-07:00

These past 6 months have consisted mostly of bugfixes, vast speed improvements, and the beginning of what will hopefully be a series of psychovisual optimizations.

How can I best describe the speed boost? Numbers would do the best job, I think. All values are my internal development build compared to the current version from 6 months ago. Adaptive quantization is disabled to make the results comparable. CRF is used for all encodes.

Max speed settings (no B-frames, subme 1, analyse none, me dia): 29.5% speed boost
Near-max speed settings (3 B-frames, subme 1, analyse none, me dia): 24.5% speed boost
Medium speed settings: (3 B-frames, subme 5): 18.5% speed boost
Slow speed settings (3 b-frames, subme 6, b-rdo, me umh, ref 4): 35% speed boost
Very slow speed settings (16 b-frames, subme 7, b-rdo, me esa, ref 16, trellis 2, no fast-pskip, partitions all, mixed-refs): 52% speed boost
Lossless: 15% speed boost

Notable new features:

1. Psy-based adaptive quantization, for improving quality in flat areas of the frame by taking bits from more complex areas of the frame.
2. --me tesa, transformed exhaustive search. Converted from a ridiculously slow initial algorithm by me to a highly optimized thresholded solution by Loren Merritt, resulting in an even slower alternative to --me esa.
3. A massive preprocessor-based abstraction layer for assembly, allowing complete abstraction between 32-bit and 64-bit assembly and even automatic handling of everything from stack offsets to macros that permute their arguments and SSE/MMX abstraction. Written from scratch by Loren Merritt and drastically simplifies all assembly development.

Notable speed increases:

1. Altivec implementations of various functions; much faster PowerPC encoding.
2. Cacheline optimization for SAD-based motion search. Also for luma MC.
3. Much faster exhaustive motion search.
4. Lots more SSE2 assembly. And SSSE3 too. And even more SSE2. Oh wait, more...
5. Skipping stuff.
6. Much much faster CABAC encoding.
7. Tons of small optimizations all over x264. Yes, there's lots more of these. And more of these. And even more... wait, there's more here...

Chroma encoding optimizations

2008-05-06T00:53:00.000-07:00

This post revolves around this diff.

The chroma encoding process is an often-neglected one; we focus all too much on the complexities of luma encoding while forgetting the chroma encoding process, which is exactly the same regardless of block type. The 8x8 residual blocks for the two chroma planes (from motion compensation or intra prediction) are DCT'd, quantized, and encoded. However, there are some aspects to chroma encoding that make it subtly different:

1. Like i16x16 blocks, chroma encoding is separated into the DC coefficients of each 4x4 DCT block and the AC coefficients. DC coefficients are "flat" frequencies, that is, a number representing a uniform change over the whole block. AC coefficients are non-flat, and represent a spatial frequency. In most block types, DC coefficients are not treated differently from AC; in chroma and i16x16, they are. In chroma in particular, the 4 DC coefficients (for each of the 4 DCT blocks in a color plane) form a 2x2 array, to which a Hadamard transform is applied, and then the result is quantized. This allows the overall "flat" change in color to be coded separately from any more complex change in color.

2. Chroma blocks are generally very simple and have nearly no residual data. This is part of the reason that 1) is how the H.264 standard implements chroma coding; nearly all the data is probably going to be very simple if it is there at all.

Now, this changes things slightly. First of all, it changes how DCT decimation works; normally, decimate works by picking a DCT block and setting its contents to zero if its contents are sufficiently simple that it would save a lot of bits just to not code it at all (and have a relatively small quality loss relative to the bit savings). For chroma in particular, decimate happens a *lot*, because usually there are nearly no AC coefficients.

But what if, like we often do, we decimate the AC coefficients... but there's DC coefficients left over? We don't decimate these; the visual effect could potentially be large to do so, and the bit savings is small. But we still have to decode the DC-only chroma residual data, that is, perform an inverse DCT, and store the resulting data to represent the decoded frame.

But if we know that there's only a DC coefficient and no AC coefficients, why do an entire iDCT? That would be a waste of time, since having only a DC coefficient literally just means we're adding the same value to every pixel in the block. So I ported the DC-only chroma iDCT from ffh264 and rewrote it to do all 4 4x4 blocks at once, so it can handle an entire 8x8 chroma block in one call. Now, whenever we have a DC-only chroma block, we can skip most of the iDCT process, saving a bit of time. I also cleaned up a lot of the decimate code in the function, speeding things up further. Thanks a lot to Loren for help with the assembly on this one.

Film grain optimization

2008-05-03T02:30:00.000-07:00

Optimizing an encoder for film grain is a tough problem. For one, film grain is, by definition, basically uncorrelated between frames; that is, film grain from a previous frame is totally useless in encoding the current frame's film grain (at least it would seem!). This would suggest that intra blocks are necessary for encoding film grain, which is what generally results. Yet this encounters another problem: film grain is made up of a whole slew of spacial frequencies, many of which cannot be represented at the quantizers often used in P/B-frames! This makes it extremely difficult to efficiently represent the film grain at reasonable bitrates.

But we can cheat.

Previous frames have a lot of the necessary spatial frequencies--why not steal them? Sure, an inter block won't be as efficient as an intra block, but it might work better. Indeed, the initial idea I got from glancing at the results of the film grain optimization in Elecard's encoder (Mainconcept core). Their film grain optimization almost completely disabled I-blocks in P-frames, suggesting that this was indeed the avenue to go down. Of course, their film grain optimization really wasn't that good--so who knows?

To begin with, I tried the obvious; completely disable intra blocks in P-frames for the hell of it. Surprisingly, this actually worked; in many cases it improved grain retention! But if I was to make this practical, I'd have to find a real way of implementing a metric to decide what block type to use, rather than just brute-force disabling an entire category of blocks.

I eventually came back upon an idea I considered a while back--what about NSSD? NSSD, also known as "noise-retaining sum of squared differences," is a block comparison metric that is supposed to promote retaining grain/noise. How exactly does it do this? NSSD is equal to the sum of the ordinary SSD and the absolute value of the difference in "noise" values for the two blocks to be compared. "Noise" is abs( x(i,j) - x(i+1,j) - x(i,j+1) + x(i+1,j+1) ) summed up over all pixels x(i,j) in the source block (ignoring pixels that would result in this formula going over the edge of the block). In other words, it doesn't compare the pixels of the two blocks; it simply measures the "noisiness" of each block, and makes sure that they have a "similar" amount of noise. Keeping the two blocks visually similar is taken care of by the SSD portion of the score.

Amazingly, this worked; replacing the RD metric (SSD) with NSSD, combined with tweaking of the RD thresholds to ensure that modes that tended to retain noise were always analyzed, drastically improved grain retention, and made inter blocks drastically more common in grainy footage. The patch can be found here, complete with mildly optimized MMX assembly for the "noise" operation, ported from ffmpeg (where NSSD is available as a -cmp/-subcmp/-rdcmp option).

Google summer of code

2008-05-02T10:04:00.000-07:00

This year, x264 is participating in Google Summer of Code. We have accepted four applications out of a total of roughly 15 applications (out of Videolan's roughly 80 applications and 14 slots). The projects are as follows:

Robert Deaton (masquerade): Improve B-frame decision, both in terms of simple numbers of B-frames, direct modes, frame ordering, reference frame using, etc.

Joey Degges (keram): Improve inter mode search and decision and experiment with more psychovisual optimizations

Aki Jäntti (Kuukunen): Use a "macroblock tree" structure to measure the temporal importance of various parts of the image.

Holger Lubitz (holger): General assembly optimizations and speed improvements.

Good luck to all participants!

Skipping stuff

2008-05-02T00:59:00.000-07:00

Its nice to be able to take shortcuts in the encoding process--its even better when we can take a shortcut that doesn't even change the output.

A recent example was my intra skip patch. The basic idea behind intra skip lies in the method by which intra analysis works. For each block of an i4x4 or i8x8 block, all 9 prediction modes are analyzed and the best chosen. The prediction modes use the top, left, and/or top-right pixels to predict the block--so the blocks to the top, left, and top-right of the current block have to be encoded in order to know which pixels we will be predicting with:

The numbers show the order in which the blocks are encoded, in order to make sure all the necessary edge pixels are available during analysis. The gray blocks are from neighboring macroblocks which have already been encoded. Note that the "16" block never gets encoded as part of intra analysis, since it isn't needed for the edges of anything else.

As a result, we have to encode each block as we go along in the analysis process. Once we're done, we can save the results of the encoding so that later, if that intra mode is chosen, we can just restore the backup, saving over 2500 clocks of predict/DCT/quant/zigzag/dequant/iDCT.

Next, there's my p/bskip patch. When pskip/bskip analysis is done, motion compensation on the block is done (with respect to the "skip" motion vector) and then analysis follows. If the skip is chosen, the analysis terminates and the block is encoded... where the motion compensation gets done again. But we can't just turn off all skip-based motion compensation, because there are some cases where you can have a skip in which the motion compensation wasn't the last thing that was done. So I made a variable that told the encoder whether it could skip it or not.

Finally, there's my upcoming fast probe_skip patch, which takes a number of shortcuts in the skip check process:

1. The current skip_check does a full 16x16 DCT (16 4x4 DCTs), and then checks each 4x4 block individually. Quite often, it'll be able to tell after the first block or two that the block won't be a skip; in this case, doing the full 16x16 DCT is a good waste of a few hundred clock cycles. So I made it to an 8x8 DCT (4 4x4 DCTs) for each 8x8 block. Why didn't I do each 4x4 DCT as I went along? The 8x4 DCT (2 4x4 DCTs) is much faster than the 4x4 because its SSE2-accelerated, so I just went ahead and did the 8x8, which is coded as two 8x4s.

2. When checking for a skip, its highly likely that if one got past the first DCT block or two without terminating, most of the rest of the blocks will be zero. As a result, its efficient to check if they're all zero before zigzag/decimate_score; this only takes a few clocks and quite often allows us to skip the aforementioned somewhat time-consuming steps.

As you can see, its quite good when we can skip something entirely; its even better than speeding up a function; its calling a function less often.

Cacheline splits, aka Intel hell

2008-05-01T22:39:00.001-07:00

About 6 months ago Loren Merritt and I, after relatively exhaustive testing on over a dozen types of processors, concluded that Intel chips in general have a problem in the case of a "cacheline split."

To begin with, modern processors divide their cache into "lines"; for example, a Pentium 3 has a 32-byte cacheline size, while a Core 2 has a 64-byte cacheline. The way these work is that whenever the processor is told to fetch data from memory, it will fetch a full cacheline at a time. This also affects how the data is organized in the cache.

Now, when you're loading aligned data, that is, data aligned to a 16-byte line, you're guaranteed to never have that data cross a cache line, since the data is loaded in 8 or 16 byte chunks. But if you're loading unaligned data, which is completely unavoidable in the case of the motion search, you have to do unaligned loads. In the case of a 16x16 motion search and a 64-byte cacheline, this means that 1 in every 4 motion vectors checked will result in the load spanning a cacheline--that is, some of the data comes from one cacheline, and some from another.

Why is this bad? On AMD chips, it isn't; the penalty is no different from any other unaligned load. But on Intel chips the penalty is enormous; in fact, the cost of a cacheline-split load is roughly equivalent to the L2 cache latency, suggesting that a cacheline split actually results in a load from L2 cache. This may not seem too bad, but this adds roughly 12 clocks per load on a Core 2... boosting the cost of a single 16x16 SAD from 48 clocks to over 230 clocks. Splits on page lines are even worse; a single load can cost over 220 clock cycles, roughly equivalent to the main memory latency! A 16x16 SAD has now gone from 48 clocks to over 3600 clocks. The penalty on AMD chips for a pageline split exists, but its extremely small.

Since cacheline splits happen only some of the time (and 1 in 64 cachelines are pagelines) it isn't as bad as it sounds, but the end result is that SADs take about an average of 100 clocks instead of 48. Fortunately, Loren Merritt's massive cacheline split patch fixed this for SADs, resulting in a considerably faster motion search. Investigating his patch, you can see four solutions that he implemented for this problem:

1. The easiest, SSE3-based. The "lddqu" operation tells the processor to, instead of loading the unaligned data, to load two aligned pieces of data and shift them accordingly to give the same result. As a result, it has none of the cost of a cacheline split... but unfortunately it only works on Pentium 4Ds and Core 1s. On Core 2s, lddqu does the same thing as movdqu.

2. The second easiest, MMX-based. Shift amounts are calculated based on the position of the data to be loaded, the data is loaded in two chunks, and they are shifted and OR'd together to get the result. This is best expressed in an image:

As can be seen, this is quite a bit more complex than an ordinary load; it involves precalculation of two numbers (the shift values) and two shifts plus one OR for every single load! But its still far faster than the 12-14 clock latency for cacheline splits. But wait, you thought this workaround was messy? Just wait until you see the rest...

3. The second hardest, using SSSE3's palignr. palignr does what the two shifts and the OR did above, all in a single operation! This would be easier than the MMX version, but there's one complication; the MMX shift described above takes a *variable* value, so we can calculate on runtime the shift amount to use, and then do it. But palignr takes a constant which must be written into the opcode on compile-time! So for this, Loren Merritt made a set of 15 loops, one for each possible alignment, and had the program jump to the correct loop based on the current alignment. Since each loop had a constant size, he could literally calculate the position of the loop in the code and jump to its position numerically instead of storing an array of pointers to the various loops. What a mess! But it works, and faster than the MMX version, since palignr is so much simpler.

4. The worst is SSE; SSE's version of MMX's full-shift has the same problem as palignr; it only takes a constant shift amount. So we have to do the same as palignr's 15-loops, except with all the same hackiness as in the MMX version.

So there we have it; the 4 workarounds, all of which give a similar performance boost on Intel processors. Now you understand why coding assembly for Intel chips can be hell; one has to compensate for such ridiculous performance penalties like these. I extended the cacheline patch to work for the qpel interpolation also, which is used in all of the subpel motion search. This gave an overall speed boost of 1-2% or so (25-40% for qpel interpolation only). My patch only uses the MMX and SSE3 workarounds, since the others were unnecessarily complex for this smaller case. Loren Merritt's sse2/ssse3 hpel_filter patch also used this concept, though in this case the misalignments were precisely known, so using palignr was drastically easier. My frame_init_lowres asm patch also provides an SSE2 and SSSE3-based solution for cacheline splits of known alignment.

Finite state machines and CABAC

2008-05-01T22:30:00.001-07:00

During CABAC binarization, the coefficients in each DCT block are converted to binary symbols which are arithmetically coded into the bitstream. Each symbol has a specific context, the choice of which is calculated through a simple algorithm. This context-choice, of course, has to be the same on encoding and decoding. One can calculate this context for each coefficient--or one can make a finite state machine using a set of states and a transition tables, so that given the current context, the next context can be calculated using merely an array lookup.

This improves performance both in CABAC encoding and CABAC decoding. Note the similarities between the two diffs--despite the fact that one is in x264 and designed for encoding, and the other is in ffmpeg and designed for decoding, they are practically the same code. This is true of most of the CABAC code; in fact, most of x264's CABAC binarization code is simply the code from ffmpeg, except reversed. Original credit for the finite state machine code goes to Loren Merritt, who wrote it to speed up the calculation of CABAC states in x264's trellis quantization algorithm.

Why, Intel, why?

2008-05-01T18:08:00.001-07:00

This diff is highly related to this post.

If one looks in Intel's documentation of their assembly, one notices a few things. In particular, there are a whole bunch of operations which do exactly the same thing but have different opcodes. Intel introduces "movaps" and "movups" for aligned and unaligned moves in SSE1, and then "movdqa" and "movdqu" in SSE2... to do exactly the same thing. The same situation occurs with pand and andps... etc. The end result is a number of things:
1. Wasted opcode space on opcodes that do exactly the same thing.
2. Wasted executable size, since movdqa is larger than movaps (3 byte vs 2 byte opcode) despite doing exactly the same thing.
3. Loss of our sanity.

Unrolling a loop makes it smaller

2008-05-01T18:04:00.001-07:00

The topic of this post is this recent diff. It doesn't at all change the results of the function; I simply unrolled the loop to take advantage of the fact that most of the loop's variables were dependent on the loop constant itself. The result was only 7 lines (!) down from well over 30. Thanks to an earlier ffmpeg patch for the original idea and some of the code.

Apparently GCC doesn't actually measure the benefit gained from constant propagation in unrolling loops, so one is forced to manually unroll in this sort of case.

Oh, and I got roughly a 50% speedup in this function by doing this (not counting the encode_decision calls).

Inter RD refine bugs

2008-05-01T14:16:00.000-07:00

I think I've found two of these in one week now.

For those who don't know, on inter blocks in P-frames, subme 7 works by a process called "qpel RD"; that is, it does an ordinary subpixel refinement of the motion vectors except instead of the usual fast metric (SAD or SATD), it does a full rate-distortion comparison on each qpel position using a hexagonal search. Of course, to increase speed, it uses a SATD threshold above which it won't bother with the whole RD process. The reason for this is obvious when you see the numbers; a full-macroblock SATD takes about 450 clocks, while a full-macroblock RD takes about 10,000 clocks. So even if SATD allowed us to avoid doing an RD 1/20th of the time, it would be worth it; the real numbers are much higher than that, of course.

Now, onto the bugs. The first one was in CAVLC, where in an 8x8dct inter block the numbers for the numbers of non-zero coefficients in each DCT block were not being calculated, resulting in incorrect calculations of bit cost. This wasn't a problem for CABAC, because CABAC only needs to know whether a block is all-zero or not all-zero; while CAVLC needs to know exactly how many non-zero coefficients there are. This was resolved as part of my overhaul of the nnz code.

The second bug I just ran into today, where I found that when RD was done on 8x16 and 16x8 blocks, for simplicity's sake, the RD function encoded two 8x8 blocks separately and then summed the resulting scores. This isn't a problem per se, but the 8x8 RD function went on to check what type of 8x8 block it was: this could be an 8x8, 2 8x4s, 2 4x8s, or 4 4x4 blocks. An 8x16 or 16x8 block can't have such subblocks, while an 8x8 block can. This again isn't a problem... but when a 16x8 or 8x16 block type is chosen, it doesn't reset the subpartition types used for the 8x8 search... so if the 8x8 search chose a sub-8x8 block type, the 8x8 block encode now thinks that we have a sub-8x8 block type even if we cannot possibly have one. The solution was pretty simple.

Array overflows

2008-05-01T14:03:00.000-07:00

x264 keeps a set of pointers to various arrays used for custom quantization matrices (CQMs), deadzone biases, etc. These are stored in the primary x264_t struct as follows:

uint16_t (*quant4_bias[4])[16]; /* [4][52][16] */
uint16_t (*quant8_bias[2])[64]; /* [2][52][64] */

They are malloced at the start of the program and deleted when x264 finishes. Unfortunately the delete code looks something like this:

for( i = 0; i < 6; i++ )
{
...
x264_free( h->quant4_bias[i] );
}

A small part of me died when I read this code. Yes, that's right, its overflowing the array of pointers intentionally because they're arranged sequentially in the struct. Apparently, according to Loren Merritt, this simplifies the deletion code.