<br><br>
<br><br><div class="gmail_quote">On Wed, Jun 16, 2010 at 3:03 AM, Gregory Maxwell <span dir="ltr"><<a href="mailto:gmaxwell@gmail.com">gmaxwell@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<div class="im">On Wed, Jun 9, 2010 at 7:04 PM, salsaman <<a href="mailto:salsaman@gmail.com">salsaman@gmail.com</a>> wrote:<br>
> While I am waiting for a reply, I just thought I would explain the search<br>
> algorithm used, so you verify it is very efficient.<br>
><br>
> We create an index on the fly, this index is basically:<br>
> offset in file -> maximum frame number<br>
><br>
> When asked to seek to a particular frame, we first check the index to see if<br>
> we have approximate boundaries for the seek, otherwise we will seek in the<br>
> whole file, from data_start until the end.<br>
><br>
> The area to be searched is divided into two halves. We first check the upper<br>
> half, and get the highest and lowest granulepos. (The granulepos is<br>
> basically keyframe * keyframe_offset + frame offset). If our target frame<br>
> lies in this region we subdivide it into two halves, otherwise we check the<br>
> lower half from earlier. We stop when we have found the keyframe for our<br>
> target frame, or the search region is < minimum_page_size.<br>
<br>
<br>
</div>This sounds like a plain bisection search. You can get faster results<br>
using an interpolated bisection.<br>
<br>
If the current range is 0........10,000 seconds. And 0....100Mbytes<br>
and you want 2500 seconds, you seek to ~25mbytes (minus the average or<br>
maximum page size) because  2500 seconds is 25% of 10000 and 25 is 25%<br>
of 100.<br>
<br>
This is guaranteed to converge just like a bisection search.  You can<br>
optimize this further, becoming closer to bisection as the ranges get<br>
smaller and the variability becomes greater, and biasing more downward<br>
because backward motion is more expensive that forward motion... but<br>
simply using an interpolation in the outer most step can cut several<br>
seeks out of a large file. If the bitrate is very constant (like<br>
audio) it can get your average down to something like three no matter<br>
what the file size is.  (libvorbisfile does this)<br>
<br></blockquote><div><br><br>OK, I will test this, although I think it will improve only the very first search. The way it works currently is that we first seed the index with first and last granulepos (we set a fake keyframe at time==0 and we discover the last keyframe when calculating the file duration). After this we search using the index to get approximate bounds, then using bi-sections. Now imagine if we were seeking to 25%. It would save one iteration on the first search, but we would not discover the information at 50%. So assuming we were seeking randomly, we would have to check 50% later on anyway. But I can see the point - that as we get closer to the predicted point, the probability thet we need that information later decreases.<br>

<br>Anyway I will look into your suggestion. I am not sure how to implement it though, since the current algorithm requires two equally sized areas (upper is checked first - we get first granulepos, if the lower keyframe is too large, we check the lower section; if the lower keyframe is OK we check the upper keyframe and then subdivide and repeat the process). The idea being, we check upper first, since lower is more likely to have been played already, and thus have its data in the index.<br>

<br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Regarding keyframes.  Your text above is concerning me.  You do not<br>
know the granpos of the keyframe covering a particular frame until you<br>
have visited that frame.    The granshift implies a _maximum_ keyframe<br>
interval, but the keyframes can be placed sooner than that as the<br>
encoder desires, and they often are.    It wasn't quite clear to me<br>
that your approach was dealing with this.  I should probably go read<br>
the code.<br>
<br></blockquote><div><br>You are correct. In fact the code makes no assumptions, it only maps frame -> keyframe as it discovers this. Then later if we discover a higher frame that maps to the same keyframe it updates that entry.<br>

<br>In fact, the above is not strictly true, what is mapped is:<br><br>granulepos of highest_frame -> file offset in bytes<br><br>where the file offset is a suitable point to decode the keyframe for highest_frame, since we can get both frame and keyframe from the granulepos. This is ordered by granulepos in a doubly-linked list. When we are asked to find a new frame, we first get approximate bounds from the index, then bisect the remaining search domain.<br>

<br>During playback, we also update any existing entries if we find a higher frame that maps to a keyframe already in the index.<br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">


