[theora] Indexing Ogg files for faster seeking

[Benjamin M. Schwartz]

Chris Pearce wrote:
> Could you provide a spec for the index packet so we can see how 
> this would work?

I tried to modify your Skeleton 3.3 document for a bit higher efficiency,
and possibly improved "elegance".  To avoid confusion I'm calling it
"Skeleton A-mod", and the proposal is available at

http://github.com/bemasc/OggIndex/blob/master/Proposed-modified-spec.txt

I tried to make minimal modifications, and get github to display a diff,
but it didn't work.

In this proposal, times do not appear in the index header at all.  The
index is instead specified in terms of granpos, which is shifted to remove
low bits, differenced to deltas, and then Rice coded.  The removal of some
low bits is "lossless" in Theora, Dirac, and Vorbis.  If the keypoints are
rounded off so that they are equally spaced, then the timing information
for each one requires only 1 bit.

Performance on byte offsets is harder to predict, but because byte offsets
can be rounded off I expect them to be dramatically compressible as well.

Each index stream provides a "b_max" value indicating  the maximum
introduced error.  Adding b_max to the maximum offset delta bounds the
number of bytes that must be read to decode any inter-frame.

--Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
Url : http://lists.xiph.org/pipermail/theora/attachments/20100129/f34a6dec/attachment.pgp