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