opusfile.c 125 KB
Newer Older
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1 2 3 4 5 6 7
/********************************************************************
 *                                                                  *
 * THIS FILE IS PART OF THE libopusfile SOFTWARE CODEC SOURCE CODE. *
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
 *                                                                  *
8
 * THE libopusfile SOURCE CODE IS (C) COPYRIGHT 1994-2012           *
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
9 10 11 12 13 14 15 16
 * by the Xiph.Org Foundation and contributors http://www.xiph.org/ *
 *                                                                  *
 ********************************************************************

 function: stdio-based convenience library for opening/seeking/decoding
 last mod: $Id: vorbisfile.c 17573 2010-10-27 14:53:59Z xiphmont $

 ********************************************************************/
17 18 19 20
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
21 22 23 24 25 26 27 28
#include "internal.h"
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>
#include <string.h>
#include <math.h>

Ralph Giles's avatar
Ralph Giles committed
29
#include "opusfile.h"
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

/*This implementation is largely based off of libvorbisfile.
  All of the Ogg bits work roughly the same, though I have made some
   "improvements" that have not been folded back there, yet.*/

/*A 'chained bitstream' is an Ogg Opus bitstream that contains more than one
   logical bitstream arranged end to end (the only form of Ogg multiplexing
   supported by this library.
  Grouping (parallel multiplexing) is not supported, except to the extent that
   if there are multiple logical Ogg streams in a single link of the chain, we
   will ignore all but the first Opus stream we find.*/

/*An Ogg Opus file can be played beginning to end (streamed) without worrying
   ahead of time about chaining (see opusdec from the opus-tools package).
  If we have the whole file, however, and want random access
   (seeking/scrubbing) or desire to know the total length/time of a file, we
   need to account for the possibility of chaining.*/

/*We can handle things a number of ways.
  We can determine the entire bitstream structure right off the bat, or find
   pieces on demand.
  This library determines and caches structure for the entire bitstream, but
   builds a virtual decoder on the fly when moving between links in the chain.*/

/*There are also different ways to implement seeking.
  Enough information exists in an Ogg bitstream to seek to sample-granularity
   positions in the output.
  Or, one can seek by picking some portion of the stream roughly in the desired
   area if we only want coarse navigation through the stream.
  We implement and expose both strategies.*/

/*The maximum number of bytes in a page (including the page headers).*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
62
#define OP_PAGE_SIZE_MAX  (65307)
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
63 64 65 66 67 68
/*The default amount to seek backwards per step when trying to find the
   previous page.
  This must be at least as large as the maximum size of a page.*/
#define OP_CHUNK_SIZE     (65536)
/*The maximum amount to seek backwards per step when trying to find the
   previous page.*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
69
#define OP_CHUNK_SIZE_MAX (1024*(opus_int32)1024)
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
/*A smaller read size is needed for low-rate streaming.*/
#define OP_READ_SIZE      (2048)

int op_test(OpusHead *_head,
 const unsigned char *_initial_data,size_t _initial_bytes){
  ogg_sync_state  oy;
  char           *data;
  int             err;
  /*The first page of a normal Opus file will be at most 57 bytes (27 Ogg
     page header bytes + 1 lacing value + 21 Opus header bytes + 8 channel
     mapping bytes).
    It will be at least 47 bytes (27 Ogg page header bytes + 1 lacing value +
     19 Opus header bytes using channel mapping family 0).
    If we don't have at least that much data, give up now.*/
  if(_initial_bytes<47)return OP_FALSE;
  /*Only proceed if we start with the magic OggS string.
    This is to prevent us spending a lot of time allocating memory and looking
     for Ogg pages in non-Ogg files.*/
  if(memcmp(_initial_data,"OggS",4)!=0)return OP_ENOTFORMAT;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
89
  if(OP_UNLIKELY(_initial_bytes>(size_t)LONG_MAX))return OP_EFAULT;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
90
  ogg_sync_init(&oy);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
91
  data=ogg_sync_buffer(&oy,(long)_initial_bytes);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
92 93 94 95 96
  if(data!=NULL){
    ogg_stream_state os;
    ogg_page         og;
    int              ret;
    memcpy(data,_initial_data,_initial_bytes);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
97
    ogg_sync_wrote(&oy,(long)_initial_bytes);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131
    ogg_stream_init(&os,-1);
    err=OP_FALSE;
    do{
      ogg_packet op;
      ret=ogg_sync_pageout(&oy,&og);
      /*Ignore holes.*/
      if(ret<0)continue;
      /*Stop if we run out of data.*/
      if(!ret)break;
      ogg_stream_reset_serialno(&os,ogg_page_serialno(&og));
      ogg_stream_pagein(&os,&og);
      /*Only process the first packet on this page (if it's a BOS packet,
         it's required to be the only one).*/
      if(ogg_stream_packetout(&os,&op)==1){
        if(op.b_o_s){
          ret=opus_head_parse(_head,op.packet,op.bytes);
          /*If this didn't look like Opus, keep going.*/
          if(ret==OP_ENOTFORMAT)continue;
          /*Otherwise we're done, one way or another.*/
          err=ret;
        }
        /*We finished parsing the headers.
          There is no Opus to be found.*/
        else err=OP_ENOTFORMAT;
      }
    }
    while(err==OP_FALSE);
    ogg_stream_clear(&os);
  }
  else err=OP_EFAULT;
  ogg_sync_clear(&oy);
  return err;
}

Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
132 133 134 135 136 137 138 139
/*Many, many internal helpers.
  The intention is not to be confusing.
  Rampant duplication and monolithic function implementation (though we do have
   some large, omnibus functions still) would be harder to understand anyway.
  The high level functions are last.
  Begin grokking near the end of the file if you prefer to read things
   top-down.*/

140 141
/*The read/seek functions track absolute position within the stream.*/

142
/*Read a little more data from the file/pipe into the ogg_sync framer.
143
  _nbytes: The maximum number of bytes to read.
144 145
  Return: A positive number of bytes read on success, 0 on end-of-file, or a
           negative value on failure.*/
146
static int op_get_data(OggOpusFile *_of,int _nbytes){
147
  unsigned char *buffer;
148 149 150 151 152 153 154
  int            nbytes;
  OP_ASSERT(_nbytes>0);
  buffer=(unsigned char *)ogg_sync_buffer(&_of->oy,_nbytes);
  nbytes=(int)(*_of->callbacks.read)(_of->source,buffer,_nbytes);
  OP_ASSERT(nbytes<=_nbytes);
  if(OP_LIKELY(nbytes>0))ogg_sync_wrote(&_of->oy,nbytes);
  return nbytes;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
155 156 157 158
}

/*Save a tiny smidge of verbosity to make the code more readable.*/
static int op_seek_helper(OggOpusFile *_of,opus_int64 _offset){
159
  if(_offset==_of->offset)return 0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
160 161
  if(_of->callbacks.seek==NULL
   ||(*_of->callbacks.seek)(_of->source,_offset,SEEK_SET)){
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
162 163 164 165 166 167 168
    return OP_EREAD;
  }
  _of->offset=_offset;
  ogg_sync_reset(&_of->oy);
  return 0;
}

169 170
/*Get the current position indicator of the underlying source.
  This should be the same as the value reported by tell().*/
171
static opus_int64 op_position(const OggOpusFile *_of){
172 173 174 175
  /*The current position indicator is _not_ simply offset.
    We may also have unprocessed, buffered data in the sync state.*/
  return _of->offset+_of->oy.fill-_of->oy.returned;
}
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
176 177 178 179

