codebook.c - vx32 - Local 9vx git repository for patches.
(HTM) git clone git://r-36.net/vx32
(DIR) Log
(DIR) Files
(DIR) Refs
---
codebook.c (17767B)
---
1 /********************************************************************
2 * *
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. *
7 * *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002 *
9 * by the XIPHOPHORUS Company http://www.xiph.org/ *
10 * *
11 ********************************************************************
12
13 function: basic codebook pack/unpack/code/decode operations
14 last mod: $Id: codebook.c 1942 2005-10-12 23:35:43Z baford $
15
16 ********************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include <ogg/ogg.h>
22 #include "vorbis/codec.h"
23 #include "codebook.h"
24 #include "scales.h"
25 #include "misc.h"
26 #include "os.h"
27
28 /* packs the given codebook into the bitstream **************************/
29
30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
31 long i,j;
32 int ordered=0;
33
34 /* first the basic parameters */
35 oggpack_write(opb,0x564342,24);
36 oggpack_write(opb,c->dim,16);
37 oggpack_write(opb,c->entries,24);
38
39 /* pack the codewords. There are two packings; length ordered and
40 length random. Decide between the two now. */
41
42 for(i=1;i<c->entries;i++)
43 if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
44 if(i==c->entries)ordered=1;
45
46 if(ordered){
47 /* length ordered. We only need to say how many codewords of
48 each length. The actual codewords are generated
49 deterministically */
50
51 long count=0;
52 oggpack_write(opb,1,1); /* ordered */
53 oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
54
55 for(i=1;i<c->entries;i++){
56 long this=c->lengthlist[i];
57 long last=c->lengthlist[i-1];
58 if(this>last){
59 for(j=last;j<this;j++){
60 oggpack_write(opb,i-count,_ilog(c->entries-count));
61 count=i;
62 }
63 }
64 }
65 oggpack_write(opb,i-count,_ilog(c->entries-count));
66
67 }else{
68 /* length random. Again, we don't code the codeword itself, just
69 the length. This time, though, we have to encode each length */
70 oggpack_write(opb,0,1); /* unordered */
71
72 /* algortihmic mapping has use for 'unused entries', which we tag
73 here. The algorithmic mapping happens as usual, but the unused
74 entry has no codeword. */
75 for(i=0;i<c->entries;i++)
76 if(c->lengthlist[i]==0)break;
77
78 if(i==c->entries){
79 oggpack_write(opb,0,1); /* no unused entries */
80 for(i=0;i<c->entries;i++)
81 oggpack_write(opb,c->lengthlist[i]-1,5);
82 }else{
83 oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
84 for(i=0;i<c->entries;i++){
85 if(c->lengthlist[i]==0){
86 oggpack_write(opb,0,1);
87 }else{
88 oggpack_write(opb,1,1);
89 oggpack_write(opb,c->lengthlist[i]-1,5);
90 }
91 }
92 }
93 }
94
95 /* is the entry number the desired return value, or do we have a
96 mapping? If we have a mapping, what type? */
97 oggpack_write(opb,c->maptype,4);
98 switch(c->maptype){
99 case 0:
100 /* no mapping */
101 break;
102 case 1:case 2:
103 /* implicitly populated value mapping */
104 /* explicitly populated value mapping */
105
106 if(!c->quantlist){
107 /* no quantlist? error */
108 return(-1);
109 }
110
111 /* values that define the dequantization */
112 oggpack_write(opb,c->q_min,32);
113 oggpack_write(opb,c->q_delta,32);
114 oggpack_write(opb,c->q_quant-1,4);
115 oggpack_write(opb,c->q_sequencep,1);
116
117 {
118 int quantvals;
119 switch(c->maptype){
120 case 1:
121 /* a single column of (c->entries/c->dim) quantized values for
122 building a full value list algorithmically (square lattice) */
123 quantvals=_book_maptype1_quantvals(c);
124 break;
125 case 2:
126 /* every value (c->entries*c->dim total) specified explicitly */
127 quantvals=c->entries*c->dim;
128 break;
129 default: /* NOT_REACHABLE */
130 quantvals=-1;
131 }
132
133 /* quantized values */
134 for(i=0;i<quantvals;i++)
135 oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
136
137 }
138 break;
139 default:
140 /* error case; we don't have any other map types now */
141 return(-1);
142 }
143
144 return(0);
145 }
146
147 /* unpacks a codebook from the packet buffer into the codebook struct,
148 readies the codebook auxiliary structures for decode *************/
149 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
150 long i,j;
151 memset(s,0,sizeof(*s));
152 s->allocedp=1;
153
154 /* make sure alignment is correct */
155 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
156
157 /* first the basic parameters */
158 s->dim=oggpack_read(opb,16);
159 s->entries=oggpack_read(opb,24);
160 if(s->entries==-1)goto _eofout;
161
162 /* codeword ordering.... length ordered or unordered? */
163 switch((int)oggpack_read(opb,1)){
164 case 0:
165 /* unordered */
166 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
167
168 /* allocated but unused entries? */
169 if(oggpack_read(opb,1)){
170 /* yes, unused entries */
171
172 for(i=0;i<s->entries;i++){
173 if(oggpack_read(opb,1)){
174 long num=oggpack_read(opb,5);
175 if(num==-1)goto _eofout;
176 s->lengthlist[i]=num+1;
177 }else
178 s->lengthlist[i]=0;
179 }
180 }else{
181 /* all entries used; no tagging */
182 for(i=0;i<s->entries;i++){
183 long num=oggpack_read(opb,5);
184 if(num==-1)goto _eofout;
185 s->lengthlist[i]=num+1;
186 }
187 }
188
189 break;
190 case 1:
191 /* ordered */
192 {
193 long length=oggpack_read(opb,5)+1;
194 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
195
196 for(i=0;i<s->entries;){
197 long num=oggpack_read(opb,_ilog(s->entries-i));
198 if(num==-1)goto _eofout;
199 for(j=0;j<num && i<s->entries;j++,i++)
200 s->lengthlist[i]=length;
201 length++;
202 }
203 }
204 break;
205 default:
206 /* EOF */
207 return(-1);
208 }
209
210 /* Do we have a mapping to unpack? */
211 switch((s->maptype=oggpack_read(opb,4))){
212 case 0:
213 /* no mapping */
214 break;
215 case 1: case 2:
216 /* implicitly populated value mapping */
217 /* explicitly populated value mapping */
218
219 s->q_min=oggpack_read(opb,32);
220 s->q_delta=oggpack_read(opb,32);
221 s->q_quant=oggpack_read(opb,4)+1;
222 s->q_sequencep=oggpack_read(opb,1);
223
224 {
225 int quantvals=0;
226 switch(s->maptype){
227 case 1:
228 quantvals=_book_maptype1_quantvals(s);
229 break;
230 case 2:
231 quantvals=s->entries*s->dim;
232 break;
233 }
234
235 /* quantized values */
236 s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
237 for(i=0;i<quantvals;i++)
238 s->quantlist[i]=oggpack_read(opb,s->q_quant);
239
240 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
241 }
242 break;
243 default:
244 goto _errout;
245 }
246
247 /* all set */
248 return(0);
249
250 _errout:
251 _eofout:
252 vorbis_staticbook_clear(s);
253 return(-1);
254 }
255
256 /* returns the number of bits ************************************************/
257 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
258 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
259 return(book->c->lengthlist[a]);
260 }
261
262 /* One the encode side, our vector writers are each designed for a
263 specific purpose, and the encoder is not flexible without modification:
264
265 The LSP vector coder uses a single stage nearest-match with no
266 interleave, so no step and no error return. This is specced by floor0
267 and doesn't change.
268
269 Residue0 encoding interleaves, uses multiple stages, and each stage
270 peels of a specific amount of resolution from a lattice (thus we want
271 to match by threshold, not nearest match). Residue doesn't *have* to
272 be encoded that way, but to change it, one will need to add more
273 infrastructure on the encode side (decode side is specced and simpler) */
274
275 /* floor0 LSP (single stage, non interleaved, nearest match) */
276 /* returns entry number and *modifies a* to the quantization value *****/
277 int vorbis_book_errorv(codebook *book,float *a){
278 int dim=book->dim,k;
279 int best=_best(book,a,1);
280 for(k=0;k<dim;k++)
281 a[k]=(book->valuelist+best*dim)[k];
282 return(best);
283 }
284
285 /* returns the number of bits and *modifies a* to the quantization value *****/
286 int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
287 int k,dim=book->dim;
288 for(k=0;k<dim;k++)
289 a[k]=(book->valuelist+best*dim)[k];
290 return(vorbis_book_encode(book,best,b));
291 }
292
293 #if 1 /* XXX vx32 hack */
294 static unsigned long mask[]=
295 {0x00000000,0x00000001,0x00000003,0x00000007,0x0000000f,
296 0x0000001f,0x0000003f,0x0000007f,0x000000ff,0x000001ff,
297 0x000003ff,0x000007ff,0x00000fff,0x00001fff,0x00003fff,
298 0x00007fff,0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
299 0x000fffff,0x001fffff,0x003fffff,0x007fffff,0x00ffffff,
300 0x01ffffff,0x03ffffff,0x07ffffff,0x0fffffff,0x1fffffff,
301 0x3fffffff,0x7fffffff,0xffffffff };
302
303 /* Read in bits without advancing the bitptr; bits <= 32 */
304 static inline long st_oggpack_look(oggpack_buffer *b,int bits){
305 unsigned long ret;
306 unsigned long m=mask[bits];
307
308 bits+=b->endbit;
309
310 if(b->endbyte+4>=b->storage){
311 /* not the main path */
312 if(b->endbyte*8+bits>b->storage*8)return(-1);
313 }
314
315 ret=b->ptr[0]>>b->endbit;
316 if(bits>8){
317 ret|=b->ptr[1]<<(8-b->endbit);
318 if(bits>16){
319 ret|=b->ptr[2]<<(16-b->endbit);
320 if(bits>24){
321 ret|=b->ptr[3]<<(24-b->endbit);
322 if(bits>32 && b->endbit)
323 ret|=b->ptr[4]<<(32-b->endbit);
324 }
325 }
326 }
327 return(m&ret);
328 }
329 #define oggpack_look st_oggpack_look
330
331 static inline void st_oggpack_adv(oggpack_buffer *b,int bits){
332 bits+=b->endbit;
333 b->ptr+=bits/8;
334 b->endbyte+=bits/8;
335 b->endbit=bits&7;
336 }
337 #define oggpack_adv st_oggpack_adv
338 #endif /* XXX end vx32 hack */
339
340
341 /* the 'eliminate the decode tree' optimization actually requires the
342 codewords to be MSb first, not LSb. This is an annoying inelegancy
343 (and one of the first places where carefully thought out design
344 turned out to be wrong; Vorbis II and future Ogg codecs should go
345 to an MSb bitpacker), but not actually the huge hit it appears to
346 be. The first-stage decode table catches most words so that
347 bitreverse is not in the main execution path. */
348
349 static ogg_uint32_t bitreverse(ogg_uint32_t x){
350 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
351 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
352 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
353 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
354 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
355 }
356
357 static inline long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
358 int read=book->dec_maxlength;
359 long lo,hi;
360 long lok = oggpack_look(b,book->dec_firsttablen);
361
362 if (lok >= 0) {
363 long entry = book->dec_firsttable[lok];
364 if(entry&0x80000000UL){
365 lo=(entry>>15)&0x7fff;
366 hi=book->used_entries-(entry&0x7fff);
367 }else{
368 oggpack_adv(b, book->dec_codelengths[entry-1]);
369 return(entry-1);
370 }
371 }else{
372 lo=0;
373 hi=book->used_entries;
374 }
375
376 lok = oggpack_look(b, read);
377
378 while(lok<0 && read>1)
379 lok = oggpack_look(b, --read);
380 if(lok<0)return -1;
381
382 /* bisect search for the codeword in the ordered list */
383 {
384 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
385
386 while(hi-lo>1){
387 long p=(hi-lo)>>1;
388 long test=book->codelist[lo+p]>testword;
389 lo+=p&(test-1);
390 hi-=p&(-test);
391 }
392
393 if(book->dec_codelengths[lo]<=read){
394 oggpack_adv(b, book->dec_codelengths[lo]);
395 return(lo);
396 }
397 }
398
399 oggpack_adv(b, read);
400 return(-1);
401 }
402
403 /* Decode side is specced and easier, because we don't need to find
404 matches using different criteria; we simply read and map. There are
405 two things we need to do 'depending':
406
407 We may need to support interleave. We don't really, but it's
408 convenient to do it here rather than rebuild the vector later.
409
410 Cascades may be additive or multiplicitive; this is not inherent in
411 the codebook, but set in the code using the codebook. Like
412 interleaving, it's easiest to do it here.
413 addmul==0 -> declarative (set the value)
414 addmul==1 -> additive
415 addmul==2 -> multiplicitive */
416
417 /* returns the [original, not compacted] entry number or -1 on eof *********/
418 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
419 long packed_entry=decode_packed_entry_number(book,b);
420 if(packed_entry>=0)
421 return(book->dec_index[packed_entry]);
422
423 /* if there's no dec_index, the codebook unpacking isn't collapsed */
424 return(packed_entry);
425 }
426
427 /* returns 0 on OK or -1 on eof *************************************/
428 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
429 int step=n/book->dim;
430 long *entry = alloca(sizeof(*entry)*step);
431 float **t = alloca(sizeof(*t)*step);
432 int i,j,o;
433
434 for (i = 0; i < step; i++) {
435 entry[i]=decode_packed_entry_number(book,b);
436 if(entry[i]==-1)return(-1);
437 t[i] = book->valuelist+entry[i]*book->dim;
438 }
439 for(i=0,o=0;i<book->dim;i++,o+=step)
440 for (j=0;j<step;j++)
441 a[o+j]+=t[j][i];
442 return(0);
443 }
444
445 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
446 int i,j,entry;
447 float *t;
448
449 if(book->dim>8){
450 for(i=0;i<n;){
451 entry = decode_packed_entry_number(book,b);
452 if(entry==-1)return(-1);
453 t = book->valuelist+entry*book->dim;
454 for (j=0;j<book->dim;)
455 a[i++]+=t[j++];
456 }
457 }else{
458 for(i=0;i<n;){
459 entry = decode_packed_entry_number(book,b);
460 if(entry==-1)return(-1);
461 t = book->valuelist+entry*book->dim;
462 j=0;
463 switch((int)book->dim){
464 case 8:
465 a[i++]+=t[j++];
466 case 7:
467 a[i++]+=t[j++];
468 case 6:
469 a[i++]+=t[j++];
470 case 5:
471 a[i++]+=t[j++];
472 case 4:
473 a[i++]+=t[j++];
474 case 3:
475 a[i++]+=t[j++];
476 case 2:
477 a[i++]+=t[j++];
478 case 1:
479 a[i++]+=t[j++];
480 case 0:
481 break;
482 }
483 }
484 }
485 return(0);
486 }
487
488 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
489 int i,j,entry;
490 float *t;
491
492 for(i=0;i<n;){
493 entry = decode_packed_entry_number(book,b);
494 if(entry==-1)return(-1);
495 t = book->valuelist+entry*book->dim;
496 for (j=0;j<book->dim;)
497 a[i++]=t[j++];
498 }
499 return(0);
500 }
501
502 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
503 oggpack_buffer *b,int n){
504 long i,j,entry;
505 int chptr=0;
506
507 for(i=offset/ch;i<(offset+n)/ch;){
508 entry = decode_packed_entry_number(book,b);
509 if(entry==-1)return(-1);
510 {
511 const float *t = book->valuelist+entry*book->dim;
512 for (j=0;j<book->dim;j++){
513 a[chptr++][i]+=t[j];
514 if(chptr==ch){
515 chptr=0;
516 i++;
517 }
518 }
519 }
520 }
521 return(0);
522 }
523
524 #ifdef _V_SELFTEST
525 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
526 number of vectors through (keeping track of the quantized values),
527 and decode using the unpacked book. quantized version of in should
528 exactly equal out */
529
530 #include <stdio.h>
531
532 #include "vorbis/book/lsp20_0.vqh"
533 #include "vorbis/book/res0a_13.vqh"
534 #define TESTSIZE 40
535
536 float test1[TESTSIZE]={
537 0.105939f,
538 0.215373f,
539 0.429117f,
540 0.587974f,
541
542 0.181173f,
543 0.296583f,
544 0.515707f,
545 0.715261f,
546
547 0.162327f,
548 0.263834f,
549 0.342876f,
550 0.406025f,
551
552 0.103571f,
553 0.223561f,
554 0.368513f,
555 0.540313f,
556
557 0.136672f,
558 0.395882f,
559 0.587183f,
560 0.652476f,
561
562 0.114338f,
563 0.417300f,
564 0.525486f,
565 0.698679f,
566
567 0.147492f,
568 0.324481f,
569 0.643089f,
570 0.757582f,
571
572 0.139556f,
573 0.215795f,
574 0.324559f,
575 0.399387f,
576
577 0.120236f,
578 0.267420f,
579 0.446940f,
580 0.608760f,
581
582 0.115587f,
583 0.287234f,
584 0.571081f,
585 0.708603f,
586 };
587
588 float test3[TESTSIZE]={
589 0,1,-2,3,4,-5,6,7,8,9,
590 8,-2,7,-1,4,6,8,3,1,-9,
591 10,11,12,13,14,15,26,17,18,19,
592 30,-25,-30,-1,-5,-32,4,3,-2,0};
593
594 static_codebook *testlist[]={&_vq_book_lsp20_0,
595 &_vq_book_res0a_13,NULL};
596 float *testvec[]={test1,test3};
597
598 int main(){
599 oggpack_buffer write;
600 oggpack_buffer read;
601 long ptr=0,i;
602 oggpack_writeinit(&write);
603
604 fprintf(stderr,"Testing codebook abstraction...:\n");
605
606 while(testlist[ptr]){
607 codebook c;
608 static_codebook s;
609 float *qv=alloca(sizeof(*qv)*TESTSIZE);
610 float *iv=alloca(sizeof(*iv)*TESTSIZE);
611 memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
612 memset(iv,0,sizeof(*iv)*TESTSIZE);
613
614 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
615
616 /* pack the codebook, write the testvector */
617 oggpack_reset(&write);
618 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
619 we can write */
620 vorbis_staticbook_pack(testlist[ptr],&write);
621 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
622 for(i=0;i<TESTSIZE;i+=c.dim){
623 int best=_best(&c,qv+i,1);
624 vorbis_book_encodev(&c,best,qv+i,&write);
625 }
626 vorbis_book_clear(&c);
627
628 fprintf(stderr,"OK.\n");
629 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
630
631 /* transfer the write data to a read buffer and unpack/read */
632 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
633 if(vorbis_staticbook_unpack(&read,&s)){
634 fprintf(stderr,"Error unpacking codebook.\n");
635 exit(1);
636 }
637 if(vorbis_book_init_decode(&c,&s)){
638 fprintf(stderr,"Error initializing codebook.\n");
639 exit(1);
640 }
641
642 for(i=0;i<TESTSIZE;i+=c.dim)
643 if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
644 fprintf(stderr,"Error reading codebook test data (EOP).\n");
645 exit(1);
646 }
647 for(i=0;i<TESTSIZE;i++)
648 if(fabs(qv[i]-iv[i])>.000001){
649 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
650 iv[i],qv[i],i);
651 exit(1);
652 }
653
654 fprintf(stderr,"OK\n");
655 ptr++;
656 }
657
658 /* The above is the trivial stuff; now try unquantizing a log scale codebook */
659
660 exit(0);
661 }
662
663 #endif