[ogg-dev] Seeking to granules in discontinuous streams

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

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 ?