I thought I had brainstormed a simple, elegant, multithreaded, deadlock-free refactoring for FATE in a previous post. However, I sort of glossed over the test ordering logic which I had not yet prototyped. The grim, possibly deadlock-afflicted reality is that the main thread needs to be notified as tests are completed. So, the main thread sends test specs through a queue to be executed by n tester threads and those threads send results to a results aggregator thread. Additionally, the results aggregator will need to send completed test IDs back to the main thread.

But when I step back and look at the graph, I can’t rationalize why there should be a separate results aggregator thread. That was added to cut down on deadlock possibilities since the main thread and the tester threads would not be waiting for data from each other. Now that I’ve come to terms with the fact that the main and the testers need to exchange data in realtime, I think I can safely eliminate the result thread. Adding more threads is not the best way to guard against race conditions and deadlocks. Ask xine.

Read the rest of this entry »

Thanks to David Conrad and Ronald Bultje who committed their native VP8 video decoder to the FFmpeg codebase yesterday. At this point, it can decode 14/17 of the VP8 test vectors that Google released during the initial open sourcing event. Work is ongoing on those 3 non-passing samples (missing bilinear filter). Meanwhile, FFmpeg’s optimization-obsessive personalities are hard at work optimizing the native decoder. The current decoder is already profiled to be faster than Google/On2′s official libvpx.

Testing
So it falls to FATE to test this on the ridiculous diversity of platforms that FFmpeg supports. I staged individual test specs for each of the 17 test vectors: vp8-test-vector-001 … vp8-test-vector-017. After the samples have propagated through to the various FATE installations, I’ll activate the 14 test specs that are currently passing.

Initial Testing Methodology
Inspired by Ronald Bultje’s idea, I built the latest FFmpeg-SVN with libvpx enabled. Then I selected between the reference and native decoders as such:

$ for i in 001 002 003 004 005 006 007 008 009 \
 010 011 012 013 014 015 016 017
do
  echo vp80-00-comprehensive-${i}.ivf
  ffmpeg -vcodec libvpx -i \
    /path/to/vp8-test-vectors-r1/vp80-00-comprehensive-${i}.ivf \
    -f framemd5 - 2> /dev/null
done > refs.txt

$ for i in 001 002 003 004 005 006 007 008 009 \
 010 011 012 013 014 015 016 017
do
  echo vp80-00-comprehensive-${i}.ivf
  ffmpeg -vcodec vp8 -i \
    /path/to/vp8-test-vectors-r1/vp80-00-comprehensive-${i}.ivf \
    -f framemd5 - 2> /dev/null
done > native.txt

$ diff -u refs.txt native.txt

That reveals precisely which files differ.

Great news: Hot on the heels of FFmpeg’s 0.6 release, the WebM project released version 0.9.1 of their libvpx. I can finally obsolete my last set of instructions on getting FFmpeg-svn working with libvpx 0.9.

Building libvpx 0.9.1
Do this to build libvpx 0.9.1 on Unix-like systems:

• Download libvpx 0.9.1 from http://code.google.com/p/webm/downloads/list
• Unpack, chdir to the source dir, ‘./configure && make && make install’

libvpx’s build system has been firmed up a bit since version 0.9. It’s now smart enough to install when said target is invoked and it also builds the assembly language optimizations. Be advised that on 32- and 64-bit x86 machines, Yasm must be present (install either from source or through your package manager).

Building FFmpeg 0.6
To build the newly-released FFmpeg 0.6:

• Install Vorbis through your package manager if you care to encode WebM files with audio; e.g., ‘libvorbis-dev’ is the package you want on Ubuntu
• Download FFmpeg 0.6 from the project’s download page
• Configure FFmpeg with at least these options: ./configure --enable-libvpx --enable-libvorbis --enable-pthreads; the final link step still seems to fail on Linux if the pthreads option is disabled
• ‘make’

Verifying
Check this out:

$ ./ffmpeg -formats 2> /dev/null | grep WebM
  E webm            WebM file format

$ ./ffmpeg -codecs 2> /dev/null | grep libvpx
 DEV    libvpx          libvpx VP8

That means that this FFmpeg binary can mux a WebM file and can both decode and encode VP8 video via libvpx. If you’re wondering why the WebM format does not list a ‘D’ indicating the ability to demux a WebM file, that’s because demuxing WebM is handled by the general Matroska demuxer.

Doing Work
Encode a WebM file:

ffmpeg -i <input_file> <output_file.webm>

FFmpeg just does the right thing when it seems that .webm extension on the output file. It’s almost magical.

For instant gratification that the encoded file is valid, you can view it immediately using ‘ffplay’, if that binary was built (done by default if the right support libraries are present). If ffplay is not present, you can always execute this command line to see some decode operation:

ffmpeg -i <output_file.webm> -f framecrc -

The FFmpeg project made a formal release yesterday. You can download version 0.6 from the project’s download page.

