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-2002 *
9 * by the XIPHOPHORUS Company 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 /* codeword ordering.... length ordered or unordered? */
163 switch((int)oggpack_read(opb,1)){
166 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
168 /* allocated but unused entries? */
169 if(oggpack_read(opb,1)){
170 /* yes, unused entries */
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;
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;
193 long length=oggpack_read(opb,5)+1;
194 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
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;
210 /* Do we have a mapping to unpack? */
211 switch((s->maptype=oggpack_read(opb,4))){
216 /* implicitly populated value mapping */
217 /* explicitly populated value mapping */
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);
228 quantvals=_book_maptype1_quantvals(s);
231 quantvals=s->entries*s->dim;
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);
240 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
252 vorbis_staticbook_clear(s);
256 /* returns the number of bits ************************************************/
257 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
258 if(a<0 || a>=book->c->entries)return(0);
259 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
260 return(book->c->lengthlist[a]);
263 /* One the encode side, our vector writers are each designed for a
264 specific purpose, and the encoder is not flexible without modification:
266 The LSP vector coder uses a single stage nearest-match with no
267 interleave, so no step and no error return. This is specced by floor0
270 Residue0 encoding interleaves, uses multiple stages, and each stage
271 peels of a specific amount of resolution from a lattice (thus we want
272 to match by threshold, not nearest match). Residue doesn't *have* to
273 be encoded that way, but to change it, one will need to add more
274 infrastructure on the encode side (decode side is specced and simpler) */
276 /* floor0 LSP (single stage, non interleaved, nearest match) */
277 /* returns entry number and *modifies a* to the quantization value *****/
278 int vorbis_book_errorv(codebook *book,float *a){
280 int best=_best(book,a,1);
282 a[k]=(book->valuelist+best*dim)[k];
286 /* returns the number of bits and *modifies a* to the quantization value *****/
287 int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){
290 a[k]=(book->valuelist+best*dim)[k];
291 return(vorbis_book_encode(book,best,b));
294 /* the 'eliminate the decode tree' optimization actually requires the
295 codewords to be MSb first, not LSb. This is an annoying inelegancy
296 (and one of the first places where carefully thought out design
297 turned out to be wrong; Vorbis II and future Ogg codecs should go
298 to an MSb bitpacker), but not actually the huge hit it appears to
299 be. The first-stage decode table catches most words so that
300 bitreverse is not in the main execution path. */
302 static ogg_uint32_t bitreverse(ogg_uint32_t x){
303 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
304 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
305 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
306 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
307 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
310 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
311 int read=book->dec_maxlength;
313 long lok = oggpack_look(b,book->dec_firsttablen);
316 long entry = book->dec_firsttable[lok];
317 if(entry&0x80000000UL){
318 lo=(entry>>15)&0x7fff;
319 hi=book->used_entries-(entry&0x7fff);
321 oggpack_adv(b, book->dec_codelengths[entry-1]);
326 hi=book->used_entries;
329 lok = oggpack_look(b, read);
331 while(lok<0 && read>1)
332 lok = oggpack_look(b, --read);
335 /* bisect search for the codeword in the ordered list */
337 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
341 long test=book->codelist[lo+p]>testword;
346 if(book->dec_codelengths[lo]<=read){
347 oggpack_adv(b, book->dec_codelengths[lo]);
352 oggpack_adv(b, read);
357 /* Decode side is specced and easier, because we don't need to find
358 matches using different criteria; we simply read and map. There are
359 two things we need to do 'depending':
361 We may need to support interleave. We don't really, but it's
362 convenient to do it here rather than rebuild the vector later.
364 Cascades may be additive or multiplicitive; this is not inherent in
365 the codebook, but set in the code using the codebook. Like
366 interleaving, it's easiest to do it here.
367 addmul==0 -> declarative (set the value)
368 addmul==1 -> additive
369 addmul==2 -> multiplicitive */
371 /* returns the [original, not compacted] entry number or -1 on eof *********/
372 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
373 if(book->used_entries>0){
374 long packed_entry=decode_packed_entry_number(book,b);
376 return(book->dec_index[packed_entry]);
379 /* if there's no dec_index, the codebook unpacking isn't collapsed */
383 /* returns 0 on OK or -1 on eof *************************************/
384 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
385 if(book->used_entries>0){
386 int step=n/book->dim;
387 long *entry = alloca(sizeof(*entry)*step);
388 float **t = alloca(sizeof(*t)*step);
391 for (i = 0; i < step; i++) {
392 entry[i]=decode_packed_entry_number(book,b);
393 if(entry[i]==-1)return(-1);
394 t[i] = book->valuelist+entry[i]*book->dim;
396 for(i=0,o=0;i<book->dim;i++,o+=step)
403 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
404 if(book->used_entries>0){
410 entry = decode_packed_entry_number(book,b);
411 if(entry==-1)return(-1);
412 t = book->valuelist+entry*book->dim;
413 for (j=0;j<book->dim;)
418 entry = decode_packed_entry_number(book,b);
419 if(entry==-1)return(-1);
420 t = book->valuelist+entry*book->dim;
422 switch((int)book->dim){
448 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
449 if(book->used_entries>0){
454 entry = decode_packed_entry_number(book,b);
455 if(entry==-1)return(-1);
456 t = book->valuelist+entry*book->dim;
457 for (j=0;j<book->dim;)
464 for (j=0;j<book->dim;)
471 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
472 oggpack_buffer *b,int n){
476 if(book->used_entries>0){
477 for(i=offset/ch;i<(offset+n)/ch;){
478 entry = decode_packed_entry_number(book,b);
479 if(entry==-1)return(-1);
481 const float *t = book->valuelist+entry*book->dim;
482 for (j=0;j<book->dim;j++){
496 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
497 number of vectors through (keeping track of the quantized values),
498 and decode using the unpacked book. quantized version of in should
503 #include "vorbis/book/lsp20_0.vqh"
504 #include "vorbis/book/res0a_13.vqh"
507 float test1[TESTSIZE]={
559 float test3[TESTSIZE]={
560 0,1,-2,3,4,-5,6,7,8,9,
561 8,-2,7,-1,4,6,8,3,1,-9,
562 10,11,12,13,14,15,26,17,18,19,
563 30,-25,-30,-1,-5,-32,4,3,-2,0};
565 static_codebook *testlist[]={&_vq_book_lsp20_0,
566 &_vq_book_res0a_13,NULL};
567 float *testvec[]={test1,test3};
570 oggpack_buffer write;
573 oggpack_writeinit(&write);
575 fprintf(stderr,"Testing codebook abstraction...:\n");
577 while(testlist[ptr]){
580 float *qv=alloca(sizeof(*qv)*TESTSIZE);
581 float *iv=alloca(sizeof(*iv)*TESTSIZE);
582 memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE);
583 memset(iv,0,sizeof(*iv)*TESTSIZE);
585 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
587 /* pack the codebook, write the testvector */
588 oggpack_reset(&write);
589 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
591 vorbis_staticbook_pack(testlist[ptr],&write);
592 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
593 for(i=0;i<TESTSIZE;i+=c.dim){
594 int best=_best(&c,qv+i,1);
595 vorbis_book_encodev(&c,best,qv+i,&write);
597 vorbis_book_clear(&c);
599 fprintf(stderr,"OK.\n");
600 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
602 /* transfer the write data to a read buffer and unpack/read */
603 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
604 if(vorbis_staticbook_unpack(&read,&s)){
605 fprintf(stderr,"Error unpacking codebook.\n");
608 if(vorbis_book_init_decode(&c,&s)){
609 fprintf(stderr,"Error initializing codebook.\n");
613 for(i=0;i<TESTSIZE;i+=c.dim)
614 if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){
615 fprintf(stderr,"Error reading codebook test data (EOP).\n");
618 for(i=0;i<TESTSIZE;i++)
619 if(fabs(qv[i]-iv[i])>.000001){
620 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
625 fprintf(stderr,"OK\n");
629 /* The above is the trivial stuff; now try unquantizing a log scale codebook */