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     case VLC_CODEC_DAALA: /* Same convention used in daala */
 456         if ( p_packet->bytes <= 0 || p_packet->packet[0] & THEORA_FTYPE_NOTDATA )
 457             return false;
 458         else
 459             return !( p_packet->packet[0] & THEORA_FTYPE_INTERFRAME );
 460     case VLC_CODEC_VP8:
 461         return ( ( ( p_packet->granulepos >> 3 ) & 0x07FFFFFF ) == 0 );
 462     case VLC_CODEC_DIRAC:
 463         return ( p_packet->granulepos & 0xFF8000FF );
 464     default:
 465         return true;
 466     }
 467 }
 468
 469 int64_t Ogg_GetKeyframeGranule( logical_stream_t *p_stream, int64_t i_granule )
 470 {
 471     if ( p_stream->b_oggds )
 472     {
 473            return -1; /* We have no way to know */
 474     }
 475     else if( p_stream->fmt.i_codec == VLC_CODEC_THEORA ||
 476              p_stream->fmt.i_codec == VLC_CODEC_DAALA )
 477     {
 478         return ( i_granule >> p_stream->i_granule_shift ) << p_stream->i_granule_shift;
 479     }
 480     else if( p_stream->fmt.i_codec == VLC_CODEC_DIRAC )
 481     {
 482         return ( i_granule >> 31 ) << 31;
 483     }
 484     /* No change, that's keyframe or it can't be shifted out (oggds) */
 485     return i_granule;
 486 }
 487
 488 static bool OggSeekToPacket( demux_t *p_demux, logical_stream_t *p_stream,
 489             int64_t i_granulepos, packetStartCoordinates *p_lastpacketcoords,
 490             bool b_exact )
 491 {
 492     ogg_packet op;
 493     demux_sys_t *p_sys  = p_demux->p_sys;
 494     if ( ogg_stream_pagein( &p_stream->os, &p_sys->current_page ) != 0 )
 495         return false;
 496     p_sys->b_page_waiting = true;
 497     int i=0;
 498
 499     int64_t itarget_frame = Ogg_GetKeyframeGranule( p_stream, i_granulepos );
 500     int64_t iframe = Ogg_GetKeyframeGranule( p_stream, ogg_page_granulepos( &p_sys->current_page ) );
 501
 502     if ( ! ogg_page_continued( &p_sys->current_page ) )
 503     {
 504         /* Start of frame, not continued page, but no packet. */
 505         p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
 506         p_lastpacketcoords->i_pos = p_sys->i_input_position;
 507         p_lastpacketcoords->i_skip = 0;
 508     }
 509
 510     if ( b_exact && iframe > itarget_frame )
 511     {
 512         while( ogg_stream_packetout( &p_stream->os, &op ) > 0 ) {};
 513         p_sys->b_page_waiting = false;
 514         return false;
 515     }
 516
 517     while( ogg_stream_packetpeek( &p_stream->os, &op ) > 0 )
 518     {
 519         if ( ( !b_exact || itarget_frame == iframe ) && Ogg_IsKeyFrame( p_stream, &op ) )
 520         {
 521             OggDebug(
 522                 msg_Dbg(p_demux, "** KEYFRAME **" );
 523                 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 );
 524                 msg_Dbg(p_demux, "KEYFRAME PACKET IS at pageno %"PRId64" OFFSET %"PRId64" with skip %d packet (%d / %d) ",
 525                     ogg_page_pageno( &p_sys->current_page ), p_sys->i_input_position, i, i+1, ogg_page_packets( &p_sys->current_page ) );
 526                 DemuxDebug( p_sys->b_seeked = true; )
 527             );
 528
 529             if ( i != 0 ) /* Not continued packet */
 530             {
 531                 /* We need to handle the case when the packet spans onto N
 532                        previous page(s). packetout() will be valid only when
 533                        all segments are assembled.
 534                        Keyframe flag is only available after assembling last part
 535                        (when packetout() becomes valid). We have no way to guess
 536                        keyframe at earlier time.
 537                     */
 538                 p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
 539                 p_lastpacketcoords->i_pos = p_sys->i_input_position;
 540                 p_lastpacketcoords->i_skip = i;
 541             }
 542             return true;
 543         }
 544
 545         p_lastpacketcoords->i_pageno = ogg_page_pageno( &p_sys->current_page );
 546         p_lastpacketcoords->i_pos = p_sys->i_input_position;
 547         p_lastpacketcoords->i_skip = i + 1;
 548         i++;
 549         /* remove that packet and go sync to next */
 550         ogg_stream_packetout( &p_stream->os, &op );
 551     }
 552
 553     return false;
 554 }
 555
 556 static int64_t OggForwardSeekToFrame( demux_t *p_demux, int64_t i_pos1, int64_t i_pos2,
 557                 logical_stream_t *p_stream, int64_t i_granulepos, bool b_fastseek )
 558 {
 559     int64_t i_result;
 560     int64_t i_bytes_to_read;
 561     int64_t i_bytes_read;
 562
 563     demux_sys_t *p_sys  = p_demux->p_sys;
 564
 565     i_bytes_to_read = i_pos2 - i_pos1 + 1;
 566     seek_byte( p_demux, i_pos1 );
 567     if ( i_bytes_to_read > OGGSEEK_BYTES_TO_READ ) i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
 568
 569     OggDebug(
 570         msg_Dbg( p_demux, "Probing Fwd %"PRId64" %"PRId64" for granule %"PRId64,
 571         i_pos1, i_pos2, i_granulepos );
 572     );
 573
 574     while ( 1 )
 575     {
 576
 577         if ( p_sys->i_input_position >= i_pos2 )
 578             return SEGMENT_NOT_FOUND;
 579
 580         /* read next chunk */
 581         if ( ! ( i_bytes_read = get_data( p_demux, i_bytes_to_read ) ) )
 582             return SEGMENT_NOT_FOUND;
 583
 584         i_bytes_to_read = OGGSEEK_BYTES_TO_READ;
 585
 586         i_result = ogg_sync_pageseek( &p_sys->oy, &p_sys->current_page );
 587
 588         if ( i_result < 0 )
 589         {
 590             /* found a page, sync to page start */
 591             p_sys->i_input_position -= i_result;
 592             i_pos1 = p_sys->i_input_position;
 593             continue;
 594         }
 595
 596         if ( i_result > 0 || ( i_result == 0 && p_sys->oy.fill > 3 &&
 597                                ! strncmp( (char *)p_sys->oy.data, "OggS" , 4 ) ) )
 598         {
 599             i_pos1 = p_sys->i_input_position;
 600             break;
 601         }
 602
 603         p_sys->i_input_position += i_bytes_read;
 604     };
 605
 606     seek_byte( p_demux, p_sys->i_input_position );
 607     ogg_stream_reset( &p_stream->os );
 608
 609     ogg_packet op;
 610     while( ogg_stream_packetout( &p_stream->os, &op ) > 0 ) {};
 611
 612     packetStartCoordinates lastpacket = { -1, -1, -1 };
 613
 614     while( 1 )
 615     {
 616
 617         if ( p_sys->i_input_position >= i_pos2 )
 618         {
 619             /* reached the end of the search region and nothing was found */
 620             break;
 621         }
 622
 623         p_sys->b_page_waiting = false;
 624
 625         if ( ! ( i_result = oggseek_read_page( p_demux ) ) )
 626         {
 627             /* EOF */
 628             break;
 629         }
 630
 631         // found a page
 632         if ( p_stream->os.serialno != ogg_page_serialno( &p_sys->current_page ) )
 633         {
 634             /* page is not for this stream */
 635             p_sys->i_input_position += i_result;
 636             continue;
 637         }
 638
 639         if ( OggSeekToPacket( p_demux, p_stream, i_granulepos, &lastpacket, b_fastseek ) )
 640         {
 641             p_sys->i_input_position = lastpacket.i_pos;
 642             p_stream->i_skip_frames = 0;
 643             return p_sys->i_input_position;
 644         }
 645
 646         /*  -> start of next page */
 647         p_sys->i_input_position += i_result;
 648     }
 649
 650     return SEGMENT_NOT_FOUND;
 651 }
 652
 653 static int64_t OggBackwardSeekToFrame( demux_t *p_demux, int64_t i_pos1, int64_t i_pos2,
 654                                logical_stream_t *p_stream, int64_t i_granulepos )
 655 {
 656     int64_t i_result;
 657     int64_t i_offset = __MAX( 1 + ( (i_pos2 - i_pos1) >> 1 ), OGGSEEK_BYTES_TO_READ );
 658
 659 restart:
 660
 661     OggDebug(
 662         msg_Dbg( p_demux, "Probing Back %"PRId64" %"PRId64" for granule %"PRId64,
 663         i_pos1, i_pos2, i_granulepos );
 664     );
 665
 666     i_result = OggForwardSeekToFrame( p_demux, i_pos1, i_pos2, p_stream,
 667                                       i_granulepos, true );
 668
 669     if ( i_result == SEGMENT_NOT_FOUND && i_pos1 > p_stream->i_data_start )
 670     {
 671         i_pos1 = __MAX( p_stream->i_data_start, i_pos1 - i_offset );
 672         goto restart;
 673     }
 674
 675     return i_result;
 676 }
 677
 678 /* Dont use b_presentation with frames granules ! */
 679 int64_t Oggseek_GranuleToAbsTimestamp( logical_stream_t *p_stream,
 680                                        int64_t i_granule, bool b_presentation )
 681 {
 682     int64_t i_timestamp = -1;
 683     if ( i_granule < 1 )
 684         return -1;
 685
 686     if ( p_stream->b_oggds )
 687     {
 688         if ( b_presentation ) i_granule--;
 689         i_timestamp = i_granule * CLOCK_FREQ / p_stream->f_rate;
 690     }
 691     else  switch( p_stream->fmt.i_codec )
 692     {
 693     case VLC_CODEC_THEORA:
 694     case VLC_CODEC_DAALA:
 695     case VLC_CODEC_KATE:
 696     {
 697         ogg_int64_t iframe = i_granule >> p_stream->i_granule_shift;
 698         ogg_int64_t pframe = i_granule - ( iframe << p_stream->i_granule_shift );
 699         /* See Theora A.2.3 */
 700         if ( b_presentation ) pframe -= p_stream->i_keyframe_offset;
 701         i_timestamp = ( iframe + pframe ) * CLOCK_FREQ / p_stream->f_rate;
 702         break;
 703     }
 704     case VLC_CODEC_VP8:
 705     {
 706         ogg_int64_t frame = i_granule >> p_stream->i_granule_shift;
 707         if ( b_presentation ) frame--;
 708         i_timestamp = frame * CLOCK_FREQ / p_stream->f_rate;
 709         break;
 710     }
 711     case VLC_CODEC_DIRAC:
 712     {
 713         ogg_int64_t i_dts = i_granule >> 31;
 714         ogg_int64_t delay = (i_granule >> 9) & 0x1fff;
 715         /* NB, OggDirac granulepos values are in units of 2*picturerate */
 716         double f_rate = p_stream->f_rate;
 717         if ( !p_stream->special.dirac.b_interlaced ) f_rate *= 2;
 718         if ( b_presentation ) i_dts += delay;
 719         i_timestamp = i_dts * CLOCK_FREQ / f_rate;
 720         break;
 721     }
 722     case VLC_CODEC_OPUS:
 723     {
 724         if ( b_presentation ) return VLC_TS_INVALID;
 725         i_timestamp = ( i_granule - p_stream->i_pre_skip ) * CLOCK_FREQ / 48000;
 726         break;
 727     }
 728     case VLC_CODEC_VORBIS:
 729     case VLC_CODEC_FLAC:
 730     {
 731         if ( b_presentation ) return VLC_TS_INVALID;
 732         i_timestamp = i_granule * CLOCK_FREQ / p_stream->f_rate;
 733         break;
 734     }
 735     case VLC_CODEC_SPEEX:
 736     {
 737         if ( b_presentation )
 738             i_granule -= p_stream->special.speex.i_framesize *
 739                          p_stream->special.speex.i_framesperpacket;
 740         i_timestamp = i_granule * CLOCK_FREQ / p_stream->f_rate;
 741         break;
 742     }
 743     }
 744
 745     return i_timestamp;
 746 }
 747
 748 /* returns pos */
 749 static int64_t OggBisectSearchByTime( demux_t *p_demux, logical_stream_t *p_stream,
 750             int64_t i_targettime, int64_t i_pos_lower, int64_t i_pos_upper)
 751 {
 752     int64_t i_start_pos;
 753     int64_t i_end_pos;
 754     int64_t i_segsize;
 755
 756     struct
 757     {
 758         int64_t i_pos;
 759         int64_t i_timestamp;
 760         int64_t i_granule;
 761     } bestlower = { p_stream->i_data_start, -1, -1 },
 762       current = { -1, -1, -1 },
 763       lowestupper = { -1, -1, -1 };
 764
 765     demux_sys_t *p_sys  = p_demux->p_sys;
 766
 767     i_pos_lower = __MAX( i_pos_lower, p_stream->i_data_start );
 768     i_pos_upper = __MIN( i_pos_upper, p_sys->i_total_length );
 769     if ( i_pos_upper < 0 ) i_pos_upper = p_sys->i_total_length;
 770
 771     i_start_pos = i_pos_lower;
 772     i_end_pos = i_pos_upper;
 773
 774     i_segsize = ( i_end_pos - i_start_pos + 1 ) >> 1;
 775     i_start_pos += i_segsize;
 776
 777     OggDebug( msg_Dbg(p_demux, "Bisecting for time=%"PRId64" between %"PRId64" and %"PRId64,
 778             i_targettime, i_pos_lower, i_pos_upper ) );
 779
 780     do
 781     {
 782         /* see if the frame lies in current segment */
 783         i_start_pos = __MAX( i_start_pos, i_pos_lower );
 784         i_end_pos = __MIN( i_end_pos, i_pos_upper );
 785
 786         if ( i_start_pos >= i_end_pos )
 787         {
 788             if ( i_start_pos == i_pos_lower)
 789             {
 790                 return i_start_pos;
 791             }
 792             return -1;
 793         }
 794
 795
 796         current.i_pos = find_first_page_granule( p_demux,
 797                                                  i_start_pos, i_end_pos,
 798                                                  p_stream,
 799                                                  &current.i_granule );
 800
 801         current.i_timestamp = Oggseek_GranuleToAbsTimestamp( p_stream,
 802                                                              current.i_granule, false );
 803
 804         if ( current.i_timestamp == -1 && current.i_granule > 0 )
 805         {
 806             msg_Err( p_demux, "Unmatched granule. New codec ?" );
 807             return -1;
 808         }
 809         else if ( current.i_timestamp < -1 )  /* due to preskip with some codecs */
 810         {
 811             current.i_timestamp = 0;
 812         }
 813
 814         if ( current.i_pos != -1 && current.i_granule != -1 )
 815         {
 816             /* found a page */
 817
 818             if ( current.i_timestamp <= i_targettime )
 819             {
 820                 /* set our lower bound */
 821                 if ( current.i_timestamp > bestlower.i_timestamp )
 822                     bestlower = current;
 823                 i_start_pos = current.i_pos;
 824             }
 825             else if ( current.i_timestamp > i_targettime )
 826             {
 827                 if ( lowestupper.i_timestamp == -1 || current.i_timestamp < lowestupper.i_timestamp )
 828                     lowestupper = current;
 829                 /* check lower half of segment */
 830                 i_start_pos -= i_segsize;
 831                 i_end_pos -= i_segsize;
 832             }
 833         }
 834         else
 835         {
 836             /* no keyframe found, check lower segment */
 837             i_end_pos -= i_segsize;
 838             i_start_pos -= i_segsize;
 839         }
 840
 841         OggDebug( msg_Dbg(p_demux, "Bisect restart i_segsize=%"PRId64" between %"PRId64
 842                                    " and %"PRId64 " bl %"PRId64" lu %"PRId64,
 843                 i_segsize, i_start_pos, i_end_pos, bestlower.i_granule, lowestupper.i_granule  ) );
 844
 845         i_segsize = ( i_end_pos - i_start_pos + 1 ) >> 1;
 846         i_start_pos += i_segsize;
 847
 848     } while ( i_segsize > 64 );
 849
 850     if ( bestlower.i_granule == -1 )
 851     {
 852         if ( lowestupper.i_granule == -1 )
 853             return -1;
 854         else
 855             bestlower = lowestupper;
 856     }
 857
 858     if ( p_stream->b_oggds )
 859     {
 860         int64_t a = OggBackwardSeekToFrame( p_demux,
 861                 __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ),
 862                 bestlower.i_pos,
 863                 p_stream, bestlower.i_granule /* unused */ );
 864         return a;
 865     }
 866     /* If not each packet is usable as keyframe, query the codec for keyframe */
 867     else if ( Ogg_GetKeyframeGranule( p_stream, bestlower.i_granule ) != bestlower.i_granule )
 868     {
 869         int64_t i_keyframegranule = Ogg_GetKeyframeGranule( p_stream, bestlower.i_granule );
 870
 871         OggDebug( msg_Dbg( p_demux, "Need to reseek to keyframe (%"PRId64") granule (%"PRId64"!=%"PRId64") to t=%"PRId64,
 872                            i_keyframegranule >> p_stream->i_granule_shift,
 873                            bestlower.i_granule,
 874                            i_pos_upper,
 875                            Oggseek_GranuleToAbsTimestamp( p_stream, i_keyframegranule, false ) ) );
 876
 877         OggDebug( msg_Dbg( p_demux, "Seeking back to %"PRId64, __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ) ) );
 878
 879         int64_t a = OggBackwardSeekToFrame( p_demux,
 880             __MAX ( bestlower.i_pos - OGGSEEK_BYTES_TO_READ, p_stream->i_data_start ),
 881             stream_Size( p_demux->s ), p_stream, i_keyframegranule );
 882         return a;
 883     }
 884
 885     return bestlower.i_pos;
 886 }
 887
 888
 889 /************************************************************************
 890  * public functions
 891  *************************************************************************/
 892
 893 int Oggseek_BlindSeektoAbsoluteTime( demux_t *p_demux, logical_stream_t *p_stream,
 894                                      int64_t i_time, bool b_fastseek )
 895 {
 896     demux_sys_t *p_sys  = p_demux->p_sys;
 897     int64_t i_lowerpos = -1;
 898     int64_t i_upperpos = -1;
 899     bool b_found = false;
 900
 901     /* Search in skeleton */
 902     Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_lowerpos, &i_upperpos );
 903     if ( i_lowerpos != -1 ) b_found = true;
 904
 905     /* And also search in our own index */
 906     if ( !b_found && OggSeekIndexFind( p_stream, i_time, &i_lowerpos, &i_upperpos ) )
 907     {
 908         b_found = true;
 909     }
 910
 911     /* Or try to be smart with audio fixed bitrate streams */
 912     if ( !b_found && p_stream->fmt.i_cat == AUDIO_ES && p_sys->i_streams == 1
 913          && p_sys->i_bitrate && Ogg_GetKeyframeGranule( p_stream, 0xFF00FF00 ) == 0xFF00FF00 )
 914     {
 915         /* But only if there's no keyframe/preload requirements */
 916         /* FIXME: add function to get preload time by codec, ex: opus */
 917         i_lowerpos = i_time * p_sys->i_bitrate / INT64_C(8000000);
 918         b_found = true;
 919     }
 920
 921     /* or search */
 922     if ( !b_found && b_fastseek )
 923     {
 924         i_lowerpos = OggBisectSearchByTime( p_demux, p_stream, i_time,
 925                                             p_stream->i_data_start, p_sys->i_total_length );
 926         b_found = ( i_lowerpos != -1 );
 927     }
 928
 929     if ( !b_found ) return -1;
 930
 931     if ( i_lowerpos < p_stream->i_data_start || i_upperpos > p_sys->i_total_length )
 932         return -1;
 933
 934     /* And really do seek */
 935     p_sys->i_input_position = i_lowerpos;
 936     seek_byte( p_demux, p_sys->i_input_position );
 937     ogg_stream_reset( &p_stream->os );
 938
 939     return i_lowerpos;
 940 }
 941
 942 int Oggseek_BlindSeektoPosition( demux_t *p_demux, logical_stream_t *p_stream,
 943                                  double f, bool b_canfastseek )
 944 {
 945     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Blind Pos" ) );
 946     int64_t i_size = stream_Size( p_demux->s );
 947     int64_t i_granule;
 948     int64_t i_pagepos;
 949
 950     i_size = find_first_page_granule( p_demux,
 951                                              i_size * f, i_size,
 952                                              p_stream,
 953                                              &i_granule );
 954
 955     OggDebug( msg_Dbg( p_demux, "Seek start pos is %"PRId64" granule %"PRId64, i_size, i_granule ) );
 956
 957     i_granule = Ogg_GetKeyframeGranule( p_stream, i_granule );
 958
 959     if ( b_canfastseek )
 960     {
 961         /* Peek back until we meet a keyframe to start our decoding up to our
 962          * final seek time */
 963         i_pagepos = OggBackwardSeekToFrame( p_demux,
 964                 __MAX ( i_size - MAX_PAGE_SIZE, p_stream->i_data_start ),
 965                 __MIN ( i_size + MAX_PAGE_SIZE, p_demux->p_sys->i_total_length ),
 966                 p_stream, i_granule );
 967     }
 968     else
 969     {
 970         /* Otherwise, we just sync to the next keyframe we meet */
 971         i_pagepos = OggForwardSeekToFrame( p_demux,
 972                 __MAX ( i_size - MAX_PAGE_SIZE, p_stream->i_data_start ),
 973                 stream_Size( p_demux->s ),
 974                 p_stream, i_granule, false );
 975     }
 976
 977     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" granule %"PRId64, i_pagepos, i_granule ) );
 978     return i_pagepos;
 979 }
 980
 981 int Oggseek_SeektoAbsolutetime( demux_t *p_demux, logical_stream_t *p_stream,
 982                                 int64_t i_time )
 983 {
 984     demux_sys_t *p_sys  = p_demux->p_sys;
 985
 986     OggDebug( msg_Dbg( p_demux, "=================== Seeking To Absolute Time %"PRId64, i_time ) );
 987     int64_t i_offset_lower = -1;
 988     int64_t i_offset_upper = -1;
 989
 990     if ( Ogg_GetBoundsUsingSkeletonIndex( p_stream, i_time, &i_offset_lower, &i_offset_upper ) )
 991     {
 992         /* Exact match */
 993         OggDebug( msg_Dbg( p_demux, "Found keyframe at %"PRId64" using skeleton index", i_offset_lower ) );
 994         if ( i_offset_lower == -1 ) i_offset_lower = p_stream->i_data_start;
 995         p_sys->i_input_position = i_offset_lower;
 996         seek_byte( p_demux, p_sys->i_input_position );
 997         ogg_stream_reset( &p_stream->os );
 998         return i_offset_lower;
 999     }
1000     OggDebug( msg_Dbg( p_demux, "Search bounds set to %"PRId64" %"PRId64" using skeleton index", i_offset_lower, i_offset_upper ) );
1001
1002     OggNoDebug(
1003         OggSeekIndexFind( p_stream, i_time, &i_offset_lower, &i_offset_upper )
1004     );
1005
1006     i_offset_lower = __MAX( i_offset_lower, p_stream->i_data_start );
1007     i_offset_upper = __MIN( i_offset_upper, p_sys->i_total_length );
1008
1009     int64_t i_pagepos = OggBisectSearchByTime( p_demux, p_stream, i_time,
1010                                        i_offset_lower, i_offset_upper);
1011     if ( i_pagepos >= 0 )
1012     {
1013         /* be sure to clear any state or read+pagein() will fail on same # */
1014         ogg_stream_reset( &p_stream->os );
1015         seek_byte( p_demux, p_sys->i_input_position );
1016     }
1017     /* Insert keyframe position into index */
1018     OggNoDebug(
1019     if ( i_pagepos >= p_stream->i_data_start )
1020         OggSeek_IndexAdd( p_stream, i_time, i_pagepos )
1021     );
1022
1023     OggDebug( msg_Dbg( p_demux, "=================== Seeked To %"PRId64" time %"PRId64, i_pagepos, i_time ) );
1024     return i_pagepos;
1025 }
1026
1027 /****************************************************************************
1028  * oggseek_read_page: Read a full Ogg page from the physical bitstream.
1029  ****************************************************************************
1030  * Returns number of bytes read. This should always be > 0
1031  * unless we are at the end of stream.
1032  *
1033  ****************************************************************************/
1034
1035 int64_t oggseek_read_page( demux_t *p_demux )
1036 {
1037     demux_sys_t *p_ogg = p_demux->p_sys  ;
1038     uint8_t header[PAGE_HEADER_BYTES+255];
1039     int i_nsegs;
1040     int i;
1041     int64_t i_in_pos;
1042     int64_t i_result;
1043     int i_page_size;
1044     char *buf;
1045
1046     demux_sys_t *p_sys  = p_demux->p_sys;
1047
1048     /* store position of this page */
1049     i_in_pos = p_ogg->i_input_position = stream_Tell( p_demux->s );
1050
1051     if ( p_sys->b_page_waiting) {
1052         msg_Warn( p_demux, "Ogg page already loaded" );
1053         return 0;
1054     }
1055
1056     if ( stream_Read ( p_demux->s, header, PAGE_HEADER_BYTES ) < PAGE_HEADER_BYTES )
1057     {
1058         stream_Seek( p_demux->s, i_in_pos );
1059         msg_Dbg ( p_demux, "Reached clean EOF in ogg file" );
1060         return 0;
1061     }
1062
1063     i_nsegs = header[ PAGE_HEADER_BYTES - 1 ];
1064
1065     if ( stream_Read ( p_demux->s, header+PAGE_HEADER_BYTES, i_nsegs ) < i_nsegs )
1066     {
1067         stream_Seek( p_demux->s, i_in_pos );
1068         msg_Warn ( p_demux, "Reached broken EOF in ogg file" );
1069         return 0;
1070     }
1071
1072     i_page_size = PAGE_HEADER_BYTES + i_nsegs;
1073
1074     for ( i = 0; i < i_nsegs; i++ )
1075     {
1076         i_page_size += header[ PAGE_HEADER_BYTES + i ];
1077     }
1078
1079     ogg_sync_reset( &p_ogg->oy );
1080
1081     buf = ogg_sync_buffer( &p_ogg->oy, i_page_size );
1082
1083     memcpy( buf, header, PAGE_HEADER_BYTES + i_nsegs );
1084
1085     i_result = stream_Read ( p_demux->s, (uint8_t*)buf + PAGE_HEADER_BYTES + i_nsegs,
1086                              i_page_size - PAGE_HEADER_BYTES - i_nsegs );
1087
1088     ogg_sync_wrote( &p_ogg->oy, i_result + PAGE_HEADER_BYTES + i_nsegs );
1089
1090
1091
1092
1093     if ( ogg_sync_pageout( &p_ogg->oy, &p_ogg->current_page ) != 1 )
1094     {
1095         msg_Err( p_demux , "Got invalid packet, read %"PRId64" of %i: %s %"PRId64,
1096                  i_result, i_page_size, buf, i_in_pos );
1097         return 0;
1098     }
1099
1100     return i_result + PAGE_HEADER_BYTES + i_nsegs;
1101 }
1102