[vlc-devel] Updated patch for ogg/theora seeking

[salsaman]

While I am waiting for a reply, I just thought I would explain the search
algorithm used, so you verify it is very efficient.

We create an index on the fly, this index is basically:
offset in file -> maximum frame number

When asked to seek to a particular frame, we first check the index to see if
we have approximate boundaries for the seek, otherwise we will seek in the
whole file, from data_start until the end.

The area to be searched is divided into two halves. We first check the upper
half, and get the highest and lowest granulepos. (The granulepos is
basically keyframe * keyframe_offset + frame offset). If our target frame
lies in this region we subdivide it into two halves, otherwise we check the
lower half from earlier. We stop when we have found the keyframe for our
target frame, or the search region is < minimum_page_size.

What we are aiming to find on this first pass, is the highest keyframe (sync
point) which is <= target frame.

Once we have found this, we need to rewind a bit further, because the ogg
container only discloses where a frame ends, not where it begins. So we do a
second pass and find the highest granulepos < target granulepos from the
last step. We begin decoding from here, ignoring any frames which are output
on this first page. We then start counting down until we reach the target
frame.

As we discover keyframes (sync points) these are added to the index. Also,
if we discover a higher frame number which is based on the same keyframe we
update our index. Additionally, during normal playback the index is updated
with keyframes as we play them.


If the codec/demuxer is installed and working properly you can see this in
operation - the first seek takes a noticable fraction of a second,
subsequent seeks become increasingly faster as the keyframe -> highest frame
index is built up.


I believe this is the most efficient way of seeking in ogg (at least for
theora - and probably for dirac; although dirac seems a little different in
that there is a lower bound but no upper bound for dirac, and according to
the dirac spec the granulepos shows the first frame decoded on a page rather
than the last frame).

There is currently one known issue, which is if the entire file is <
min_page_size, we never find any keyframes. I am working on a fix for this,
I believe the solution in this case is simply to divide the min_page_size by
2 until we get a keyframe produced.

Regards,
Gabriel.


http://lives.sourceforge.net
https://www.ohloh.net/accounts/salsaman



On Wed, Jun 9, 2010 at 2:35 PM, salsaman <salsaman at gmail.com> wrote:

> As a result of my work, I would like to propose a new flag for the stream:
>
> STREAM_CAN_EXACTSEEK
>
> - the proposed meaning of this flag is that within the stream one can seek
> exactly to any given frame without artifacts in the frame. This flag must be
> settable by the demuxer plugin, and is not fixed - for example you could
> have a container with two video streams one after the other, the first could
> set this flag and the second (using a different codec) could be not
> seekable.
>
> Rationale:
> I understand that you are creating libvlc with the intention of this being
> used for video editing applications. I know from my own experience with
> LiVES that such applications require demuxers which can deliver the exact
> frame requested, so generally one would need to look at STREAM_CAN_EXACTSEEK
> | STREAM_CAN_FASTSEEK to see if the stream is immediately usable or requires
> further processing (caching, indexing, etc).
>
>
>
>
> Regards,
> Gabriel.
>
>
>
>
>
> http://lives.sourceforge.net
> https://www.ohloh.net/accounts/salsaman
>
>
>
> On Wed, Jun 9, 2010 at 10:37 AM, salsaman <salsaman at gmail.com> wrote:
>
>> You could also try uncommenting some of the fprintf in oggseek.c and
>> seeing what happens.
>>
>> You should see it homing in on the keyframe before the target frame.
>>
>>
>> Gabriel.
>>
>>
>> http://lives.sourceforge.net
>> https://www.ohloh.net/accounts/salsaman
>>
>>
>>
>> On Wed, Jun 9, 2010 at 10:19 AM, salsaman <salsaman at gmail.com> wrote:
>>
>>> OK, here is the patch updated with FASTSEEK.
>>>
>>> If you are seeing problems even after downloading elephants dream, then I
>>> think there is some other problem. Maybe you are using a different demuxer
>>> (avformat ?) instead of the ogg demuxer ?
>>>
>>>
>>>
>>> Regards,
>>> Gabriel.
>>>
>>> http://lives.sourceforge.net
>>> https://www.ohloh.net/accounts/salsaman
>>>
>>>
>>>
>>> On Wed, Jun 9, 2010 at 3:52 AM, Ilkka Ollakka <ileoo at videolan.org>wrote:
>>>
>>>> On Tue, Jun 08, 2010 at 07:28:27PM -0300, salsaman wrote:
>>>> >    Please check back in this thread. I asked how to tell if we are
>>>> dealing
>>>> >    with a stream or a file, and I was told to use stream_Control(
>>>> stream_t *,
>>>> >    STREAM_CAN_SEEK, &boolean );
>>>>
>>>> Hi,
>>>>
>>>> You don't really need to know if access has file or stream coming in do
>>>> you? Seems that you just need to know if it can be seeked (fast in this
>>>> case seems like the info you need ) so STREAM_CAN_FASTSEEK would tell
>>>> you if
>>>> seeking is really a fast one (like local files etc) or not (not able to
>>>> seek, or slow seek like in http-case).
>>>>
>>>> I think there could be still seeking problem even with local files. I
>>>> tried that elephantsdream as local file, and it behaved same as behind
>>>> http, so maybe patch is missing some boundary limit, or I just had some
>>>> other problem in that case. I'll try to test more tonight.
>>>>
>>>> --
>>>> Ilkka Ollakka
>>>> "I've seen, I SAY, I've seen better heads on a mug of beer"
>>>>                -- Senator Claghorn
>>>>
>>>> _______________________________________________
>>>> vlc-devel mailing list
>>>> To unsubscribe or modify your subscription options:
>>>> http://mailman.videolan.org/listinfo/vlc-devel
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.videolan.org/pipermail/vlc-devel/attachments/20100609/67195d8c/attachment.html>