1 /********************************************************************
3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH *
6 * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
8 * THE OggVorbis 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.20 2000/12/21 21:04:39 xiphmont Exp $
17 ********************************************************************/
23 #include "vorbis/codec.h"
29 /* packs the given codebook into the bitstream **************************/
31 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
35 /* first the basic parameters */
36 oggpack_write(opb,0x564342,24);
37 oggpack_write(opb,c->dim,16);
38 oggpack_write(opb,c->entries,24);
40 /* pack the codewords. There are two packings; length ordered and
41 length random. Decide between the two now. */
43 for(i=1;i<c->entries;i++)
44 if(c->lengthlist[i]<c->lengthlist[i-1])break;
45 if(i==c->entries)ordered=1;
48 /* length ordered. We only need to say how many codewords of
49 each length. The actual codewords are generated
53 oggpack_write(opb,1,1); /* ordered */
54 oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
56 for(i=1;i<c->entries;i++){
57 long this=c->lengthlist[i];
58 long last=c->lengthlist[i-1];
60 for(j=last;j<this;j++){
61 oggpack_write(opb,i-count,_ilog(c->entries-count));
66 oggpack_write(opb,i-count,_ilog(c->entries-count));
69 /* length random. Again, we don't code the codeword itself, just
70 the length. This time, though, we have to encode each length */
71 oggpack_write(opb,0,1); /* unordered */
73 /* algortihmic mapping has use for 'unused entries', which we tag
74 here. The algorithmic mapping happens as usual, but the unused
75 entry has no codeword. */
76 for(i=0;i<c->entries;i++)
77 if(c->lengthlist[i]==0)break;
80 oggpack_write(opb,0,1); /* no unused entries */
81 for(i=0;i<c->entries;i++)
82 oggpack_write(opb,c->lengthlist[i]-1,5);
84 oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
85 for(i=0;i<c->entries;i++){
86 if(c->lengthlist[i]==0){
87 oggpack_write(opb,0,1);
89 oggpack_write(opb,1,1);
90 oggpack_write(opb,c->lengthlist[i]-1,5);
96 /* is the entry number the desired return value, or do we have a
97 mapping? If we have a mapping, what type? */
98 oggpack_write(opb,c->maptype,4);
104 /* implicitly populated value mapping */
105 /* explicitly populated value mapping */
108 /* no quantlist? error */
112 /* values that define the dequantization */
113 oggpack_write(opb,c->q_min,32);
114 oggpack_write(opb,c->q_delta,32);
115 oggpack_write(opb,c->q_quant-1,4);
116 oggpack_write(opb,c->q_sequencep,1);
122 /* a single column of (c->entries/c->dim) quantized values for
123 building a full value list algorithmically (square lattice) */
124 quantvals=_book_maptype1_quantvals(c);
127 /* every value (c->entries*c->dim total) specified explicitly */
128 quantvals=c->entries*c->dim;
130 default: /* NOT_REACHABLE */
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));
155 /* make sure alignment is correct */
156 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
158 /* first the basic parameters */
159 s->dim=oggpack_read(opb,16);
160 s->entries=oggpack_read(opb,24);
161 if(s->entries==-1)goto _eofout;
163 /* codeword ordering.... length ordered or unordered? */
164 switch(oggpack_read(opb,1)){
167 s->lengthlist=_ogg_malloc(sizeof(long)*s->entries);
169 /* allocated but unused entries? */
170 if(oggpack_read(opb,1)){
171 /* yes, unused entries */
173 for(i=0;i<s->entries;i++){
174 if(oggpack_read(opb,1)){
175 long num=oggpack_read(opb,5);
176 if(num==-1)goto _eofout;
177 s->lengthlist[i]=num+1;
182 /* all entries used; no tagging */
183 for(i=0;i<s->entries;i++){
184 long num=oggpack_read(opb,5);
185 if(num==-1)goto _eofout;
186 s->lengthlist[i]=num+1;
194 long length=oggpack_read(opb,5)+1;
195 s->lengthlist=_ogg_malloc(sizeof(long)*s->entries);
197 for(i=0;i<s->entries;){
198 long num=oggpack_read(opb,_ilog(s->entries-i));
199 if(num==-1)goto _eofout;
200 for(j=0;j<num;j++,i++)
201 s->lengthlist[i]=length;
211 /* Do we have a mapping to unpack? */
212 switch((s->maptype=oggpack_read(opb,4))){
217 /* implicitly populated value mapping */
218 /* explicitly populated value mapping */
220 s->q_min=oggpack_read(opb,32);
221 s->q_delta=oggpack_read(opb,32);
222 s->q_quant=oggpack_read(opb,4)+1;
223 s->q_sequencep=oggpack_read(opb,1);
229 quantvals=_book_maptype1_quantvals(s);
232 quantvals=s->entries*s->dim;
236 /* quantized values */
237 s->quantlist=_ogg_malloc(sizeof(float)*quantvals);
238 for(i=0;i<quantvals;i++)
239 s->quantlist[i]=oggpack_read(opb,s->q_quant);
241 if(s->quantlist[quantvals-1]==-1)goto _eofout;
253 vorbis_staticbook_clear(s);
257 /* returns the number of bits ************************************************/
258 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
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 /* res0 (multistage, interleave, lattice) */
295 /* returns the number of bits and *modifies a* to the remainder value ********/
296 int vorbis_book_encodevs(codebook *book,float *a,oggpack_buffer *b,
297 int step,int addmul){
299 int best=vorbis_book_besterror(book,a,step,addmul);
300 return(vorbis_book_encode(book,best,b));
303 /* Decode side is specced and easier, because we don't need to find
304 matches using different criteria; we simply read and map. There are
305 two things we need to do 'depending':
307 We may need to support interleave. We don't really, but it's
308 convenient to do it here rather than rebuild the vector later.
310 Cascades may be additive or multiplicitive; this is not inherent in
311 the codebook, but set in the code using the codebook. Like
312 interleaving, it's easiest to do it here.
313 addmul==0 -> declarative (set the value)
314 addmul==1 -> additive
315 addmul==2 -> multiplicitive */
317 /* returns the entry number or -1 on eof *************************************/
318 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
320 decode_aux *t=book->decode_tree;
321 int lok = oggpack_look(b, t->tabn);
325 oggpack_adv(b, t->tabl[lok]);
331 switch(oggpack_read1(b)){
345 /* returns the entry number or -1 on eof *************************************/
346 long vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
347 int step,int addmul){
348 long entry=vorbis_book_decode(book,b);
351 if(entry==-1)return(-1);
352 t = book->valuelist+entry*book->dim;
355 for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
361 for(;i<book->dim;i++,o+=step)
365 for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
371 for(;i<book->dim;i++,o+=step)
375 for(i=0,o=0;i<book->dim-3;i+=4,o+=4*step) {
381 for(;i<book->dim;i++,o+=step)
388 /* returns 0 on OK or -1 on eof *************************************/
389 long s_vorbis_book_decodevs(codebook *book,float *a,oggpack_buffer *b,
390 int step,int addmul){
391 long *entry = alloca(sizeof(long)*step);
392 float **t = alloca(sizeof(float *)*step);
395 for (i = 0; i < step; i++) {
396 entry[i]=vorbis_book_decode(book,b);
397 if(entry[i]==-1)return(-1);
398 t[i] = book->valuelist+entry[i]*book->dim;
402 for(i=0,o=0;i<book->dim;i++,o+=step)
407 for(i=0,o=0;i<book->dim;i++,o+=step)
412 for(i=0,o=0;i<book->dim;i++,o+=step)
422 /* Simple enough; pack a few candidate codebooks, unpack them. Code a
423 number of vectors through (keeping track of the quantized values),
424 and decode using the unpacked book. quantized version of in should
429 #include "vorbis/book/lsp20_0.vqh"
430 #include "vorbis/book/res0a_13.vqh"
433 float test1[TESTSIZE]={
485 float test3[TESTSIZE]={
486 0,1,-2,3,4,-5,6,7,8,9,
487 8,-2,7,-1,4,6,8,3,1,-9,
488 10,11,12,13,14,15,26,17,18,19,
489 30,-25,-30,-1,-5,-32,4,3,-2,0};
491 static_codebook *testlist[]={&_vq_book_lsp20_0,
492 &_vq_book_res0a_13,NULL};
493 float *testvec[]={test1,test3};
496 oggpack_buffer write;
499 oggpack_writeinit(&write);
501 fprintf(stderr,"Testing codebook abstraction...:\n");
503 while(testlist[ptr]){
506 float *qv=alloca(sizeof(float)*TESTSIZE);
507 float *iv=alloca(sizeof(float)*TESTSIZE);
508 memcpy(qv,testvec[ptr],sizeof(float)*TESTSIZE);
509 memset(iv,0,sizeof(float)*TESTSIZE);
511 fprintf(stderr,"\tpacking/coding %ld... ",ptr);
513 /* pack the codebook, write the testvector */
514 oggpack_reset(&write);
515 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory
517 vorbis_staticbook_pack(testlist[ptr],&write);
518 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write));
519 for(i=0;i<TESTSIZE;i+=c.dim){
520 int best=_best(&c,qv+i,1);
521 vorbis_book_encodev(&c,best,qv+i,&write);
523 vorbis_book_clear(&c);
525 fprintf(stderr,"OK.\n");
526 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr);
528 /* transfer the write data to a read buffer and unpack/read */
529 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write));
530 if(vorbis_staticbook_unpack(&read,&s)){
531 fprintf(stderr,"Error unpacking codebook.\n");
534 if(vorbis_book_init_decode(&c,&s)){
535 fprintf(stderr,"Error initializing codebook.\n");
539 for(i=0;i<TESTSIZE;i+=c.dim)
540 if(vorbis_book_decodevs(&c,iv+i,&read,1,-1)==-1){
541 fprintf(stderr,"Error reading codebook test data (EOP).\n");
544 for(i=0;i<TESTSIZE;i++)
545 if(fabs(qv[i]-iv[i])>.000001){
546 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n",
551 fprintf(stderr,"OK\n");
555 /* The above is the trivial stuff; now try unquantizing a log scale codebook */