/********************************************************************
 *                                                                  *
 * THIS FILE IS PART OF THE OggVorbis SOFTWARE 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 SOURCE CODE IS (C) COPYRIGHT 1994-2015             *
 * by the Xiph.Org Foundation http://www.xiph.org/                  *
 *                                                                  *
 ********************************************************************

 function: basic codebook pack/unpack/code/decode operations
 last mod: $Id: codebook.c 19457 2015-03-03 00:15:29Z giles $

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

#include <string.h>
#include "codec.h"
#include "codebook.h"
#include "os.h"

/* unpacks a codebook from the packet buffer into the codebook struct,
   readies the codebook auxiliary structures for decode *************/
static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
  int32_t i,j;
  static_codebook *s=_ogg_calloc(1,sizeof(*s));
  if (!s) return NULL;

  /* make sure alignment is correct */
  if(oggpack_read(opb,24)!=0x564342)goto _eofout;

  /* first the basic parameters */
  s->dim=oggpack_read(opb,16);
  s->entries=oggpack_read(opb,24);
  if(s->entries==-1)goto _eofout;

  if(ilog(s->dim)+ilog(s->entries)>24)goto _eofout;

  /* codeword ordering.... length ordered or unordered? */
  switch((int)oggpack_read(opb,1)){
  case 0:{
    int32_t unused;
    /* allocated but unused entries? */
    unused=oggpack_read(opb,1);
//    if(((s->entries*(unused?1:5)+7)>>3)>(opb->storage-oggpack_bytes(opb))
//      goto _eofout;
    /* unordered */
    s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
    if (!s->lengthlist) goto _errout;

    /* allocated but unused entries? */
    if(unused){
      /* yes, unused entries */

      for(i=0;i<s->entries;i++){
    if(oggpack_read(opb,1)){
      int32_t num=oggpack_read(opb,5);
      if(num==-1)goto _eofout;
      s->lengthlist[i]=num+1;
    }else
      s->lengthlist[i]=0;
      }
    }else{
      /* all entries used; no tagging */
      for(i=0;i<s->entries;i++){
    int32_t num=oggpack_read(opb,5);
    if(num==-1)goto _eofout;
    s->lengthlist[i]=num+1;
      }
    }
  }
  break;
  case 1:
    /* ordered */
    {
      int32_t length=oggpack_read(opb,5)+1;
      if(length==0)goto _eofout;
      s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
      if (!s->lengthlist) goto _errout;

      for(i=0;i<s->entries;){
        int32_t num=oggpack_read(opb,ilog(s->entries-i));
        if(num==-1)goto _eofout;
        if(length>32 || num>s->entries-i ||
           (num>0 && (num-1)>>(length-1)>1)){
          goto _errout;
        }
        for(j=0;j<num;j++,i++)
          s->lengthlist[i]=length;
        length++;
      }
    }
    break;
  default:
    /* EOF */
    goto _eofout;
  }

  /* Do we have a mapping to unpack? */
  switch((s->maptype=oggpack_read(opb,4))){
  case 0:
    /* no mapping */
    break;
  case 1: case 2:
    /* implicitly populated value mapping */
    /* explicitly populated value mapping */

    s->q_min=oggpack_read(opb,32);
    s->q_delta=oggpack_read(opb,32);
    s->q_quant=oggpack_read(opb,4)+1;
    s->q_sequencep=oggpack_read(opb,1);
    if(s->q_sequencep==-1)goto _eofout;

    {
      int quantvals=0;
      switch(s->maptype){
      case 1:
        quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
    break;
      case 2:
    quantvals=s->entries*s->dim;
    break;
      }

      /* quantized values */
//      if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
//        goto _eofout;
      s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
      if (!s->quantlist) goto _errout;
      for(i=0;i<quantvals;i++)
    s->quantlist[i]=oggpack_read(opb,s->q_quant);

      if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
    }
    break;
  default:
    goto _errout;
  }

  /* all set */
  return(s);

 _errout:
 _eofout:
  vorbis_staticbook_destroy(s);
  return(NULL);
}

/* the 'eliminate the decode tree' optimization actually requires the
   codewords to be MSb first, not LSb.  This is an annoying inelegancy
   (and one of the first places where carefully thought out design
   turned out to be wrong; Vorbis II and future Ogg codecs should go
   to an MSb bitpacker), but not actually the huge hit it appears to
   be.  The first-stage decode table catches most words so that
   bitreverse is not in the main execution path. */

static uint32_t bitreverse(uint32_t x){
  x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
  x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
  x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
  x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
  return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
}

