WMAVoice codec dissection

Since my last post,I’ve completed my first version of a free (as in speech) WMA-Voice/Speech codec. The patch is available on the FFmpeg mailinglist. As described previously, the codec has some very interesting behaviour, e.g. related to integer rounding. At unofficial forums, you will generally get the impression that use of WMAVoice is discouraged, because other codecs, notable WMAPro, offer better quality at the same bitrate.

This is essentially true. For low-bitrate streams, for which CELP-based voice codecs are optimized, WMAVoice has considerable noise compared to other Voice codecs. Why is this? While studying the codec, I found one particularly interesting bug (?) in the codec. Most behaviour in CELP-based codecs is based on the concept of a pitch. A pitch is like the wavelength of a sine-like frequency curve. Usually, the bitstream will code an adaptive and a fixed codebook, where the adaptive codebook is basically some sort of a modified (e.g. different gain) repetition of a previous excitation signal, whereas the fixed codebook contains completely new (“innovative”) excitation signal that was not based on any previous excitation signal. The excitation signal is a series of pulses (in an otherwise zero background) at a pitch-interval, and thus both codebooks are based on the pitch-value. After generation of the excitation signal using these two codebooks, the pulses from the two codebooks are then interleaved, so that LPCs can be used to synthesize the actual wave frequencies from the excitation pulses.

So, pitches are important. Let’s see how WMAVoice calculates pitch: pitch is coded per-frame (a frame contains 160 audio samples). This code uses the frame-pitch (an actual integer, with no fractional bits) to calculate the pitch-per-block (which can be 20/40/80/160 samples, depending on the frame type) and the pitch-per-sample. These values are obviously fractional, e.g. if you go from a pitch of 40 to a pitch of 41, then somewhere halfway the frame you’ll have a pitch of “40.5″. In the next calculation, I’ve replaced the int-math by float-math to make it clearer what they’re doing.

for (n = 0; n < s->n_blocks; n++) {
float f = (samples_per_block + 0.5) / samples_per_frame;
block_pitch[n] = round(f * prev_frame_pitch + (1 - f) * cur_frame_pitch);
}

Why is this wrong? Well, look at what f means. f increments from (a bit above) zero to (a bit below) one for each block in the frame. If the frame has two blocks, f will subsequently have the values 0.25 and 0.75. However, block_pitch[n] receives a value for the first block of 0.25 * prev_frame_pitch + 0.75 * cur_frame_pitch. For the second block, we’ll get the reverse, i.e. 0.75 * prev_frame_pitch + 0.25 * cur_frame_pitch. Instead of creating an incremental array that slides us from the pitch of (the end of) the last frame towards the pitch of the (end of the) current frame, an array was created that slides back from the (end of the) current frame’s pitch to the (end of the) last frame’s pitch. The result is audible noise introduced in the decoded audio:

stddev: 1588.23 PSNR: 32.31 bytes: 264014/ 264014

Of course, the FFmpeg decoder does not have this bug.

Posted in General | 5 Comments

Codec woes

I’ve recently become interested in codecs. We all know the brilliant FFmpeg project, which has provided free (as per FSF definition) implementations of a variety of popular codecs, such as Windows Media or MPEG/H.26x.

I’ve started to study one member of the Windows Media Audio family, the WMAVoice codec. I’m studying an integer version of it, which means that multiplications are done by mult/shift pairs. For example, if you imagine a (32-bit) integer with 1 bit sign (+/-), 1 bit for pre-digit numbers and the other 30 bits being fractional, then the number 1.0 would be encoded as 0x3FFFFFFF. To multiply 1.0 * 1.0 (which should give 1.0 as result) in this integer scheme, you’d use:

#define mulFrac30(a, b) (((int64_t) a * (int64_t) b) >> 30)

