src/opusfile.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE libopusfile SOFTWARE CODEC SOURCE CODE. *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE libopusfile SOURCE CODE IS (C) COPYRIGHT 1994-2012           *
   9  * by the Xiph.Org Foundation and contributors http://www.xiph.org/ *
  10  *                                                                  *
  11  ********************************************************************
  12
  13  function: stdio-based convenience library for opening/seeking/decoding
  14  last mod: $Id: vorbisfile.c 17573 2010-10-27 14:53:59Z xiphmont $
  15
  16  ********************************************************************/
  17 #include "internal.h"
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <errno.h>
  21 #include <limits.h>
  22 #include <string.h>
  23 #include <math.h>
  24
  25 #include "opusfile.h"
  26
  27 /*This implementation is largely based off of libvorbisfile.
  28   All of the Ogg bits work roughly the same, though I have made some
  29    "improvements" that have not been folded back there, yet.*/
  30
  31 /*A 'chained bitstream' is an Ogg Opus bitstream that contains more than one
  32    logical bitstream arranged end to end (the only form of Ogg multiplexing
  33    supported by this library.
  34   Grouping (parallel multiplexing) is not supported, except to the extent that
  35    if there are multiple logical Ogg streams in a single link of the chain, we
  36    will ignore all but the first Opus stream we find.*/
  37
  38 /*An Ogg Opus file can be played beginning to end (streamed) without worrying
  39    ahead of time about chaining (see opusdec from the opus-tools package).
  40   If we have the whole file, however, and want random access
  41    (seeking/scrubbing) or desire to know the total length/time of a file, we
  42    need to account for the possibility of chaining.*/
  43
  44 /*We can handle things a number of ways.
  45   We can determine the entire bitstream structure right off the bat, or find
  46    pieces on demand.
  47   This library determines and caches structure for the entire bitstream, but
  48    builds a virtual decoder on the fly when moving between links in the chain.*/
  49
  50 /*There are also different ways to implement seeking.
  51   Enough information exists in an Ogg bitstream to seek to sample-granularity
  52    positions in the output.
  53   Or, one can seek by picking some portion of the stream roughly in the desired
  54    area if we only want coarse navigation through the stream.
  55   We implement and expose both strategies.*/
  56
  57 /*The maximum number of bytes in a page (including the page headers).*/
  58 #define OP_PAGE_SIZE_MAX  (65307)
  59 /*The default amount to seek backwards per step when trying to find the
  60    previous page.
  61   This must be at least as large as the maximum size of a page.*/
  62 #define OP_CHUNK_SIZE     (65536)
  63 /*The maximum amount to seek backwards per step when trying to find the
  64    previous page.*/
  65 #define OP_CHUNK_SIZE_MAX (1024*(opus_int32)1024)
  66 /*A smaller read size is needed for low-rate streaming.*/
  67 #define OP_READ_SIZE      (2048)
  68
  69 int op_test(OpusHead *_head,
  70  const unsigned char *_initial_data,size_t _initial_bytes){
  71   ogg_sync_state  oy;
  72   char           *data;
  73   int             err;
  74   /*The first page of a normal Opus file will be at most 57 bytes (27 Ogg
  75      page header bytes + 1 lacing value + 21 Opus header bytes + 8 channel
  76      mapping bytes).
  77     It will be at least 47 bytes (27 Ogg page header bytes + 1 lacing value +
  78      19 Opus header bytes using channel mapping family 0).
  79     If we don't have at least that much data, give up now.*/
  80   if(_initial_bytes<47)return OP_FALSE;
  81   /*Only proceed if we start with the magic OggS string.
  82     This is to prevent us spending a lot of time allocating memory and looking
  83      for Ogg pages in non-Ogg files.*/
  84   if(memcmp(_initial_data,"OggS",4)!=0)return OP_ENOTFORMAT;
  85   ogg_sync_init(&oy);
  86   data=ogg_sync_buffer(&oy,_initial_bytes);
  87   if(data!=NULL){
  88     ogg_stream_state os;
  89     ogg_page         og;
  90     int              ret;
  91     memcpy(data,_initial_data,_initial_bytes);
  92     ogg_sync_wrote(&oy,_initial_bytes);
  93     ogg_stream_init(&os,-1);
  94     err=OP_FALSE;
  95     do{
  96       ogg_packet op;
  97       ret=ogg_sync_pageout(&oy,&og);
  98       /*Ignore holes.*/
  99       if(ret<0)continue;
 100       /*Stop if we run out of data.*/
 101       if(!ret)break;
 102       ogg_stream_reset_serialno(&os,ogg_page_serialno(&og));
 103       ogg_stream_pagein(&os,&og);
 104       /*Only process the first packet on this page (if it's a BOS packet,
 105          it's required to be the only one).*/
 106       if(ogg_stream_packetout(&os,&op)==1){
 107         if(op.b_o_s){
 108           ret=opus_head_parse(_head,op.packet,op.bytes);
 109           /*If this didn't look like Opus, keep going.*/
 110           if(ret==OP_ENOTFORMAT)continue;
 111           /*Otherwise we're done, one way or another.*/
 112           err=ret;
 113         }
 114         /*We finished parsing the headers.
 115           There is no Opus to be found.*/
 116         else err=OP_ENOTFORMAT;
 117       }
 118     }
 119     while(err==OP_FALSE);
 120     ogg_stream_clear(&os);
 121   }
 122   else err=OP_EFAULT;
 123   ogg_sync_clear(&oy);
 124   return err;
 125 }
 126
 127 /*Many, many internal helpers.
 128   The intention is not to be confusing.
 129   Rampant duplication and monolithic function implementation (though we do have
 130    some large, omnibus functions still) would be harder to understand anyway.
 131   The high level functions are last.
 132   Begin grokking near the end of the file if you prefer to read things
 133    top-down.*/
 134
 135 /*The read/seek functions track absolute position within the stream.*/
 136
 137 /*Read a little more data from the file/pipe into the ogg_sync framer.
 138   _nbytes: The maximum number of bytes to read.
 139   Return: A positive number of bytes read on success, 0 on end-of-file, or a
 140            negative value on failure.*/
 141 static int op_get_data(OggOpusFile *_of,int _nbytes){
 142   unsigned char *buffer;
 143   int            nbytes;
 144   OP_ASSERT(_nbytes>0);
 145   buffer=(unsigned char *)ogg_sync_buffer(&_of->oy,_nbytes);
 146   nbytes=(int)(*_of->callbacks.read)(_of->source,buffer,_nbytes);
 147   OP_ASSERT(nbytes<=_nbytes);
 148   if(OP_LIKELY(nbytes>0))ogg_sync_wrote(&_of->oy,nbytes);
 149   return nbytes;
 150 }
 151
 152 /*Save a tiny smidge of verbosity to make the code more readable.*/
 153 static int op_seek_helper(OggOpusFile *_of,opus_int64 _offset){
 154   if(_offset==_of->offset)return 0;
 155   if(_of->callbacks.seek==NULL||
 156    (*_of->callbacks.seek)(_of->source,_offset,SEEK_SET)){
 157     return OP_EREAD;
 158   }
 159   _of->offset=_offset;
 160   ogg_sync_reset(&_of->oy);
 161   return 0;
 162 }
 163
 164 /*Get the current position indicator of the underlying source.
 165   This should be the same as the value reported by tell().*/
 166 static opus_int64 op_position(OggOpusFile *_of){
 167   /*The current position indicator is _not_ simply offset.
 168     We may also have unprocessed, buffered data in the sync state.*/
 169   return _of->offset+_of->oy.fill-_of->oy.returned;
 170 }
 171
 172 /*From the head of the stream, get the next page.
 173   _boundary specifies if the function is allowed to fetch more data from the
 174    stream (and how much) or only use internally buffered data.
 175   _boundary: -1: Unbounded search.
 176               0: Read no additional data.
 177                  Use only cached data.
 178               n: Search for the start of a new page up to file position n.
 179   Return: n>=0:       Found a page at absolute offset n.
 180           OP_FALSE:   Hit the _boundary limit.
 181           OP_EREAD:   An underlying read operation failed.
 182           OP_BADLINK: We hit end-of-file before reaching _boundary.*/
 183 static opus_int64 op_get_next_page(OggOpusFile *_of,ogg_page *_og,
 184  opus_int64 _boundary){
 185   while(_boundary<=0||_of->offset<_boundary){
 186     int more;
 187     more=ogg_sync_pageseek(&_of->oy,_og);
 188     /*Skipped (-more) bytes.*/
 189     if(OP_UNLIKELY(more<0))_of->offset-=more;
 190     else if(more==0){
 191       int read_nbytes;
 192       int ret;
 193       /*Send more paramedics.*/
 194       if(!_boundary)return OP_FALSE;
 195       if(_boundary<0)read_nbytes=OP_READ_SIZE;
 196       else{
 197         opus_int64 position;
 198         position=op_position(_of);
 199         if(position>=_boundary)return OP_FALSE;
 200         read_nbytes=(int)OP_MIN(_boundary-position,OP_READ_SIZE);
 201       }
 202       ret=op_get_data(_of,read_nbytes);
 203       if(OP_UNLIKELY(ret<0))return OP_EREAD;
 204       if(OP_UNLIKELY(ret==0)){
 205         /*Only fail cleanly on EOF if we didn't have a known boundary.
 206           Otherwise, we should have been able to reach that boundary, and this
 207            is a fatal error.*/
 208         return OP_UNLIKELY(_boundary<0)?OP_FALSE:OP_EBADLINK;
 209       }
 210     }
 211     else{
 212       /*Got a page.
 213         Return the page start offset and advance the internal offset past the
 214          page end.*/
 215       opus_int64 page_offset;
 216       page_offset=_of->offset;
 217       _of->offset+=more;
 218       OP_ASSERT(page_offset>=0);
 219       return page_offset;
 220     }
 221   }
 222   return OP_FALSE;
 223 }
 224
 225 static int op_add_serialno(ogg_page *_og,
 226  ogg_uint32_t **_serialnos,int *_nserialnos,int *_cserialnos){
 227   ogg_uint32_t *serialnos;
 228   int           nserialnos;
 229   int           cserialnos;
 230   ogg_uint32_t s;
 231   s=ogg_page_serialno(_og);
 232   serialnos=*_serialnos;
 233   nserialnos=*_nserialnos;
 234   cserialnos=*_cserialnos;
 235   if(OP_UNLIKELY(nserialnos>=cserialnos)){
 236     if(OP_UNLIKELY(cserialnos>INT_MAX-1>>1))return OP_EFAULT;
 237     cserialnos=2*cserialnos+1;
 238     OP_ASSERT(nserialnos<cserialnos);
 239     serialnos=(ogg_uint32_t *)_ogg_realloc(serialnos,
 240      sizeof(*serialnos)*cserialnos);
 241     if(OP_UNLIKELY(serialnos==NULL))return OP_EFAULT;
 242   }
 243   serialnos[nserialnos++]=s;
 244   *_serialnos=serialnos;
 245   *_nserialnos=nserialnos;
 246   *_cserialnos=cserialnos;
 247   return 0;
 248 }
 249
 250 /*Returns nonzero if found.*/
 251 static int op_lookup_serialno(ogg_uint32_t _s,
 252  const ogg_uint32_t *_serialnos,int _nserialnos){
 253   int i;
 254   for(i=0;i<_nserialnos&&_serialnos[i]!=_s;i++);
 255   return i<_nserialnos;
 256 }
 257
 258 static int op_lookup_page_serialno(ogg_page *_og,
 259  const ogg_uint32_t *_serialnos,int _nserialnos){
 260   return op_lookup_serialno(ogg_page_serialno(_og),_serialnos,_nserialnos);
 261 }
 262
 263 typedef struct OpusSeekRecord OpusSeekRecord;
 264
 265 /*We use this to remember the pages we found while enumerating the links of a
 266    chained stream.
 267   We keep track of the starting and ending offsets, as well as the point we
 268    started searching from, so we know where to bisect.
 269   We also keep the serial number, so we can tell if the page belonged to the
 270    current link or not, as well as the granule position, to aid in estimating
 271    the start of the link.*/
 272 struct OpusSeekRecord{
 273   /*The earliest byte we know of such that reading forward from it causes
 274      capture to be regained at this page.*/
 275   opus_int64   search_start;
 276   /*The offset of this page.*/
 277   opus_int64   offset;
 278   /*The size of this page.*/
 279   opus_int32   size;
 280   /*The serial number of this page.*/
 281   ogg_uint32_t serialno;
 282   /*The granule position of this page.*/
 283   ogg_int64_t  gp;
 284 };
 285
 286 /*Find the last page beginning before _offset with a valid granule position.
 287   There is no '_boundary' parameter as it will always have to read more data.
 288   This is much dirtier than the above, as Ogg doesn't have any backward search
 289    linkage.
 290   This search prefers pages of the specified serial number.
 291   If a page of the specified serial number is spotted during the
 292    seek-back-and-read-forward, it will return the info of last page of the
 293    matching serial number, instead of the very last page, unless the very last
 294    page belongs to a different link than preferred serial number.
 295   If no page of the specified serial number is seen, it will return the info of
 296    the last page.
 297   [out] _sr:   Returns information about the page that was found on success.
 298   _offset:     The _offset before which to find a page.
 299                Any page returned will consist of data entirely before _offset.
 300   _serialno:   The preferred serial number.
 301                If a page with this serial number is found, it will be returned
 302                 even if another page in the same link is found closer to
 303                 _offset.
 304                This is purely opportunistic: there is no guarantee such a page
 305                 will be found if it exists.
 306   _serialnos:  The list of serial numbers in the link that contains the
 307                 preferred serial number.
 308   _nserialnos: The number of serial numbers in the current link.
 309   Return: 0 on success, or a negative value on failure.
 310           OP_EREAD:    Failed to read more data (error or EOF).
 311           OP_EBADLINK: We couldn't find a page even after seeking back to the
 312                         start of the stream.*/
 313 static int op_get_prev_page_serial(OggOpusFile *_of,OpusSeekRecord *_sr,
 314  opus_int64 _offset,ogg_uint32_t _serialno,
 315  const ogg_uint32_t *_serialnos,int _nserialnos){
 316   OpusSeekRecord preferred_sr;
 317   ogg_page       og;
 318   opus_int64     begin;
 319   opus_int64     end;
 320   opus_int64     original_end;
 321   opus_int32     chunk_size;
 322   int            preferred_found;
 323   original_end=end=begin=_offset;
 324   preferred_found=0;
 325   _offset=-1;
 326   chunk_size=OP_CHUNK_SIZE;
 327   do{
 328     opus_int64 search_start;
 329     int        ret;
 330     OP_ASSERT(chunk_size>=OP_PAGE_SIZE_MAX);
 331     begin=OP_MAX(begin-chunk_size,0);
 332     ret=op_seek_helper(_of,begin);
 333     if(OP_UNLIKELY(ret<0))return ret;
 334     search_start=begin;
 335     while(_of->offset<end){
 336       opus_int64   llret;
 337       ogg_uint32_t serialno;
 338       llret=op_get_next_page(_of,&og,end);
 339       if(OP_UNLIKELY(llret<OP_FALSE))return (int)llret;
 340       else if(llret==OP_FALSE)break;
 341       serialno=ogg_page_serialno(&og);
 342       /*Save the information for this page.
 343         We're not interested in the page itself... just the serial number, byte
 344          offset, page size, and granule position.*/
 345       _sr->search_start=search_start;
 346       _sr->offset=_offset=llret;
 347       _sr->serialno=serialno;
 348       OP_ASSERT(_of->offset-_offset>=0);
 349       OP_ASSERT(_of->offset-_offset<=OP_PAGE_SIZE_MAX);
 350       _sr->size=(opus_int32)(_of->offset-_offset);
 351       _sr->gp=ogg_page_granulepos(&og);
 352       /*If this page is from the stream we're looking for, remember it.*/
 353       if(serialno==_serialno){
 354         preferred_found=1;
 355         *&preferred_sr=*_sr;
 356       }
 357       if(!op_lookup_serialno(serialno,_serialnos,_nserialnos)){
 358         /*We fell off the end of the link, which means we seeked back too far
 359            and shouldn't have been looking in that link to begin with.
 360           If we found the preferred serial number, forget that we saw it.*/
 361         preferred_found=0;
 362       }
 363       search_start=llret+1;
 364     }
 365     /*We started from the beginning of the stream and found nothing.
 366       This should be impossible unless the contents of the source changed out
 367        from under us after we read from it.*/
 368     if(OP_UNLIKELY(!begin)&&OP_UNLIKELY(_offset<0))return OP_EBADLINK;
 369     /*Bump up the chunk size.
 370       This is mildly helpful when seeks are very expensive (http).*/
 371     chunk_size=OP_MIN(2*chunk_size,OP_CHUNK_SIZE_MAX);
 372     /*Avoid quadratic complexity if we hit an invalid patch of the file.*/
 373     end=OP_MIN(begin+OP_PAGE_SIZE_MAX-1,original_end);
 374   }
 375   while(_offset<0);
 376   if(preferred_found)*_sr=*&preferred_sr;
 377   return 0;
 378 }
 379
 380 /*Find the last page beginning before _offset with the given serial number and
 381    a valid granule position.
 382   Unlike the above search, this continues until it finds such a page, but does
 383    not stray outside the current link.
 384   We could implement it (inefficiently) by calling op_get_prev_page_serial()
 385    repeatedly until it returned a page that had both our preferred serial
 386    number and a valid granule position, but doing it with a separate function
 387    allows us to avoid repeatedly re-scanning valid pages from other streams as
 388    we seek-back-and-read-forward.
 389   [out] _gp:   Returns the granule position of the page that was found on
 390                 success.
 391   _offset:     The _offset before which to find a page.
 392                Any page returned will consist of data entirely before _offset.
 393   _serialno:   The target serial number.
 394   _serialnos:  The list of serial numbers in the link that contains the
 395                 preferred serial number.
 396   _nserialnos: The number of serial numbers in the current link.
 397   Return: The offset of the page on success, or a negative value on failure.
 398           OP_EREAD:    Failed to read more data (error or EOF).
 399           OP_EBADLINK: We couldn't find a page even after seeking back past the
 400                         beginning of the link.*/
 401 static opus_int64 op_get_last_page(OggOpusFile *_of,ogg_int64_t *_gp,
 402  opus_int64 _offset,ogg_uint32_t _serialno,
 403  const ogg_uint32_t *_serialnos,int _nserialnos){
 404   ogg_page    og;
 405   ogg_int64_t gp;
 406   opus_int64  begin;
 407   opus_int64  end;
 408   opus_int64  original_end;
 409   opus_int32  chunk_size;
 410   /*The target serial number must belong to the current link.*/
 411   OP_ASSERT(op_lookup_serialno(_serialno,_serialnos,_nserialnos));
 412   original_end=end=begin=_offset;
 413   _offset=-1;
 414   /*We shouldn't have to initialize gp, but gcc is too dumb to figure out that
 415      ret>=0 implies we entered the if(page_gp!=-1) block at least once.*/
 416   gp=-1;
 417   chunk_size=OP_CHUNK_SIZE;
 418   do{
 419     int left_link;
 420     int ret;
 421     OP_ASSERT(chunk_size>=OP_PAGE_SIZE_MAX);
 422     begin=OP_MAX(begin-chunk_size,0);
 423     ret=op_seek_helper(_of,begin);
 424     if(OP_UNLIKELY(ret<0))return ret;
 425     left_link=0;
 426     while(_of->offset<end){
 427       opus_int64   llret;
 428       ogg_uint32_t serialno;
 429       llret=op_get_next_page(_of,&og,end);
 430       if(OP_UNLIKELY(llret<OP_FALSE))return llret;
 431       else if(llret==OP_FALSE)break;
 432       serialno=ogg_page_serialno(&og);
 433       if(serialno==_serialno){
 434         ogg_int64_t page_gp;
 435         /*The page is from the right stream...*/
 436         page_gp=ogg_page_granulepos(&og);
 437         if(page_gp!=-1){
 438           /*And has a valid granule position.
 439             Let's remember it.*/
 440           _offset=llret;
 441           gp=page_gp;
 442         }
 443       }
 444       else if(OP_UNLIKELY(!op_lookup_serialno(serialno,
 445        _serialnos,_nserialnos))){
 446         /*We fell off the start of the link, which means we don't need to keep
 447            seeking any farther back.*/
 448         left_link=1;
 449       }
 450     }
 451     /*We started from at or before the beginning of the link and found nothing.
 452       This should be impossible unless the contents of the source changed out
 453        from under us after we read from it.*/
 454     if((OP_UNLIKELY(left_link)||OP_UNLIKELY(!begin))&&OP_UNLIKELY(_offset<0)){
 455       return OP_EBADLINK;
 456     }
 457     /*Bump up the chunk size.
 458       This is mildly helpful when seeks are very expensive (http).*/
 459     chunk_size=OP_MIN(2*chunk_size,OP_CHUNK_SIZE_MAX);
 460     /*Avoid quadratic complexity if we hit an invalid patch of the file.*/
 461     end=OP_MIN(begin+OP_PAGE_SIZE_MAX-1,original_end);
 462   }
 463   while(_offset<0);
 464   *_gp=gp;
 465   return _offset;
 466 }
 467
 468 /*Uses the local ogg_stream storage in _of.
 469   This is important for non-streaming input sources.*/
 470 static int op_fetch_headers_impl(OggOpusFile *_of,OpusHead *_head,
 471  OpusTags *_tags,ogg_uint32_t **_serialnos,int *_nserialnos,
 472  int *_cserialnos,ogg_page *_og){
 473   ogg_packet op;
 474   int        ret;
 475   if(_serialnos!=NULL)*_nserialnos=0;
 476   /*Extract the serialnos of all BOS pages plus the first set of Opus headers
 477      we see in the link.*/
 478   while(ogg_page_bos(_og)){
 479     if(_serialnos!=NULL){
 480       if(OP_UNLIKELY(op_lookup_page_serialno(_og,*_serialnos,*_nserialnos))){
 481         /*A dupe serialnumber in an initial header packet set==invalid stream.*/
 482         return OP_EBADHEADER;
 483       }
 484       ret=op_add_serialno(_og,_serialnos,_nserialnos,_cserialnos);
 485       if(OP_UNLIKELY(ret<0))return ret;
 486     }
 487     if(_of->ready_state<OP_STREAMSET){
 488       /*We don't have an Opus stream in this link yet, so begin prospective
 489          stream setup.
 490         We need a stream to get packets.*/
 491       ogg_stream_reset_serialno(&_of->os,ogg_page_serialno(_og));
 492       ogg_stream_pagein(&_of->os,_og);
 493       if(OP_LIKELY(ogg_stream_packetout(&_of->os,&op)>0)){
 494         ret=opus_head_parse(_head,op.packet,op.bytes);
 495         /*If it's just a stream type we don't recognize, ignore it.*/
 496         if(ret==OP_ENOTFORMAT)continue;
 497         /*Everything else is fatal.*/
 498         if(OP_UNLIKELY(ret<0))return ret;
 499         /*Found a valid Opus header.
 500           Continue setup.*/
 501         _of->ready_state=OP_STREAMSET;
 502       }
 503     }
 504     /*Get the next page.
 505       No need to clamp the boundary offset against _of->end, as all errors
 506        become OP_ENOTFORMAT.*/
 507     if(OP_UNLIKELY(op_get_next_page(_of,_og,
 508      OP_ADV_OFFSET(_of->offset,OP_CHUNK_SIZE))<0)){
 509       return OP_ENOTFORMAT;
 510     }
 511     /*If this page also belongs to our Opus stream, submit it and break.*/
 512     if(_of->ready_state==OP_STREAMSET
 513      &&_of->os.serialno==ogg_page_serialno(_og)){
 514       ogg_stream_pagein(&_of->os,_og);
 515       break;
 516     }
 517   }
 518   if(OP_UNLIKELY(_of->ready_state!=OP_STREAMSET))return OP_ENOTFORMAT;
 519   /*Loop getting packets.*/
 520   for(;;){
 521     switch(ogg_stream_packetout(&_of->os,&op)){
 522       case 0:{
 523         /*Loop getting pages.*/
 524         for(;;){
 525           /*No need to clamp the boundary offset against _of->end, as all
 526              errors become OP_EBADHEADER.*/
 527           if(OP_UNLIKELY(op_get_next_page(_of,_og,
 528            OP_ADV_OFFSET(_of->offset,OP_CHUNK_SIZE))<0)){
 529             return OP_EBADHEADER;
 530           }
 531           /*If this page belongs to the correct stream, go parse it.*/
 532           if(_of->os.serialno==ogg_page_serialno(_og)){
 533             ogg_stream_pagein(&_of->os,_og);
 534             break;
 535           }
 536           /*If the link ends before we see the Opus comment header, abort.*/
 537           if(OP_UNLIKELY(ogg_page_bos(_og)))return OP_EBADHEADER;
 538           /*Otherwise, keep looking.*/
 539         }
 540       }break;
 541       /*We shouldn't get a hole in the headers!*/
 542       case -1:return OP_EBADHEADER;
 543       default:{
 544         /*Got a packet.
 545           It should be the comment header.*/
 546         ret=opus_tags_parse(_tags,op.packet,op.bytes);
 547         if(OP_UNLIKELY(ret<0))return ret;
 548         /*Make sure the page terminated at the end of the comment header.
 549           If there is another packet on the page, or part of a packet, then
 550            reject the stream.
 551           Otherwise seekable sources won't be able to seek back to the start
 552            properly.*/
 553         ret=ogg_stream_packetout(&_of->os,&op);
 554         if(OP_UNLIKELY(ret!=0)
 555          ||OP_UNLIKELY(_og->header[_og->header_len-1]==255)){
 556           /*If we fail, the caller assumes our tags are uninitialized.*/
 557           opus_tags_clear(_tags);
 558           return OP_EBADHEADER;
 559         }
 560         return 0;
 561       }
 562     }
 563   }
 564 }
 565
 566 static int op_fetch_headers(OggOpusFile *_of,OpusHead *_head,
 567  OpusTags *_tags,ogg_uint32_t **_serialnos,int *_nserialnos,
 568  int *_cserialnos,ogg_page *_og){
 569   ogg_page og;
 570   int      ret;
 571   if(!_og){
 572     /*No need to clamp the boundary offset against _of->end, as all errors
 573        become OP_ENOTFORMAT.*/
 574     if(OP_UNLIKELY(op_get_next_page(_of,&og,
 575      OP_ADV_OFFSET(_of->offset,OP_CHUNK_SIZE))<0)){
 576       return OP_ENOTFORMAT;
 577     }
 578     _og=&og;
 579   }
 580   _of->ready_state=OP_OPENED;
 581   ret=op_fetch_headers_impl(_of,_head,_tags,_serialnos,_nserialnos,
 582    _cserialnos,_og);
 583   /*Revert back from OP_STREAMSET to OP_OPENED on failure, to prevent
 584      double-free of the tags in an unseekable stream.*/
 585   if(OP_UNLIKELY(ret<0))_of->ready_state=OP_OPENED;
 586   return ret;
 587 }
 588
 589 /*Granule position manipulation routines.
 590   A granule position is defined to be an unsigned 64-bit integer, with the
 591    special value -1 in two's complement indicating an unset or invalid granule
 592    position.
 593   We are not guaranteed to have an unsigned 64-bit type, so we construct the
 594    following routines that
 595    a) Properly order negative numbers as larger than positive numbers, and
 596    b) Check for underflow or overflow past the special -1 value.
 597   This lets us operate on the full, valid range of granule positions in a
 598    consistent and safe manner.
 599   This full range is organized into distinct regions:
 600    [ -1 (invalid) ][ 0 ... OP_INT64_MAX ][ OP_INT64_MIN ... -2 ][-1 (invalid) ]
 601
 602   No one should actually use granule positions so large that they're negative,
 603    even if they are technically valid, as very little software handles them
 604    correctly (including most of Xiph.Org's).
 605   This library also refuses to support durations so large they won't fit in a
 606    signed 64-bit integer (to avoid exposing this mess to the application, and
 607    to simplify a good deal of internal arithmetic), so the only way to use them
 608    successfully is if pcm_start is very large.
 609   This means there isn't anything you can do with negative granule positions
 610    that you couldn't have done with purely non-negative ones.
 611   The main purpose of these routines is to allow us to think very explicitly
 612    about the possible failure cases of all granule position manipulations.*/
 613
 614 /*Safely adds a small signed integer to a valid (not -1) granule position.
 615   The result can use the full 64-bit range of values (both positive and
 616    negative), but will fail on overflow (wrapping past -1; wrapping past
 617    OP_INT64_MAX is explicitly okay).
 618   [out] _dst_gp: The resulting granule position.
 619                  Only modified on success.
 620   _src_gp:       The granule position to add to.
 621                  This must not be -1.
 622   _delta:        The amount to add.
 623                  This is allowed to be up to 32 bits to support the maximum
 624                   duration of a single Ogg page (255 packets * 120 ms per
 625                   packet == 1,468,800 samples at 48 kHz).
 626   Return: 0 on success, or OP_EINVAL if the result would wrap around past -1.*/
 627 static int op_granpos_add(ogg_int64_t *_dst_gp,ogg_int64_t _src_gp,
 628  opus_int32 _delta){
 629   /*The code below handles this case correctly, but there's no reason we
 630      should ever be called with these values, so make sure we aren't.*/
 631   OP_ASSERT(_src_gp!=-1);
 632   if(_delta>0){
 633     /*Adding this amount to the granule position would overflow its 64-bit
 634        range.*/
 635     if(OP_UNLIKELY(_src_gp<0)&&OP_UNLIKELY(_src_gp>=-1-_delta))return OP_EINVAL;
 636     if(OP_UNLIKELY(_src_gp>OP_INT64_MAX-_delta)){
 637       /*Adding this amount to the granule position would overflow the positive
 638          half of its 64-bit range.
 639         Since signed overflow is undefined in C, do it in a way the compiler
 640          isn't allowed to screw up.*/
 641       _delta-=(opus_int32)(OP_INT64_MAX-_src_gp)+1;
 642       _src_gp=OP_INT64_MIN;
 643     }
 644   }
 645   else if(_delta<0){
 646     /*Subtracting this amount from the granule position would underflow its
 647        64-bit range.*/
 648     if(_src_gp>=0&&OP_UNLIKELY(_src_gp<-_delta))return OP_EINVAL;
 649     if(OP_UNLIKELY(_src_gp<OP_INT64_MIN-_delta)){
 650       /*Subtracting this amount from the granule position would underflow the
 651          negative half of its 64-bit range.
 652         Since signed underflow is undefined in C, do it in a way the compiler
 653          isn't allowed to screw up.*/
 654       _delta+=(opus_int32)(_src_gp-OP_INT64_MIN)+1;
 655       _src_gp=OP_INT64_MAX;
 656     }
 657   }
 658   *_dst_gp=_src_gp+_delta;
 659   return 0;
 660 }
 661
 662 /*Safely computes the difference between two granule positions.
 663   The difference must fit in a signed 64-bit integer, or the function fails.
 664   It correctly handles the case where the granule position has wrapped around
 665    from positive values to negative ones.
 666   [out] _delta: The difference between the granule positions.
 667                 Only modified on success.
 668   _gp_a:        The granule position to subtract from.
 669                 This must not be -1.
 670   _gp_b:        The granule position to subtract.
 671                 This must not be -1.
 672   Return: 0 on success, or OP_EINVAL if the result would not fit in a signed
 673            64-bit integer.*/
 674 static int op_granpos_diff(ogg_int64_t *_delta,
 675  ogg_int64_t _gp_a,ogg_int64_t _gp_b){
 676   int gp_a_negative;
 677   int gp_b_negative;
 678   /*The code below handles these cases correctly, but there's no reason we
 679      should ever be called with these values, so make sure we aren't.*/
 680   OP_ASSERT(_gp_a!=-1);
 681   OP_ASSERT(_gp_b!=-1);
 682   gp_a_negative=OP_UNLIKELY(_gp_a<0);
 683   gp_b_negative=OP_UNLIKELY(_gp_b<0);
 684   if(OP_UNLIKELY(gp_a_negative^gp_b_negative)){
 685     ogg_int64_t da;
 686     ogg_int64_t db;
 687     if(gp_a_negative){
 688       /*_gp_a has wrapped to a negative value but _gp_b hasn't: the difference
 689          should be positive.*/
 690       /*Step 1: Handle wrapping.*/
 691       /*_gp_a < 0 => da < 0.*/
 692       da=(OP_INT64_MIN-_gp_a)-1;
 693       /*_gp_b >= 0  => db >= 0.*/
 694       db=OP_INT64_MAX-_gp_b;
 695       /*Step 2: Check for overflow.*/
 696       if(OP_UNLIKELY(OP_INT64_MAX+da<db))return OP_EINVAL;
 697       *_delta=db-da;
 698     }
 699     else{
 700       /*_gp_b has wrapped to a negative value but _gp_a hasn't: the difference
 701          should be negative.*/
 702       /*Step 1: Handle wrapping.*/
 703       /*_gp_a >= 0 => da <= 0*/
 704       da=_gp_a+OP_INT64_MIN;
 705       /*_gp_b < 0 => db <= 0*/
 706       db=OP_INT64_MIN-_gp_b;
 707       /*Step 2: Check for overflow.*/
 708       if(OP_UNLIKELY(da<OP_INT64_MIN-db))return OP_EINVAL;
 709       *_delta=da+db;
 710     }
 711   }
 712   else *_delta=_gp_a-_gp_b;
 713   return 0;
 714 }
 715
 716 static int op_granpos_cmp(ogg_int64_t _gp_a,ogg_int64_t _gp_b){
 717   /*The invalid granule position -1 should behave like NaN: neither greater
 718      than nor less than any other granule position, nor equal to any other
 719      granule position, including itself.
 720     However, that means there isn't anything we could sensibly return from this
 721      function for it.*/
 722   OP_ASSERT(_gp_a!=-1);
 723   OP_ASSERT(_gp_b!=-1);
 724   /*Handle the wrapping cases.*/
 725   if(OP_UNLIKELY(_gp_a<0)){
 726     if(_gp_b>=0)return 1;
 727     /*Else fall through.*/
 728   }
 729   else if(OP_UNLIKELY(_gp_b<0))return -1;
 730   /*No wrapping case.*/
 731   return (_gp_a>_gp_b)-(_gp_b>_gp_a);
 732 }
 733
 734 /*Returns the duration of the packet (in samples at 48 kHz), or a negative
 735    value on error.*/
 736 static int op_get_packet_duration(const unsigned char *_data,int _len){
 737   int nframes;
 738   int frame_size;
 739   int nsamples;
 740   nframes=opus_packet_get_nb_frames(_data,_len);
 741   if(OP_UNLIKELY(nframes<0))return OP_EBADPACKET;
 742   frame_size=opus_packet_get_samples_per_frame(_data,48000);
 743   nsamples=nframes*frame_size;
 744   if(OP_UNLIKELY(nsamples>120*48))return OP_EBADPACKET;
 745   return nsamples;
 746 }
 747
 748 /*This function more properly belongs in info.c, but we define it here to allow
 749    the static granule position manipulation functions to remain static.*/
 750 ogg_int64_t opus_granule_sample(const OpusHead *_head,ogg_int64_t _gp){
 751   opus_int32 pre_skip;
 752   pre_skip=_head->pre_skip;
 753   if(_gp!=-1&&op_granpos_add(&_gp,_gp,-pre_skip))_gp=-1;
 754   return _gp;
 755 }
 756
 757 /*Grab all the packets currently in the stream state, and compute their
 758    durations.
 759   _of->op_count is set to the number of packets collected.
 760   [out] _durations: Returns the durations of the individual packets.
 761   Return: The total duration of all packets, or OP_HOLE if there was a hole.*/
 762 static opus_int32 op_collect_audio_packets(OggOpusFile *_of,
 763  int _durations[255]){
 764   opus_int32 total_duration;
 765   int        op_count;
 766   /*Count the durations of all packets in the page.*/
 767   op_count=0;
 768   total_duration=0;
 769   for(;;){
 770     int ret;
 771     /*This takes advantage of undocumented libogg behavior that returned
 772        ogg_packet buffers are valid at least until the next page is
 773        submitted.
 774       Relying on this is not too terrible, as _none_ of the Ogg memory
 775        ownership/lifetime rules are well-documented.
 776       But I can read its code and know this will work.*/
 777     ret=ogg_stream_packetout(&_of->os,_of->op+op_count);
 778     if(!ret)break;
 779     if(OP_UNLIKELY(ret<0)){
 780       /*We shouldn't get holes in the middle of pages.*/
 781       OP_ASSERT(op_count==0);
 782       /*Set the return value and break out of the loop.
 783         We want to make sure op_count gets set to 0, because we've ingested a
 784          page, so any previously loaded packets are now invalid.*/
 785       total_duration=OP_HOLE;
 786       break;
 787     }
 788     /*Unless libogg is broken, we can't get more than 255 packets from a
 789        single page.*/
 790     OP_ASSERT(op_count<255);
 791     _durations[op_count]=op_get_packet_duration(_of->op[op_count].packet,
 792      _of->op[op_count].bytes);
 793     if(OP_LIKELY(_durations[op_count]>0)){
 794       /*With at most 255 packets on a page, this can't overflow.*/
 795       total_duration+=_durations[op_count++];
 796     }
 797     /*Ignore packets with an invalid TOC sequence.*/
 798     else if(op_count>0){
 799       /*But save the granule position, if there was one.*/
 800       _of->op[op_count-1].granulepos=_of->op[op_count].granulepos;
 801     }
 802   }
 803   _of->op_pos=0;
 804   _of->op_count=op_count;
 805   return total_duration;
 806 }
 807
 808 /*Starting from current cursor position, get the initial PCM offset of the next
 809    page.
 810   This also validates the granule position on the first page with a completed
 811    audio data packet, as required by the spec.
 812   If this link is completely empty (no pages with completed packets), then this
 813    function sets pcm_start=pcm_end=0 and returns the BOS page of the next link
 814    (if any).
 815   In the seekable case, we initialize pcm_end=-1 before calling this function,
 816    so that later we can detect that the link was empty before calling
 817    op_find_final_pcm_offset().
 818   [inout] _link: The link for which to find pcm_start.
 819   [out] _og:     Returns the BOS page of the next link if this link was empty.
 820                  In the unseekable case, we can then feed this to
 821                   op_fetch_headers() to start the next link.
 822                  The caller may pass NULL (e.g., for seekable streams), in
 823                   which case this page will be discarded.
 824   Return: 0 on success, 1 if there is a buffered BOS page available, or a
 825            negative value on unrecoverable error.*/
 826 static int op_find_initial_pcm_offset(OggOpusFile *_of,
 827  OggOpusLink *_link,ogg_page *_og){
 828   ogg_page     og;
 829   ogg_int64_t  pcm_start;
 830   ogg_int64_t  prev_packet_gp;
 831   ogg_int64_t  cur_page_gp;
 832   ogg_uint32_t serialno;
 833   opus_int32   total_duration;
 834   int          durations[255];
 835   int          cur_page_eos;
 836   int          op_count;
 837   int          pi;
 838   if(_og==NULL)_og=&og;
 839   serialno=_of->os.serialno;
 840   op_count=0;
 841   /*We shouldn't have to initialize total_duration, but gcc is too dumb to
 842      figure out that op_count>0 implies we've been through the whole loop at
 843      least once.*/
 844   total_duration=0;
 845   do{
 846     opus_int64 llret;
 847     llret=op_get_next_page(_of,_og,_of->end);
 848     /*We should get a page unless the file is truncated or mangled.
 849       Otherwise there are no audio data packets in the whole logical stream.*/
 850     if(OP_UNLIKELY(llret<0)){
 851       /*Fail if there was a read error.*/
 852       if(llret<OP_FALSE)return (int)llret;
 853       /*Fail if the pre-skip is non-zero, since it's asking us to skip more
 854          samples than exist.*/
 855       if(_link->head.pre_skip>0)return OP_EBADTIMESTAMP;
 856       /*Set pcm_end and end_offset so we can skip the call to
 857          op_find_final_pcm_offset().*/
 858       _link->pcm_start=_link->pcm_end=0;
 859       _link->end_offset=_link->data_offset;
 860       return 0;
 861     }
 862     /*Similarly, if we hit the next link in the chain, we've gone too far.*/
 863     if(OP_UNLIKELY(ogg_page_bos(_og))){
 864       if(_link->head.pre_skip>0)return OP_EBADTIMESTAMP;
 865       /*Set pcm_end and end_offset so we can skip the call to
 866          op_find_final_pcm_offset().*/
 867       _link->pcm_end=_link->pcm_start=0;
 868       _link->end_offset=_link->data_offset;
 869       /*Tell the caller we've got a buffered page for them.*/
 870       return 1;
 871     }
 872     /*Ignore pages from other streams (not strictly necessary, because of the
 873        checks in ogg_stream_pagein(), but saves some work).*/
 874     if(serialno!=(ogg_uint32_t)ogg_page_serialno(_og))continue;
 875     ogg_stream_pagein(&_of->os,_og);
 876     /*Bitrate tracking: add the header's bytes here.
 877       The body bytes are counted when we consume the packets.*/
 878     _of->bytes_tracked+=_og->header_len;
 879     /*Count the durations of all packets in the page.*/
 880     do total_duration=op_collect_audio_packets(_of,durations);
 881     /*Ignore holes.*/
 882     while(OP_UNLIKELY(total_duration<0));
 883     op_count=_of->op_count;
 884   }
 885   while(op_count<=0);
 886   /*We found the first page with a completed audio data packet: actually look
 887      at the granule position.
 888     RFC 3533 says, "A special value of -1 (in two's complement) indicates that
 889      no packets finish on this page," which does not say that a granule
 890      position that is NOT -1 indicates that some packets DO finish on that page
 891      (even though this was the intention, libogg itself violated this intention
 892      for years before we fixed it).
 893     The Ogg Opus specification only imposes its start-time requirements
 894      on the granule position of the first page with completed packets,
 895      so we ignore any set granule positions until then.*/
 896   cur_page_gp=_of->op[op_count-1].granulepos;
 897   /*But getting a packet without a valid granule position on the page is not
 898      okay.*/
 899   if(cur_page_gp==-1)return OP_EBADTIMESTAMP;
 900   cur_page_eos=_of->op[op_count-1].e_o_s;
 901   if(OP_LIKELY(!cur_page_eos)){
 902     /*The EOS flag wasn't set.
 903       Work backwards from the provided granule position to get the starting PCM
 904        offset.*/
 905     if(OP_UNLIKELY(op_granpos_add(&pcm_start,cur_page_gp,-total_duration)<0)){
 906       /*The starting granule position MUST not be smaller than the amount of
 907          audio on the first page with completed packets.*/
 908       return OP_EBADTIMESTAMP;
 909     }
 910   }
 911   else{
 912     /*The first page with completed packets was also the last.*/
 913     if(OP_LIKELY(op_granpos_add(&pcm_start,cur_page_gp,-total_duration)<0)){
 914       /*If there's less audio on the page than indicated by the granule
 915          position, then we're doing end-trimming, and the starting PCM offset
 916          is zero by spec mandate.*/
 917       pcm_start=0;
 918       /*However, the end-trimming MUST not ask us to trim more samples than
 919          exist after applying the pre-skip.*/
 920       if(OP_UNLIKELY(op_granpos_cmp(cur_page_gp,_link->head.pre_skip)<0)){
 921         return OP_EBADTIMESTAMP;
 922       }
 923     }
 924   }
 925   /*Timestamp the individual packets.*/
 926   prev_packet_gp=pcm_start;
 927   for(pi=0;pi<op_count;pi++){
 928     if(cur_page_eos){
 929       ogg_int64_t diff;
 930       OP_ALWAYS_TRUE(!op_granpos_diff(&diff,cur_page_gp,prev_packet_gp));
 931       diff=durations[pi]-diff;
 932       /*If we have samples to trim...*/
 933       if(diff>0){
 934         /*If we trimmed the entire packet, stop (the spec says encoders
 935            shouldn't do this, but we support it anyway).*/
 936         if(OP_UNLIKELY(diff>durations[pi]))break;
 937         _of->op[pi].granulepos=prev_packet_gp=cur_page_gp;
 938         /*Move the EOS flag to this packet, if necessary, so we'll trim the
 939            samples.*/
 940         _of->op[pi].e_o_s=1;
 941         continue;
 942       }
 943     }
 944     /*Update the granule position as normal.*/
 945     OP_ALWAYS_TRUE(!op_granpos_add(&_of->op[pi].granulepos,
 946      prev_packet_gp,durations[pi]));
 947     prev_packet_gp=_of->op[pi].granulepos;
 948   }
 949   /*Update the packet count after end-trimming.*/
 950   _of->op_count=pi;
 951   _of->cur_discard_count=_link->head.pre_skip;
 952   _of->prev_packet_gp=_link->pcm_start=pcm_start;
 953   return 0;
 954 }
 955
 956 /*Starting from current cursor position, get the final PCM offset of the
 957    previous page.
 958   This also validates the duration of the link, which, while not strictly
 959    required by the spec, we need to ensure duration calculations don't
 960    overflow.
 961   This is only done for seekable sources.
 962   We must validate that op_find_initial_pcm_offset() succeeded for this link
 963    before calling this function, otherwise it will scan the entire stream
 964    backwards until it reaches the start, and then fail.*/
 965 static int op_find_final_pcm_offset(OggOpusFile *_of,
 966  const ogg_uint32_t *_serialnos,int _nserialnos,OggOpusLink *_link,
 967  opus_int64 _offset,ogg_uint32_t _end_serialno,ogg_int64_t _end_gp,
 968  ogg_int64_t *_total_duration){
 969   ogg_int64_t  total_duration;
 970   ogg_int64_t  duration;
 971   ogg_uint32_t cur_serialno;
 972   /*For the time being, fetch end PCM offset the simple way.*/
 973   cur_serialno=_link->serialno;
 974   if(_end_serialno!=cur_serialno||_end_gp==-1){
 975     _offset=op_get_last_page(_of,&_end_gp,_offset,
 976      cur_serialno,_serialnos,_nserialnos);
 977     if(OP_UNLIKELY(_offset<0))return (int)_offset;
 978   }
 979   /*At worst we should have found the first page with completed packets.*/
 980   if(OP_UNLIKELY(_offset<_link->data_offset))return OP_EBADLINK;
 981   /*This implementation requires that the difference between the first and last
 982      granule positions in each link be representable in a signed, 64-bit
 983      number, and that each link also have at least as many samples as the
 984      pre-skip requires.*/
 985   if(OP_UNLIKELY(op_granpos_diff(&duration,_end_gp,_link->pcm_start)<0)
 986    ||OP_UNLIKELY(duration<_link->head.pre_skip)){
 987     return OP_EBADTIMESTAMP;
 988   }
 989   /*We also require that the total duration be representable in a signed,
 990      64-bit number.*/
 991   duration-=_link->head.pre_skip;
 992   total_duration=*_total_duration;
 993   if(OP_UNLIKELY(OP_INT64_MAX-duration<total_duration))return OP_EBADTIMESTAMP;
 994   *_total_duration=total_duration+duration;
 995   _link->pcm_end=_end_gp;
 996   _link->end_offset=_offset;
 997   return 0;
 998 }
 999
