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