By changing the “30″ in this macro, you could multiply numbers with different amounts of fractional bits. Those trying it themselves will notice that mulFrac30(0x3FFFFFFF, 0x3FFFFFFF) results in 0x3FFFFFFE (i.e. 0.999999999), so the result is not precise. But it’s close enough to be useful on embedded devices where floating-point operations are expensive. (It’s true that I’m basically demonstrating (n * n) / ((n + 1) * (n + 1)) here, i.e. you can get around it for this particular example by encoding 1.0 as 0×40000000 instead of 0x3FFFFFFF, but similar behaviour would show up for other numbers.)

This “rounding error” becomes more prominent if you decrease the number of fractional bits. For example, 1.0 * 1.0 in frac-16 integers (0xFFFF) = 0xFFFE, which is 0.99997. It also gets worse as you convert between fractional types, e.g. to go from a frac-16 1.0 (0xFFFF) to a frac-30 1.0, would be done by:

#define convertFrac16ToFrac30(x) (x << 14)

And the result of that on 1.0 in Frac-16 (0xFFFF) would be 0x3FFFC000. Why is that a problem? Well, look at this particular piece of code present in the codec:

void function(int array[], int v, int size)
{
    int stp = mulFrac31(v, 0xCCCCCC /* 0.00625 */),
        min = mulFrac31(v, 0x189374 /* 0.00075 */),
        max = mulFrac31(v, 0x3FE76C8B /* 0.49925 */), n;
    int array2[size], array3[size];

    for (n = 0; n < size; n++)
        array2[n] = array3[n] =
            mulFrac31(array1[n], v);

    array3[0] = MAX(array3[0], min);
    for (n = 1; n < size; n++)
        array3[n] = MAX(array3[n - 1] + stp,
                        array3[n]);
    array3[size - 1] = MIN(array3[size - 1],
                           max);

    for (n = 0; n < size; n++)
        if (array2[n] != array3[n])
            array1[n] = divFrac31(array3[n], v);
}

This loosely translates to the simpler float version:

void function(float array[], int v, int size)
{
    array1[0] = MAX(array1[0], 0.00075);
    for (int n = 1; n < size; n++)
        array1[n] = MAX(array1[n - 1] + 0.00625,
                        array1[n]);
    array1[size - 1] = MIN(array1[size - 1], 0.49925);
}

But there's a catch. The original code converts from a scale as given by the input array1 to a scale provided by the magnitude of the "v" variable, whatever "v" may be. Turns out that "v" is the samplerate. For this type of codec, samperate is generally low, e.g. 8000Hz. Therefore, if the value in array1 is e.g. 0.25 (0x1FFFFFFF), then in array2/3, this same value would be mulFrac31(0x1FFFFFFF, 8000) = 1999. Converting this back would bring it to divFrac31(1999, 8000) = 0x1FFBE76E. We just chopped off 19 bits of our number! Needless to say, the quality of the audio is affected by this kind of behaviour (stddev is the average square-root difference between samples decoded with and without this behaviour):

stddev:    0.15 PSNR:112.41 bytes:   264014/   264014
stddev:    0.56 PSNR:101.29 bytes:   264014/   264014
stddev:   13.73 PSNR: 73.57 bytes:   527906/   527906
stddev:    2.35 PSNR: 88.87 bytes:  2538240/  2538240

Which makes me wonder: why do they do that?

Posted in General | 2 Comments

My first publications

In daily life, I’m a Ph.D. student studying the development of the central nervous system. A few months ago, the first paper was released with my name on it (as a second author), and just yesterday, I received notification of publication of my first paper as a first author.

  • Yu YC, Bultje RS, Wang X & Shi SH. Specific synapses develop preferentially among sister excitatory neurons in the neocortex. Nature 458 (7237), pp. 501-4 (2009) [ abstract at Nature ];
  • Bultje RS, Castaneda-Castellanos DR, Jan LY, Jan YN, Kriegstein AR & Shi SH. Mammalian Par3 Regulates Progenitor Cell Asymmetric Division via Notch Signaling in the Developing Neocortex. Neuron 63 (2), pp. 189-202 (2009) [ explanation, abstract at Neuron ].

