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

> The advantage of storing this in the granulepos field itself, like
> theora and CMML do, is that the seek code may already understand how
> to handle the back pointer. Right now everything assumes the mapping
> is from 'initialized decoder' + 'granulepos from page
header' =>
> timestamp, or in the case of theora and CMML => 'timestamp' +
'last
> keyframe timestamp.' Having to look in the accompanying page data is
> an additional complication.
Since the format of that back pointer is specific to each codec, the seek
code must already know how that codec does its backlink, for each codec
it supports. This is not generic for all codecs. Therefore, picking an extra
64 bits granulepos at the start of the data is a fairly trivial complication, as
the Ogg layer will have the data handy since it just seeked to it. That extra
complication comes with the plus of not chopping off half the granule bit
space for the backlink, leaving only a 4 billionth of the granule space
available (if one assumes no reserved bits).
Or is there something that makes it that much easier to deal with a backlink
in the granulepos itself ?
For reference, my data packets start with start granule, end granule, backlink
granule, all 64 bits, so picking the granule is just a simple constant offset
lookup into the data packet, eg, you replace:

backlink = granulepos<<32;

by

backlink = read64le(op.packet+constant_offset);

Hardly complex.
> decoders to find all the relevant data. Put another way, start-time
> labelling for substreams with low page frequency helps buffering after
> they're muxed, but it only goes so far if there's not also a lower
> bound on that frequency.
If I understand what you want to get at, the frequency would be tied to the
maximum delay between two packets ?
FWIW, we only need to find a packet from the disc stream on the first
bisection (to find the backlink). For the second bisection, it is enough to
seek to a time before that backlink, as streaming in will eventually encounter
the backlinked packet, and that's enough for our purposes. Therefore, the
second bisection can be done timewise on the main continuous codec (eg,
the accompanying theora video).
If there is no accompanying theora video (or similar), then I don't think
the
problem happens, since you'll be swamped by kate packets anyway, since
there'll be nothing else there, so you don't waste time looking for
them.
Still means you get the hit for the first bisection.

Following on your point about a lower bound on the frequency, maybe one
could add "keepalive" packets when no data packets have been issued
for
a long enough time, and such packets would carry no data but the backlink
itself. Hmm, I like the idea. The packets would be very small (well, datawise,
most of the data will be Ogg header stuff), and we wouldn't get that bad
data
duplication that was inherent in the "echo" method described in the
Writ doc.

Mind you, that kind of frequency info is something that might be usefully put
in a new skeleton field, if it could help the seek code seek more efficiently.
Not sure if and how it could though.

On 11-Feb-08, at 2:46 AM, ogg.k.ogg.k@googlemail.com wrote:
> For reference, my data packets start with start granule, end  
> granule, backlink
> granule, all 64 bits, so picking the granule is just a simple  
> constant offset
> lookup into the data packet, eg, you replace:
>
> backlink = granulepos<<32;
>
> by
>
> backlink = read64le(op.packet+constant_offset);
It is more complex, because the granulepos is available at the page  
level. We've generally designed the seeking algorithm so it can be  
implemented without looking inside the packets beyond looking up the  
samplerate in the first few packets. And you can repeat both the  
samplerate and how much to shift the granulepos to get a backlink in  
a skeleton packet.

Of course we could add your scheme to Skeleton as well, but the start  
of the packet data could be on a completely different page from the  
granulepos.
> If I understand what you want to get at, the frequency would be  
> tied to the
> maximum delay between two packets ?
Yes, possibly with a hint about this in the skeleton metadata.
> FWIW, we only need to find a packet from the disc stream on the first
> bisection (to find the backlink). For the second bisection, it is  
> enough to
> seek to a time before that backlink, as streaming in will  
> eventually encounter
> the backlinked packet, and that's enough for our purposes.  
> Therefore, the
> second bisection can be done timewise on the main continuous codec  
> (eg,
> the accompanying theora video).
We need to work out recommendations for this. And it depends on your  
purposes: the mod_annodex thing of trying to efficiently serve a  
chunk out of an existing file is the most demanding. But even for  
generic playback from a file, you have to know whether you need to  
find the kate packet after a seek or just wait and see if one  
eventually falls out.
> Following on your point about a lower bound on the frequency, maybe  
> one
> could add "keepalive" packets when no data packets have been
issued
> for
> a long enough time, and such packets would carry no data but the  
> backlink
> itself. Hmm, I like the idea. The packets would be very small  
> (well, datawise,
> most of the data will be Ogg header stuff), and we wouldn't get  
> that bad data
> duplication that was inherent in the "echo" method described in
the
> Writ doc.
That's the sort of thing I was talking about.
> Mind you, that kind of frequency info is something that might be  
> usefully put
> in a new skeleton field, if it could help the seek code seek more  
> efficiently.
> Not sure if and how it could though.
I can think of two 'seeking hints' that might be useful in skeleton.  
One is some kind of minumum page frequency, to help an implementation  
decide if it's looked hard enough for a packet from a particular  
stream. Another is just a way to say a particular stream isn't  
essential for playback: if you find a page, great, otherwise just  
wait for the next one to fall out. These could be combined of course.

  -r