/*From the head of the stream, get the next page.
  _boundary specifies if the function is allowed to fetch more data from the
   stream (and how much) or only use internally buffered data.
180 181
  _boundary: -1: Unbounded search.
              0: Read no additional data.
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
182
                 Use only cached data.
183 184 185 186 187
              n: Search for the start of a new page up to file position n.
  Return: n>=0:       Found a page at absolute offset n.
          OP_FALSE:   Hit the _boundary limit.
          OP_EREAD:   An underlying read operation failed.
          OP_BADLINK: We hit end-of-file before reaching _boundary.*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
188 189
static opus_int64 op_get_next_page(OggOpusFile *_of,ogg_page *_og,
 opus_int64 _boundary){
190
  while(_boundary<=0||_of->offset<_boundary){
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
191 192 193 194 195
    int more;
    more=ogg_sync_pageseek(&_of->oy,_og);
    /*Skipped (-more) bytes.*/
    if(OP_UNLIKELY(more<0))_of->offset-=more;
    else if(more==0){
196
      int read_nbytes;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
197 198 199
      int ret;
      /*Send more paramedics.*/
      if(!_boundary)return OP_FALSE;
200 201 202 203 204 205 206 207
      if(_boundary<0)read_nbytes=OP_READ_SIZE;
      else{
        opus_int64 position;
        position=op_position(_of);
        if(position>=_boundary)return OP_FALSE;
        read_nbytes=(int)OP_MIN(_boundary-position,OP_READ_SIZE);
      }
      ret=op_get_data(_of,read_nbytes);
208 209
      if(OP_UNLIKELY(ret<0))return OP_EREAD;
      if(OP_UNLIKELY(ret==0)){
210 211 212 213
        /*Only fail cleanly on EOF if we didn't have a known boundary.
          Otherwise, we should have been able to reach that boundary, and this
           is a fatal error.*/
        return OP_UNLIKELY(_boundary<0)?OP_FALSE:OP_EBADLINK;
214
      }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
215 216 217
    }
    else{
      /*Got a page.
218 219
        Return the page start offset and advance the internal offset past the
         page end.*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
220 221 222
      opus_int64 page_offset;
      page_offset=_of->offset;
      _of->offset+=more;
223
      OP_ASSERT(page_offset>=0);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
224 225 226
      return page_offset;
    }
  }
227
  return OP_FALSE;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
228 229
}

230
static int op_add_serialno(const ogg_page *_og,
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
231 232 233 234 235 236 237 238 239 240
 ogg_uint32_t **_serialnos,int *_nserialnos,int *_cserialnos){
  ogg_uint32_t *serialnos;
  int           nserialnos;
  int           cserialnos;
  ogg_uint32_t s;
  s=ogg_page_serialno(_og);
  serialnos=*_serialnos;
  nserialnos=*_nserialnos;
  cserialnos=*_cserialnos;
  if(OP_UNLIKELY(nserialnos>=cserialnos)){
241 242 243
    if(OP_UNLIKELY(cserialnos>INT_MAX/(int)sizeof(*serialnos)-1>>1)){
      return OP_EFAULT;
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
244 245
    cserialnos=2*cserialnos+1;
    OP_ASSERT(nserialnos<cserialnos);
246 247
    serialnos=(ogg_uint32_t *)_ogg_realloc(serialnos,
     sizeof(*serialnos)*cserialnos);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264
    if(OP_UNLIKELY(serialnos==NULL))return OP_EFAULT;
  }
  serialnos[nserialnos++]=s;
  *_serialnos=serialnos;
  *_nserialnos=nserialnos;
  *_cserialnos=cserialnos;
  return 0;
}

/*Returns nonzero if found.*/
static int op_lookup_serialno(ogg_uint32_t _s,
 const ogg_uint32_t *_serialnos,int _nserialnos){
  int i;
  for(i=0;i<_nserialnos&&_serialnos[i]!=_s;i++);
  return i<_nserialnos;
}

265
static int op_lookup_page_serialno(const ogg_page *_og,
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
266 267 268 269
 const ogg_uint32_t *_serialnos,int _nserialnos){
  return op_lookup_serialno(ogg_page_serialno(_og),_serialnos,_nserialnos);
}

270 271 272 273
typedef struct OpusSeekRecord OpusSeekRecord;

/*We use this to remember the pages we found while enumerating the links of a
   chained stream.
274 275 276 277 278
  We keep track of the starting and ending offsets, as well as the point we
   started searching from, so we know where to bisect.
  We also keep the serial number, so we can tell if the page belonged to the
   current link or not, as well as the granule position, to aid in estimating
   the start of the link.*/
279 280 281 282 283 284 285 286 287 288 289 290 291 292
struct OpusSeekRecord{
  /*The earliest byte we know of such that reading forward from it causes
     capture to be regained at this page.*/
  opus_int64   search_start;
  /*The offset of this page.*/
  opus_int64   offset;
  /*The size of this page.*/
  opus_int32   size;
  /*The serial number of this page.*/
  ogg_uint32_t serialno;
  /*The granule position of this page.*/
  ogg_int64_t  gp;
};

293 294
/*Find the last page beginning before _offset with a valid granule position.
  There is no '_boundary' parameter as it will always have to read more data.
295 296 297
  This is much dirtier than the above, as Ogg doesn't have any backward search
   linkage.
  This search prefers pages of the specified serial number.
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
298 299
  If a page of the specified serial number is spotted during the
   seek-back-and-read-forward, it will return the info of last page of the
300 301
   matching serial number, instead of the very last page, unless the very last
   page belongs to a different link than preferred serial number.
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
302
  If no page of the specified serial number is seen, it will return the info of
303 304 305 306 307 308 309 310 311 312 313 314 315
   the last page.
  [out] _sr:   Returns information about the page that was found on success.
  _offset:     The _offset before which to find a page.
               Any page returned will consist of data entirely before _offset.
  _serialno:   The preferred serial number.
               If a page with this serial number is found, it will be returned
                even if another page in the same link is found closer to
                _offset.
               This is purely opportunistic: there is no guarantee such a page
                will be found if it exists.
  _serialnos:  The list of serial numbers in the link that contains the
                preferred serial number.
  _nserialnos: The number of serial numbers in the current link.
316
  Return: 0 on success, or a negative value on failure.
317 318 319
          OP_EREAD:    Failed to read more data (error or EOF).
          OP_EBADLINK: We couldn't find a page even after seeking back to the
                        start of the stream.*/
320 321 322
static int op_get_prev_page_serial(OggOpusFile *_of,OpusSeekRecord *_sr,
 opus_int64 _offset,ogg_uint32_t _serialno,
 const ogg_uint32_t *_serialnos,int _nserialnos){
323 324 325 326 327 328 329
  OpusSeekRecord preferred_sr;
  ogg_page       og;
  opus_int64     begin;
  opus_int64     end;
  opus_int64     original_end;
  opus_int32     chunk_size;
  int            preferred_found;
330
  original_end=end=begin=_offset;
331 332
  preferred_found=0;
  _offset=-1;
333
  chunk_size=OP_CHUNK_SIZE;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
334
  do{
335 336
    opus_int64 search_start;
    int        ret;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
337
    OP_ASSERT(chunk_size>=OP_PAGE_SIZE_MAX);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
338 339 340
    begin=OP_MAX(begin-chunk_size,0);
    ret=op_seek_helper(_of,begin);
    if(OP_UNLIKELY(ret<0))return ret;
341
    search_start=begin;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
342
    while(_of->offset<end){
343 344
      opus_int64   llret;
      ogg_uint32_t serialno;
345
      llret=op_get_next_page(_of,&og,end);
346
      if(OP_UNLIKELY(llret<OP_FALSE))return (int)llret;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
347
      else if(llret==OP_FALSE)break;
348 349 350 351 352 353 354 355
      serialno=ogg_page_serialno(&og);
      /*Save the information for this page.
        We're not interested in the page itself... just the serial number, byte
         offset, page size, and granule position.*/
      _sr->search_start=search_start;
      _sr->offset=_offset=llret;
      _sr->serialno=serialno;
      OP_ASSERT(_of->offset-_offset>=0);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
356
      OP_ASSERT(_of->offset-_offset<=OP_PAGE_SIZE_MAX);
357 358 359 360 361 362
      _sr->size=(opus_int32)(_of->offset-_offset);
      _sr->gp=ogg_page_granulepos(&og);
      /*If this page is from the stream we're looking for, remember it.*/
      if(serialno==_serialno){
        preferred_found=1;
        *&preferred_sr=*_sr;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
363
      }
364
      if(!op_lookup_serialno(serialno,_serialnos,_nserialnos)){
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
365 366 367
        /*We fell off the end of the link, which means we seeked back too far
           and shouldn't have been looking in that link to begin with.
          If we found the preferred serial number, forget that we saw it.*/
368
        preferred_found=0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
369
      }
370
      search_start=llret+1;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
371 372 373 374
    }
    /*We started from the beginning of the stream and found nothing.
      This should be impossible unless the contents of the source changed out
       from under us after we read from it.*/
375
    if(OP_UNLIKELY(!begin)&&OP_UNLIKELY(_offset<0))return OP_EBADLINK;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
376 377 378 379
    /*Bump up the chunk size.
      This is mildly helpful when seeks are very expensive (http).*/
    chunk_size=OP_MIN(2*chunk_size,OP_CHUNK_SIZE_MAX);
    /*Avoid quadratic complexity if we hit an invalid patch of the file.*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
380
    end=OP_MIN(begin+OP_PAGE_SIZE_MAX-1,original_end);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
381
  }
382 383 384
  while(_offset<0);
  if(preferred_found)*_sr=*&preferred_sr;
  return 0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
385 386
}

387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
/*Find the last page beginning before _offset with the given serial number and
   a valid granule position.
  Unlike the above search, this continues until it finds such a page, but does
   not stray outside the current link.
  We could implement it (inefficiently) by calling op_get_prev_page_serial()
   repeatedly until it returned a page that had both our preferred serial
   number and a valid granule position, but doing it with a separate function
   allows us to avoid repeatedly re-scanning valid pages from other streams as
   we seek-back-and-read-forward.
  [out] _gp:   Returns the granule position of the page that was found on
                success.
  _offset:     The _offset before which to find a page.
               Any page returned will consist of data entirely before _offset.
  _serialno:   The target serial number.
  _serialnos:  The list of serial numbers in the link that contains the
                preferred serial number.
  _nserialnos: The number of serial numbers in the current link.
  Return: The offset of the page on success, or a negative value on failure.
          OP_EREAD:    Failed to read more data (error or EOF).
          OP_EBADLINK: We couldn't find a page even after seeking back past the
                        beginning of the link.*/
static opus_int64 op_get_last_page(OggOpusFile *_of,ogg_int64_t *_gp,
 opus_int64 _offset,ogg_uint32_t _serialno,
 const ogg_uint32_t *_serialnos,int _nserialnos){
  ogg_page    og;
  ogg_int64_t gp;
  opus_int64  begin;
  opus_int64  end;
  opus_int64  original_end;
  opus_int32  chunk_size;
  /*The target serial number must belong to the current link.*/
  OP_ASSERT(op_lookup_serialno(_serialno,_serialnos,_nserialnos));
  original_end=end=begin=_offset;
  _offset=-1;
421 422 423
  /*We shouldn't have to initialize gp, but gcc is too dumb to figure out that
     ret>=0 implies we entered the if(page_gp!=-1) block at least once.*/
  gp=-1;
424 425 426 427 428 429 430 431 432 433 434 435 436
  chunk_size=OP_CHUNK_SIZE;
  do{
    int left_link;
    int ret;
    OP_ASSERT(chunk_size>=OP_PAGE_SIZE_MAX);
    begin=OP_MAX(begin-chunk_size,0);
    ret=op_seek_helper(_of,begin);
    if(OP_UNLIKELY(ret<0))return ret;
    left_link=0;
    while(_of->offset<end){
      opus_int64   llret;
      ogg_uint32_t serialno;
      llret=op_get_next_page(_of,&og,end);
437
      if(OP_UNLIKELY(llret<OP_FALSE))return llret;
438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474
      else if(llret==OP_FALSE)break;
      serialno=ogg_page_serialno(&og);
      if(serialno==_serialno){
        ogg_int64_t page_gp;
        /*The page is from the right stream...*/
        page_gp=ogg_page_granulepos(&og);
        if(page_gp!=-1){
          /*And has a valid granule position.
            Let's remember it.*/
          _offset=llret;
          gp=page_gp;
        }
      }
      else if(OP_UNLIKELY(!op_lookup_serialno(serialno,
       _serialnos,_nserialnos))){
        /*We fell off the start of the link, which means we don't need to keep
           seeking any farther back.*/
        left_link=1;
      }
    }
    /*We started from at or before the beginning of the link and found nothing.
      This should be impossible unless the contents of the source changed out
       from under us after we read from it.*/
    if((OP_UNLIKELY(left_link)||OP_UNLIKELY(!begin))&&OP_UNLIKELY(_offset<0)){
      return OP_EBADLINK;
    }
    /*Bump up the chunk size.
      This is mildly helpful when seeks are very expensive (http).*/
    chunk_size=OP_MIN(2*chunk_size,OP_CHUNK_SIZE_MAX);
    /*Avoid quadratic complexity if we hit an invalid patch of the file.*/
    end=OP_MIN(begin+OP_PAGE_SIZE_MAX-1,original_end);
  }
  while(_offset<0);
  *_gp=gp;
  return _offset;
}

Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
/*Uses the local ogg_stream storage in _of.
  This is important for non-streaming input sources.*/
static int op_fetch_headers_impl(OggOpusFile *_of,OpusHead *_head,
 OpusTags *_tags,ogg_uint32_t **_serialnos,int *_nserialnos,
 int *_cserialnos,ogg_page *_og){
  ogg_packet op;
  int        ret;
  if(_serialnos!=NULL)*_nserialnos=0;
  /*Extract the serialnos of all BOS pages plus the first set of Opus headers
     we see in the link.*/
  while(ogg_page_bos(_og)){
    if(_serialnos!=NULL){
      if(OP_UNLIKELY(op_lookup_page_serialno(_og,*_serialnos,*_nserialnos))){
        /*A dupe serialnumber in an initial header packet set==invalid stream.*/
        return OP_EBADHEADER;
      }
      ret=op_add_serialno(_og,_serialnos,_nserialnos,_cserialnos);
      if(OP_UNLIKELY(ret<0))return ret;
    }
    if(_of->ready_state<OP_STREAMSET){
      /*We don't have an Opus stream in this link yet, so begin prospective
         stream setup.
        We need a stream to get packets.*/
      ogg_stream_reset_serialno(&_of->os,ogg_page_serialno(_og));
      ogg_stream_pagein(&_of->os,_og);
      if(OP_LIKELY(ogg_stream_packetout(&_of->os,&op)>0)){
        ret=opus_head_parse(_head,op.packet,op.bytes);
        /*Found a valid Opus header.
          Continue setup.*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
504 505 506 507
        if(OP_LIKELY(ret>=0))_of->ready_state=OP_STREAMSET;
        /*If it's just a stream type we don't recognize, ignore it.
          Everything else is fatal.*/
        else if(ret!=OP_ENOTFORMAT)return ret;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
508
      }
509
      /*TODO: Should a BOS page with no packets be an error?*/
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
510
    }
511
    /*Get the next page.
512
      No need to clamp the boundary offset against _of->end, as all errors
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
513
       become OP_ENOTFORMAT or OP_EBADHEADER.*/
514 515
    if(OP_UNLIKELY(op_get_next_page(_of,_og,
     OP_ADV_OFFSET(_of->offset,OP_CHUNK_SIZE))<0)){
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
516
      return _of->ready_state<OP_STREAMSET?OP_ENOTFORMAT:OP_EBADHEADER;
517
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
518 519
  }
  if(OP_UNLIKELY(_of->ready_state!=OP_STREAMSET))return OP_ENOTFORMAT;
520 521
  /*If the first non-header page belonged to our Opus stream, submit it.*/
  if(_of->os.serialno==ogg_page_serialno(_og))ogg_stream_pagein(&_of->os,_og);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
522 523 524 525 526 527
  /*Loop getting packets.*/
  for(;;){
    switch(ogg_stream_packetout(&_of->os,&op)){
      case 0:{
        /*Loop getting pages.*/
        for(;;){
528 529
          /*No need to clamp the boundary offset against _of->end, as all
             errors become OP_EBADHEADER.*/
530
          if(OP_UNLIKELY(op_get_next_page(_of,_og,
531
           OP_ADV_OFFSET(_of->offset,OP_CHUNK_SIZE))<0)){
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574
            return OP_EBADHEADER;
          }
          /*If this page belongs to the correct stream, go parse it.*/
          if(_of->os.serialno==ogg_page_serialno(_og)){
            ogg_stream_pagein(&_of->os,_og);
            break;
          }
          /*If the link ends before we see the Opus comment header, abort.*/
          if(OP_UNLIKELY(ogg_page_bos(_og)))return OP_EBADHEADER;
          /*Otherwise, keep looking.*/
        }
      }break;
      /*We shouldn't get a hole in the headers!*/
      case -1:return OP_EBADHEADER;
      default:{
        /*Got a packet.
          It should be the comment header.*/
        ret=opus_tags_parse(_tags,op.packet,op.bytes);
        if(OP_UNLIKELY(ret<0))return ret;
        /*Make sure the page terminated at the end of the comment header.
          If there is another packet on the page, or part of a packet, then
           reject the stream.
          Otherwise seekable sources won't be able to seek back to the start
           properly.*/
        ret=ogg_stream_packetout(&_of->os,&op);
        if(OP_UNLIKELY(ret!=0)
         ||OP_UNLIKELY(_og->header[_og->header_len-1]==255)){
          /*If we fail, the caller assumes our tags are uninitialized.*/
          opus_tags_clear(_tags);
          return OP_EBADHEADER;
        }
        return 0;
      }
    }
  }
}

static int op_fetch_headers(OggOpusFile *_of,OpusHead *_head,
 OpusTags *_tags,ogg_uint32_t **_serialnos,int *_nserialnos,
 int *_cserialnos,ogg_page *_og){
  ogg_page og;
  int      ret;
  if(!_og){
575 576 577 578 579 580
    /*No need to clamp the boundary offset against _of->end, as all errors
       become OP_ENOTFORMAT.*/
    if(OP_UNLIKELY(op_get_next_page(_of,&og,
     OP_ADV_OFFSET(_of->offset,OP_CHUNK_SIZE))<0)){
      return OP_ENOTFORMAT;
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784
    _og=&og;
  }
  _of->ready_state=OP_OPENED;
  ret=op_fetch_headers_impl(_of,_head,_tags,_serialnos,_nserialnos,
   _cserialnos,_og);
  /*Revert back from OP_STREAMSET to OP_OPENED on failure, to prevent
     double-free of the tags in an unseekable stream.*/
  if(OP_UNLIKELY(ret<0))_of->ready_state=OP_OPENED;
  return ret;
}

/*Granule position manipulation routines.
  A granule position is defined to be an unsigned 64-bit integer, with the
   special value -1 in two's complement indicating an unset or invalid granule
   position.
  We are not guaranteed to have an unsigned 64-bit type, so we construct the
   following routines that
   a) Properly order negative numbers as larger than positive numbers, and
   b) Check for underflow or overflow past the special -1 value.
  This lets us operate on the full, valid range of granule positions in a
   consistent and safe manner.
  This full range is organized into distinct regions:
   [ -1 (invalid) ][ 0 ... OP_INT64_MAX ][ OP_INT64_MIN ... -2 ][-1 (invalid) ]

  No one should actually use granule positions so large that they're negative,
   even if they are technically valid, as very little software handles them
   correctly (including most of Xiph.Org's).
  This library also refuses to support durations so large they won't fit in a
   signed 64-bit integer (to avoid exposing this mess to the application, and
   to simplify a good deal of internal arithmetic), so the only way to use them
   successfully is if pcm_start is very large.
  This means there isn't anything you can do with negative granule positions
   that you couldn't have done with purely non-negative ones.
  The main purpose of these routines is to allow us to think very explicitly
   about the possible failure cases of all granule position manipulations.*/

/*Safely adds a small signed integer to a valid (not -1) granule position.
  The result can use the full 64-bit range of values (both positive and
   negative), but will fail on overflow (wrapping past -1; wrapping past
   OP_INT64_MAX is explicitly okay).
  [out] _dst_gp: The resulting granule position.
                 Only modified on success.
  _src_gp:       The granule position to add to.
                 This must not be -1.
  _delta:        The amount to add.
                 This is allowed to be up to 32 bits to support the maximum
                  duration of a single Ogg page (255 packets * 120 ms per
                  packet == 1,468,800 samples at 48 kHz).
  Return: 0 on success, or OP_EINVAL if the result would wrap around past -1.*/
static int op_granpos_add(ogg_int64_t *_dst_gp,ogg_int64_t _src_gp,
 opus_int32 _delta){
  /*The code below handles this case correctly, but there's no reason we
     should ever be called with these values, so make sure we aren't.*/
  OP_ASSERT(_src_gp!=-1);
  if(_delta>0){
    /*Adding this amount to the granule position would overflow its 64-bit
       range.*/
    if(OP_UNLIKELY(_src_gp<0)&&OP_UNLIKELY(_src_gp>=-1-_delta))return OP_EINVAL;
    if(OP_UNLIKELY(_src_gp>OP_INT64_MAX-_delta)){
      /*Adding this amount to the granule position would overflow the positive
         half of its 64-bit range.
        Since signed overflow is undefined in C, do it in a way the compiler
         isn't allowed to screw up.*/
      _delta-=(opus_int32)(OP_INT64_MAX-_src_gp)+1;
      _src_gp=OP_INT64_MIN;
    }
  }
  else if(_delta<0){
    /*Subtracting this amount from the granule position would underflow its
       64-bit range.*/
    if(_src_gp>=0&&OP_UNLIKELY(_src_gp<-_delta))return OP_EINVAL;
    if(OP_UNLIKELY(_src_gp<OP_INT64_MIN-_delta)){
      /*Subtracting this amount from the granule position would underflow the
         negative half of its 64-bit range.
        Since signed underflow is undefined in C, do it in a way the compiler
         isn't allowed to screw up.*/
      _delta+=(opus_int32)(_src_gp-OP_INT64_MIN)+1;
      _src_gp=OP_INT64_MAX;
    }
  }
  *_dst_gp=_src_gp+_delta;
  return 0;
}

/*Safely computes the difference between two granule positions.
  The difference must fit in a signed 64-bit integer, or the function fails.
  It correctly handles the case where the granule position has wrapped around
   from positive values to negative ones.
  [out] _delta: The difference between the granule positions.
                Only modified on success.
  _gp_a:        The granule position to subtract from.
                This must not be -1.
  _gp_b:        The granule position to subtract.
                This must not be -1.
  Return: 0 on success, or OP_EINVAL if the result would not fit in a signed
           64-bit integer.*/
static int op_granpos_diff(ogg_int64_t *_delta,
 ogg_int64_t _gp_a,ogg_int64_t _gp_b){
  int gp_a_negative;
  int gp_b_negative;
  /*The code below handles these cases correctly, but there's no reason we
     should ever be called with these values, so make sure we aren't.*/
  OP_ASSERT(_gp_a!=-1);
  OP_ASSERT(_gp_b!=-1);
  gp_a_negative=OP_UNLIKELY(_gp_a<0);
  gp_b_negative=OP_UNLIKELY(_gp_b<0);
  if(OP_UNLIKELY(gp_a_negative^gp_b_negative)){
    ogg_int64_t da;
    ogg_int64_t db;
    if(gp_a_negative){
      /*_gp_a has wrapped to a negative value but _gp_b hasn't: the difference
         should be positive.*/
      /*Step 1: Handle wrapping.*/
      /*_gp_a < 0 => da < 0.*/
      da=(OP_INT64_MIN-_gp_a)-1;
      /*_gp_b >= 0  => db >= 0.*/
      db=OP_INT64_MAX-_gp_b;
      /*Step 2: Check for overflow.*/
      if(OP_UNLIKELY(OP_INT64_MAX+da<db))return OP_EINVAL;
      *_delta=db-da;
    }
    else{
      /*_gp_b has wrapped to a negative value but _gp_a hasn't: the difference
         should be negative.*/
      /*Step 1: Handle wrapping.*/
      /*_gp_a >= 0 => da <= 0*/
      da=_gp_a+OP_INT64_MIN;
      /*_gp_b < 0 => db <= 0*/
      db=OP_INT64_MIN-_gp_b;
      /*Step 2: Check for overflow.*/
      if(OP_UNLIKELY(da<OP_INT64_MIN-db))return OP_EINVAL;
      *_delta=da+db;
    }
  }
  else *_delta=_gp_a-_gp_b;
  return 0;
}

static int op_granpos_cmp(ogg_int64_t _gp_a,ogg_int64_t _gp_b){
  /*The invalid granule position -1 should behave like NaN: neither greater
     than nor less than any other granule position, nor equal to any other
     granule position, including itself.
    However, that means there isn't anything we could sensibly return from this
     function for it.*/
  OP_ASSERT(_gp_a!=-1);
  OP_ASSERT(_gp_b!=-1);
  /*Handle the wrapping cases.*/
  if(OP_UNLIKELY(_gp_a<0)){
    if(_gp_b>=0)return 1;
    /*Else fall through.*/
  }
  else if(OP_UNLIKELY(_gp_b<0))return -1;
  /*No wrapping case.*/
  return (_gp_a>_gp_b)-(_gp_b>_gp_a);
}

/*Returns the duration of the packet (in samples at 48 kHz), or a negative
   value on error.*/
static int op_get_packet_duration(const unsigned char *_data,int _len){
  int nframes;
  int frame_size;
  int nsamples;
  nframes=opus_packet_get_nb_frames(_data,_len);
  if(OP_UNLIKELY(nframes<0))return OP_EBADPACKET;
  frame_size=opus_packet_get_samples_per_frame(_data,48000);
  nsamples=nframes*frame_size;
  if(OP_UNLIKELY(nsamples>120*48))return OP_EBADPACKET;
  return nsamples;
}

/*This function more properly belongs in info.c, but we define it here to allow
   the static granule position manipulation functions to remain static.*/
ogg_int64_t opus_granule_sample(const OpusHead *_head,ogg_int64_t _gp){
  opus_int32 pre_skip;
  pre_skip=_head->pre_skip;
  if(_gp!=-1&&op_granpos_add(&_gp,_gp,-pre_skip))_gp=-1;
  return _gp;
}

/*Grab all the packets currently in the stream state, and compute their
   durations.
  _of->op_count is set to the number of packets collected.
  [out] _durations: Returns the durations of the individual packets.
  Return: The total duration of all packets, or OP_HOLE if there was a hole.*/
static opus_int32 op_collect_audio_packets(OggOpusFile *_of,
 int _durations[255]){
  opus_int32 total_duration;
  int        op_count;
  /*Count the durations of all packets in the page.*/
  op_count=0;
  total_duration=0;
  for(;;){
    int ret;
    /*This takes advantage of undocumented libogg behavior that returned
       ogg_packet buffers are valid at least until the next page is
       submitted.
      Relying on this is not too terrible, as _none_ of the Ogg memory
       ownership/lifetime rules are well-documented.
      But I can read its code and know this will work.*/
    ret=ogg_stream_packetout(&_of->os,_of->op+op_count);
    if(!ret)break;
    if(OP_UNLIKELY(ret<0)){
      /*We shouldn't get holes in the middle of pages.*/
      OP_ASSERT(op_count==0);
785 786 787 788 789
      /*Set the return value and break out of the loop.
        We want to make sure op_count gets set to 0, because we've ingested a
         page, so any previously loaded packets are now invalid.*/
      total_duration=OP_HOLE;
      break;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
790
    }
791 792 793
    /*Unless libogg is broken, we can't get more than 255 packets from a
       single page.*/
    OP_ASSERT(op_count<255);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
794 795 796 797 798 799 800
    _durations[op_count]=op_get_packet_duration(_of->op[op_count].packet,
     _of->op[op_count].bytes);
    if(OP_LIKELY(_durations[op_count]>0)){
      /*With at most 255 packets on a page, this can't overflow.*/
      total_duration+=_durations[op_count++];
    }
    /*Ignore packets with an invalid TOC sequence.*/
801 802 803 804
    else if(op_count>0){
      /*But save the granule position, if there was one.*/
      _of->op[op_count-1].granulepos=_of->op[op_count].granulepos;
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
  }
  _of->op_pos=0;
  _of->op_count=op_count;
  return total_duration;
}

/*Starting from current cursor position, get the initial PCM offset of the next
   page.
  This also validates the granule position on the first page with a completed
   audio data packet, as required by the spec.
  If this link is completely empty (no pages with completed packets), then this
   function sets pcm_start=pcm_end=0 and returns the BOS page of the next link
   (if any).
  In the seekable case, we initialize pcm_end=-1 before calling this function,
   so that later we can detect that the link was empty before calling
   op_find_final_pcm_offset().
  [inout] _link: The link for which to find pcm_start.
  [out] _og:     Returns the BOS page of the next link if this link was empty.
                 In the unseekable case, we can then feed this to
                  op_fetch_headers() to start the next link.
                 The caller may pass NULL (e.g., for seekable streams), in
                  which case this page will be discarded.
  Return: 0 on success, 1 if there is a buffered BOS page available, or a
           negative value on unrecoverable error.*/
static int op_find_initial_pcm_offset(OggOpusFile *_of,
 OggOpusLink *_link,ogg_page *_og){
  ogg_page     og;
832
  opus_int64   page_offset;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
833 834 835 836 837 838 839 840 841 842 843
  ogg_int64_t  pcm_start;
  ogg_int64_t  prev_packet_gp;
  ogg_int64_t  cur_page_gp;
  ogg_uint32_t serialno;
  opus_int32   total_duration;
  int          durations[255];
  int          cur_page_eos;
  int          op_count;
  int          pi;
  if(_og==NULL)_og=&og;
  serialno=_of->os.serialno;
844 845 846 847 848
  op_count=0;
  /*We shouldn't have to initialize total_duration, but gcc is too dumb to
     figure out that op_count>0 implies we've been through the whole loop at
     least once.*/
  total_duration=0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
849
  do{
850
    page_offset=op_get_next_page(_of,_og,_of->end);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
851 852
    /*We should get a page unless the file is truncated or mangled.
      Otherwise there are no audio data packets in the whole logical stream.*/
853
    if(OP_UNLIKELY(page_offset<0)){
854
      /*Fail if there was a read error.*/
855
      if(page_offset<OP_FALSE)return (int)page_offset;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
856 857 858
      /*Fail if the pre-skip is non-zero, since it's asking us to skip more
         samples than exist.*/
      if(_link->head.pre_skip>0)return OP_EBADTIMESTAMP;
859
      _link->pcm_file_offset=0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
860 861 862 863 864 865 866 867 868 869 870
      /*Set pcm_end and end_offset so we can skip the call to
         op_find_final_pcm_offset().*/
      _link->pcm_start=_link->pcm_end=0;
      _link->end_offset=_link->data_offset;
      return 0;
    }
    /*Similarly, if we hit the next link in the chain, we've gone too far.*/
    if(OP_UNLIKELY(ogg_page_bos(_og))){
      if(_link->head.pre_skip>0)return OP_EBADTIMESTAMP;
      /*Set pcm_end and end_offset so we can skip the call to
         op_find_final_pcm_offset().*/
871 872
      _link->pcm_file_offset=0;
      _link->pcm_start=_link->pcm_end=0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934
      _link->end_offset=_link->data_offset;
      /*Tell the caller we've got a buffered page for them.*/
      return 1;
    }
    /*Ignore pages from other streams (not strictly necessary, because of the
       checks in ogg_stream_pagein(), but saves some work).*/
    if(serialno!=(ogg_uint32_t)ogg_page_serialno(_og))continue;
    ogg_stream_pagein(&_of->os,_og);
    /*Bitrate tracking: add the header's bytes here.
      The body bytes are counted when we consume the packets.*/
    _of->bytes_tracked+=_og->header_len;
    /*Count the durations of all packets in the page.*/
    do total_duration=op_collect_audio_packets(_of,durations);
    /*Ignore holes.*/
    while(OP_UNLIKELY(total_duration<0));
    op_count=_of->op_count;
  }
  while(op_count<=0);
  /*We found the first page with a completed audio data packet: actually look
     at the granule position.
    RFC 3533 says, "A special value of -1 (in two's complement) indicates that
     no packets finish on this page," which does not say that a granule
     position that is NOT -1 indicates that some packets DO finish on that page
     (even though this was the intention, libogg itself violated this intention
     for years before we fixed it).
    The Ogg Opus specification only imposes its start-time requirements
     on the granule position of the first page with completed packets,
     so we ignore any set granule positions until then.*/
  cur_page_gp=_of->op[op_count-1].granulepos;
  /*But getting a packet without a valid granule position on the page is not
     okay.*/
  if(cur_page_gp==-1)return OP_EBADTIMESTAMP;
  cur_page_eos=_of->op[op_count-1].e_o_s;
  if(OP_LIKELY(!cur_page_eos)){
    /*The EOS flag wasn't set.
      Work backwards from the provided granule position to get the starting PCM
       offset.*/
    if(OP_UNLIKELY(op_granpos_add(&pcm_start,cur_page_gp,-total_duration)<0)){
      /*The starting granule position MUST not be smaller than the amount of
         audio on the first page with completed packets.*/
      return OP_EBADTIMESTAMP;
    }
  }
  else{
    /*The first page with completed packets was also the last.*/
    if(OP_LIKELY(op_granpos_add(&pcm_start,cur_page_gp,-total_duration)<0)){
      /*If there's less audio on the page than indicated by the granule
         position, then we're doing end-trimming, and the starting PCM offset
         is zero by spec mandate.*/
      pcm_start=0;
      /*However, the end-trimming MUST not ask us to trim more samples than
         exist after applying the pre-skip.*/
      if(OP_UNLIKELY(op_granpos_cmp(cur_page_gp,_link->head.pre_skip)<0)){
        return OP_EBADTIMESTAMP;
      }
    }
  }
  /*Timestamp the individual packets.*/
  prev_packet_gp=pcm_start;
  for(pi=0;pi<op_count;pi++){
    if(cur_page_eos){
      ogg_int64_t diff;
935
      OP_ALWAYS_TRUE(!op_granpos_diff(&diff,cur_page_gp,prev_packet_gp));
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
936 937 938 939 940 941 942 943 944 945 946 947 948 949
      diff=durations[pi]-diff;
      /*If we have samples to trim...*/
      if(diff>0){
        /*If we trimmed the entire packet, stop (the spec says encoders
           shouldn't do this, but we support it anyway).*/
        if(OP_UNLIKELY(diff>durations[pi]))break;
        _of->op[pi].granulepos=prev_packet_gp=cur_page_gp;
        /*Move the EOS flag to this packet, if necessary, so we'll trim the
           samples.*/
        _of->op[pi].e_o_s=1;
        continue;
      }
    }
    /*Update the granule position as normal.*/
950 951
    OP_ALWAYS_TRUE(!op_granpos_add(&_of->op[pi].granulepos,
     prev_packet_gp,durations[pi]));
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
952 953 954 955 956
    prev_packet_gp=_of->op[pi].granulepos;
  }
  /*Update the packet count after end-trimming.*/
  _of->op_count=pi;
  _of->cur_discard_count=_link->head.pre_skip;
957
  _link->pcm_file_offset=0;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
958
  _of->prev_packet_gp=_link->pcm_start=pcm_start;
959
  _of->prev_page_offset=page_offset;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
960 961 962 963 964 965 966 967 968 969 970 971 972 973
  return 0;
}

/*Starting from current cursor position, get the final PCM offset of the
   previous page.
  This also validates the duration of the link, which, while not strictly
   required by the spec, we need to ensure duration calculations don't
   overflow.
  This is only done for seekable sources.
  We must validate that op_find_initial_pcm_offset() succeeded for this link
   before calling this function, otherwise it will scan the entire stream
   backwards until it reaches the start, and then fail.*/
static int op_find_final_pcm_offset(OggOpusFile *_of,
 const ogg_uint32_t *_serialnos,int _nserialnos,OggOpusLink *_link,
974
 opus_int64 _offset,ogg_uint32_t _end_serialno,ogg_int64_t _end_gp,
975
 ogg_int64_t *_total_duration){
976 977 978
  ogg_int64_t  total_duration;
  ogg_int64_t  duration;
  ogg_uint32_t cur_serialno;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
979 980
  /*For the time being, fetch end PCM offset the simple way.*/
  cur_serialno=_link->serialno;
981 982
  if(_end_serialno!=cur_serialno||_end_gp==-1){
    _offset=op_get_last_page(_of,&_end_gp,_offset,
983
     cur_serialno,_serialnos,_nserialnos);
984
    if(OP_UNLIKELY(_offset<0))return (int)_offset;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
985
  }
986 987
  /*At worst we should have found the first page with completed packets.*/
  if(OP_UNLIKELY(_offset<_link->data_offset))return OP_EBADLINK;
988
  /*This implementation requires that the difference between the first and last
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
989 990 991
     granule positions in each link be representable in a signed, 64-bit
     number, and that each link also have at least as many samples as the
     pre-skip requires.*/
992
  if(OP_UNLIKELY(op_granpos_diff(&duration,_end_gp,_link->pcm_start)<0)
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
993 994 995 996 997 998 999 1000 1001
   ||OP_UNLIKELY(duration<_link->head.pre_skip)){
    return OP_EBADTIMESTAMP;
  }
  /*We also require that the total duration be representable in a signed,
     64-bit number.*/
  duration-=_link->head.pre_skip;
  total_duration=*_total_duration;
  if(OP_UNLIKELY(OP_INT64_MAX-duration<total_duration))return OP_EBADTIMESTAMP;
  *_total_duration=total_duration+duration;
1002 1003
  _link->pcm_end=_end_gp;
  _link->end_offset=_offset;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1004 1005 1006
  return 0;
}

1007 1008
/*Rescale the number _x from the range [0,_from] to [0,_to].
  _from and _to must be positive.*/
1009
static opus_int64 op_rescale64(opus_int64 _x,opus_int64 _from,opus_int64 _to){
1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032
  opus_int64 frac;
  opus_int64 ret;
  int        i;
  if(_x>=_from)return _to;
  if(_x<=0)return 0;
  frac=0;
  for(i=0;i<63;i++){
    frac<<=1;
    OP_ASSERT(_x<=_from);
    if(_x>=_from>>1){
      _x-=_from-_x;
      frac|=1;
    }
    else _x<<=1;
  }
  ret=0;
  for(i=0;i<63;i++){
    if(frac&1)ret=(ret&_to&1)+(ret>>1)+(_to>>1);
    else ret>>=1;
    frac>>=1;
  }
  return ret;
}
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1033

1034 1035 1036 1037 1038 1039 1040 1041 1042 1043
/*The minimum granule position spacing allowed for making predictions.
  This corresponds to about 1 second of audio at 48 kHz for both Opus and
   Vorbis, or one keyframe interval in Theora with the default keyframe spacing
   of 256.*/
#define OP_GP_SPACING_MIN (48000)

/*Try to estimate the location of the next link using the current seek
   records, assuming the initial granule position of any streams we've found is
   0.*/
static opus_int64 op_predict_link_start(const OpusSeekRecord *_sr,int _nsr,
1044
 opus_int64 _searched,opus_int64 _end_searched,opus_int32 _bias){
1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075
  opus_int64 bisect;
  int        sri;
  int        srj;
  /*Require that we be at least OP_CHUNK_SIZE from the end.
    We don't require that we be at least OP_CHUNK_SIZE from the beginning,
     because if we are we'll just scan forward without seeking.*/
  _end_searched-=OP_CHUNK_SIZE;
  if(_searched>=_end_searched)return -1;
  bisect=_end_searched;
  for(sri=0;sri<_nsr;sri++){
    ogg_int64_t  gp1;
    ogg_int64_t  gp2_min;
    ogg_uint32_t serialno1;
    opus_int64   offset1;
    /*If the granule position is negative, either it's invalid or we'd cause
       overflow.*/
    gp1=_sr[sri].gp;
    if(gp1<0)continue;
    /*We require some minimum distance between granule positions to make an
       estimate.
      We don't actually know what granule position scheme is being used,
       because we have no idea what kind of stream these came from.
      Therefore we require a minimum spacing between them, with the
       expectation that while bitrates and granule position increments might
       vary locally in quite complex ways, they are globally smooth.*/
    if(OP_UNLIKELY(op_granpos_add(&gp2_min,gp1,OP_GP_SPACING_MIN)<0)){
      /*No granule position would satisfy us.*/
      continue;
    }
    offset1=_sr[sri].offset;
    serialno1=_sr[sri].serialno;
1076
    for(srj=sri;srj-->0;){
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1077 1078 1079 1080 1081
      ogg_int64_t gp2;
      opus_int64  offset2;
      opus_int64  num;
      ogg_int64_t den;
      ogg_int64_t ipart;
1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
      gp2=_sr[srj].gp;
      if(gp2<gp2_min)continue;
      /*Oh, and also make sure these came from the same stream.*/
      if(_sr[srj].serialno!=serialno1)continue;
      offset2=_sr[srj].offset;
      /*For once, we can subtract with impunity.*/
      den=gp2-gp1;
      ipart=gp2/den;
      num=offset2-offset1;
      OP_ASSERT(num>0);
      if(ipart>0&&(offset2-_searched)/ipart<num)continue;
      offset2-=ipart*num;
      gp2-=ipart*den;
1095
      offset2-=op_rescale64(gp2,den,num)-_bias;
1096 1097
      if(offset2<_searched)continue;
      bisect=OP_MIN(bisect,offset2);
1098
      break;
1099 1100 1101 1102
    }
  }
  return bisect>=_end_searched?-1:bisect;
}
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1103 1104 1105 1106

/*Finds each bitstream link, one at a time, using a bisection search.
  This has to begin by knowing the offset of the first link's initial page.*/
static int op_bisect_forward_serialno(OggOpusFile *_of,
1107
 opus_int64 _searched,OpusSeekRecord *_sr,int _csr,
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129
 ogg_uint32_t **_serialnos,int *_nserialnos,int *_cserialnos){
  ogg_page      og;
  OggOpusLink  *links;
  int           nlinks;
  int           clinks;
  ogg_uint32_t *serialnos;
  int           nserialnos;
  ogg_int64_t   total_duration;
  int           nsr;
  int           ret;
  links=_of->links;
  nlinks=clinks=_of->nlinks;
  total_duration=0;
  /*We start with one seek record, for the last page in the file.
    We build up a list of records for places we seek to during link
     enumeration.
    This list is kept sorted in reverse order.
    We only care about seek locations that were _not_ in the current link,
     therefore we can add them one at a time to the end of the list as we
     improve the lower bound on the location where the next link starts.*/
  nsr=1;
  for(;;){
1130 1131 1132 1133
    opus_int64  end_searched;
    opus_int64  bisect;
    opus_int64  next;
    opus_int64  last;
1134
    ogg_int64_t end_offset;
1135 1136
    ogg_int64_t end_gp;
    int         sri;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1137 1138 1139 1140 1141 1142
    serialnos=*_serialnos;
    nserialnos=*_nserialnos;
    if(OP_UNLIKELY(nlinks>=clinks)){
      if(OP_UNLIKELY(clinks>INT_MAX-1>>1))return OP_EFAULT;
      clinks=2*clinks+1;
      OP_ASSERT(nlinks<clinks);
1143
      links=(OggOpusLink *)_ogg_realloc(links,sizeof(*links)*clinks);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1144 1145 1146 1147 1148 1149 1150 1151 1152
      if(OP_UNLIKELY(links==NULL))return OP_EFAULT;
      _of->links=links;
    }
    /*Invariants:
      We have the headers and serial numbers for the link beginning at 'begin'.
      We have the offset and granule position of the last page in the file
       (potentially not a page we care about).*/
    /*Scan the seek records we already have to save us some bisection.*/
    for(sri=0;sri<nsr;sri++){
1153
      if(op_lookup_serialno(_sr[sri].serialno,serialnos,nserialnos))break;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1154 1155 1156 1157 1158
    }
    /*Is the last page in our current list of serial numbers?*/
    if(sri<=0)break;
    /*Last page wasn't found.
      We have at least one more link.*/
1159
    last=-1;
1160 1161
    end_searched=_sr[sri-1].search_start;
    next=_sr[sri-1].offset;
1162 1163 1164
    end_gp=-1;
    if(sri<nsr){
      _searched=_sr[sri].offset+_sr[sri].size;
1165 1166 1167 1168
      if(_sr[sri].serialno==links[nlinks-1].serialno){
        end_gp=_sr[sri].gp;
        end_offset=_sr[sri].offset;
      }
1169
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1170
    nsr=sri;
1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188
    bisect=-1;
    /*If we've already found the end of at least one link, try to pick the
       first bisection point at twice the average link size.
      This is a good choice for files with lots of links that are all about the
       same size.*/
    if(nlinks>1){
      opus_int64 last_offset;
      opus_int64 avg_link_size;
      opus_int64 upper_limit;
      last_offset=links[nlinks-1].offset;
      avg_link_size=last_offset/(nlinks-1);
      upper_limit=end_searched-OP_CHUNK_SIZE-avg_link_size;
      if(OP_LIKELY(last_offset>_searched-avg_link_size)
       &&OP_LIKELY(last_offset<upper_limit)){
        bisect=last_offset+avg_link_size;
        if(OP_LIKELY(bisect<upper_limit))bisect+=avg_link_size;
      }
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1189 1190 1191
    /*We guard against garbage separating the last and first pages of two
       links below.*/
    while(_searched<end_searched){
1192
      opus_int32 next_bias;
1193
      /*If we don't have a better estimate, use simple bisection.*/
1194
      if(bisect==-1)bisect=_searched+(end_searched-_searched>>1);
1195 1196 1197 1198
      /*If we're within OP_CHUNK_SIZE of the start, scan forward.*/
      if(bisect-_searched<OP_CHUNK_SIZE)bisect=_searched;
      /*Otherwise we're skipping data.
        Forget the end page, if we saw one, as we might miss a later one.*/
1199
      else end_gp=-1;
1200 1201
      ret=op_seek_helper(_of,bisect);
      if(OP_UNLIKELY(ret<0))return ret;
1202 1203 1204 1205
      last=op_get_next_page(_of,&og,_sr[nsr-1].offset);
      if(OP_UNLIKELY(last<OP_FALSE))return (int)last;
      next_bias=0;
      if(last==OP_FALSE)end_searched=bisect;
1206
      else{
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
        ogg_uint32_t serialno;
        ogg_int64_t  gp;
        serialno=ogg_page_serialno(&og);
        gp=ogg_page_granulepos(&og);
        if(!op_lookup_serialno(serialno,serialnos,nserialnos)){
          end_searched=bisect;
          next=last;
          /*In reality we should always have enough room, but be paranoid.*/
          if(OP_LIKELY(nsr<_csr)){
            _sr[nsr].search_start=bisect;
            _sr[nsr].offset=last;
            OP_ASSERT(_of->offset-last>=0);
            OP_ASSERT(_of->offset-last<=OP_PAGE_SIZE_MAX);
            _sr[nsr].size=(opus_int32)(_of->offset-last);
            _sr[nsr].serialno=serialno;
            _sr[nsr].gp=gp;
            nsr++;
          }
        }
        else{
          _searched=_of->offset;
          next_bias=OP_CHUNK_SIZE;
          if(serialno==links[nlinks-1].serialno){
            /*This page was from the stream we want, remember it.
              If it's the last such page in the link, we won't have to go back
               looking for it later.*/
            end_gp=gp;
            end_offset=last;
          }
1236
        }
1237
      }
1238
      bisect=op_predict_link_start(_sr,nsr,_searched,end_searched,next_bias);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1239 1240 1241 1242 1243 1244
    }
    /*Bisection point found.
      Get the final granule position of the previous link, assuming
       op_find_initial_pcm_offset() didn't already determine the link was
       empty.*/
    if(OP_LIKELY(links[nlinks-1].pcm_end==-1)){
1245 1246 1247 1248 1249 1250 1251 1252
      if(end_gp==-1){
        /*If we don't know where the end page is, we'll have to seek back and
           look for it, starting from the end of the link.*/
        end_offset=next;
        /*Also forget the last page we read.
          It won't be available after the seek.*/
        last=-1;
      }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1253
      ret=op_find_final_pcm_offset(_of,serialnos,nserialnos,
1254 1255
       links+nlinks-1,end_offset,links[nlinks-1].serialno,end_gp,
       &total_duration);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1256 1257
      if(OP_UNLIKELY(ret<0))return ret;
    }
1258
    if(last!=next){
1259 1260 1261 1262 1263
      /*The last page we read was not the first page the next link.
        Move the cursor position to the offset of that first page.
        This only performs an actual seek if the first page of the next link
         does not start at the end of the last page from the current Opus
         stream with a valid granule position.*/
1264 1265 1266
      ret=op_seek_helper(_of,next);
      if(OP_UNLIKELY(ret<0))return ret;
    }
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1267
    ret=op_fetch_headers(_of,&links[nlinks].head,&links[nlinks].tags,
1268
     _serialnos,_nserialnos,_cserialnos,last!=next?NULL:&og);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1269 1270 1271 1272 1273 1274 1275 1276 1277
    if(OP_UNLIKELY(ret<0))return ret;
    links[nlinks].offset=next;
    links[nlinks].data_offset=_of->offset;
    links[nlinks].serialno=_of->os.serialno;
    links[nlinks].pcm_end=-1;
    /*This might consume a page from the next link, however the next bisection
       always starts with a seek.*/
    ret=op_find_initial_pcm_offset(_of,links+nlinks,NULL);
    if(OP_UNLIKELY(ret<0))return ret;
1278
    links[nlinks].pcm_file_offset=total_duration;
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1279 1280 1281 1282 1283 1284 1285 1286 1287 1288
    _searched=_of->offset;
    /*Mark the current link count so it can be cleaned up on error.*/
    _of->nlinks=++nlinks;
  }
  /*Last page is in the starting serialno list, so we've reached the last link.
    Now find the last granule position for it (if we didn't the first time we
     looked at the end of the stream, and if op_find_initial_pcm_offset()
     didn't already determine the link was empty).*/
  if(OP_LIKELY(links[nlinks-1].pcm_end==-1)){
    ret=op_find_final_pcm_offset(_of,serialnos,nserialnos,
1289
     links+nlinks-1,_sr[0].offset,_sr[0].serialno,_sr[0].gp,&total_duration);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1290 1291 1292
    if(OP_UNLIKELY(ret<0))return ret;
  }
  /*Trim back the links array if necessary.*/
1293
  links=(OggOpusLink *)_ogg_realloc(links,sizeof(*links)*nlinks);
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
1294 1295 1296 1297 1298 1299 1300 1301
  if(OP_LIKELY(links!=NULL))_of->links=links;
  /*We also don't need these anymore.*/
  _ogg_free(*_serialnos);
  *_serialnos=NULL;
  *_cserialnos=*_nserialnos=0;
  return 0;
}

1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315
static void op_update_gain(OggOpusFile *_of){
  OpusHead   *head;
  opus_int32  gain_q8;
  int         li;
  /*If decode isn't ready, then we'll apply the gain when we initialize the
     decoder.*/
  if(_of->ready_state<OP_INITSET)return;
  gain_q8=_of->gain_offset_q8;
  li=_of->seekable?_of->cur_link:0;
  head=&_of->links[li].head;
  /*We don't have to worry about overflow here because the header gain and
     track gain must lie in the range [-32768,32767], and the user-supplied
     offset has been pre-clamped to [-98302,98303].*/
  switch(_of->gain_type){
1316 1317 1318 1319 1320 1321 1322
    case OP_ALBUM_GAIN:{
      int album_gain_q8;
      album_gain_q8=0;
      opus_tags_get_album_gain(&_of->links[li].tags,&album_gain_q8);
      gain_q8+=album_gain_q8;
      gain_q8+=head->output_gain;
    }break;
1323 1324 1325 1326 1327
    case OP_TRACK_GAIN:{
      int track_gain_q8;
      track_gain_q8=0;
      opus_tags_get_track_gain(&_of->links[li].tags,&track_gain_q8);
      gain_q8+=track_gain_q8;
1328 1329
      gain_q8+=head->output_gain;
    }break;
1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345
    case OP_HEADER_GAIN:gain_q8+=head->output_gain;break;
    case OP_ABSOLUTE_GAIN:break;
    default:OP_ASSERT(0);
  }
  gain_q8=OP_CLAMP(-32768,gain_q8,32767);
  OP_ASSERT(_of