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-2009 *
9 * by the Xiph.Org Foundation http://www.xiph.org/ *
11 ********************************************************************
13 function: basic codebook pack/unpack/code/decode operations
16 ********************************************************************/
22 #include "vorbis/codec.h"
28 /* packs the given codebook into the bitstream **************************/
30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
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);
39 /* pack the codewords. There are two packings; length ordered and
40 length random. Decide between the two now. */
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;
47 /* length ordered. We only need to say how many codewords of
48 each length. The actual codewords are generated
52 oggpack_write(opb,1,1); /* ordered */
53 oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
55 for(i=1;i<c->entries;i++){
56 long this=c->lengthlist[i];
57 long last=c->lengthlist[i-1];
59 for(j=last;j<this;j++){
60 oggpack_write(opb,i-count,_ilog(c->entries-count));
65 oggpack_write(opb,i-count,_ilog(c->entries-count));
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 */
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;
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);
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);
88 oggpack_write(opb,1,1);
89 oggpack_write(opb,c->lengthlist[i]-1,5);
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);
103 /* implicitly populated value mapping */
104 /* explicitly populated value mapping */
107 /* no quantlist? error */
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);
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);
126 /* every value (c->entries*c->dim total) specified explicitly */
127 quantvals=c->entries*c->dim;
129 default: /* NOT_REACHABLE */
133 /* quantized values */
134 for(i=0;i<quantvals;i++)
135 oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
140 /* error case; we don't have any other map types now */
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){
151 memset(s,0,sizeof(*s));
154 /* make sure alignment is correct */
155 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
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;
162 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
164 /* codeword ordering.... length ordered or unordered? */
165 switch((int)oggpack_read(opb,1)){
168 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
170 /* allocated but unused entries? */
171 if(oggpack_read(opb,1)){
172 /* yes, unused entries */
174 for(i=0;i<s->entries;i++){
175 if(oggpack_read(opb,1)){
176 long num=oggpack_read(opb,5);
177 if(num==-1)goto _eofout;
178 s->lengthlist[i]=num+1;
183 /* all entries used; no tagging */
184 for(i=0;i<s->entries;i++){
185 long num=oggpack_read(opb,5);
186 if(num==-1)goto _eofout;
187 s->lengthlist[i]=num+1;
195 long length=oggpack_read(opb,5)+1;
196 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
198 for(i=0;i<s->entries;){
199 long num=oggpack_read(opb,_ilog(s->entries-i));
200 if(num==-1)goto _eofout;
201 if(length>32)goto _errout;
202 for(j=0;j<num && i<s->entries;j++,i++)
203 s->lengthlist[i]=length;
213 /* Do we have a mapping to unpack? */
214 switch((s->maptype=oggpack_read(opb,4))){
219 /* implicitly populated value mapping */
220 /* explicitly populated value mapping */
222 s->q_min=oggpack_read(opb,32);
223 s->q_delta=oggpack_read(opb,32);
224 s->q_quant=oggpack_read(opb,4)+1;
225 s->q_sequencep=oggpack_read(opb,1);
226 if(s->q_sequencep==-1)goto _eofout;
232 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
235 quantvals=s->entries*s->dim;
239 /* quantized values */
240 s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
241 for(i=0;i<quantvals;i++)
242 s->quantlist[i]=oggpack_read(opb,s->q_quant);
244 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
256 vorbis_staticbook_clear(s);
260 /* returns the number of bits ************************************************/
261 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
262 if(a<0 || a>=book->c->entries)return(0);
263 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
264 return(book->c->lengthlist[a]);
267 /* One the encode side, our vector writers are each designed for a
268 specific purpose, and the encoder is not flexible without modification:
270 The LSP vector coder uses a single stage nearest-match with no
271 interleave, so no step and no error return. This is specced by floor0
274 Residue0 encoding interleaves, uses multiple stages, and each stage
275 peels of a specific amount of resolution from a lattice (thus we want
276 to match by threshold, not nearest match). Residue doesn't *have* to
277 be encoded that way, but to change it, one will need to add more
278 infrastructure on the encode side (decode side is specced and simpler) */
280 /* floor0 LSP (single stage, non interleaved, nearest match) */
281 /* returns entry number and *modifies a* to the quantization value *****/
282 int vorbis_book_errorv(codebook *book,float *a){
284 int best=_best(book,a,1);
286 a[k]=(book->valuelist+best*dim)[k];
290 /* returns the number of bits and *modifies a* to the quantization value *****/
291 int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
294 a[k]=(book->valuelist+best*dim)[k];
295 return(vorbis_book_encode(book,best,b));
298 /* the 'eliminate the decode tree' optimization actually requires the
299 codewords to be MSb first, not LSb. This is an annoying inelegancy
300 (and one of the first places where carefully thought out design
301 turned out to be wrong; Vorbis II and future Ogg codecs should go
302 to an MSb bitpacker), but not actually the huge hit it appears to
303 be. The first-stage decode table catches most words so that
304 bitreverse is not in the main execution path. */
306 static ogg_uint32_t bitreverse(ogg_uint32_t x){
307 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
308 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
309 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
310 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
311 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
314 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
315 int read=book->dec_maxlength;
317 long lok = oggpack_look(b,book->dec_firsttablen);
320 long entry = book->dec_firsttable[lok];
321 if(entry&0x80000000UL){
322 lo=(entry>>15)&0x7fff;
323 hi=book->used_entries-(entry&0x7fff);
325 oggpack_adv(b, book->dec_codelengths[entry-1]);
330 hi=book->used_entries;
333 lok = oggpack_look(b, read);
335 while(lok<0 && read>1)
336 lok = oggpack_look(b, --read);
339 /* bisect search for the codeword in the ordered list */
341 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
345 long test=book->codelist[lo+p]>testword;
350 if(book->dec_codelengths[lo]<=read){
351 oggpack_adv(b, book->dec_codelengths[lo]);
356 oggpack_adv(b, read);
361 /* Decode side is specced and easier, because we don't need to find
362 matches using different criteria; we simply read and map. There are
363 two things we need to do 'depending':
365 We may need to support interleave. We don't really, but it's
366 convenient to do it here rather than rebuild the vector later.
368 Cascades may be additive or multiplicitive; this is not inherent in
369 the codebook, but set in the code using the codebook. Like
370 interleaving, it's easiest to do it here.
371 addmul==0 -> declarative (set the value)
372 addmul==1 -> additive
373 addmul==2 -> multiplicitive */
375 /* returns the [original, not compacted] entry number or -1 on eof *********/
376 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
377 if(book->used_entries>0){
378 long packed_entry=decode_packed_entry_number(book,b);
380 return(book->dec_index[packed_entry]);
383 /* if there's no dec_index, the codebook unpacking isn't collapsed */
387 /* returns 0 on OK or -1 on eof *************************************/
388 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
389 if(book->used_entries>0){
390 int step=n/book->dim;
391 long *entry = alloca(sizeof(*entry)*step);
392 float **t = alloca(sizeof(*t)*step);
395 for (i = 0; i < step; i++) {
396 entry[i]=decode_packed_entry_number(book,b);
397 if(entry[i]==-1)return(-1);
398 t[i] = book->valuelist+entry[i]*book->dim;
400 for(i=0,o=0;i<book->dim;i++,o+=step)
407 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
408 if(book->used_entries>0){
414 entry = decode_packed_entry_number(book,b);
415 if(entry==-1)return(-1);
416 t = book->valuelist+entry*book->dim;
417 for (j=0;j<book->dim;)
422 entry = decode_packed_entry_number(book,b);
423 if(entry==-1)return(-1);
424 t = book->valuelist+entry*book->dim;
426 switch((int)book->dim){
452 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
453 if(book->used_entries>0){
458 entry = decode_packed_entry_number(book,b);
459 if(entry==-1)return(-1);
460 t = book->valuelist+entry*book->dim;
461 for (j=0;j<book->dim;)
468 for (j=0;j<book->dim;)
475 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
476 oggpack_buffer *b,int n){
480 if(book->used_entries>0){
481 for(i=offset/ch;i<(offset+n)/ch;){
482 entry = decode_packed_entry_number(book,b);
483 if(entry==-1)return(-1);
485 const float *t = book->valuelist+entry*book->dim;
486 for (j=0;j<book->dim;j++){
500 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
501 number of vectors through (keeping track of the quantized values),
502 and decode using the unpacked book. quantized version of in should
507 #include "vorbis/book/lsp20_0.vqh"
508 #include "vorbis/book/res0a_13.vqh"
511 float test1[TESTSIZE]={
563 float test3[TESTSIZE]={
564 0,1,-2,3,4,-5,6,7,8,9,
565 8,-2,7,-1,4,6,8,3,1,-9,
566 10,11,12,13,14,15,26,17,18,19,
567 30,-25,-30,-1,-5,-32,4,3,-2,0};
569 static_codebook *testlist[]={&_vq_book_lsp20_0,
570 &_vq_book_res0a_13,NULL};
571 float *testvec[]={test1,test3};
574 oggpack_buffer write;
577 oggpack_writeinit(&write);
579 fprintf(stderr,"Testing codebook abstraction...:\n");
581 while(testlist[ptr]){
584 float *qv=alloca(sizeof(*qv)*TESTSIZE);
585 float *iv=alloca(sizeof(*iv)*TESTSIZE);
586 memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
587 memset(iv,0,sizeof(*iv)*TESTSIZE);
589 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
591 /* pack the codebook, write the testvector */
592 oggpack_reset(&write);
593 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
595 vorbis_staticbook_pack(testlist[ptr],&write);
596 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
597 for(i=0;i<TESTSIZE;i+=c.dim){
598 int best=_best(&c,qv+i,1);
599 vorbis_book_encodev(&c,best,qv+i,&write);
601 vorbis_book_clear(&c);
603 fprintf(stderr,"OK.\n");
604 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
606 /* transfer the write data to a read buffer and unpack/read */
607 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
608 if(vorbis_staticbook_unpack(&read,&s)){
609 fprintf(stderr,"Error unpacking codebook.\n");
612 if(vorbis_book_init_decode(&c,&s)){
613 fprintf(stderr,"Error initializing codebook.\n");
617 for(i=0;i<TESTSIZE;i+=c.dim)
618 if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
619 fprintf(stderr,"Error reading codebook test data (EOP).\n");
622 for(i=0;i<TESTSIZE;i++)
623 if(fabs(qv[i]-iv[i])>.000001){
624 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
629 fprintf(stderr,"OK\n");
633 /* The above is the trivial stuff; now try unquantizing a log scale codebook */