git.sesse.net Git - vlc/blob - 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 #include <vlc_common.h>
  34 #include <vlc_demux.h>
  35
  36 #include <ogg/ogg.h>
  37 #include <limits.h>
  38
  39 #include <assert.h>
  40
  41 #include "ogg.h"
  42 #include "oggseek.h"
  43
  44 /* Theora spec 7.1 */
  45 #define THEORA_FTYPE_NOTDATA       0x80
  46 #define THEORA_FTYPE_INTERFRAME    0x40
  47
  48 #define SEGMENT_NOT_FOUND -1
  49
  50 #define MAX_PAGE_SIZE 65307
  51 typedef struct packetStartCoordinates
  52 {
  53     int64_t i_pos;
  54     int64_t i_pageno;
  55     int64_t i_skip;
  56 } packetStartCoordinates;
  57
  58 //#define OGG_SEEK_DEBUG 1
  59 #ifdef OGG_SEEK_DEBUG
  60   #define OggDebug(code) code
  61   #define OggNoDebug(code)
  62 #else
  63   #define OggDebug(code)
  64   #define OggNoDebug(code) code
  65 #endif
  66 /************************************************************
  67 * index entries
  68 *************************************************************/
  69
  70 /* free all entries in index list */
  71
  72 void oggseek_index_entries_free ( demux_index_entry_t *idx )
  73 {
  74     demux_index_entry_t *idx_next;
  75
  76     while ( idx != NULL )
  77     {
  78         idx_next = idx->p_next;
  79         free( idx );
  80         idx = idx_next;
  81     }
  82 }
  83
  84
  85 /* internal function to create a new list member */
  86
  87 static demux_index_entry_t *index_entry_new( void )
  88 {
  89     demux_index_entry_t *idx = xmalloc( sizeof( demux_index_entry_t ) );
  90     if ( !idx ) return NULL;
  91     idx->p_next = idx->p_prev = NULL;
  92     idx->i_pagepos_end = -1;
  93     return idx;
  94 }
  95
  96
  97
  98 /* add a theora entry to our list; format is highest granulepos -> page offset of
  99    keyframe start */
 100
 101 const demux_index_entry_t *oggseek_theora_index_entry_add ( logical_stream_t *p_stream,
 102                                                             int64_t i_granule,
 103                                                             int64_t i_pagepos)
 104 {
 105     /* add or update entry for keyframe */
 106     demux_index_entry_t *idx;
 107     demux_index_entry_t *oidx;
 108     demux_index_entry_t *last_idx = NULL;
 109     int64_t i_gpos;
 110     int64_t i_frame;
 111     int64_t i_kframe;
 112     int64_t i_tframe;
 113     int64_t i_tkframe;
 114
 115     if ( p_stream == NULL ) return NULL;
 116
 117     oidx = idx = p_stream->idx;
 118
 119     i_tkframe = i_granule >> p_stream->i_granule_shift;
 120     i_tframe = i_tkframe + i_granule - ( i_tkframe << p_stream->i_granule_shift );
 121
 122     if ( i_tkframe < 1 ) return NULL;
 123
 124     if ( idx == NULL )
 125     {
 126         demux_index_entry_t *ie = index_entry_new();
 127         ie->i_value = i_granule;
 128         ie->i_pagepos = i_pagepos;
 129         p_stream->idx = ie;
 130         return ie;
 131     }
 132
 133
 134     while ( idx != NULL )
 135     {
 136         i_gpos = idx->i_value;
 137
 138         i_kframe = i_gpos >> p_stream->i_granule_shift;
 139         if ( i_kframe > i_tframe ) break;
 140
 141         if ( i_kframe == i_tkframe )
 142         {
 143             /* entry exists, update it if applicable, and return it */
 144             i_frame = i_kframe + i_gpos - ( i_kframe << p_stream->i_granule_shift );
 145             if ( i_frame < i_tframe )
 146             {
 147                 idx->i_value = i_granule;
 148                 idx->i_pagepos = i_pagepos;
 149             }
 150
 151             return idx;
 152         }
 153
 154         last_idx = idx;
 155         idx = idx->p_next;
 156     }
 157
 158
 159     /* new entry; insert after last_idx */
 160
 161     idx = index_entry_new();
 162
 163     if ( last_idx != NULL )
 164     {
 165         idx->p_next = last_idx->p_next;
 166         last_idx->p_next = idx;
 167         idx->p_prev = last_idx;
 168     }
 169     else
 170     {
 171         idx->p_next = oidx;
 172         oidx = idx;
 173     }
 174
 175     if ( idx->p_next != NULL )
 176     {
 177         idx->p_next->p_prev = idx;
 178     }
 179
 180     idx->i_value = i_granule;
 181     idx->i_pagepos = i_pagepos;
 182
 183     return idx;
 184 }
 185
 186 /* We insert into index, sorting by pagepos (as a page can match multiple
 187    time stamps) */
 188 const demux_index_entry_t *OggSeek_IndexAdd ( logical_stream_t *p_stream,
 189                                              int64_t i_timestamp,
 190                                              int64_t i_pagepos )
 191 {
 192     demux_index_entry_t *idx;
 193     demux_index_entry_t *oidx;
 194     demux_index_entry_t *last_idx = NULL;
 195
 196     if ( p_stream == NULL ) return NULL;
 197
 198     oidx = idx = p_stream->idx;
 199
 200     if ( i_timestamp < 1 || i_pagepos < 1 ) return NULL;
 201
 202     if ( idx == NULL )
 203     {
 204         demux_index_entry_t *ie = index_entry_new();
 205         if ( !ie ) return NULL;
 206         ie->i_value = i_timestamp;
 207         ie->i_pagepos = i_pagepos;
 208         p_stream->idx = ie;
 209         return ie;
 210     }
 211
 212     while ( idx != NULL )
 213     {
 214         if ( idx->i_pagepos > i_pagepos ) break;
 215         last_idx = idx;
 216         idx = idx->p_next;
 217     }
 218
 219     /* new entry; insert after last_idx */
 220     idx = index_entry_new();
 221     if ( !idx ) return NULL;
 222     if ( last_idx != NULL )
 223     {
 224         idx->p_next = last_idx->p_next;
 225         last_idx->p_next = idx;
 226         idx->p_prev = last_idx;
 227     }
 228     else
 229     {
 230         idx->p_next = oidx;
 231         oidx = idx;
 232     }
 233
 234     if ( idx->p_next != NULL )
 235     {
 236         idx->p_next->p_prev = idx;
 237     }
 238
 239     idx->i_value = i_timestamp;
 240     idx->i_pagepos = i_pagepos;
 241
 242     return idx;
 243 }
 244
 245 static bool OggSeekIndexFind ( logical_stream_t *p_stream, int64_t i_timestamp,
 246                                int64_t *pi_pos_lower, int64_t *pi_pos_upper )
 247 {
 248     demux_index_entry_t *idx = p_stream->idx;
 249
 250     while ( idx != NULL )
 251     {
 252         if ( idx->i_value <= i_timestamp )
 253         {
 254             if ( !idx->p_next ) /* found on last index */
 255             {
 256                 *pi_pos_lower = idx->i_pagepos;
 257                 return true;
 258             }
 259             if ( idx->p_next->i_value > i_timestamp )
 260             {
 261                 *pi_pos_lower = idx->i_pagepos;
 262                 *pi_pos_upper = idx->p_next->i_pagepos;
 263                 return true;
 264             }
 265         }
 266         idx = idx->p_next;
 267     }
 268
 269     return false;
 270 }
 271
 272 /*********************************************************************
 273  * private functions
 274  **********************************************************************/
 275
 276 /* seek in ogg file to offset i_pos and update the sync */
 277
 278 static void seek_byte( demux_t *p_demux, int64_t i_pos )
 279 {
 280     demux_sys_t *p_sys  = p_demux->p_sys;
 281
 282     if ( ! stream_Seek( p_demux->s, i_pos ) )
 283     {
 284         ogg_sync_reset( &p_sys->oy );
 285
 286         p_sys->i_input_position = i_pos;
 287         p_sys->b_page_waiting = false;
 288     }
 289 }
 290
 291
 292
 293 /* read bytes from the ogg file to try to find a page start */
 294
 295 static int64_t get_data( demux_t *p_demux, int64_t i_bytes_to_read )
 296 {
 297     demux_sys_t *p_sys  = p_demux->p_sys;
 298
 299     char *buf;
 300     int64_t i_result;
 301
 302     if ( p_sys->i_total_length > 0 )
 303     {
 304         if ( p_sys->i_input_position + i_bytes_to_read > p_sys->i_total_length )
 305         {
 306             i_bytes_to_read = p_sys->i_total_length - p_sys->i_input_position;
 307             if ( i_bytes_to_read <= 0 ) {
 308                 return 0;
 309             }
 310         }
 311     }
 312
 313     i_bytes_to_read = __MIN( i_bytes_to_read, INT_MAX );
 314
 315     seek_byte ( p_demux, p_sys->i_input_position );
 316
 317     buf = ogg_sync_buffer( &p_sys->oy, i_bytes_to_read );
 318
 319     i_result = stream_Read( p_demux->s, buf, i_bytes_to_read );
 320
 321     p_sys->b_page_waiting = false;
 322
 323     ogg_sync_wrote( &p_sys->oy, i_result );
 324     return i_result;
 325 }
 326
 327
 328 void Oggseek_ProbeEnd( demux_t *p_demux )
 329 {
 330     /* Temporary state */
 331     ogg_stream_state os;
 332     ogg_sync_state oy;
 333     ogg_page page;
 334     demux_sys_t *p_sys = p_demux->p_sys;
 335     int64_t i_pos, i_startpos, i_result, i_granule, i_lowerbound;
 336     int64_t i_length = 0;
 337     int64_t i_backup_pos = stream_Tell( p_demux->s );
 338     int64_t i_upperbound = stream_Size( p_demux->s );
 339     unsigned int i_backoffset = OGGSEEK_BYTES_TO_READ;
 340     assert( OGGSEEK_BYTES_TO_READ < UINT_MAX );
 341
 342     const char *buffer;
 343
 344     ogg_stream_init( &os, -1 );
 345     ogg_sync_init( &oy );
 346
 347     /* Try to lookup last granule from each logical stream */
 348     i_lowerbound = stream_Size( p_demux->s ) - p_sys->i_streams * MAX_PAGE_SIZE * 2;
 349     i_lowerbound = __MAX( 0, i_lowerbound );
 350
 351     i_pos = i_startpos = __MAX( i_lowerbound, i_upperbound - i_backoffset );
 352
 353     if ( stream_Seek( p_demux->s, i_pos ) )
 354     {
 355         ogg_sync_clear( &oy );
 356         ogg_stream_clear( &os );
 357         return;
 358     }
 359
 360     while( i_pos >= i_lowerbound )
 361     {
 362
 363         while( i_pos < i_upperbound )
 364         {
 365             if ( oy.unsynced )
 366                 i_result = ogg_sync_pageseek( &oy, &page );
 367
 368             buffer = ogg_sync_buffer( &oy, OGGSEEK_BYTES_TO_READ );
 369             if ( buffer == NULL ) goto clean;
 370             i_result = stream_Read( p_demux->s, (void*) buffer, OGGSEEK_BYTES_TO_READ );
 371             if ( i_result < 1 ) goto clean;
 372             i_pos += i_result;
 373             ogg_sync_wrote( &oy, i_result );
 374
 375             while( ogg_sync_pageout( &oy, &page ) == 1 )
 376             {
 377                 i_granule = ogg_page_granulepos( &page );
 378                 if ( i_granule == -1 ) continue;
 379
 380                 for ( int i=0; i< p_sys->i_streams; i++ )
 381                 {
 382                     if ( p_sys->pp_stream[i]->i_serial_no != ogg_page_serialno( &page ) )
 383                         continue;
 384
 385                     i_length = Oggseek_GranuleToAbsTimestamp( p_sys->pp_stream[i], i_granule, false );
 386                     p_sys->i_length = __MAX( p_sys->i_length, i_length / 1000000 );
 387                     break;
 388                 }
 389             }
 390             if ( i_length > 0 ) break;
 391         }
 392
 393         /* We found at least a page with valid granule */
 394         if ( i_length > 0 ) break;
 395
 396         /* Otherwise increase read size, starting earlier */
 397         if ( i_backoffset <= ( UINT_MAX >> 1 ) )
 398         {
 399             i_backoffset <<= 1;
 400             i_startpos = i_upperbound - i_backoffset;
 401         }
 402         else
 403         {
 404             i_startpos -= i_backoffset;
 405         }
 406         i_pos = i_startpos;
 407
 408         if ( stream_Seek( p_demux->s, i_pos ) )
 409             break;
 410     }
 411
 412 clean:
 413     stream_Seek( p_demux->s, i_backup_pos );
 414
 415     ogg_sync_clear( &oy );
 416     ogg_stream_clear( &os );
 417 }
 418
 419 /* convert a theora frame to a granulepos */
 420
 421 static inline int64_t frame_to_gpos( logical_stream_t *p_stream, int64_t i_kframe,
 422                                      int64_t i_frame )
 423 {
 424     if ( p_stream->fmt.i_codec == VLC_CODEC_THEORA )
 425     {
 426         return ( i_kframe << p_stream->i_granule_shift ) + ( i_frame - i_kframe );
 427     }
 428
 429     return i_kframe;
 430 }
 431
 432
 433 static int64_t find_first_page_granule( demux_t *p_demux,
 434                                 int64_t i_pos1, int64_t i_pos2,
 435                                 logical_stream_t *p_stream,
 436                                 int64_t *i_granulepos )
 437 {
 438     int64_t i_result;
 439     *i_granulepos = -1;
 440     int64_t i_bytes_to_read = i_pos2 - i_pos1 + 1;
 441     int64_t i_bytes_read;
 442     int64_t i_pages_checked = 0;
 443     int64_t i_packets_checked;
 444
 445     demux_sys_t *p_sys  = p_demux->p_sys;
 446
 447     ogg_packet op;
 448
 449     seek_byte( p_demux, i_pos1 );
 450
 451     if ( i_pos1 == p_stream->i_data_start )
 452     {
 453         p_sys->b_page_waiting = true;
 454         return p_sys->i_input_position;
 455     }
 456
 457     if ( i_bytes_to_read > OGGSEEK_BYTES_TO_READ ) i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
 458
 459     while ( 1 )
 460     {
 461
 462         if ( p_sys->i_input_position >= i_pos2 )
 463         {
 464             /* we reached the end and found no pages */
 465             return -1;
 466         }
 467
 468         /* read next chunk */
 469         if ( ! ( i_bytes_read = get_data( p_demux, i_bytes_to_read ) ) )
 470         {
 471             /* EOF */
 472             return -1;
 473         }
 474
 475         i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
 476
 477         i_result = ogg_sync_pageseek( &p_sys->oy, &p_sys->current_page );
 478
 479         if ( i_result < 0 )
 480         {
 481             /* found a page, sync to page start */
 482             p_sys->i_input_position -= i_result;
 483             i_pos1 = p_sys->i_input_position;
 484             continue;
 485         }
 486
 487         if ( i_result > 0 || ( i_result == 0 && p_sys->oy.fill > 3 &&
 488                                ! strncmp( (char *)p_sys->oy.data, "OggS" , 4 ) ) )
 489         {
 490             i_pos1 = p_sys->i_input_position;
 491             break;
 492         }
 493
 494         p_sys->i_input_position += i_bytes_read;
 495
 496     };
 497
 498     seek_byte( p_demux, p_sys->i_input_position );
 499     ogg_stream_reset( &p_stream->os );
 500
 501     while( 1 )
 502     {
 503
 504         if ( p_sys->i_input_position >= i_pos2 )
 505         {
 506             /* reached the end of the search region and nothing was found */
 507             return p_sys->i_input_position;
 508         }
 509
 510         p_sys->b_page_waiting = false;
 511
 512         if ( ! ( i_result = oggseek_read_page( p_demux ) ) )
 513         {
 514             /* EOF */
 515             return p_sys->i_input_position;
 516         }
 517
 518         // found a page
 519         if ( p_stream->os.serialno != ogg_page_serialno( &p_sys->current_page ) )
 520         {
 521             /* page is not for this stream */
 522             p_sys->i_input_position += i_result;
 523             if ( ! i_pages_checked ) i_pos1 = p_sys->i_input_position;
 524             continue;
 525         }
 526
 527         ogg_stream_pagein( &p_stream->os, &p_sys->current_page );
 528
 529         i_pages_checked++;
 530         i_packets_checked = 0;
 531
 532         if ( ogg_stream_packetout( &p_stream->os, &op ) > 0 )
 533         {
 534             i_packets_checked++;
 535         }
 536
 537         if ( i_packets_checked )
 538         {
 539             *i_granulepos = ogg_page_granulepos( &p_sys->current_page );
 540             p_sys->b_page_waiting = true;
 541             return i_pos1;
 542
 543         }
 544
 545         /*  -> start of next page */
 546         p_sys->i_input_position += i_result;
 547     }
 548 }
 549
 550 /* Checks if current packet matches codec keyframe */
 551 bool Ogg_IsKeyFrame( logical_stream_t *p_stream, ogg_packet *p_packet )
 552 {
 553     if ( p_stream->b_oggds )
 554     {
 555         return ( p_packet->bytes > 0 && p_packet->packet[0] & PACKET_IS_SYNCPOINT );
 556     }
 557     else if ( p_stream->fmt.i_codec == VLC_CODEC_THEORA )
 558     {
 559         if ( p_packet->bytes <= 0 || p_packet->packet[0] & THEORA_FTYPE_NOTDATA )
 560             return false;
 561         else
 562             return !( p_packet->packet[0] & THEORA_FTYPE_INTERFRAME );
 563     }
 564     else if ( p_stream->fmt.i_codec == VLC_CODEC_VP8 )
 565     {
 566         return ( ( ( p_packet->granulepos >> 3 ) & 0x07FFFFFF ) == 0 );
 567     }
 568     return true;
 569 }
 570
 571 int64_t Ogg_GetKeyframeGranule( logical_stream_t *p_stream, int64_t i_granule )
 572 {
 573     if ( p_stream->b_oggds )
 574     {
 575            return -1; /* We have no way to know */
 576     }
 577     else if( p_stream->fmt.i_codec == VLC_CODEC_THEORA )
 578     {
 579         return ( i_granule >> p_stream->i_granule_shift ) << p_stream->i_granule_shift;
 580     }
 581     else if( p_stream->fmt.i_codec == VLC_CODEC_DIRAC )
 582     {
 583         return ( i_granule >> 31 ) << 31;
 584     }
 585     /* No change, that's keyframe or it can't be shifted out (oggds) */
 586     return i_granule;
 587 }
 588
 589 static bool OggSeekToPacket( demux_t *p_demux, logical_stream_t *p_stream,
 590             int64_t i_granulepos, packetStartCoordinates *p_lastpacketcoords,
 591             bool b_exact )
 592 {
 593     ogg_packet op;
 594     demux_sys_t *p_sys  = p_demux->p_sys;
 595     ogg_stream_pagein( &p_stream->os, &p_sys->current_page );
 596     int i=0;
 597
 598     int64_t itarget_frame = Ogg_GetKeyframeGranule( p_stream, i_granulepos );
 599     int64_t iframe = Ogg_GetKeyframeGranule( p_stream, ogg_page_granulepos( &p_sys->current_page ) );
 600
 601     if ( ! ogg_page_continued( &p_sys->current_page ) )
 602     {
 603         /* Start of frame, not continued page, but no packet. */
 604         p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
 605         p_lastpacketcoords->i_pos = p_sys->i_input_position;
 606         p_lastpacketcoords->i_skip = 0;
 607     }
 608
 609     if ( b_exact && iframe > itarget_frame )
 610     {
 611         while( ogg_stream_packetout( &p_stream->os, &op ) > 0 ) {};
 612         return false;
 613     }
 614
 615     while( ogg_stream_packetpeek( &p_stream->os, &op ) > 0 )
 616     {
 617         if ( ( !b_exact || itarget_frame == iframe ) && Ogg_IsKeyFrame( p_stream, &op ) )
 618         {
 619             OggDebug(
 620                 msg_Dbg(p_demux, "** KEYFRAME **" );
 621                 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 );
 622                 msg_Dbg(p_demux, "KEYFRAME PACKET IS at pageno %"PRId64" OFFSET %"PRId64" with skip %d packet (%d / %d) ",
 623                     ogg_page_pageno( &p_sys->current_page ), p_sys->i_input_position, i, i+1, ogg_page_packets( &p_sys->current_page ) );
 624                 DemuxDebug( p_sys->b_seeked = true; )
 625             );
 626
 627             if ( i != 0 ) /* Not continued packet */
 628             {
 629                 /* We need to handle the case when the packet spans onto N
 630                        previous page(s). packetout() will be valid only when
 631                        all segments are assembled.
 632                        Keyframe flag is only available after assembling last part
 633                        (when packetout() becomes valid). We have no way to guess
 634                        keyframe at earlier time.
 635                     */
 636                 p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
 637                 p_lastpacketcoords->i_pos = p_sys->i_input_position;
 638                 p_lastpacketcoords->i_skip = i;
 639             }
 640
 641             return true;
 642         }
 643
 644         p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
 645         p_lastpacketcoords->i_pos = p_sys->i_input_position;
 646         p_lastpacketcoords->i_skip = i + 1;
 647         i++;
 648         /* remove that packet and go sync to next */
 649         ogg_stream_packetout( &p_stream->os, &op );
 650     }
 651     return false;
 652 }
 653
 654 static int64_t OggForwardSeekToFrame( demux_t *p_demux, int64_t i_pos1, int64_t i_pos2,
 655                 logical_stream_t *p_stream, int64_t i_granulepos, bool b_fastseek )
 656 {
 657     int64_t i_result;
 658     int64_t i_bytes_to_read;
 659     int64_t i_bytes_read;
 660
 661     demux_sys_t *p_sys  = p_demux->p_sys;
 662
 663     i_bytes_to_read = i_pos2 - i_pos1 + 1;
 664     seek_byte( p_demux, i_pos1 );
 665     if ( i_bytes_to_read > OGGSEEK_BYTES_TO_READ ) i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
 666
 667     OggDebug(
 668         msg_Dbg( p_demux, "Probing Fwd %"PRId64" %"PRId64" for granule %"PRId64,
 669         i_pos1, i_pos2, i_granulepos );
 670     );
 671
 672     while ( 1 )
 673     {
 674
 675         if ( p_sys->i_input_position >= i_pos2 )
 676             return SEGMENT_NOT_FOUND;
 677
 678         /* read next chunk */
 679         if ( ! ( i_bytes_read = get_data( p_demux, i_bytes_to_read ) ) )
 680             return SEGMENT_NOT_FOUND;
 681
 682         i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
 683
 684         i_result = ogg_sync_pageseek( &p_sys->oy, &p_sys->current_page );
 685
 686         if ( i_result < 0 )
 687         {
 688             /* found a page, sync to page start */
 689             p_sys->i_input_position -= i_result;
 690             i_pos1 = p_sys->i_input_position;
 691             continue;
 692         }
 693
 694         if ( i_result > 0 || ( i_result == 0 && p_sys->oy.fill > 3 &&
 695                                ! strncmp( (char *)p_sys->oy.data, "OggS" , 4 ) ) )
 696         {
 697             i_pos1 = p_sys->i_input_position;
 698             break;
 699         }
 700
 701         p_sys->i_input_position += i_bytes_read;
 702     };
 703
 704     seek_byte( p_demux, p_sys->i_input_position );
 705     ogg_stream_reset( &p_stream->os );
 706
 707     packetStartCoordinates lastpacket = { -1, -1, -1 };
 708
 709     while( 1 )
 710     {
 711
 712         if ( p_sys->i_input_position >= i_pos2 )
 713         {
 714             /* reached the end of the search region and nothing was found */
 715             break;
 716         }
 717
 718         p_sys->b_page_waiting = false;
 719
 720         if ( ! ( i_result = oggseek_read_page( p_demux ) ) )
 721         {
 722             /* EOF */
 723             break;
 724         }
 725
 726         // found a page
 727         if ( p_stream->os.serialno != ogg_page_serialno( &p_sys->current_page ) )
 728         {
 729             /* page is not for this stream */
 730             p_sys->i_input_position += i_result;
 731             continue;
 732         }
 733
 734         if ( OggSeekToPacket( p_demux, p_stream, i_granulepos, &lastpacket, b_fastseek ) )
 735         {
 736             p_sys->i_input_position = lastpacket.i_pos;
 737             p_stream->i_skip_frames = 0;
 738             p_sys->b_page_waiting = true;
 739             return p_sys->i_input_position;
 740         }
 741
 742         /*  -> start of next page */
 743         p_sys->i_input_position += i_result;
 744     }
 745
 746     return SEGMENT_NOT_FOUND;
 747 }
 748
 749 static int64_t OggBackwardSeekToFrame( demux_t *p_demux, int64_t i_pos1, int64_t i_pos2,
 750                                logical_stream_t *p_stream, int64_t i_granulepos )
 751 {
 752     int64_t i_result;
 753     int64_t i_offset = __MAX( 1 + ( (i_pos2 - i_pos1) >> 1 ), OGGSEEK_BYTES_TO_READ );
 754
 755 restart:
 756
 757     OggDebug(
 758         msg_Dbg( p_demux, "Probing Back %"PRId64" %"PRId64" for granule %"PRId64,
 759         i_pos1, i_pos2, i_granulepos );
 760     );
 761
 762     i_result = OggForwardSeekToFrame( p_demux, i_pos1, i_pos2, p_stream,
 763                                       i_granulepos, true );
 764
 765     if ( i_result == SEGMENT_NOT_FOUND && i_pos1 > p_stream->i_data_start )
 766     {
 767         i_pos1 = __MAX( p_stream->i_data_start, i_pos1 - i_offset );
 768         goto restart;
 769     }
 770
 771     return i_result;
 772 }
 773
 774 /* Dont use b_presentation with frames granules ! */
 775 int64_t Oggseek_GranuleToAbsTimestamp( logical_stream_t *p_stream,
 776                                        int64_t i_granule, bool b_presentation )
 777 {
 778     int64_t i_timestamp = -1;
 779
 780     if ( p_stream->b_oggds )
 781     {
 782         i_timestamp = i_granule * CLOCK_FREQ / p_stream->f_rate;
 783     }
 784     else if( p_stream->fmt.i_codec == VLC_CODEC_THEORA ||
 785         p_stream->fmt.i_codec == VLC_CODEC_KATE )
 786     {
 787         ogg_int64_t iframe = i_granule >> p_stream->i_granule_shift;
 788         ogg_int64_t pframe = i_granule - ( iframe << p_stream->i_granule_shift );
 789         /* See Theora A.2.3 */
 790         if ( b_presentation ) pframe -= p_stream->i_keyframe_offset;
 791         i_timestamp = ( iframe + pframe ) * CLOCK_FREQ / p_stream->f_rate;
 792     }
 793     else if ( p_stream->fmt.i_codec == VLC_CODEC_VP8 )
 794     {
 795         ogg_int64_t frame = i_granule >> p_stream->i_granule_shift;
 796         if ( b_presentation ) frame--;
 797         i_timestamp = frame * CLOCK_FREQ / p_stream->f_rate;
 798     }
 799     else if( p_stream->fmt.i_codec == VLC_CODEC_DIRAC )
 800     {
 801         ogg_int64_t i_dts = i_granule >> 31;
 802         /* NB, OggDirac granulepos values are in units of 2*picturerate */
 803         i_timestamp = (i_dts/2) * CLOCK_FREQ / p_stream->f_rate;
 804     }
 805     else if( p_stream->fmt.i_codec == VLC_CODEC_OPUS )
 806     {
 807         i_timestamp = ( i_granule - p_stream->i_pre_skip ) * CLOCK_FREQ / 48000;
 808     }
 809     else if( p_stream->fmt.i_codec == VLC_CODEC_VORBIS )
 810     {
 811         i_timestamp = i_granule * CLOCK_FREQ / p_stream->f_rate;
 812     }
 813
 814     return i_timestamp;
 815 }
 816
 817 bool Oggseek_PacketPCRFixup( logical_stream_t *p_stream, ogg_page *p_page,
 818                              ogg_packet *p_packet )
 819 {
 820     if ( p_packet->granulepos != -1 )
 821         return false;
 822     else
 823     if ( p_stream->b_oggds )
 824     {
 825         p_stream->i_pcr = Oggseek_GranuleToAbsTimestamp( p_stream,
 826                 ogg_page_granulepos( p_page ), true );
 827         return true;
 828     }
 829     else if ( p_stream->fmt.i_codec == VLC_CODEC_THEORA )
 830     {
 831         p_stream->i_pcr = Oggseek_GranuleToAbsTimestamp( p_stream,
 832                                         ogg_page_granulepos( p_page ), false );
 833         /* Computes the presentation time of the first packet on page */
 834         p_stream->i_pcr -= CLOCK_FREQ *
 835                 ogg_page_packets( p_page ) / p_stream->f_rate;
 836         return true;
 837     }
 838     else if ( p_stream->fmt.i_codec == VLC_CODEC_VP8 )
 839     {
 840         ogg_int64_t frame = ogg_page_granulepos( p_page ) >> p_stream->i_granule_shift;
 841         frame -= ogg_page_packets( p_page );
 842         p_stream->i_pcr = frame * CLOCK_FREQ / p_stream->f_rate;
 843     }
 844
 845     return false;
 846 }
 847
 848 /* returns pos */
 849 static int64_t OggBisectSearchByTime( demux_t *p_demux, logical_stream_t *p_stream,
 850             int64_t i_targettime, int64_t i_pos_lower, int64_t i_pos_upper)
 851 {
 852     int64_t i_start_pos;
 853     int64_t i_end_pos;
 854     int64_t i_segsize;
 855
 856     struct
 857     {
 858         int64_t i_pos;
 859         int64_t i_timestamp;
 860         int64_t i_granule;
 861     } bestlower = { p_stream->i_data_start, -1, -1 },
 862       current = { -1, -1, -1 };
 863
 864     demux_sys_t *p_sys  = p_demux->p_sys;
 865
 866     i_pos_lower = __MAX( i_pos_lower, p_stream->i_data_start );
 867     i_pos_upper = __MIN( i_pos_upper, p_sys->i_total_length );
 868     if ( i_pos_upper < 0 ) i_pos_upper = p_sys->i_total_length;
 869
 870     i_start_pos = i_pos_lower;
 871     i_end_pos = i_pos_upper;
 872
 873     i_segsize = ( i_end_pos - i_start_pos + 1 ) >> 1;
 874     i_start_pos += i_segsize;
 875
 876     OggDebug( msg_Dbg(p_demux, "Bisecting for time=%"PRId64" between %"PRId64" and %"PRId64,
 877             i_targettime, i_pos_lower, i_pos_upper ) );
 878
 879     do
 880     {
 881         /* see if the frame lies in current segment */
 882         i_start_pos = __MAX( i_start_pos, i_pos_lower );
 883         i_end_pos = __MIN( i_end_pos, i_pos_upper );
 884
 885         if ( i_start_pos >= i_end_pos )
 886         {
 887             if ( i_start_pos == i_pos_lower)
 888             {
 889                 return i_start_pos;
 890             }
 891             return -1;
 892         }
 893
 894
 895         current.i_pos = find_first_page_granule( p_demux,
 896                                                  i_start_pos, i_end_pos,
 897                                                  p_stream,
 898                                                  &current.i_granule );
 899
 900         current.i_timestamp = Oggseek_GranuleToAbsTimestamp( p_stream,
 901                                                              current.i_granule, false );
 902
 903         if ( current.i_timestamp == -1 )
 904         {
 905             msg_Err( p_demux, "Unmatched granule. New codec ?" );
 906             return -1;
 907         }
 908
 909         if ( current.i_pos != -1 && current.i_granule != -1 )
 910         {
 911             /* found a page */
 912
 913             if ( current.i_timestamp <= i_targettime )
 914             {
 915                 /* set our lower bound */
 916                 if ( current.i_timestamp > bestlower.i_timestamp )
 917                     bestlower = current;
 918                 i_start_pos = current.i_pos;
 919             }
 920             else if ( current.i_timestamp > i_targettime )
 921             {
 922                 /* check lower half of segment */
 923                 i_start_pos -= i_segsize;
 924                 i_end_pos -= i_segsize;
 925             }
 926         }
 927         else
 928         {
 929             /* no keyframe found, check lower segment */
 930             i_end_pos -= i_segsize;
 931             i_start_pos -= i_segsize;
 932         }
 933
 934         OggDebug( msg_Dbg(p_demux, "Bisect restart i_segsize=%"PRId64" between %"PRId64" and %"PRId64,
 935                 i_segsize, i_start_pos, i_end_pos ) );
 936
 937         i_segsize = ( i_end_pos - i_start_pos + 1 ) >> 1;
 938         i_start_pos += i_segsize;
 939
 940     } while ( i_segsize > 64 );
 941
 942     if ( bestlower.i_granule == -1 ) return -1;
 943
 944     if ( p_stream->b_oggds )
 945     {
 946         int64_t a = OggBackwardSeekToFrame( p_demux,
 947                 __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ),
 948                 bestlower.i_pos,
 949                 p_stream, bestlower.i_granule /* unused */ );
 950         return a;
 951     }
 952     /* If not each packet is usable as keyframe, query the codec for keyframe */
 953     else if ( Ogg_GetKeyframeGranule( p_stream, bestlower.i_granule ) != bestlower.i_granule )
 954     {
 955         int64_t i_keyframegranule = Ogg_GetKeyframeGranule( p_stream, bestlower.i_granule );
 956
 957         OggDebug( msg_Dbg( p_demux, "Need to reseek to keyframe (%"PRId64") granule (%"PRId64"!=%"PRId64") to t=%"PRId64,
 958                            i_keyframegranule >> p_stream->i_granule_shift,
 959                            bestlower.i_granule,
 960                            i_pos_upper,
 961                            Oggseek_GranuleToAbsTimestamp( p_stream, i_keyframegranule, false ) ) );
 962
 963         OggDebug( msg_Dbg( p_demux, "Seeking back to %"PRId64, __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ) ) );
 964
 965         int64_t a = OggBackwardSeekToFrame( p_demux,
 966             __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ),
 967             stream_Size( p_demux->s ), p_stream, i_keyframegranule );
 968         return a;
 969     }
 970
 971     return bestlower.i_pos;
 972 }
 973
 974
 975 /************************************************************************
 976  * public functions
 977  *************************************************************************/
 978
 979 int Oggseek_BlindSeektoAbsoluteTime( demux_t *p_demux, logical_stream_t *p_stream,
 980                                      int64_t i_time, bool b_fastseek )
 981 {
 982     demux_sys_t *p_sys  = p_demux->p_sys;
 983     int64_t i_lowerpos = -1;
 984     int64_t i_upperpos = -1;
 985     bool b_found = false;
 986
 987     /* Search in skeleton */
 988     Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_lowerpos, &i_upperpos );
 989     if ( i_lowerpos != -1 ) b_found = true;
 990
 991     /* And also search in our own index */
 992     if ( !b_found && OggSeekIndexFind( p_stream, i_time, &i_lowerpos, &i_upperpos ) )
 993     {
 994         b_found = true;
 995     }
 996
 997     /* Or try to be smart with audio fixed bitrate streams */
 998     if ( !b_found && p_stream->fmt.i_cat == AUDIO_ES && p_sys->i_streams == 1
 999          && p_sys->i_bitrate && Ogg_GetKeyframeGranule( p_stream, 0xFF00FF00 ) == 0xFF00FF00 )
