:rikaichan for Vimperator

Some of my favourite Firefox plugins are:

• Rikaichan, a Japanese dictionary, which adds instant translation popups when you mouse over a word;
• Vimperator, which provides vi-like user interface;
• and Hide Tab Bar, because Vimperator's buffer list is more useful.

Vimperator hides the menu bar by default. Tools->Toggle Rikaichan has no default keybinding, and the keybindings to navigate the menubar are not available if the menubar is not visible, so Rikaichan can no longer be activated.

The following adds a vimperator command :rikaichan; save it to .vimperator/plugin/toggleRikaichan.js:

(function(){
    vimperator.commands.add(new vimperator.Command(
        ['rikaichan', 'rikai'],
        function(){
            rcxMain.inlineToggle();
        }
    ))
}) ();

It is aliased to :rikai for short, but unfortunately vimperator won't recognize :理解. Thanks to ktsukagoshi for the explanation of how to write a vimperator plugin (vimperatorのプラグインの作成).

Remember, the interface is inside your mind.

Continuation Fest 2008: Continuations for video decoding and scrubbing

Yesterday was Continuation Fest 2008, at the University of Tokyo's campus in Akihabara (a very nice venue!). It was very well attended; latecomers overflowed to a second room and participated by video conference. It was a little strange to see so many people interested in such an obscure, troublesome and malignant expressively powerful programming construct; the breadth of talks made for a very inspiring and practical introduction to the theory, applications and implementation of continuations in many different languages.

I recommend reading Kenichi Asai's introduction to delimited continuations (slides [PDF]). He introduced the shift and reset operators through the problem of expressing exceptional control flow, and then explained how to use these to type (ie. determine a concrete type for) printf. The main point was that shift/reset provide a high-level abstraction over control flow, with minimal impact on the implementation of your existing functions.

Oleg Kiselyov demonstrated some new code for transactional web applications, using delimited continuations for explicit state sharing between parallel connections. The result is that the user has a consistent view across multiple tabs are open on the same site, and the state is transactional so that there is no need for warnings like "Do not press the BUY button more than once!". He said that everyone already understands delimited continuations, they just don't realize it.

The topic of my presentation at Continuation Fest was Continuations for video decoding and scrubbing:

Playback of encoded video involves scheduling the decoding of audio and video frames and synchronizing their playback. "Scrubbing" is the ability to quickly seek to and display an arbitrary frame, and is a common user interface requirement for a video editor. The implementation of playback and scrubbing is complicated by data dependencies in compressed video formats, which require setup and manipulation of decoder state.

We present the preliminary design of a continuation-based system for video decoding, reified as a cursor into a stream of decoded video frames. Frames are decoded lazily, and decoder states are recreated or restored when seeking. To reduce space requirements, a sequence of decoded frames can be replaced after use by the continuation which created them. We outline implementations in Haskell and C.

• Slides [383KB PDF]
• Article [215KB PDF]

I'll be introducing the code for this over the next few months. Whereas in my presentation about video player internals at BOSSA I outlined the problem space in designing a multimedia architecture, at Continuation Fest I tried to break it down into subproblems and considered useful data structures and programming techniques for dealing with them.

I got a lot of great feedback, and I think I succeeded in my mission to introduce this problem space to some really smart people. Thanks particularly to Chung-chieh Shan for some insightful ideas about how to deal with existing stateful codec implementations. It was also very interesting to talk with Shinji Kono about Continuation-based C (cBc) (slides [HTML tarball]), a C-like language capable of expressing continuations, non-local jumps, multiple function entry-points, and assorted other ways to shoot yourself in the foot. He suggested that it was designed for exactly the kind of thing I'm doing, and I'll be interested to try it out. It is implemented in a modifed GCC 4.x as an RTL code generator, so should now be (fairly) architecture-independent.

Thanks to the organizers of Continuation Fest 2008 for putting together such a useful and interesting event. I look forward to implementing just some of the things I learned :-)

Release: Sweep 0.9.3

This is a bugfix release of Sweep, addressing CVE-2008-1686. For details, see my earlier post about libfishsound 0.9.1. Thanks to Peter Shorthose for managing this release.

Release: libfishsound 0.9.1

This is a maintenance release, fixing a security vulnerability in Speex header processing as outlined in oCERT 2008-02. When used in a client for web video content, as in the OggPlay Firefox Plugin or the Ogg DirectShow filters, a specially crafted Ogg Speex stream hosted on a server could be used to allow an attacker to execute arbitrary code on the client system. The OggPlay plugin binaries available from www.annodex.net have already been updated.

Details

The Speex header contains a 32-bit modeID field, interpreted by libspeex as a signed int (spx_int32_t) The normal way to use this is to index into a global mode list to retrieve a SpeexMode *:

mode = (SpeexMode *)speex_mode_list[modeID];

and then use that to set up a decoder:

st = speex_decoder_init(mode);

This calls speex_decoder_init() in libspeex, which looks like:

void *speex_decoder_init(const SpeexMode *mode)
{
   return mode->dec_init(mode);
}

