[theora] Indexing Ogg files for faster seeking

[Chris Pearce]

I've developed an indexer which embeds a keyframe index track in Ogg 
files. It embeds the index in its own track, so that players that don't 
understand or don't want to use the index can just ignore it.

Ogg needs this to make seeking over networks faster and more efficient.

Currently we must do a bisection search when seeking, which usually 
takes aound 6 HTTP requests, give or take a few. If we are to compete 
with existing internet video (AKA the "YouTube" case) we need to do that 
faster and more efficiently - using fewer HTTP requests. We need an 
index so that seeking only takes 1 HTTP request.

Using an index of keyframes also makes it easier to seek without visual 
artifacts - though of course robust players should be able to do that in 
the absence of an index.

You can download the source code for my indexer here:
http://github.com/cpearce/OggIndex

My specification for the index track is stored in that repo, here:
http://tinyurl.com/l4c9yg

I'd appreciate comments on the spec...

To see how it improves network seeking performance, you can download a 
version of Firefox which can take advantage indexes here:
http://pearce.org.nz/video/firefox-indexed-ogg-seek.linux.tar.bz2
http://pearce.org.nz/video/firefox-indexed-ogg-seek.macosx.dmg
http://pearce.org.nz/video/firefox-indexed-ogg-seek.win32.zip

Then point that browser here:
http://pearce.org.nz/video/indexed-seek-demo.html
(There's a couple of other indexed ogg files in
http://pearce.org.nz/video/ too)

In terms of compatibility, currently the following players can play and 
seek in indexed files (i.e. aren't broken when playing/seeking indexed 
files):
* VLC
* Cortardo
* XiphQT plugin

The following players can play indexed files, but can't seek:
* Anything that uses liboggz (including Firefox 3.5).
* The DirectShow filters (do these use liboggz?)

It only takes a pretty trivial patch to enable liboggz (and thus FF3.5) 
to seek in files with an index; liboggz refuses to seek because it 
doesn't understand metrics for the index track. It shouldn't be too hard 
to fix other players as well.

Totem on Ubuntu9.04 refuses to play the indexed files, though it decodes 
the first few frames. That may require a gstreamer patch.

So... what do you guys think?