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

Hi,

I have a question about seeking. In fact, it's more or less a kind
of rambling and thinking aloud, circling around a question.

I've been wondering how to deal with seeking in a stream, and what
to do when seeking in the middle of a set of active events (eg,
when several bits of text are supposed to be shown, but you seek
after the time when they are first shown, and before the time when
they are hidden).

The three main ways I see to do this are:
 - The CMML way: split the granule pos in two and encode the previous
   clip's start granule in the low bits - this preserves the continuity
   of granulepos's.
 - The Writ way: repeat events at regular intervals, so you can always
   be sure to have all packets if you seek to at least that interval
   before the actual time you want to seek to.
 - adding a field in packets with the granulepos of the earliest
   packet still active (that's my current favored solution)

Up to now, I thought the way CMML handled seeking to the previous
clip required only one seek, since it encodes the granule of that
previous clip in the low bits of the current clip's start granule,
so you can seek to (current_granule<<32)|0.
However, when you seek to a random time within a stream, you do
not know the actual granule of the packet you seek to, you compute
a rough granule that corresponds to the time you seek to, and start
seeking in the stream.
Actually, for discontinuous codecs like CMML or Kate, you won't,
you'll just seek on the video (or audio) stream, or you'd spend
your time looking for a packet blindly, since the vast majority of
packets will be video or audio, and a binary search would be rather
inefficient.

So, you still have to do two seeks: one to find a CMML packet at
roughly the right time, and then seek to the previous clip. You
can only do it then, since you just learnt the granulepos of the
"current" packet, and thus the granulepos of the previous one.
The only other alternative (short of having a convenient index of
all packets and their granulepos, but that's cheating) is to search
a bit before the time you want to seek to, and then linearly seek
backwards till we catch a packet. That'd work if all clips end when
another one starts.

But that doesn't work for Kate, which can have any number of active
events at a given time, though that might be OK for CMML. But if
this is enough, then it doesn't matter at all that the granulepos
of the previous clip be shoved into the lower bits of the granulepos
of the current packet, this would just decrease the granulespace by
4 billionfold for no gain.
And I don't really want to do that for Kate anyway since I need a
few bits for allowing multiple events at the same time (this avoids
things like increasing granulepos's necessarily mapping to different
times).

Anyway, this means that you have to do two seeks, though only one
decode - but decode is cheap for something like CMML once you have
the packet anyway.

If storing the granulepos of the earlier still active event in any
packet, it means two seeks and two decodes (or a decode and a half,
as I store that granulepos at the start of the packet at a fixed
offset, so it's just a lookup away), and that's pretty much the
same for no reduction in granulespace (to keep this in perspective,
at a granule per millisecond, the granulespace is about 50 days,
which is uncomfortably low for my taste (while it'd be perfectly
fine for movie subtitles, it might not for other uses - especially
as my current implementation reserves a few low bits for mapping
several events to the same time).

Am I missing something ? Is it still somehow possible to do single
step seeks with the granule-in-granule method ? Or does it have
another benefit which I haven't seen ?

On 06/02/2008, ogg.k.ogg.k@googlemail.com <ogg.k.ogg.k@googlemail.com>
wrote:
> Hi,
>
> I have a question about seeking. In fact, it's more or less a kind
> of rambling and thinking aloud, circling around a question.
Hi,

No particular answers, but I can at least point out that the way
things were designed for CMML was to work with the existing Ogg
seeking algorithm. The idea is that a generic seeking routine can work
on any Ogg file, as long as it knows the granulepos->time mapping for
the logical bitstreams in the file. That's why all the
timestamp-related info is crammed into granulepos rather than being
placed in packet data, where it is no longer visible in the
container..

Assumptions about seeking in Ogg:
http://www.annodex.net/software/liboggz/html/group__seek__semantics.html

which quotes from a mail from Monty in 2002 explaining the seek algorithm.

Ralph's recent talk at LCA, "Seeking is hard: Ogg design
internals":
http://linux.conf.au/programme/friday

Hope that clarifies things a little bit. The answer may simply be that
what you want to do isn't possible within the existing Ogg container +
seek algorithm.

K.

> No particular answers, but I can at least point out that the way
> things were designed for CMML was to work with the existing Ogg
> seeking algorithm. The idea is that a generic seeking routine can work
> on any Ogg file, as long as it knows the granulepos->time mapping for
> the logical bitstreams in the file. That's why all the
> timestamp-related info is crammed into granulepos rather than being
> placed in packet data, where it is no longer visible in the
> container..
I think I'm missing something here, but I'm not quite sure what and
I'd
really like to understand it.

At a basic level, CMML granule-to-time function is (granule>>32)*scale.
This loses the low bits, which encode the high bits of the previous packet's
granulepos. Please stop me there if I'm wrong.

If one wants to seek into a CMML stream, one starts with a time. One does
not have a granulepos, but has to construct one from the time, so one just
generates a "good guess" granulepos: (time/scale<<32). The low
bits may
as well be left to zero, since we have no knowledge what they might be.

And this is the crux of the problem, as far as I understand how it works:
you'll have to do a first bisection to find the page that maps to that
granulepos,
then, and only then, you get to know the low bits of the actual granulepos,
and then you have to do another bisection to find it.

This is *not* handled by Ogg, since the granulepos encoding is wholly out
of its concern, so there's no way it can optimize out hte second biseciton.
If you want to be clever and you know clips are short and can't overlap,
you can get away with manual backward streaming to avoid the bisection,
but that's still a second seek.

Compare this with storing the granulepos of the earliest still active packet,
which is what I'm doing currently. This means a granulepos doesn't
contain
info on the previous packet's granulepos, but since you have to do two seeks
anyway, you don't mind. You'll just have to start decoding the first
packet to
find out the granulepos of the earlier packet, rather than just shift the found
granulepos by 32. This means you have to know the packet format, so it does
depend on the lib/codec. *BUT* this is also the case for CMML, where the
seeking client must know about the fact that CMML encodes a granule like
it does, with (x<<32)|y. Ogg can't do anything from this knowledge
(*), it still
has to be handled via the client code. The only difference I see between the
two methods is that mine requires a lookup inside the packet, which you'll
have anyway since Ogg had to seek to it beforehand.

(*) or can it ? Is this the bit I'm missing ? I'm 99% sure it can't,
but I'd be happy
to be proved wrong as it would resolve the conendrum.
> Assumptions about seeking in Ogg:
> http://www.annodex.net/software/liboggz/html/group__seek__semantics.html
>
> which quotes from a mail from Monty in 2002 explaining the seek algorithm.
Ah, quite interesting. That last solution Monty mentions would "fix"
the double
seek problems.
> Ralph's recent talk at LCA, "Seeking is hard: Ogg design
internals":
> http://linux.conf.au/programme/friday
I'll have a look, seems very topical.
> Hope that clarifies things a little bit. The answer may simply be that
> what you want to do isn't possible within the existing Ogg container +
> seek algorithm.
I don't think so, though it'd require a bit of help from the client
code, who'd
know the semantics of the codec. Unless this is also a consequence of the
bit I'm missing and not managing to get my head around.