6defaca2316a9d8d8e4fe2ac703667d378bb70ba
[vlc.git] / modules / demux / oggseek.c
1 /*****************************************************************************
2  * oggseek.c : ogg seeking functions for ogg demuxer vlc
3  *****************************************************************************
4  * Copyright (C) 2008 - 2010 Gabriel Finch <salsaman@gmail.com>
5  *
6  * Authors: Gabriel Finch <salsaman@gmail.com>
7  * adapted from: http://lives.svn.sourceforge.net/viewvc/lives/trunk/lives-plugins
8  * /plugins/decoders/ogg_theora_decoder.c
9  *
10  * This program is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this program; if not, write to the Free Software Foundation,
22  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
23  *****************************************************************************/
24
25 /*****************************************************************************
26  * Preamble
27  *****************************************************************************/
28
29 #ifdef HAVE_CONFIG_H
30 # include "config.h"
31 #endif
32
33 #ifdef HAVE_LIBVORBIS
34   #include <vorbis/codec.h>
35 #endif
36
37 #include <vlc_common.h>
38 #include <vlc_demux.h>
39
40 #include <ogg/ogg.h>
41 #include <limits.h>
42
43 #include <assert.h>
44
45 #include "ogg.h"
46 #include "oggseek.h"
47 #include "ogg_granule.h"
48
49 #define SEGMENT_NOT_FOUND -1
50
51 #define MAX_PAGE_SIZE 65307
52 typedef struct packetStartCoordinates
53 {
54     int64_t i_pos;
55     int64_t i_pageno;
56     int64_t i_skip;
57 } packetStartCoordinates;
58
59 /************************************************************
60 * index entries
61 *************************************************************/
62
63 /* free all entries in index list */
64
65 void oggseek_index_entries_free ( demux_index_entry_t *idx )
66 {
67     demux_index_entry_t *idx_next;
68
69     while ( idx != NULL )
70     {
71         idx_next = idx->p_next;
72         free( idx );
73         idx = idx_next;
74     }
75 }
76
77
78 /* internal function to create a new list member */
79
80 static demux_index_entry_t *index_entry_new( void )
81 {
82     demux_index_entry_t *idx = xmalloc( sizeof( demux_index_entry_t ) );
83     if ( !idx ) return NULL;
84     idx->p_next = idx->p_prev = NULL;
85     idx->i_pagepos_end = -1;
86     return idx;
87 }
88
89 /* We insert into index, sorting by pagepos (as a page can match multiple
90    time stamps) */
91 const demux_index_entry_t *OggSeek_IndexAdd ( logical_stream_t *p_stream,
92                                              vlc_tick_t i_timestamp,
93                                              int64_t i_pagepos )
94 {
95     demux_index_entry_t *idx;
96     demux_index_entry_t *last_idx = NULL;
97
98     if ( p_stream == NULL ) return NULL;
99
100     idx = p_stream->idx;
101
102     if ( i_timestamp == VLC_TICK_INVALID || i_pagepos < 1 ) return NULL;
103
104     if ( idx == NULL )
105     {
106         demux_index_entry_t *ie = index_entry_new();
107         if ( !ie ) return NULL;
108         ie->i_value = i_timestamp;
109         ie->i_pagepos = i_pagepos;
110         p_stream->idx = ie;
111         return ie;
112     }
113
114     while ( idx != NULL )
115     {
116         if ( idx->i_pagepos > i_pagepos ) break;
117         last_idx = idx;
118         idx = idx->p_next;
119     }
120
121     /* new entry; insert after last_idx */
122     idx = index_entry_new();
123     if ( !idx ) return NULL;
124     if ( last_idx != NULL )
125     {
126         idx->p_next = last_idx->p_next;
127         last_idx->p_next = idx;
128         idx->p_prev = last_idx;
129     }
130     else
131     {
132         idx->p_next = p_stream->idx;
133         p_stream->idx = idx;
134     }
135
136     if ( idx->p_next != NULL )
137     {
138         idx->p_next->p_prev = idx;
139     }
140
141     idx->i_value = i_timestamp;
142     idx->i_pagepos = i_pagepos;
143
144     return idx;
145 }
146
147 static bool OggSeekIndexFind ( logical_stream_t *p_stream, vlc_tick_t i_timestamp,
148                                int64_t *pi_pos_lower, int64_t *pi_pos_upper )
149 {
150     demux_index_entry_t *idx = p_stream->idx;
151
152     while ( idx != NULL )
153     {
154         if ( idx->i_value <= i_timestamp )
155         {
156             if ( !idx->p_next ) /* found on last index */
157             {
158                 *pi_pos_lower = idx->i_pagepos;
159                 return true;
160             }
161             if ( idx->p_next->i_value > i_timestamp )
162             {
163                 *pi_pos_lower = idx->i_pagepos;
164                 *pi_pos_upper = idx->p_next->i_pagepos;
165                 return true;
166             }
167         }
168         idx = idx->p_next;
169     }
170
171     return false;
172 }
173
174 /*********************************************************************
175  * private functions
176  **********************************************************************/
177
178 /* seek in ogg file to offset i_pos and update the sync */
179
180 static void seek_byte( demux_t *p_demux, int64_t i_pos )
181 {
182     demux_sys_t *p_sys  = p_demux->p_sys;
183
184     if ( ! vlc_stream_Seek( p_demux->s, i_pos ) )
185     {
186         ogg_sync_reset( &p_sys->oy );
187
188         p_sys->i_input_position = i_pos;
189         p_sys->b_page_waiting = false;
190     }
191 }
192
193
194
195 /* read bytes from the ogg file to try to find a page start */
196
197 static int64_t get_data( demux_t *p_demux, int64_t i_bytes_to_read )
198 {
199     demux_sys_t *p_sys  = p_demux->p_sys;
200
201     char *buf;
202     int64_t i_result;
203
204     if ( p_sys->i_total_length > 0 )
205     {
206         if ( p_sys->i_input_position + i_bytes_to_read > p_sys->i_total_length )
207         {
208             i_bytes_to_read = p_sys->i_total_length - p_sys->i_input_position;
209             if ( i_bytes_to_read <= 0 ) {
210                 return 0;
211             }
212         }
213     }
214
215     i_bytes_to_read = __MIN( i_bytes_to_read, INT_MAX );
216
217     seek_byte ( p_demux, p_sys->i_input_position );
218
219     buf = ogg_sync_buffer( &p_sys->oy, i_bytes_to_read );
220
221     i_result = vlc_stream_Read( p_demux->s, buf, i_bytes_to_read );
222
223     ogg_sync_wrote( &p_sys->oy, i_result );
224     return i_result;
225 }
226
227
228 void Oggseek_ProbeEnd( demux_t *p_demux )
229 {
230     /* Temporary state */
231     ogg_stream_state os;
232     ogg_sync_state oy;
233     ogg_page page;
234     demux_sys_t *p_sys = p_demux->p_sys;
235     int64_t i_pos, i_startpos, i_result, i_granule, i_lowerbound;
236     int64_t i_length = 0;
237     int64_t i_backup_pos = vlc_stream_Tell( p_demux->s );
238     int64_t i_upperbound = stream_Size( p_demux->s );
239     unsigned int i_backoffset = OGGSEEK_BYTES_TO_READ;
240     assert( OGGSEEK_BYTES_TO_READ < UINT_MAX );
241
242     const char *buffer;
243
244     ogg_stream_init( &os, -1 );
245     ogg_sync_init( &oy );
246
247     /* Try to lookup last granule from each logical stream */
248     i_lowerbound = stream_Size( p_demux->s ) - p_sys->i_streams * MAX_PAGE_SIZE * 2;
249     i_lowerbound = __MAX( 0, i_lowerbound );
250
251     i_pos = i_startpos = __MAX( i_lowerbound, i_upperbound - i_backoffset );
252
253     if ( vlc_stream_Seek( p_demux->s, i_pos ) )
254     {
255         ogg_sync_clear( &oy );
256         ogg_stream_clear( &os );
257         return;
258     }
259
260     while( i_pos >= i_lowerbound )
261     {
262
263         while( i_pos < i_upperbound )
264         {
265             if ( oy.unsynced )
266                 i_result = ogg_sync_pageseek( &oy, &page );
267
268             buffer = ogg_sync_buffer( &oy, OGGSEEK_BYTES_TO_READ );
269             if ( buffer == NULL ) goto clean;
270             i_result = vlc_stream_Read( p_demux->s, (void*) buffer, OGGSEEK_BYTES_TO_READ );
271             if ( i_result < 1 ) goto clean;
272             i_pos += i_result;
273             ogg_sync_wrote( &oy, i_result );
274
275             while( ogg_sync_pageout( &oy, &page ) == 1 )
276             {
277                 i_granule = ogg_page_granulepos( &page );
278                 if ( i_granule == -1 ) continue;
279
280                 for ( int i=0; i< p_sys->i_streams; i++ )
281                 {
282                     if ( p_sys->pp_stream[i]->i_serial_no != ogg_page_serialno( &page ) )
283                         continue;
284
285                     i_length = Ogg_GranuleToTime( p_sys->pp_stream[i], i_granule,
286                                                   !p_sys->pp_stream[i]->b_contiguous, false );
287                     if( i_length != VLC_TICK_INVALID )
288                     {
289                         /* We found at least a page with valid granule */
290                         p_sys->i_length = __MAX( p_sys->i_length, SEC_FROM_VLC_TICK(i_length - VLC_TICK_0) );
291                         goto clean;
292                     }
293                     break;
294                 }
295             }
296         }
297
298         /* Otherwise increase read size, starting earlier */
299         if ( i_backoffset <= ( UINT_MAX >> 1 ) )
300         {
301             i_backoffset <<= 1;
302             i_startpos = i_upperbound - i_backoffset;
303         }
304         else
305         {
306             i_startpos -= i_backoffset;
307         }
308         i_pos = i_startpos;
309
310         if ( vlc_stream_Seek( p_demux->s, i_pos ) )
311             break;
312     }
313
314 clean:
315     vlc_stream_Seek( p_demux->s, i_backup_pos );
316
317     ogg_sync_clear( &oy );
318     ogg_stream_clear( &os );
319 }
320
321
322 static int64_t find_first_page_granule( demux_t *p_demux,
323                                 int64_t i_pos1, int64_t i_pos2,
324                                 logical_stream_t *p_stream,
325                                 int64_t *i_granulepos )
326 {
327     int64_t i_result;
328     *i_granulepos = -1;
329     int64_t i_bytes_to_read = i_pos2 - i_pos1 + 1;
330     int64_t i_bytes_read;
331     int64_t i_packets_checked;
332
333     demux_sys_t *p_sys  = p_demux->p_sys;
334
335     ogg_packet op;
336
337     seek_byte( p_demux, i_pos1 );
338
339     if ( i_pos1 == p_stream->i_data_start )
340         return p_sys->i_input_position;
341
342     if ( i_bytes_to_read > OGGSEEK_BYTES_TO_READ ) i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
343
344     while ( 1 )
345     {
346
347         if ( p_sys->i_input_position >= i_pos2 )
348         {
349             /* we reached the end and found no pages */
350             return -1;
351         }
352
353         /* read next chunk */
354         if ( ! ( i_bytes_read = get_data( p_demux, i_bytes_to_read ) ) )
355         {
356             /* EOF */
357             return -1;
358         }
359
360         i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
361
362         i_result = ogg_sync_pageseek( &p_sys->oy, &p_sys->current_page );
363
364         if ( i_result < 0 )
365         {
366             /* found a page, sync to page start */
367             p_sys->i_input_position -= i_result;
368             i_pos1 = p_sys->i_input_position;
369             continue;
370         }
371
372         if ( i_result > 0 || ( i_result == 0 && p_sys->oy.fill > 3 &&
373                                ! strncmp( (char *)p_sys->oy.data, "OggS" , 4 ) ) )
374         {
375             i_pos1 = p_sys->i_input_position;
376             break;
377         }
378
379         p_sys->i_input_position += i_bytes_read;
380
381     };
382
383     seek_byte( p_demux, p_sys->i_input_position );
384     ogg_stream_reset( &p_stream->os );
385
386     while( 1 )
387     {
388
389         if ( p_sys->i_input_position >= i_pos2 )
390         {
391             /* reached the end of the search region and nothing was found */
392             return p_sys->i_input_position;
393         }
394
395         p_sys->b_page_waiting = false;
396
397         if ( ! ( i_result = oggseek_read_page( p_demux ) ) )
398         {
399             /* EOF */
400             return p_sys->i_input_position;
401         }
402
403         // found a page
404         if ( ogg_stream_pagein( &p_stream->os, &p_sys->current_page ) != 0 )
405         {
406             /* page is not for this stream or incomplete */
407             p_sys->i_input_position += i_result;
408             continue;
409         }
410
411         if ( ogg_page_granulepos( &p_sys->current_page ) <= 0 )
412         {
413             /* A negative granulepos means that the packet continues on the
414              * next page => read the next page */
415             p_sys->i_input_position += i_result;
416             continue;
417         }
418
419         i_packets_checked = 0;
420
421         while ( ogg_stream_packetout( &p_stream->os, &op ) > 0 )
422         {
423             i_packets_checked++;
424         }
425
426         if ( i_packets_checked )
427         {
428             *i_granulepos = ogg_page_granulepos( &p_sys->current_page );
429             return i_pos1;
430         }
431
432         /*  -> start of next page */
433         p_sys->i_input_position += i_result;
434         i_pos1 = p_sys->i_input_position;
435     }
436 }
437
438 static bool OggSeekToPacket( demux_t *p_demux, logical_stream_t *p_stream,
439             int64_t i_granulepos, packetStartCoordinates *p_lastpacketcoords,
440             bool b_exact )
441 {
442     ogg_packet op;
443     demux_sys_t *p_sys  = p_demux->p_sys;
444     if ( ogg_stream_pagein( &p_stream->os, &p_sys->current_page ) != 0 )
445         return false;
446     p_sys->b_page_waiting = true;
447     int i=0;
448
449     int64_t itarget_frame = Ogg_GetKeyframeGranule( p_stream, i_granulepos );
450     int64_t iframe = Ogg_GetKeyframeGranule( p_stream, ogg_page_granulepos( &p_sys->current_page ) );
451
452     if ( ! ogg_page_continued( &p_sys->current_page ) )
453     {
454         /* Start of frame, not continued page, but no packet. */
455         p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
456         p_lastpacketcoords->i_pos = p_sys->i_input_position;
457         p_lastpacketcoords->i_skip = 0;
458     }
459
460     if ( b_exact && iframe > itarget_frame )
461     {
462         while( ogg_stream_packetout( &p_stream->os, &op ) > 0 ) {};
463         p_sys->b_page_waiting = false;
464         return false;
465     }
466
467     while( ogg_stream_packetpeek( &p_stream->os, &op ) > 0 )
468     {
469         if ( ( !b_exact || itarget_frame == iframe ) && Ogg_IsKeyFrame( p_stream, &op ) )
470         {
471             OggDebug(
472                 msg_Dbg(p_demux, "** KEYFRAME **" );
473                 msg_Dbg(p_demux, "** KEYFRAME PACKET START pageno %"PRId64" OFFSET %"PRId64" skip %"PRId64" **", p_lastpacketcoords->i_pageno, p_lastpacketcoords->i_pos, p_lastpacketcoords->i_skip );
474                 msg_Dbg(p_demux, "KEYFRAME PACKET IS at pageno %"PRId64" OFFSET %"PRId64" with skip %d packet (%d / %d) ",
475                     ogg_page_pageno( &p_sys->current_page ), p_sys->i_input_position, i, i+1, ogg_page_packets( &p_sys->current_page ) );
476                 DemuxDebug( p_sys->b_seeked = true; )
477             );
478
479             if ( i != 0 ) /* Not continued packet */
480             {
481                 /* We need to handle the case when the packet spans onto N
482                        previous page(s). packetout() will be valid only when
483                        all segments are assembled.
484                        Keyframe flag is only available after assembling last part
485                        (when packetout() becomes valid). We have no way to guess
486                        keyframe at earlier time.
487                     */
488                 p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
489                 p_lastpacketcoords->i_pos = p_sys->i_input_position;
490                 p_lastpacketcoords->i_skip = i;
491             }
492             return true;
493         }
494
495         p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
496         p_lastpacketcoords->i_pos = p_sys->i_input_position;
497         p_lastpacketcoords->i_skip = i + 1;
498         i++;
499         /* remove that packet and go sync to next */
500         ogg_stream_packetout( &p_stream->os, &op );
501     }
502
503     return false;
504 }
505
506 static int64_t OggForwardSeekToFrame( demux_t *p_demux, int64_t i_pos1, int64_t i_pos2,
507                 logical_stream_t *p_stream, int64_t i_granulepos, bool b_fastseek )
508 {
509     int64_t i_result;
510     int64_t i_bytes_to_read;
511     int64_t i_bytes_read;
512
513     demux_sys_t *p_sys  = p_demux->p_sys;
514
515     i_bytes_to_read = i_pos2 - i_pos1 + 1;
516     seek_byte( p_demux, i_pos1 );
517     if ( i_bytes_to_read > OGGSEEK_BYTES_TO_READ ) i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
518
519     OggDebug(
520         msg_Dbg( p_demux, "Probing Fwd %"PRId64" %"PRId64" for granule %"PRId64,
521         i_pos1, i_pos2, i_granulepos );
522     );
523
524     while ( 1 )
525     {
526
527         if ( p_sys->i_input_position >= i_pos2 )
528             return SEGMENT_NOT_FOUND;
529
530         /* read next chunk */
531         if ( ! ( i_bytes_read = get_data( p_demux, i_bytes_to_read ) ) )
532             return SEGMENT_NOT_FOUND;
533
534         i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
535
536         i_result = ogg_sync_pageseek( &p_sys->oy, &p_sys->current_page );
537
538         if ( i_result < 0 )
539         {
540             /* found a page, sync to page start */
541             p_sys->i_input_position -= i_result;
542             i_pos1 = p_sys->i_input_position;
543             continue;
544         }
545
546         if ( i_result > 0 || ( i_result == 0 && p_sys->oy.fill > 3 &&
547                                ! strncmp( (char *)p_sys->oy.data, "OggS" , 4 ) ) )
548         {
549             i_pos1 = p_sys->i_input_position;
550             break;
551         }
552
553         p_sys->i_input_position += i_bytes_read;
554     };
555
556     seek_byte( p_demux, p_sys->i_input_position );
557     ogg_stream_reset( &p_stream->os );
558
559     ogg_packet op;
560     while( ogg_stream_packetout( &p_stream->os, &op ) > 0 ) {};
561
562     packetStartCoordinates lastpacket = { -1, -1, -1 };
563
564     while( 1 )
565     {
566
567         if ( p_sys->i_input_position >= i_pos2 )
568         {
569             /* reached the end of the search region and nothing was found */
570             break;
571         }
572
573         p_sys->b_page_waiting = false;
574
575         if ( ! ( i_result = oggseek_read_page( p_demux ) ) )
576         {
577             /* EOF */
578             break;
579         }
580
581         // found a page
582         if ( p_stream->os.serialno != ogg_page_serialno( &p_sys->current_page ) )
583         {
584             /* page is not for this stream */
585             p_sys->i_input_position += i_result;
586             continue;
587         }
588
589         if ( OggSeekToPacket( p_demux, p_stream, i_granulepos, &lastpacket, b_fastseek ) )
590         {
591             p_sys->i_input_position = lastpacket.i_pos;
592             p_stream->i_skip_frames = 0;
593             return p_sys->i_input_position;
594         }
595
596         /*  -> start of next page */
597         p_sys->i_input_position += i_result;
598     }
599
600     return SEGMENT_NOT_FOUND;
601 }
602
603 static int64_t OggBackwardSeekToFrame( demux_t *p_demux, int64_t i_pos1, int64_t i_pos2,
604                                logical_stream_t *p_stream, int64_t i_granulepos )
605 {
606     int64_t i_result;
607     int64_t i_offset = __MAX( 1 + ( (i_pos2 - i_pos1) >> 1 ), OGGSEEK_BYTES_TO_READ );
608
609 restart:
610
611     OggDebug(
612         msg_Dbg( p_demux, "Probing Back %"PRId64" %"PRId64" for granule %"PRId64,
613         i_pos1, i_pos2, i_granulepos );
614     );
615
616     i_result = OggForwardSeekToFrame( p_demux, i_pos1, i_pos2, p_stream,
617                                       i_granulepos, true );
618
619     if ( i_result == SEGMENT_NOT_FOUND && i_pos1 > p_stream->i_data_start )
620     {
621         i_pos1 = __MAX( p_stream->i_data_start, i_pos1 - i_offset );
622         goto restart;
623     }
624
625     return i_result;
626 }
627
628 /* returns pos */
629 static int64_t OggBisectSearchByTime( demux_t *p_demux, logical_stream_t *p_stream,
630             vlc_tick_t i_targettime, int64_t i_pos_lower, int64_t i_pos_upper)
631 {
632     int64_t i_start_pos;
633     int64_t i_end_pos;
634     int64_t i_segsize;
635
636     struct
637     {
638         int64_t i_pos;
639         vlc_tick_t i_timestamp;
640         int64_t i_granule;
641     } bestlower = { p_stream->i_data_start, VLC_TICK_INVALID, -1 },
642       current = { -1, VLC_TICK_INVALID, -1 },
643       lowestupper = { -1, VLC_TICK_INVALID, -1 };
644
645     demux_sys_t *p_sys  = p_demux->p_sys;
646
647     i_pos_lower = __MAX( i_pos_lower, p_stream->i_data_start );
648     i_pos_upper = __MIN( i_pos_upper, p_sys->i_total_length );
649     if ( i_pos_upper < 0 ) i_pos_upper = p_sys->i_total_length;
650
651     i_start_pos = i_pos_lower;
652     i_end_pos = i_pos_upper;
653
654     i_segsize = ( i_end_pos - i_start_pos + 1 ) >> 1;
655     i_start_pos += i_segsize;
656
657     OggDebug( msg_Dbg(p_demux, "Bisecting for time=%"PRId64" between %"PRId64" and %"PRId64,
658             i_targettime, i_pos_lower, i_pos_upper ) );
659
660     do
661     {
662         /* see if the frame lies in current segment */
663         i_start_pos = __MAX( i_start_pos, i_pos_lower );
664         i_end_pos = __MIN( i_end_pos, i_pos_upper );
665
666         if ( i_start_pos >= i_end_pos )
667         {
668             if ( i_start_pos == i_pos_lower)
669             {
670                 return i_start_pos;
671             }
672             return -1;
673         }
674
675
676         current.i_pos = find_first_page_granule( p_demux,
677                                                  i_start_pos, i_end_pos,
678                                                  p_stream,
679                                                  &current.i_granule );
680
681         current.i_timestamp = Ogg_GranuleToTime( p_stream, current.i_granule,
682                                                  !p_stream->b_contiguous, false );
683
684         if ( current.i_timestamp == VLC_TICK_INVALID && current.i_granule > 0 )
685         {
686             msg_Err( p_demux, "Unmatched granule. New codec ?" );
687             return -1;
688         }
689         else if ( current.i_timestamp < 0 )  /* due to preskip with some codecs */
690         {
691             current.i_timestamp = 0;
692         }
693
694         if ( current.i_pos != -1 && current.i_granule != -1 )
695         {
696             /* found a page */
697
698             if ( current.i_timestamp <= i_targettime )
699             {
700                 /* set our lower bound */
701                 if ( current.i_timestamp > bestlower.i_timestamp )
702                     bestlower = current;
703                 i_start_pos = current.i_pos;
704             }
705             else
706             {
707                 if ( lowestupper.i_timestamp == VLC_TICK_INVALID ||
708                      current.i_timestamp < lowestupper.i_timestamp )
709                     lowestupper = current;
710                 /* check lower half of segment */
711                 i_start_pos -= i_segsize;
712                 i_end_pos -= i_segsize;
713             }
714         }
715         else
716         {
717             /* no keyframe found, check lower segment */
718             i_end_pos -= i_segsize;
719             i_start_pos -= i_segsize;
720         }
721
722         OggDebug( msg_Dbg(p_demux, "Bisect restart i_segsize=%"PRId64" between %"PRId64
723                                    " and %"PRId64 " bl %"PRId64" lu %"PRId64,
724                 i_segsize, i_start_pos, i_end_pos, bestlower.i_granule, lowestupper.i_granule  ) );
725
726         i_segsize = ( i_end_pos - i_start_pos + 1 ) >> 1;
727         i_start_pos += i_segsize;
728
729     } while ( i_segsize > 64 );
730
731     if ( bestlower.i_granule == -1 )
732     {
733         if ( lowestupper.i_granule == -1 )
734             return -1;
735         else
736             bestlower = lowestupper;
737     }
738
739     if ( p_stream->b_oggds )
740     {
741         int64_t a = OggBackwardSeekToFrame( p_demux,
742                 __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ),
743                 bestlower.i_pos,
744                 p_stream, bestlower.i_granule /* unused */ );
745         return a;
746     }
747     /* If not each packet is usable as keyframe, query the codec for keyframe */
748     else if ( Ogg_GetKeyframeGranule( p_stream, bestlower.i_granule ) != bestlower.i_granule )
749     {
750         int64_t i_keyframegranule = Ogg_GetKeyframeGranule( p_stream, bestlower.i_granule );
751
752         OggDebug( msg_Dbg( p_demux, "Need to reseek to keyframe (%"PRId64") granule (%"PRId64"!=%"PRId64") to t=%"PRId64,
753                            i_keyframegranule >> p_stream->i_granule_shift,
754                            bestlower.i_granule,
755                            i_pos_upper,
756                            Ogg_GranuleToTime( p_stream, i_keyframegranule, !p_stream->b_contiguous, false ) ) );
757
758         OggDebug( msg_Dbg( p_demux, "Seeking back to %"PRId64, __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ) ) );
759
760         int64_t a = OggBackwardSeekToFrame( p_demux,
761             __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ),
762             stream_Size( p_demux->s ), p_stream, i_keyframegranule );
763         return a;
764     }
765
766     return bestlower.i_pos;
767 }
768
769
770 /************************************************************************
771  * public functions
772  *************************************************************************/
773
774 int Oggseek_BlindSeektoAbsoluteTime( demux_t *p_demux, logical_stream_t *p_stream,
775                                      vlc_tick_t i_time, bool b_fastseek )
776 {
777     demux_sys_t *p_sys  = p_demux->p_sys;
778     int64_t i_lowerpos = -1;
779     int64_t i_upperpos = -1;
780     bool b_found = false;
781
782     /* Search in skeleton */
783     Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_lowerpos, &i_upperpos );
784     if ( i_lowerpos != -1 ) b_found = true;
785
786     /* And also search in our own index */
787     if ( !b_found && OggSeekIndexFind( p_stream, i_time, &i_lowerpos, &i_upperpos ) )
788     {
789         b_found = true;
790     }
791
792     /* Or try to be smart with audio fixed bitrate streams */
793     if ( !b_found && p_stream->fmt.i_cat == AUDIO_ES && p_sys->i_streams == 1
794          && p_sys->i_bitrate && Ogg_GetKeyframeGranule( p_stream, 0xFF00FF00 ) == 0xFF00FF00 )
795     {
796         /* But only if there's no keyframe/preload requirements */
797         /* FIXME: add function to get preload time by codec, ex: opus */
798         i_lowerpos = VLC_TICK_0 + (i_time - VLC_TICK_0) * p_sys->i_bitrate / (CLOCK_FREQ * 8);
799         b_found = true;
800     }
801
802     /* or search */
803     if ( !b_found && b_fastseek )
804     {
805         i_lowerpos = OggBisectSearchByTime( p_demux, p_stream, i_time,
806                                             p_stream->i_data_start, p_sys->i_total_length );
807         b_found = ( i_lowerpos != -1 );
808     }
809
810     if ( !b_found ) return -1;
811
812     if ( i_lowerpos < p_stream->i_data_start || i_upperpos > p_sys->i_total_length )
813         return -1;
814
815     /* And really do seek */
816     p_sys->i_input_position = i_lowerpos;
817     seek_byte( p_demux, p_sys->i_input_position );
818     ogg_stream_reset( &p_stream->os );
819
820     return i_lowerpos;
821 }
822
823 int Oggseek_BlindSeektoPosition( demux_t *p_demux, logical_stream_t *p_stream,
824                                  double f, bool b_canfastseek )
825 {
826     demux_sys_t *p_sys = p_demux->p_sys;
827     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Blind Pos" ) );
828     int64_t i_size = stream_Size( p_demux->s );
829     uint64_t i_startpos = vlc_stream_Tell( p_demux->s );
830     int64_t i_granule;
831     int64_t i_pagepos;
832
833     i_size = find_first_page_granule( p_demux,
834                                              i_size * f, i_size,
835                                              p_stream,
836                                              &i_granule );
837     if( i_granule == -1 )
838     {
839         if( vlc_stream_Seek( p_demux->s, i_startpos ) != VLC_SUCCESS )
840             msg_Err( p_demux, "Seek back failed. Not seekable ?" );
841         return VLC_EGENERIC;
842     }
843
844     OggDebug( msg_Dbg( p_demux, "Seek start pos is %"PRId64" granule %"PRId64, i_size, i_granule ) );
845
846     i_granule = Ogg_GetKeyframeGranule( p_stream, i_granule );
847
848     if ( b_canfastseek )
849     {
850         /* Peek back until we meet a keyframe to start our decoding up to our
851          * final seek time */
852         i_pagepos = OggBackwardSeekToFrame( p_demux,
853                 __MAX ( i_size - MAX_PAGE_SIZE, p_stream->i_data_start ),
854                 __MIN ( i_size + MAX_PAGE_SIZE, p_sys->i_total_length ),
855                 p_stream, i_granule );
856     }
857     else
858     {
859         /* Otherwise, we just sync to the next keyframe we meet */
860         i_pagepos = OggForwardSeekToFrame( p_demux,
861                 __MAX ( i_size - MAX_PAGE_SIZE, p_stream->i_data_start ),
862                 stream_Size( p_demux->s ),
863                 p_stream, i_granule, false );
864     }
865
866     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" granule %"PRId64, i_pagepos, i_granule ) );
867     (void) i_pagepos;
868     return VLC_SUCCESS;
869 }
870
871 int Oggseek_SeektoAbsolutetime( demux_t *p_demux, logical_stream_t *p_stream,
872                                 vlc_tick_t i_time )
873 {
874     demux_sys_t *p_sys  = p_demux->p_sys;
875
876     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Absolute Time %"PRId64, i_time ) );
877     int64_t i_offset_lower = -1;
878     int64_t i_offset_upper = -1;
879
880     if ( Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_offset_lower, &i_offset_upper ) )
881     {
882         /* Exact match */
883         OggDebug( msg_Dbg( p_demux, "Found keyframe at %"PRId64" using skeleton index", i_offset_lower ) );
884         if ( i_offset_lower == -1 ) i_offset_lower = p_stream->i_data_start;
885         p_sys->i_input_position = i_offset_lower;
886         seek_byte( p_demux, p_sys->i_input_position );
887         ogg_stream_reset( &p_stream->os );
888         return i_offset_lower;
889     }
890     OggDebug( msg_Dbg( p_demux, "Search bounds set to %"PRId64" %"PRId64" using skeleton index", i_offset_lower, i_offset_upper ) );
891
892     OggNoDebug(
893         OggSeekIndexFind( p_stream, i_time, &i_offset_lower, &i_offset_upper )
894     );
895
896     i_offset_lower = __MAX( i_offset_lower, p_stream->i_data_start );
897     i_offset_upper = __MIN( i_offset_upper, p_sys->i_total_length );
898
899     int64_t i_pagepos = OggBisectSearchByTime( p_demux, p_stream, i_time,
900                                        i_offset_lower, i_offset_upper);
901     if ( i_pagepos >= 0 )
902     {
903         /* be sure to clear any state or read+pagein() will fail on same # */
904         ogg_stream_reset( &p_stream->os );
905         p_sys->i_input_position = i_pagepos;
906         seek_byte( p_demux, p_sys->i_input_position );
907     }
908     /* Insert keyframe position into index */
909     OggNoDebug(
910     if ( i_pagepos >= p_stream->i_data_start )
911         OggSeek_IndexAdd( p_stream, i_time, i_pagepos )
912     );
913
914     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" time %"PRId64, i_pagepos, i_time ) );
915     return i_pagepos;
916 }
917
918 /****************************************************************************
919  * oggseek_read_page: Read a full Ogg page from the physical bitstream.
920  ****************************************************************************
921  * Returns number of bytes read. This should always be > 0
922  * unless we are at the end of stream.
923  *
924  ****************************************************************************/
925
926 int64_t oggseek_read_page( demux_t *p_demux )
927 {
928     demux_sys_t *p_ogg = p_demux->p_sys  ;
929     uint8_t header[PAGE_HEADER_BYTES+255];
930     int i_nsegs;
931     int i;
932     int64_t i_in_pos;
933     int64_t i_result;
934     int i_page_size;
935     char *buf;
936
937     demux_sys_t *p_sys  = p_demux->p_sys;
938
939     /* store position of this page */
940     i_in_pos = p_ogg->i_input_position = vlc_stream_Tell( p_demux->s );
941
942     if ( p_sys->b_page_waiting) {
943         msg_Warn( p_demux, "Ogg page already loaded" );
944         return 0;
945     }
946
947     if ( vlc_stream_Read ( p_demux->s, header, PAGE_HEADER_BYTES ) < PAGE_HEADER_BYTES )
948     {
949         vlc_stream_Seek( p_demux->s, i_in_pos );
950         msg_Dbg ( p_demux, "Reached clean EOF in ogg file" );
951         return 0;
952     }
953
954     i_nsegs = header[ PAGE_HEADER_BYTES - 1 ];
955
956     if ( vlc_stream_Read ( p_demux->s, header+PAGE_HEADER_BYTES, i_nsegs ) < i_nsegs )
957     {
958         vlc_stream_Seek( p_demux->s, i_in_pos );
959         msg_Warn ( p_demux, "Reached broken EOF in ogg file" );
960         return 0;
961     }
962
963     i_page_size = PAGE_HEADER_BYTES + i_nsegs;
964
965     for ( i = 0; i < i_nsegs; i++ )
966     {
967         i_page_size += header[ PAGE_HEADER_BYTES + i ];
968     }
969
970     ogg_sync_reset( &p_ogg->oy );
971
972     buf = ogg_sync_buffer( &p_ogg->oy, i_page_size );
973
974     memcpy( buf, header, PAGE_HEADER_BYTES + i_nsegs );
975
976     i_result = vlc_stream_Read ( p_demux->s, (uint8_t*)buf + PAGE_HEADER_BYTES + i_nsegs,
977                              i_page_size - PAGE_HEADER_BYTES - i_nsegs );
978
979     ogg_sync_wrote( &p_ogg->oy, i_result + PAGE_HEADER_BYTES + i_nsegs );
980
981
982
983
984     if ( ogg_sync_pageout( &p_ogg->oy, &p_ogg->current_page ) != 1 )
985     {
986         msg_Err( p_demux , "Got invalid packet, read %"PRId64" of %i: %s %"PRId64,
987                  i_result, i_page_size, buf, i_in_pos );
988         return 0;
989     }
990
991     return i_result + PAGE_HEADER_BYTES + i_nsegs;
992 }
993