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 7187 2004-07-20 07:24:27Z xiphmont $
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
vorbis_staticbook_pack(const static_codebook * c,oggpack_buffer * opb)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 *************/
vorbis_staticbook_unpack(oggpack_buffer * opb,static_codebook * s)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 ************************************************/
vorbis_book_encode(codebook * book,int a,oggpack_buffer * b)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 *****/
vorbis_book_errorv(codebook * book,float * a)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 *****/
vorbis_book_encodev(codebook * book,int best,float * a,oggpack_buffer * b)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 /* the 'eliminate the decode tree' optimization actually requires the
294 codewords to be MSb first, not LSb. This is an annoying inelegancy
295 (and one of the first places where carefully thought out design
296 turned out to be wrong; Vorbis II and future Ogg codecs should go
297 to an MSb bitpacker), but not actually the huge hit it appears to
298 be. The first-stage decode table catches most words so that
299 bitreverse is not in the main execution path. */
300
bitreverse(ogg_uint32_t x)301 static ogg_uint32_t bitreverse(ogg_uint32_t x){
302 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
303 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
304 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
305 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
306 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
307 }
308
decode_packed_entry_number(codebook * book,oggpack_buffer * b)309 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
310 int read=book->dec_maxlength;
311 long lo,hi;
312 long lok = oggpack_look(b,book->dec_firsttablen);
313
314 if (lok >= 0) {
315 long entry = book->dec_firsttable[lok];
316 if(entry&0x80000000UL){
317 lo=(entry>>15)&0x7fff;
318 hi=book->used_entries-(entry&0x7fff);
319 }else{
320 oggpack_adv(b, book->dec_codelengths[entry-1]);
321 return(entry-1);
322 }
323 }else{
324 lo=0;
325 hi=book->used_entries;
326 }
327
328 lok = oggpack_look(b, read);
329
330 while(lok<0 && read>1)
331 lok = oggpack_look(b, --read);
332 if(lok<0)return -1;
333
334 /* bisect search for the codeword in the ordered list */
335 {
336 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
337
338 while(hi-lo>1){
339 long p=(hi-lo)>>1;
340 long test=book->codelist[lo+p]>testword;
341 lo+=p&(test-1);
342 hi-=p&(-test);
343 }
344
345 if(book->dec_codelengths[lo]<=read){
346 oggpack_adv(b, book->dec_codelengths[lo]);
347 return(lo);
348 }
349 }
350
351 oggpack_adv(b, read);
352 return(-1);
353 }
354
355 /* Decode side is specced and easier, because we don't need to find
356 matches using different criteria; we simply read and map. There are
357 two things we need to do 'depending':
358
359 We may need to support interleave. We don't really, but it's
360 convenient to do it here rather than rebuild the vector later.
361
362 Cascades may be additive or multiplicitive; this is not inherent in
363 the codebook, but set in the code using the codebook. Like
364 interleaving, it's easiest to do it here.
365 addmul==0 -> declarative (set the value)
366 addmul==1 -> additive
367 addmul==2 -> multiplicitive */
368
369 /* returns the [original, not compacted] entry number or -1 on eof *********/
vorbis_book_decode(codebook * book,oggpack_buffer * b)370 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
371 long packed_entry=decode_packed_entry_number(book,b);
372 if(packed_entry>=0)
373 return(book->dec_index[packed_entry]);
374
375 /* if there's no dec_index, the codebook unpacking isn't collapsed */
376 return(packed_entry);
377 }
378
379 /* returns 0 on OK or -1 on eof *************************************/
vorbis_book_decodevs_add(codebook * book,float * a,oggpack_buffer * b,int n)380 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
381 int step=n/book->dim;
382 long *entry = alloca(sizeof(*entry)*step);
383 float **t = alloca(sizeof(*t)*step);
384 int i,j,o;
385
386 for (i = 0; i < step; i++) {
387 entry[i]=decode_packed_entry_number(book,b);
388 if(entry[i]==-1)return(-1);
389 t[i] = book->valuelist+entry[i]*book->dim;
390 }
391 for(i=0,o=0;i<book->dim;i++,o+=step)
392 for (j=0;j<step;j++)
393 a[o+j]+=t[j][i];
394 return(0);
395 }
396
vorbis_book_decodev_add(codebook * book,float * a,oggpack_buffer * b,int n)397 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
398 int i,j,entry;
399 float *t;
400
401 if(book->dim>8){
402 for(i=0;i<n;){
403 entry = decode_packed_entry_number(book,b);
404 if(entry==-1)return(-1);
405 t = book->valuelist+entry*book->dim;
406 for (j=0;j<book->dim;)
407 a[i++]+=t[j++];
408 }
409 }else{
410 for(i=0;i<n;){
411 entry = decode_packed_entry_number(book,b);
412 if(entry==-1)return(-1);
413 t = book->valuelist+entry*book->dim;
414 j=0;
415 switch((int)book->dim){
416 case 8:
417 a[i++]+=t[j++];
418 case 7:
419 a[i++]+=t[j++];
420 case 6:
421 a[i++]+=t[j++];
422 case 5:
423 a[i++]+=t[j++];
424 case 4:
425 a[i++]+=t[j++];
426 case 3:
427 a[i++]+=t[j++];
428 case 2:
429 a[i++]+=t[j++];
430 case 1:
431 a[i++]+=t[j++];
432 case 0:
433 break;
434 }
435 }
436 }
437 return(0);
438 }
439
vorbis_book_decodev_set(codebook * book,float * a,oggpack_buffer * b,int n)440 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
441 int i,j,entry;
442 float *t;
443
444 for(i=0;i<n;){
445 entry = decode_packed_entry_number(book,b);
446 if(entry==-1)return(-1);
447 t = book->valuelist+entry*book->dim;
448 for (j=0;j<book->dim;)
449 a[i++]=t[j++];
450 }
451 return(0);
452 }
453
vorbis_book_decodevv_add(codebook * book,float ** a,long offset,int ch,oggpack_buffer * b,int n)454 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
455 oggpack_buffer *b,int n){
456 long i,j,entry;
457 int chptr=0;
458
459 for(i=offset/ch;i<(offset+n)/ch;){
460 entry = decode_packed_entry_number(book,b);
461 if(entry==-1)return(-1);
462 {
463 const float *t = book->valuelist+entry*book->dim;
464 for (j=0;j<book->dim;j++){
465 a[chptr++][i]+=t[j];
466 if(chptr==ch){
467 chptr=0;
468 i++;
469 }
470 }
471 }
472 }
473 return(0);
474 }
475
476 #ifdef _V_SELFTEST
477 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
478 number of vectors through (keeping track of the quantized values),
479 and decode using the unpacked book. quantized version of in should
480 exactly equal out */
481
482 #include <stdio.h>
483
484 #include "vorbis/book/lsp20_0.vqh"
485 #include "vorbis/book/res0a_13.vqh"
486 #define TESTSIZE 40
487
488 float test1[TESTSIZE]={
489 0.105939f,
490 0.215373f,
491 0.429117f,
492 0.587974f,
493
494 0.181173f,
495 0.296583f,
496 0.515707f,
497 0.715261f,
498
499 0.162327f,
500 0.263834f,
501 0.342876f,
502 0.406025f,
503
504 0.103571f,
505 0.223561f,
506 0.368513f,
507 0.540313f,
508
509 0.136672f,
510 0.395882f,
511 0.587183f,
512 0.652476f,
513
514 0.114338f,
515 0.417300f,
516 0.525486f,
517 0.698679f,
518
519 0.147492f,
520 0.324481f,
521 0.643089f,
522 0.757582f,
523
524 0.139556f,
525 0.215795f,
526 0.324559f,
527 0.399387f,
528
529 0.120236f,
530 0.267420f,
531 0.446940f,
532 0.608760f,
533
534 0.115587f,
535 0.287234f,
536 0.571081f,
537 0.708603f,
538 };
539
540 float test3[TESTSIZE]={
541 0,1,-2,3,4,-5,6,7,8,9,
542 8,-2,7,-1,4,6,8,3,1,-9,
543 10,11,12,13,14,15,26,17,18,19,
544 30,-25,-30,-1,-5,-32,4,3,-2,0};
545
546 static_codebook *testlist[]={&_vq_book_lsp20_0,
547 &_vq_book_res0a_13,NULL};
548 float *testvec[]={test1,test3};
549
main()550 int main(){
551 oggpack_buffer write;
552 oggpack_buffer read;
553 long ptr=0,i;
554 oggpack_writeinit(&write);
555
556 fprintf(stderr,"Testing codebook abstraction...:\n");
557
558 while(testlist[ptr]){
559 codebook c;
560 static_codebook s;
561 float *qv=alloca(sizeof(*qv)*TESTSIZE);
562 float *iv=alloca(sizeof(*iv)*TESTSIZE);
563 memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
564 memset(iv,0,sizeof(*iv)*TESTSIZE);
565
566 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
567
568 /* pack the codebook, write the testvector */
569 oggpack_reset(&write);
570 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
571 we can write */
572 vorbis_staticbook_pack(testlist[ptr],&write);
573 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
574 for(i=0;i<TESTSIZE;i+=c.dim){
575 int best=_best(&c,qv+i,1);
576 vorbis_book_encodev(&c,best,qv+i,&write);
577 }
578 vorbis_book_clear(&c);
579
580 fprintf(stderr,"OK.\n");
581 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
582
583 /* transfer the write data to a read buffer and unpack/read */
584 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
585 if(vorbis_staticbook_unpack(&read,&s)){
586 fprintf(stderr,"Error unpacking codebook.\n");
587 exit(1);
588 }
589 if(vorbis_book_init_decode(&c,&s)){
590 fprintf(stderr,"Error initializing codebook.\n");
591 exit(1);
592 }
593
594 for(i=0;i<TESTSIZE;i+=c.dim)
595 if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
596 fprintf(stderr,"Error reading codebook test data (EOP).\n");
597 exit(1);
598 }
599 for(i=0;i<TESTSIZE;i++)
600 if(fabs(qv[i]-iv[i])>.000001){
601 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
602 iv[i],qv[i],i);
603 exit(1);
604 }
605
606 fprintf(stderr,"OK\n");
607 ptr++;
608 }
609
610 /* The above is the trivial stuff; now try unquantizing a log scale codebook */
611
612 exit(0);
613 }
614
615 #endif
616