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 codebook pack/unpack/code/decode operations
15 last mod: $Id: codebook.c,v 1.18 2000/10/12 03:12:52 xiphmont Exp $
17 ********************************************************************/
23 #include "vorbis/codec.h"
24 #include "vorbis/codebook.h"
26 #include "sharedbook.h"
27 #include "bookinternal.h"
31 /* packs the given codebook into the bitstream **************************/
33 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
37 /* first the basic parameters */
38 oggpack_write(opb,0x564342,24);
39 oggpack_write(opb,c->dim,16);
40 oggpack_write(opb,c->entries,24);
42 /* pack the codewords. There are two packings; length ordered and
43 length random. Decide between the two now. */
45 for(i=1;i<c->entries;i++)
46 if(c->lengthlist[i]<c->lengthlist[i-1])break;
47 if(i==c->entries)ordered=1;
50 /* length ordered. We only need to say how many codewords of
51 each length. The actual codewords are generated
55 oggpack_write(opb,1,1); /* ordered */
56 oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
58 for(i=1;i<c->entries;i++){
59 long this=c->lengthlist[i];
60 long last=c->lengthlist[i-1];
62 for(j=last;j<this;j++){
63 oggpack_write(opb,i-count,_ilog(c->entries-count));
68 oggpack_write(opb,i-count,_ilog(c->entries-count));
71 /* length random. Again, we don't code the codeword itself, just
72 the length. This time, though, we have to encode each length */
73 oggpack_write(opb,0,1); /* unordered */
75 /* algortihmic mapping has use for 'unused entries', which we tag
76 here. The algorithmic mapping happens as usual, but the unused
77 entry has no codeword. */
78 for(i=0;i<c->entries;i++)
79 if(c->lengthlist[i]==0)break;
82 oggpack_write(opb,0,1); /* no unused entries */
83 for(i=0;i<c->entries;i++)
84 oggpack_write(opb,c->lengthlist[i]-1,5);
86 oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
87 for(i=0;i<c->entries;i++){
88 if(c->lengthlist[i]==0){
89 oggpack_write(opb,0,1);
91 oggpack_write(opb,1,1);
92 oggpack_write(opb,c->lengthlist[i]-1,5);
98 /* is the entry number the desired return value, or do we have a
99 mapping? If we have a mapping, what type? */
100 oggpack_write(opb,c->maptype,4);
106 /* implicitly populated value mapping */
107 /* explicitly populated value mapping */
110 /* no quantlist? error */
114 /* values that define the dequantization */
115 oggpack_write(opb,c->q_min,32);
116 oggpack_write(opb,c->q_delta,32);
117 oggpack_write(opb,c->q_quant-1,4);
118 oggpack_write(opb,c->q_sequencep,1);
124 /* a single column of (c->entries/c->dim) quantized values for
125 building a full value list algorithmically (square lattice) */
126 quantvals=_book_maptype1_quantvals(c);
129 /* every value (c->entries*c->dim total) specified explicitly */
130 quantvals=c->entries*c->dim;
134 /* quantized values */
135 for(i=0;i<quantvals;i++)
136 oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
141 /* error case; we don't have any other map types now */
148 /* unpacks a codebook from the packet buffer into the codebook struct,
149 readies the codebook auxiliary structures for decode *************/
150 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
152 memset(s,0,sizeof(static_codebook));
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(oggpack_read(opb,1)){
166 s->lengthlist=malloc(sizeof(long)*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=malloc(sizeof(long)*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;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=malloc(sizeof(float)*quantvals);
237 for(i=0;i<quantvals;i++)
238 s->quantlist[i]=oggpack_read(opb,s->q_quant);
240 if(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 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
259 return(book->c->lengthlist[a]);
262 /* One the encode side, our vector writers are each designed for a
263 specific purpose, and the encoder is not flexible without modification:
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
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) */
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){
279 int best=_best(book,a,1);
281 a[k]=(book->valuelist+best*dim)[k];
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){
289 a[k]=(book->valuelist+best*dim)[k];
290 return(vorbis_book_encode(book,best,b));
293 /* res0 (multistage, interleave, lattice) */
294 /* returns the number of bits and *modifies a* to the remainder value ********/
295 int vorbis_book_encodevs(codebook *book,float *a,oggpack_buffer *b,
296 int step,int addmul){
298 int best=vorbis_book_besterror(book,a,step,addmul);
299 return(vorbis_book_encode(book,best,b));
302 /* Decode side is specced and easier, because we don't need to find
303 matches using different criteria; we simply read and map. There are
304 two things we need to do 'depending':
306 We may need to support interleave. We don't really, but it's
307 convenient to do it here rather than rebuild the vector later.
309 Cascades may be additive or multiplicitive; this is not inherent in
310 the codebook, but set in the code using the codebook. Like
311 interleaving, it's easiest to do it here.
312 addmul==0 -> declarative (set the value)
313 addmul==1 -> additive
314 addmul==2 -> multiplicitive */
316 /* returns the entry number or -1 on eof *************************************/
317 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
319 decode_aux *t=book->decode_tree;
320 int lok = oggpack_look(b, t->tabn);
324 oggpack_adv(b, t->tabl[lok]);
330 switch(oggpack_read1(b)){
344 /* returns the entry number or -1 on eof *************************************/
345 long vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
346 int step,int addmul){
347 long entry=vorbis_book_decode(book,b);
350 if(entry==-1)return(-1);
351 t = book->valuelist+entry*book->dim;
354 for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
360 for(;i<book->dim;i++,o+=step)
364 for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
370 for(;i<book->dim;i++,o+=step)
374 for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
380 for(;i<book->dim;i++,o+=step)
387 /* returns 0 on OK or -1 on eof *************************************/
388 long s_vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
389 int step,int addmul){
390 long *entry = alloca(sizeof(long)*step);
391 float **t = alloca(sizeof(float)*step);
394 for (i = 0; i < step; i++) {
395 entry[i]=vorbis_book_decode(book,b);
396 if(entry[i]==-1)return(-1);
397 t[i] = book->valuelist+entry[i]*book->dim;
401 for(i=0,o=0;i<book->dim;i++,o+=step)
406 for(i=0,o=0;i<book->dim;i++,o+=step)
411 for(i=0,o=0;i<book->dim;i++,o+=step)
421 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
422 number of vectors through (keeping track of the quantized values),
423 and decode using the unpacked book. quantized version of in should
428 #include "vorbis/book/lsp20_0.vqh"
429 #include "vorbis/book/res0a_13.vqh"
432 float test1[TESTSIZE]={
484 float test3[TESTSIZE]={
485 0,1,-2,3,4,-5,6,7,8,9,
486 8,-2,7,-1,4,6,8,3,1,-9,
487 10,11,12,13,14,15,26,17,18,19,
488 30,-25,-30,-1,-5,-32,4,3,-2,0};
490 static_codebook *testlist[]={&_vq_book_lsp20_0,
491 &_vq_book_res0a_13,NULL};
492 float *testvec[]={test1,test3};
495 oggpack_buffer write;
498 oggpack_writeinit(&write);
500 fprintf(stderr,"Testing codebook abstraction...:\n");
502 while(testlist[ptr]){
505 float *qv=alloca(sizeof(float)*TESTSIZE);
506 float *iv=alloca(sizeof(float)*TESTSIZE);
507 memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
508 memset(iv,0,sizeof(float)*TESTSIZE);
510 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
512 /* pack the codebook, write the testvector */
513 oggpack_reset(&write);
514 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
516 vorbis_staticbook_pack(testlist[ptr],&write);
517 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
518 for(i=0;i<TESTSIZE;i+=c.dim){
519 int best=_best(&c,qv+i,1);
520 vorbis_book_encodev(&c,best,qv+i,&write);
522 vorbis_book_clear(&c);
524 fprintf(stderr,"OK.\n");
525 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
527 /* transfer the write data to a read buffer and unpack/read */
528 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
529 if(vorbis_staticbook_unpack(&read,&s)){
530 fprintf(stderr,"Error unpacking codebook.\n");
533 if(vorbis_book_init_decode(&c,&s)){
534 fprintf(stderr,"Error initializing codebook.\n");
538 for(i=0;i<TESTSIZE;i+=c.dim)
539 if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
540 fprintf(stderr,"Error reading codebook test data (EOP).\n");
543 for(i=0;i<TESTSIZE;i++)
544 if(fabs(qv[i]-iv[i])>.000001){
545 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
550 fprintf(stderr,"OK\n");
554 /* The above is the trivial stuff; now try unquantizing a log scale codebook */