1 /********************************************************************
3 * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *
6 * PLEASE READ THESE TERMS DISTRIBUTING. *
8 * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
9 * by Monty <monty@xiph.org> and The XIPHOPHORUS Company *
10 * http://www.xiph.org/ *
12 ********************************************************************
14 function: basic shared codebook operations
15 last mod: $Id: sharedbook.c,v 1.4 2000/06/14 01:38:32 xiphmont Exp $
17 ********************************************************************/
23 #include "vorbis/codec.h"
24 #include "vorbis/codebook.h"
27 #include "sharedbook.h"
29 /**** pack/unpack helpers ******************************************/
30 int _ilog(unsigned int v){
39 /* 32 bit float (not IEEE; nonnormalized mantissa +
40 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
41 Why not IEEE? It's just not that important here. */
45 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
47 /* doesn't currently guard under/overflow */
48 long _float32_pack(double val){
56 exp= floor(log(val)/log(2));
57 mant=rint(ldexp(val,(VQ_FMAN-1)-exp));
58 exp=(exp+VQ_FEXP_BIAS)<<VQ_FMAN;
60 return(sign|exp|mant);
63 double _float32_unpack(long val){
64 double mant=val&0x1fffff;
65 double sign=val&0x80000000;
66 double exp =(val&0x7fe00000)>>VQ_FMAN;
68 return(ldexp(mant,exp-(VQ_FMAN-1)-VQ_FEXP_BIAS));
71 /* given a list of word lengths, generate a list of codewords. Works
72 for length ordered or unordered, always assigns the lowest valued
73 codewords first. Extended to handle unused entries (length 0) */
74 long *_make_words(long *l,long n){
77 long *r=malloc(n*sizeof(long));
78 memset(marker,0,sizeof(marker));
83 long entry=marker[length];
85 /* when we claim a node for an entry, we also claim the nodes
86 below it (pruning off the imagined tree that may have dangled
87 from it) as well as blocking the use of any nodes directly
91 if(length<32 && (entry>>length)){
92 /* error condition; the lengths must specify an overpopulated tree */
98 /* Look to see if the next shorter marker points to the node
99 above. if so, update it and repeat. */
101 for(j=length;j>0;j--){
104 /* have to jump branches */
108 marker[j]=marker[j-1]<<1;
109 break; /* invariant says next upper marker would already
110 have been moved if it was on the same path */
116 /* prune the tree; the implicit invariant says all the longer
117 markers were dangling from our just-taken node. Dangle them
118 from our *new* node. */
119 for(j=length+1;j<33;j++)
120 if((marker[j]>>1) == entry){
122 marker[j]=marker[j-1]<<1;
128 /* bitreverse the words because our bitwise packer/unpacker is LSb
142 /* build the decode helper tree from the codewords */
143 decode_aux *_make_decode_tree(codebook *c){
144 const static_codebook *s=c->c;
146 decode_aux *t=malloc(sizeof(decode_aux));
147 long *ptr0=t->ptr0=calloc(c->entries*2,sizeof(long));
148 long *ptr1=t->ptr1=calloc(c->entries*2,sizeof(long));
149 long *codelist=_make_words(s->lengthlist,s->entries);
151 if(codelist==NULL)return(NULL);
154 for(i=0;i<c->entries;i++){
155 if(s->lengthlist[i]>0){
157 for(j=0;j<s->lengthlist[i]-1;j++){
158 int bit=(codelist[i]>>j)&1;
169 if(!((codelist[i]>>j)&1))
179 /* there might be a straightforward one-line way to do the below
180 that's portable and totally safe against roundoff, but I haven't
181 thought of it. Therefore, we opt on the side of caution */
182 long _book_maptype1_quantvals(const static_codebook *b){
183 long vals=floor(pow(b->entries,1./b->dim));
185 /* the above *should* be reliable, but we'll not assume that FP is
186 ever reliable when bitstream sync is at stake; verify via integer
187 means that vals really is the greatest value of dim for which
188 vals^b->bim <= b->entries */
189 /* treat the above as an initial guess */
194 for(i=0;i<b->dim;i++){
198 if(acc<=b->entries && acc1>b->entries){
210 /* unpack the quantized list of values for encode/decode ***********/
211 /* we need to deal with two map types: in map type 1, the values are
212 generated algorithmically (each column of the vector counts through
213 the values in the quant vector). in map type 2, all the values came
214 in in an explicit list. Both value lists must be unpacked */
215 double *_book_unquantize(const static_codebook *b){
217 if(b->maptype==1 || b->maptype==2){
219 double mindel=_float32_unpack(b->q_min);
220 double delta=_float32_unpack(b->q_delta);
221 double *r=calloc(b->entries*b->dim,sizeof(double));
223 /* maptype 1 and 2 both use a quantized value vector, but
227 /* most of the time, entries%dimensions == 0, but we need to be
228 well defined. We define that the possible vales at each
229 scalar is values == entries/dim. If entries%dim != 0, we'll
230 have 'too few' values (values*dim<entries), which means that
231 we'll have 'left over' entries; left over entries use zeroed
232 values (and are wasted). So don't generate codebooks like
234 quantvals=_book_maptype1_quantvals(b);
235 for(j=0;j<b->entries;j++){
238 for(k=0;k<b->dim;k++){
239 int index= (j/indexdiv)%quantvals;
240 double val=b->quantlist[index];
241 val=fabs(val)*delta+mindel+last;
242 if(b->q_sequencep)last=val;
249 for(j=0;j<b->entries;j++){
251 for(k=0;k<b->dim;k++){
252 double val=b->quantlist[j*b->dim+k];
253 val=fabs(val)*delta+mindel+last;
254 if(b->q_sequencep)last=val;
264 void vorbis_staticbook_clear(static_codebook *b){
265 if(b->quantlist)free(b->quantlist);
266 if(b->lengthlist)free(b->lengthlist);
268 free(b->nearest_tree->ptr0);
269 free(b->nearest_tree->ptr1);
270 free(b->nearest_tree->p);
271 free(b->nearest_tree->q);
272 memset(b->nearest_tree,0,sizeof(encode_aux_nearestmatch));
273 free(b->nearest_tree);
276 free(b->thresh_tree->quantthresh);
277 free(b->thresh_tree->quantmap);
278 memset(b->thresh_tree,0,sizeof(encode_aux_threshmatch));
279 free(b->thresh_tree);
281 memset(b,0,sizeof(static_codebook));
284 void vorbis_book_clear(codebook *b){
285 /* static book is not cleared; we're likely called on the lookup and
286 the static codebook belongs to the info struct */
288 free(b->decode_tree->ptr0);
289 free(b->decode_tree->ptr1);
290 memset(b->decode_tree,0,sizeof(decode_aux));
291 free(b->decode_tree);
293 if(b->valuelist)free(b->valuelist);
294 if(b->codelist)free(b->codelist);
295 memset(b,0,sizeof(codebook));
298 int vorbis_book_init_encode(codebook *c,const static_codebook *s){
299 memset(c,0,sizeof(codebook));
301 c->entries=s->entries;
303 c->codelist=_make_words(s->lengthlist,s->entries);
304 c->valuelist=_book_unquantize(s);
308 int vorbis_book_init_decode(codebook *c,const static_codebook *s){
309 memset(c,0,sizeof(codebook));
311 c->entries=s->entries;
313 c->valuelist=_book_unquantize(s);
314 c->decode_tree=_make_decode_tree(c);
315 if(c->decode_tree==NULL)goto err_out;
318 vorbis_book_clear(c);
322 int _best(codebook *book, double *a, int step){
323 encode_aux_nearestmatch *nt=book->c->nearest_tree;
324 encode_aux_threshmatch *tt=book->c->thresh_tree;
328 /* we assume for now that a thresh tree is the only other possibility */
331 /* find the quant val of each scalar */
332 for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
334 /* linear search the quant list for now; it's small and although
335 with > 8 entries, it would be faster to bisect, this would be
336 a misplaced optimization for now */
337 for(i=0;i<tt->threshvals-1;i++)
338 if(a[o]<tt->quantthresh[i])break;
340 index=(index*tt->quantvals)+tt->quantmap[i];
342 /* regular lattices are easy :-) */
343 if(book->c->lengthlist[index]>0) /* is this unused? If so, we'll
344 use a decision tree after all
350 /* optimized using the decision tree */
353 double *p=book->valuelist+nt->p[ptr];
354 double *q=book->valuelist+nt->q[ptr];
356 for(k=0,o=0;k<dim;k++,o+=step)
357 c+=(p[k]-q[k])*(a[o]-(p[k]+q[k])*.5);
371 static double _dist(int el,double *a, double *b){
375 double val=(a[i]-b[i]);
381 /* returns the entry number and *modifies a* to the remainder value ********/
382 int vorbis_book_besterror(codebook *book,double *a,int step,int addmul){
383 int dim=book->dim,i,o;
384 int best=_best(book,a,step);
387 for(i=0,o=0;i<dim;i++,o+=step)
388 a[o]-=(book->valuelist+best*dim)[i];
391 for(i=0,o=0;i<dim;i++,o+=step){
392 double val=(book->valuelist+best*dim)[i];
404 long vorbis_book_codeword(codebook *book,int entry){
405 return book->codelist[entry];
408 long vorbis_book_codelen(codebook *book,int entry){
409 return book->c->lengthlist[entry];
414 /* Unit tests of the dequantizer; this stuff will be OK
415 cross-platform, I simply want to be sure that special mapping cases
416 actually work properly; a bug could go unnoticed for a while */
423 full, explicit mapping
430 static long full_quantlist1[]={0,1,2,3, 4,5,6,7, 8,3,6,1};
431 static long partial_quantlist1[]={0,7,2};
434 static_codebook test1={
442 static double *test1_result=NULL;
444 /* linear, full mapping, nonsequential */
445 static_codebook test2={
449 -533200896,1611661312,4,0,
453 static double test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
455 /* linear, full mapping, sequential */
456 static_codebook test3={
460 -533200896,1611661312,4,1,
464 static double test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
466 /* linear, algorithmic mapping, nonsequential */
467 static_codebook test4={
471 -533200896,1611661312,4,0,
475 static double test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
476 -3, 4,-3, 4, 4,-3, -1, 4,-3,
477 -3,-1,-3, 4,-1,-3, -1,-1,-3,
478 -3,-3, 4, 4,-3, 4, -1,-3, 4,
479 -3, 4, 4, 4, 4, 4, -1, 4, 4,
480 -3,-1, 4, 4,-1, 4, -1,-1, 4,
481 -3,-3,-1, 4,-3,-1, -1,-3,-1,
482 -3, 4,-1, 4, 4,-1, -1, 4,-1,
483 -3,-1,-1, 4,-1,-1, -1,-1,-1};
485 /* linear, algorithmic mapping, sequential */
486 static_codebook test5={
490 -533200896,1611661312,4,1,
494 static double test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
495 -3, 1,-2, 4, 8, 5, -1, 3, 0,
496 -3,-4,-7, 4, 3, 0, -1,-2,-5,
497 -3,-6,-2, 4, 1, 5, -1,-4, 0,
498 -3, 1, 5, 4, 8,12, -1, 3, 7,
499 -3,-4, 0, 4, 3, 7, -1,-2, 2,
500 -3,-6,-7, 4, 1, 0, -1,-4,-5,
501 -3, 1, 0, 4, 8, 7, -1, 3, 2,
502 -3,-4,-5, 4, 3, 2, -1,-2,-3};
504 void run_test(static_codebook *b,double *comp){
505 double *out=_book_unquantize(b);
510 fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
514 for(i=0;i<b->entries*b->dim;i++)
515 if(fabs(out[i]-comp[i])>.0001){
516 fprintf(stderr,"disagreement in unquantized and reference data:\n"
517 "position %d, %g != %g\n",i,out[i],comp[i]);
523 fprintf(stderr,"_book_unquantize returned a value array: \n"
524 " correct result should have been NULL\n");
531 /* run the nine dequant tests, and compare to the hand-rolled results */
532 fprintf(stderr,"Dequant test 1... ");
533 run_test(&test1,test1_result);
534 fprintf(stderr,"OK\nDequant test 2... ");
535 run_test(&test2,test2_result);
536 fprintf(stderr,"OK\nDequant test 3... ");
537 run_test(&test3,test3_result);
538 fprintf(stderr,"OK\nDequant test 4... ");
539 run_test(&test4,test4_result);
540 fprintf(stderr,"OK\nDequant test 5... ");
541 run_test(&test5,test5_result);
542 fprintf(stderr,"OK\n\n");