static int32_t decode_packed_entry_number(const codebook *book, oggpack_buffer *b){
  int  read=book->dec_maxlength;
  int32_t lo,hi;
  int32_t lok = oggpack_look(b,book->dec_firsttablen);

  if (lok >= 0) {
    int32_t entry = book->dec_firsttable[lok];
    if(entry&0x80000000U){
      lo=(entry>>15)&0x7fff;
      hi=book->used_entries-(entry&0x7fff);
    }else{
      oggpack_adv(b, book->dec_codelengths[entry-1]);
      return(entry-1);
    }
  }else{
    lo=0;
    hi=book->used_entries;
  }

  /* Single entry codebooks use a firsttablen of 1 and a
     dec_maxlength of 1.  If a single-entry codebook gets here (due to
     failure to read one bit above), the next look attempt will also
     fail and we'll correctly kick out instead of trying to walk the
     underformed tree */

  lok = oggpack_look(b, read);

  while(lok<0 && read>1)
    lok = oggpack_look(b, --read);
  if(lok<0)return -1;

  /* bisect search for the codeword in the ordered list */
  {
    uint32_t testword=bitreverse((uint32_t)lok);

    while(hi-lo>1){
      int32_t p=(hi-lo)>>1;
      int32_t test=book->codelist[lo+p]>testword;
      lo+=p&(test-1);
      hi-=p&(-test);
    }

    if(book->dec_codelengths[lo]<=read){
      oggpack_adv(b, book->dec_codelengths[lo]);
      return(lo);
    }
  }

  oggpack_adv(b, read);
  return(-1);
}

/* Decode side is specced and easier, because we don't need to find
   matches using different criteria; we simply read and map.  There are
   two things we need to do 'depending':

   We may need to support interleave.  We don't really, but it's
   convenient to do it here rather than rebuild the vector later.

   Cascades may be additive or multiplicitive; this is not inherent in
   the codebook, but set in the code using the codebook.  Like
   interleaving, it's easiest to do it here.
   addmul==0 -> declarative (set the value)
   addmul==1 -> additive
   addmul==2 -> multiplicitive */

/* returns the [original, not compacted] entry number or -1 on eof *********/
int32_t vorbis_book_decode(const codebook *book, oggpack_buffer *b){
  if(book->used_entries>0){
    int32_t packed_entry=decode_packed_entry_number(book,b);
    if(packed_entry>=0)
      return(book->dec_index[packed_entry]);
  }

  /* if there's no dec_index, the codebook unpacking isn't collapsed */
  return(-1);
}

/* returns 0 on OK or -1 on eof *************************************/
/* decode vector / dim granularity gaurding is done in the upper layer */
int32_t vorbis_book_decodevs_add(const codebook* book, bint* a, oggpack_buffer* b, int n){
  if(book->used_entries>0){
    int step=n/book->dim;
    int i,j,o,entry;
    bint* t;

    for (i=0;i<step;i++){
      entry=decode_packed_entry_number(book,b);
      if(entry==-1)return(-1);
      t = book->valuelist+entry*book->dim;
      for (j=0,o=0;j<book->dim;j++,o+=step)
        a[o+i]+=t[j];
    }
  }

  return(0);
}

/* decode vector / dim granularity gaurding is done in the upper layer */
int32_t vorbis_book_decodev_add(const codebook* book, bint* a, oggpack_buffer* b, int n){
  if(book->used_entries>0){
    int i,j,entry;
    bint* t;

    for(i=0;i<n;){
      entry = decode_packed_entry_number(book,b);
      if(entry==-1)return(-1);
      t = book->valuelist+entry*book->dim;
      for (j=0;j<book->dim;)
        a[i++]+=t[j++];
    }
  }
  return(0);
}

/* unlike the others, we guard against n not being an integer number
   of <dim> internally rather than in the upper layer (called only by
   floor0) */
int32_t vorbis_book_decodev_set(const codebook* book, bint* a, oggpack_buffer* b, int n){
  if(book->used_entries>0){
    int i,j,entry;
    bint* t;

    for(i=0;i<n;){
      entry = decode_packed_entry_number(book,b);
      if(entry==-1)return(-1);
      t = book->valuelist+entry*book->dim;
      for (j=0;i<n && j<book->dim;)
        a[i++]=t[j++];
    }
  }else{
    int i;
    for(i=0;i<n;){
        a[i++]=BIZERO;
    }
  }
  return(0);
}

int32_t vorbis_book_decodevv_add(const codebook* book, bint** a, int32_t offset, int ch,
                  oggpack_buffer* b, int n){
  if(book->used_entries>0){
    int32_t i,j,entry;
    int chptr=0;

    for(i=offset/ch;i<(offset+n)/ch;){
      entry = decode_packed_entry_number(book,b);
      if(entry==-1)return(-1);
      {
        const bint* t = book->valuelist+entry*book->dim;
        for (j=0;j<book->dim;j++){
          a[chptr++][i]+=t[j];
          if(chptr==ch){
            chptr=0;
            i++;
          }
        }
      }
    }
  }
  return(0);
}
