ogg dev - Feb 2008 - Seeking to granules in discontinuous streams

Hi,

do you still think you need all this, if you are allowed to have equal
granulepos on subsequent pages?

Conrad.

On 18/02/2008, ogg.k.ogg.k@googlemail.com <ogg.k.ogg.k@googlemail.com>
wrote:
> Hi,
>
>  I've now got another way of encoding granule (oh, not *again*, I hear
>  you cry). I believe it's an improvement over the existing
"generic"
>  method, so I'll outline it here for your consideration. Again,
it's
>  different from what Skeleton can handle, but it's a simple superset
and
>  would be easy to add to Skeleton (and liboggz). It is also compatible
>  with other existing codecs (eg, theora). It is implemented in libkate,
>  so it works and the changes needed are minimal. I'm happy to make the
>  necessary changes in oggmerge/liboggz if needed.
>
>  The two advantages this change brings are increased usable time (for the
>  same timestamping precision) and the ability to map different granules
>  to the same time. Both are adjustable by client code.
>
>  That said, I see the interest of having a shared method of mapping time
>  and granules, and I'll use the Theora/CMML method if this proposed
>  method doesn't convince you.
>
>  See the end of the mail for the trivial code difference between the two
>  methods.
>
>  The proposed mapping is based on the existing granule shift based
>  system, and adds two more quantities:
>  - a second granule rate fraction
>  - a second granule shift
>
>  If the second granule rate fraction is equal to the main granule rate
>  fraction, and the second granule shift is zero, the system is equivalent
>  to the existing one, ensuring backwards compatibility (eg, for those
>  older streams, one can set the second fraction to the first one, and the
>  second granule shift to zero).
>
>  The current system uses the same granule rate for both the base (the
>  high bits) and the offset (the low bits) of the granulepos. Here, a
>  separate granule rate (typically coarser) is applied to the base,
>  allowing the base to span a larger timespace. Since the offset added to
>  that base uses the finer grained granule rate, the precision of the
>  resulting timestamping remains (as long as the time than an offset can
>  span is less or equal to the granularity of the base, but that does
>  leave quite a bit of leeway). In effect, the existing method maps a lot
>  of different granules to the same time (though not contiguous granules).
>  In other words, a particular timestamp can be represented by a lot of
>  different granules. This is where the new method gets bits back without
>  sacrificing timestamping precision.
>
>  Additionally, a second granule shift can be used to reserve a few low
>  bits so that they will not be used in the timestamping computation. This
>  allows a codec to use those bits as a counter which will not advance the
>  time (eg, to allow multiple events at the same time, which is not
>  possible with the current system). Setting this shift to zero reverts to
>  the existing system.
>
>  Attached is a simple program that shows the two different methods and
>  the granules generated by base/offset pairs, along with the number of
>  bits each requires.
>
>  For a timestamping precision of 1ms, as you can see by running the
>  program, the existing method can't handle a base+offset of more than
>  about 50 days. If you move the granuleshift around, since the two are
>  added together, you just move the granulespace from base to offset or
>  the other way round, without getting more actual space.
>
>  With the method I've described, one can choose to lengthen the usable
>  time space by losing precision on the base. As shown by running the
>  program, the default setup (25 bits for the base, 2 kill bits) can
>  encode both a 1157 day base and a 1157 offset at the same time while
>  keeping the base precision to 10 seconds (the timestamping precision
>  still being 1 ms, so all times between 0 and 2300 days or so can be
>  represented at millisecond precision), and seek to any of those times
>  will be only at most 10 seconds before the intended time. Of course, for
>  smaller time ranges (such as a two hour movie), the base precision can
>  be kept to the same millisecond precision.
>
>  I believe that the replacement of the current "generic"
description of
>  granule mapping, as described in skeleton, by this sytem should be
>  considered for the following reasons:
>
>  - For the same timestamping precision, that new mapping extends greatly
>   the range of times that can be represented
>
>  - The new mapping allows the low bits of the granulepos to map to the
>   same time, allowing multiple events at the same time
>
>  - The user code can choose to extend (to all intents and purposes)
>   arbitrarily the representable range of times, at the expense of base
>   precision (though the base+offset precision remains the same)
>
>  - Ogg does not mandate any particular mapping, so the current system
>   overly constrains the range of mappings (the proposed one still
>   constrains to a linear mapping, but constrains less).
>
>  - Skeleton isn't widely used yet (AFAIK), and CMML is being changed,
so
>   now is a good time for such a change (well, that's not a reason to
>   change, but rather a lack of reason not to change).
>
>  - Finally, the proposed mapping is a superset of the currently used one,
>   and resolves to it if the kill bits granule shift is zero and the
>   granule rate fraction is the same for both base and offset, so
>   backwards compatibility is kept for streams encoded with the existing
>   method.
>
>
>
>  For reference, the code difference between the two methods is:
>
>  Current method (from libtheora's toplevel.c):
>
>     ogg_int64_t iframe=granulepos>>pbi->keyframe_granule_shift;
>     ogg_int64_t
pframe=granulepos-(iframe<<pbi->keyframe_granule_shift);
>
>     return (iframe+pframe)*
>       ((double)pbi->info.fps_denominator/pbi->info.fps_numerator);
>
>  Proposed method (from libkate's kate_granule.c):
>
>   base=granulepos>>ki->granule_shift;
>  
offset=(granulepos-(base<<ki->granule_shift))>>ki->granule_shift2;
>   return
base*(kate_float)ki->gps_base_denominator/ki->gps_base_numerator
>      
+offset*(kate_float)ki->gps_offset_denominator/ki->gps_offset_numerator;
>
> _______________________________________________
>  ogg-dev mailing list
>  ogg-dev@xiph.org
>  http://lists.xiph.org/mailman/listinfo/ogg-dev
>
>

> do you still think you need all this, if you are allowed to have equal
> granulepos on subsequent pages?
The time figures I mentioned earlier were without bits reserved for the
counter, so yes, I think so.

However, I'm not sure about allowing the same granulepos for distinct
events at the same time for the following reason:

The Seek Algorithm bisects to the latest page with a granpos equal or
lower than the one we're seeking to. If you've got, say, two events at
granule 10, and the bisection finds the second one, it'll then bisect to
the later side, so it'll seek to that second page, missing the first. That
seems like the wrong thing to do. In my case, I wouldn't want that to
happen.

Something else that needs more thinking about.

On Mon, Feb 25, 2008 at 6:02 AM, ogg.k.ogg.k@googlemail.com
<ogg.k.ogg.k@googlemail.com> wrote:
>  The Seek Algorithm bisects to the latest page with a granpos equal or
>  lower than the one we're seeking to. If you've got, say, two
events at
>  granule 10, and the bisection finds the second one, it'll then bisect
to
>  the later side, so it'll seek to that second page, missing the first.
That
>  seems like the wrong thing to do. In my case, I wouldn't want that to
>  happen.
No, it seeks to the highest granpos position *preceeding* the requested time.

Monty