Firefox Bug 620614 — nsTheoraState::MaxKeyframeOffset doesn’t need to use MulOverflow

Several weeks ago, I worked on Firefox bug 620614. The title simply said “nsTheoraState::MaxKeyframeOffset doesn’t need to use MulOverflow”.

Yeah I know, I was stumped too.

Understanding it required me to go through some the basics of Theora and decoders in Firefox. I’ll try and report on some of what I learned here.

To best understand the problem, let’s understand the code around it by running through a test case and emulating the need for it.

Go to the OGG video here.
Why a debate from Davos 2012 on Capitalism? Because it’s under Creative Commons and ~70 MB. The length and the size are important, you’ll see why.

What you see now is the video slowly buffer up from start to the 26th minute. When a video buffers, it is simply downloading some “video data” required to play it to your computer, so that when you seek any portion of it, the player can get to it easily. Now as the video loads, click around in the timebar in some unbuffered areas and wait for the video to load up. Try doing this a few times.

Now go to a second video here. This is a desktop recording of me doing the exact same thing that you are, but of an intentionally hijacked build of Firefox. As you can see, when I click on a part of the video, the frame that loads up is choppy and blocky everytime without fail, as opposed to yours which is smooth. To understand why this happens, read on. Also remember this point as point [1], which I will refer back to.

Our current usecase occurs in the method SeekInUnbuffered() in nsOggReader.cpp. It does so like this:

if (HasVideo() && mTheoraState) {
keyframeOffsetMs = mTheoraState->MaxKeyframeOffset();
}

Alright, so this means that when a user “seeks in unbuffered”, or clicks a part of the video timeline that has not yet buffered, the codec, upon some conditions, tries to calculate the ‘keyframe offset’ in milliseconds.

If we look inside the method in question, MaxKeyframeOffset(), we see this

PRInt64 d = 0;
MulOverflow(USECS_PER_S, mInfo.fps_denominator, d);
frameDuration = d / mInfo.fps_numerator;

So what seems to be happening here is that MaxKeyFrameOffset is being set based on the calculation mInfo.fps_denomicator x USECS_PER_S.

mInfo.fps_denomicator is, as the name suggests, the denominator of the fps (frames per second) the video plays at, and USECS_PER_S is the number of microseconds in a second, or 1000000.

The product of these is stored in the PRInt64 type ‘d’, which is then used to calculate the frameDuration, and subsequently MaxKeyFrameOffset. But notice that d is a 64-bit Integer, and multiplication overflows can occur if the FPS of the video is large enough. This would result in ‘d’ being a 0, and hence the MaxFrameOffset also being 0. So why would this produce the broken video buffers demonstrated at [1]?

This has to do with some of the information that OGG videos carry. One piece of the data is called the Skeleton. This gives a keyframe by keyframe structure to the video, such that the location of all keyframes is known by the skeleton. When a user seeks any given frame, the player uses what’s called a “bisection search” to determine the closest keyframe, and play the video from there. Some videos don’t have skeletons, in which case the player cannot correctly determine the closest keyframe, as in our case. When this happens, and a bisection search is impossible, a MaxKeyframeOffset is sougth. In some cases, while this is being calculated, our d would be 0. In such a case the player will render the closest frame which, by virtue of not being a keyframe, looks messy and choppy.

This occurrence is rare; it would happen only in videos where a multiplication overflow is likely to occur (or where the FPS is really high), and where a skeleton does not exist. Software such as ffmpeg2theora today, by default generate a skeleton for any video they process, but this was not the case until early 2011. The demo video that I produced in [1] was produced with ffmpeg2theora with the parameter — no-skeleton. It’s size and length enable us to experiment with it and increase the probability of the bug occurring. Like I mentioned earlier though, the bug here is EMULATED. I built a copy of Firefox in which I forced d to be always 0, and hence we see what would happen when the overflow would occur.

Fun stuff!

But our specific bug is a little less interesting. All it says is that the MulOverflow64() is not needed as one of the two numbers involved is 32-bit. The solution to that is simple, as included in my patch, but to really understand what was going on and why I was doing what I was doing required me to understand the above. Thought I’d share it.