dbf-halloween2015

diff libs/vorbis/sharedbook.c @ 1:c3f5c32cb210

barfed all the libraries in the source tree to make porting easier
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 01 Nov 2015 00:36:56 +0200
parents
children
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/vorbis/sharedbook.c	Sun Nov 01 00:36:56 2015 +0200
     1.3 @@ -0,0 +1,579 @@
     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 shared codebook operations
    1.17 + last mod: $Id: sharedbook.c 17030 2010-03-25 06:52:55Z xiphmont $
    1.18 +
    1.19 + ********************************************************************/
    1.20 +
    1.21 +#include <stdlib.h>
    1.22 +#include <math.h>
    1.23 +#include <string.h>
    1.24 +#include <ogg/ogg.h>
    1.25 +#include "os.h"
    1.26 +#include "misc.h"
    1.27 +#include "vorbis/codec.h"
    1.28 +#include "codebook.h"
    1.29 +#include "scales.h"
    1.30 +
    1.31 +/**** pack/unpack helpers ******************************************/
    1.32 +int _ilog(unsigned int v){
    1.33 +  int ret=0;
    1.34 +  while(v){
    1.35 +    ret++;
    1.36 +    v>>=1;
    1.37 +  }
    1.38 +  return(ret);
    1.39 +}
    1.40 +
    1.41 +/* 32 bit float (not IEEE; nonnormalized mantissa +
    1.42 +   biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
    1.43 +   Why not IEEE?  It's just not that important here. */
    1.44 +
    1.45 +#define VQ_FEXP 10
    1.46 +#define VQ_FMAN 21
    1.47 +#define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
    1.48 +
    1.49 +/* doesn't currently guard under/overflow */
    1.50 +long _float32_pack(float val){
    1.51 +  int sign=0;
    1.52 +  long exp;
    1.53 +  long mant;
    1.54 +  if(val<0){
    1.55 +    sign=0x80000000;
    1.56 +    val= -val;
    1.57 +  }
    1.58 +  exp= floor(log(val)/log(2.f)+.001); /*+epsilon*/
    1.59 +  mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
    1.60 +  exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
    1.61 +
    1.62 +  return(sign|exp|mant);
    1.63 +}
    1.64 +
    1.65 +float _float32_unpack(long val){
    1.66 +  double mant=val&0x1fffff;
    1.67 +  int    sign=val&0x80000000;
    1.68 +  long   exp =(val&0x7fe00000L)>>VQ_FMAN;
    1.69 +  if(sign)mant= -mant;
    1.70 +  return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
    1.71 +}
    1.72 +
    1.73 +/* given a list of word lengths, generate a list of codewords.  Works
    1.74 +   for length ordered or unordered, always assigns the lowest valued
    1.75 +   codewords first.  Extended to handle unused entries (length 0) */
    1.76 +ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
    1.77 +  long i,j,count=0;
    1.78 +  ogg_uint32_t marker[33];
    1.79 +  ogg_uint32_t *r=_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
    1.80 +  memset(marker,0,sizeof(marker));
    1.81 +
    1.82 +  for(i=0;i<n;i++){
    1.83 +    long length=l[i];
    1.84 +    if(length>0){
    1.85 +      ogg_uint32_t entry=marker[length];
    1.86 +
    1.87 +      /* when we claim a node for an entry, we also claim the nodes
    1.88 +         below it (pruning off the imagined tree that may have dangled
    1.89 +         from it) as well as blocking the use of any nodes directly
    1.90 +         above for leaves */
    1.91 +
    1.92 +      /* update ourself */
    1.93 +      if(length<32 && (entry>>length)){
    1.94 +        /* error condition; the lengths must specify an overpopulated tree */
    1.95 +        _ogg_free(r);
    1.96 +        return(NULL);
    1.97 +      }
    1.98 +      r[count++]=entry;
    1.99 +
   1.100 +      /* Look to see if the next shorter marker points to the node
   1.101 +         above. if so, update it and repeat.  */
   1.102 +      {
   1.103 +        for(j=length;j>0;j--){
   1.104 +
   1.105 +          if(marker[j]&1){
   1.106 +            /* have to jump branches */
   1.107 +            if(j==1)
   1.108 +              marker[1]++;
   1.109 +            else
   1.110 +              marker[j]=marker[j-1]<<1;
   1.111 +            break; /* invariant says next upper marker would already
   1.112 +                      have been moved if it was on the same path */
   1.113 +          }
   1.114 +          marker[j]++;
   1.115 +        }
   1.116 +      }
   1.117 +
   1.118 +      /* prune the tree; the implicit invariant says all the longer
   1.119 +         markers were dangling from our just-taken node.  Dangle them
   1.120 +         from our *new* node. */
   1.121 +      for(j=length+1;j<33;j++)
   1.122 +        if((marker[j]>>1) == entry){
   1.123 +          entry=marker[j];
   1.124 +          marker[j]=marker[j-1]<<1;
   1.125 +        }else
   1.126 +          break;
   1.127 +    }else
   1.128 +      if(sparsecount==0)count++;
   1.129 +  }
   1.130 +
   1.131 +  /* sanity check the huffman tree; an underpopulated tree must be
   1.132 +     rejected. The only exception is the one-node pseudo-nil tree,
   1.133 +     which appears to be underpopulated because the tree doesn't
   1.134 +     really exist; there's only one possible 'codeword' or zero bits,
   1.135 +     but the above tree-gen code doesn't mark that. */
   1.136 +  if(sparsecount != 1){
   1.137 +    for(i=1;i<33;i++)
   1.138 +      if(marker[i] & (0xffffffffUL>>(32-i))){
   1.139 +	_ogg_free(r);
   1.140 +	return(NULL);
   1.141 +      }
   1.142 +  }
   1.143 +
   1.144 +  /* bitreverse the words because our bitwise packer/unpacker is LSb
   1.145 +     endian */
   1.146 +  for(i=0,count=0;i<n;i++){
   1.147 +    ogg_uint32_t temp=0;
   1.148 +    for(j=0;j<l[i];j++){
   1.149 +      temp<<=1;
   1.150 +      temp|=(r[count]>>j)&1;
   1.151 +    }
   1.152 +
   1.153 +    if(sparsecount){
   1.154 +      if(l[i])
   1.155 +        r[count++]=temp;
   1.156 +    }else
   1.157 +      r[count++]=temp;
   1.158 +  }
   1.159 +
   1.160 +  return(r);
   1.161 +}
   1.162 +
   1.163 +/* there might be a straightforward one-line way to do the below
   1.164 +   that's portable and totally safe against roundoff, but I haven't
   1.165 +   thought of it.  Therefore, we opt on the side of caution */
   1.166 +long _book_maptype1_quantvals(const static_codebook *b){
   1.167 +  long vals=floor(pow((float)b->entries,1.f/b->dim));
   1.168 +
   1.169 +  /* the above *should* be reliable, but we'll not assume that FP is
   1.170 +     ever reliable when bitstream sync is at stake; verify via integer
   1.171 +     means that vals really is the greatest value of dim for which
   1.172 +     vals^b->bim <= b->entries */
   1.173 +  /* treat the above as an initial guess */
   1.174 +  while(1){
   1.175 +    long acc=1;
   1.176 +    long acc1=1;
   1.177 +    int i;
   1.178 +    for(i=0;i<b->dim;i++){
   1.179 +      acc*=vals;
   1.180 +      acc1*=vals+1;
   1.181 +    }
   1.182 +    if(acc<=b->entries && acc1>b->entries){
   1.183 +      return(vals);
   1.184 +    }else{
   1.185 +      if(acc>b->entries){
   1.186 +        vals--;
   1.187 +      }else{
   1.188 +        vals++;
   1.189 +      }
   1.190 +    }
   1.191 +  }
   1.192 +}
   1.193 +
   1.194 +/* unpack the quantized list of values for encode/decode ***********/
   1.195 +/* we need to deal with two map types: in map type 1, the values are
   1.196 +   generated algorithmically (each column of the vector counts through
   1.197 +   the values in the quant vector). in map type 2, all the values came
   1.198 +   in in an explicit list.  Both value lists must be unpacked */
   1.199 +float *_book_unquantize(const static_codebook *b,int n,int *sparsemap){
   1.200 +  long j,k,count=0;
   1.201 +  if(b->maptype==1 || b->maptype==2){
   1.202 +    int quantvals;
   1.203 +    float mindel=_float32_unpack(b->q_min);
   1.204 +    float delta=_float32_unpack(b->q_delta);
   1.205 +    float *r=_ogg_calloc(n*b->dim,sizeof(*r));
   1.206 +
   1.207 +    /* maptype 1 and 2 both use a quantized value vector, but
   1.208 +       different sizes */
   1.209 +    switch(b->maptype){
   1.210 +    case 1:
   1.211 +      /* most of the time, entries%dimensions == 0, but we need to be
   1.212 +         well defined.  We define that the possible vales at each
   1.213 +         scalar is values == entries/dim.  If entries%dim != 0, we'll
   1.214 +         have 'too few' values (values*dim<entries), which means that
   1.215 +         we'll have 'left over' entries; left over entries use zeroed
   1.216 +         values (and are wasted).  So don't generate codebooks like
   1.217 +         that */
   1.218 +      quantvals=_book_maptype1_quantvals(b);
   1.219 +      for(j=0;j<b->entries;j++){
   1.220 +        if((sparsemap && b->lengthlist[j]) || !sparsemap){
   1.221 +          float last=0.f;
   1.222 +          int indexdiv=1;
   1.223 +          for(k=0;k<b->dim;k++){
   1.224 +            int index= (j/indexdiv)%quantvals;
   1.225 +            float val=b->quantlist[index];
   1.226 +            val=fabs(val)*delta+mindel+last;
   1.227 +            if(b->q_sequencep)last=val;
   1.228 +            if(sparsemap)
   1.229 +              r[sparsemap[count]*b->dim+k]=val;
   1.230 +            else
   1.231 +              r[count*b->dim+k]=val;
   1.232 +            indexdiv*=quantvals;
   1.233 +          }
   1.234 +          count++;
   1.235 +        }
   1.236 +
   1.237 +      }
   1.238 +      break;
   1.239 +    case 2:
   1.240 +      for(j=0;j<b->entries;j++){
   1.241 +        if((sparsemap && b->lengthlist[j]) || !sparsemap){
   1.242 +          float last=0.f;
   1.243 +
   1.244 +          for(k=0;k<b->dim;k++){
   1.245 +            float val=b->quantlist[j*b->dim+k];
   1.246 +            val=fabs(val)*delta+mindel+last;
   1.247 +            if(b->q_sequencep)last=val;
   1.248 +            if(sparsemap)
   1.249 +              r[sparsemap[count]*b->dim+k]=val;
   1.250 +            else
   1.251 +              r[count*b->dim+k]=val;
   1.252 +          }
   1.253 +          count++;
   1.254 +        }
   1.255 +      }
   1.256 +      break;
   1.257 +    }
   1.258 +
   1.259 +    return(r);
   1.260 +  }
   1.261 +  return(NULL);
   1.262 +}
   1.263 +
   1.264 +void vorbis_staticbook_destroy(static_codebook *b){
   1.265 +  if(b->allocedp){
   1.266 +    if(b->quantlist)_ogg_free(b->quantlist);
   1.267 +    if(b->lengthlist)_ogg_free(b->lengthlist);
   1.268 +    memset(b,0,sizeof(*b));
   1.269 +    _ogg_free(b);
   1.270 +  } /* otherwise, it is in static memory */
   1.271 +}
   1.272 +
   1.273 +void vorbis_book_clear(codebook *b){
   1.274 +  /* static book is not cleared; we're likely called on the lookup and
   1.275 +     the static codebook belongs to the info struct */
   1.276 +  if(b->valuelist)_ogg_free(b->valuelist);
   1.277 +  if(b->codelist)_ogg_free(b->codelist);
   1.278 +
   1.279 +  if(b->dec_index)_ogg_free(b->dec_index);
   1.280 +  if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
   1.281 +  if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
   1.282 +
   1.283 +  memset(b,0,sizeof(*b));
   1.284 +}
   1.285 +
   1.286 +int vorbis_book_init_encode(codebook *c,const static_codebook *s){
   1.287 +
   1.288 +  memset(c,0,sizeof(*c));
   1.289 +  c->c=s;
   1.290 +  c->entries=s->entries;
   1.291 +  c->used_entries=s->entries;
   1.292 +  c->dim=s->dim;
   1.293 +  c->codelist=_make_words(s->lengthlist,s->entries,0);
   1.294 +  /*c->valuelist=_book_unquantize(s,s->entries,NULL);*/
   1.295 +  c->quantvals=_book_maptype1_quantvals(s);
   1.296 +  c->minval=(int)rint(_float32_unpack(s->q_min));
   1.297 +  c->delta=(int)rint(_float32_unpack(s->q_delta));
   1.298 +
   1.299 +  return(0);
   1.300 +}
   1.301 +
   1.302 +static ogg_uint32_t bitreverse(ogg_uint32_t x){
   1.303 +  x=    ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
   1.304 +  x=    ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
   1.305 +  x=    ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
   1.306 +  x=    ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
   1.307 +  return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
   1.308 +}
   1.309 +
   1.310 +static int sort32a(const void *a,const void *b){
   1.311 +  return ( **(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
   1.312 +    ( **(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
   1.313 +}
   1.314 +
   1.315 +/* decode codebook arrangement is more heavily optimized than encode */
   1.316 +int vorbis_book_init_decode(codebook *c,const static_codebook *s){
   1.317 +  int i,j,n=0,tabn;
   1.318 +  int *sortindex;
   1.319 +  memset(c,0,sizeof(*c));
   1.320 +
   1.321 +  /* count actually used entries */
   1.322 +  for(i=0;i<s->entries;i++)
   1.323 +    if(s->lengthlist[i]>0)
   1.324 +      n++;
   1.325 +
   1.326 +  c->entries=s->entries;
   1.327 +  c->used_entries=n;
   1.328 +  c->dim=s->dim;
   1.329 +
   1.330 +  if(n>0){
   1.331 +
   1.332 +    /* two different remappings go on here.
   1.333 +
   1.334 +    First, we collapse the likely sparse codebook down only to
   1.335 +    actually represented values/words.  This collapsing needs to be
   1.336 +    indexed as map-valueless books are used to encode original entry
   1.337 +    positions as integers.
   1.338 +
   1.339 +    Second, we reorder all vectors, including the entry index above,
   1.340 +    by sorted bitreversed codeword to allow treeless decode. */
   1.341 +
   1.342 +    /* perform sort */
   1.343 +    ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
   1.344 +    ogg_uint32_t **codep=alloca(sizeof(*codep)*n);
   1.345 +
   1.346 +    if(codes==NULL)goto err_out;
   1.347 +
   1.348 +    for(i=0;i<n;i++){
   1.349 +      codes[i]=bitreverse(codes[i]);
   1.350 +      codep[i]=codes+i;
   1.351 +    }
   1.352 +
   1.353 +    qsort(codep,n,sizeof(*codep),sort32a);
   1.354 +
   1.355 +    sortindex=alloca(n*sizeof(*sortindex));
   1.356 +    c->codelist=_ogg_malloc(n*sizeof(*c->codelist));
   1.357 +    /* the index is a reverse index */
   1.358 +    for(i=0;i<n;i++){
   1.359 +      int position=codep[i]-codes;
   1.360 +      sortindex[position]=i;
   1.361 +    }
   1.362 +
   1.363 +    for(i=0;i<n;i++)
   1.364 +      c->codelist[sortindex[i]]=codes[i];
   1.365 +    _ogg_free(codes);
   1.366 +
   1.367 +
   1.368 +    c->valuelist=_book_unquantize(s,n,sortindex);
   1.369 +    c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index));
   1.370 +
   1.371 +    for(n=0,i=0;i<s->entries;i++)
   1.372 +      if(s->lengthlist[i]>0)
   1.373 +        c->dec_index[sortindex[n++]]=i;
   1.374 +
   1.375 +    c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths));
   1.376 +    for(n=0,i=0;i<s->entries;i++)
   1.377 +      if(s->lengthlist[i]>0)
   1.378 +        c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
   1.379 +
   1.380 +    c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
   1.381 +    if(c->dec_firsttablen<5)c->dec_firsttablen=5;
   1.382 +    if(c->dec_firsttablen>8)c->dec_firsttablen=8;
   1.383 +
   1.384 +    tabn=1<<c->dec_firsttablen;
   1.385 +    c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
   1.386 +    c->dec_maxlength=0;
   1.387 +
   1.388 +    for(i=0;i<n;i++){
   1.389 +      if(c->dec_maxlength<c->dec_codelengths[i])
   1.390 +        c->dec_maxlength=c->dec_codelengths[i];
   1.391 +      if(c->dec_codelengths[i]<=c->dec_firsttablen){
   1.392 +        ogg_uint32_t orig=bitreverse(c->codelist[i]);
   1.393 +        for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
   1.394 +          c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
   1.395 +      }
   1.396 +    }
   1.397 +
   1.398 +    /* now fill in 'unused' entries in the firsttable with hi/lo search
   1.399 +       hints for the non-direct-hits */
   1.400 +    {
   1.401 +      ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
   1.402 +      long lo=0,hi=0;
   1.403 +
   1.404 +      for(i=0;i<tabn;i++){
   1.405 +        ogg_uint32_t word=i<<(32-c->dec_firsttablen);
   1.406 +        if(c->dec_firsttable[bitreverse(word)]==0){
   1.407 +          while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
   1.408 +          while(    hi<n && word>=(c->codelist[hi]&mask))hi++;
   1.409 +
   1.410 +          /* we only actually have 15 bits per hint to play with here.
   1.411 +             In order to overflow gracefully (nothing breaks, efficiency
   1.412 +             just drops), encode as the difference from the extremes. */
   1.413 +          {
   1.414 +            unsigned long loval=lo;
   1.415 +            unsigned long hival=n-hi;
   1.416 +
   1.417 +            if(loval>0x7fff)loval=0x7fff;
   1.418 +            if(hival>0x7fff)hival=0x7fff;
   1.419 +            c->dec_firsttable[bitreverse(word)]=
   1.420 +              0x80000000UL | (loval<<15) | hival;
   1.421 +          }
   1.422 +        }
   1.423 +      }
   1.424 +    }
   1.425 +  }
   1.426 +
   1.427 +  return(0);
   1.428 + err_out:
   1.429 +  vorbis_book_clear(c);
   1.430 +  return(-1);
   1.431 +}
   1.432 +
   1.433 +long vorbis_book_codeword(codebook *book,int entry){
   1.434 +  if(book->c) /* only use with encode; decode optimizations are
   1.435 +                 allowed to break this */
   1.436 +    return book->codelist[entry];
   1.437 +  return -1;
   1.438 +}
   1.439 +
   1.440 +long vorbis_book_codelen(codebook *book,int entry){
   1.441 +  if(book->c) /* only use with encode; decode optimizations are
   1.442 +                 allowed to break this */
   1.443 +    return book->c->lengthlist[entry];
   1.444 +  return -1;
   1.445 +}
   1.446 +
   1.447 +#ifdef _V_SELFTEST
   1.448 +
   1.449 +/* Unit tests of the dequantizer; this stuff will be OK
   1.450 +   cross-platform, I simply want to be sure that special mapping cases
   1.451 +   actually work properly; a bug could go unnoticed for a while */
   1.452 +
   1.453 +#include <stdio.h>
   1.454 +
   1.455 +/* cases:
   1.456 +
   1.457 +   no mapping
   1.458 +   full, explicit mapping
   1.459 +   algorithmic mapping
   1.460 +
   1.461 +   nonsequential
   1.462 +   sequential
   1.463 +*/
   1.464 +
   1.465 +static long full_quantlist1[]={0,1,2,3,    4,5,6,7, 8,3,6,1};
   1.466 +static long partial_quantlist1[]={0,7,2};
   1.467 +
   1.468 +/* no mapping */
   1.469 +static_codebook test1={
   1.470 +  4,16,
   1.471 +  NULL,
   1.472 +  0,
   1.473 +  0,0,0,0,
   1.474 +  NULL,
   1.475 +  0
   1.476 +};
   1.477 +static float *test1_result=NULL;
   1.478 +
   1.479 +/* linear, full mapping, nonsequential */
   1.480 +static_codebook test2={
   1.481 +  4,3,
   1.482 +  NULL,
   1.483 +  2,
   1.484 +  -533200896,1611661312,4,0,
   1.485 +  full_quantlist1,
   1.486 +  0
   1.487 +};
   1.488 +static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
   1.489 +
   1.490 +/* linear, full mapping, sequential */
   1.491 +static_codebook test3={
   1.492 +  4,3,
   1.493 +  NULL,
   1.494 +  2,
   1.495 +  -533200896,1611661312,4,1,
   1.496 +  full_quantlist1,
   1.497 +  0
   1.498 +};
   1.499 +static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
   1.500 +
   1.501 +/* linear, algorithmic mapping, nonsequential */
   1.502 +static_codebook test4={
   1.503 +  3,27,
   1.504 +  NULL,
   1.505 +  1,
   1.506 +  -533200896,1611661312,4,0,
   1.507 +  partial_quantlist1,
   1.508 +  0
   1.509 +};
   1.510 +static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
   1.511 +                              -3, 4,-3, 4, 4,-3, -1, 4,-3,
   1.512 +                              -3,-1,-3, 4,-1,-3, -1,-1,-3,
   1.513 +                              -3,-3, 4, 4,-3, 4, -1,-3, 4,
   1.514 +                              -3, 4, 4, 4, 4, 4, -1, 4, 4,
   1.515 +                              -3,-1, 4, 4,-1, 4, -1,-1, 4,
   1.516 +                              -3,-3,-1, 4,-3,-1, -1,-3,-1,
   1.517 +                              -3, 4,-1, 4, 4,-1, -1, 4,-1,
   1.518 +                              -3,-1,-1, 4,-1,-1, -1,-1,-1};
   1.519 +
   1.520 +/* linear, algorithmic mapping, sequential */
   1.521 +static_codebook test5={
   1.522 +  3,27,
   1.523 +  NULL,
   1.524 +  1,
   1.525 +  -533200896,1611661312,4,1,
   1.526 +  partial_quantlist1,
   1.527 +  0
   1.528 +};
   1.529 +static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
   1.530 +                              -3, 1,-2, 4, 8, 5, -1, 3, 0,
   1.531 +                              -3,-4,-7, 4, 3, 0, -1,-2,-5,
   1.532 +                              -3,-6,-2, 4, 1, 5, -1,-4, 0,
   1.533 +                              -3, 1, 5, 4, 8,12, -1, 3, 7,
   1.534 +                              -3,-4, 0, 4, 3, 7, -1,-2, 2,
   1.535 +                              -3,-6,-7, 4, 1, 0, -1,-4,-5,
   1.536 +                              -3, 1, 0, 4, 8, 7, -1, 3, 2,
   1.537 +                              -3,-4,-5, 4, 3, 2, -1,-2,-3};
   1.538 +
   1.539 +void run_test(static_codebook *b,float *comp){
   1.540 +  float *out=_book_unquantize(b,b->entries,NULL);
   1.541 +  int i;
   1.542 +
   1.543 +  if(comp){
   1.544 +    if(!out){
   1.545 +      fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
   1.546 +      exit(1);
   1.547 +    }
   1.548 +
   1.549 +    for(i=0;i<b->entries*b->dim;i++)
   1.550 +      if(fabs(out[i]-comp[i])>.0001){
   1.551 +        fprintf(stderr,"disagreement in unquantized and reference data:\n"
   1.552 +                "position %d, %g != %g\n",i,out[i],comp[i]);
   1.553 +        exit(1);
   1.554 +      }
   1.555 +
   1.556 +  }else{
   1.557 +    if(out){
   1.558 +      fprintf(stderr,"_book_unquantize returned a value array: \n"
   1.559 +              " correct result should have been NULL\n");
   1.560 +      exit(1);
   1.561 +    }
   1.562 +  }
   1.563 +}
   1.564 +
   1.565 +int main(){
   1.566 +  /* run the nine dequant tests, and compare to the hand-rolled results */
   1.567 +  fprintf(stderr,"Dequant test 1... ");
   1.568 +  run_test(&test1,test1_result);
   1.569 +  fprintf(stderr,"OK\nDequant test 2... ");
   1.570 +  run_test(&test2,test2_result);
   1.571 +  fprintf(stderr,"OK\nDequant test 3... ");
   1.572 +  run_test(&test3,test3_result);
   1.573 +  fprintf(stderr,"OK\nDequant test 4... ");
   1.574 +  run_test(&test4,test4_result);
   1.575 +  fprintf(stderr,"OK\nDequant test 5... ");
   1.576 +  run_test(&test5,test5_result);
   1.577 +  fprintf(stderr,"OK\n\n");
   1.578 +
   1.579 +  return(0);
   1.580 +}
   1.581 +
   1.582 +#endif