[theora] Ogg Index A-mod

[Benjamin M. Schwartz]

Chris Pearce wrote:
> In general, I think Benjamin's ideas are sound, they're improvements,
> and I'm open to being convinced to take them in the next index version.

Wow.  Thank you.  I have to admit that it's definitely not perfect.  I
still don't know quite what to do about rolling-intra and out-of-order
streams (Dirac).

> We should try to avoid changing the 'fishead' packet to be incompatible
> with previous minor-versions.

OK.  I put them on the end of fishead, thinking that this would be
sufficient for compatibility.  If it's not sufficient, then I agree we
should avoid breaking compatibility.

> If we move the start/end time fields into
> the index packets, which is sensible, it would break backwards
> compatibility of this version with earlier versions of the same major
> version. Silvia et al wanted to add some new fields to the skeleton
> track, so maybe we should increment the version to 4.0, include those
> fields, and change the rest of the index format?

Do the new fields proposed by Silvia require a new format?  I thought the
point of fisbone was to be extensible.  Maybe Silvia has proposed more
things that I don't know about.

> Benjamin: have you made any index A-mod prototype encoders to get an
> encoded-index size comparison?

I'm afraid not.  My few statistics that suggest a typical stream might
spend a total of 4 bits per keypoint.

> Am I right to assume that the binary value of the remainder is encoded
> in a fixed width field of log2(Golomb_Rice_parameter)? e.g. log2(16)=4
> bits in this example?

Yes, the remainder is fixed-width (but not aligned).

>> Note that it is not always safe to
>> round granpos down after division: if rounding down would cause the
>> granpos
>> to move too early, then it must be rounded up.
> 
> Can you give an example of this? Is it the case when you divide the
> granulepos such that it moves to before the previous keypoint's granulepos?

If you were to round down the granulepos but not the byte offset, then the
granulepos might say "seek to this offset to get granulepos 4", when in
fact the granulepos at that offset is 7.  If you were looking for
granulepos 5, you're too late in the stream.

This can still happen even if both are being rounded down.  The safe
solution is to round the offset down and the granpos up.  However, it will
sometimes be valid, and slightly more efficient for seeking, to round both
down.

>> 9. 'n' key points, each of which contain, in the following order:
>>     - the keypoint's byte offset delta, as a shifted Golomb-Rice encoded
>>       integer. This is the number of bytes that this keypoint is after
>> the
>>       preceeding keypoint's offset, or from the start of the segment
>> if this
>>       is the first keypoint. The keypoint's byte offset is therefore
>> the sum
>>       of the byte-offset-deltas of all the keypoints which come before
>> it.
>>     - the granpos delta for this keypoint as a shifted Golomb-Rice
>> encoded
>>       integer. This is the difference from the previous keypoint's
>> granpos
>>       value. The keypoint's granpos is therefore the sum of
>>       all the granpos deltas up to and including the keypoint's.
> 
> Would you expect the granulepos scaling shift to be equal to the
> granuleshift for theora streams, at least initially? Have you given any
> thought to how to determine good values for the shifts and Rice parameters?

The spec suggests that for most streams a granularity of 2 seconds or 64
KB is sufficient.  I think that corresponds to a granulepos scaling shift
of granuleshift+log2(2 seconds / granulerate), and a byte offset scaling
shift of log2(64K) = 16.  That quantization may be a touch excessive;
maybe 1 second and 32 KB would be sufficient.  For selecting the Rice
parameter, the optimum parameter is log2(mean(data)) up to rounding.

--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/20100423/62b48022/attachment.pgp