Monthly Archives: June 2010

Revised FATE Test Spec System

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.

Understanding the VP8 Token Tree

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.

FATE Ends the Mac

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.

Fighting with the VP8 Spec

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 →