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.5 2000/06/18 12:33:47 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 static double _dist(int el,double *ref, double *b,int step){
326 double val=(ref[i]-b[i*step]);
332 int _best(codebook *book, double *a, int step){
333 encode_aux_nearestmatch *nt=book->c->nearest_tree;
334 encode_aux_threshmatch *tt=book->c->thresh_tree;
338 /* we assume for now that a thresh tree is the only other possibility */
341 /* find the quant val of each scalar */
342 for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
344 /* linear search the quant list for now; it's small and although
345 with > 8 entries, it would be faster to bisect, this would be
346 a misplaced optimization for now */
347 for(i=0;i<tt->threshvals-1;i++)
348 if(a[o]<tt->quantthresh[i])break;
350 index=(index*tt->quantvals)+tt->quantmap[i];
352 /* regular lattices are easy :-) */
353 if(book->c->lengthlist[index]>0) /* is this unused? If so, we'll
354 use a decision tree after all
360 /* optimized using the decision tree */
363 double *p=book->valuelist+nt->p[ptr];
364 double *q=book->valuelist+nt->q[ptr];
366 for(k=0,o=0;k<dim;k++,o+=step)
367 c+=(p[k]-q[k])*(a[o]-(p[k]+q[k])*.5);
378 /* brute force it! */
380 const static_codebook *c=book->c;
383 double *e=book->valuelist;
384 for(i=0;i<book->entries;i++){
385 if(c->lengthlist[i]>0){
386 double this=_dist(dim,e,a,step);
387 if(besti==-1 || this<best){
398 /* returns the entry number and *modifies a* to the remainder value ********/
399 int vorbis_book_besterror(codebook *book,double *a,int step,int addmul){
400 int dim=book->dim,i,o;
401 int best=_best(book,a,step);
404 for(i=0,o=0;i<dim;i++,o+=step)
405 a[o]-=(book->valuelist+best*dim)[i];
408 for(i=0,o=0;i<dim;i++,o+=step){
409 double val=(book->valuelist+best*dim)[i];
421 long vorbis_book_codeword(codebook *book,int entry){
422 return book->codelist[entry];
425 long vorbis_book_codelen(codebook *book,int entry){
426 return book->c->lengthlist[entry];
431 /* Unit tests of the dequantizer; this stuff will be OK
432 cross-platform, I simply want to be sure that special mapping cases
433 actually work properly; a bug could go unnoticed for a while */
440 full, explicit mapping
447 static long full_quantlist1[]={0,1,2,3, 4,5,6,7, 8,3,6,1};
448 static long partial_quantlist1[]={0,7,2};
451 static_codebook test1={
459 static double *test1_result=NULL;
461 /* linear, full mapping, nonsequential */
462 static_codebook test2={
466 -533200896,1611661312,4,0,
470 static double test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};
472 /* linear, full mapping, sequential */
473 static_codebook test3={
477 -533200896,1611661312,4,1,
481 static double test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};
483 /* linear, algorithmic mapping, nonsequential */
484 static_codebook test4={
488 -533200896,1611661312,4,0,
492 static double test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
493 -3, 4,-3, 4, 4,-3, -1, 4,-3,
494 -3,-1,-3, 4,-1,-3, -1,-1,-3,
495 -3,-3, 4, 4,-3, 4, -1,-3, 4,
496 -3, 4, 4, 4, 4, 4, -1, 4, 4,
497 -3,-1, 4, 4,-1, 4, -1,-1, 4,
498 -3,-3,-1, 4,-3,-1, -1,-3,-1,
499 -3, 4,-1, 4, 4,-1, -1, 4,-1,
500 -3,-1,-1, 4,-1,-1, -1,-1,-1};
502 /* linear, algorithmic mapping, sequential */
503 static_codebook test5={
507 -533200896,1611661312,4,1,
511 static double test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
512 -3, 1,-2, 4, 8, 5, -1, 3, 0,
513 -3,-4,-7, 4, 3, 0, -1,-2,-5,
514 -3,-6,-2, 4, 1, 5, -1,-4, 0,
515 -3, 1, 5, 4, 8,12, -1, 3, 7,
516 -3,-4, 0, 4, 3, 7, -1,-2, 2,
517 -3,-6,-7, 4, 1, 0, -1,-4,-5,
518 -3, 1, 0, 4, 8, 7, -1, 3, 2,
519 -3,-4,-5, 4, 3, 2, -1,-2,-3};
521 void run_test(static_codebook *b,double *comp){
522 double *out=_book_unquantize(b);
527 fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
531 for(i=0;i<b->entries*b->dim;i++)
532 if(fabs(out[i]-comp[i])>.0001){
533 fprintf(stderr,"disagreement in unquantized and reference data:\n"
534 "position %d, %g != %g\n",i,out[i],comp[i]);
540 fprintf(stderr,"_book_unquantize returned a value array: \n"
541 " correct result should have been NULL\n");
548 /* run the nine dequant tests, and compare to the hand-rolled results */
549 fprintf(stderr,"Dequant test 1... ");
550 run_test(&test1,test1_result);
551 fprintf(stderr,"OK\nDequant test 2... ");
552 run_test(&test2,test2_result);
553 fprintf(stderr,"OK\nDequant test 3... ");
554 run_test(&test3,test3_result);
555 fprintf(stderr,"OK\nDequant test 4... ");
556 run_test(&test4,test4_result);
557 fprintf(stderr,"OK\nDequant test 5... ");
558 run_test(&test5,test5_result);
559 fprintf(stderr,"OK\n\n");