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