So if you don't check that the modeID given in the stream header is within the bounds of speex_mode_list[], arbitrary code can be executed. libfishsound was checking the upper bound (modeID < SPEEX_NB_MODES) but was not checking against negative values.

Discussion

This header processing is all boilerplate, and a reference implementation is given in speexdec.c. I took a copy of that about 7 years ago for Sweep, which I then adapted for libfishsound. The current reference speexdec.c does not have this bug.

For the Symbian port of Speex we created a function which returns the desired mode given a modeID, rather than having application code index into a global mode list. I wrote and committed speex_get_mode() to libspeex in September 2004, and it does the correct bounds checking. So if I'd been using that function in libfishsound then today's problem would never have happened. As it turns out, the libfishsound svn trunk version of speex.c does use that function. As far as I am aware, the OggPlay plugin binaries have always been built against the libfishsound svn trunk, so they were never vulnerable in the first place. However, recent tarball releases of libfishsound have been coming of a separate branch, so the advisory is valid for applications linked against those releases.

Finally, I sent a patch to Jean-Marc Valin yesterday which entirely removes the possibility of this bug happening again by bounding the mode values returned by speex_packet_to_header() in libspeex. It will be available very soon in a libspeex release.

Acknowledgements

Thanks to the team at oCERT for the efficient reporting of this advisory, and to the anonymous submitter for the details. I was able to patch the offending branches, which allowed j^ to build and upload new OggPlay plugin binaries (within 24 hours of contact by oCERT).

• libfishsound 0.9.1 release notes
• oCERT 2008-02

Release: HOgg 0.4.0

HOgg is a Haskell library and commandline tool for manipulating Ogg files. This release contains a bunch of code written during FOMS and LCA 2008, including a new sort subcommand and proper handling of Skeleton when merging and ripping files. Full details are in the release notes.

sort implementation

My favourite part is the implementation of the new sort subcommand:

sort :: [OggPage] -> [OggPage]
sort = sortHeaders . listMerge . demux

This is somewhat shorter than the equivalent C implementation, oggz-sort.c — Haskell affords abstraction whereas in C it's a trade-off. sortHeaders is a long (21 line) function that re-orders header pages according to the Theora and Skeleton specifications, and listMerge is a generic list merging function, also used in the merge subcommand. demux is tiny:

demux :: (Serialled a) => [a] -> [[a]]
demux = classify serialEq

You can read that as "demux is classification by serial number": classify is a generic list function, classifying list elements according to some criterion you give it. Here, for example, the list of pages:

[Video0, Audio0, Video1, Audio1, Audio2, Audio3, Video2, Audio4, Video3, ...]

will get classified into two separate lists:

[[Video0, Video1, Video2, Video3, ...],
 [Audio0, Audio1, Audio2, Audio3, Audio4, ...]]

This is done lazily, meaning that the processing is done on the fly and big intermediate lists are not constructed in memory. Video0, Audio0 will be passed through listMerge and sortHeaders and written to disk by the consumer of sort well before Video103 and Audio5007 are seen.

Documentation improvements and self-checking

The help for each subcommand now contains long descriptions, mostly similar to the man pages of the Oggz tools. The descriptions also have explicit sections describing how Theora, Skeleton and chained files are handled. The example commandlines for each subcommand use the Ogg MIME types and file extensions that we are now recommending in Xiph.Org.

The best bit though is hogg selfcheck, which checks that the help examples are valid. It checks that all the example commandlines pass through getOpt without errors, and that all file extensions used in options are valid. This is the kind of nice touch which would have been a pain to code up in C, but fell out cleanly in the Haskell implementation. As it is fairly cheap to run (and printing help text is hardly a performance-critical operation), this option is also silently run after printing out any help output at all, so that such errors are more likely to be found and reported. The same commit that introduced hogg selfcheck also fixed two such documentation errors which were found by this option :-)

Release: xsel 1.2.0

XSel is a command-line tool for manipulating the X selection. This is a maintenance release, improving argument handling, documentation and X11 library detection.

• xsel-1.2.0.tar.gz
• Release notes

BOSSA 2008: Video Player Internals

Last week I attended BOSSA, a conference on open source software for mobile embedded platforms, organized by INdT. It was held in the town of Porto de Galinhas, Brazil. Since then I have been hanging out in the INdT labs in Recife, hacking on xine, catching up with friends and exploring the old city.

The topic of my presentation at BOSSA was Video Player Internals:

Embedded platforms put demands on latency and memory use. Video playback makes these difficult to guarantee. This presentation discusses the architecture of video players, and the problems imposed on them by the design of video codecs and their containers. To explain these problems we look at both proprietary and open source formats (MPEG, Ogg, Theora, Dirac, etc.) and evaluate open source video players in this context. We particularly examine xine and GStreamer, and introduce the minimal architecture of OggPlay.

• Slides [613KB PDF]
• Article [330KB PDF]

I'm very grateful to INdT for the opportunity to attend, it was an awesome conference in a very beautiful part of the world.