1000 /*Rescale the number _x from the range [0,_from] to [0,_to].
1001   _from and _to must be positive.*/
1002 opus_int64 op_rescale64(opus_int64 _x,opus_int64 _from,opus_int64 _to){
1003   opus_int64 frac;
1004   opus_int64 ret;
1005   int        i;
1006   if(_x>=_from)return _to;
1007   if(_x<=0)return 0;
1008   frac=0;
1009   for(i=0;i<63;i++){
1010     frac<<=1;
1011     OP_ASSERT(_x<=_from);
1012     if(_x>=_from>>1){
1013       _x-=_from-_x;
1014       frac|=1;
1015     }
1016     else _x<<=1;
1017   }
1018   ret=0;
1019   for(i=0;i<63;i++){
1020     if(frac&1)ret=(ret&_to&1)+(ret>>1)+(_to>>1);
1021     else ret>>=1;
1022     frac>>=1;
1023   }
1024   return ret;
1025 }
1026
1027 /*The minimum granule position spacing allowed for making predictions.
1028   This corresponds to about 1 second of audio at 48 kHz for both Opus and
1029    Vorbis, or one keyframe interval in Theora with the default keyframe spacing
1030    of 256.*/
1031 #define OP_GP_SPACING_MIN (48000)
1032
1033 /*Try to estimate the location of the next link using the current seek
1034    records, assuming the initial granule position of any streams we've found is
1035    0.*/
1036 static opus_int64 op_predict_link_start(const OpusSeekRecord *_sr,int _nsr,
1037  opus_int64 _searched,opus_int64 _end_searched,opus_int32 _bias){
1038   opus_int64 bisect;
1039   int        sri;
1040   int        srj;
1041   /*Require that we be at least OP_CHUNK_SIZE from the end.
1042     We don't require that we be at least OP_CHUNK_SIZE from the beginning,
1043      because if we are we'll just scan forward without seeking.*/
1044   _end_searched-=OP_CHUNK_SIZE;
1045   if(_searched>=_end_searched)return -1;
1046   bisect=_end_searched;
1047   for(sri=0;sri<_nsr;sri++){
1048     ogg_int64_t  gp1;
1049     ogg_int64_t  gp2_min;
1050     ogg_uint32_t serialno1;
1051     opus_int64   offset1;
1052     /*If the granule position is negative, either it's invalid or we'd cause
1053        overflow.*/
1054     gp1=_sr[sri].gp;
1055     if(gp1<0)continue;
1056     /*We require some minimum distance between granule positions to make an
1057        estimate.
1058       We don't actually know what granule position scheme is being used,
1059        because we have no idea what kind of stream these came from.
1060       Therefore we require a minimum spacing between them, with the
1061        expectation that while bitrates and granule position increments might
1062        vary locally in quite complex ways, they are globally smooth.*/
1063     if(OP_UNLIKELY(op_granpos_add(&gp2_min,gp1,OP_GP_SPACING_MIN)<0)){
1064       /*No granule position would satisfy us.*/
1065       continue;
1066     }
1067     offset1=_sr[sri].offset;
1068     serialno1=_sr[sri].serialno;
1069     for(srj=sri;srj-->0;){
1070       ogg_int64_t gp2;
1071       opus_int64  offset2;
1072       opus_int64  num;
1073       ogg_int64_t den;
1074       ogg_int64_t ipart;
1075       gp2=_sr[srj].gp;
1076       if(gp2<gp2_min)continue;
1077       /*Oh, and also make sure these came from the same stream.*/
1078       if(_sr[srj].serialno!=serialno1)continue;
1079       offset2=_sr[srj].offset;
1080       /*For once, we can subtract with impunity.*/
1081       den=gp2-gp1;
1082       ipart=gp2/den;
1083       num=offset2-offset1;
1084       OP_ASSERT(num>0);
1085       if(ipart>0&&(offset2-_searched)/ipart<num)continue;
1086       offset2-=ipart*num;
1087       gp2-=ipart*den;
1088       offset2-=op_rescale64(gp2,den,num)-_bias;
1089       if(offset2<_searched)continue;
1090       bisect=OP_MIN(bisect,offset2);
1091       break;
1092     }
1093   }
1094   return bisect>=_end_searched?-1:bisect;
1095 }
1096
1097 /*Finds each bitstream link, one at a time, using a bisection search.
1098   This has to begin by knowing the offset of the first link's initial page.*/
1099 static int op_bisect_forward_serialno(OggOpusFile *_of,
1100  opus_int64 _searched,OpusSeekRecord *_sr,int _csr,
1101  ogg_uint32_t **_serialnos,int *_nserialnos,int *_cserialnos){
1102   ogg_page      og;
1103   OggOpusLink  *links;
1104   int           nlinks;
1105   int           clinks;
1106   ogg_uint32_t *serialnos;
1107   int           nserialnos;
1108   ogg_int64_t   total_duration;
1109   int           nsr;
1110   int           ret;
1111   links=_of->links;
1112   nlinks=clinks=_of->nlinks;
1113   total_duration=0;
1114   /*We start with one seek record, for the last page in the file.
1115     We build up a list of records for places we seek to during link
1116      enumeration.
1117     This list is kept sorted in reverse order.
1118     We only care about seek locations that were _not_ in the current link,
1119      therefore we can add them one at a time to the end of the list as we
1120      improve the lower bound on the location where the next link starts.*/
1121   nsr=1;
1122   for(;;){
1123     opus_int64  end_searched;
1124     opus_int64  bisect;
1125     opus_int64  next;
1126     opus_int64  last;
1127     ogg_int64_t end_offset;
1128     ogg_int64_t end_gp;
1129     int         sri;
1130     serialnos=*_serialnos;
1131     nserialnos=*_nserialnos;
1132     if(OP_UNLIKELY(nlinks>=clinks)){
1133       if(OP_UNLIKELY(clinks>INT_MAX-1>>1))return OP_EFAULT;
1134       clinks=2*clinks+1;
1135       OP_ASSERT(nlinks<clinks);
1136       links=(OggOpusLink *)_ogg_realloc(links,sizeof(*links)*clinks);
1137       if(OP_UNLIKELY(links==NULL))return OP_EFAULT;
1138       _of->links=links;
1139     }
1140     /*Invariants:
1141       We have the headers and serial numbers for the link beginning at 'begin'.
1142       We have the offset and granule position of the last page in the file
1143        (potentially not a page we care about).*/
1144     /*Scan the seek records we already have to save us some bisection.*/
1145     for(sri=0;sri<nsr;sri++){
1146       if(op_lookup_serialno(_sr[sri].serialno,*_serialnos,*_nserialnos))break;
1147     }
1148     /*Is the last page in our current list of serial numbers?*/
1149     if(sri<=0)break;
1150     /*Last page wasn't found.
1151       We have at least one more link.*/
1152     last=-1;
1153     end_searched=_sr[sri-1].search_start;
1154     next=_sr[sri-1].offset;
1155     end_gp=-1;
1156     if(sri<nsr){
1157       _searched=_sr[sri].offset+_sr[sri].size;
1158       if(_sr[sri].serialno==links[nlinks-1].serialno){
1159         end_gp=_sr[sri].gp;
1160         end_offset=_sr[sri].offset;
1161       }
1162     }
1163     nsr=sri;
1164     bisect=-1;
1165     /*If we've already found the end of at least one link, try to pick the
1166        first bisection point at twice the average link size.
1167       This is a good choice for files with lots of links that are all about the
1168        same size.*/
1169     if(nlinks>1){
1170       opus_int64 last_offset;
1171       opus_int64 avg_link_size;
1172       opus_int64 upper_limit;
1173       last_offset=links[nlinks-1].offset;
1174       avg_link_size=last_offset/(nlinks-1);
1175       upper_limit=end_searched-OP_CHUNK_SIZE-avg_link_size;
1176       if(OP_LIKELY(last_offset>_searched-avg_link_size)
1177        &&OP_LIKELY(last_offset<upper_limit)){
1178         bisect=last_offset+avg_link_size;
1179         if(OP_LIKELY(bisect<upper_limit))bisect+=avg_link_size;
1180       }
1181     }
1182     /*We guard against garbage separating the last and first pages of two
1183        links below.*/
1184     while(_searched<end_searched){
1185       opus_int32 next_bias;
1186       /*If we don't have a better estimate, use simple bisection.*/
1187       if(bisect==-1)bisect=_searched+(end_searched-_searched>>1);
1188       /*If we're within OP_CHUNK_SIZE of the start, scan forward.*/
1189       if(bisect-_searched<OP_CHUNK_SIZE)bisect=_searched;
1190       /*Otherwise we're skipping data.
1191         Forget the end page, if we saw one, as we might miss a later one.*/
1192       else end_gp=-1;
1193       ret=op_seek_helper(_of,bisect);
1194       if(OP_UNLIKELY(ret<0))return ret;
1195       last=op_get_next_page(_of,&og,_sr[nsr-1].offset);
1196       if(OP_UNLIKELY(last<OP_FALSE))return (int)last;
1197       next_bias=0;
1198       if(last==OP_FALSE)end_searched=bisect;
1199       else{
1200         ogg_uint32_t serialno;
1201         ogg_int64_t  gp;
1202         serialno=ogg_page_serialno(&og);
1203         gp=ogg_page_granulepos(&og);
1204         if(!op_lookup_serialno(serialno,serialnos,nserialnos)){
1205           end_searched=bisect;
1206           next=last;
1207           /*In reality we should always have enough room, but be paranoid.*/
1208           if(OP_LIKELY(nsr<_csr)){
1209             _sr[nsr].search_start=bisect;
1210             _sr[nsr].offset=last;
1211             OP_ASSERT(_of->offset-last>=0);
1212             OP_ASSERT(_of->offset-last<=OP_PAGE_SIZE_MAX);
1213             _sr[nsr].size=(opus_int32)(_of->offset-last);
1214             _sr[nsr].serialno=serialno;
1215             _sr[nsr].gp=gp;
1216             nsr++;
1217           }
1218         }
1219         else{
1220           _searched=_of->offset;
1221           next_bias=OP_CHUNK_SIZE;
1222           if(serialno==links[nlinks-1].serialno){
1223             /*This page was from the stream we want, remember it.
1224               If it's the last such page in the link, we won't have to go back
1225                looking for it later.*/
1226             end_gp=gp;
1227             end_offset=last;
1228           }
1229         }
1230       }
1231       bisect=op_predict_link_start(_sr,nsr,_searched,end_searched,next_bias);
1232     }
1233     /*Bisection point found.
1234       Get the final granule position of the previous link, assuming
1235        op_find_initial_pcm_offset() didn't already determine the link was
1236        empty.*/
1237     if(OP_LIKELY(links[nlinks-1].pcm_end==-1)){
1238       if(end_gp==-1){
1239         /*If we don't know where the end page is, we'll have to seek back and
1240            look for it, starting from the end of the link.*/
1241         end_offset=next;
1242         /*Also forget the last page we read.
1243           It won't be available after the seek.*/
1244         last=-1;
1245       }
1246       ret=op_find_final_pcm_offset(_of,serialnos,nserialnos,
1247        links+nlinks-1,end_offset,links[nlinks-1].serialno,end_gp,
1248        &total_duration);
1249       if(OP_UNLIKELY(ret<0))return ret;
1250     }
1251     if(last!=next){
1252       /*The last page we read was not the first page the next link.
1253         Move the cursor position to the offset of that first page.
1254         This only performs an actual seek if the first page of the next link
1255          does not start at the end of the last page from the current Opus
1256          stream with a valid granule position.*/
1257       ret=op_seek_helper(_of,next);
1258       if(OP_UNLIKELY(ret<0))return ret;
1259     }
1260     ret=op_fetch_headers(_of,&links[nlinks].head,&links[nlinks].tags,
1261      _serialnos,_nserialnos,_cserialnos,last!=next?NULL:&og);
1262     if(OP_UNLIKELY(ret<0))return ret;
1263     links[nlinks].offset=next;
1264     links[nlinks].data_offset=_of->offset;
1265     links[nlinks].serialno=_of->os.serialno;
1266     links[nlinks].pcm_end=-1;
1267     /*This might consume a page from the next link, however the next bisection
1268        always starts with a seek.*/
1269     ret=op_find_initial_pcm_offset(_of,links+nlinks,NULL);
1270     if(OP_UNLIKELY(ret<0))return ret;
1271     _searched=_of->offset;
1272     /*Mark the current link count so it can be cleaned up on error.*/
1273     _of->nlinks=++nlinks;
1274   }
1275   /*Last page is in the starting serialno list, so we've reached the last link.
1276     Now find the last granule position for it (if we didn't the first time we
1277      looked at the end of the stream, and if op_find_initial_pcm_offset()
1278      didn't already determine the link was empty).*/
1279   if(OP_LIKELY(links[nlinks-1].pcm_end==-1)){
1280     ret=op_find_final_pcm_offset(_of,serialnos,nserialnos,
1281      links+nlinks-1,_sr[0].offset,_sr[0].serialno,_sr[0].gp,&total_duration);
1282     if(OP_UNLIKELY(ret<0))return ret;
1283   }
1284   /*Trim back the links array if necessary.*/
1285   links=(OggOpusLink *)_ogg_realloc(links,sizeof(*links)*nlinks);
1286   if(OP_LIKELY(links!=NULL))_of->links=links;
1287   /*We also don't need these anymore.*/
1288   _ogg_free(*_serialnos);
1289   *_serialnos=NULL;
1290   *_cserialnos=*_nserialnos=0;
1291   return 0;
1292 }
1293
1294 static int op_make_decode_ready(OggOpusFile *_of){
1295   OpusHead *head;
1296   int       li;
1297   int       stream_count;
1298   int       coupled_count;
1299   int       channel_count;
1300   if(_of->ready_state>OP_STREAMSET)return 0;
1301   if(OP_UNLIKELY(_of->ready_state<OP_STREAMSET))return OP_EFAULT;
1302   li=_of->seekable?_of->cur_link:0;
1303   head=&_of->links[li].head;
1304   stream_count=head->stream_count;
1305   coupled_count=head->coupled_count;
1306   channel_count=head->channel_count;
1307   /*Check to see if the current decoder is compatible with the current link.*/
1308   if(_of->od!=NULL&&_of->od_stream_count==stream_count
1309    &&_of->od_coupled_count==coupled_count&&_of->od_channel_count==channel_count
1310    &&memcmp(_of->od_mapping,head->mapping,
1311    sizeof(*head->mapping)*channel_count)==0){
1312     opus_multistream_decoder_ctl(_of->od,OPUS_RESET_STATE);
1313   }
1314   else{
1315     int err;
1316     opus_multistream_decoder_destroy(_of->od);
1317     _of->od=opus_multistream_decoder_create(48000,channel_count,
1318      stream_count,coupled_count,head->mapping,&err);
1319     if(_of->od==NULL)return OP_EFAULT;
1320     _of->od_stream_count=stream_count;
1321     _of->od_coupled_count=coupled_count;
1322     _of->od_channel_count=channel_count;
1323     memcpy(_of->od_mapping,head->mapping,sizeof(*head->mapping)*channel_count);
1324   }
1325 #if defined(OPUS_SET_GAIN)
1326   opus_multistream_decoder_ctl(_of->od,OPUS_SET_GAIN(head->output_gain));
1327 #else
1328 /*A fallback that works with both float and fixed-point is a bunch of work,
1329    so just force people to use a sufficiently new version.
1330   This is deployed well enough at this point that this shouldn't be a burden.*/
1331 # error "libopus 1.0.1 or later required"
1332 #endif
1333   _of->ready_state=OP_INITSET;
1334   _of->bytes_tracked=0;
1335   _of->samples_tracked=0;
1336 #if !defined(OP_FIXED_POINT)
1337   _of->state_channel_count=0;
1338   /*Use the serial number for the PRNG seed to get repeatable output for
1339      straight play-throughs.*/
1340   _of->dither_seed=_of->links[li].serialno;
1341 #endif
1342   return 0;
1343 }
1344
1345 static int op_open_seekable2_impl(OggOpusFile *_of){
1346   /*64 seek records should be enough for anybody.
1347     Actually, with a bisection search in a 63-bit range down to OP_CHUNK_SIZE
1348      granularity, much more than enough.*/
1349   OpusSeekRecord sr[64];
1350   opus_int64     data_offset;
1351   int            ret;
1352   /*We can seek, so set out learning all about this file.*/
1353   (*_of->callbacks.seek)(_of->source,0,SEEK_END);
1354   _of->offset=_of->end=(*_of->callbacks.tell)(_of->source);
1355   if(OP_UNLIKELY(_of->end<0))return OP_EREAD;
1356   data_offset=_of->links[0].data_offset;
1357   if(OP_UNLIKELY(_of->end<data_offset))return OP_EBADLINK;
1358   /*Get the offset of the last page of the physical bitstream, or, if we're
1359      lucky, the last Opus page of the first link, as most Ogg Opus files will
1360      contain a single logical bitstream.*/
1361   ret=op_get_prev_page_serial(_of,sr,_of->end,
1362    _of->links[0].serialno,_of->serialnos,_of->nserialnos);
1363   if(OP_UNLIKELY(ret<0))return ret;
1364   /*If there's any trailing junk, forget about it.*/
1365   _of->end=sr[0].offset+sr[0].size;
1366   if(OP_UNLIKELY(_of->end<data_offset))return OP_EBADLINK;
1367   /*Now enumerate the bitstream structure.*/
1368   return op_bisect_forward_serialno(_of,data_offset,sr,sizeof(sr)/sizeof(*sr),
1369    &_of->serialnos,&_of->nserialnos,&_of->cserialnos);
1370 }
1371
1372 static int op_open_seekable2(OggOpusFile *_of){
1373   ogg_sync_state    oy_start;
1374   ogg_stream_state  os_start;
1375   ogg_packet       *op_start;
1376   opus_int64        start_offset;
1377   int               start_op_count;
1378   int               ret;
1379   /*We're partially open and have a first link header state in storage in _of.
1380     Save off that stream state so we can come back to it.
1381     It would be simpler to just dump all this state and seek back to
1382      links[0].data_offset when we're done.
1383     But we do the extra work to allow us to seek back to _exactly_ the same
1384      stream position we're at now.
1385     This allows, e.g., the HTTP backend to continue reading from the original
1386      connection (if it's still available), instead of opening a new one.
1387     This means we can open and start playing a normal Opus file with a single
1388      link and reasonable packet sizes using only two HTTP requests.*/
1389   start_op_count=_of->op_count;
1390   /*This is a bit too large to put on the stack unconditionally.*/
1391   op_start=(ogg_packet *)_ogg_malloc(sizeof(*op_start)*start_op_count);
1392   if(op_start==NULL)return OP_EFAULT;
1393   *&oy_start=_of->oy;
1394   *&os_start=_of->os;
1395   start_offset=_of->offset;
1396   memcpy(op_start,_of->op,sizeof(*op_start)*start_op_count);
1397   OP_ASSERT((*_of->callbacks.tell)(_of->source)==op_position(_of));
1398   ogg_sync_init(&_of->oy);
1399   ogg_stream_init(&_of->os,-1);
1400   ret=op_open_seekable2_impl(_of);
1401   /*Restore the old stream state.*/
1402   ogg_stream_clear(&_of->os);
1403   ogg_sync_clear(&_of->oy);
1404   *&_of->oy=*&oy_start;
1405   *&_of->os=*&os_start;
1406   _of->offset=start_offset;
1407   _of->op_count=start_op_count;
1408   memcpy(_of->op,op_start,sizeof(*_of->op)*start_op_count);
1409   _ogg_free(op_start);
1410   _of->prev_packet_gp=_of->links[0].pcm_start;
1411   _of->cur_discard_count=_of->links[0].head.pre_skip;
1412   if(OP_UNLIKELY(ret<0))return ret;
1413   /*And restore the position indicator.*/
1414   ret=(*_of->callbacks.seek)(_of->source,op_position(_of),SEEK_SET);
1415   return OP_UNLIKELY(ret<0)?OP_EREAD:0;
1416 }
1417
1418 /*Clear out the current logical bitstream decoder.*/
1419 static void op_decode_clear(OggOpusFile *_of){
1420   /*We don't actually free the decoder.
1421     We might be able to re-use it for the next link.*/
1422   _of->op_count=0;
1423   _of->od_buffer_size=0;
1424   _of->prev_packet_gp=-1;
1425   if(!_of->seekable){
1426     OP_ASSERT(_of->ready_state>=OP_INITSET);
1427     opus_tags_clear(&_of->links[0].tags);
1428   }
1429   _of->ready_state=OP_OPENED;
1430 }
1431
1432 static void op_clear(OggOpusFile *_of){
1433   OggOpusLink *links;
1434   _ogg_free(_of->od_buffer);
1435   if(_of->od!=NULL)opus_multistream_decoder_destroy(_of->od);
1436   links=_of->links;
1437   if(!_of->seekable){
1438     if(_of->ready_state>OP_OPENED||_of->ready_state==OP_PARTOPEN){
1439       opus_tags_clear(&links[0].tags);
1440     }
1441   }
1442   else if(OP_LIKELY(links!=NULL)){
1443     int nlinks;
1444     int link;
1445     nlinks=_of->nlinks;
1446     for(link=0;link<nlinks;link++)opus_tags_clear(&links[link].tags);
1447   }
1448   _ogg_free(links);
1449   _ogg_free(_of->serialnos);
1450   ogg_stream_clear(&_of->os);
1451   ogg_sync_clear(&_of->oy);
1452   if(_of->callbacks.close!=NULL)(*_of->callbacks.close)(_of->source);
1453 }
1454
1455 static int op_open1(OggOpusFile *_of,
1456  void *_source,const OpusFileCallbacks *_cb,
1457  const unsigned char *_initial_data,size_t _initial_bytes){
1458   ogg_page  og;
1459   ogg_page *pog;
1460   int       seekable;
1461   int       ret;
1462   memset(_of,0,sizeof(*_of));
1463   _of->end=-1;
1464   _of->source=_source;
1465   *&_of->callbacks=*_cb;
1466   /*At a minimum, we need to be able to read data.*/
1467   if(OP_UNLIKELY(_of->callbacks.read==NULL))return OP_EREAD;
1468   /*Initialize the framing state.*/
1469   ogg_sync_init(&_of->oy);
1470   /*Perhaps some data was previously read into a buffer for testing against
1471      other stream types.
1472     Allow initialization from this previously read data (especially as we may
1473      be reading from a non-seekable stream).
1474     This requires copying it into a buffer allocated by ogg_sync_buffer() and
1475      doesn't support seeking, so this is not a good mechanism to use for
1476      decoding entire files from RAM.*/
1477   if(_initial_bytes>0){
1478     char *buffer;
1479     buffer=ogg_sync_buffer(&_of->oy,_initial_bytes);
1480     memcpy(buffer,_initial_data,_initial_bytes*sizeof(*buffer));
1481     ogg_sync_wrote(&_of->oy,_initial_bytes);
1482   }
1483   /*Can we seek?
1484     Stevens suggests the seek test is portable.*/
1485   seekable=_cb->seek!=NULL&&(*_cb->seek)(_source,0,SEEK_CUR)!=-1;
1486   /*If seek is implemented, tell must also be implemented.*/
1487   if(seekable){
1488     if(OP_UNLIKELY(_of->callbacks.tell==NULL))return OP_EINVAL;
1489     else{
1490       opus_int64 pos;
1491       pos=(*_of->callbacks.tell)(_of->source);
1492       /*If the current position is not equal to the initial bytes consumed,
1493          absolute seeking will not work.*/
1494       if(OP_UNLIKELY(pos!=(opus_int64)_initial_bytes))return OP_EINVAL;
1495     }
1496   }
1497   _of->seekable=seekable;
1498   /*Don't seek yet.
1499     Set up a 'single' (current) logical bitstream entry for partial open.*/
1500   _of->links=(OggOpusLink *)_ogg_malloc(sizeof(*_of->links));
1501   /*The serialno gets filled in later by op_fetch_headers().*/
1502   ogg_stream_init(&_of->os,-1);
1503   pog=NULL;
1504   for(;;){
1505     /*Fetch all BOS pages, store the Opus header and all seen serial numbers,
1506       and load subsequent Opus setup headers.*/
1507     ret=op_fetch_headers(_of,&_of->links[0].head,&_of->links[0].tags,
1508      &_of->serialnos,&_of->nserialnos,&_of->cserialnos,pog);
1509     if(OP_UNLIKELY(ret<0))break;
1510     _of->nlinks=1;
1511     _of->links[0].offset=0;
1512     _of->links[0].data_offset=_of->offset;
1513     _of->links[0].pcm_end=-1;
1514     _of->links[0].serialno=_of->os.serialno;
1515     /*Fetch the initial PCM offset.*/
1516     ret=op_find_initial_pcm_offset(_of,_of->links,&og);
1517     if(seekable||OP_LIKELY(ret<=0))break;
1518     /*This link was empty, but we already have the BOS page for the next one in
1519        og.
1520       We can't seek, so start processing the next link right now.*/
1521     opus_tags_clear(&_of->links[0].tags);
1522     _of->nlinks=0;
1523     if(!seekable)_of->cur_link++;
1524     pog=&og;
1525   }
1526   if(OP_UNLIKELY(ret<0)){
1527     /*Don't auto-close the stream on failure.*/
1528     _of->callbacks.close=NULL;
1529     op_clear(_of);
1530   }
1531   else _of->ready_state=OP_PARTOPEN;
1532   return ret;
1533 }
1534
1535 static int op_open2(OggOpusFile *_of){
1536   int ret;
1537   OP_ASSERT(_of->ready_state==OP_PARTOPEN);
1538   if(_of->seekable){
1539     _of->ready_state=OP_OPENED;
1540     ret=op_open_seekable2(_of);
1541   }
1542   else ret=0;
1543   if(OP_LIKELY(ret>=0)){
1544     /*We have buffered packets from op_find_initial_pcm_offset().
1545       Move to OP_INITSET so we can use them.*/
1546     _of->ready_state=OP_STREAMSET;
1547     ret=op_make_decode_ready(_of);
1548     if(OP_LIKELY(ret>=0))return 0;
1549   }
1550   /*Don't auto-close the stream on failure.*/
1551   _of->callbacks.close=NULL;
1552   op_clear(_of);
1553   return ret;
1554 }
1555
1556 OggOpusFile *op_test_callbacks(void *_source,const OpusFileCallbacks *_cb,
1557  const unsigned char *_initial_data,size_t _initial_bytes,int *_error){
1558   OggOpusFile *of;
1559   int          ret;
1560   of=(OggOpusFile *)_ogg_malloc(sizeof(*of));
1561   ret=OP_EFAULT;
1562   if(OP_LIKELY(of!=NULL)){
1563     ret=op_open1(of,_source,_cb,_initial_data,_initial_bytes);
1564     if(OP_LIKELY(ret>=0)){
1565       if(_error!=NULL)*_error=0;
1566       return of;
1567     }
1568     _ogg_free(of);
1569   }
1570   if(_error!=NULL)*_error=ret;
1571   return NULL;
1572 }
1573
1574 OggOpusFile *op_open_callbacks(void *_source,const OpusFileCallbacks *_cb,
1575  const unsigned char *_initial_data,size_t _initial_bytes,int *_error){
1576   OggOpusFile *of;
1577   of=op_test_callbacks(_source,_cb,_initial_data,_initial_bytes,_error);
1578   if(OP_LIKELY(of!=NULL)){
1579     int ret;
1580     ret=op_open2(of);
1581     if(OP_LIKELY(ret>=0))return of;
1582     if(_error!=NULL)*_error=ret;
1583     _ogg_free(of);
1584   }
1585   return NULL;
1586 }
1587
1588 /*Convenience routine to clean up from failure for the open functions that
1589    create their own streams.*/
1590 static OggOpusFile *op_open_close_on_failure(void *_source,
1591  const OpusFileCallbacks *_cb,int *_error){
1592   OggOpusFile *of;
1593   if(OP_UNLIKELY(_source==NULL)){
1594     if(_error!=NULL)*_error=OP_EFAULT;
1595     return NULL;
1596   }
1597   of=op_open_callbacks(_source,_cb,NULL,0,_error);
1598   if(OP_UNLIKELY(of==NULL))(*_cb->close)(_source);
1599   return of;
1600 }
1601
1602 OggOpusFile *op_open_file(const char *_path,int *_error){
1603   OpusFileCallbacks cb;
1604   return op_open_close_on_failure(op_fopen(&cb,_path,"rb"),&cb,_error);
1605 }
1606
1607 OggOpusFile *op_open_memory(const unsigned char *_data,size_t _size,
1608  int *_error){
1609   OpusFileCallbacks cb;
1610   return op_open_close_on_failure(op_mem_stream_create(&cb,_data,_size),&cb,
1611    _error);
1612 }
1613
1614 /*Convenience routine to clean up from failure for the open functions that
1615    create their own streams.*/
1616 static OggOpusFile *op_test_close_on_failure(void *_source,
1617  const OpusFileCallbacks *_cb,int *_error){
1618   OggOpusFile *of;
1619   if(OP_UNLIKELY(_source==NULL)){
1620     if(_error!=NULL)*_error=OP_EFAULT;
1621     return NULL;
1622   }
1623   of=op_test_callbacks(_source,_cb,NULL,0,_error);
1624   if(OP_UNLIKELY(of==NULL))(*_cb->close)(_source);
1625   return of;
1626 }
1627
1628 OggOpusFile *op_test_file(const char *_path,int *_error){
1629   OpusFileCallbacks cb;
1630   return op_test_close_on_failure(op_fopen(&cb,_path,"rb"),&cb,_error);
1631 }
1632
1633 OggOpusFile *op_test_memory(const unsigned char *_data,size_t _size,
1634  int *_error){
1635   OpusFileCallbacks cb;
1636   return op_test_close_on_failure(op_mem_stream_create(&cb,_data,_size),&cb,
1637    _error);
1638 }
1639
1640 int op_test_open(OggOpusFile *_of){
1641   int ret;
1642   if(OP_UNLIKELY(_of->ready_state!=OP_PARTOPEN))return OP_EINVAL;
1643   ret=op_open2(_of);
1644   /*op_open2() will clear this structure on failure.
1645     Reset its contents to prevent double-frees in op_free().*/
1646   if(OP_UNLIKELY(ret<0))memset(_of,0,sizeof(*_of));
1647   return ret;
1648 }
1649
1650 void op_free(OggOpusFile *_of){
1651   if(OP_LIKELY(_of!=NULL)){
1652     op_clear(_of);
1653     _ogg_free(_of);
1654   }
1655 }
1656
1657 int op_seekable(OggOpusFile *_of){
1658   return _of->seekable;
1659 }
1660
1661 int op_link_count(OggOpusFile *_of){
1662   return _of->nlinks;
1663 }
1664
1665 ogg_uint32_t op_serialno(OggOpusFile *_of,int _li){
1666   if(OP_UNLIKELY(_li>=_of->nlinks))_li=_of->nlinks-1;
1667   if(!_of->seekable)_li=0;
1668   return _of->links[_li<0?_of->cur_link:_li].serialno;
1669 }
1670
1671 int op_channel_count(OggOpusFile *_of,int _li){
1672   return op_head(_of,_li)->channel_count;
1673 }
1674
1675 opus_int64 op_raw_total(OggOpusFile *_of,int _li){
1676   if(OP_UNLIKELY(_of->ready_state<OP_OPENED)
1677    ||OP_UNLIKELY(!_of->seekable)
1678    ||OP_UNLIKELY(_li>=_of->nlinks)){
1679     return OP_EINVAL;
1680   }
1681   if(_li<0)return _of->end-_of->links[0].offset;
1682   return (_li+1>=_of->nlinks?_of->end:_of->links[_li+1].offset)
1683    -_of->links[_li].offset;
1684 }
1685
1686 ogg_int64_t op_pcm_total(OggOpusFile *_of,int _li){
1687   OggOpusLink *links;
1688   ogg_int64_t  diff;
1689   int          nlinks;
1690   nlinks=_of->nlinks;
1691   if(OP_UNLIKELY(_of->ready_state<OP_OPENED)
1692    ||OP_UNLIKELY(!_of->seekable)
1693    ||OP_UNLIKELY(_li>=nlinks)){
1694     return OP_EINVAL;
1695   }
1696   links=_of->links;
1697   /*We verify that the granule position differences are larger than the
1698      pre-skip and that the total duration does not overflow during link
1699      enumeration, so we don't have to check here.*/
1700   if(_li<0){
1701     ogg_int64_t pcm_total;
1702     int         li;
1703     pcm_total=0;
1704     for(li=0;li<nlinks;li++){
1705       OP_ALWAYS_TRUE(!op_granpos_diff(&diff,
1706        links[li].pcm_end,links[li].pcm_start));
1707       pcm_total+=diff-links[li].head.pre_skip;
1708     }
1709     return pcm_total;
1710   }
1711   OP_ALWAYS_TRUE(!op_granpos_diff(&diff,
1712    links[_li].pcm_end,links[_li].pcm_start));
1713   return diff-links[_li].head.pre_skip;
1714 }
1715
1716 const OpusHead *op_head(OggOpusFile *_of,int _li){
1717   if(OP_UNLIKELY(_li>=_of->nlinks))_li=_of->nlinks-1;
1718   if(!_of->seekable)_li=0;
1719   return &_of->links[_li<0?_of->cur_link:_li].head;
1720 }
1721
1722 const OpusTags *op_tags(OggOpusFile *_of,int _li){
1723   if(OP_UNLIKELY(_li>=_of->nlinks))_li=_of->nlinks-1;
1724   if(!_of->seekable){
1725     if(_of->ready_state<OP_STREAMSET&&_of->ready_state!=OP_PARTOPEN){
1726       return NULL;
1727     }
1728     _li=0;
1729   }
1730   else if(_li<0)_li=_of->ready_state>=OP_STREAMSET?_of->cur_link:0;
1731   return &_of->links[_li].tags;
1732 }
1733
1734 int op_current_link(OggOpusFile *_of){
1735   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
1736   return _of->cur_link;
1737 }
1738
1739 /*Compute an average bitrate given a byte and sample count.
1740   Return: The bitrate in bits per second.*/
1741 static opus_int32 op_calc_bitrate(opus_int64 _bytes,ogg_int64_t _samples){
1742   /*These rates are absurd, but let's handle them anyway.*/
1743   if(OP_UNLIKELY(_bytes>(OP_INT64_MAX-(_samples>>1))/(48000*8))){
1744     ogg_int64_t den;
1745     if(OP_UNLIKELY(_bytes/(0x7FFFFFFFF/(48000*8))>=_samples))return 0x7FFFFFFF;
1746     den=_samples/(48000*8);
1747     return (opus_int32)((_bytes+(den>>1))/den);
1748   }
1749   if(OP_UNLIKELY(_samples<=0))return 0x7FFFFFFF;
1750   /*This can't actually overflow in normal operation: even with a pre-skip of
1751      545 2.5 ms frames with 8 streams running at 1282*8+1 bytes per packet
1752      (1275 byte frames + Opus framing overhead + Ogg lacing values), that all
1753      produce a single sample of decoded output, we still don't top 45 Mbps.
1754     The only way to get bitrates larger than that is with excessive Opus
1755      padding, more encoded streams than output channels, or lots and lots of
1756      Ogg pages with no packets on them.*/
1757   return (opus_int32)OP_MIN((_bytes*48000*8+(_samples>>1))/_samples,0x7FFFFFFF);
1758 }
1759
1760 opus_int32 op_bitrate(OggOpusFile *_of,int _li){
1761   if(OP_UNLIKELY(_of->ready_state<OP_OPENED)||OP_UNLIKELY(!_of->seekable)
1762    ||OP_UNLIKELY(_li>=_of->nlinks)){
1763     return OP_EINVAL;
1764   }
1765   return op_calc_bitrate(op_raw_total(_of,_li),op_pcm_total(_of,_li));
1766 }
1767
1768 opus_int32 op_bitrate_instant(OggOpusFile *_of){
1769   ogg_int64_t samples_tracked;
1770   opus_int32  ret;
1771   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
1772   samples_tracked=_of->samples_tracked;
1773   if(OP_UNLIKELY(samples_tracked==0))return OP_FALSE;
1774   ret=op_calc_bitrate(_of->bytes_tracked,samples_tracked);
1775   _of->bytes_tracked=0;
1776   _of->samples_tracked=0;
1777   return ret;
1778 }
1779
1780 /*Fetch and process a page.
1781   This handles the case where we're at a bitstream boundary and dumps the
1782    decoding machine.
1783   If the decoding machine is unloaded, it loads it.
1784   It also keeps prev_packet_gp up to date (seek and read both use this; seek
1785    uses a special hack with _readp).
1786   Return: <0) Error, OP_HOLE (lost packet), or OP_EOF.
1787            0) Need more data (only if _readp==0).
1788            1) Got at least one audio data packet.*/
1789 static int op_fetch_and_process_page(OggOpusFile *_of,
1790  ogg_page *_og,opus_int64 _page_pos,int _readp,int _spanp,int _ignore_holes){
1791   OggOpusLink  *links;
1792   ogg_uint32_t  cur_serialno;
1793   int           seekable;
1794   int           cur_link;
1795   int           ret;
1796   if(OP_LIKELY(_of->ready_state>=OP_INITSET)
1797    &&OP_LIKELY(_of->op_pos<_of->op_count)){
1798     /*We're ready to decode and have at least one packet available already.*/
1799     return 1;
1800   }
1801   if(!_readp)return 0;
1802   seekable=_of->seekable;
1803   links=_of->links;
1804   cur_link=seekable?_of->cur_link:0;
1805   cur_serialno=links[cur_link].serialno;
1806   /*Handle one page.*/
1807   for(;;){
1808     ogg_page og;
1809     OP_ASSERT(_of->ready_state>=OP_OPENED);
1810     /*This loop is not strictly necessary, but there's no sense in doing the
1811        extra checks of the larger loop for the common case in a multiplexed
1812        bistream where the page is simply part of a different logical
1813        bitstream.*/
1814     do{
1815       /*If we were given a page to use, use it.*/
1816       if(_og!=NULL){
1817         *&og=*_og;
1818         _og=NULL;
1819       }
1820       /*Keep reading until we get a page with the correct serialno.*/
1821       else _page_pos=op_get_next_page(_of,&og,_of->end);
1822       /*EOF: Leave uninitialized.*/
1823       if(_page_pos<0)return _page_pos<OP_FALSE?(int)_page_pos:OP_EOF;
1824       if(OP_LIKELY(_of->ready_state>=OP_STREAMSET)){
1825         if(cur_serialno!=(ogg_uint32_t)ogg_page_serialno(&og)){
1826           /*Two possibilities:
1827              1) Another stream is multiplexed into this logical section, or*/
1828           if(OP_LIKELY(!ogg_page_bos(&og)))continue;
1829           /* 2) Our decoding just traversed a bitstream boundary.*/
1830           if(!_spanp)return OP_EOF;
1831           if(OP_LIKELY(_of->ready_state>=OP_INITSET))op_decode_clear(_of);
1832           break;
1833         }
1834       }
1835       /*Bitrate tracking: add the header's bytes here.
1836         The body bytes are counted when we consume the packets.*/
1837       _of->bytes_tracked+=og.header_len;
1838     }
1839     while(0);
1840     /*Do we need to load a new machine before submitting the page?
1841       This is different in the seekable and non-seekable cases.
1842       In the seekable case, we already have all the header information loaded
1843        and cached.
1844       We just initialize the machine with it and continue on our merry way.
1845       In the non-seekable (streaming) case, we'll only be at a boundary if we
1846        just left the previous logical bitstream, and we're now nominally at the
1847        header of the next bitstream.*/
1848     if(OP_UNLIKELY(_of->ready_state<OP_STREAMSET)){
1849       if(seekable){
1850         ogg_uint32_t serialno;
1851         int          nlinks;
1852         int          li;
1853         serialno=ogg_page_serialno(&og);
1854         /*Match the serialno to bitstream section.
1855           We use this rather than offset positions to avoid problems near
1856            logical bitstream boundaries.*/
1857         nlinks=_of->nlinks;
1858         for(li=0;li<nlinks&&links[li].serialno!=serialno;li++);
1859         /*Not a desired Opus bitstream section.
1860           Keep trying.*/
1861         if(li>=nlinks)continue;
1862         cur_serialno=serialno;
1863         _of->cur_link=cur_link=li;
1864         ogg_stream_reset_serialno(&_of->os,serialno);
1865         _of->ready_state=OP_STREAMSET;
1866         /*If we're at the start of this link, initialize the granule position
1867            and pre-skip tracking.*/
1868         if(_page_pos<=links[cur_link].data_offset){
1869           _of->prev_packet_gp=links[cur_link].pcm_start;
1870           _of->cur_discard_count=links[cur_link].head.pre_skip;
1871           /*Ignore a hole at the start of a new link (this is common for
1872              streams joined in the middle) or after seeking.*/
1873           _ignore_holes=1;
1874         }
1875       }
1876       else{
1877         do{
1878           /*We're streaming.
1879             Fetch the two header packets, build the info struct.*/
1880           ret=op_fetch_headers(_of,&links[0].head,&links[0].tags,
1881            NULL,NULL,NULL,&og);
1882           if(OP_UNLIKELY(ret<0))return ret;
1883           /*op_find_initial_pcm_offset() will suppress any initial hole for us,
1884              so no need to set _ignore_holes.*/
1885           ret=op_find_initial_pcm_offset(_of,links,&og);
1886           if(OP_UNLIKELY(ret<0))return ret;
1887           _of->links[0].serialno=cur_serialno=_of->os.serialno;
1888           _of->cur_link++;
1889         }
1890         /*If the link was empty, keep going, because we already have the
1891            BOS page of the next one in og.*/
1892         while(OP_UNLIKELY(ret>0));
1893         /*If we didn't get any packets out of op_find_initial_pcm_offset(),
1894            keep going (this is possible if end-trimming trimmed them all).*/
1895         if(_of->op_count<=0)continue;
1896         /*Otherwise, we're done.*/
1897         ret=op_make_decode_ready(_of);
1898         if(OP_UNLIKELY(ret<0))return ret;
1899         return 1;
1900       }
1901     }
1902     /*The buffered page is the data we want, and we're ready for it.
1903       Add it to the stream state.*/
1904     if(OP_UNLIKELY(_of->ready_state==OP_STREAMSET)){
1905       ret=op_make_decode_ready(_of);
1906       if(OP_UNLIKELY(ret<0))return ret;
1907     }
1908     /*Extract all the packets from the current page.*/
1909     ogg_stream_pagein(&_of->os,&og);
1910     if(OP_LIKELY(_of->ready_state>=OP_INITSET)){
1911       opus_int32 total_duration;
1912       int        durations[255];
1913       int        op_count;
1914       total_duration=op_collect_audio_packets(_of,durations);
1915       if(OP_UNLIKELY(total_duration<0)){
1916         /*Drain the packets from the page anyway.*/
1917         total_duration=op_collect_audio_packets(_of,durations);
1918         OP_ASSERT(total_duration>=0);
1919         /*Report holes to the caller.*/
1920         if(!_ignore_holes)return OP_HOLE;
1921       }
1922       op_count=_of->op_count;
1923       /*If we found at least one audio data packet, compute per-packet granule
1924          positions for them.*/
1925       if(op_count>0){
1926         ogg_int64_t diff;
1927         ogg_int64_t prev_packet_gp;
1928         ogg_int64_t cur_packet_gp;
1929         ogg_int64_t cur_page_gp;
1930         int         cur_page_eos;
1931         int         pi;
1932         cur_page_gp=_of->op[op_count-1].granulepos;
1933         cur_page_eos=_of->op[op_count-1].e_o_s;
1934         prev_packet_gp=_of->prev_packet_gp;
1935         if(OP_UNLIKELY(prev_packet_gp==-1)){
1936           opus_int32 cur_discard_count;
1937           /*This is the first call after a raw seek.
1938             Try to reconstruct prev_packet_gp from scratch.*/
1939           OP_ASSERT(seekable);
1940           if(OP_UNLIKELY(cur_page_eos)){
1941             /*If the first page we hit after our seek was the EOS page, and
1942                we didn't start from data_offset or before, we don't have
1943                enough information to do end-trimming.
1944               Proceed to the next link, rather than risk playing back some
1945                samples that shouldn't have been played.*/
1946             _of->op_count=0;
1947             continue;
1948           }
1949           /*By default discard 80 ms of data after a seek, unless we seek
1950              into the pre-skip region.*/
1951           cur_discard_count=80*48;
1952           cur_page_gp=_of->op[op_count-1].granulepos;
1953           /*Try to initialize prev_packet_gp.
1954             If the current page had packets but didn't have a granule
1955              position, or the granule position it had was too small (both
1956              illegal), just use the starting granule position for the link.*/
1957           prev_packet_gp=links[cur_link].pcm_start;
1958           if(OP_LIKELY(cur_page_gp!=-1)){
1959             op_granpos_add(&prev_packet_gp,cur_page_gp,-total_duration);
1960           }
1961           if(OP_LIKELY(!op_granpos_diff(&diff,
1962            prev_packet_gp,links[cur_link].pcm_start))){
1963             opus_int32 pre_skip;
1964             /*If we start at the beginning of the pre-skip region, or we're
1965                at least 80 ms from the end of the pre-skip region, we discard
1966                to the end of the pre-skip region.
1967               Otherwise, we still use the 80 ms default, which will discard
1968                past the end of the pre-skip region.*/
1969             pre_skip=links[cur_link].head.pre_skip;
1970             if(diff>=0&&diff<=OP_MAX(0,pre_skip-80*48)){
1971               cur_discard_count=pre_skip-(int)diff;
1972             }
1973           }
1974           _of->cur_discard_count=cur_discard_count;
1975         }
1976         if(OP_UNLIKELY(cur_page_gp==-1)){
1977           /*This page had completed packets but didn't have a valid granule
1978              position.
1979             This is illegal, but we'll try to handle it by continuing to count
1980              forwards from the previous page.*/
1981           if(op_granpos_add(&cur_page_gp,prev_packet_gp,total_duration)<0){
1982             /*The timestamp for this page overflowed.*/
1983             cur_page_gp=links[cur_link].pcm_end;
1984           }
1985         }
1986         /*If we hit the last page, handle end-trimming.*/
1987         if(OP_UNLIKELY(cur_page_eos)
1988          &&OP_LIKELY(!op_granpos_diff(&diff,cur_page_gp,prev_packet_gp))
1989          &&OP_LIKELY(diff<total_duration)){
1990           cur_packet_gp=prev_packet_gp;
1991           for(pi=0;pi<op_count;pi++){
1992             diff=durations[pi]-diff;
1993             /*If we have samples to trim...*/
1994             if(diff>0){
1995               /*If we trimmed the entire packet, stop (the spec says encoders
1996                  shouldn't do this, but we support it anyway).*/
1997               if(OP_UNLIKELY(diff>durations[pi]))break;
1998               cur_packet_gp=cur_page_gp;
1999               /*Move the EOS flag to this packet, if necessary, so we'll trim
2000                  the samples during decode.*/
2001               _of->op[pi].e_o_s=1;
2002             }
2003             else{
2004               /*Update the granule position as normal.*/
2005               OP_ALWAYS_TRUE(!op_granpos_add(&cur_packet_gp,
2006                cur_packet_gp,durations[pi]));
2007             }
2008             _of->op[pi].granulepos=cur_packet_gp;
2009             OP_ALWAYS_TRUE(!op_granpos_diff(&diff,cur_page_gp,cur_packet_gp));
2010           }
2011         }
2012         else{
2013           /*Propagate timestamps to earlier packets.
2014             op_granpos_add(&prev_packet_gp,prev_packet_gp,total_duration)
2015              should succeed and give prev_packet_gp==cur_page_gp.
2016             But we don't bother to check that, as there isn't much we can do
2017              if it's not true.
2018             The only thing we guarantee is that the start and end granule
2019              positions of the packets are valid, and that they are monotonic
2020              within a page.
2021             They might be completely out of range for this link (we'll check
2022              that elsewhere), or non-monotonic between pages.*/
2023           if(OP_UNLIKELY(op_granpos_add(&prev_packet_gp,
2024            cur_page_gp,-total_duration)<0)){
2025             /*The starting timestamp for the first packet on this page
2026                underflowed.
2027               This is illegal, but we ignore it.*/
2028             prev_packet_gp=0;
2029           }
2030           for(pi=0;pi<op_count;pi++){
2031             if(OP_UNLIKELY(op_granpos_add(&cur_packet_gp,
2032              cur_page_gp,-total_duration)<0)){
2033               /*The start timestamp for this packet underflowed.
2034                 This is illegal, but we ignore it.*/
2035               cur_packet_gp=0;
2036             }
2037             total_duration-=durations[pi];
2038             OP_ASSERT(total_duration>=0);
2039             OP_ALWAYS_TRUE(!op_granpos_add(&cur_packet_gp,
2040              cur_packet_gp,durations[pi]));
2041             _of->op[pi].granulepos=cur_packet_gp;
2042           }
2043           OP_ASSERT(total_duration==0);
2044         }
2045         _of->prev_packet_gp=prev_packet_gp;
2046         _of->op_count=pi;
2047         /*If end-trimming didn't trim all the packets, we're done.*/
2048         if(OP_LIKELY(pi>0))return 1;
2049       }
2050     }
2051   }
2052 }
2053
2054 int op_raw_seek(OggOpusFile *_of,opus_int64 _pos){
2055   int          ret;
2056   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
2057   /*Don't dump the decoder state if we can't seek.*/
2058   if(OP_UNLIKELY(!_of->seekable))return OP_ENOSEEK;
2059   if(OP_UNLIKELY(_pos<0)||OP_UNLIKELY(_pos>_of->end))return OP_EINVAL;
2060   /*Clear out any buffered, decoded data.*/
2061   op_decode_clear(_of);
2062   _of->bytes_tracked=0;
2063   _of->samples_tracked=0;
2064   ret=op_seek_helper(_of,_pos);
2065   if(OP_UNLIKELY(ret<0))return OP_EREAD;
2066   ret=op_fetch_and_process_page(_of,NULL,-1,1,1,1);
2067   /*If we hit EOF, op_fetch_and_process_page() leaves us uninitialized.
2068     Instead, jump to the end.*/
2069   if(ret==OP_EOF){
2070     int cur_link;
2071     op_decode_clear(_of);
2072     cur_link=_of->nlinks-1;
2073     _of->cur_link=cur_link;
2074     _of->prev_packet_gp=_of->links[cur_link].pcm_end;
2075     _of->cur_discard_count=0;
2076     ret=0;
2077   }
2078   else if(ret>0)ret=0;
2079   return ret;
2080 }
2081
2082 /*Convert a PCM offset relative to the start of the whole stream to a granule
2083    position in an individual link.*/
2084 static ogg_int64_t op_get_granulepos(const OggOpusFile *_of,
2085  ogg_int64_t _pcm_offset,int *_li){
2086   OggOpusLink *links;
2087   ogg_int64_t  duration;
2088   int          nlinks;
2089   int          li;
2090   OP_ASSERT(_pcm_offset>=0);
2091   nlinks=_of->nlinks;
2092   links=_of->links;
2093   for(li=0;OP_LIKELY(li<nlinks);li++){
2094     ogg_int64_t pcm_start;
2095     opus_int32  pre_skip;
2096     pcm_start=links[li].pcm_start;
2097     pre_skip=links[li].head.pre_skip;
2098     OP_ALWAYS_TRUE(!op_granpos_diff(&duration,links[li].pcm_end,pcm_start));
2099     duration-=pre_skip;
2100     if(_pcm_offset<duration){
2101       _pcm_offset+=pre_skip;
2102       if(OP_UNLIKELY(pcm_start>OP_INT64_MAX-_pcm_offset)){
2103         /*Adding this amount to the granule position would overflow the positive
2104            half of its 64-bit range.
2105           Since signed overflow is undefined in C, do it in a way the compiler
2106            isn't allowed to screw up.*/
2107         _pcm_offset-=OP_INT64_MAX-pcm_start+1;
2108         pcm_start=OP_INT64_MIN;
2109       }
2110       pcm_start+=_pcm_offset;
2111       *_li=li;
2112       return pcm_start;
2113     }
2114     _pcm_offset-=duration;
2115   }
2116   return -1;
2117 }
2118
2119 /*This controls how close the target has to be to use the current stream
2120    position to subdivide the initial range.
2121   Two minutes seems to be a good default.*/
2122 #define OP_CUR_TIME_THRESH (120*48*(opus_int32)1000)
2123
2124 /*Note: The OP_SMALL_FOOTPRINT #define doesn't (currently) save much code size,
2125    but it's meant to serve as documentation for portions of the seeking
2126    algorithm that are purely optional, to aid others learning from/porting this
2127    code to other contexts.*/
2128 /*#define OP_SMALL_FOOTPRINT (1)*/
2129
2130 /*Search within link _li for the page with the highest granule position
2131    preceding (or equal to) _target_gp.
2132   There is a danger here: missing pages or incorrect frame number information
2133    in the bitstream could make our task impossible.
2134   Account for that (and report it as an error condition).*/
2135 static int op_pcm_seek_page(OggOpusFile *_of,
2136  ogg_int64_t _target_gp,int _li){
2137   OggOpusLink  *link;
2138   ogg_page      og;
2139   ogg_int64_t   pcm_pre_skip;
2140   ogg_int64_t   pcm_start;
2141   ogg_int64_t   pcm_end;
2142   ogg_int64_t   best_gp;
2143   ogg_int64_t   diff;
2144   ogg_uint32_t  serialno;
2145   opus_int32    pre_skip;
2146   opus_int64    begin;
2147   opus_int64    end;
2148   opus_int64    boundary;
2149   opus_int64    best;
2150   opus_int64    page_offset;
2151   opus_int64    d0;
2152   opus_int64    d1;
2153   opus_int64    d2;
2154   int           force_bisect;
2155   int           ret;
2156   _of->bytes_tracked=0;
2157   _of->samples_tracked=0;
2158   link=_of->links+_li;
2159   best_gp=pcm_start=link->pcm_start;
2160   pcm_end=link->pcm_end;
2161   serialno=link->serialno;
2162   best=begin=link->data_offset;
2163   page_offset=-1;
2164   /*We discard the first 80 ms of data after a seek, so seek back that much
2165      farther.
2166     If we can't, simply seek to the beginning of the link.*/
2167   if(OP_UNLIKELY(op_granpos_add(&_target_gp,_target_gp,-80*48)<0)
2168    ||OP_UNLIKELY(op_granpos_cmp(_target_gp,pcm_start)<0)){
2169     _target_gp=pcm_start;
2170   }
2171   /*Special case seeking to the start of the link.*/
2172   pre_skip=link->head.pre_skip;
2173   OP_ALWAYS_TRUE(!op_granpos_add(&pcm_pre_skip,pcm_start,pre_skip));
2174   if(op_granpos_cmp(_target_gp,pcm_pre_skip)<0)end=boundary=begin;
2175   else{
2176     end=boundary=link->end_offset;
2177 #if !defined(OP_SMALL_FOOTPRINT)
2178     /*If we were decoding from this link, we can narrow the range a bit.*/
2179     if(_li==_of->cur_link&&_of->ready_state>=OP_INITSET){
2180       opus_int64 offset;
2181       int        op_count;
2182       op_count=_of->op_count;
2183       /*The only way the offset can be invalid _and_ we can fail the granule
2184          position checks below is if someone changed the contents of the last
2185          page since we read it.
2186         We'd be within our rights to just return OP_EBADLINK in that case, but
2187          we'll simply ignore the current position instead.*/
2188       offset=_of->offset;
2189       if(op_count>0&&OP_LIKELY(offset<=end)){
2190         ogg_int64_t gp;
2191         /*Make sure the timestamp is valid.
2192           The granule position might be -1 if we collected the packets from a
2193            page without a granule position after reporting a hole.*/
2194         gp=_of->op[op_count-1].granulepos;
2195         if(OP_LIKELY(gp!=-1)&&OP_LIKELY(op_granpos_cmp(pcm_start,gp)<0)
2196          &&OP_LIKELY(op_granpos_cmp(pcm_end,gp)>0)){
2197           OP_ALWAYS_TRUE(!op_granpos_diff(&diff,gp,_target_gp));
2198           /*We only actually use the current time if either
2199             a) We can cut off at least half the range, or
2200             b) We're seeking sufficiently close to the current position that
2201                 it's likely to be informative.
2202             Otherwise it appears using the whole link range to estimate the
2203              first seek location gives better results, on average.*/
2204           if(diff<0){
2205             OP_ASSERT(offset>=begin);
2206             if(offset-begin>=end-begin>>1||diff>-OP_CUR_TIME_THRESH){
2207               best=begin=offset;
2208               best_gp=pcm_start=gp;
2209             }
2210           }
2211           else{
2212             ogg_int64_t prev_page_gp;
2213             /*We might get lucky and already have the packet with the target
2214                buffered.
2215               Worth checking.
2216               For very small files (with all of the data in a single page,
2217                generally 1 second or less), we can loop them continuously
2218                without seeking at all.*/
2219             OP_ALWAYS_TRUE(!op_granpos_add(&prev_page_gp,_of->op[0].granulepos,
2220              op_get_packet_duration(_of->op[0].packet,_of->op[0].bytes)));
2221             if(op_granpos_cmp(prev_page_gp,_target_gp)<=0){
2222               /*Don't call op_decode_clear(), because it will dump our
2223                  packets.*/
2224               _of->op_pos=0;
2225               _of->od_buffer_size=0;
2226               _of->prev_packet_gp=prev_page_gp;
2227               _of->ready_state=OP_STREAMSET;
2228               return op_make_decode_ready(_of);
2229             }
2230             /*No such luck.
2231               Check if we can cut off at least half the range, though.*/
2232             if(offset-begin<=end-begin>>1||diff<OP_CUR_TIME_THRESH){
2233               /*We really want the page start here, but this will do.*/
2234               end=boundary=offset;
2235               pcm_end=gp;
2236             }
2237           }
2238         }
2239       }
2240     }
2241 #endif
2242   }
2243   /*This code was originally based on the "new search algorithm by HB (Nicholas
2244      Vinen)" from libvorbisfile.
2245     It has been modified substantially since.*/
2246   op_decode_clear(_of);
2247   /*Initialize the interval size history.*/
2248   d2=d1=d0=end-begin;
2249   force_bisect=0;
2250   while(begin<end){
2251     opus_int64 bisect;
2252     opus_int64 next_boundary;
2253     opus_int32 chunk_size;
2254     if(end-begin<OP_CHUNK_SIZE)bisect=begin;
2255     else{
2256       /*Update the interval size history.*/
2257       d0=d1>>1;
2258       d1=d2>>1;
2259       d2=end-begin>>1;
2260       if(force_bisect)bisect=begin+(end-begin>>1);
2261       else{
2262         ogg_int64_t diff2;
2263         OP_ALWAYS_TRUE(!op_granpos_diff(&diff,_target_gp,pcm_start));
2264         OP_ALWAYS_TRUE(!op_granpos_diff(&diff2,pcm_end,pcm_start));
2265         /*Take a (pretty decent) guess.*/
2266         bisect=begin+op_rescale64(diff,diff2,end-begin)-OP_CHUNK_SIZE;
2267       }
2268       if(bisect-OP_CHUNK_SIZE<begin)bisect=begin;
2269       force_bisect=0;
2270     }
2271     if(bisect!=_of->offset){
2272       page_offset=-1;
2273       ret=op_seek_helper(_of,bisect);
2274       if(OP_UNLIKELY(ret<0))return ret;
2275     }
2276     chunk_size=OP_CHUNK_SIZE;
2277     next_boundary=boundary;
2278     while(begin<end){
2279       page_offset=op_get_next_page(_of,&og,boundary);
2280       if(page_offset<0){
2281         if(page_offset<OP_FALSE)return (int)page_offset;
2282         /*There are no more pages in our interval from our stream with a valid
2283            timestamp that start at position bisect or later.*/
2284         /*If we scanned the whole interval, we're done.*/
2285         if(bisect<=begin+1)end=begin;
2286         else{
2287           /*Otherwise, back up one chunk.*/
2288           bisect=OP_MAX(bisect-chunk_size,begin);
2289           ret=op_seek_helper(_of,bisect);
2290           if(OP_UNLIKELY(ret<0))return ret;
2291           /*Bump up the chunk size.*/
2292           chunk_size=OP_MIN(2*chunk_size,OP_CHUNK_SIZE_MAX);
2293           /*If we did find a page from another stream or without a timestamp,
2294              don't read past it.*/
2295           boundary=next_boundary;
2296         }
2297       }
2298       else{
2299         ogg_int64_t gp;
2300         /*Save the offset of the first page we found after the seek, regardless
2301            of the stream it came from or whether or not it has a timestamp.*/
2302         next_boundary=OP_MIN(page_offset,next_boundary);
2303         if(serialno!=(ogg_uint32_t)ogg_page_serialno(&og))continue;
2304         gp=ogg_page_granulepos(&og);
2305         if(gp==-1)continue;
2306         if(op_granpos_cmp(gp,_target_gp)<0){
2307           /*We found a page that ends before our target.
2308             Advance to the raw offset of the next page.*/
2309           begin=_of->offset;
2310           if(OP_UNLIKELY(op_granpos_cmp(pcm_start,gp)>0)
2311            ||OP_UNLIKELY(op_granpos_cmp(pcm_end,gp)<0)){
2312             /*Don't let pcm_start get out of range!
2313               That could happen with an invalid timestamp.*/
2314             break;
2315           }
2316           /*Save the byte offset of the end of the page with this granule
2317              position.*/
2318           best=begin;
2319           best_gp=pcm_start=gp;
2320           OP_ALWAYS_TRUE(!op_granpos_diff(&diff,_target_gp,pcm_start));
2321           /*If we're more than a second away from our target, break out and
2322              do another bisection.*/
2323           if(diff>48000)break;
2324           /*Otherwise, keep scanning forward (do NOT use begin+1).*/
2325           bisect=begin;
2326         }
2327         else{
2328           /*We found a page that ends after our target.*/
2329           /*If we scanned the whole interval before we found it, we're done.*/
2330           if(bisect<=begin+1)end=begin;
2331           else{
2332             end=bisect;
2333             /*In later iterations, don't read past the first page we found.*/
2334             boundary=next_boundary;
2335             /*If we're not making much progress shrinking the interval size,
2336                start forcing straight bisection to limit the worst case.*/
2337             force_bisect=end-begin>d0*2;
2338             /*Don't let pcm_end get out of range!
2339               That could happen with an invalid timestamp.*/
2340             if(OP_LIKELY(op_granpos_cmp(pcm_end,gp)>0)
2341              &&OP_LIKELY(op_granpos_cmp(pcm_start,gp)<=0)){
2342               pcm_end=gp;
2343             }
2344             break;
2345           }
2346         }
2347       }
2348     }
2349   }
2350   /*Found our page.
2351     Seek to the end of it and update prev_packet_gp.
2352     Our caller will set cur_discard_count.
2353     This is an easier case than op_raw_seek(), as we don't need to keep any
2354      packets from the page we found.*/
2355   /*Seek, if necessary.*/
2356   if(best!=page_offset){
2357     page_offset=-1;
2358     ret=op_seek_helper(_of,best);
2359     if(OP_UNLIKELY(ret<0))return ret;
2360   }
2361   OP_ASSERT(op_granpos_cmp(best_gp,pcm_start)>=0);
2362   _of->cur_link=_li;
2363   _of->ready_state=OP_STREAMSET;
2364   _of->prev_packet_gp=best_gp;
2365   ogg_stream_reset_serialno(&_of->os,serialno);
2366   ret=op_fetch_and_process_page(_of,page_offset<0?NULL:&og,page_offset,1,0,1);
2367   if(OP_UNLIKELY(ret<=0))return OP_EBADLINK;
2368   /*Verify result.*/
2369   if(OP_UNLIKELY(op_granpos_cmp(_of->prev_packet_gp,_target_gp)>0)){
2370     return OP_EBADLINK;
2371   }
2372   return 0;
2373 }
2374
2375 int op_pcm_seek(OggOpusFile *_of,ogg_int64_t _pcm_offset){
2376   OggOpusLink *link;
2377   ogg_int64_t  pcm_start;
2378   ogg_int64_t  target_gp;
2379   ogg_int64_t  prev_packet_gp;
2380   ogg_int64_t  skip;
2381   ogg_int64_t  diff;
2382   int          op_count;
2383   int          op_pos;
2384   int          ret;
2385   int          li;
2386   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
2387   if(OP_UNLIKELY(!_of->seekable))return OP_ENOSEEK;
2388   if(OP_UNLIKELY(_pcm_offset<0))return OP_EINVAL;
2389   target_gp=op_get_granulepos(_of,_pcm_offset,&li);
2390   if(OP_UNLIKELY(target_gp==-1))return OP_EINVAL;
2391   link=_of->links+li;
2392   pcm_start=link->pcm_start;
2393   OP_ALWAYS_TRUE(!op_granpos_diff(&_pcm_offset,target_gp,pcm_start));
2394 #if !defined(OP_SMALL_FOOTPRINT)
2395   /*For small (90 ms or less) forward seeks within the same link, just decode
2396      forward.
2397     This also optimizes the case of seeking to the current position.*/
2398   if(li==_of->cur_link&&_of->ready_state>=OP_INITSET){
2399     ogg_int64_t gp;
2400     gp=_of->prev_packet_gp;
2401     if(OP_LIKELY(gp!=-1)){
2402       int nbuffered;
2403       nbuffered=OP_MAX(_of->od_buffer_size-_of->od_buffer_pos,0);
2404       OP_ALWAYS_TRUE(!op_granpos_add(&gp,gp,-nbuffered));
2405       /*We do _not_ add cur_discard_count to gp.
2406         Otherwise the total amount to discard could grow without bound, and it
2407          would be better just to do a full seek.*/
2408       if(OP_LIKELY(!op_granpos_diff(&diff,gp,pcm_start))){
2409         ogg_int64_t discard_count;
2410         discard_count=_pcm_offset-diff;
2411         /*We use a threshold of 90 ms instead of 80, since 80 ms is the
2412            _minimum_ we would have discarded after a full seek.
2413           Assuming 20 ms frames (the default), we'd discard 90 ms on average.*/
2414         if(discard_count>=0&&OP_UNLIKELY(discard_count<90*48)){
2415           _of->cur_discard_count=(opus_int32)discard_count;
2416           return 0;
2417         }
2418       }
2419     }
2420   }
2421 #endif
2422   ret=op_pcm_seek_page(_of,target_gp,li);
2423   if(OP_UNLIKELY(ret<0))return ret;
2424   /*Now skip samples until we actually get to our target.*/
2425   /*Figure out where we should skip to.*/
2426   if(_pcm_offset<=link->head.pre_skip)skip=0;
2427   else skip=OP_MAX(_pcm_offset-80*48,0);
2428   OP_ASSERT(_pcm_offset-skip>=0);
2429   OP_ASSERT(_pcm_offset-skip<0x7FFFFFFF-120*48);
2430   /*Skip packets until we find one with samples past our skip target.*/
2431   for(;;){
2432     op_count=_of->op_count;
2433     prev_packet_gp=_of->prev_packet_gp;
2434     for(op_pos=_of->op_pos;op_pos<op_count;op_pos++){
2435       ogg_int64_t cur_packet_gp;
2436       cur_packet_gp=_of->op[op_pos].granulepos;
2437       if(OP_LIKELY(!op_granpos_diff(&diff,cur_packet_gp,pcm_start))
2438        &&diff>skip){
2439         break;
2440       }
2441       prev_packet_gp=cur_packet_gp;
2442     }
2443     _of->prev_packet_gp=prev_packet_gp;
2444     _of->op_pos=op_pos;
2445     if(op_pos<op_count)break;
2446     /*We skipped all the packets on this page.
2447       Fetch another.*/
2448     ret=op_fetch_and_process_page(_of,NULL,-1,1,0,1);
2449     if(OP_UNLIKELY(ret<=0))return OP_EBADLINK;
2450   }
2451   OP_ALWAYS_TRUE(!op_granpos_diff(&diff,prev_packet_gp,pcm_start));
2452   /*We skipped too far.
2453     Either the timestamps were illegal or there was a hole in the data.*/
2454   if(diff>skip)return OP_EBADLINK;
2455   OP_ASSERT(_pcm_offset-diff<0x7FFFFFFF);
2456   /*TODO: If there are further holes/illegal timestamps, we still won't decode
2457      to the correct sample.
2458     However, at least op_pcm_tell() will report the correct value immediately
2459      after returning.*/
2460   _of->cur_discard_count=(opus_int32)(_pcm_offset-diff);
2461   return 0;
2462 }
2463
2464 opus_int64 op_raw_tell(OggOpusFile *_of){
2465   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
2466   return _of->offset;
2467 }
2468
2469 /*Convert a granule position from a given link to a PCM offset relative to the
2470    start of the whole stream.
2471   For unseekable sources, this gets reset to 0 at the beginning of each link.*/
2472 static ogg_int64_t op_get_pcm_offset(const OggOpusFile *_of,
2473  ogg_int64_t _gp,int _li){
2474   OggOpusLink *links;
2475   ogg_int64_t  pcm_offset;
2476   ogg_int64_t  delta;
2477   int          li;
2478   links=_of->links;
2479   pcm_offset=0;
2480   OP_ASSERT(_li<_of->nlinks);
2481   for(li=0;li<_li;li++){
2482     OP_ALWAYS_TRUE(!op_granpos_diff(&delta,
2483      links[li].pcm_end,links[li].pcm_start));
2484     delta-=links[li].head.pre_skip;
2485     pcm_offset+=delta;
2486   }
2487   OP_ASSERT(_li>=0);
2488   if(_of->seekable&&OP_UNLIKELY(op_granpos_cmp(_gp,links[_li].pcm_end)>0)){
2489     _gp=links[_li].pcm_end;
2490   }
2491   if(OP_LIKELY(op_granpos_cmp(_gp,links[_li].pcm_start)>0)){
2492     OP_ALWAYS_TRUE(!op_granpos_diff(&delta,_gp,links[_li].pcm_start));
2493     if(delta<links[_li].head.pre_skip)delta=0;
2494     else delta-=links[_li].head.pre_skip;
2495     pcm_offset+=delta;
2496   }
2497   return pcm_offset;
2498 }
2499
2500 ogg_int64_t op_pcm_tell(OggOpusFile *_of){
2501   ogg_int64_t gp;
2502   int         nbuffered;
2503   int         li;
2504   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
2505   gp=_of->prev_packet_gp;
2506   if(gp==-1)return 0;
2507   nbuffered=OP_MAX(_of->od_buffer_size-_of->od_buffer_pos,0);
2508   OP_ALWAYS_TRUE(!op_granpos_add(&gp,gp,-nbuffered));
2509   li=_of->seekable?_of->cur_link:0;
2510   if(op_granpos_add(&gp,gp,_of->cur_discard_count)<0){
2511     gp=_of->links[li].pcm_end;
2512   }
2513   return op_get_pcm_offset(_of,gp,li);
2514 }
2515
2516 /*Allocate the decoder scratch buffer.
2517   This is done lazily, since if the user provides large enough buffers, we'll
2518    never need it.*/
2519 static int op_init_buffer(OggOpusFile *_of){
2520   int nchannels_max;
2521   if(_of->seekable){
2522     OggOpusLink *links;
2523     int          nlinks;
2524     int          li;
2525     links=_of->links;
2526     nlinks=_of->nlinks;
2527     nchannels_max=1;
2528     for(li=0;li<nlinks;li++){
2529       nchannels_max=OP_MAX(nchannels_max,links[li].head.channel_count);
2530     }
2531   }
2532   else nchannels_max=OP_NCHANNELS_MAX;
2533   _of->od_buffer=(op_sample *)_ogg_malloc(
2534    sizeof(*_of->od_buffer)*nchannels_max*120*48);
2535   if(_of->od_buffer==NULL)return OP_EFAULT;
2536   return 0;
2537 }
2538
2539 /*Read more samples from the stream, using the same API as op_read() or
2540    op_read_float().*/
2541 static int op_read_native(OggOpusFile *_of,
2542  op_sample *_pcm,int _buf_size,int *_li){
2543   if(OP_UNLIKELY(_of->ready_state<OP_OPENED))return OP_EINVAL;
2544   for(;;){
2545     int ret;
2546     if(OP_LIKELY(_of->ready_state>=OP_INITSET)){
2547       int nchannels;
2548       int od_buffer_pos;
2549       int nsamples;
2550       int op_pos;
2551       nchannels=_of->links[_of->seekable?_of->cur_link:0].head.channel_count;
2552       od_buffer_pos=_of->od_buffer_pos;
2553       nsamples=_of->od_buffer_size-od_buffer_pos;
2554       /*If we have buffered samples, return them.*/
2555       if(OP_UNLIKELY(nsamples>0)){
2556         if(OP_UNLIKELY(nsamples*nchannels>_buf_size)){
2557           nsamples=_buf_size/nchannels;
2558         }
2559         memcpy(_pcm,_of->od_buffer+nchannels*od_buffer_pos,
2560          sizeof(*_pcm)*nchannels*nsamples);
2561         od_buffer_pos+=nsamples;
2562         _of->od_buffer_pos=od_buffer_pos;
2563         if(_li!=NULL)*_li=_of->cur_link;
2564         return nsamples;
2565       }
2566       /*If we have buffered packets, decode one.*/
2567       op_pos=_of->op_pos;
2568       if(OP_LIKELY(op_pos<_of->op_count)){
2569         ogg_packet  *pop;
2570         ogg_int64_t  diff;
2571         opus_int32   cur_discard_count;
2572         int          duration;
2573         int          trimmed_duration;
2574         pop=_of->op+op_pos++;
2575         _of->op_pos=op_pos;
2576         cur_discard_count=_of->cur_discard_count;
2577         duration=op_get_packet_duration(pop->packet,pop->bytes);
2578         /*We don't buffer packets with an invalid TOC sequence.*/
2579         OP_ASSERT(duration>0);
2580         trimmed_duration=duration;
2581         /*Perform end-trimming.*/
2582         if(OP_UNLIKELY(pop->e_o_s)){
2583           if(OP_UNLIKELY(op_granpos_cmp(pop->granulepos,
2584            _of->prev_packet_gp)<=0)){
2585             trimmed_duration=0;
2586           }
2587           else if(OP_LIKELY(!op_granpos_diff(&diff,
2588            pop->granulepos,_of->prev_packet_gp))){
2589             trimmed_duration=(int)OP_MIN(diff,trimmed_duration);
2590           }
2591         }
2592         _of->prev_packet_gp=pop->granulepos;
2593         if(OP_UNLIKELY(duration*nchannels>_buf_size)){
2594           op_sample *buf;
2595           /*If the user's buffer is too small, decode into a scratch buffer.*/
2596           buf=_of->od_buffer;
2597           if(OP_UNLIKELY(buf==NULL)){
2598             ret=op_init_buffer(_of);
2599             if(OP_UNLIKELY(ret<0))return ret;
2600             buf=_of->od_buffer;
2601           }
2602 #if defined(OP_FIXED_POINT)
2603           ret=opus_multistream_decode(_of->od,
2604            pop->packet,pop->bytes,buf,120*48,0);
2605 #else
2606           ret=opus_multistream_decode_float(_of->od,
2607            pop->packet,pop->bytes,buf,120*48,0);
2608 #endif
2609           if(OP_UNLIKELY(ret<0))return OP_EBADPACKET;
2610           OP_ASSERT(ret==duration);
2611           /*Perform pre-skip/pre-roll.*/
2612           od_buffer_pos=(int)OP_MIN(trimmed_duration,cur_discard_count);
2613           cur_discard_count-=od_buffer_pos;
2614           _of->cur_discard_count=cur_discard_count;
2615           _of->od_buffer_pos=od_buffer_pos;
2616           _of->od_buffer_size=trimmed_duration;
2617           /*Update bitrate tracking based on the actual samples we used from
2618              what was decoded.*/
2619           _of->bytes_tracked+=pop->bytes;
2620           _of->samples_tracked+=trimmed_duration-od_buffer_pos;
2621           /*Don't grab another page yet.*/
2622           if(OP_LIKELY(od_buffer_pos<trimmed_duration))continue;
2623         }
2624         else{
2625           /*Otherwise decode directly into the user's buffer.*/
2626 #if defined(OP_FIXED_POINT)
2627           ret=opus_multistream_decode(_of->od,pop->packet,pop->bytes,
2628            _pcm,_buf_size/nchannels,0);
2629 #else
2630           ret=opus_multistream_decode_float(_of->od,pop->packet,pop->bytes,
2631            _pcm,_buf_size/nchannels,0);
2632 #endif
2633           if(OP_UNLIKELY(ret<0))return OP_EBADPACKET;
2634           OP_ASSERT(ret==duration);
2635           if(OP_LIKELY(trimmed_duration>0)){
2636             /*Perform pre-skip/pre-roll.*/
2637             od_buffer_pos=(int)OP_MIN(trimmed_duration,cur_discard_count);
2638             cur_discard_count-=od_buffer_pos;
2639             _of->cur_discard_count=cur_discard_count;
2640             if(OP_UNLIKELY(od_buffer_pos>0)
2641              &&OP_LIKELY(od_buffer_pos<trimmed_duration)){
2642               memmove(_pcm,_pcm+od_buffer_pos*nchannels,
2643                sizeof(*_pcm)*(trimmed_duration-od_buffer_pos)*nchannels);
2644             }
2645             trimmed_duration-=od_buffer_pos;
2646             /*Update bitrate tracking based on the actual samples we used from
2647                what was decoded.*/
2648             _of->bytes_tracked+=pop->bytes;
2649             _of->samples_tracked+=trimmed_duration;
2650             if(OP_LIKELY(trimmed_duration>0)){
2651               if(_li!=NULL)*_li=_of->cur_link;
2652               return trimmed_duration;
2653             }
2654           }
2655         }
2656       }
2657     }
2658     /*Suck in another page.*/
2659     ret=op_fetch_and_process_page(_of,NULL,-1,1,1,0);
2660     if(OP_UNLIKELY(ret==OP_EOF)){
2661       if(_li!=NULL)*_li=_of->cur_link;
2662       return 0;
2663     }
2664     if(OP_UNLIKELY(ret<0))return ret;
2665   }
2666 }
2667
2668 typedef int (*op_read_filter_func)(OggOpusFile *_of,void *_dst,int _dst_sz,
2669  op_sample *_src,int _nsamples,int _nchannels);
2670
2671 /*Decode some samples and then apply a custom filter to them.
2672   This is used to convert to different output formats.*/
2673 static int op_read_native_filter(OggOpusFile *_of,void *_dst,int _dst_sz,
2674  op_read_filter_func _filter,int *_li){
2675   int ret;
2676   /*Ensure we have some decoded samples in our buffer.*/
2677   ret=op_read_native(_of,NULL,0,_li);
2678   /*Now apply the filter to them.*/
2679   if(OP_LIKELY(ret>=0)&&OP_LIKELY(_of->ready_state>=OP_INITSET)){
2680     int od_buffer_pos;
2681     od_buffer_pos=_of->od_buffer_pos;
2682     ret=_of->od_buffer_size-od_buffer_pos;
2683     if(OP_LIKELY(ret>0)){
2684       int nchannels;
2685       nchannels=_of->links[_of->seekable?_of->cur_link:0].head.channel_count;
2686       ret=(*_filter)(_of,_dst,_dst_sz,
2687        _of->od_buffer+nchannels*od_buffer_pos,ret,nchannels);
2688       OP_ASSERT(ret>=0);
2689       OP_ASSERT(ret<=_of->od_buffer_size-od_buffer_pos);
2690       od_buffer_pos+=ret;
2691       _of->od_buffer_pos=od_buffer_pos;
2692     }
2693   }
2694   return ret;
2695 }
2696
2697 #if defined(OP_FIXED_POINT)
2698
2699 int op_read(OggOpusFile *_of,opus_int16 *_pcm,int _buf_size,int *_li){
2700   return op_read_native(_of,_pcm,_buf_size,_li);
2701 }
2702
2703 /*Matrices for downmixing from the supported channel counts to stereo.
2704   The matrices with 5 or more channels are normalized to a total volume of 2.0,
2705    since most mixes sound too quiet if normalized to 1.0 (as there is generally
2706    little volume in the side/rear channels).
2707   Hence we keep the coefficients in Q14, so the downmix values won't overflow a
2708    32-bit number.*/
2709 static const opus_int16 OP_STEREO_DOWNMIX_Q14
2710  [OP_NCHANNELS_MAX-2][OP_NCHANNELS_MAX][2]={
2711   /*3.0*/
2712   {
2713     {9598,0},{6786,6786},{0,9598}
2714   },
2715   /*quadrophonic*/
2716   {
2717     {6924,0},{0,6924},{5996,3464},{3464,5996}
2718   },
2719   /*5.0*/
2720   {
2721     {10666,0},{7537,7537},{0,10666},{9234,5331},{5331,9234}
2722   },
2723   /*5.1*/
2724   {
2725     {8668,0},{6129,6129},{0,8668},{7507,4335},{4335,7507},{6129,6129}
2726   },
2727   /*6.1*/
2728   {
2729     {7459,0},{5275,5275},{0,7459},{6460,3731},{3731,6460},{4568,4568},
2730     {5275,5275}
2731   },
2732   /*7.1*/
2733   {
2734     {6368,0},{4502,4502},{0,6368},{5515,3183},{3183,5515},{5515,3183},
2735     {3183,5515},{4502,4502}
2736   }
2737 };
2738
2739 static int op_stereo_filter(OggOpusFile *_of,void *_dst,int _dst_sz,
2740  op_sample *_src,int _nsamples,int _nchannels){
2741   (void)_of;
2742   _nsamples=OP_MIN(_nsamples,_dst_sz>>1);
2743   if(_nchannels==2)memcpy(_dst,_src,_nsamples*2*sizeof(*_src));
2744   else{
2745     opus_int16 *dst;
2746     int         i;
2747     dst=(opus_int16 *)_dst;
2748     if(_nchannels==1){
2749       for(i=0;i<_nsamples;i++)dst[2*i+0]=dst[2*i+1]=_src[i];
2750     }
2751     else{
2752       for(i=0;i<_nsamples;i++){
2753         opus_int32 l;
2754         opus_int32 r;
2755         int        ci;
2756         l=r=0;
2757         for(ci=0;ci<_nchannels;ci++){
2758           opus_int32 s;
2759           s=_src[_nchannels*i+ci];
2760           l+=OP_STEREO_DOWNMIX_Q14[_nchannels-3][ci][0]*s;
2761           r+=OP_STEREO_DOWNMIX_Q14[_nchannels-3][ci][1]*s;
2762         }
2763         dst[2*i+0]=(opus_int16)OP_CLAMP(-32768,l+8192>>14,32767);
2764         dst[2*i+1]=(opus_int16)OP_CLAMP(-32768,r+8192>>14,32767);
2765       }
2766     }
2767   }
2768   return _nsamples;
2769 }
2770
2771 int op_read_stereo(OggOpusFile *_of,opus_int16 *_pcm,int _buf_size){
2772   return op_read_native_filter(_of,_pcm,_buf_size,op_stereo_filter,NULL);
2773 }
2774
2775 # if !defined(OP_DISABLE_FLOAT_API)
2776
2777 static int op_short2float_filter(OggOpusFile *_of,void *_dst,int _dst_sz,
2778  op_sample *_src,int _nsamples,int _nchannels){
2779   float *dst;
2780   int    i;
2781   (void)_of;
2782   dst=(float *)_dst;
2783   if(OP_UNLIKELY(_nsamples*_nchannels>_dst_sz))_nsamples=_dst_sz/_nchannels;
2784   _dst_sz=_nsamples*_nchannels;
2785   for(i=0;i<_dst_sz;i++)dst[i]=(1.0F/32768)*_src[i];
2786   return _nsamples;
2787 }
2788
2789 int op_read_float(OggOpusFile *_of,float *_pcm,int _buf_size,int *_li){
2790   return op_read_native_filter(_of,_pcm,_buf_size,op_short2float_filter,_li);
2791 }
2792
2793 static int op_short2float_stereo_filter(OggOpusFile *_of,
2794  void *_dst,int _dst_sz,op_sample *_src,int _nsamples,int _nchannels){
2795   float *dst;
2796   dst=(float *)_dst;
2797   _nsamples=OP_MIN(_nsamples,_dst_sz>>1);
2798   if(_nchannels==1){
2799     int i;
2800     _nsamples=op_short2float_filter(_of,dst,_nsamples,_src,_nsamples,1);
2801     for(i=_nsamples;i-->0;)dst[2*i+0]=dst[2*i+1]=dst[i];
2802     return _nsamples;
2803   }
2804   /*It would be better to convert to floats and then downmix (so that we don't
2805      risk clipping with more than 5 channels), but that would require a large
2806      stack buffer, which is probably not a good idea if you're using the
2807      fixed-point build.*/
2808   if(_nchannels>2){
2809     _nsamples=op_stereo_filter(_of,_src,_nsamples*2,
2810      _src,_nsamples,_nchannels);
2811   }
2812   return op_short2float_filter(_of,dst,_dst_sz,_src,_nsamples,2);
2813 }
2814
2815 int op_read_float_stereo(OggOpusFile *_of,float *_pcm,int _buf_size){
2816   return op_read_native_filter(_of,_pcm,_buf_size,
2817    op_short2float_stereo_filter,NULL);
2818 }
2819
2820 # endif
2821
2822 #else
2823
2824 # if defined(OP_HAVE_LRINTF)
2825 #  include <math.h>
2826 #  define op_float2int(_x) (lrintf(_x))
2827 # else
2828 #  define op_float2int(_x) ((int)((_x)+((_x)<0?-0.5F:0.5F)))
2829 # endif
2830
2831 /*The dithering code here is adapted from opusdec, part of opus-tools.
2832   It was originally written by Greg Maxwell.*/
2833
2834 static opus_uint32 op_rand(opus_uint32 _seed){
2835   return _seed*96314165+907633515&0xFFFFFFFFU;
2836 }
2837
2838 /*This implements 16-bit quantization with full triangular dither and IIR noise
2839    shaping.
2840   The noise shaping filters were designed by Sebastian Gesemann, and are based
2841    on the LAME ATH curves with flattening to limit their peak gain to 20 dB.
2842   Everyone else's noise shaping filters are mildly crazy.
2843   The 48 kHz version of this filter is just a warped version of the 44.1 kHz
2844    filter and probably could be improved by shifting the HF shelf up in
2845    frequency a little bit, since 48 kHz has a bit more room and being more
2846    conservative against bat-ears is probably more important than more noise
2847    suppression.
2848   This process can increase the peak level of the signal (in theory by the peak
2849    error of 1.5 +20 dB, though that is unobservably rare).
2850   To avoid clipping, the signal is attenuated by a couple thousandths of a dB.
2851   Initially, the approach taken here was to only attenuate by the 99.9th
2852    percentile, making clipping rare but not impossible (like SoX), but the
2853    limited gain of the filter means that the worst case was only two
2854    thousandths of a dB more, so this just uses the worst case.
2855   The attenuation is probably also helpful to prevent clipping in the DAC
2856    reconstruction filters or downstream resampling, in any case.*/
2857
2858 # define OP_GAIN (32753.0F)
2859
2860 # define OP_PRNG_GAIN (1.0F/0xFFFFFFFF)
2861
2862 /*48 kHz noise shaping filter, sd=2.34.*/
2863
2864 static const float OP_FCOEF_B[4]={
2865   2.2374F,-0.7339F,-0.1251F,-0.6033F
2866 };
2867
2868 static const float OP_FCOEF_A[4]={
2869   0.9030F,0.0116F,-0.5853F,-0.2571F
2870 };
2871
2872 static void op_shaped_dither16(OggOpusFile *_of,opus_int16 *_dst,
2873  float *_src,int _nsamples,int _nchannels){
2874   opus_uint32 seed;
2875   int         mute;
2876   int         ci;
2877   int         i;
2878   mute=_of->dither_mute;
2879   seed=_of->dither_seed;
2880   if(_of->state_channel_count!=_nchannels){
2881     mute=65;
2882 # if defined(OP_SOFT_CLIP)
2883     for(ci=0;ci<_nchannels;ci++)_of->clip_state[ci]=0;
2884 # endif
2885   }
2886 # if defined(OP_SOFT_CLIP)
2887   opus_pcm_soft_clip(_src,_nsamples,_nchannels,_of->clip_state);
2888 # endif
2889   /*In order to avoid replacing digital silence with quiet dither noise, we
2890      mute if the output has been silent for a while.*/
2891   if(mute>64)memset(_of->dither_a,0,sizeof(*_of->dither_a)*4*_nchannels);
2892   for(i=0;i<_nsamples;i++){
2893     int silent;
2894     silent=1;
2895     for(ci=0;ci<_nchannels;ci++){
2896       float r;
2897       float s;
2898       float err;
2899       int   si;
2900       int   j;
2901       s=_src[_nchannels*i+ci];
2902       silent&=s==0;
2903       s*=OP_GAIN;
2904       err=0;
2905       for(j=0;j<4;j++){
2906         err+=OP_FCOEF_B[j]*_of->dither_b[ci*4+j]
2907          -OP_FCOEF_A[j]*_of->dither_a[ci*4+j];
2908       }
2909       for(j=3;j-->0;)_of->dither_a[ci*4+j+1]=_of->dither_a[ci*4+j];
2910       for(j=3;j-->0;)_of->dither_b[ci*4+j+1]=_of->dither_b[ci*4+j];
2911       _of->dither_a[ci*4]=err;
2912       s-=err;
2913       if(mute>16)r=0;
2914       else{
2915         seed=op_rand(seed);
2916         r=seed*OP_PRNG_GAIN;
2917         seed=op_rand(seed);
2918         r-=seed*OP_PRNG_GAIN;
2919       }
2920       /*Clamp in float out of paranoia that the input will be > 96 dBFS and
2921          wrap if the integer is clamped.*/
2922       si=op_float2int(OP_CLAMP(-32768,s+r,32767));
2923       _dst[_nchannels*i+ci]=(opus_int16)si;
2924       /*Including clipping in the noise shaping is generally disastrous: the
2925          futile effort to restore the clipped energy results in more clipping.
2926         However, small amounts---at the level which could normally be created
2927          by dither and rounding---are harmless and can even reduce clipping
2928          somewhat due to the clipping sometimes reducing the dither + rounding
2929          error.*/
2930       _of->dither_b[ci*4]=mute>16?0:OP_CLAMP(-1.5F,si-s,1.5F);
2931     }
2932     mute++;
2933     if(!silent)mute=0;
2934   }
2935   _of->dither_mute=OP_MIN(mute,65);
2936   _of->dither_seed=seed;
2937   _of->state_channel_count=_nchannels;
2938 }
2939
2940 static int op_float2short_filter(OggOpusFile *_of,void *_dst,int _dst_sz,
2941  op_sample *_src,int _nsamples,int _nchannels){
2942   opus_int16 *dst;
2943   dst=(opus_int16 *)_dst;
2944   if(OP_UNLIKELY(_nsamples*_nchannels>_dst_sz))_nsamples=_dst_sz/_nchannels;
2945   op_shaped_dither16(_of,dst,_src,_nsamples,_nchannels);
2946   return _nsamples;
2947 }
2948
2949 int op_read(OggOpusFile *_of,opus_int16 *_pcm,int _buf_size,int *_li){
2950   return op_read_native_filter(_of,_pcm,_buf_size,op_float2short_filter,_li);
2951 }
2952
2953 int op_read_float(OggOpusFile *_of,float *_pcm,int _buf_size,int *_li){
2954   _of->state_channel_count=0;
2955   return op_read_native(_of,_pcm,_buf_size,_li);
2956 }
2957
2958 /*Matrices for downmixing from the supported channel counts to stereo.
2959   The matrices with 5 or more channels are normalized to a total volume of 2.0,
2960    since most mixes sound too quiet if normalized to 1.0 (as there is generally
2961    little volume in the side/rear channels).*/
2962 static const float OP_STEREO_DOWNMIX[OP_NCHANNELS_MAX-2][OP_NCHANNELS_MAX][2]={
2963   /*3.0*/
2964   {
2965     {0.5858F,0.0F},{0.4142F,0.4142F},{0.0F,0.5858F}
2966   },
2967   /*quadrophonic*/
2968   {
2969     {0.4226F,0.0F},{0.0F,0.4226F},{0.366F,0.2114F},{0.2114F,0.336F}
2970   },
2971   /*5.0*/
2972   {
2973     {0.651F,0.0F},{0.46F,0.46F},{0.0F,0.651F},{0.5636F,0.3254F},
2974     {0.3254F,0.5636F}
2975   },
2976   /*5.1*/
2977   {
2978     {0.529F,0.0F},{0.3741F,0.3741F},{0.0F,0.529F},{0.4582F,0.2645F},
2979     {0.2645F,0.4582F},{0.3741F,0.3741F}
2980   },
2981   /*6.1*/
2982   {
2983     {0.4553F,0.0F},{0.322F,0.322F},{0.0F,0.4553F},{0.3943F,0.2277F},
2984     {0.2277F,0.3943F},{0.2788F,0.2788F},{0.322F,0.322F}
2985   },
2986   /*7.1*/
2987   {
2988     {0.3886F,0.0F},{0.2748F,0.2748F},{0.0F,0.3886F},{0.3366F,0.1943F},
2989     {0.1943F,0.3366F},{0.3366F,0.1943F},{0.1943F,0.3366F},{0.2748F,0.2748F}
2990   }
2991 };
2992
2993 static int op_stereo_filter(OggOpusFile *_of,void *_dst,int _dst_sz,
2994  op_sample *_src,int _nsamples,int _nchannels){
2995   (void)_of;
2996   _nsamples=OP_MIN(_nsamples,_dst_sz>>1);
2997   if(_nchannels==2)memcpy(_dst,_src,_nsamples*2*sizeof(*_src));
2998   else{
2999     float *dst;
3000     int    i;
3001     dst=(float *)_dst;
3002     if(_nchannels==1){
3003       for(i=0;i<_nsamples;i++)dst[2*i+0]=dst[2*i+1]=_src[i];
3004     }
3005     else{
3006       for(i=0;i<_nsamples;i++){
3007         float l;
3008         float r;
3009         int   ci;
3010         l=r=0;
3011         for(ci=0;ci<_nchannels;ci++){
3012           l+=OP_STEREO_DOWNMIX[_nchannels-3][ci][0]*_src[_nchannels*i+ci];
3013           r+=OP_STEREO_DOWNMIX[_nchannels-3][ci][1]*_src[_nchannels*i+ci];
3014         }
3015         dst[2*i+0]=l;
3016         dst[2*i+1]=r;
3017       }
3018     }
3019   }
3020   return _nsamples;
3021 }
3022
3023 static int op_float2short_stereo_filter(OggOpusFile *_of,
3024  void *_dst,int _dst_sz,op_sample *_src,int _nsamples,int _nchannels){
3025   opus_int16 *dst;
3026   dst=(opus_int16 *)_dst;
3027   _nsamples=OP_MIN(_nsamples,_dst_sz>>1);
3028   if(_nchannels==1){
3029     int i;
3030     op_shaped_dither16(_of,dst,_src,_nsamples,1);
3031     for(i=_nsamples;i-->0;)dst[2*i+0]=dst[2*i+1]=dst[i];
3032   }
3033   else{
3034     if(_nchannels>2){
3035       _nsamples=op_stereo_filter(_of,_src,_nsamples*2,
3036        _src,_nsamples,_nchannels);
3037     }
3038     op_shaped_dither16(_of,dst,_src,_nsamples,2);
3039   }
3040   return _nsamples;
3041 }
3042
3043 int op_read_stereo(OggOpusFile *_of,opus_int16 *_pcm,int _buf_size){
3044   return op_read_native_filter(_of,_pcm,_buf_size,
3045    op_float2short_stereo_filter,NULL);
3046 }
3047
3048 int op_read_float_stereo(OggOpusFile *_of,float *_pcm,int _buf_size){
3049   _of->state_channel_count=0;
3050   return op_read_native_filter(_of,_pcm,_buf_size,op_stereo_filter,NULL);
3051 }
3052
3053 #endif