Tremor/framing.c

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