1 /********************************************************************
3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009 *
9 * by the Xiph.Org Foundation http://www.xiph.org/ *
11 ********************************************************************
13 function: basic shared codebook operations
16 ********************************************************************/
24 #include "vorbis/codec.h"
28 /**** pack/unpack helpers ******************************************/
29 int _ilog(unsigned int v){
38 /* 32 bit float (not IEEE; nonnormalized mantissa +
39 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
40 Why not IEEE? It's just not that important here. */
44 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
46 /* doesn't currently guard under/overflow */
47 long _float32_pack(float val){
55 exp= floor(log(val)/log(2.f)+.001); //+epsilon
56 mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
57 exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
59 return(sign|exp|mant);
62 float _float32_unpack(long val){
63 double mant=val&0x1fffff;
64 int sign=val&0x80000000;
65 long exp =(val&0x7fe00000L)>>VQ_FMAN;
67 return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
70 /* given a list of word lengths, generate a list of codewords. Works
71 for length ordered or unordered, always assigns the lowest valued
72 codewords first. Extended to handle unused entries (length 0) */
73 ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
75 ogg_uint32_t marker[33];
76 ogg_uint32_t *r=_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
77 memset(marker,0,sizeof(marker));
82 ogg_uint32_t entry=marker[length];
84 /* when we claim a node for an entry, we also claim the nodes
85 below it (pruning off the imagined tree that may have dangled
86 from it) as well as blocking the use of any nodes directly
90 if(length<32 && (entry>>length)){
91 /* error condition; the lengths must specify an overpopulated tree */
97 /* Look to see if the next shorter marker points to the node
98 above. if so, update it and repeat. */
100 for(j=length;j>0;j--){
103 /* have to jump branches */
107 marker[j]=marker[j-1]<<1;
108 break; /* invariant says next upper marker would already
109 have been moved if it was on the same path */
115 /* prune the tree; the implicit invariant says all the longer
116 markers were dangling from our just-taken node. Dangle them
117 from our *new* node. */
118 for(j=length+1;j<33;j++)
119 if((marker[j]>>1) == entry){
121 marker[j]=marker[j-1]<<1;
125 if(sparsecount==0)count++;
128 /* sanity check the huffman tree; an underpopulated tree must be
129 rejected. The only exception is the one-node pseudo-nil tree,
130 which appears to be underpopulated because the tree doesn't
131 really exist; there's only one possible 'codeword' or zero bits,
132 but the above tree-gen code doesn't mark that. */
133 if(sparsecount != 1){
135 if(marker[i] & (0xffffffffUL>>(32-i))){
141 /* bitreverse the words because our bitwise packer/unpacker is LSb
143 for(i=0,count=0;i<n;i++){
147 temp|=(r[count]>>j)&1;
160 /* there might be a straightforward one-line way to do the below
161 that's portable and totally safe against roundoff, but I haven't
162 thought of it. Therefore, we opt on the side of caution */
163 long _book_maptype1_quantvals(const static_codebook *b){
164 long vals=floor(pow((float)b->entries,1.f/b->dim));
166 /* the above *should* be reliable, but we'll not assume that FP is
167 ever reliable when bitstream sync is at stake; verify via integer
168 means that vals really is the greatest value of dim for which
169 vals^b->bim <= b->entries */
170 /* treat the above as an initial guess */
175 for(i=0;i<b->dim;i++){
179 if(acc<=b->entries && acc1>b->entries){
191 /* unpack the quantized list of values for encode/decode ***********/
192 /* we need to deal with two map types: in map type 1, the values are
193 generated algorithmically (each column of the vector counts through
194 the values in the quant vector). in map type 2, all the values came
195 in in an explicit list. Both value lists must be unpacked */
196 float *_book_unquantize(const static_codebook *b,int n,int *sparsemap){
198 if(b->maptype==1 || b->maptype==2){
200 float mindel=_float32_unpack(b->q_min);
201 float delta=_float32_unpack(b->q_delta);
202 float *r=_ogg_calloc(n*b->dim,sizeof(*r));
204 /* maptype 1 and 2 both use a quantized value vector, but
208 /* most of the time, entries%dimensions == 0, but we need to be
209 well defined. We define that the possible vales at each
210 scalar is values == entries/dim. If entries%dim != 0, we'll
211 have 'too few' values (values*dim<entries), which means that
212 we'll have 'left over' entries; left over entries use zeroed
213 values (and are wasted). So don't generate codebooks like
215 quantvals=_book_maptype1_quantvals(b);
216 for(j=0;j<b->entries;j++){
217 if((sparsemap && b->lengthlist[j]) || !sparsemap){
220 for(k=0;k<b->dim;k++){
221 int index= (j/indexdiv)%quantvals;
222 float val=b->quantlist[index];
223 val=fabs(val)*delta+mindel+last;
224 if(b->q_sequencep)last=val;
226 r[sparsemap[count]*b->dim+k]=val;
228 r[count*b->dim+k]=val;
237 for(j=0;j<b->entries;j++){
238 if((sparsemap && b->lengthlist[j]) || !sparsemap){
241 for(k=0;k<b->dim;k++){
242 float val=b->quantlist[j*b->dim+k];
243 val=fabs(val)*delta+mindel+last;
244 if(b->q_sequencep)last=val;
246 r[sparsemap[count]*b->dim+k]=val;
248 r[count*b->dim+k]=val;
261 void vorbis_staticbook_clear(static_codebook *b){
263 if(b->quantlist)_ogg_free(b->quantlist);
264 if(b->lengthlist)_ogg_free(b->lengthlist);
265 memset(b,0,sizeof(*b));
269 void vorbis_staticbook_destroy(static_codebook *b){
271 vorbis_staticbook_clear(b);
276 void vorbis_book_clear(codebook *b){
277 /* static book is not cleared; we're likely called on the lookup and
278 the static codebook belongs to the info struct */
279 if(b->valuelist)_ogg_free(b->valuelist);
280 if(b->codelist)_ogg_free(b->codelist);
282 if(b->dec_index)_ogg_free(b->dec_index);
283 if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
284 if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
286 memset(b,0,sizeof(*b));
289 int vorbis_book_init_encode(codebook *c,const static_codebook *s){
291 memset(c,0,sizeof(*c));
293 c->entries=s->entries;
294 c->used_entries=s->entries;
296 c->codelist=_make_words(s->lengthlist,s->entries,0);
297 //c->valuelist=_book_unquantize(s,s->entries,NULL);
298 c->quantvals=_book_maptype1_quantvals(s);
299 c->minval=(int)rint(_float32_unpack(s->q_min));
300 c->delta=(int)rint(_float32_unpack(s->q_delta));
305 static ogg_uint32_t bitreverse(ogg_uint32_t x){
306 x= ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
307 x= ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
308 x= ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
309 x= ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
310 return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
313 static int sort32a(const void *a,const void *b){
314 return ( **(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
315 ( **(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
318 /* decode codebook arrangement is more heavily optimized than encode */
319 int vorbis_book_init_decode(codebook *c,const static_codebook *s){
322 memset(c,0,sizeof(*c));
324 /* count actually used entries */
325 for(i=0;i<s->entries;i++)
326 if(s->lengthlist[i]>0)
329 c->entries=s->entries;
335 /* two different remappings go on here.
337 First, we collapse the likely sparse codebook down only to
338 actually represented values/words. This collapsing needs to be
339 indexed as map-valueless books are used to encode original entry
340 positions as integers.
342 Second, we reorder all vectors, including the entry index above,
343 by sorted bitreversed codeword to allow treeless decode. */
346 ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
347 ogg_uint32_t **codep=alloca(sizeof(*codep)*n);
349 if(codes==NULL)goto err_out;
352 codes[i]=bitreverse(codes[i]);
356 qsort(codep,n,sizeof(*codep),sort32a);
358 sortindex=alloca(n*sizeof(*sortindex));
359 c->codelist=_ogg_malloc(n*sizeof(*c->codelist));
360 /* the index is a reverse index */
362 int position=codep[i]-codes;
363 sortindex[position]=i;
367 c->codelist[sortindex[i]]=codes[i];
371 c->valuelist=_book_unquantize(s,n,sortindex);
372 c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index));
374 for(n=0,i=0;i<s->entries;i++)
375 if(s->lengthlist[i]>0)
376 c->dec_index[sortindex[n++]]=i;
378 c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths));
379 for(n=0,i=0;i<s->entries;i++)
380 if(s->lengthlist[i]>0)
381 c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
383 c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
384 if(c->dec_firsttablen<5)c->dec_firsttablen=5;
385 if(c->dec_firsttablen>8)c->dec_firsttablen=8;
387 tabn=1<<c->dec_firsttablen;
388 c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
392 if(c->dec_maxlength<c->dec_codelengths[i])
393 c->dec_maxlength=c->dec_codelengths[i];
394 if(c->dec_codelengths[i]<=c->dec_firsttablen){
395 ogg_uint32_t orig=bitreverse(c->codelist[i]);
396 for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
397 c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
401 /* now fill in 'unused' entries in the firsttable with hi/lo search
402 hints for the non-direct-hits */
404 ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
408 ogg_uint32_t word=i<<(32-c->dec_firsttablen);
409 if(c->dec_firsttable[bitreverse(word)]==0){
410 while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
411 while( hi<n && word>=(c->codelist[hi]&mask))hi++;
413 /* we only actually have 15 bits per hint to play with here.
414 In order to overflow gracefully (nothing breaks, efficiency
415 just drops), encode as the difference from the extremes. */
417 unsigned long loval=lo;
418 unsigned long hival=n-hi;
420 if(loval>0x7fff)loval=0x7fff;
421 if(hival>0x7fff)hival=0x7fff;
422 c->dec_firsttable[bitreverse(word)]=
423 0x80000000UL | (loval<<15) | hival;
432 vorbis_book_clear(c);
436 long vorbis_book_codeword(codebook *book,int entry){
437 if(book->c) /* only use with encode; decode optimizations are
438 allowed to break this */
439 return book->codelist[entry];
443 long vorbis_book_codelen(codebook *book,int entry){
444 if(book->c) /* only use with encode; decode optimizations are
445 allowed to break this */
446 return book->c->lengthlist[entry];
452 /* Unit tests of the dequantizer; this stuff will be OK
453 cross-platform, I simply want to be sure that special mapping cases
454 actually work properly; a bug could go unnoticed for a while */
461 full, explicit mapping
468 static long full_quantlist1[]={0,1,2,3, 4,5,6,7, 8,3,6,1};
469 static long partial_quantlist1[]={0,7,2};
472 static_codebook test1={
480 static float *test1_result=NULL;
482 /* linear, full mapping, nonsequential */
483 static_codebook test2={
487 -533200896,1611661312,4,0,
491 static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
493 /* linear, full mapping, sequential */
494 static_codebook test3={
498 -533200896,1611661312,4,1,
502 static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
504 /* linear, algorithmic mapping, nonsequential */
505 static_codebook test4={
509 -533200896,1611661312,4,0,
513 static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
514 -3, 4,-3, 4, 4,-3, -1, 4,-3,
515 -3,-1,-3, 4,-1,-3, -1,-1,-3,
516 -3,-3, 4, 4,-3, 4, -1,-3, 4,
517 -3, 4, 4, 4, 4, 4, -1, 4, 4,
518 -3,-1, 4, 4,-1, 4, -1,-1, 4,
519 -3,-3,-1, 4,-3,-1, -1,-3,-1,
520 -3, 4,-1, 4, 4,-1, -1, 4,-1,
521 -3,-1,-1, 4,-1,-1, -1,-1,-1};
523 /* linear, algorithmic mapping, sequential */
524 static_codebook test5={
528 -533200896,1611661312,4,1,
532 static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
533 -3, 1,-2, 4, 8, 5, -1, 3, 0,
534 -3,-4,-7, 4, 3, 0, -1,-2,-5,
535 -3,-6,-2, 4, 1, 5, -1,-4, 0,
536 -3, 1, 5, 4, 8,12, -1, 3, 7,
537 -3,-4, 0, 4, 3, 7, -1,-2, 2,
538 -3,-6,-7, 4, 1, 0, -1,-4,-5,
539 -3, 1, 0, 4, 8, 7, -1, 3, 2,
540 -3,-4,-5, 4, 3, 2, -1,-2,-3};
542 void run_test(static_codebook *b,float *comp){
543 float *out=_book_unquantize(b,b->entries,NULL);
548 fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
552 for(i=0;i<b->entries*b->dim;i++)
553 if(fabs(out[i]-comp[i])>.0001){
554 fprintf(stderr,"disagreement in unquantized and reference data:\n"
555 "position %d, %g != %g\n",i,out[i],comp[i]);
561 fprintf(stderr,"_book_unquantize returned a value array: \n"
562 " correct result should have been NULL\n");
569 /* run the nine dequant tests, and compare to the hand-rolled results */
570 fprintf(stderr,"Dequant test 1... ");
571 run_test(&test1,test1_result);
572 fprintf(stderr,"OK\nDequant test 2... ");
573 run_test(&test2,test2_result);
574 fprintf(stderr,"OK\nDequant test 3... ");
575 run_test(&test3,test3_result);
576 fprintf(stderr,"OK\nDequant test 4... ");
577 run_test(&test4,test4_result);
578 fprintf(stderr,"OK\nDequant test 5... ");
579 run_test(&test5,test5_result);
580 fprintf(stderr,"OK\n\n");