[ogg-dev] Seeking to granules in discontinuous streams

[ogg.k.ogg.k at googlemail.com]

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