misc/libtremor/tremor/framing.c
branchhedgeroid
changeset 6045 9a7cc0f29430
parent 6043 9bd2d6b1ba52
child 7697 767d3c4153a1
equal deleted inserted replaced
6043:9bd2d6b1ba52 6045:9a7cc0f29430
       
     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