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 STATICIRAM_NOT_MDCT ogg_reference *_fetch_ref(ogg_buffer_state *bs)
 108     ICODE_ATTR_TREMOR_NOT_MDCT;
 109 STATICIRAM_NOT_MDCT 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 STATICIRAM_NOT_MDCT void _span_queued_page(ogg_stream_state *os)
 793     ICODE_ATTR_TREMOR_NOT_MDCT;
 794 STATICIRAM_NOT_MDCT void _span_queued_page(ogg_stream_state *os){
 795   while( !(os->body_fill&FINFLAG) ){
 796
 797     if(!os->header_tail)break;
 798
 799     /* first flush out preceeding page header (if any).  Body is
 800        flushed as it's consumed, so that's not done here. */
 801
 802     if(os->lacing_fill>=0)
 803       os->header_tail=ogg_buffer_pretruncate(os->header_tail,
 804                                              os->lacing_fill+27);
 805     os->lacing_fill=0;
 806     os->laceptr=0;
 807     os->clearflag=0;
 808
 809     if(!os->header_tail){
 810       os->header_head=0;
 811       break;
 812     }else{
 813
 814       /* process/prepare next page, if any */
 815
 816       long pageno;
 817       oggbyte_buffer ob;
 818       ogg_page og;               /* only for parsing header values */
 819       og.header=os->header_tail; /* only for parsing header values */
 820       pageno=ogg_page_pageno(&og);
 821
 822       oggbyte_init(&ob,os->header_tail);
 823       os->lacing_fill=oggbyte_read1(&ob,26);
 824
 825       /* are we in sequence? */
 826       if(pageno!=os->pageno){
 827         if(os->pageno==-1) /* indicates seek or reset */
 828           os->holeflag=1;  /* set for internal use */
 829         else
 830           os->holeflag=2;  /* set for external reporting */
 831
 832         os->body_tail=ogg_buffer_pretruncate(os->body_tail,
 833                                              os->body_fill);
 834         if(os->body_tail==0)os->body_head=0;
 835         os->body_fill=0;
 836
 837       }
 838
 839       if(ogg_page_continued(&og)){
 840         if(os->body_fill==0){
 841           /* continued packet, but no preceeding data to continue */
 842           /* dump the first partial packet on the page */
 843           _next_lace(&ob,os);
 844           os->body_tail=
 845             ogg_buffer_pretruncate(os->body_tail,os->body_fill_next&FINMASK);
 846           if(os->body_tail==0)os->body_head=0;
 847           /* set span flag */
 848           if(!os->spanflag && !os->holeflag)os->spanflag=2;
 849         }
 850       }else{
 851         if(os->body_fill>0){
 852           /* preceeding data to continue, but not a continued page */
 853           /* dump body_fill */
 854           os->body_tail=ogg_buffer_pretruncate(os->body_tail,
 855                                                os->body_fill);
 856           if(os->body_tail==0)os->body_head=0;
 857           os->body_fill=0;
 858
 859           /* set espan flag */
 860           if(!os->spanflag && !os->holeflag)os->spanflag=2;
 861         }
 862       }
 863
 864       if(os->laceptr<os->lacing_fill){
 865         os->granulepos=ogg_page_granulepos(&og);
 866
 867         /* get current packet size & flag */
 868         _next_lace(&ob,os);
 869         os->body_fill+=os->body_fill_next; /* addition handles the flag fine;
 870                                              unsigned on purpose */
 871         /* ...and next packet size & flag */
 872         _next_lace(&ob,os);
 873
 874       }
 875
 876       os->pageno=pageno+1;
 877       os->e_o_s=ogg_page_eos(&og);
 878       os->b_o_s=ogg_page_bos(&og);
 879
 880     }
 881   }
 882 }
 883
 884 /* add the incoming page to the stream state; we decompose the page
 885    into packet segments here as well. */
 886
 887 int ogg_stream_pagein(ogg_stream_state *os, ogg_page *og){
 888
 889   int serialno=ogg_page_serialno(og);
 890   int version=ogg_page_version(og);
 891
 892   /* check the serial number */
 893   if(serialno!=os->serialno){
 894     ogg_page_release(og);
 895     return OGG_ESERIAL;
 896   }
 897   if(version>0){
 898     ogg_page_release(og);
 899     return OGG_EVERSION;
 900   }
 901
 902   /* add to fifos */
 903   if(!os->body_tail){
 904     os->body_tail=og->body;
 905     os->body_head=ogg_buffer_walk(og->body);
 906   }else{
 907     os->body_head=ogg_buffer_cat(os->body_head,og->body);
 908   }
 909   if(!os->header_tail){
 910     os->header_tail=og->header;
 911     os->header_head=ogg_buffer_walk(og->header);
 912     os->lacing_fill=-27;
 913   }else{
 914     os->header_head=ogg_buffer_cat(os->header_head,og->header);
 915   }
 916
 917   memset(og,0,sizeof(*og));
 918   return OGG_SUCCESS;
 919 }
 920
 921 int ogg_stream_reset(ogg_stream_state *os){
 922
 923   ogg_buffer_release(os->header_tail);
 924   ogg_buffer_release(os->body_tail);
 925   os->header_tail=os->header_head=0;
 926   os->body_tail=os->body_head=0;
 927
 928   os->e_o_s=0;
 929   os->b_o_s=0;
 930   os->pageno=-1;
 931   os->packetno=0;
 932   os->granulepos=0;
 933
 934   os->body_fill=0;
 935   os->lacing_fill=0;
 936
 937   os->holeflag=0;
 938   os->spanflag=0;
 939   os->clearflag=0;
 940   os->laceptr=0;
 941   os->body_fill_next=0;
 942
 943   return OGG_SUCCESS;
 944 }
 945
 946 int ogg_stream_reset_serialno(ogg_stream_state *os,int serialno){
 947   ogg_stream_reset(os);
 948   os->serialno=serialno;
 949   return OGG_SUCCESS;
 950 }
 951
 952 STATICIRAM_NOT_MDCT int _packetout(ogg_stream_state *os,ogg_packet *op,int adv)
 953     ICODE_ATTR_TREMOR_NOT_MDCT;
 954 STATICIRAM_NOT_MDCT int _packetout(ogg_stream_state *os,ogg_packet *op,int adv){
 955
 956   ogg_packet_release(op);
 957   _span_queued_page(os);
 958
 959   if(os->holeflag){
 960     int temp=os->holeflag;
 961     if(os->clearflag)
 962       os->holeflag=0;
 963     else
 964       os->holeflag=1;
 965     if(temp==2){
 966       os->packetno++;
 967       return OGG_HOLE;
 968     }
 969   }
 970   if(os->spanflag){
 971     int temp=os->spanflag;
 972     if(os->clearflag)
 973       os->spanflag=0;
 974     else
 975       os->spanflag=1;
 976     if(temp==2){
 977       os->packetno++;
 978       return OGG_SPAN;
 979     }
 980   }
 981
 982   if(!(os->body_fill&FINFLAG)) return 0;
 983   if(!op && !adv)return 1; /* just using peek as an inexpensive way
 984                                to ask if there's a whole packet
 985                                waiting */
 986   if(op){
 987     op->b_o_s=os->b_o_s;
 988     if(os->e_o_s && os->body_fill_next==0)
 989       op->e_o_s=os->e_o_s;
 990     else
 991       op->e_o_s=0;
 992     if( (os->body_fill&FINFLAG) && !(os->body_fill_next&FINFLAG) )
 993       op->granulepos=os->granulepos;
 994     else
 995       op->granulepos=-1;
 996     op->packetno=os->packetno;
 997   }
 998
 999   if(adv){
1000     oggbyte_buffer ob;
1001     oggbyte_init(&ob,os->header_tail);
1002
1003     /* split the body contents off */
1004     if(op){
1005       op->packet=ogg_buffer_split(&os->body_tail,&os->body_head,
1006                   os->body_fill&FINMASK);
1007       op->bytes=os->body_fill&FINMASK;
1008     }else{
1009       os->body_tail=ogg_buffer_pretruncate(os->body_tail,
1010                        os->body_fill&FINMASK);
1011       if(os->body_tail==0)os->body_head=0;
1012     }
1013
1014     /* update lacing pointers */
1015     os->body_fill=os->body_fill_next;
1016     _next_lace(&ob,os);
1017   }else{
1018     if(op){
1019       op->packet=ogg_buffer_sub(os->body_tail,0,os->body_fill&FINMASK);
1020       op->bytes=os->body_fill&FINMASK;
1021     }
1022   }
1023
1024   if(adv){
1025     os->packetno++;
1026     os->b_o_s=0;
1027   }
1028
1029   return 1;
1030 }
1031
1032 int ogg_stream_packetout(ogg_stream_state *os,ogg_packet *op)
1033     ICODE_ATTR_TREMOR_NOT_MDCT;
1034 int ogg_stream_packetout(ogg_stream_state *os,ogg_packet *op){
1035   return _packetout(os,op,1);
1036 }
1037
1038 int ogg_stream_packetpeek(ogg_stream_state *os,ogg_packet *op)
1039     ICODE_ATTR_TREMOR_NOT_MDCT;
1040 int ogg_stream_packetpeek(ogg_stream_state *os,ogg_packet *op){
1041   return _packetout(os,op,0);
1042 }
1043
1044 int ogg_packet_release(ogg_packet *op) {
1045   if(op){
1046     ogg_buffer_release(op->packet);
1047     memset(op, 0, sizeof(*op));
1048   }
1049   return OGG_SUCCESS;
1050 }
1051
1052 int ogg_page_release(ogg_page *og) {
1053   if(og){
1054     ogg_buffer_release(og->header);
1055     ogg_buffer_release(og->body);
1056     memset(og, 0, sizeof(*og));
1057   }
1058   return OGG_SUCCESS;
1059 }
1060
1061 void ogg_page_dup(ogg_page *dup,ogg_page *orig){
1062   dup->header_len=orig->header_len;
1063   dup->body_len=orig->body_len;
1064   dup->header=ogg_buffer_dup(orig->header);
1065   dup->body=ogg_buffer_dup(orig->body);
1066 }
1067