Needless to say, I’m very excited and hope for more novel findings in the future. In short, my publication describes the identification of a mechanism by which radial glial cells, the “stem cells” that give rise to excitatory neurons in the cerebral cortex (the brain region that handles most higher-level functions in mouse and man), divide “asymmetrically”. In this process, stem cells divide to give rise to two different kind of daughter cells: one is another radial glial cells, which will undergo the same process again. The other daughter cell will be a neuron or a transit-amplifying cell (a committed neuronal precursor that will divide to give rise to two neurons). We identified and analyzed the protein mPar3, which seggregates into one half of the dividing cell, and we identified two other molecules downstream of mPar3, through which mPar3 regulates cell fate (“stem cell” versus “neuron”) of the daughter cells.

Asymmetric Division of Radial Glial Cells

Asymmetric Division of Radial Glial Cells

Posted in General | 2 Comments

A Real Shame

As Christian pointed out, Real Networks is an odd pea in our pot. They do Free Software at some level, but at other levels they appear to truly dislike “us” – the Free Software community. A friend of mine runs a company shipping a media product based on FFmpeg. This media product includes decoding capabilities for Microsoft’s and Real’s proprietary audio formats. When trying to buy patent licenses for their free software-based product (which can be legal; Google does this also in Chrome), this company received the following responses:

  • Microsoft: “Sure, no problem”
  • Real: “FFmpeg developers are thieves so we don’t want your money if you’ll use their product”

It’s interesting to point out here that the once-so-hated Microsoft has – especially after the EU antitrust case – done everything that we once asked for. They have published many of their protocols on MSDN. They might be corporate to the bone, but they play relatively fair and there’s will & potential for co-existence on both ends. Real wants no co-existence. They do not subscribe to our “Free” ideals.

Posted in General | 3 Comments

PowerPoint Remote for your iPhone

First, a short introduction to how this all came about. Lately, I’ve been interested in iPhone applications. The one thing that Apple did really well (after some initial crack) is to deliver a SDK and ecosystem to extend the iPhone with all the crap that you could come up with. Most of them are games, I don’t really play games, but some of them are quite useful.

For example, consider that with minimal effort, you could write applications to make your iPhone act as:

  • a USB data stick
  • a remote control for tv, audio or computer
  • a notepad

This all comes in addition to basic features that all already exist:

  • calendar
  • portable e-mail
  • SMS, IM, social networks

Suddenly the very thought of carrying 20 items with you to office every day feels really tragic. Don’t get me started about all these devices that are lingering around at home in the living room. How many remote controls do you have? You can probably imagine that I would love the Blackberry a lot, too.

For my studies, I use PowerPoint. A lot. Imagine my excitement when I found that several applications existed to use your iPhone as a remote control for PowerPoint, such as iClickr and iPresenter. Both failed in the usability department, especially when compared to Apple’s Keynote iPhone Remote application, and therefore I decided that I would have to write my own. I present you: iPhone PowerPoint Remote (more screenshots available by clicking the link).

  • swipe and tap your finger to switch between slides
  • drag your finger to show an on-screen (in your actually running slideshow) arrow pointer
  • hold-and-drag your finger to make colored annotations

annotation-tn1

The application is available in the Apple iTunes store, and requires a small piece of software to run on your host Mac, available here.

Posted in General | Tagged , , | 3 Comments

Married

Li-Ling & me in City Hall, New York

Li-Ling & me in City Hall, New York

I tend to announce things late – but better late than never. I got married ~4 weeks ago, at least speaking in civil terms. We celebrated with lunch in Boqueria, drinks in Felix and dinner in Nobu. A true great celebration for an even greater event. The “celebration ceremony” for family & friends will be later this year.

Posted in General | Tagged | 1 Comment

Authentication over a network

I’m in the process of writing a pair of applications that allows two hosts to interact. The idea is that one application (the “server”) would run on any desktop computer, propagated by Bonjour/Zeroconf (?), and the other application would run on a cell phone (iPhone, Android).

