/********************************************************************

 *                                                                  *

 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *

 *                                                                  *

 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *

 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *

 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *

 *                                                                  *

 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2003    *

 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *

 *                                                                  *

 ********************************************************************

 function: decode Ogg streams back into raw packets

 note: The CRC code is directly derived from public domain code by

 Ross Williams (ross@guest.adelaide.edu.au).  See docs/framing.html

 for details.

 ********************************************************************/

#include <stdlib.h>

#include <string.h>

#include "ogg.h"

#include "misc.h"

/* A complete description of Ogg framing exists in docs/framing.html */

/* basic, centralized Ogg memory management based on linked lists of

   references to refcounted memory buffers.  References and buffers

   are both recycled.  Buffers are passed around and consumed in

   reference form. */

static ogg_buffer_state *ogg_buffer_create(void){

  ogg_buffer_state *bs=_ogg_calloc(1,sizeof(*bs));

  return bs;

}

/* destruction is 'lazy'; there may be memory references outstanding,

   and yanking the buffer state out from underneath would be

   antisocial.  Dealloc what is currently unused and have

   _release_one watch for the stragglers to come in.  When they do,

   finish destruction. */

/* call the helper while holding lock */

static void _ogg_buffer_destroy(ogg_buffer_state *bs){

  ogg_buffer *bt;

  ogg_reference *rt;

  if(bs->shutdown){

    bt=bs->unused_buffers;

    rt=bs->unused_references;

    while(bt){

      ogg_buffer *b=bt;

      bt=b->ptr.next;

      if(b->data)_ogg_free(b->data);

      _ogg_free(b);

    }

    bs->unused_buffers=0;

    while(rt){

      ogg_reference *r=rt;

      rt=r->next;

      _ogg_free(r);

    }

    bs->unused_references=0;

    if(!bs->outstanding)

      _ogg_free(bs);

  }

}

static void ogg_buffer_destroy(ogg_buffer_state *bs){

  bs->shutdown=1;

  _ogg_buffer_destroy(bs);

}

static ogg_buffer *_fetch_buffer(ogg_buffer_state *bs,long bytes){

  ogg_buffer    *ob;

  bs->outstanding++;

  /* do we have an unused buffer sitting in the pool? */

  if(bs->unused_buffers){

    ob=bs->unused_buffers;

    bs->unused_buffers=ob->ptr.next;

    /* if the unused buffer is too small, grow it */

    if(ob->size<bytes){

      ob->data=_ogg_realloc(ob->data,bytes);

      ob->size=bytes;

    }

  }else{

    /* allocate a new buffer */

    ob=_ogg_malloc(sizeof(*ob));

    ob->data=_ogg_malloc(bytes<16?16:bytes);

    ob->size=bytes;

  }

  ob->refcount=1;

  ob->ptr.owner=bs;

  return ob;

}

static ogg_reference *_fetch_ref(ogg_buffer_state *bs){

  ogg_reference *or;

  bs->outstanding++;

  /* do we have an unused reference sitting in the pool? */

  if(bs->unused_references){

    or=bs->unused_references;

    bs->unused_references=or->next;

  }else{

    /* allocate a new reference */

    or=_ogg_malloc(sizeof(*or));

  }

  or->begin=0;

  or->length=0;

  or->next=0;

  return or;

}

/* fetch a reference pointing to a fresh, initially continguous buffer

   of at least [bytes] length */

static ogg_reference *ogg_buffer_alloc(ogg_buffer_state *bs,long bytes){

  ogg_buffer    *ob=_fetch_buffer(bs,bytes);

  ogg_reference *or=_fetch_ref(bs);

  or->buffer=ob;

  return or;

}

/* enlarge the data buffer in the current link */

static void ogg_buffer_realloc(ogg_reference *or,long bytes){

  ogg_buffer    *ob=or->buffer;

  /* if the unused buffer is too small, grow it */

  if(ob->size<bytes){

    ob->data=_ogg_realloc(ob->data,bytes);

    ob->size=bytes;

  }

}

