ogg.k.ogg.k@googlemail.com
2008-Feb-06 03:33 UTC
[ogg-dev] 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 ?
Conrad Parker
2008-Feb-07 01:07 UTC
[ogg-dev] Seeking to granules in discontinuous streams
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.
ogg.k.ogg.k@googlemail.com
2008-Feb-07 03:20 UTC
[ogg-dev] Seeking to granules in discontinuous streams
> 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/fridayI'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.