How, then, do you authenticate the cell phone? A question as simple as this has kept me busy for three straight days and I can’t find a good answer to it. Ideally, the service would be installed as a package (on OSX) and there should be no user interaction at that stage, and the service would continually be available through launchd (like inetd). Authentication-driven authorization is needed because other users would be able to maliciously connect to the service while you don’t want them to. That, then, gives us two goals:

  1. When the user itself is requesting authorization, it should be as easy as possible on both the desktop and server side
  2. When a malicious users is requesting authorization, then the authentication mechanism should automatically reject the connection, without any interaction on the desktop. I might at this point be writing an important document and would not want to be disturbed with silly dialogs saying “would you like to authenticate this user”.

So how do you implement authentication over a network that meets both of these requirements?

  • I am considering using the password of the currently logged-in user on the Mac as key for authentication. However, I have yet to find a way to actually check a password for validity in Mac OS X. Its security model (rightly so) places actual authentication in a process separate than the running application (securityd and Security Agent), which means that I can’t do my own version of that. Of course, the password would be sent encryptedly over the network.
  • I could use a separate password, but then the desktop-service would require configuration, which sucks.
  • Bluetooth pairing-style authentication/authorization involves actual interaction, violating condition (2) above.
  • You could pop up a dialog on the desktop asking the currently logged in user if it’s OK for the iPhone to connect, but that again sucks for the reason given in condition (2).

Dear lazyweb, any ideas?

Posted in General | 4 Comments

FFmpeg and the Google Summer of Code

Are you proficient in C, interested in highly technical problems and do you want to learn more about multimedia and free software while earning $4500? Apply as a student for one of the FFmpeg projects in the Summer of Code program, sponsored by Google! Over the past years, this has resulted in highly popular and succesful projects such as the VC-1/Windows Media Video 9 decoder and the Realvideo-3/4 decoder, which are now used in multimedia applications all around the world.

Are you ready to be the free software world’s next multimedia-hero?

Posted in General | Comments Off

FFmpeg release

The rocking guys at FFmpeg have just released version 0.5, the first release in eons! Congratulations!

You don’t know what FFmpeg is? Go read about it on Wikipedia. For most people, FFmpeg is what provides the horsepowers to their media applications, in the form of codec and format implementations, and as such it acts as a critical cornerstone of better-PR’ed projects such as GStreamer, Mplayer, Xine or VLC.

Posted in General | 1 Comment

Firefox, GMail and content-type of attachments

Dear lazyweb,

I – being a developer – like to send patches (“.patch” files) using GMail to a mailinglist. My peers will want to read these patches, and thus I’d like to associate a content-type (or mime-type, or file-type) with these patches so that in email clients, it’ll be opened in a text editor, or GMail with show a “View” link. The normal content-type for this is text/plain, so in past versions of Firefox, I used the MacOSX MisFox preferences pane to add a content-type “text/plain” for files with the extension “.patch”. Worked great.

However, this stopped working after an upgrade of Firefox. I used to send emails with an attached “.patch” file, and GMail would show a “View” link. In my current Firefox, this “View” link is still there for old emails. However, when I send new emails with “.patch” files attached, the “View” link is not there. It seems that while sending emails, my Firefox misdetects “.patch” files for something else. My only available action is “Download”, which (when pressed) tells me it is not a “text/plain” file, but a “Patch file”.

This name “Patch file” occurs in the Firefox “Preferences -> Applications” window, for “text/x-diff” and “text/x-patch” files. Clients on the other side of my emails, including GMail and patch reviewers, do not know these content-types and can thus not auto-view my patches in their email client. How do I permanently get rid of this content-type association in Firefox?

[edit, 1 day later] I looked at mimeTypes.rdf, and I adapted what I could so that “.patch” is now recognized as “text/plain” on downloads, but uploads still fail to display a “View” link for “.patch” files, whereas “.txt” files display the “View” link just fine. Are uploads independent of mimeTypes.rdf? [/edit]

[edit:2] From similar tests in Safari, I see the same problem. All descriptions of this problem in previous versions of Firefox are browser-specific. In other words, this might not be a Firefox-problem, it appears like Google is changing the content-type of uploads server-side. Why? [/edit]

Posted in General | 1 Comment