On Feb 11, 2008 9:46 PM, ogg.k.ogg.k@googlemail.com <
ogg.k.ogg.k@googlemail.com> wrote:
> Following on your point about a lower bound on the frequency, maybe one
> could add "keepalive" packets when no data packets have been
issued for
> a long enough time, and such packets would carry no data but the backlink
> itself. Hmm, I like the idea. The packets would be very small (well,
> datawise,
> most of the data will be Ogg header stuff), and we wouldn't get that
bad
> data
> duplication that was inherent in the "echo" method described in
the Writ
> doc.

We have considered the "keepalive" idea for CMML, too, for similar
reasons.
I think it may well be the best solution - they are a small overhead to pay
for more efficient seeking. And the frequency could be added to the skeleton
headers.

Cheers,
Silvia.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://lists.xiph.org/pipermail/ogg-dev/attachments/20080212/4a24a02f/attachment.htm

> It is more complex, because the granulepos is available at the page
> level.
Ah. Good point, I always forget about the partial page problem :(
I conveniently flush pages after each data packet in my case (due to
unknown/arbitrary latency), so I tend to forget easily about those.
> We've generally designed the seeking algorithm so it can be
> implemented without looking inside the packets beyond looking up the
> samplerate in the first few packets. And you can repeat both the
> samplerate and how much to shift the granulepos to get a backlink in
> a skeleton packet.
This puzzles me: what are you referring to when you say "the seeking
algorithm" ? If you're referring a particular implementation, then it
does
mandate the linear (or is it affine ?) granule/time mapping, but I've not
seen any of this in the Ogg docs. If, you're referring to the structure of
Ogg packets/pages where you have to do one (or more) bisection(s),
then this is more general, and cannot rely on this knowledge, which is
particular to each codec.

Actually, I'm thinking about all this while writing, and it's hitting me
that
it should not matter whether you have partial pages or not: if you have a
partial page, it means that no packets end on that page (I'm assuming
the semantics of a -1 granulepos is the same for both continuous and
discontinous streams here). You can therefore ignore that page for the
purposes of seeking, since you couldn't make use of it to start decoding
anyway. Unless you have monster packets that span pages all the time,
this won't happen much anyway.
Or is there a reason such pages have to be handled specially ?
> Of course we could add your scheme to Skeleton as well, but the start
> of the packet data could be on a completely different page from the
> granulepos.
That was not the intent, my scheme is likely to be very specific to my case.
My point was to try to understand how the splitting of granules in two would
avoid a double bisection, which it doesn't if I got that well, so I'm
trying to
get an explanation of its interest, which so far seems to be that it keeps all
the granule data in the same place, at the page level, which so far does
not convince me it is worth the loss of 32 bits of granule space.
> We need to work out recommendations for this. And it depends on your
> purposes: the mod_annodex thing of trying to efficiently serve a
> chunk out of an existing file is the most demanding. But even for
> generic playback from a file, you have to know whether you need to
> find the kate packet after a seek or just wait and see if one
> eventually falls out.
Provided you seeked at or before the backlink, just playing and waiting
for the next packet is enough, since that's the point of that backlink.

On 12-Feb-08, at 1:33 AM, Silvia Pfeiffer wrote:
> We have considered the "keepalive" idea for CMML, too, for
similar
> reasons. I think it may well be the best solution - they are a  
> small overhead to pay for more efficient seeking. And the frequency  
> could be added to the skeleton headers.
Conrad mentioned this as well. Can you be more specific about this  
proposal? Was the idea to repeat the previous packet? Use empty (zero- 
length) packets?

  -r