static void _ogg_buffer_mark_one(ogg_reference *or){

  or->buffer->refcount++;

}

/* increase the refcount of the buffers to which the reference points */

static void ogg_buffer_mark(ogg_reference *or){

  while(or){

    _ogg_buffer_mark_one(or);

    or=or->next;

  }

}

/* duplicate a reference (pointing to the same actual buffer memory)

   and increment buffer refcount.  If the desired segment begins out

   of range, NULL is returned; if the desired segment is simply zero

   length, a zero length ref is returned.  Partial range overlap

   returns the overlap of the ranges */

static ogg_reference *ogg_buffer_sub(ogg_reference *or,long begin,long length){

  ogg_reference *ret=0,*head=0;

  /* walk past any preceeding fragments we don't want */

  while(or && begin>=or->length){

    begin-=or->length;

    or=or->next;

  }

  /* duplicate the reference chain; increment refcounts */

  while(or && length){

    ogg_reference *temp=_fetch_ref(or->buffer->ptr.owner);

    if(head)

      head->next=temp;

    else

      ret=temp;

    head=temp;

    head->buffer=or->buffer;    

    head->begin=or->begin+begin;

    head->length=length;

    if(head->length>or->length-begin)

      head->length=or->length-begin;

    begin=0;

    length-=head->length;

    or=or->next;

  }

  ogg_buffer_mark(ret);

  return ret;

}

ogg_reference *ogg_buffer_dup(ogg_reference *or){

  ogg_reference *ret=0,*head=0;

  /* duplicate the reference chain; increment refcounts */

  while(or){

    ogg_reference *temp=_fetch_ref(or->buffer->ptr.owner);

    if(head)

      head->next=temp;

    else

      ret=temp;

    head=temp;

    head->buffer=or->buffer;    

    head->begin=or->begin;

    head->length=or->length;

    or=or->next;

  }

  ogg_buffer_mark(ret);

  return ret;

}

/* split a reference into two references; 'return' is a reference to

   the buffer preceeding pos and 'head'/'tail' are the buffer past the

   split.  If pos is at or past the end of the passed in segment,

   'head/tail' are NULL */

static ogg_reference *ogg_buffer_split(ogg_reference **tail,

                                ogg_reference **head,long pos){

  /* walk past any preceeding fragments to one of:

     a) the exact boundary that seps two fragments

     b) the fragment that needs split somewhere in the middle */

  ogg_reference *ret=*tail;

  ogg_reference *or=*tail;

  while(or && pos>or->length){

    pos-=or->length;

    or=or->next;

  }

  if(!or || pos==0){

    return 0;

  }else{

    if(pos>=or->length){

      /* exact split, or off the end? */

      if(or->next){

        /* a split */

        *tail=or->next;

        or->next=0;

      }else{

        /* off or at the end */

        *tail=*head=0;

      }

    }else{

      /* split within a fragment */

      long lengthA=pos;

      long beginB=or->begin+pos;

      long lengthB=or->length-pos;

      /* make a new reference to tail the second piece */

      *tail=_fetch_ref(or->buffer->ptr.owner);

      (*tail)->buffer=or->buffer;

      (*tail)->begin=beginB;

      (*tail)->length=lengthB;

      (*tail)->next=or->next;

      _ogg_buffer_mark_one(*tail);

      if(head && or==*head)*head=*tail;    

      /* update the first piece */

      or->next=0;

      or->length=lengthA;

    }

  }

  return ret;

}

static void ogg_buffer_release_one(ogg_reference *or){

  ogg_buffer *ob=or->buffer;

  ogg_buffer_state *bs=ob->ptr.owner;

  ob->refcount--;

  if(ob->refcount==0){

    bs->outstanding--; /* for the returned buffer */

    ob->ptr.next=bs->unused_buffers;

    bs->unused_buffers=ob;

  }

  bs->outstanding--; /* for the returned reference */

  or->next=bs->unused_references;

  bs->unused_references=or;

  _ogg_buffer_destroy(bs); /* lazy cleanup (if needed) */

}

