1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/vorbis/codebook.c	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,484 @@
     1.4 +/********************************************************************
     1.5 + *                                                                  *
     1.6 + * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
     1.7 + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
     1.8 + * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
     1.9 + * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
    1.10 + *                                                                  *
    1.11 + * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009             *
    1.12 + * by the Xiph.Org Foundation http://www.xiph.org/                  *
    1.13 + *                                                                  *
    1.14 + ********************************************************************
    1.15 +
    1.16 + function: basic codebook pack/unpack/code/decode operations
    1.17 + last mod: $Id: codebook.c 18183 2012-02-03 20:51:27Z xiphmont $
    1.18 +
    1.19 + ********************************************************************/
    1.20 +
    1.21 +#include <stdlib.h>
    1.22 +#include <string.h>
    1.23 +#include <math.h>
    1.24 +#include <ogg/ogg.h>
    1.25 +#include "vorbis/codec.h"
    1.26 +#include "codebook.h"
    1.27 +#include "scales.h"
    1.28 +#include "misc.h"
    1.29 +#include "os.h"
    1.30 +
    1.31 +/* packs the given codebook into the bitstream **************************/
    1.32 +
    1.33 +int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
    1.34 +  long i,j;
    1.35 +  int ordered=0;
    1.36 +
    1.37 +  /* first the basic parameters */
    1.38 +  oggpack_write(opb,0x564342,24);
    1.39 +  oggpack_write(opb,c->dim,16);
    1.40 +  oggpack_write(opb,c->entries,24);
    1.41 +
    1.42 +  /* pack the codewords.  There are two packings; length ordered and
    1.43 +     length random.  Decide between the two now. */
    1.44 +
    1.45 +  for(i=1;i<c->entries;i++)
    1.46 +    if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
    1.47 +  if(i==c->entries)ordered=1;
    1.48 +
    1.49 +  if(ordered){
    1.50 +    /* length ordered.  We only need to say how many codewords of
    1.51 +       each length.  The actual codewords are generated
    1.52 +       deterministically */
    1.53 +
    1.54 +    long count=0;
    1.55 +    oggpack_write(opb,1,1);  /* ordered */
    1.56 +    oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
    1.57 +
    1.58 +    for(i=1;i<c->entries;i++){
    1.59 +      long this=c->lengthlist[i];
    1.60 +      long last=c->lengthlist[i-1];
    1.61 +      if(this>last){
    1.62 +        for(j=last;j<this;j++){
    1.63 +          oggpack_write(opb,i-count,_ilog(c->entries-count));
    1.64 +          count=i;
    1.65 +        }
    1.66 +      }
    1.67 +    }
    1.68 +    oggpack_write(opb,i-count,_ilog(c->entries-count));
    1.69 +
    1.70 +  }else{
    1.71 +    /* length random.  Again, we don't code the codeword itself, just
    1.72 +       the length.  This time, though, we have to encode each length */
    1.73 +    oggpack_write(opb,0,1);   /* unordered */
    1.74 +
    1.75 +    /* algortihmic mapping has use for 'unused entries', which we tag
    1.76 +       here.  The algorithmic mapping happens as usual, but the unused
    1.77 +       entry has no codeword. */
    1.78 +    for(i=0;i<c->entries;i++)
    1.79 +      if(c->lengthlist[i]==0)break;
    1.80 +
    1.81 +    if(i==c->entries){
    1.82 +      oggpack_write(opb,0,1); /* no unused entries */
    1.83 +      for(i=0;i<c->entries;i++)
    1.84 +        oggpack_write(opb,c->lengthlist[i]-1,5);
    1.85 +    }else{
    1.86 +      oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
    1.87 +      for(i=0;i<c->entries;i++){
    1.88 +        if(c->lengthlist[i]==0){
    1.89 +          oggpack_write(opb,0,1);
    1.90 +        }else{
    1.91 +          oggpack_write(opb,1,1);
    1.92 +          oggpack_write(opb,c->lengthlist[i]-1,5);
    1.93 +        }
    1.94 +      }
    1.95 +    }
    1.96 +  }
    1.97 +
    1.98 +  /* is the entry number the desired return value, or do we have a
    1.99 +     mapping? If we have a mapping, what type? */
   1.100 +  oggpack_write(opb,c->maptype,4);
   1.101 +  switch(c->maptype){
   1.102 +  case 0:
   1.103 +    /* no mapping */
   1.104 +    break;
   1.105 +  case 1:case 2:
   1.106 +    /* implicitly populated value mapping */
   1.107 +    /* explicitly populated value mapping */
   1.108 +
   1.109 +    if(!c->quantlist){
   1.110 +      /* no quantlist?  error */
   1.111 +      return(-1);
   1.112 +    }
   1.113 +
   1.114 +    /* values that define the dequantization */
   1.115 +    oggpack_write(opb,c->q_min,32);
   1.116 +    oggpack_write(opb,c->q_delta,32);
   1.117 +    oggpack_write(opb,c->q_quant-1,4);
   1.118 +    oggpack_write(opb,c->q_sequencep,1);
   1.119 +
   1.120 +    {
   1.121 +      int quantvals;
   1.122 +      switch(c->maptype){
   1.123 +      case 1:
   1.124 +        /* a single column of (c->entries/c->dim) quantized values for
   1.125 +           building a full value list algorithmically (square lattice) */
   1.126 +        quantvals=_book_maptype1_quantvals(c);
   1.127 +        break;
   1.128 +      case 2:
   1.129 +        /* every value (c->entries*c->dim total) specified explicitly */
   1.130 +        quantvals=c->entries*c->dim;
   1.131 +        break;
   1.132 +      default: /* NOT_REACHABLE */
   1.133 +        quantvals=-1;
   1.134 +      }
   1.135 +
   1.136 +      /* quantized values */
   1.137 +      for(i=0;i<quantvals;i++)
   1.138 +        oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
   1.139 +
   1.140 +    }
   1.141 +    break;
   1.142 +  default:
   1.143 +    /* error case; we don't have any other map types now */
   1.144 +    return(-1);
   1.145 +  }
   1.146 +
   1.147 +  return(0);
   1.148 +}
   1.149 +
   1.150 +/* unpacks a codebook from the packet buffer into the codebook struct,
   1.151 +   readies the codebook auxiliary structures for decode *************/
   1.152 +static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
   1.153 +  long i,j;
   1.154 +  static_codebook *s=_ogg_calloc(1,sizeof(*s));
   1.155 +  s->allocedp=1;
   1.156 +
   1.157 +  /* make sure alignment is correct */
   1.158 +  if(oggpack_read(opb,24)!=0x564342)goto _eofout;
   1.159 +
   1.160 +  /* first the basic parameters */
   1.161 +  s->dim=oggpack_read(opb,16);
   1.162 +  s->entries=oggpack_read(opb,24);
   1.163 +  if(s->entries==-1)goto _eofout;
   1.164 +
   1.165 +  if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
   1.166 +
   1.167 +  /* codeword ordering.... length ordered or unordered? */
   1.168 +  switch((int)oggpack_read(opb,1)){
   1.169 +  case 0:{
   1.170 +    long unused;
   1.171 +    /* allocated but unused entries? */
   1.172 +    unused=oggpack_read(opb,1);
   1.173 +    if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
   1.174 +      goto _eofout;
   1.175 +    /* unordered */
   1.176 +    s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
   1.177 +
   1.178 +    /* allocated but unused entries? */
   1.179 +    if(unused){
   1.180 +      /* yes, unused entries */
   1.181 +
   1.182 +      for(i=0;i<s->entries;i++){
   1.183 +        if(oggpack_read(opb,1)){
   1.184 +          long num=oggpack_read(opb,5);
   1.185 +          if(num==-1)goto _eofout;
   1.186 +          s->lengthlist[i]=num+1;
   1.187 +        }else
   1.188 +          s->lengthlist[i]=0;
   1.189 +      }
   1.190 +    }else{
   1.191 +      /* all entries used; no tagging */
   1.192 +      for(i=0;i<s->entries;i++){
   1.193 +        long num=oggpack_read(opb,5);
   1.194 +        if(num==-1)goto _eofout;
   1.195 +        s->lengthlist[i]=num+1;
   1.196 +      }
   1.197 +    }
   1.198 +
   1.199 +    break;
   1.200 +  }
   1.201 +  case 1:
   1.202 +    /* ordered */
   1.203 +    {
   1.204 +      long length=oggpack_read(opb,5)+1;
   1.205 +      if(length==0)goto _eofout;
   1.206 +      s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
   1.207 +
   1.208 +      for(i=0;i<s->entries;){
   1.209 +        long num=oggpack_read(opb,_ilog(s->entries-i));
   1.210 +        if(num==-1)goto _eofout;
   1.211 +        if(length>32 || num>s->entries-i ||
   1.212 +           (num>0 && (num-1)>>(length-1)>1)){
   1.213 +          goto _errout;
   1.214 +        }
   1.215 +        if(length>32)goto _errout;
   1.216 +        for(j=0;j<num;j++,i++)
   1.217 +          s->lengthlist[i]=length;
   1.218 +        length++;
   1.219 +      }
   1.220 +    }
   1.221 +    break;
   1.222 +  default:
   1.223 +    /* EOF */
   1.224 +    goto _eofout;
   1.225 +  }
   1.226 +
   1.227 +  /* Do we have a mapping to unpack? */
   1.228 +  switch((s->maptype=oggpack_read(opb,4))){
   1.229 +  case 0:
   1.230 +    /* no mapping */
   1.231 +    break;
   1.232 +  case 1: case 2:
   1.233 +    /* implicitly populated value mapping */
   1.234 +    /* explicitly populated value mapping */
   1.235 +
   1.236 +    s->q_min=oggpack_read(opb,32);
   1.237 +    s->q_delta=oggpack_read(opb,32);
   1.238 +    s->q_quant=oggpack_read(opb,4)+1;
   1.239 +    s->q_sequencep=oggpack_read(opb,1);
   1.240 +    if(s->q_sequencep==-1)goto _eofout;
   1.241 +
   1.242 +    {
   1.243 +      int quantvals=0;
   1.244 +      switch(s->maptype){
   1.245 +      case 1:
   1.246 +        quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
   1.247 +        break;
   1.248 +      case 2:
   1.249 +        quantvals=s->entries*s->dim;
   1.250 +        break;
   1.251 +      }
   1.252 +
   1.253 +      /* quantized values */
   1.254 +      if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
   1.255 +        goto _eofout;
   1.256 +      s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
   1.257 +      for(i=0;i<quantvals;i++)
   1.258 +        s->quantlist[i]=oggpack_read(opb,s->q_quant);
   1.259 +
   1.260 +      if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
   1.261 +    }
   1.262 +    break;
   1.263 +  default:
   1.264 +    goto _errout;
   1.265 +  }
   1.266 +
   1.267 +  /* all set */
   1.268 +  return(s);
   1.269 +
   1.270 + _errout:
   1.271 + _eofout:
   1.272 +  vorbis_staticbook_destroy(s);
   1.273 +  return(NULL);
   1.274 +}
   1.275 +
   1.276 +/* returns the number of bits ************************************************/
   1.277 +int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
   1.278 +  if(a<0 || a>=book->c->entries)return(0);
   1.279 +  oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
   1.280 +  return(book->c->lengthlist[a]);
   1.281 +}
   1.282 +
   1.283 +/* the 'eliminate the decode tree' optimization actually requires the
   1.284 +   codewords to be MSb first, not LSb.  This is an annoying inelegancy
   1.285 +   (and one of the first places where carefully thought out design
   1.286 +   turned out to be wrong; Vorbis II and future Ogg codecs should go
   1.287 +   to an MSb bitpacker), but not actually the huge hit it appears to
   1.288 +   be.  The first-stage decode table catches most words so that
   1.289 +   bitreverse is not in the main execution path. */
   1.290 +
   1.291 +static ogg_uint32_t bitreverse(ogg_uint32_t x){
   1.292 +  x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
   1.293 +  x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
   1.294 +  x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
   1.295 +  x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
   1.296 +  return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
   1.297 +}
   1.298 +
   1.299 +STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
   1.300 +  int  read=book->dec_maxlength;
   1.301 +  long lo,hi;
   1.302 +  long lok = oggpack_look(b,book->dec_firsttablen);
   1.303 +
   1.304 +  if (lok >= 0) {
   1.305 +    long entry = book->dec_firsttable[lok];
   1.306 +    if(entry&0x80000000UL){
   1.307 +      lo=(entry>>15)&0x7fff;
   1.308 +      hi=book->used_entries-(entry&0x7fff);
   1.309 +    }else{
   1.310 +      oggpack_adv(b, book->dec_codelengths[entry-1]);
   1.311 +      return(entry-1);
   1.312 +    }
   1.313 +  }else{
   1.314 +    lo=0;
   1.315 +    hi=book->used_entries;
   1.316 +  }
   1.317 +
   1.318 +  lok = oggpack_look(b, read);
   1.319 +
   1.320 +  while(lok<0 && read>1)
   1.321 +    lok = oggpack_look(b, --read);
   1.322 +  if(lok<0)return -1;
   1.323 +
   1.324 +  /* bisect search for the codeword in the ordered list */
   1.325 +  {
   1.326 +    ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
   1.327 +
   1.328 +    while(hi-lo>1){
   1.329 +      long p=(hi-lo)>>1;
   1.330 +      long test=book->codelist[lo+p]>testword;
   1.331 +      lo+=p&(test-1);
   1.332 +      hi-=p&(-test);
   1.333 +      }
   1.334 +
   1.335 +    if(book->dec_codelengths[lo]<=read){
   1.336 +      oggpack_adv(b, book->dec_codelengths[lo]);
   1.337 +      return(lo);
   1.338 +    }
   1.339 +  }
   1.340 +
   1.341 +  oggpack_adv(b, read);
   1.342 +
   1.343 +  return(-1);
   1.344 +}
   1.345 +
   1.346 +/* Decode side is specced and easier, because we don't need to find
   1.347 +   matches using different criteria; we simply read and map.  There are
   1.348 +   two things we need to do 'depending':
   1.349 +
   1.350 +   We may need to support interleave.  We don't really, but it's
   1.351 +   convenient to do it here rather than rebuild the vector later.
   1.352 +
   1.353 +   Cascades may be additive or multiplicitive; this is not inherent in
   1.354 +   the codebook, but set in the code using the codebook.  Like
   1.355 +   interleaving, it's easiest to do it here.
   1.356 +   addmul==0 -> declarative (set the value)
   1.357 +   addmul==1 -> additive
   1.358 +   addmul==2 -> multiplicitive */
   1.359 +
   1.360 +/* returns the [original, not compacted] entry number or -1 on eof *********/
   1.361 +long vorbis_book_decode(codebook *book, oggpack_buffer *b){
   1.362 +  if(book->used_entries>0){
   1.363 +    long packed_entry=decode_packed_entry_number(book,b);
   1.364 +    if(packed_entry>=0)
   1.365 +      return(book->dec_index[packed_entry]);
   1.366 +  }
   1.367 +
   1.368 +  /* if there's no dec_index, the codebook unpacking isn't collapsed */
   1.369 +  return(-1);
   1.370 +}
   1.371 +
   1.372 +/* returns 0 on OK or -1 on eof *************************************/
   1.373 +/* decode vector / dim granularity gaurding is done in the upper layer */
   1.374 +long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
   1.375 +  if(book->used_entries>0){
   1.376 +    int step=n/book->dim;
   1.377 +    long *entry = alloca(sizeof(*entry)*step);
   1.378 +    float **t = alloca(sizeof(*t)*step);
   1.379 +    int i,j,o;
   1.380 +
   1.381 +    for (i = 0; i < step; i++) {
   1.382 +      entry[i]=decode_packed_entry_number(book,b);
   1.383 +      if(entry[i]==-1)return(-1);
   1.384 +      t[i] = book->valuelist+entry[i]*book->dim;
   1.385 +    }
   1.386 +    for(i=0,o=0;i<book->dim;i++,o+=step)
   1.387 +      for (j=0;j<step;j++)
   1.388 +        a[o+j]+=t[j][i];
   1.389 +  }
   1.390 +  return(0);
   1.391 +}
   1.392 +
   1.393 +/* decode vector / dim granularity gaurding is done in the upper layer */
   1.394 +long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
   1.395 +  if(book->used_entries>0){
   1.396 +    int i,j,entry;
   1.397 +    float *t;
   1.398 +
   1.399 +    if(book->dim>8){
   1.400 +      for(i=0;i<n;){
   1.401 +        entry = decode_packed_entry_number(book,b);
   1.402 +        if(entry==-1)return(-1);
   1.403 +        t     = book->valuelist+entry*book->dim;
   1.404 +        for (j=0;j<book->dim;)
   1.405 +          a[i++]+=t[j++];
   1.406 +      }
   1.407 +    }else{
   1.408 +      for(i=0;i<n;){
   1.409 +        entry = decode_packed_entry_number(book,b);
   1.410 +        if(entry==-1)return(-1);
   1.411 +        t     = book->valuelist+entry*book->dim;
   1.412 +        j=0;
   1.413 +        switch((int)book->dim){
   1.414 +        case 8:
   1.415 +          a[i++]+=t[j++];
   1.416 +        case 7:
   1.417 +          a[i++]+=t[j++];
   1.418 +        case 6:
   1.419 +          a[i++]+=t[j++];
   1.420 +        case 5:
   1.421 +          a[i++]+=t[j++];
   1.422 +        case 4:
   1.423 +          a[i++]+=t[j++];
   1.424 +        case 3:
   1.425 +          a[i++]+=t[j++];
   1.426 +        case 2:
   1.427 +          a[i++]+=t[j++];
   1.428 +        case 1:
   1.429 +          a[i++]+=t[j++];
   1.430 +        case 0:
   1.431 +          break;
   1.432 +        }
   1.433 +      }
   1.434 +    }
   1.435 +  }
   1.436 +  return(0);
   1.437 +}
   1.438 +
   1.439 +/* unlike the others, we guard against n not being an integer number
   1.440 +   of <dim> internally rather than in the upper layer (called only by
   1.441 +   floor0) */
   1.442 +long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
   1.443 +  if(book->used_entries>0){
   1.444 +    int i,j,entry;
   1.445 +    float *t;
   1.446 +
   1.447 +    for(i=0;i<n;){
   1.448 +      entry = decode_packed_entry_number(book,b);
   1.449 +      if(entry==-1)return(-1);
   1.450 +      t     = book->valuelist+entry*book->dim;
   1.451 +      for (j=0;i<n && j<book->dim;){
   1.452 +        a[i++]=t[j++];
   1.453 +      }
   1.454 +    }
   1.455 +  }else{
   1.456 +    int i;
   1.457 +
   1.458 +    for(i=0;i<n;){
   1.459 +      a[i++]=0.f;
   1.460 +    }
   1.461 +  }
   1.462 +  return(0);
   1.463 +}
   1.464 +
   1.465 +long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
   1.466 +                              oggpack_buffer *b,int n){
   1.467 +
   1.468 +  long i,j,entry;
   1.469 +  int chptr=0;
   1.470 +  if(book->used_entries>0){
   1.471 +    for(i=offset/ch;i<(offset+n)/ch;){
   1.472 +      entry = decode_packed_entry_number(book,b);
   1.473 +      if(entry==-1)return(-1);
   1.474 +      {
   1.475 +        const float *t = book->valuelist+entry*book->dim;
   1.476 +        for (j=0;j<book->dim;j++){
   1.477 +          a[chptr++][i]+=t[j];
   1.478 +          if(chptr==ch){
   1.479 +            chptr=0;
   1.480 +            i++;
   1.481 +          }
   1.482 +        }
   1.483 +      }
   1.484 +    }
   1.485 +  }
   1.486 +  return(0);
   1.487 +}