1/************************************************************************
2 * Copyright (C) 2002-2009, Xiph.org Foundation
3 * Copyright (C) 2010, Robin Watts for Pinknoise Productions Ltd
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 *     * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *     * Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following disclaimer
14 * in the documentation and/or other materials provided with the
15 * distribution.
16 *     * Neither the names of the Xiph.org Foundation nor Pinknoise
17 * Productions Ltd nor the names of its contributors may be used to
18 * endorse or promote products derived from this software without
19 * specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ************************************************************************
33
34 function: decode Ogg streams back into raw packets
35
36 note: The CRC code is directly derived from public domain code by
37 Ross Williams (ross@guest.adelaide.edu.au).  See docs/framing.html
38 for details.
39
40 ************************************************************************/
41
42#include <stdlib.h>
43#include <string.h>
44#include "ogg.h"
45#include "misc.h"
46
47
48/* A complete description of Ogg framing exists in docs/framing.html */
49
50/* basic, centralized Ogg memory management based on linked lists of
51   references to refcounted memory buffers.  References and buffers
52   are both recycled.  Buffers are passed around and consumed in
53   reference form. */
54
55static ogg_buffer_state *ogg_buffer_create(void){
56  ogg_buffer_state *bs=_ogg_calloc(1,sizeof(*bs));
57  return bs;
58}
59
60/* destruction is 'lazy'; there may be memory references outstanding,
61   and yanking the buffer state out from underneath would be
62   antisocial.  Dealloc what is currently unused and have
63   _release_one watch for the stragglers to come in.  When they do,
64   finish destruction. */
65
66/* call the helper while holding lock */
67static void _ogg_buffer_destroy(ogg_buffer_state *bs){
68  ogg_buffer *bt;
69  ogg_reference *rt;
70
71  if(bs->shutdown){
72
73    bt=bs->unused_buffers;
74    rt=bs->unused_references;
75
76    while(bt){
77      ogg_buffer *b=bt;
78      bt=b->ptr.next;
79      if(b->data)_ogg_free(b->data);
80      _ogg_free(b);
81    }
82    bs->unused_buffers=0;
83    while(rt){
84      ogg_reference *r=rt;
85      rt=r->next;
86      _ogg_free(r);
87    }
88    bs->unused_references=0;
89
90    if(!bs->outstanding)
91      _ogg_free(bs);
92
93  }
94}
95
96static void ogg_buffer_destroy(ogg_buffer_state *bs){
97  bs->shutdown=1;
98  _ogg_buffer_destroy(bs);
99}
100
101static ogg_buffer *_fetch_buffer(ogg_buffer_state *bs,long bytes){
102  ogg_buffer    *ob;
103  bs->outstanding++;
104
105  /* do we have an unused buffer sitting in the pool? */
106  if(bs->unused_buffers){
107    ob=bs->unused_buffers;
108    bs->unused_buffers=ob->ptr.next;
109
110    /* if the unused buffer is too small, grow it */
111    if(ob->size<bytes){
112      ob->data=_ogg_realloc(ob->data,bytes);
113      ob->size=bytes;
114    }
115  }else{
116    /* allocate a new buffer */
117    ob=_ogg_malloc(sizeof(*ob));
118    ob->data=_ogg_malloc(bytes<16?16:bytes);
119    ob->size=bytes;
120  }
121
122  ob->refcount=1;
123  ob->ptr.owner=bs;
124  return ob;
125}
126
127static ogg_reference *_fetch_ref(ogg_buffer_state *bs){
128  ogg_reference *or;
129  bs->outstanding++;
130
131  /* do we have an unused reference sitting in the pool? */
132  if(bs->unused_references){
133    or=bs->unused_references;
134    bs->unused_references=or->next;
135  }else{
136    /* allocate a new reference */
137    or=_ogg_malloc(sizeof(*or));
138  }
139
140  or->begin=0;
141  or->length=0;
142  or->next=0;
143  return or;
144}
145
146/* fetch a reference pointing to a fresh, initially continguous buffer
147   of at least [bytes] length */
148static ogg_reference *ogg_buffer_alloc(ogg_buffer_state *bs,long bytes){
149  ogg_buffer    *ob=_fetch_buffer(bs,bytes);
150  ogg_reference *or=_fetch_ref(bs);
151  or->buffer=ob;
152  return or;
153}
154
155/* enlarge the data buffer in the current link */
156static void ogg_buffer_realloc(ogg_reference *or,long bytes){
157  ogg_buffer    *ob=or->buffer;
158
159  /* if the unused buffer is too small, grow it */
160  if(ob->size<bytes){
161    ob->data=_ogg_realloc(ob->data,bytes);
162    ob->size=bytes;
163  }
164}
165
166static void _ogg_buffer_mark_one(ogg_reference *or){
167  or->buffer->refcount++;
168}
169
170/* increase the refcount of the buffers to which the reference points */
171static void ogg_buffer_mark(ogg_reference *or){
172  while(or){
173    _ogg_buffer_mark_one(or);
174    or=or->next;
175  }
176}
177
178/* duplicate a reference (pointing to the same actual buffer memory)
179   and increment buffer refcount.  If the desired segment is zero
180   length, a zero length ref is returned. */
181static ogg_reference *ogg_buffer_sub(ogg_reference *or,long length){
182  ogg_reference *ret=0,*head=0;
183
184  /* duplicate the reference chain; increment refcounts */
185  while(or && length){
186    ogg_reference *temp=_fetch_ref(or->buffer->ptr.owner);
187    if(head)
188      head->next=temp;
189    else
190      ret=temp;
191    head=temp;
192    head->buffer=or->buffer;
193    head->begin=or->begin;
194    head->length=length;
195    if(head->length>or->length)
196      head->length=or->length;
197
198    length-=head->length;
199    or=or->next;
200  }
201
202  ogg_buffer_mark(ret);
203  return ret;
204}
205
206ogg_reference *ogg_buffer_dup(ogg_reference *or){
207  ogg_reference *ret=0,*head=0;
208  /* duplicate the reference chain; increment refcounts */
209  while(or){
210    ogg_reference *temp=_fetch_ref(or->buffer->ptr.owner);
211    if(head)
212      head->next=temp;
213    else
214      ret=temp;
215    head=temp;
216    head->buffer=or->buffer;
217    head->begin=or->begin;
218    head->length=or->length;
219    or=or->next;
220  }
221
222  ogg_buffer_mark(ret);
223  return ret;
224}
225
226/* split a reference into two references; 'return' is a reference to
227   the buffer preceeding pos and 'head'/'tail' are the buffer past the
228   split.  If pos is at or past the end of the passed in segment,
229   'head/tail' are NULL */
230static ogg_reference *ogg_buffer_split(ogg_reference **tail,
231                                ogg_reference **head,long pos){
232
233  /* walk past any preceeding fragments to one of:
234     a) the exact boundary that seps two fragments
235     b) the fragment that needs split somewhere in the middle */
236  ogg_reference *ret=*tail;
237  ogg_reference *or=*tail;
238
239  while(or && pos>or->length){
240    pos-=or->length;
241    or=or->next;
242  }
243
244  if(!or || pos==0){
245
246    return 0;
247
248  }else{
249
250    if(pos>=or->length){
251      /* exact split, or off the end? */
252      if(or->next){
253
254        /* a split */
255        *tail=or->next;
256        or->next=0;
257
258      }else{
259
260        /* off or at the end */
261        *tail=*head=0;
262
263      }
264    }else{
265
266      /* split within a fragment */
267      long lengthA=pos;
268      long beginB=or->begin+pos;
269      long lengthB=or->length-pos;
270
271      /* make a new reference to tail the second piece */
272      *tail=_fetch_ref(or->buffer->ptr.owner);
273
274      (*tail)->buffer=or->buffer;
275      (*tail)->begin=beginB;
276      (*tail)->length=lengthB;
277      (*tail)->next=or->next;
278      _ogg_buffer_mark_one(*tail);
279      if(head && or==*head)*head=*tail;
280
281      /* update the first piece */
282      or->next=0;
283      or->length=lengthA;
284
285    }
286  }
287  return ret;
288}
289
290static void ogg_buffer_release_one(ogg_reference *or){
291  ogg_buffer *ob=or->buffer;
292  ogg_buffer_state *bs=ob->ptr.owner;
293
294  ob->refcount--;
295  if(ob->refcount==0){
296    bs->outstanding--; /* for the returned buffer */
297    ob->ptr.next=bs->unused_buffers;
298    bs->unused_buffers=ob;
299  }
300
301  bs->outstanding--; /* for the returned reference */
302  or->next=bs->unused_references;
303  bs->unused_references=or;
304
305  _ogg_buffer_destroy(bs); /* lazy cleanup (if needed) */
306
307}
308
309/* release the references, decrease the refcounts of buffers to which
310   they point, release any buffers with a refcount that drops to zero */
311static void ogg_buffer_release(ogg_reference *or){
312  while(or){
313    ogg_reference *next=or->next;
314    ogg_buffer_release_one(or);
315    or=next;
316  }
317}
318
319static ogg_reference *ogg_buffer_pretruncate(ogg_reference *or,long pos){
320  /* release preceeding fragments we don't want */
321  while(or && pos>=or->length){
322    ogg_reference *next=or->next;
323    pos-=or->length;
324    ogg_buffer_release_one(or);
325    or=next;
326  }
327  if (or) {
328    or->begin+=pos;
329    or->length-=pos;
330  }
331  return or;
332}
333
334static ogg_reference *ogg_buffer_walk(ogg_reference *or){
335  if(!or)return NULL;
336  while(or->next){
337    or=or->next;
338  }
339  return(or);
340}
341
342/* *head is appended to the front end (head) of *tail; both continue to
343   be valid pointers, with *tail at the tail and *head at the head */
344static ogg_reference *ogg_buffer_cat(ogg_reference *tail, ogg_reference *head){
345  if(!tail)return head;
346
347  while(tail->next){
348    tail=tail->next;
349  }
350  tail->next=head;
351  return ogg_buffer_walk(head);
352}
353
354static void _positionB(oggbyte_buffer *b,int pos){
355  if(pos<b->pos){
356    /* start at beginning, scan forward */
357    b->ref=b->baseref;
358    b->pos=0;
359    b->end=b->pos+b->ref->length;
360    b->ptr=b->ref->buffer->data+b->ref->begin;
361  }
362}
363
364static void _positionF(oggbyte_buffer *b,int pos){
365  /* scan forward for position */
366  while(pos>=b->end){
367    /* just seek forward */
368    b->pos+=b->ref->length;
369    b->ref=b->ref->next;
370    b->end=b->ref->length+b->pos;
371    b->ptr=b->ref->buffer->data+b->ref->begin;
372  }
373}
374
375static int oggbyte_init(oggbyte_buffer *b,ogg_reference *or){
376  memset(b,0,sizeof(*b));
377  if(or){
378    b->ref=b->baseref=or;
379    b->pos=0;
380    b->end=b->ref->length;
381    b->ptr=b->ref->buffer->data+b->ref->begin;
382    return 0;
383  }else
384    return -1;
385}
386
387static void oggbyte_set4(oggbyte_buffer *b,ogg_uint32_t val,int pos){
388  int i;
389  _positionB(b,pos);
390  for(i=0;i<4;i++){
391    _positionF(b,pos);
392    b->ptr[pos-b->pos]=val;
393    val>>=8;
394    ++pos;
395  }
396}
397
398static unsigned char oggbyte_read1(oggbyte_buffer *b,int pos){
399  _positionB(b,pos);
400  _positionF(b,pos);
401  return b->ptr[pos-b->pos];
402}
403
404static ogg_uint32_t oggbyte_read4(oggbyte_buffer *b,int pos){
405  ogg_uint32_t ret;
406  _positionB(b,pos);
407  _positionF(b,pos);
408  ret=b->ptr[pos-b->pos];
409  _positionF(b,++pos);
410  ret|=b->ptr[pos-b->pos]<<8;
411  _positionF(b,++pos);
412  ret|=b->ptr[pos-b->pos]<<16;
413  _positionF(b,++pos);
414  ret|=b->ptr[pos-b->pos]<<24;
415  return ret;
416}
417
418static ogg_int64_t oggbyte_read8(oggbyte_buffer *b,int pos){
419  ogg_int64_t ret;
420  unsigned char t[7];
421  int i;
422  _positionB(b,pos);
423  for(i=0;i<7;i++){
424    _positionF(b,pos);
425    t[i]=b->ptr[pos++ -b->pos];
426  }
427
428  _positionF(b,pos);
429  ret=b->ptr[pos-b->pos];
430
431  for(i=6;i>=0;--i)
432    ret= ret<<8 | t[i];
433
434  return ret;
435}
436
437/* Now we get to the actual framing code */
438
439int ogg_page_version(ogg_page *og){
440  oggbyte_buffer ob;
441  if(oggbyte_init(&ob,og->header))return -1;
442  return oggbyte_read1(&ob,4);
443}
444
445int ogg_page_continued(ogg_page *og){
446  oggbyte_buffer ob;
447  if(oggbyte_init(&ob,og->header))return -1;
448  return oggbyte_read1(&ob,5)&0x01;
449}
450
451int ogg_page_bos(ogg_page *og){
452  oggbyte_buffer ob;
453  if(oggbyte_init(&ob,og->header))return -1;
454  return oggbyte_read1(&ob,5)&0x02;
455}
456
457int ogg_page_eos(ogg_page *og){
458  oggbyte_buffer ob;
459  if(oggbyte_init(&ob,og->header))return -1;
460  return oggbyte_read1(&ob,5)&0x04;
461}
462
463ogg_int64_t ogg_page_granulepos(ogg_page *og){
464  oggbyte_buffer ob;
465  if(oggbyte_init(&ob,og->header))return -1;
466  return oggbyte_read8(&ob,6);
467}
468
469ogg_uint32_t ogg_page_serialno(ogg_page *og){
470  oggbyte_buffer ob;
471  if(oggbyte_init(&ob,og->header)) return 0xffffffffUL;
472  return oggbyte_read4(&ob,14);
473}
474
475ogg_uint32_t ogg_page_pageno(ogg_page *og){
476  oggbyte_buffer ob;
477  if(oggbyte_init(&ob,og->header))return 0xffffffffUL;
478  return oggbyte_read4(&ob,18);
479}
480
481/* returns the number of packets that are completed on this page (if
482   the leading packet is begun on a previous page, but ends on this
483   page, it's counted */
484
485/* NOTE:
486If a page consists of a packet begun on a previous page, and a new
487packet begun (but not completed) on this page, the return will be:
488  ogg_page_packets(page)   ==1,
489  ogg_page_continued(page) !=0
490
491If a page happens to be a single packet that was begun on a
492previous page, and spans to the next page (in the case of a three or
493more page packet), the return will be:
494  ogg_page_packets(page)   ==0,
495  ogg_page_continued(page) !=0
496*/
497
498int ogg_page_packets(ogg_page *og){
499  int i;
500  int n;
501  int count=0;
502  oggbyte_buffer ob;
503  oggbyte_init(&ob,og->header);
504
505  n=oggbyte_read1(&ob,26);
506  for(i=0;i<n;i++)
507    if(oggbyte_read1(&ob,27+i)<255)count++;
508  return(count);
509}
510
511/* Static CRC calculation table.  See older code in CVS for dead
512   run-time initialization code. */
513
514ogg_uint32_t crc_lookup[256]={
515  0x00000000,0x04c11db7,0x09823b6e,0x0d4326d9,
516  0x130476dc,0x17c56b6b,0x1a864db2,0x1e475005,
517  0x2608edb8,0x22c9f00f,0x2f8ad6d6,0x2b4bcb61,
518  0x350c9b64,0x31cd86d3,0x3c8ea00a,0x384fbdbd,
519  0x4c11db70,0x48d0c6c7,0x4593e01e,0x4152fda9,
520  0x5f15adac,0x5bd4b01b,0x569796c2,0x52568b75,
521  0x6a1936c8,0x6ed82b7f,0x639b0da6,0x675a1011,
522  0x791d4014,0x7ddc5da3,0x709f7b7a,0x745e66cd,
523  0x9823b6e0,0x9ce2ab57,0x91a18d8e,0x95609039,
524  0x8b27c03c,0x8fe6dd8b,0x82a5fb52,0x8664e6e5,
525  0xbe2b5b58,0xbaea46ef,0xb7a96036,0xb3687d81,
526  0xad2f2d84,0xa9ee3033,0xa4ad16ea,0xa06c0b5d,
527  0xd4326d90,0xd0f37027,0xddb056fe,0xd9714b49,
528  0xc7361b4c,0xc3f706fb,0xceb42022,0xca753d95,
529  0xf23a8028,0xf6fb9d9f,0xfbb8bb46,0xff79a6f1,
530  0xe13ef6f4,0xe5ffeb43,0xe8bccd9a,0xec7dd02d,
531  0x34867077,0x30476dc0,0x3d044b19,0x39c556ae,
532  0x278206ab,0x23431b1c,0x2e003dc5,0x2ac12072,
533  0x128e9dcf,0x164f8078,0x1b0ca6a1,0x1fcdbb16,
534  0x018aeb13,0x054bf6a4,0x0808d07d,0x0cc9cdca,
535  0x7897ab07,0x7c56b6b0,0x71159069,0x75d48dde,
536  0x6b93dddb,0x6f52c06c,0x6211e6b5,0x66d0fb02,
537  0x5e9f46bf,0x5a5e5b08,0x571d7dd1,0x53dc6066,
538  0x4d9b3063,0x495a2dd4,0x44190b0d,0x40d816ba,
539  0xaca5c697,0xa864db20,0xa527fdf9,0xa1e6e04e,
540  0xbfa1b04b,0xbb60adfc,0xb6238b25,0xb2e29692,
541  0x8aad2b2f,0x8e6c3698,0x832f1041,0x87ee0df6,
542  0x99a95df3,0x9d684044,0x902b669d,0x94ea7b2a,
543  0xe0b41de7,0xe4750050,0xe9362689,0xedf73b3e,
544  0xf3b06b3b,0xf771768c,0xfa325055,0xfef34de2,
545  0xc6bcf05f,0xc27dede8,0xcf3ecb31,0xcbffd686,
546  0xd5b88683,0xd1799b34,0xdc3abded,0xd8fba05a,
547  0x690ce0ee,0x6dcdfd59,0x608edb80,0x644fc637,
548  0x7a089632,0x7ec98b85,0x738aad5c,0x774bb0eb,
549  0x4f040d56,0x4bc510e1,0x46863638,0x42472b8f,
550  0x5c007b8a,0x58c1663d,0x558240e4,0x51435d53,
551  0x251d3b9e,0x21dc2629,0x2c9f00f0,0x285e1d47,
552  0x36194d42,0x32d850f5,0x3f9b762c,0x3b5a6b9b,
553  0x0315d626,0x07d4cb91,0x0a97ed48,0x0e56f0ff,
554  0x1011a0fa,0x14d0bd4d,0x19939b94,0x1d528623,
555  0xf12f560e,0xf5ee4bb9,0xf8ad6d60,0xfc6c70d7,
556  0xe22b20d2,0xe6ea3d65,0xeba91bbc,0xef68060b,
557  0xd727bbb6,0xd3e6a601,0xdea580d8,0xda649d6f,
558  0xc423cd6a,0xc0e2d0dd,0xcda1f604,0xc960ebb3,
559  0xbd3e8d7e,0xb9ff90c9,0xb4bcb610,0xb07daba7,
560  0xae3afba2,0xaafbe615,0xa7b8c0cc,0xa379dd7b,
561  0x9b3660c6,0x9ff77d71,0x92b45ba8,0x9675461f,
562  0x8832161a,0x8cf30bad,0x81b02d74,0x857130c3,
563  0x5d8a9099,0x594b8d2e,0x5408abf7,0x50c9b640,
564  0x4e8ee645,0x4a4ffbf2,0x470cdd2b,0x43cdc09c,
565  0x7b827d21,0x7f436096,0x7200464f,0x76c15bf8,
566  0x68860bfd,0x6c47164a,0x61043093,0x65c52d24,
567  0x119b4be9,0x155a565e,0x18197087,0x1cd86d30,
568  0x029f3d35,0x065e2082,0x0b1d065b,0x0fdc1bec,
569  0x3793a651,0x3352bbe6,0x3e119d3f,0x3ad08088,
570  0x2497d08d,0x2056cd3a,0x2d15ebe3,0x29d4f654,
571  0xc5a92679,0xc1683bce,0xcc2b1d17,0xc8ea00a0,
572  0xd6ad50a5,0xd26c4d12,0xdf2f6bcb,0xdbee767c,
573  0xe3a1cbc1,0xe760d676,0xea23f0af,0xeee2ed18,
574  0xf0a5bd1d,0xf464a0aa,0xf9278673,0xfde69bc4,
575  0x89b8fd09,0x8d79e0be,0x803ac667,0x84fbdbd0,
576  0x9abc8bd5,0x9e7d9662,0x933eb0bb,0x97ffad0c,
577  0xafb010b1,0xab710d06,0xa6322bdf,0xa2f33668,
578  0xbcb4666d,0xb8757bda,0xb5365d03,0xb1f740b4};
579
580void ogg_sync_init(ogg_sync_state *oy){
581  memset(oy,0,sizeof(*oy));
582  oy->bufferpool=ogg_buffer_create();
583}
584
585ogg_sync_state *ogg_sync_create(void){
586  ogg_sync_state *oy=_ogg_calloc(1,sizeof(*oy));
587  memset(oy,0,sizeof(*oy));
588  oy->bufferpool=ogg_buffer_create();
589  return oy;
590}
591
592int ogg_sync_clear(ogg_sync_state *oy){
593  if(oy){
594    ogg_sync_reset(oy);
595    ogg_buffer_destroy(oy->bufferpool);
596    memset(oy,0,sizeof(*oy));
597  }
598  return OGG_SUCCESS;
599}
600
601int ogg_sync_destroy(ogg_sync_state *oy){
602  if(oy){
603    ogg_sync_reset(oy);
604    ogg_buffer_destroy(oy->bufferpool);
605    memset(oy,0,sizeof(*oy));
606    _ogg_free(oy);
607  }
608  return OGG_SUCCESS;
609}
610
611unsigned char *ogg_sync_bufferin(ogg_sync_state *oy, long bytes){
612
613  /* [allocate and] expose a buffer for data submission.
614
615     If there is no head fragment
616       allocate one and expose it
617     else
618       if the current head fragment has sufficient unused space
619         expose it
620       else
621         if the current head fragment is unused
622           resize and expose it
623         else
624           allocate new fragment and expose it
625  */
626
627  /* base case; fifo uninitialized */
628  if(!oy->fifo_head){
629    oy->fifo_head=oy->fifo_tail=ogg_buffer_alloc(oy->bufferpool,bytes);
630    return oy->fifo_head->buffer->data;
631  }
632
633  /* space left in current fragment case */
634  if(oy->fifo_head->buffer->size-
635     oy->fifo_head->length-
636     oy->fifo_head->begin >= bytes)
637    return oy->fifo_head->buffer->data+
638      oy->fifo_head->length+oy->fifo_head->begin;
639
640  /* current fragment is unused, but too small */
641  if(!oy->fifo_head->length){
642    ogg_buffer_realloc(oy->fifo_head,bytes);
643    return oy->fifo_head->buffer->data+oy->fifo_head->begin;
644  }
645
646  /* current fragment used/full; get new fragment */
647  {
648    ogg_reference *new=ogg_buffer_alloc(oy->bufferpool,bytes);
649    oy->fifo_head->next=new;
650    oy->fifo_head=new;
651  }
652  return oy->fifo_head->buffer->data;
653}
654
655int ogg_sync_wrote(ogg_sync_state *oy, long bytes){
656  if(!oy->fifo_head)return OGG_EINVAL;
657  if(oy->fifo_head->buffer->size-oy->fifo_head->length-oy->fifo_head->begin <
658     bytes)return OGG_EINVAL;
659  oy->fifo_head->length+=bytes;
660  oy->fifo_fill+=bytes;
661  return OGG_SUCCESS;
662}
663
664#ifndef ONLY_C
665ogg_uint32_t _checksum(ogg_reference *or, int bytes);
666#else
667static ogg_uint32_t _checksum(ogg_reference *or, int bytes){
668  ogg_uint32_t crc_reg=0;
669  int j,post;
670
671  while(or){
672    unsigned char *data=or->buffer->data+or->begin;
673    post=(bytes<or->length?bytes:or->length);
674    for(j=0;j<post;++j)
675      crc_reg=(crc_reg<<8)^crc_lookup[((crc_reg >> 24)&0xff)^data[j]];
676    bytes-=j;
677    or=or->next;
678  }
679
680  return crc_reg;
681}
682#endif
683
684/* sync the stream.  This is meant to be useful for finding page
685   boundaries.
686
687   return values for this:
688  -n) skipped n bytes
689   0) page not ready; more data (no bytes skipped)
690   n) page synced at current location; page length n bytes
691
692*/
693
694long ogg_sync_pageseek(ogg_sync_state *oy,ogg_page *og){
695  oggbyte_buffer page;
696  long           bytes,ret=0;
697
698  ogg_page_release(og);
699
700  bytes=oy->fifo_fill;
701  oggbyte_init(&page,oy->fifo_tail);
702
703  if(oy->headerbytes==0){
704    if(bytes<27)goto sync_out; /* not enough for even a minimal header */
705
706    /* verify capture pattern */
707    if(oggbyte_read1(&page,0)!=(int)'O' ||
708       oggbyte_read1(&page,1)!=(int)'g' ||
709       oggbyte_read1(&page,2)!=(int)'g' ||
710       oggbyte_read1(&page,3)!=(int)'S'    ) goto sync_fail;
711
712    oy->headerbytes=oggbyte_read1(&page,26)+27;
713  }
714  if(bytes<oy->headerbytes)goto sync_out; /* not enough for header +
715                                             seg table */
716  if(oy->bodybytes==0){
717    int i;
718    /* count up body length in the segment table */
719    for(i=0;i<oy->headerbytes-27;i++)
720      oy->bodybytes+=oggbyte_read1(&page,27+i);
721  }
722
723  if(oy->bodybytes+oy->headerbytes>bytes)goto sync_out;
724
725  /* we have what appears to be a complete page; last test: verify
726     checksum */
727  {
728    ogg_uint32_t chksum=oggbyte_read4(&page,22);
729    oggbyte_set4(&page,0,22);
730
731    /* Compare checksums; memory continues to be common access */
732    if(chksum!=_checksum(oy->fifo_tail,oy->bodybytes+oy->headerbytes)){
733
734      /* D'oh.  Mismatch! Corrupt page (or miscapture and not a page
735         at all). replace the computed checksum with the one actually
736         read in; remember all the memory is common access */
737
738      oggbyte_set4(&page,chksum,22);
739      goto sync_fail;
740    }
741    oggbyte_set4(&page,chksum,22);
742  }
743
744  /* We have a page.  Set up page return. */
745  if(og){
746    /* set up page output */
747    og->header=ogg_buffer_split(&oy->fifo_tail,&oy->fifo_head,oy->headerbytes);
748    og->header_len=oy->headerbytes;
749    og->body=ogg_buffer_split(&oy->fifo_tail,&oy->fifo_head,oy->bodybytes);
750    og->body_len=oy->bodybytes;
751  }else{
752    /* simply advance */
753    oy->fifo_tail=
754      ogg_buffer_pretruncate(oy->fifo_tail,oy->headerbytes+oy->bodybytes);
755    if(!oy->fifo_tail)oy->fifo_head=0;
756  }
757
758  ret=oy->headerbytes+oy->bodybytes;
759  oy->unsynced=0;
760  oy->headerbytes=0;
761  oy->bodybytes=0;
762  oy->fifo_fill-=ret;
763
764  return ret;
765
766 sync_fail:
767
768  oy->headerbytes=0;
769  oy->bodybytes=0;
770  oy->fifo_tail=ogg_buffer_pretruncate(oy->fifo_tail,1);
771  ret--;
772
773  /* search forward through fragments for possible capture */
774  while(oy->fifo_tail){
775    /* invariant: fifo_cursor points to a position in fifo_tail */
776    unsigned char *now=oy->fifo_tail->buffer->data+oy->fifo_tail->begin;
777    unsigned char *next=memchr(now, 'O', oy->fifo_tail->length);
778
779    if(next){
780      /* possible capture in this segment */
781      long bytes=next-now;
782      oy->fifo_tail=ogg_buffer_pretruncate(oy->fifo_tail,bytes);
783      ret-=bytes;
784      break;
785    }else{
786      /* no capture.  advance to next segment */
787      long bytes=oy->fifo_tail->length;
788      ret-=bytes;
789      oy->fifo_tail=ogg_buffer_pretruncate(oy->fifo_tail,bytes);
790    }
791  }
792  if(!oy->fifo_tail)oy->fifo_head=0;
793  oy->fifo_fill+=ret;
794
795 sync_out:
796  return ret;
797}
798
799/* sync the stream and get a page.  Keep trying until we find a page.
800   Supress 'sync errors' after reporting the first.
801
802   return values:
803   OGG_HOLE) recapture (hole in data)
804          0) need more data
805          1) page returned
806
807   Returns pointers into buffered data; invalidated by next call to
808   _stream, _clear, _init, or _buffer */
809
810int ogg_sync_pageout(ogg_sync_state *oy, ogg_page *og){
811
812  /* all we need to do is verify a page at the head of the stream
813     buffer.  If it doesn't verify, we look for the next potential
814     frame */
815
816  while(1){
817    long ret=ogg_sync_pageseek(oy,og);
818    if(ret>0){
819      /* have a page */
820      return 1;
821    }
822    if(ret==0){
823      /* need more data */
824      return 0;
825    }
826
827    /* head did not start a synced page... skipped some bytes */
828    if(!oy->unsynced){
829      oy->unsynced=1;
830      return OGG_HOLE;
831    }
832
833    /* loop. keep looking */
834
835  }
836}
837
838/* clear things to an initial state.  Good to call, eg, before seeking */
839int ogg_sync_reset(ogg_sync_state *oy){
840
841  ogg_buffer_release(oy->fifo_tail);
842  oy->fifo_tail=0;
843  oy->fifo_head=0;
844  oy->fifo_fill=0;
845
846  oy->unsynced=0;
847  oy->headerbytes=0;
848  oy->bodybytes=0;
849  return OGG_SUCCESS;
850}
851
852void ogg_stream_init(ogg_stream_state *os, int serialno){
853  memset(os, 0, sizeof(*os));
854  os->serialno=serialno;
855  os->pageno=-1;
856}
857
858ogg_stream_state *ogg_stream_create(int serialno){
859  ogg_stream_state *os=_ogg_calloc(1,sizeof(*os));
860  os->serialno=serialno;
861  os->pageno=-1;
862  return os;
863}
864
865int ogg_stream_clear(ogg_stream_state *os){
866  if(os){
867    ogg_buffer_release(os->header_tail);
868    ogg_buffer_release(os->body_tail);
869    memset(os,0,sizeof(*os));
870  }
871  return OGG_SUCCESS;
872}
873
874int ogg_stream_destroy(ogg_stream_state *os){
875  if(os){
876    ogg_buffer_release(os->header_tail);
877    ogg_buffer_release(os->body_tail);
878    memset(os,0,sizeof(*os));
879    _ogg_free(os);
880  }
881  return OGG_SUCCESS;
882}
883
884
885#define FINFLAG 0x80000000UL
886#define FINMASK 0x7fffffffUL
887
888static void _next_lace(oggbyte_buffer *ob,ogg_stream_state *os){
889  /* search ahead one lace */
890  os->body_fill_next=0;
891  while(os->laceptr<os->lacing_fill){
892    int val=oggbyte_read1(ob,27+os->laceptr++);
893    os->body_fill_next+=val;
894    if(val<255){
895      os->body_fill_next|=FINFLAG;
896      os->clearflag=1;
897      break;
898    }
899  }
900}
901
902static void _span_queued_page(ogg_stream_state *os){
903  while( !(os->body_fill&FINFLAG) ){
904
905    if(!os->header_tail)break;
906
907    /* first flush out preceeding page header (if any).  Body is
908       flushed as it's consumed, so that's not done here. */
909
910    if(os->lacing_fill>=0)
911      os->header_tail=ogg_buffer_pretruncate(os->header_tail,
912                                             os->lacing_fill+27);
913    os->lacing_fill=0;
914    os->laceptr=0;
915    os->clearflag=0;
916
917    if(!os->header_tail){
918      os->header_head=0;
919      break;
920    }else{
921
922      /* process/prepare next page, if any */
923
924      long pageno;
925      oggbyte_buffer ob;
926      ogg_page og;               /* only for parsing header values */
927      og.header=os->header_tail; /* only for parsing header values */
928      pageno=ogg_page_pageno(&og);
929
930      oggbyte_init(&ob,os->header_tail);
931      os->lacing_fill=oggbyte_read1(&ob,26);
932
933      /* are we in sequence? */
934      if(pageno!=os->pageno){
935        if(os->pageno==-1) /* indicates seek or reset */
936          os->holeflag=1;  /* set for internal use */
937        else
938          os->holeflag=2;  /* set for external reporting */
939
940        os->body_tail=ogg_buffer_pretruncate(os->body_tail,
941                                             os->body_fill);
942        if(os->body_tail==0)os->body_head=0;
943        os->body_fill=0;
944
945      }
946
947      if(ogg_page_continued(&og)){
948        if(os->body_fill==0){
949          /* continued packet, but no preceeding data to continue */
950          /* dump the first partial packet on the page */
951          _next_lace(&ob,os);
952          os->body_tail=
953            ogg_buffer_pretruncate(os->body_tail,os->body_fill_next&FINMASK);
954          if(os->body_tail==0)os->body_head=0;
955          /* set span flag */
956          if(!os->spanflag && !os->holeflag)os->spanflag=2;
957        }
958      }else{
959        if(os->body_fill>0){
960          /* preceeding data to continue, but not a continued page */
961          /* dump body_fill */
962          os->body_tail=ogg_buffer_pretruncate(os->body_tail,
963                                               os->body_fill);
964          if(os->body_tail==0)os->body_head=0;
965          os->body_fill=0;
966
967          /* set espan flag */
968          if(!os->spanflag && !os->holeflag)os->spanflag=2;
969        }
970      }
971
972      if(os->laceptr<os->lacing_fill){
973        os->granulepos=ogg_page_granulepos(&og);
974
975        /* get current packet size & flag */
976        _next_lace(&ob,os);
977        os->body_fill+=os->body_fill_next; /* addition handles the flag fine;
978                                             unsigned on purpose */
979        /* ...and next packet size & flag */
980        _next_lace(&ob,os);
981
982      }
983
984      os->pageno=pageno+1;
985      os->e_o_s=ogg_page_eos(&og);
986      os->b_o_s=ogg_page_bos(&og);
987
988    }
989  }
990}
991
992/* add the incoming page to the stream state; we decompose the page
993   into packet segments here as well. */
994
995int ogg_stream_pagein(ogg_stream_state *os, ogg_page *og){
996
997  int serialno=ogg_page_serialno(og);
998  int version=ogg_page_version(og);
999
1000  /* check the serial number */
1001  if(serialno!=os->serialno){
1002    //ogg_page_release(og);
1003    return OGG_ESERIAL;
1004  }
1005  if(version>0){
1006    //ogg_page_release(og);
1007    return OGG_EVERSION;
1008  }
1009
1010  /* add to fifos */
1011  if(!os->body_tail){
1012    os->body_tail=og->body;
1013    os->body_head=ogg_buffer_walk(og->body);
1014  }else{
1015    os->body_head=ogg_buffer_cat(os->body_head,og->body);
1016  }
1017  if(!os->header_tail){
1018    os->header_tail=og->header;
1019    os->header_head=ogg_buffer_walk(og->header);
1020    os->lacing_fill=-27;
1021  }else{
1022    os->header_head=ogg_buffer_cat(os->header_head,og->header);
1023  }
1024
1025  memset(og,0,sizeof(*og));
1026  return OGG_SUCCESS;
1027}
1028
1029int ogg_stream_reset(ogg_stream_state *os){
1030
1031  ogg_buffer_release(os->header_tail);
1032  ogg_buffer_release(os->body_tail);
1033  os->header_tail=os->header_head=0;
1034  os->body_tail=os->body_head=0;
1035
1036  os->e_o_s=0;
1037  os->b_o_s=0;
1038  os->pageno=-1;
1039  os->packetno=0;
1040  os->granulepos=0;
1041
1042  os->body_fill=0;
1043  os->lacing_fill=0;
1044
1045  os->holeflag=0;
1046  os->spanflag=0;
1047  os->clearflag=0;
1048  os->laceptr=0;
1049  os->body_fill_next=0;
1050
1051  return OGG_SUCCESS;
1052}
1053
1054int ogg_stream_reset_serialno(ogg_stream_state *os,int serialno){
1055  ogg_stream_reset(os);
1056  os->serialno=serialno;
1057  return OGG_SUCCESS;
1058}
1059
1060static int _packetout(ogg_stream_state *os,ogg_packet *op,int adv){
1061
1062  ogg_packet_release(op);
1063  _span_queued_page(os);
1064
1065  if(os->holeflag){
1066    int temp=os->holeflag;
1067    if(os->clearflag)
1068      os->holeflag=0;
1069    else
1070      os->holeflag=1;
1071    if(temp==2){
1072      os->packetno++;
1073      return OGG_HOLE;
1074    }
1075  }
1076  if(os->spanflag){
1077    int temp=os->spanflag;
1078    if(os->clearflag)
1079      os->spanflag=0;
1080    else
1081      os->spanflag=1;
1082    if(temp==2){
1083      os->packetno++;
1084      return OGG_SPAN;
1085    }
1086  }
1087
1088  if(!(os->body_fill&FINFLAG)) return 0;
1089  if(!op && !adv)return 1; /* just using peek as an inexpensive way
1090                               to ask if there's a whole packet
1091                               waiting */
1092  if(op){
1093    op->b_o_s=os->b_o_s;
1094    if(os->e_o_s && os->body_fill_next==0)
1095      op->e_o_s=os->e_o_s;
1096    else
1097      op->e_o_s=0;
1098    if( (os->body_fill&FINFLAG) && !(os->body_fill_next&FINFLAG) )
1099      op->granulepos=os->granulepos;
1100    else
1101      op->granulepos=-1;
1102    op->packetno=os->packetno;
1103  }
1104
1105  if(adv){
1106    oggbyte_buffer ob;
1107    oggbyte_init(&ob,os->header_tail);
1108
1109    /* split the body contents off */
1110    if(op){
1111      op->packet=ogg_buffer_split(&os->body_tail,&os->body_head,
1112				  os->body_fill&FINMASK);
1113      op->bytes=os->body_fill&FINMASK;
1114    }else{
1115      os->body_tail=ogg_buffer_pretruncate(os->body_tail,
1116					   os->body_fill&FINMASK);
1117      if(os->body_tail==0)os->body_head=0;
1118    }
1119
1120    /* update lacing pointers */
1121    os->body_fill=os->body_fill_next;
1122    _next_lace(&ob,os);
1123  }else{
1124    if(op){
1125      op->packet=ogg_buffer_sub(os->body_tail,os->body_fill&FINMASK);
1126      op->bytes=os->body_fill&FINMASK;
1127    }
1128  }
1129
1130  if(adv){
1131    os->packetno++;
1132    os->b_o_s=0;
1133  }
1134
1135  return 1;
1136}
1137
1138int ogg_stream_packetout(ogg_stream_state *os,ogg_packet *op){
1139  return _packetout(os,op,1);
1140}
1141
1142int ogg_stream_packetpeek(ogg_stream_state *os,ogg_packet *op){
1143  return _packetout(os,op,0);
1144}
1145
1146int ogg_packet_release(ogg_packet *op) {
1147  if(op){
1148    ogg_buffer_release(op->packet);
1149    memset(op, 0, sizeof(*op));
1150  }
1151  return OGG_SUCCESS;
1152}
1153
1154int ogg_page_release(ogg_page *og) {
1155  if(og){
1156    ogg_buffer_release(og->header);
1157    ogg_buffer_release(og->body);
1158    memset(og, 0, sizeof(*og));
1159  }
1160  return OGG_SUCCESS;
1161}
1162
1163void ogg_page_dup(ogg_page *dup,ogg_page *orig){
1164  dup->header_len=orig->header_len;
1165  dup->body_len=orig->body_len;
1166  dup->header=ogg_buffer_dup(orig->header);
1167  dup->body=ogg_buffer_dup(orig->body);
1168}
1169
1170