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                         p_sys->i_length = __MAX( p_sys->i_length, (i_length - VLC_TICK_0) / 1000000 );
 289                     break;
 290                 }
 291             }
 292             if ( i_length > VLC_TICK_INVALID ) break;
 293         }
 294
 295         /* We found at least a page with valid granule */
 296         if ( i_length > VLC_TICK_INVALID ) break;
 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 if ( current.i_timestamp > i_targettime )
 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 / INT64_C(8000000);
 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     return VLC_SUCCESS;
 868 }
 869
 870 int Oggseek_SeektoAbsolutetime( demux_t *p_demux, logical_stream_t *p_stream,
 871                                 vlc_tick_t i_time )
 872 {
 873     demux_sys_t *p_sys  = p_demux->p_sys;
 874
 875     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Absolute Time %"PRId64, i_time ) );
 876     int64_t i_offset_lower = -1;
 877     int64_t i_offset_upper = -1;
 878
 879     if ( Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_offset_lower, &i_offset_upper ) )
 880     {
 881         /* Exact match */
 882         OggDebug( msg_Dbg( p_demux, "Found keyframe at %"PRId64" using skeleton index", i_offset_lower ) );
 883         if ( i_offset_lower == -1 ) i_offset_lower = p_stream->i_data_start;
 884         p_sys->i_input_position = i_offset_lower;
 885         seek_byte( p_demux, p_sys->i_input_position );
 886         ogg_stream_reset( &p_stream->os );
 887         return i_offset_lower;
 888     }
 889     OggDebug( msg_Dbg( p_demux, "Search bounds set to %"PRId64" %"PRId64" using skeleton index", i_offset_lower, i_offset_upper ) );
 890
 891     OggNoDebug(
 892         OggSeekIndexFind( p_stream, i_time, &i_offset_lower, &i_offset_upper )
 893     );
 894
 895     i_offset_lower = __MAX( i_offset_lower, p_stream->i_data_start );
 896     i_offset_upper = __MIN( i_offset_upper, p_sys->i_total_length );
 897
 898     int64_t i_pagepos = OggBisectSearchByTime( p_demux, p_stream, i_time,
 899                                        i_offset_lower, i_offset_upper);
 900     if ( i_pagepos >= 0 )
 901     {
 902         /* be sure to clear any state or read+pagein() will fail on same # */
 903         ogg_stream_reset( &p_stream->os );
 904         p_sys->i_input_position = i_pagepos;
 905         seek_byte( p_demux, p_sys->i_input_position );
 906     }
 907     /* Insert keyframe position into index */
 908     OggNoDebug(
 909     if ( i_pagepos >= p_stream->i_data_start )
 910         OggSeek_IndexAdd( p_stream, i_time, i_pagepos )
 911     );
 912
 913     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" time %"PRId64, i_pagepos, i_time ) );
 914     return i_pagepos;
 915 }
 916
 917 /****************************************************************************
 918  * oggseek_read_page: Read a full Ogg page from the physical bitstream.
 919  ****************************************************************************
 920  * Returns number of bytes read. This should always be > 0
 921  * unless we are at the end of stream.
 922  *
 923  ****************************************************************************/
 924
 925 int64_t oggseek_read_page( demux_t *p_demux )
 926 {
 927     demux_sys_t *p_ogg = p_demux->p_sys  ;
 928     uint8_t header[PAGE_HEADER_BYTES+255];
 929     int i_nsegs;
 930     int i;
 931     int64_t i_in_pos;
 932     int64_t i_result;
 933     int i_page_size;
 934     char *buf;
 935
 936     demux_sys_t *p_sys  = p_demux->p_sys;
 937
 938     /* store position of this page */
 939     i_in_pos = p_ogg->i_input_position = vlc_stream_Tell( p_demux->s );
 940
 941     if ( p_sys->b_page_waiting) {
 942         msg_Warn( p_demux, "Ogg page already loaded" );
 943         return 0;
 944     }
 945
 946     if ( vlc_stream_Read ( p_demux->s, header, PAGE_HEADER_BYTES ) < PAGE_HEADER_BYTES )
 947     {
 948         vlc_stream_Seek( p_demux->s, i_in_pos );
 949         msg_Dbg ( p_demux, "Reached clean EOF in ogg file" );
 950         return 0;
 951     }
 952
 953     i_nsegs = header[ PAGE_HEADER_BYTES - 1 ];
 954
 955     if ( vlc_stream_Read ( p_demux->s, header+PAGE_HEADER_BYTES, i_nsegs ) < i_nsegs )
 956     {
 957         vlc_stream_Seek( p_demux->s, i_in_pos );
 958         msg_Warn ( p_demux, "Reached broken EOF in ogg file" );
 959         return 0;
 960     }
 961
 962     i_page_size = PAGE_HEADER_BYTES + i_nsegs;
 963
 964     for ( i = 0; i < i_nsegs; i++ )
 965     {
 966         i_page_size += header[ PAGE_HEADER_BYTES + i ];
 967     }
 968
 969     ogg_sync_reset( &p_ogg->oy );
 970
 971     buf = ogg_sync_buffer( &p_ogg->oy, i_page_size );
 972
 973     memcpy( buf, header, PAGE_HEADER_BYTES + i_nsegs );
 974
 975     i_result = vlc_stream_Read ( p_demux->s, (uint8_t*)buf + PAGE_HEADER_BYTES + i_nsegs,
 976                              i_page_size - PAGE_HEADER_BYTES - i_nsegs );
 977
 978     ogg_sync_wrote( &p_ogg->oy, i_result + PAGE_HEADER_BYTES + i_nsegs );
 979
 980
 981
 982
 983     if ( ogg_sync_pageout( &p_ogg->oy, &p_ogg->current_page ) != 1 )
 984     {
 985         msg_Err( p_demux , "Got invalid packet, read %"PRId64" of %i: %s %"PRId64,
 986                  i_result, i_page_size, buf, i_in_pos );
 987         return 0;
 988     }
 989
 990     return i_result + PAGE_HEADER_BYTES + i_nsegs;
 991 }
 992