1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libtremor/lib/tremor_sharedbook.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,447 @@
1.4 +/********************************************************************
1.5 + * *
1.6 + * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. *
1.7 + * *
1.8 + * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
1.9 + * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
1.10 + * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
1.11 + * *
1.12 + * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002 *
1.13 + * BY THE Xiph.Org FOUNDATION http://www.xiph.org/ *
1.14 + * *
1.15 + ********************************************************************
1.16 +
1.17 + function: basic shared codebook operations
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 "misc.h"
1.26 +#include "ivorbiscodec.h"
1.27 +#include "codebook.h"
1.28 +
1.29 +/**** pack/unpack helpers ******************************************/
1.30 +int _ilog(unsigned int v){
1.31 + int ret=0;
1.32 + while(v){
1.33 + ret++;
1.34 + v>>=1;
1.35 + }
1.36 + return(ret);
1.37 +}
1.38 +
1.39 +/* 32 bit float (not IEEE; nonnormalized mantissa +
1.40 + biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
1.41 + Why not IEEE? It's just not that important here. */
1.42 +
1.43 +#define VQ_FEXP 10
1.44 +#define VQ_FMAN 21
1.45 +#define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
1.46 +
1.47 +static ogg_int32_t _float32_unpack(long val,int *point){
1.48 + long mant=val&0x1fffff;
1.49 + int sign=val&0x80000000;
1.50 + long exp =(val&0x7fe00000L)>>VQ_FMAN;
1.51 +
1.52 + exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS;
1.53 +
1.54 + if(mant){
1.55 + while(!(mant&0x40000000)){
1.56 + mant<<=1;
1.57 + exp-=1;
1.58 + }
1.59 +
1.60 + if(sign)mant= -mant;
1.61 + }else{
1.62 + sign=0;
1.63 + exp=-9999;
1.64 + }
1.65 +
1.66 + *point=exp;
1.67 + return mant;
1.68 +}
1.69 +
1.70 +/* given a list of word lengths, generate a list of codewords. Works
1.71 + for length ordered or unordered, always assigns the lowest valued
1.72 + codewords first. Extended to handle unused entries (length 0) */
1.73 +ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
1.74 + long i,j,count=0;
1.75 + ogg_uint32_t marker[33];
1.76 + ogg_uint32_t *r=(ogg_uint32_t *)_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
1.77 + memset(marker,0,sizeof(marker));
1.78 +
1.79 + for(i=0;i<n;i++){
1.80 + long length=l[i];
1.81 + if(length>0){
1.82 + ogg_uint32_t entry=marker[length];
1.83 +
1.84 + /* when we claim a node for an entry, we also claim the nodes
1.85 + below it (pruning off the imagined tree that may have dangled
1.86 + from it) as well as blocking the use of any nodes directly
1.87 + above for leaves */
1.88 +
1.89 + /* update ourself */
1.90 + if(length<32 && (entry>>length)){
1.91 + /* error condition; the lengths must specify an overpopulated tree */
1.92 + _ogg_free(r);
1.93 + return(NULL);
1.94 + }
1.95 + r[count++]=entry;
1.96 +
1.97 + /* Look to see if the next shorter marker points to the node
1.98 + above. if so, update it and repeat. */
1.99 + {
1.100 + for(j=length;j>0;j--){
1.101 +
1.102 + if(marker[j]&1){
1.103 + /* have to jump branches */
1.104 + if(j==1)
1.105 + marker[1]++;
1.106 + else
1.107 + marker[j]=marker[j-1]<<1;
1.108 + break; /* invariant says next upper marker would already
1.109 + have been moved if it was on the same path */
1.110 + }
1.111 + marker[j]++;
1.112 + }
1.113 + }
1.114 +
1.115 + /* prune the tree; the implicit invariant says all the longer
1.116 + markers were dangling from our just-taken node. Dangle them
1.117 + from our *new* node. */
1.118 + for(j=length+1;j<33;j++)
1.119 + if((marker[j]>>1) == entry){
1.120 + entry=marker[j];
1.121 + marker[j]=marker[j-1]<<1;
1.122 + }else
1.123 + break;
1.124 + }else
1.125 + if(sparsecount==0)count++;
1.126 + }
1.127 +
1.128 + /* sanity check the huffman tree; an underpopulated tree must be
1.129 + rejected. The only exception is the one-node pseudo-nil tree,
1.130 + which appears to be underpopulated because the tree doesn't
1.131 + really exist; there's only one possible 'codeword' or zero bits,
1.132 + but the above tree-gen code doesn't mark that. */
1.133 + if(sparsecount != 1){
1.134 + for(i=1;i<33;i++)
1.135 + if(marker[i] & (0xffffffffUL>>(32-i))){
1.136 + _ogg_free(r);
1.137 + return(NULL);
1.138 + }
1.139 + }
1.140 +
1.141 + /* bitreverse the words because our bitwise packer/unpacker is LSb
1.142 + endian */
1.143 + for(i=0,count=0;i<n;i++){
1.144 + ogg_uint32_t temp=0;
1.145 + for(j=0;j<l[i];j++){
1.146 + temp<<=1;
1.147 + temp|=(r[count]>>j)&1;
1.148 + }
1.149 +
1.150 + if(sparsecount){
1.151 + if(l[i])
1.152 + r[count++]=temp;
1.153 + }else
1.154 + r[count++]=temp;
1.155 + }
1.156 +
1.157 + return(r);
1.158 +}
1.159 +
1.160 +/* there might be a straightforward one-line way to do the below
1.161 + that's portable and totally safe against roundoff, but I haven't
1.162 + thought of it. Therefore, we opt on the side of caution */
1.163 +long _book_maptype1_quantvals(const static_codebook *b){
1.164 + /* get us a starting hint, we'll polish it below */
1.165 + int bits=_ilog(b->entries);
1.166 + int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
1.167 +
1.168 + while(1){
1.169 + long acc=1;
1.170 + long acc1=1;
1.171 + int i;
1.172 + for(i=0;i<b->dim;i++){
1.173 + acc*=vals;
1.174 + acc1*=vals+1;
1.175 + }
1.176 + if(acc<=b->entries && acc1>b->entries){
1.177 + return(vals);
1.178 + }else{
1.179 + if(acc>b->entries){
1.180 + vals--;
1.181 + }else{
1.182 + vals++;
1.183 + }
1.184 + }
1.185 + }
1.186 +}
1.187 +
1.188 +/* different than what _book_unquantize does for mainline:
1.189 + we repack the book in a fixed point format that shares the same
1.190 + binary point. Upon first use, we can shift point if needed */
1.191 +
1.192 +/* we need to deal with two map types: in map type 1, the values are
1.193 + generated algorithmically (each column of the vector counts through
1.194 + the values in the quant vector). in map type 2, all the values came
1.195 + in in an explicit list. Both value lists must be unpacked */
1.196 +
1.197 +ogg_int32_t *_book_unquantize(const static_codebook *b,int n,int *sparsemap,
1.198 + int *maxpoint){
1.199 + long j,k,count=0;
1.200 + if(b->maptype==1 || b->maptype==2){
1.201 + int quantvals;
1.202 + int minpoint,delpoint;
1.203 + ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint);
1.204 + ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint);
1.205 + ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r));
1.206 + int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp));
1.207 +
1.208 + *maxpoint=minpoint;
1.209 +
1.210 + /* maptype 1 and 2 both use a quantized value vector, but
1.211 + different sizes */
1.212 + switch(b->maptype){
1.213 + case 1:
1.214 + /* most of the time, entries%dimensions == 0, but we need to be
1.215 + well defined. We define that the possible vales at each
1.216 + scalar is values == entries/dim. If entries%dim != 0, we'll
1.217 + have 'too few' values (values*dim<entries), which means that
1.218 + we'll have 'left over' entries; left over entries use zeroed
1.219 + values (and are wasted). So don't generate codebooks like
1.220 + that */
1.221 + quantvals=_book_maptype1_quantvals(b);
1.222 + for(j=0;j<b->entries;j++){
1.223 + if((sparsemap && b->lengthlist[j]) || !sparsemap){
1.224 + ogg_int32_t last=0;
1.225 + int lastpoint=0;
1.226 + int indexdiv=1;
1.227 + for(k=0;k<b->dim;k++){
1.228 + int index= (j/indexdiv)%quantvals;
1.229 + int point=0;
1.230 + int val=VFLOAT_MULTI(delta,delpoint,
1.231 + abs(b->quantlist[index]),&point);
1.232 +
1.233 + val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
1.234 + val=VFLOAT_ADD(last,lastpoint,val,point,&point);
1.235 +
1.236 + if(b->q_sequencep){
1.237 + last=val;
1.238 + lastpoint=point;
1.239 + }
1.240 +
1.241 + if(sparsemap){
1.242 + r[sparsemap[count]*b->dim+k]=val;
1.243 + rp[sparsemap[count]*b->dim+k]=point;
1.244 + }else{
1.245 + r[count*b->dim+k]=val;
1.246 + rp[count*b->dim+k]=point;
1.247 + }
1.248 + if(*maxpoint<point)*maxpoint=point;
1.249 + indexdiv*=quantvals;
1.250 + }
1.251 + count++;
1.252 + }
1.253 +
1.254 + }
1.255 + break;
1.256 + case 2:
1.257 + for(j=0;j<b->entries;j++){
1.258 + if((sparsemap && b->lengthlist[j]) || !sparsemap){
1.259 + ogg_int32_t last=0;
1.260 + int lastpoint=0;
1.261 +
1.262 + for(k=0;k<b->dim;k++){
1.263 + int point=0;
1.264 + int val=VFLOAT_MULTI(delta,delpoint,
1.265 + abs(b->quantlist[j*b->dim+k]),&point);
1.266 +
1.267 + val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
1.268 + val=VFLOAT_ADD(last,lastpoint,val,point,&point);
1.269 +
1.270 + if(b->q_sequencep){
1.271 + last=val;
1.272 + lastpoint=point;
1.273 + }
1.274 +
1.275 + if(sparsemap){
1.276 + r[sparsemap[count]*b->dim+k]=val;
1.277 + rp[sparsemap[count]*b->dim+k]=point;
1.278 + }else{
1.279 + r[count*b->dim+k]=val;
1.280 + rp[count*b->dim+k]=point;
1.281 + }
1.282 + if(*maxpoint<point)*maxpoint=point;
1.283 + }
1.284 + count++;
1.285 + }
1.286 + }
1.287 + break;
1.288 + }
1.289 +
1.290 + for(j=0;j<n*b->dim;j++)
1.291 + if(rp[j]<*maxpoint)
1.292 + r[j]>>=*maxpoint-rp[j];
1.293 +
1.294 + _ogg_free(rp);
1.295 + return(r);
1.296 + }
1.297 + return(NULL);
1.298 +}
1.299 +
1.300 +void vorbis_staticbook_destroy(static_codebook *b){
1.301 + if(b->quantlist)_ogg_free(b->quantlist);
1.302 + if(b->lengthlist)_ogg_free(b->lengthlist);
1.303 + memset(b,0,sizeof(*b));
1.304 + _ogg_free(b);
1.305 +}
1.306 +
1.307 +void vorbis_book_clear(codebook *b){
1.308 + /* static book is not cleared; we're likely called on the lookup and
1.309 + the static codebook belongs to the info struct */
1.310 + if(b->valuelist)_ogg_free(b->valuelist);
1.311 + if(b->codelist)_ogg_free(b->codelist);
1.312 +
1.313 + if(b->dec_index)_ogg_free(b->dec_index);
1.314 + if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
1.315 + if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
1.316 +
1.317 + memset(b,0,sizeof(*b));
1.318 +}
1.319 +
1.320 +static ogg_uint32_t bitreverse(ogg_uint32_t x){
1.321 + x= ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
1.322 + x= ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
1.323 + x= ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
1.324 + x= ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
1.325 + return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
1.326 +}
1.327 +
1.328 +static int sort32a(const void *a,const void *b){
1.329 + return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
1.330 + (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
1.331 +}
1.332 +
1.333 +/* decode codebook arrangement is more heavily optimized than encode */
1.334 +int vorbis_book_init_decode(codebook *c,const static_codebook *s){
1.335 + int i,j,n=0,tabn;
1.336 + int *sortindex;
1.337 + memset(c,0,sizeof(*c));
1.338 +
1.339 + /* count actually used entries */
1.340 + for(i=0;i<s->entries;i++)
1.341 + if(s->lengthlist[i]>0)
1.342 + n++;
1.343 +
1.344 + c->entries=s->entries;
1.345 + c->used_entries=n;
1.346 + c->dim=s->dim;
1.347 +
1.348 + if(n>0){
1.349 + /* two different remappings go on here.
1.350 +
1.351 + First, we collapse the likely sparse codebook down only to
1.352 + actually represented values/words. This collapsing needs to be
1.353 + indexed as map-valueless books are used to encode original entry
1.354 + positions as integers.
1.355 +
1.356 + Second, we reorder all vectors, including the entry index above,
1.357 + by sorted bitreversed codeword to allow treeless decode. */
1.358 +
1.359 + /* perform sort */
1.360 + ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
1.361 + ogg_uint32_t **codep=(ogg_uint32_t **)alloca(sizeof(*codep)*n);
1.362 +
1.363 + if(codes==NULL)goto err_out;
1.364 +
1.365 + for(i=0;i<n;i++){
1.366 + codes[i]=bitreverse(codes[i]);
1.367 + codep[i]=codes+i;
1.368 + }
1.369 +
1.370 + qsort(codep,n,sizeof(*codep),sort32a);
1.371 +
1.372 + sortindex=(int *)alloca(n*sizeof(*sortindex));
1.373 + c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist));
1.374 + /* the index is a reverse index */
1.375 + for(i=0;i<n;i++){
1.376 + int position=codep[i]-codes;
1.377 + sortindex[position]=i;
1.378 + }
1.379 +
1.380 + for(i=0;i<n;i++)
1.381 + c->codelist[sortindex[i]]=codes[i];
1.382 + _ogg_free(codes);
1.383 +
1.384 +
1.385 +
1.386 + c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint);
1.387 + c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index));
1.388 +
1.389 + for(n=0,i=0;i<s->entries;i++)
1.390 + if(s->lengthlist[i]>0)
1.391 + c->dec_index[sortindex[n++]]=i;
1.392 +
1.393 + c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths));
1.394 + for(n=0,i=0;i<s->entries;i++)
1.395 + if(s->lengthlist[i]>0)
1.396 + c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
1.397 +
1.398 + c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
1.399 + if(c->dec_firsttablen<5)c->dec_firsttablen=5;
1.400 + if(c->dec_firsttablen>8)c->dec_firsttablen=8;
1.401 +
1.402 + tabn=1<<c->dec_firsttablen;
1.403 + c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
1.404 + c->dec_maxlength=0;
1.405 +
1.406 + for(i=0;i<n;i++){
1.407 + if(c->dec_maxlength<c->dec_codelengths[i])
1.408 + c->dec_maxlength=c->dec_codelengths[i];
1.409 + if(c->dec_codelengths[i]<=c->dec_firsttablen){
1.410 + ogg_uint32_t orig=bitreverse(c->codelist[i]);
1.411 + for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
1.412 + c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
1.413 + }
1.414 + }
1.415 +
1.416 + /* now fill in 'unused' entries in the firsttable with hi/lo search
1.417 + hints for the non-direct-hits */
1.418 + {
1.419 + ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
1.420 + long lo=0,hi=0;
1.421 +
1.422 + for(i=0;i<tabn;i++){
1.423 + ogg_uint32_t word=i<<(32-c->dec_firsttablen);
1.424 + if(c->dec_firsttable[bitreverse(word)]==0){
1.425 + while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
1.426 + while( hi<n && word>=(c->codelist[hi]&mask))hi++;
1.427 +
1.428 + /* we only actually have 15 bits per hint to play with here.
1.429 + In order to overflow gracefully (nothing breaks, efficiency
1.430 + just drops), encode as the difference from the extremes. */
1.431 + {
1.432 + unsigned long loval=lo;
1.433 + unsigned long hival=n-hi;
1.434 +
1.435 + if(loval>0x7fff)loval=0x7fff;
1.436 + if(hival>0x7fff)hival=0x7fff;
1.437 + c->dec_firsttable[bitreverse(word)]=
1.438 + 0x80000000UL | (loval<<15) | hival;
1.439 + }
1.440 + }
1.441 + }
1.442 + }
1.443 + }
1.444 +
1.445 + return(0);
1.446 + err_out:
1.447 + vorbis_book_clear(c);
1.448 + return(-1);
1.449 +}
1.450 +
