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     while(bt){
  57       ogg_buffer *b=bt;
  58       bt=b->ptr.next;
  59       if(b->data)_ogg_free(b->data);
  60       _ogg_free(b);
  61     }
  62     bs->unused_buffers=0;
  63     while(rt){
  64       ogg_reference *r=rt;
  65       rt=r->next;
  66       _ogg_free(r);
  67     }
  68     bs->unused_references=0;
  69
  70     if(!bs->outstanding)
  71       _ogg_free(bs);
  72
  73   }
  74 }
  75
  76 static void ogg_buffer_destroy(ogg_buffer_state *bs){
  77   bs->shutdown=1;
  78   _ogg_buffer_destroy(bs);
  79 }
  80
  81 static ogg_buffer *_fetch_buffer(ogg_buffer_state *bs,long bytes){
  82   ogg_buffer    *ob;
  83   bs->outstanding++;
  84
  85   /* do we have an unused buffer sitting in the pool? */
  86   if(bs->unused_buffers){
  87     ob=bs->unused_buffers;
  88     bs->unused_buffers=ob->ptr.next;
  89
  90     /* if the unused buffer is too small, grow it */
  91     if(ob->size<bytes){
  92       ob->data=_ogg_realloc(ob->data,bytes);
  93       ob->size=bytes;
  94     }
  95   }else{
  96     /* allocate a new buffer */
  97     ob=_ogg_malloc(sizeof(*ob));
  98     ob->data=_ogg_malloc(bytes<16?16:bytes);
  99     ob->size=bytes;
 100   }
 101
 102   ob->refcount=1;
 103   ob->ptr.owner=bs;
 104   return ob;
 105 }
 106
 107 static ogg_reference *_fetch_ref(ogg_buffer_state *bs){
 108   ogg_reference *or;
 109   bs->outstanding++;
 110
 111   /* do we have an unused reference sitting in the pool? */
 112   if(bs->unused_references){
 113     or=bs->unused_references;
 114     bs->unused_references=or->next;
 115   }else{
 116     /* allocate a new reference */
 117     or=_ogg_malloc(sizeof(*or));
 118   }
 119
 120   or->begin=0;
 121   or->length=0;
 122   or->next=0;
 123   return or;
 124 }
 125
 126 /* fetch a reference pointing to a fresh, initially continguous buffer
 127    of at least [bytes] length */
 128 static ogg_reference *ogg_buffer_alloc(ogg_buffer_state *bs,long bytes){
 129   ogg_buffer    *ob=_fetch_buffer(bs,bytes);
 130   ogg_reference *or=_fetch_ref(bs);
 131   or->buffer=ob;
 132   return or;
 133 }
 134
 135 /* enlarge the data buffer in the current link */
 136 static void ogg_buffer_realloc(ogg_reference *or,long bytes){
 137   ogg_buffer    *ob=or->buffer;
 138
 139   /* if the unused buffer is too small, grow it */
 140   if(ob->size<bytes){
 141     ob->data=_ogg_realloc(ob->data,bytes);
 142     ob->size=bytes;
 143   }
 144 }
 145
 146 static void _ogg_buffer_mark_one(ogg_reference *or){
 147   or->buffer->refcount++;
 148 }
 149
 150 /* increase the refcount of the buffers to which the reference points */
 151 static void ogg_buffer_mark(ogg_reference *or){
 152   while(or){
 153     _ogg_buffer_mark_one(or);
 154     or=or->next;
 155   }
 156 }
 157
 158 /* duplicate a reference (pointing to the same actual buffer memory)
 159    and increment buffer refcount.  If the desired segment begins out
 160    of range, NULL is returned; if the desired segment is simply zero
 161    length, a zero length ref is returned.  Partial range overlap
 162    returns the overlap of the ranges */
 163 static ogg_reference *ogg_buffer_sub(ogg_reference *or,long begin,long length){
 164   ogg_reference *ret=0,*head=0;
 165
 166   /* walk past any preceeding fragments we don't want */
 167   while(or && begin>=or->length){
 168     begin-=or->length;
 169     or=or->next;
 170   }
 171
 172   /* duplicate the reference chain; increment refcounts */
 173   while(or && length){
 174     ogg_reference *temp=_fetch_ref(or->buffer->ptr.owner);
 175     if(head)
 176       head->next=temp;
 177     else
 178       ret=temp;
 179     head=temp;
 180     head->buffer=or->buffer;
 181     head->begin=or->begin+begin;
 182     head->length=length;
 183     if(head->length>or->length-begin)
 184       head->length=or->length-begin;
 185
 186     begin=0;
 187     length-=head->length;
 188     or=or->next;
 189   }
 190
 191   ogg_buffer_mark(ret);
 192   return ret;
 193 }
 194
 195 ogg_reference *ogg_buffer_dup(ogg_reference *or){
 196   ogg_reference *ret=0,*head=0;
 197   /* duplicate the reference chain; increment refcounts */
 198   while(or){
 199     ogg_reference *temp=_fetch_ref(or->buffer->ptr.owner);
 200     if(head)
 201       head->next=temp;
 202     else
 203       ret=temp;
 204     head=temp;
 205     head->buffer=or->buffer;
 206     head->begin=or->begin;
 207     head->length=or->length;
 208     or=or->next;
 209   }
 210
 211   ogg_buffer_mark(ret);
 212   return ret;
 213 }
 214
 215 /* split a reference into two references; 'return' is a reference to
 216    the buffer preceeding pos and 'head'/'tail' are the buffer past the
 217    split.  If pos is at or past the end of the passed in segment,
 218    'head/tail' are NULL */
 219 static ogg_reference *ogg_buffer_split(ogg_reference **tail,
 220                                 ogg_reference **head,long pos){
 221
 222   /* walk past any preceeding fragments to one of:
 223      a) the exact boundary that seps two fragments
 224      b) the fragment that needs split somewhere in the middle */
 225   ogg_reference *ret=*tail;
 226   ogg_reference *or=*tail;
 227
 228   while(or && pos>or->length){
 229     pos-=or->length;
 230     or=or->next;
 231   }
 232
 233   if(!or || pos==0){
 234
 235     return 0;
 236
 237   }else{
 238
 239     if(pos>=or->length){
 240       /* exact split, or off the end? */
 241       if(or->next){
 242
 243         /* a split */
 244         *tail=or->next;
 245         or->next=0;
 246
 247       }else{
 248
 249         /* off or at the end */
 250         *tail=*head=0;
 251
 252       }
 253     }else{
 254
 255       /* split within a fragment */
 256       long lengthA=pos;
 257       long beginB=or->begin+pos;
 258       long lengthB=or->length-pos;
 259
 260       /* make a new reference to tail the second piece */
 261       *tail=_fetch_ref(or->buffer->ptr.owner);
 262
 263       (*tail)->buffer=or->buffer;
 264       (*tail)->begin=beginB;
 265       (*tail)->length=lengthB;
 266       (*tail)->next=or->next;
 267       _ogg_buffer_mark_one(*tail);
 268       if(head && or==*head)*head=*tail;
 269
 270       /* update the first piece */
 271       or->next=0;
 272       or->length=lengthA;
 273
 274     }
 275   }
 276   return ret;
 277 }
 278
 279 static void ogg_buffer_release_one(ogg_reference *or){
 280   ogg_buffer *ob=or->buffer;
 281   ogg_buffer_state *bs=ob->ptr.owner;
 282
 283   ob->refcount--;
 284   if(ob->refcount==0){
 285     bs->outstanding--; /* for the returned buffer */
 286     ob->ptr.next=bs->unused_buffers;
 287     bs->unused_buffers=ob;
 288   }
 289
 290   bs->outstanding--; /* for the returned reference */
 291   or->next=bs->unused_references;
 292   bs->unused_references=or;
 293
 294   _ogg_buffer_destroy(bs); /* lazy cleanup (if needed) */
 295
 296 }
 297
 298 /* release the references, decrease the refcounts of buffers to which
 299    they point, release any buffers with a refcount that drops to zero */
 300 static void ogg_buffer_release(ogg_reference *or){
 301   while(or){
 302     ogg_reference *next=or->next;
 303     ogg_buffer_release_one(or);
 304     or=next;
 305   }
 306 }
 307
 308 static ogg_reference *ogg_buffer_pretruncate(ogg_reference *or,long pos){
 309   /* release preceeding fragments we don't want */
 310   while(or && pos>=or->length){
 311     ogg_reference *next=or->next;
 312     pos-=or->length;
 313     ogg_buffer_release_one(or);
 314     or=next;
 315   }
 316   if (or) {
 317     or->begin+=pos;
 318     or->length-=pos;
 319   }
 320   return or;
 321 }
 322
 323 static ogg_reference *ogg_buffer_walk(ogg_reference *or){
 324   if(!or)return NULL;
 325   while(or->next){
 326     or=or->next;
 327   }
 328   return(or);
 329 }
 330
 331 /* *head is appended to the front end (head) of *tail; both continue to
 332    be valid pointers, with *tail at the tail and *head at the head */
 333 static ogg_reference *ogg_buffer_cat(ogg_reference *tail, ogg_reference *head){
 334   if(!tail)return head;
 335
 336   while(tail->next){
 337     tail=tail->next;
 338   }
 339   tail->next=head;
 340   return ogg_buffer_walk(head);
 341 }
 342
 343 static void _positionB(oggbyte_buffer *b,int pos){
 344   if(pos<b->pos){
 345     /* start at beginning, scan forward */
 346     b->ref=b->baseref;
 347     b->pos=0;
 348     b->end=b->pos+b->ref->length;
 349     b->ptr=b->ref->buffer->data+b->ref->begin;
 350   }
 351 }
 352
 353 static void _positionF(oggbyte_buffer *b,int pos){
 354   /* scan forward for position */
 355   while(pos>=b->end){
 356     /* just seek forward */
 357     b->pos+=b->ref->length;
 358     b->ref=b->ref->next;
 359     b->end=b->ref->length+b->pos;
 360     b->ptr=b->ref->buffer->data+b->ref->begin;
 361   }
 362 }
 363
 364 static int oggbyte_init(oggbyte_buffer *b,ogg_reference *or){
 365   memset(b,0,sizeof(*b));
 366   if(or){
 367     b->ref=b->baseref=or;
 368     b->pos=0;
 369     b->end=b->ref->length;
 370     b->ptr=b->ref->buffer->data+b->ref->begin;
 371     return 0;
 372   }else
 373     return -1;
 374 }
 375
 376 static void oggbyte_set4(oggbyte_buffer *b,ogg_uint32_t val,int pos){
 377   int i;
 378   _positionB(b,pos);
 379   for(i=0;i<4;i++){
 380     _positionF(b,pos);
 381     b->ptr[pos-b->pos]=val;
 382     val>>=8;
 383     ++pos;
 384   }
 385 }
 386
 387 static unsigned char oggbyte_read1(oggbyte_buffer *b,int pos){
 388   _positionB(b,pos);
 389   _positionF(b,pos);
 390   return b->ptr[pos-b->pos];
 391 }
 392
 393 static ogg_uint32_t oggbyte_read4(oggbyte_buffer *b,int pos){
 394   ogg_uint32_t ret;
 395   _positionB(b,pos);
 396   _positionF(b,pos);
 397   ret=b->ptr[pos-b->pos];
 398   _positionF(b,++pos);
 399   ret|=b->ptr[pos-b->pos]<<8;
 400   _positionF(b,++pos);
 401   ret|=b->ptr[pos-b->pos]<<16;
 402   _positionF(b,++pos);
 403   ret|=b->ptr[pos-b->pos]<<24;
 404   return ret;
 405 }
 406
 407 static ogg_int64_t oggbyte_read8(oggbyte_buffer *b,int pos){
 408   ogg_int64_t ret;
 409   unsigned char t[7];
 410   int i;
 411   _positionB(b,pos);
 412   for(i=0;i<7;i++){
 413     _positionF(b,pos);
 414     t[i]=b->ptr[pos++ -b->pos];
 415   }
 416
 417   _positionF(b,pos);
 418   ret=b->ptr[pos-b->pos];
 419
 420   for(i=6;i>=0;--i)
 421     ret= ret<<8 | t[i];
 422
 423   return ret;
 424 }
 425
 426 /* Now we get to the actual framing code */
 427
 428 int ogg_page_version(ogg_page *og){
 429   oggbyte_buffer ob;
 430   oggbyte_init(&ob,og->header);
 431   return oggbyte_read1(&ob,4);
 432 }
 433
 434 int ogg_page_continued(ogg_page *og){
 435   oggbyte_buffer ob;
 436   oggbyte_init(&ob,og->header);
 437   return oggbyte_read1(&ob,5)&0x01;
 438 }
 439
 440 int ogg_page_bos(ogg_page *og){
 441   oggbyte_buffer ob;
 442   oggbyte_init(&ob,og->header);
 443   return oggbyte_read1(&ob,5)&0x02;
 444 }
 445
 446 int ogg_page_eos(ogg_page *og){
 447   oggbyte_buffer ob;
 448   oggbyte_init(&ob,og->header);
 449   return oggbyte_read1(&ob,5)&0x04;
 450 }
 451
 452 ogg_int64_t ogg_page_granulepos(ogg_page *og){
 453   oggbyte_buffer ob;
 454   oggbyte_init(&ob,og->header);
 455   return oggbyte_read8(&ob,6);
 456 }
 457
 458 ogg_uint32_t ogg_page_serialno(ogg_page *og){
 459   oggbyte_buffer ob;
 460   oggbyte_init(&ob,og->header);
 461   return oggbyte_read4(&ob,14);
 462 }
 463
 464 ogg_uint32_t ogg_page_pageno(ogg_page *og){
 465   oggbyte_buffer ob;
 466   oggbyte_init(&ob,og->header);
 467   return oggbyte_read4(&ob,18);
 468 }
 469
 470 /* returns the number of packets that are completed on this page (if
 471    the leading packet is begun on a previous page, but ends on this
 472    page, it's counted */
 473
 474 /* NOTE:
 475 If a page consists of a packet begun on a previous page, and a new
 476 packet begun (but not completed) on this page, the return will be:
 477   ogg_page_packets(page)   ==1,
 478   ogg_page_continued(page) !=0
 479
 480 If a page happens to be a single packet that was begun on a
 481 previous page, and spans to the next page (in the case of a three or
 482 more page packet), the return will be:
 483   ogg_page_packets(page)   ==0,
 484   ogg_page_continued(page) !=0
 485 */
 486
 487 int ogg_page_packets(ogg_page *og){
 488   int i;
 489   int n;
 490   int count=0;
 491   oggbyte_buffer ob;
 492   oggbyte_init(&ob,og->header);
 493
 494   n=oggbyte_read1(&ob,26);
 495   for(i=0;i<n;i++)
 496     if(oggbyte_read1(&ob,27+i)<255)count++;
 497   return(count);
 498 }
 499
 500 /* Static CRC calculation table.  See older code in CVS for dead
 501    run-time initialization code. */
 502
 503 static ogg_uint32_t crc_lookup[256]={
 504   0x00000000,0x04c11db7,0x09823b6e,0x0d4326d9,
 505   0x130476dc,0x17c56b6b,0x1a864db2,0x1e475005,
 506   0x2608edb8,0x22c9f00f,0x2f8ad6d6,0x2b4bcb61,
 507   0x350c9b64,0x31cd86d3,0x3c8ea00a,0x384fbdbd,
 508   0x4c11db70,0x48d0c6c7,0x4593e01e,0x4152fda9,
 509   0x5f15adac,0x5bd4b01b,0x569796c2,0x52568b75,
 510   0x6a1936c8,0x6ed82b7f,0x639b0da6,0x675a1011,
 511   0x791d4014,0x7ddc5da3,0x709f7b7a,0x745e66cd,
 512   0x9823b6e0,0x9ce2ab57,0x91a18d8e,0x95609039,
 513   0x8b27c03c,0x8fe6dd8b,0x82a5fb52,0x8664e6e5,
 514   0xbe2b5b58,0xbaea46ef,0xb7a96036,0xb3687d81,
 515   0xad2f2d84,0xa9ee3033,0xa4ad16ea,0xa06c0b5d,
 516   0xd4326d90,0xd0f37027,0xddb056fe,0xd9714b49,
 517   0xc7361b4c,0xc3f706fb,0xceb42022,0xca753d95,
 518   0xf23a8028,0xf6fb9d9f,0xfbb8bb46,0xff79a6f1,
 519   0xe13ef6f4,0xe5ffeb43,0xe8bccd9a,0xec7dd02d,
 520   0x34867077,0x30476dc0,0x3d044b19,0x39c556ae,
 521   0x278206ab,0x23431b1c,0x2e003dc5,0x2ac12072,
 522   0x128e9dcf,0x164f8078,0x1b0ca6a1,0x1fcdbb16,
 523   0x018aeb13,0x054bf6a4,0x0808d07d,0x0cc9cdca,
 524   0x7897ab07,0x7c56b6b0,0x71159069,0x75d48dde,
 525   0x6b93dddb,0x6f52c06c,0x6211e6b5,0x66d0fb02,
 526   0x5e9f46bf,0x5a5e5b08,0x571d7dd1,0x53dc6066,
 527   0x4d9b3063,0x495a2dd4,0x44190b0d,0x40d816ba,
 528   0xaca5c697,0xa864db20,0xa527fdf9,0xa1e6e04e,
 529   0xbfa1b04b,0xbb60adfc,0xb6238b25,0xb2e29692,
 530   0x8aad2b2f,0x8e6c3698,0x832f1041,0x87ee0df6,
 531   0x99a95df3,0x9d684044,0x902b669d,0x94ea7b2a,
 532   0xe0b41de7,0xe4750050,0xe9362689,0xedf73b3e,
 533   0xf3b06b3b,0xf771768c,0xfa325055,0xfef34de2,
 534   0xc6bcf05f,0xc27dede8,0xcf3ecb31,0xcbffd686,
 535   0xd5b88683,0xd1799b34,0xdc3abded,0xd8fba05a,
 536   0x690ce0ee,0x6dcdfd59,0x608edb80,0x644fc637,
 537   0x7a089632,0x7ec98b85,0x738aad5c,0x774bb0eb,
 538   0x4f040d56,0x4bc510e1,0x46863638,0x42472b8f,
 539   0x5c007b8a,0x58c1663d,0x558240e4,0x51435d53,
 540   0x251d3b9e,0x21dc2629,0x2c9f00f0,0x285e1d47,
 541   0x36194d42,0x32d850f5,0x3f9b762c,0x3b5a6b9b,
 542   0x0315d626,0x07d4cb91,0x0a97ed48,0x0e56f0ff,
 543   0x1011a0fa,0x14d0bd4d,0x19939b94,0x1d528623,
 544   0xf12f560e,0xf5ee4bb9,0xf8ad6d60,0xfc6c70d7,
 545   0xe22b20d2,0xe6ea3d65,0xeba91bbc,0xef68060b,
 546   0xd727bbb6,0xd3e6a601,0xdea580d8,0xda649d6f,
 547   0xc423cd6a,0xc0e2d0dd,0xcda1f604,0xc960ebb3,
 548   0xbd3e8d7e,0xb9ff90c9,0xb4bcb610,0xb07daba7,
 549   0xae3afba2,0xaafbe615,0xa7b8c0cc,0xa379dd7b,
 550   0x9b3660c6,0x9ff77d71,0x92b45ba8,0x9675461f,
 551   0x8832161a,0x8cf30bad,0x81b02d74,0x857130c3,
 552   0x5d8a9099,0x594b8d2e,0x5408abf7,0x50c9b640,
 553   0x4e8ee645,0x4a4ffbf2,0x470cdd2b,0x43cdc09c,
 554   0x7b827d21,0x7f436096,0x7200464f,0x76c15bf8,
 555   0x68860bfd,0x6c47164a,0x61043093,0x65c52d24,
 556   0x119b4be9,0x155a565e,0x18197087,0x1cd86d30,
 557   0x029f3d35,0x065e2082,0x0b1d065b,0x0fdc1bec,
 558   0x3793a651,0x3352bbe6,0x3e119d3f,0x3ad08088,
 559   0x2497d08d,0x2056cd3a,0x2d15ebe3,0x29d4f654,
 560   0xc5a92679,0xc1683bce,0xcc2b1d17,0xc8ea00a0,
 561   0xd6ad50a5,0xd26c4d12,0xdf2f6bcb,0xdbee767c,
 562   0xe3a1cbc1,0xe760d676,0xea23f0af,0xeee2ed18,
 563   0xf0a5bd1d,0xf464a0aa,0xf9278673,0xfde69bc4,
 564   0x89b8fd09,0x8d79e0be,0x803ac667,0x84fbdbd0,
 565   0x9abc8bd5,0x9e7d9662,0x933eb0bb,0x97ffad0c,
 566   0xafb010b1,0xab710d06,0xa6322bdf,0xa2f33668,
 567   0xbcb4666d,0xb8757bda,0xb5365d03,0xb1f740b4};
 568
 569 ogg_sync_state *ogg_sync_create(void){
 570   ogg_sync_state *oy=_ogg_calloc(1,sizeof(*oy));
 571   memset(oy,0,sizeof(*oy));
 572   oy->bufferpool=ogg_buffer_create();
 573   return oy;
 574 }
 575
 576 int ogg_sync_destroy(ogg_sync_state *oy){
 577   if(oy){
 578     ogg_sync_reset(oy);
 579     ogg_buffer_destroy(oy->bufferpool);
 580     memset(oy,0,sizeof(*oy));
 581     _ogg_free(oy);
 582   }
 583   return OGG_SUCCESS;
 584 }
 585
 586 unsigned char *ogg_sync_bufferin(ogg_sync_state *oy, long bytes){
 587
 588   /* [allocate and] expose a buffer for data submission.
 589
 590      If there is no head fragment
 591        allocate one and expose it
 592      else
 593        if the current head fragment has sufficient unused space
 594          expose it
 595        else
 596          if the current head fragment is unused
 597            resize and expose it
 598          else
 599            allocate new fragment and expose it
 600   */
 601
 602   /* base case; fifo uninitialized */
 603   if(!oy->fifo_head){
 604     oy->fifo_head=oy->fifo_tail=ogg_buffer_alloc(oy->bufferpool,bytes);
 605     return oy->fifo_head->buffer->data;
 606   }
 607
 608   /* space left in current fragment case */
 609   if(oy->fifo_head->buffer->size-
 610      oy->fifo_head->length-
 611      oy->fifo_head->begin >= bytes)
 612     return oy->fifo_head->buffer->data+
 613       oy->fifo_head->length+oy->fifo_head->begin;
 614
 615   /* current fragment is unused, but too small */
 616   if(!oy->fifo_head->length){
 617     ogg_buffer_realloc(oy->fifo_head,bytes);
 618     return oy->fifo_head->buffer->data+oy->fifo_head->begin;
 619   }
 620
 621   /* current fragment used/full; get new fragment */
 622   {
 623     ogg_reference *new=ogg_buffer_alloc(oy->bufferpool,bytes);
 624     oy->fifo_head->next=new;
 625     oy->fifo_head=new;
 626   }
 627   return oy->fifo_head->buffer->data;
 628 }
 629
 630 int ogg_sync_wrote(ogg_sync_state *oy, long bytes){
 631   if(!oy->fifo_head)return OGG_EINVAL;
 632   if(oy->fifo_head->buffer->size-oy->fifo_head->length-oy->fifo_head->begin <
 633      bytes)return OGG_EINVAL;
 634   oy->fifo_head->length+=bytes;
 635   oy->fifo_fill+=bytes;
 636   return OGG_SUCCESS;
 637 }
 638
 639 static ogg_uint32_t _checksum(ogg_reference *or, int bytes){
 640   ogg_uint32_t crc_reg=0;
 641   int j,post;
 642
 643   while(or){
 644     unsigned char *data=or->buffer->data+or->begin;
 645     post=(bytes<or->length?bytes:or->length);
 646     for(j=0;j<post;++j)
 647       crc_reg=(crc_reg<<8)^crc_lookup[((crc_reg >> 24)&0xff)^data[j]];
 648     bytes-=j;
 649     or=or->next;
 650   }
 651
 652   return crc_reg;
 653 }
 654
 655
 656 /* sync the stream.  This is meant to be useful for finding page
 657    boundaries.
 658
 659    return values for this:
 660   -n) skipped n bytes
 661    0) page not ready; more data (no bytes skipped)
 662    n) page synced at current location; page length n bytes
 663
 664 */
 665
 666 long ogg_sync_pageseek(ogg_sync_state *oy,ogg_page *og){
 667   oggbyte_buffer page;
 668   long           bytes,ret=0;
 669
 670   ogg_page_release(og);
 671
 672   bytes=oy->fifo_fill;
 673   oggbyte_init(&page,oy->fifo_tail);
 674
 675   if(oy->headerbytes==0){
 676     if(bytes<27)goto sync_out; /* not enough for even a minimal header */
 677
 678     /* verify capture pattern */
 679     if(oggbyte_read1(&page,0)!=(int)'O' ||
 680        oggbyte_read1(&page,1)!=(int)'g' ||
 681        oggbyte_read1(&page,2)!=(int)'g' ||
 682        oggbyte_read1(&page,3)!=(int)'S'    ) goto sync_fail;
 683
 684     oy->headerbytes=oggbyte_read1(&page,26)+27;
 685   }
 686   if(bytes<oy->headerbytes)goto sync_out; /* not enough for header +
 687                                              seg table */
 688   if(oy->bodybytes==0){
 689     int i;
 690     /* count up body length in the segment table */
 691     for(i=0;i<oy->headerbytes-27;i++)
 692       oy->bodybytes+=oggbyte_read1(&page,27+i);
 693   }
 694
 695   if(oy->bodybytes+oy->headerbytes>bytes)goto sync_out;
 696
 697   /* we have what appears to be a complete page; last test: verify
 698      checksum */
 699   {
 700     ogg_uint32_t chksum=oggbyte_read4(&page,22);
 701     oggbyte_set4(&page,0,22);
 702
 703     /* Compare checksums; memory continues to be common access */
 704     if(chksum!=_checksum(oy->fifo_tail,oy->bodybytes+oy->headerbytes)){
 705
 706       /* D'oh.  Mismatch! Corrupt page (or miscapture and not a page
 707          at all). replace the computed checksum with the one actually
 708          read in; remember all the memory is common access */
 709
 710       oggbyte_set4(&page,chksum,22);
 711       goto sync_fail;
 712     }
 713     oggbyte_set4(&page,chksum,22);
 714   }
 715
 716   /* We have a page.  Set up page return. */
 717   if(og){
 718     /* set up page output */
 719     og->header=ogg_buffer_split(&oy->fifo_tail,&oy->fifo_head,oy->headerbytes);
 720     og->header_len=oy->headerbytes;
 721     og->body=ogg_buffer_split(&oy->fifo_tail,&oy->fifo_head,oy->bodybytes);
 722     og->body_len=oy->bodybytes;
 723   }else{
 724     /* simply advance */
 725     oy->fifo_tail=
 726       ogg_buffer_pretruncate(oy->fifo_tail,oy->headerbytes+oy->bodybytes);
 727     if(!oy->fifo_tail)oy->fifo_head=0;
 728   }
 729
 730   ret=oy->headerbytes+oy->bodybytes;
 731   oy->unsynced=0;
 732   oy->headerbytes=0;
 733   oy->bodybytes=0;
 734   oy->fifo_fill-=ret;
 735
 736   return ret;
 737
 738  sync_fail:
 739
 740   oy->headerbytes=0;
 741   oy->bodybytes=0;
 742   oy->fifo_tail=ogg_buffer_pretruncate(oy->fifo_tail,1);
 743   ret--;
 744
 745   /* search forward through fragments for possible capture */
 746   while(oy->fifo_tail){
 747     /* invariant: fifo_cursor points to a position in fifo_tail */
 748     unsigned char *now=oy->fifo_tail->buffer->data+oy->fifo_tail->begin;
 749     unsigned char *next=memchr(now, 'O', oy->fifo_tail->length);
 750
 751     if(next){
 752       /* possible capture in this segment */
 753       long bytes=next-now;
 754       oy->fifo_tail=ogg_buffer_pretruncate(oy->fifo_tail,bytes);
 755       ret-=bytes;
 756       break;
 757     }else{
 758       /* no capture.  advance to next segment */
 759       long bytes=oy->fifo_tail->length;
 760       ret-=bytes;
 761       oy->fifo_tail=ogg_buffer_pretruncate(oy->fifo_tail,bytes);
 762     }
 763   }
 764   if(!oy->fifo_tail)oy->fifo_head=0;
 765   oy->fifo_fill+=ret;
 766
 767  sync_out:
 768   return ret;
 769 }
 770
 771 /* sync the stream and get a page.  Keep trying until we find a page.
 772    Supress 'sync errors' after reporting the first.
 773
 774    return values:
 775    OGG_HOLE) recapture (hole in data)
 776           0) need more data
 777           1) page returned
 778
 779    Returns pointers into buffered data; invalidated by next call to
 780    _stream, _clear, _init, or _buffer */
 781
 782 int ogg_sync_pageout(ogg_sync_state *oy, ogg_page *og){
 783
 784   /* all we need to do is verify a page at the head of the stream
 785      buffer.  If it doesn't verify, we look for the next potential
 786      frame */
 787
 788   while(1){
 789     long ret=ogg_sync_pageseek(oy,og);
 790     if(ret>0){
 791       /* have a page */
 792       return 1;
 793     }
 794     if(ret==0){
 795       /* need more data */
 796       return 0;
 797     }
 798
 799     /* head did not start a synced page... skipped some bytes */
 800     if(!oy->unsynced){
 801       oy->unsynced=1;
 802       return OGG_HOLE;
 803     }
 804
 805     /* loop. keep looking */
 806
 807   }
 808 }
 809
 810 /* clear things to an initial state.  Good to call, eg, before seeking */
 811 int ogg_sync_reset(ogg_sync_state *oy){
 812
 813   ogg_buffer_release(oy->fifo_tail);
 814   oy->fifo_tail=0;
 815   oy->fifo_head=0;
 816   oy->fifo_fill=0;
 817
 818   oy->unsynced=0;
 819   oy->headerbytes=0;
 820   oy->bodybytes=0;
 821   return OGG_SUCCESS;
 822 }
 823
 824 ogg_stream_state *ogg_stream_create(int serialno){
 825   ogg_stream_state *os=_ogg_calloc(1,sizeof(*os));
 826   os->serialno=serialno;
 827   os->pageno=-1;
 828   return os;
 829 }
 830
 831 int ogg_stream_destroy(ogg_stream_state *os){
 832   if(os){
 833     ogg_buffer_release(os->header_tail);
 834     ogg_buffer_release(os->body_tail);
 835     memset(os,0,sizeof(*os));
 836     _ogg_free(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