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