/* release the references, decrease the refcounts of buffers to which

   they point, release any buffers with a refcount that drops to zero */

static void ogg_buffer_release(ogg_reference *or){

  while(or){

    ogg_reference *next=or->next;

    ogg_buffer_release_one(or);

    or=next;

  }

}

static ogg_reference *ogg_buffer_pretruncate(ogg_reference *or,long pos){

  /* release preceeding fragments we don't want */

  while(or && pos>=or->length){

    ogg_reference *next=or->next;

    pos-=or->length;

    ogg_buffer_release_one(or);

    or=next;

  }

  if (or) {

    or->begin+=pos;

    or->length-=pos;

  }

  return or;

}

static ogg_reference *ogg_buffer_walk(ogg_reference *or){

  if(!or)return NULL;

  while(or->next){

    or=or->next;

  }

  return(or);

}

/* *head is appended to the front end (head) of *tail; both continue to

   be valid pointers, with *tail at the tail and *head at the head */

static ogg_reference *ogg_buffer_cat(ogg_reference *tail, ogg_reference *head){

  if(!tail)return head;

  while(tail->next){

    tail=tail->next;

  }

  tail->next=head;

  return ogg_buffer_walk(head);

}

static void _positionB(oggbyte_buffer *b,int pos){

  if(pos<b->pos){

    /* start at beginning, scan forward */

    b->ref=b->baseref;

    b->pos=0;

    b->end=b->pos+b->ref->length;

    b->ptr=b->ref->buffer->data+b->ref->begin;

  }

}

static void _positionF(oggbyte_buffer *b,int pos){

  /* scan forward for position */

  while(pos>=b->end){

    /* just seek forward */

    b->pos+=b->ref->length;

    b->ref=b->ref->next;

    b->end=b->ref->length+b->pos;

    b->ptr=b->ref->buffer->data+b->ref->begin;

  }

}

static int oggbyte_init(oggbyte_buffer *b,ogg_reference *or){

  memset(b,0,sizeof(*b));

  if(or){

    b->ref=b->baseref=or;

    b->pos=0;

    b->end=b->ref->length;

    b->ptr=b->ref->buffer->data+b->ref->begin;  

    return 0;

  }else

    return -1;

}

static void oggbyte_set4(oggbyte_buffer *b,ogg_uint32_t val,int pos){

  int i;

  _positionB(b,pos);

  for(i=0;i<4;i++){

    _positionF(b,pos);

    b->ptr[pos-b->pos]=val;

    val>>=8;

    ++pos;

  }

}

static unsigned char oggbyte_read1(oggbyte_buffer *b,int pos){

  _positionB(b,pos);

  _positionF(b,pos);

  return b->ptr[pos-b->pos];

}

static ogg_uint32_t oggbyte_read4(oggbyte_buffer *b,int pos){

  ogg_uint32_t ret;

  _positionB(b,pos);

  _positionF(b,pos);

  ret=b->ptr[pos-b->pos];

  _positionF(b,++pos);

  ret|=b->ptr[pos-b->pos]<<8;

  _positionF(b,++pos);

  ret|=b->ptr[pos-b->pos]<<16;

  _positionF(b,++pos);

  ret|=b->ptr[pos-b->pos]<<24;

  return ret;

}

static ogg_int64_t oggbyte_read8(oggbyte_buffer *b,int pos){

  ogg_int64_t ret;

  unsigned char t[7];

  int i;

  _positionB(b,pos);

  for(i=0;i<7;i++){

    _positionF(b,pos);

    t[i]=b->ptr[pos++ -b->pos];

  }

  _positionF(b,pos);

  ret=b->ptr[pos-b->pos];

  for(i=6;i>=0;--i)

    ret= ret<<8 | t[i];

  return ret;

}

