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-2015 *
9 * by the Xiph.Org Foundation http://www.xiph.org/ *
11 ********************************************************************
13 function: basic shared codebook operations
15 ********************************************************************/
24 #include "vorbis/codec.h"
28 /**** pack/unpack helpers ******************************************/
30 int ov_ilog(ogg_uint32_t v){
32 for(ret=0;v;ret++)v>>=1;
36 /* 32 bit float (not IEEE; nonnormalized mantissa +
37 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
38 Why not IEEE? It's just not that important here. */
42 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
44 /* doesn't currently guard under/overflow */
45 long _float32_pack(float val){
53 exp= floor(log(val)/log(2.f)+.001); //+epsilon
54 mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
55 exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
57 return(sign|exp|mant);
60 float _float32_unpack(long val){
61 double mant=val&0x1fffff;
62 int sign=val&0x80000000;
63 long exp =(val&0x7fe00000L)>>VQ_FMAN;
65 return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
68 /* given a list of word lengths, generate a list of codewords. Works
69 for length ordered or unordered, always assigns the lowest valued
70 codewords first. Extended to handle unused entries (length 0) */
71 ogg_uint32_t *_make_words(char *l,long n,long sparsecount){
73 ogg_uint32_t marker[33];
74 ogg_uint32_t *r=_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
75 memset(marker,0,sizeof(marker));
80 ogg_uint32_t entry=marker[length];
82 /* when we claim a node for an entry, we also claim the nodes
83 below it (pruning off the imagined tree that may have dangled
84 from it) as well as blocking the use of any nodes directly
88 if(length<32 && (entry>>length)){
89 /* error condition; the lengths must specify an overpopulated tree */
95 /* Look to see if the next shorter marker points to the node
96 above. if so, update it and repeat. */
98 for(j=length;j>0;j--){
101 /* have to jump branches */
105 marker[j]=marker[j-1]<<1;
106 break; /* invariant says next upper marker would already
107 have been moved if it was on the same path */
113 /* prune the tree; the implicit invariant says all the longer
114 markers were dangling from our just-taken node. Dangle them
115 from our *new* node. */
116 for(j=length+1;j<33;j++)
117 if((marker[j]>>1) == entry){
119 marker[j]=marker[j-1]<<1;
123 if(sparsecount==0)count++;
126 /* any underpopulated tree must be rejected. */
127 /* Single-entry codebooks are a retconned extension to the spec.
128 They have a single codeword '0' of length 1 that results in an
129 underpopulated tree. Shield that case from the underformed tree check. */
130 if(!(count==1 && marker[2]==2)){
132 if(marker[i] & (0xffffffffUL>>(32-i))){
138 /* bitreverse the words because our bitwise packer/unpacker is LSb
140 for(i=0,count=0;i<n;i++){
144 temp|=(r[count]>>j)&1;
157 /* there might be a straightforward one-line way to do the below
158 that's portable and totally safe against roundoff, but I haven't
159 thought of it. Therefore, we opt on the side of caution */
160 long _book_maptype1_quantvals(const static_codebook *b){
165 vals=floor(pow((float)b->entries,1.f/b->dim));
167 /* the above *should* be reliable, but we'll not assume that FP is
168 ever reliable when bitstream sync is at stake; verify via integer
169 means that vals really is the greatest value of dim for which
170 vals^b->bim <= b->entries */
171 /* treat the above as an initial guess */
179 for(i=0;i<b->dim;i++){
180 if(b->entries/vals<acc)break;
182 if(LONG_MAX/(vals+1)<acc1)acc1=LONG_MAX;
185 if(i>=b->dim && acc<=b->entries && acc1>b->entries){
188 if(i<b->dim || acc>b->entries){
197 /* unpack the quantized list of values for encode/decode ***********/
198 /* we need to deal with two map types: in map type 1, the values are
199 generated algorithmically (each column of the vector counts through
200 the values in the quant vector). in map type 2, all the values came
201 in in an explicit list. Both value lists must be unpacked */
202 float *_book_unquantize(const static_codebook *b,int n,int *sparsemap){
204 if(b->maptype==1 || b->maptype==2){
206 float mindel=_float32_unpack(b->q_min);
207 float delta=_float32_unpack(b->q_delta);
208 float *r=_ogg_calloc(n*b->dim,sizeof(*r));
210 /* maptype 1 and 2 both use a quantized value vector, but
214 /* most of the time, entries%dimensions == 0, but we need to be
215 well defined. We define that the possible vales at each
216 scalar is values == entries/dim. If entries%dim != 0, we'll
217 have 'too few' values (values*dim<entries), which means that
218 we'll have 'left over' entries; left over entries use zeroed
219 values (and are wasted). So don't generate codebooks like
221 quantvals=_book_maptype1_quantvals(b);
222 for(j=0;j<b->entries;j++){
223 if((sparsemap && b->lengthlist[j]) || !sparsemap){
226 for(k=0;k<b->dim;k++){
227 int index= (j/indexdiv)%quantvals;
228 float val=b->quantlist[index];
229 val=fabs(val)*delta+mindel+last;
230 if(b->q_sequencep)last=val;
232 r[sparsemap[count]*b->dim+k]=val;
234 r[count*b->dim+k]=val;
243 for(j=0;j<b->entries;j++){
244 if((sparsemap && b->lengthlist[j]) || !sparsemap){
247 for(k=0;k<b->dim;k++){
248 float val=b->quantlist[j*b->dim+k];
249 val=fabs(val)*delta+mindel+last;
250 if(b->q_sequencep)last=val;
252 r[sparsemap[count]*b->dim+k]=val;
254 r[count*b->dim+k]=val;
267 void vorbis_staticbook_destroy(static_codebook *b){
269 if(b->quantlist)_ogg_free(b->quantlist);
270 if(b->lengthlist)_ogg_free(b->lengthlist);
271 memset(b,0,sizeof(*b));
273 } /* otherwise, it is in static memory */
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){
323 memset(c,0,sizeof(*c));
325 /* count actually used entries and find max length */
326 for(i=0;i<s->entries;i++)
327 if(s->lengthlist[i]>0)
330 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];
370 c->valuelist=_book_unquantize(s,n,sortindex);
371 c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index));
373 for(n=0,i=0;i<s->entries;i++)
374 if(s->lengthlist[i]>0)
375 c->dec_index[sortindex[n++]]=i;
377 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];
382 if(s->lengthlist[i]>c->dec_maxlength)
383 c->dec_maxlength=s->lengthlist[i];
386 if(n==1 && c->dec_maxlength==1){
387 /* special case the 'single entry codebook' with a single bit
388 fastpath table (that always returns entry 0 )in order to use
389 unmodified decode paths. */
390 c->dec_firsttablen=1;
391 c->dec_firsttable=_ogg_calloc(2,sizeof(*c->dec_firsttable));
392 c->dec_firsttable[0]=c->dec_firsttable[1]=1;
395 c->dec_firsttablen=ov_ilog(c->used_entries)-4; /* this is magic */
396 if(c->dec_firsttablen<5)c->dec_firsttablen=5;
397 if(c->dec_firsttablen>8)c->dec_firsttablen=8;
399 tabn=1<<c->dec_firsttablen;
400 c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
403 if(c->dec_codelengths[i]<=c->dec_firsttablen){
404 ogg_uint32_t orig=bitreverse(c->codelist[i]);
405 for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
406 c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
410 /* now fill in 'unused' entries in the firsttable with hi/lo search
411 hints for the non-direct-hits */
413 ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
417 ogg_uint32_t word=i<<(32-c->dec_firsttablen);
418 if(c->dec_firsttable[bitreverse(word)]==0){
419 while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
420 while( hi<n && word>=(c->codelist[hi]&mask))hi++;
422 /* we only actually have 15 bits per hint to play with here.
423 In order to overflow gracefully (nothing breaks, efficiency
424 just drops), encode as the difference from the extremes. */
426 unsigned long loval=lo;
427 unsigned long hival=n-hi;
429 if(loval>0x7fff)loval=0x7fff;
430 if(hival>0x7fff)hival=0x7fff;
431 c->dec_firsttable[bitreverse(word)]=
432 0x80000000UL | (loval<<15) | hival;
442 vorbis_book_clear(c);
446 long vorbis_book_codeword(codebook *book,int entry){
447 if(book->c) /* only use with encode; decode optimizations are
448 allowed to break this */
449 return book->codelist[entry];
453 long vorbis_book_codelen(codebook *book,int entry){
454 if(book->c) /* only use with encode; decode optimizations are
455 allowed to break this */
456 return book->c->lengthlist[entry];
462 /* Unit tests of the dequantizer; this stuff will be OK
463 cross-platform, I simply want to be sure that special mapping cases
464 actually work properly; a bug could go unnoticed for a while */
471 full, explicit mapping
478 static long full_quantlist1[]={0,1,2,3, 4,5,6,7, 8,3,6,1};
479 static long partial_quantlist1[]={0,7,2};
482 static_codebook test1={
490 static float *test1_result=NULL;
492 /* linear, full mapping, nonsequential */
493 static_codebook test2={
497 -533200896,1611661312,4,0,
501 static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
503 /* linear, full mapping, sequential */
504 static_codebook test3={
508 -533200896,1611661312,4,1,
512 static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
514 /* linear, algorithmic mapping, nonsequential */
515 static_codebook test4={
519 -533200896,1611661312,4,0,
523 static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
524 -3, 4,-3, 4, 4,-3, -1, 4,-3,
525 -3,-1,-3, 4,-1,-3, -1,-1,-3,
526 -3,-3, 4, 4,-3, 4, -1,-3, 4,
527 -3, 4, 4, 4, 4, 4, -1, 4, 4,
528 -3,-1, 4, 4,-1, 4, -1,-1, 4,
529 -3,-3,-1, 4,-3,-1, -1,-3,-1,
530 -3, 4,-1, 4, 4,-1, -1, 4,-1,
531 -3,-1,-1, 4,-1,-1, -1,-1,-1};
533 /* linear, algorithmic mapping, sequential */
534 static_codebook test5={
538 -533200896,1611661312,4,1,
542 static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
543 -3, 1,-2, 4, 8, 5, -1, 3, 0,
544 -3,-4,-7, 4, 3, 0, -1,-2,-5,
545 -3,-6,-2, 4, 1, 5, -1,-4, 0,
546 -3, 1, 5, 4, 8,12, -1, 3, 7,
547 -3,-4, 0, 4, 3, 7, -1,-2, 2,
548 -3,-6,-7, 4, 1, 0, -1,-4,-5,
549 -3, 1, 0, 4, 8, 7, -1, 3, 2,
550 -3,-4,-5, 4, 3, 2, -1,-2,-3};
552 void run_test(static_codebook *b,float *comp){
553 float *out=_book_unquantize(b,b->entries,NULL);
558 fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
562 for(i=0;i<b->entries*b->dim;i++)
563 if(fabs(out[i]-comp[i])>.0001){
564 fprintf(stderr,"disagreement in unquantized and reference data:\n"
565 "position %d, %g != %g\n",i,out[i],comp[i]);
571 fprintf(stderr,"_book_unquantize returned a value array: \n"
572 " correct result should have been NULL\n");
579 /* run the nine dequant tests, and compare to the hand-rolled results */
580 fprintf(stderr,"Dequant test 1... ");
581 run_test(&test1,test1_result);
582 fprintf(stderr,"OK\nDequant test 2... ");
583 run_test(&test2,test2_result);
584 fprintf(stderr,"OK\nDequant test 3... ");
585 run_test(&test3,test3_result);
586 fprintf(stderr,"OK\nDequant test 4... ");
587 run_test(&test4,test4_result);
588 fprintf(stderr,"OK\nDequant test 5... ");
589 run_test(&test5,test5_result);
590 fprintf(stderr,"OK\n\n");