As stated in a previous blog post on the matter, FFmpeg’s policy is to reimplement codecs rather than adopt other codebases wholesale. And so it is with Google’s recently open sourced VP8 codec, the video portion of their Webm initiative. I happen to know that the new FFmpeg implementation is in the capable hands of several of my co-developers so I’m not even worrying about that angle.

Instead, I thought of another of my characteristically useless exercises: Create an independent VP8 decoder implementation entirely in pure Python. Silly? Perhaps. But it has one very practical application: By attempting to write a new decoder based on the official bitstream documentation, this could serve as a mechanism for validating said spec, something near and dear to my heart.

What is the current state of the spec? Let me reiterate that I’m glad it exists. As I stated during the initial open sourcing event, everything that Google produced for the initial event went well beyond my wildest expectations. Having said that, the documentation does fall short in a number of places. Fortunately, I am on the Webm mailing lists and am sending in corrections and ideas for general improvement. For the most part, I have been able to understand the general ideas behind the decoding flow based on the spec and am even able to implement certain pieces correctly. Then I usually instrument the libvpx source code with output statements in order to validate that I’m doing everything right.

Token Blocker
Unfortunately, I’m quite blocked right now on the chapter regarding token/DCT coefficient decoding (chapter 13 in the current document iteration). In his seminal critique of the codec, Dark Shikari complained that large segments of the spec are just C code fragments copy and pasted from the official production decoder. As annoying as that is, the biggest insult comes at the end of section 13.3:

While we have in fact completely described the coefficient decoding procedure, the reader will probably find it helpful to consult the reference implementation, which can be found in the file detokenize.c.

The reader most certainly will not find it helpful to consult the file detokenize.c. The file in question implements the coefficient residual decoding with an unholy sequence of C macros that contain goto statements. Honestly, I thought I did understand the coefficient decoding procedure based on the spec’s description. But my numbers don’t match up with the official decoder. Instrumenting or tracing macro’d code is obviously painful and studying the same code is making me think I don’t understand the procedure after all. To be fair, entropy decoding often occupies a lot of CPU time for many video decoders and I have little doubt that the macro/goto approach is much faster than clearer, more readable methods. It’s just highly inappropriate to refer to it for pedagogical purposes.

Aside: For comparison, check out the reference implementation for the VC-1 codec. It was written so clearly and naively that the implementors used an O(n) Huffman decoder. That’s commitment to clarity.

I wonder if my FFmpeg cohorts are having better luck with the DCT residue decoding in their new libavcodec implementation? Maybe if I can get this Python decoder working, it can serve as a more appropriate reference decoder.

Update: Almost immediately after I posted this entry, I figured out a big problem that was holding me back, and then several more small ones, and finally decoded by first correct DCT coefficient from the stream (I’ve never been so happy to see the number -448). I might be back on track now. Even better was realizing that my original understanding of the spec was correct.

Unrelated
I found this image on the Doom9 forums. I ROFL’d:
Continue reading →

The first thing I thought upon waking this morning was that today is not a good day to be on the internet. I knew that a video codec was going to be open sourced today. And I knew that it would pretty much dominate tech sites all day. And I knew that much of the ensuing discussion — when it strayed into the technical domain — would be misleading, misinformed, or just plain wrong. So why bother?

Fortunately, Dark Shikari posted a very thorough first look at the VP8 algorithm and analyzed how it stacks up, technically, to the currently recognized leading algorithm — H.264. Thus, he hopefully got out in front of the hype (I wouldn’t know; like I said, I haven’t read any discussion today). He dinged the algorithm in a number of areas but assessed that it has some potential and is obviously superior to VP3/Theora. Afterwards, I was able to find the source code, test vectors, and specification for download. Then I read the official announcement that the product I work on at my day job demo’d support for this codec. Then I saw that Sorenson has a product available that can encode VP8.

And then I was struck with a revelation. Put aside Dark Shikari’s learned criticism of VP8’s weaknesses as well as the ever-present patent uncertainty. Can you grasp how incredible this all is? Forgive my giddiness, but look at all we have, coordinated on the same day:

• Google releases a decent video codec. Complain if you wish that it’s not as good as H.264 but preliminary tests demonstrate that it’s still pretty darn good, certainly better than its vaunted predecessor (VP3/Theora).
• Google releases source code for it. Complain if you wish about the code’s quality, but it’s all there.
• Google posts instructions to build the source code out of the box on day 1 with free tools. Compare this to VP3’s source code release late in 2001. Here’s what it took to build:
  • Microsoft Visual C++ 6.0 (Visual Studio 6.0)
  • Microsoft Visual Studio 6.0 Service Pack 4
  • Microsoft Visual C++ Processor Pack (VCPP)
  • Macro File for Microsoft Macro Assembler for Intel Streaming SIMD Extensions
  • QuickTime for Windows SDK (4.0 or 5.x)

  That was on Windows; building on Mac required CodeWarrior. The point is, this newly-freed source code was only immediately buildable using non-free tools. I eventually separated and hacked up just enough code to build under gcc and decode frames (and if I had written a blog at the time, I probably would have published it).

• Google publishes a suite of test vectors. This is a huge sticking point for me as the volunteer QA manager for FFmpeg, especially since there has never been a good test suite published for other free codec technologies such as Theora and Vorbis.
• Google publishes a specification. Complain if you wish that “The spec consists largely of C code copy-pasted from the VP8 source code, up to and including TODOs, ‘optimizations’, and even C-specific hacks, such as workarounds for the undefined behavior of signed right shift on negative numbers.” Having this kind of thorough documentation on day 1 boggles my mind.
• Google releases patches to allow the encoder and decoder to interoperate on day 1 with leading open source multimedia programs such as FFmpeg and MPlayer. Google employees were also poised to engage these communities on day 1 to push these patches into upstream codebases (e.g., this patch and this patch from Google’s James Zern).
• My company, Adobe, demos support for VP8 in the internet’s leading video delivery platform, Flash Player (the product I work on). Complain if you wish regarding Flash Player (heh, do it) but it’s the fastest way to make a video codec ubiquitous.
• Sorenson makes an encoding product available on day 1.

All told, today’s VP8 release is nothing short of remarkable. Compare this to the last time a video codec was open sourced. That would be On2’s VP3 near the end of 2001. That was a code dump that was impossible to compile out of the box using free development tools, came with no test suite, had zero documentation outside of the code and nearly none inside the code, and was followed up with very little community engagement. It was over 2 years later that I finally started to understand the codec well enough to write the first scrap of high-level documentation as well as the first independent (and, still to this day, one of the very few) decoder implementation. I guess I was just sort of expecting the same kind of thing this time around.

The VP8 spec is titled “VP8 Data Format and Decoding Specification.” Sounds very similar to my “VP3 Bitstream Format and Decoding Process”. I like to think I helped set the standard for documentation as evidenced by the spec’s title. Is it arrogant to try to take credit for that? Which reminds me– I need to see if the Free Software Foundation has yet taken credit for Google’s open sourcing of VP8. Well, they have a press release praising the event while not taking credit.

Still, complaints that the VP8 spec might not be all that great, or that the code may be a bit weird or suboptimal or not fully C99-compliant, cause me to snicker when I put it in perspective. It makes me ecstatic to realize how far our collective community standards have evolved in the past 10 years. When VP3 was open sourced, On2 was praised for the gesture, even though the event had all the shortcomings I outlined above. If today’s open sourcing event had paralleled VP3’s event in execution, Google would be roundly (and rightfully) criticised, ridiculed, and generally dismissed. This open sourcing event has legs.

That’s progress. I’m happy.