/* Now we get to the actual framing code */

int ogg_page_version(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read1(&ob,4);

}

int ogg_page_continued(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read1(&ob,5)&0x01;

}

int ogg_page_bos(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read1(&ob,5)&0x02;

}

int ogg_page_eos(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read1(&ob,5)&0x04;

}

ogg_int64_t ogg_page_granulepos(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read8(&ob,6);

}

ogg_uint32_t ogg_page_serialno(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read4(&ob,14);

}

ogg_uint32_t ogg_page_pageno(ogg_page *og){

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  return oggbyte_read4(&ob,18);

}

/* returns the number of packets that are completed on this page (if

   the leading packet is begun on a previous page, but ends on this

   page, it's counted */

/* NOTE:

If a page consists of a packet begun on a previous page, and a new

packet begun (but not completed) on this page, the return will be:

  ogg_page_packets(page)   ==1, 

  ogg_page_continued(page) !=0

If a page happens to be a single packet that was begun on a

previous page, and spans to the next page (in the case of a three or

more page packet), the return will be: 

  ogg_page_packets(page)   ==0, 

  ogg_page_continued(page) !=0

*/

int ogg_page_packets(ogg_page *og){

  int i;

  int n;

  int count=0;

  oggbyte_buffer ob;

  oggbyte_init(&ob,og->header);

  n=oggbyte_read1(&ob,26);

  for(i=0;i<n;i++)

    if(oggbyte_read1(&ob,27+i)<255)count++;

  return(count);

}

/* Static CRC calculation table.  See older code in CVS for dead

   run-time initialization code. */

static ogg_uint32_t crc_lookup[256]={

  0x00000000,0x04c11db7,0x09823b6e,0x0d4326d9,

  0x130476dc,0x17c56b6b,0x1a864db2,0x1e475005,

  0x2608edb8,0x22c9f00f,0x2f8ad6d6,0x2b4bcb61,

  0x350c9b64,0x31cd86d3,0x3c8ea00a,0x384fbdbd,

  0x4c11db70,0x48d0c6c7,0x4593e01e,0x4152fda9,

  0x5f15adac,0x5bd4b01b,0x569796c2,0x52568b75,

  0x6a1936c8,0x6ed82b7f,0x639b0da6,0x675a1011,

  0x791d4014,0x7ddc5da3,0x709f7b7a,0x745e66cd,

  0x9823b6e0,0x9ce2ab57,0x91a18d8e,0x95609039,

  0x8b27c03c,0x8fe6dd8b,0x82a5fb52,0x8664e6e5,

  0xbe2b5b58,0xbaea46ef,0xb7a96036,0xb3687d81,

  0xad2f2d84,0xa9ee3033,0xa4ad16ea,0xa06c0b5d,

  0xd4326d90,0xd0f37027,0xddb056fe,0xd9714b49,

  0xc7361b4c,0xc3f706fb,0xceb42022,0xca753d95,

  0xf23a8028,0xf6fb9d9f,0xfbb8bb46,0xff79a6f1,

  0xe13ef6f4,0xe5ffeb43,0xe8bccd9a,0xec7dd02d,

  0x34867077,0x30476dc0,0x3d044b19,0x39c556ae,

  0x278206ab,0x23431b1c,0x2e003dc5,0x2ac12072,

  0x128e9dcf,0x164f8078,0x1b0ca6a1,0x1fcdbb16,

  0x018aeb13,0x054bf6a4,0x0808d07d,0x0cc9cdca,

  0x7897ab07,0x7c56b6b0,0x71159069,0x75d48dde,

  0x6b93dddb,0x6f52c06c,0x6211e6b5,0x66d0fb02,

  0x5e9f46bf,0x5a5e5b08,0x571d7dd1,0x53dc6066,

  0x4d9b3063,0x495a2dd4,0x44190b0d,0x40d816ba,

  0xaca5c697,0xa864db20,0xa527fdf9,0xa1e6e04e,