Normally, In order to do a fully synchronized seek you must first seek<br>
to the desired frame, extract the granpos of its keyframe, seek back<br>
to that point, then decode forward.  If you cache your seeking<br>
requests along the way and use them to hot-start the second search<br>
then you should be able to hit the key frame very quickly in one seek<br>
or so.<br>
<br></blockquote><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
I'd recommend adding both keyframes and non-keyframes to your index<br>
(or keep two indexes in memory, if you're minimizing memory usage and<br>
don't want non-keyframes polluting a finite index) since both can help<br>
constrain the bounds of your future searches, not just ones belonging<br>
to a common keyframe offset. Every seek provides information which<br>
might be useful in the future.<br>
<br></blockquote><div><br>That is precisely what the program does. It stores frame and keyframe in the i_granulpos field, and byte offset for a sync point in the i_pagepos field.<br><br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">


The indexing scheme in ogg index isn't precisely compatible with your<br>
approach, so you won't just be able to load its values into your<br>
index. This is because instead of mapping time->bytes it maps time to<br>
a byte location which is equal to or less than the byte location of<br>
the requested time,  such that the expressed byte-location is<br>
sufficient to perfectly reconstruct the requested time.    It is done<br>
this way so that it will work uniformly across formats with<br>
drastically different reference structures (dirac, theora, vorbis)<br>
without requiring too more per-codec smarts in the applications.<br>
But this also means that 1:00-> byte 1, 2:00->byte 2, 3:00->byte 3 is<br>
a perfectly valid, if useless, index. (since all those byte locations<br>
are sufficient starting points for finding those times.  In the common<br>
(theora keyframe) case the byte location will exactly match the page<br>
which starts the keyframe that you want, but the promise is that it<br>
will only be equal to or less than.<br>
<br>
So instead of copying the ogg skeleton index into your indexes, you<br>
should use it to hot start (choose the position of your first seek)<br>
your existing algorithm.  When everything works well the combination<br>
will give you the absolute minimum number of seeks possible, and when<br>
the index is missing or corrupt you would still always produce correct<br>
results.<br>
<br></blockquote><div><br>Yes, that should work I think.<br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
(the skeleton index also isn't guaranteed to store all (or even most)<br>
possible seek points, otherwise it would grow to enormous sizes, so<br>
you must still have regular seeking logic to get acceptable<br>
granularity)<br>
<br></blockquote><div><br>Actually the memory required is very small. For my index, we have:<br><br>granulepos -> page_offset per keyframe. Since both are int64_t that 16 bytes per keyframe.<br><br>Assuming an average of 8 frames per keyframe that works out at an additional 2 bytes per frame.<br>

<br>Actually if you are generating an index for skeleton, then I would suggest using my code to do so.<br><br><br>As a side note I am now looking into seeking in dirac. The method is somewhat similar except that instead of keyframes we have sync frames. These are frames which follow immediately from a sequence header start. Since the granulepos does not provide this information the algorithm is to first seek for a packet containing a sequence header (byte 4 of the packet == 0x00). Then we rewind the stream to this page and begin decoding until we get a frame number. I added a third field to the index for dirac, i_pagepos end. So we have:<br>

<br>i_pagepos -> sync_frame ->i_pagepos_end<br><br>each region searched is added to the index. If we search a region and no sync frame is found then sync_frame is set to -1, so we do not waste time by searching these regions again. i_pagepos is the byte offset of the start of the page containing the start of the sequence header packet, i_pagepos_end is aligned to the end of the page where we stopped searching. The idea is then, given a target frame, we find a lower bound at the sync_frame <= target_frame. For dirac there is no upper bound (i.e. a frame can be decoded any distance after its sync frame). In practice this distance is generally no more than 3 or 4 frames. Given a region to search we find the first and last sync frames, skipping over any regions which have been negatively searched (sync_frame==-1) and using any positive information (sync_frame>-1). If we get two contiguous regions with -1 sync_frame then these are joined together.<br>

<br>I am also interested to know what you think about my suggestion of adding the CAN_EXACTSEEK flag.<br><br><br>Regards,<br>Gabriel.<br><br><br><br><br><br><br><br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">


<br>
Cheers!<br>
<div><div></div><div class="h5">_______________________________________________<br>
vlc-devel mailing list<br>
To unsubscribe or modify your subscription options:<br>
<a href="http://mailman.videolan.org/listinfo/vlc-devel" target="_blank">http://mailman.videolan.org/listinfo/vlc-devel</a><br>
</div></div></blockquote></div><br>