[theora] Indexing Ogg files for faster seeking

[Benjamin M. Schwartz]

Chris Pearce wrote:
> I think we should remove the checksums, and simply delta and
> variable-byte encode the offsets and timestamps. We can consider an
> index invalid if:
> 
>   1. The segment/link length doesn't match the length stored in the
>      fishead packet, or
>   2. After a seek to a keypoint's offset, we don't land on a page
>      boundary, or
>   3. The first keyframe we decode after seeking to a keypoint doesn't
>      have the same presentation time as stored in the index.
> 
> Does that sound reasonable?

Maybe.  But I think you should also consider relaxing the guarantee on the
byte offsets.  Currently, I guess they're guaranteed/required to point to
a page boundary.  If you instead only guarantee that the next page after
that point is the desired page, then you can round off the offsets.  If
the shortest page in a file is at least 256 bytes*, then you can save 8
bits per offset by allowing the offsets to fall up to 255 bytes before the
desired page starts.  The incurred performance cost (scanning those 255
bytes to find the page start) is negligible.

--Ben
*: I'm not suggesting that it always will be, but you can make this
roundoff factor a parameter specified for each file

-------------- 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/20100124/b5c20ca4/attachment.pgp