I’ve actually been seeing more news items about this today than I would have expected. This is most likely because the 0.6 release is named “Works with HTML5″. Let it never be said that nerds don’t know marketing. The team really latched on to the hottest buzzword going right now.

The name of the release refers to FFmpeg’s new native support for Google’s WebM format. It can mux and demux the WebM container, and decode the Vorbis audio, all natively (FFmpeg’s Vorbis encoder has been demoted to “experimental” for this release and it is recommended to enable libvorbis for encoding). But the big news is that this release can support Google’s libvpx natively for VP8 encoding and decoding, without having to apply any other patches.

Getting libvpx to compile still might be a bit tricky. Fortunately, the first pass of a native, independent VP8 decoder is currently in review on the ffmpeg-devel list.

FATE involves some database tables that define the test specifications. Like everything else in FATE, the concept could use some improvement. After I prototyped an improved, multithreaded testing client, the next logical revision seemed to be the test spec system.

History
The test spec system has been handled by a single table that includes an FFmpeg command line (with a few possible modifiers thrown in), an integer ID, a human-friendly ID, a description, the expected command line return code, the expected command output, a maximum runtime, and a Boolean to indicate whether the test is to be considered active.

Adjunct to this test database is a large corpus of test media named the FATE suite.

At first, the FATE testing script used a direct MySQL database protocol to query the test specs from the server before every build/test cycle. I soon realized this was ludicrously inefficient since the test specs don’t change that often. So I cached the tests in a static file to be retrieved via HTTP, first in Python’s “pickled” (serialized) format, then in an SQLite database.

Planned Upgrades
There are 2 major features I would like to build into the system going forward:

1. The ability to version the entire suite so that it’s possible to test old branches of FFmpeg
2. Another database field to indicate which, if any, other test specs must be executed before this spec can be executed

I think I will take this opportunity to switch the test cache serialization format to JSON. I switched from Python pickling to SQLite because the latter was more portable between languages. JSON has that same benefit. Further, working with JSON data doesn’t require a round trip to disk (i.e., want to generate an SQLite database for sending via HTTP? It needs to go onto disk first. It’s possible to create and manipulate a database entirely in memory but not fetch the bits).

Things To Research

• Pondering how version control systems operate and what they have to teach regarding how to version this data (including the question of whether I can just use an existing version control mechanism instead of creating my own system)
• Efficient caching mechanism
• Tagging test specs for alternate purposes such as longevity testing
• Learn about web form programming in the 21st century so that it’s not quite as painful to maintain the system.

Preliminary Versioning Concept
Here is one approach I am thinking of: Create test groups. Each test spec is assigned to at least one test group. I can think of at least 2 groups: functional (the base test set in existence that validates functionality) and profiling (the projected test set that will be used for ongoing performance and memory profiling). The web frontend will allow for the creation of labels that will apply to a single group. Doing so will apply that label to all active tests in the group.

I got tripped up on another part of the VP8 decoding process today. So I drew a picture to help myself understand it. Then I went back and read David Conrad's comment on my last post regarding my difficulty understanding the VP8 spec and saw that he ran into the same problem. Since we both experienced the same hindrance in trying to sort out this matter, I thought I may as well publish the picture I drew.

VP8 defines various trees for decoding different syntax elements. There is one tree for decoding the tokens and it is expressed in the VP8 spec as such:

Here is what the table looks like when you make a tree out of it (click for full size image):

The catch is that it makes no sense for an end-of-block (EOB) token to follow a 0 token since EOB already indicates that the remainder of the coefficients should be 0 anyway. Thus, the spec states that, "decoding of certain DCT coefficients may skip the first branch, whose preceding coefficient is a DCT_0." I confess, I didn't understand what "skip the first branch" meant until I drew the tree.

For those wondering why it might be sub-optimal (clarity-wise) for a spec to simply regurgitate vast chunks of C code, this makes a decent case. As you can see, the spec makes certain assumptions about how a binary tree should be organized in a static array (node n points to elements n*2 and n*2+1 as its branches; leaves are either negative or 0). This is the second method I have seen; another piece of code (not the VP8 spec) had the nodes in the first half of the array and pointed to leaves in the second half. There must be other arrangements.

Did you know Mac OS X can even blue-screen? To be fair, it doesn't actually present a blue screen. But when Mac OS X encounters a kernel panic, it looks like this:

True to form, Mac just has to be prettier and glossier than other operating systems, even in the area of system crashes.

The reason I bring this up is that the FATE system is bringing down my Mac. My Mac Mini is reliably dying every single time I try to execute my FATE client Python script. Maybe the weather is getting too warm.

Update, 2010-6-8: Following advice in the comments, I tried to run Memtest86 on the Mac Mini in question. I couldn't get the machine to boot the CD I made. As an alternative, I turned the machine off and let it rest for a night. In the morning, I turned it on and ran the FATE client script. It's working for now.

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:
Read the rest of this entry »