[theora] Ogg Index A-mod

[Chris Pearce]

I've been looking over Benjamin Schwartz's Skeleton A-mod proposal. I've 
been pretty busy with other projects over the past few months, so 
haven't had a chance to look at Ogg indexing until now...

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. 
We may as well get the index as right as we can first time.

I like the ideas of storing the end time/max granulepos in the index 
packets, and of a b_max value for corruption detection. They're 
sensible. I will include them in the next version.

We should try to avoid changing the 'fishead' packet to be incompatible 
with previous minor-versions. 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?

Benjamin: have you made any index A-mod prototype encoders to get an 
encoded-index size comparison? I also have a few questions about your 
proposal...

> The Golomb-Rice encoded integers are encoded by subtracting 1, 
> dividing by the
> Golomb-Rice parameter, representing first the quotient in unary (1s), 
> then a 0,
> and then the remainder in binary. We subtract 1 because a Golomb-Rice code
> naturally represents 0, but 0 is not a valid delta between subsequent 
> values.
> For example, consider encoding a delta of 2496 with a scaling 
> coefficient of 64
> and a Golomb-Rice parameter of 16. First, 2496 is divided by 64, 
> giving 39. We
> subtract 1, then divide 38 by 16, yielding a quotient of 2 and 
> remainder of 6.
> The quotient and remainder are coded as 110 0110. This is a prefix 
> code, so no additional delimeters are needed to separate values.

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?


> 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?


> 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?


All the best,
Chris P.