1000     {
1001         /* But only if there's no keyframe/preload requirements */
1002         /* FIXME: add function to get preload time by codec, ex: opus */
1003         i_lowerpos = i_time * p_sys->i_bitrate / INT64_C(8000000);
1004         b_found = true;
1005     }
1006
1007     /* or search */
1008     if ( !b_found && b_fastseek )
1009     {
1010         i_lowerpos = OggBisectSearchByTime( p_demux, p_stream, i_time,
1011                                             p_stream->i_data_start, p_sys->i_total_length );
1012         b_found = ( i_lowerpos != -1 );
1013     }
1014
1015     if ( !b_found ) return -1;
1016
1017     if ( i_lowerpos < p_stream->i_data_start || i_upperpos > p_sys->i_total_length )
1018         return -1;
1019
1020     /* And really do seek */
1021     p_sys->i_input_position = i_lowerpos;
1022     seek_byte( p_demux, p_sys->i_input_position );
1023     ogg_stream_reset( &p_stream->os );
1024
1025     return i_lowerpos;
1026 }
1027
1028 int Oggseek_BlindSeektoPosition( demux_t *p_demux, logical_stream_t *p_stream,
1029                                  double f, bool b_canfastseek )
1030 {
1031     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Blind Pos" ) );
1032     int64_t i_size = stream_Size( p_demux->s );
1033     int64_t i_granule;
1034     int64_t i_pagepos;
1035
1036     i_size = find_first_page_granule( p_demux,
1037                                              i_size * f, i_size,
1038                                              p_stream,
1039                                              &i_granule );
1040
1041     OggDebug( msg_Dbg( p_demux, "Seek start pos is %"PRId64" granule %"PRId64, i_size, i_granule ) );
1042
1043     i_granule = Ogg_GetKeyframeGranule( p_stream, i_granule );
1044
1045     if ( b_canfastseek )
1046     {
1047         /* Peek back until we meet a keyframe to start our decoding up to our
1048          * final seek time */
1049         i_pagepos = OggBackwardSeekToFrame( p_demux,
1050                 __MAX ( i_size - MAX_PAGE_SIZE, p_stream->i_data_start ),
1051                 __MIN ( i_size + MAX_PAGE_SIZE, p_demux->p_sys->i_total_length ),
1052                 p_stream, i_granule );
1053     }
1054     else
1055     {
1056         /* Otherwise, we just sync to the next keyframe we meet */
1057         i_pagepos = OggForwardSeekToFrame( p_demux,
1058                 __MAX ( i_size - MAX_PAGE_SIZE, p_stream->i_data_start ),
1059                 stream_Size( p_demux->s ),
1060                 p_stream, i_granule, false );
1061     }
1062
1063     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" granule %"PRId64, i_pagepos, i_granule ) );
1064     return i_pagepos;
1065 }
1066
1067 int Oggseek_SeektoAbsolutetime( demux_t *p_demux, logical_stream_t *p_stream,
1068                                 int64_t i_time )
1069 {
1070     demux_sys_t *p_sys  = p_demux->p_sys;
1071
1072     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Absolute Time %"PRId64, i_time ) );
1073     int64_t i_offset_lower = -1;
1074     int64_t i_offset_upper = -1;
1075
1076     if ( Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_offset_lower, &i_offset_upper ) )
1077     {
1078         /* Exact match */
1079         OggDebug( msg_Dbg( p_demux, "Found keyframe at %"PRId64" using skeleton index", i_offset_lower ) );
1080         if ( i_offset_lower == -1 ) i_offset_lower = p_stream->i_data_start;
1081         p_sys->i_input_position = i_offset_lower;
1082         seek_byte( p_demux, p_sys->i_input_position );
1083         ogg_stream_reset( &p_stream->os );
1084         return i_offset_lower;
1085     }
1086     OggDebug( msg_Dbg( p_demux, "Search bounds set to %"PRId64" %"PRId64" using skeleton index", i_offset_lower, i_offset_upper ) );
1087
1088     OggNoDebug(
1089         OggSeekIndexFind( p_stream, i_time, &i_offset_lower, &i_offset_upper )
1090     );
1091
1092     i_offset_lower = __MAX( i_offset_lower, p_stream->i_data_start );
1093     i_offset_upper = __MIN( i_offset_upper, p_sys->i_total_length );
1094
1095     int64_t i_pagepos = OggBisectSearchByTime( p_demux, p_stream, i_time,
1096                                        i_offset_lower, i_offset_upper);
1097
1098     /* Insert keyframe position into index */
1099     OggNoDebug(
1100     if ( i_pagepos >= p_stream->i_data_start )
1101         OggSeek_IndexAdd( p_stream, i_time, i_pagepos )
1102     );
1103
1104     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" time %"PRId64, i_pagepos, i_time ) );
1105     return i_pagepos;
1106 }
1107
1108 /****************************************************************************
1109  * oggseek_read_page: Read a full Ogg page from the physical bitstream.
1110  ****************************************************************************
1111  * Returns number of bytes read. This should always be > 0
1112  * unless we are at the end of stream.
1113  *
1114  ****************************************************************************/
1115
1116 int64_t oggseek_read_page( demux_t *p_demux )
1117 {
1118     demux_sys_t *p_ogg = p_demux->p_sys  ;
1119     uint8_t header[PAGE_HEADER_BYTES+255];
1120     int i_nsegs;
1121     int i;
1122     int64_t i_in_pos;
1123     int64_t i_result;
1124     int i_page_size;
1125     char *buf;
1126
1127     demux_sys_t *p_sys  = p_demux->p_sys;
1128
1129     /* store position of this page */
1130     i_in_pos = p_ogg->i_input_position = stream_Tell( p_demux->s );
1131
1132     if ( p_sys->b_page_waiting) {
1133         msg_Warn( p_demux, "Ogg page already loaded" );
1134         return 0;
1135     }
1136
1137     if ( stream_Read ( p_demux->s, header, PAGE_HEADER_BYTES ) < PAGE_HEADER_BYTES )
1138     {
1139         stream_Seek( p_demux->s, i_in_pos );
1140         msg_Dbg ( p_demux, "Reached clean EOF in ogg file" );
1141         return 0;
1142     }
1143
1144     i_nsegs = header[ PAGE_HEADER_BYTES - 1 ];
1145
1146     if ( stream_Read ( p_demux->s, header+PAGE_HEADER_BYTES, i_nsegs ) < i_nsegs )
1147     {
1148         stream_Seek( p_demux->s, i_in_pos );
1149         msg_Warn ( p_demux, "Reached broken EOF in ogg file" );
1150         return 0;
1151     }
1152
1153     i_page_size = PAGE_HEADER_BYTES + i_nsegs;
1154
1155     for ( i = 0; i < i_nsegs; i++ )
1156     {
1157         i_page_size += header[ PAGE_HEADER_BYTES + i ];
1158     }
1159
1160     ogg_sync_reset( &p_ogg->oy );
1161
1162     buf = ogg_sync_buffer( &p_ogg->oy, i_page_size );
1163
1164     memcpy( buf, header, PAGE_HEADER_BYTES + i_nsegs );
1165
1166     i_result = stream_Read ( p_demux->s, (uint8_t*)buf + PAGE_HEADER_BYTES + i_nsegs,
1167                              i_page_size - PAGE_HEADER_BYTES - i_nsegs );
1168
1169     ogg_sync_wrote( &p_ogg->oy, i_result + PAGE_HEADER_BYTES + i_nsegs );
1170
1171
1172
1173
1174     if ( ogg_sync_pageout( &p_ogg->oy, &p_ogg->current_page ) != 1 )
1175     {
1176         msg_Err( p_demux , "Got invalid packet, read %"PRId64" of %i: %s %"PRId64,
1177                  i_result, i_page_size, buf, i_in_pos );
1178         return 0;
1179     }
1180
1181     p_sys->b_page_waiting = false;
1182
1183     return i_result + PAGE_HEADER_BYTES + i_nsegs;
1184 }
1185