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-2009 * 9 * by the Xiph.Org Foundation http://www.xiph.org/ * 10 * * 11 ******************************************************************** 12 13 function: basic codebook pack/unpack/code/decode operations 14 last mod: $Id: codebook.c 16227 2009-07-08 06:58:46Z xiphmont $ 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 30int 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 *************/ 149int 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 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout; 163 164 /* codeword ordering.... length ordered or unordered? */ 165 switch((int)oggpack_read(opb,1)){ 166 case 0: 167 /* unordered */ 168 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries); 169 170 /* allocated but unused entries? */ 171 if(oggpack_read(opb,1)){ 172 /* yes, unused entries */ 173 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; 179 }else 180 s->lengthlist[i]=0; 181 } 182 }else{ 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; 188 } 189 } 190 191 break; 192 case 1: 193 /* ordered */ 194 { 195 long length=oggpack_read(opb,5)+1; 196 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries); 197 198 for(i=0;i<s->entries;){ 199 long num=oggpack_read(opb,_ilog(s->entries-i)); 200 if(num==-1)goto _eofout; 201 for(j=0;j<num && i<s->entries;j++,i++) 202 s->lengthlist[i]=length; 203 length++; 204 } 205 } 206 break; 207 default: 208 /* EOF */ 209 return(-1); 210 } 211 212 /* Do we have a mapping to unpack? */ 213 switch((s->maptype=oggpack_read(opb,4))){ 214 case 0: 215 /* no mapping */ 216 break; 217 case 1: case 2: 218 /* implicitly populated value mapping */ 219 /* explicitly populated value mapping */ 220 221 s->q_min=oggpack_read(opb,32); 222 s->q_delta=oggpack_read(opb,32); 223 s->q_quant=oggpack_read(opb,4)+1; 224 s->q_sequencep=oggpack_read(opb,1); 225 if(s->q_sequencep==-1)goto _eofout; 226 227 { 228 int quantvals=0; 229 switch(s->maptype){ 230 case 1: 231 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s)); 232 break; 233 case 2: 234 quantvals=s->entries*s->dim; 235 break; 236 } 237 238 /* quantized values */ 239 s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals); 240 for(i=0;i<quantvals;i++) 241 s->quantlist[i]=oggpack_read(opb,s->q_quant); 242 243 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; 244 } 245 break; 246 default: 247 goto _errout; 248 } 249 250 /* all set */ 251 return(0); 252 253 _errout: 254 _eofout: 255 vorbis_staticbook_clear(s); 256 return(-1); 257} 258 259/* returns the number of bits ************************************************/ 260int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){ 261 if(a<0 || a>=book->c->entries)return(0); 262 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]); 263 return(book->c->lengthlist[a]); 264} 265 266/* One the encode side, our vector writers are each designed for a 267specific purpose, and the encoder is not flexible without modification: 268 269The LSP vector coder uses a single stage nearest-match with no 270interleave, so no step and no error return. This is specced by floor0 271and doesn't change. 272 273Residue0 encoding interleaves, uses multiple stages, and each stage 274peels of a specific amount of resolution from a lattice (thus we want 275to match by threshold, not nearest match). Residue doesn't *have* to 276be encoded that way, but to change it, one will need to add more 277infrastructure on the encode side (decode side is specced and simpler) */ 278 279/* floor0 LSP (single stage, non interleaved, nearest match) */ 280/* returns entry number and *modifies a* to the quantization value *****/ 281int vorbis_book_errorv(codebook *book,float *a){ 282 int dim=book->dim,k; 283 int best=_best(book,a,1); 284 for(k=0;k<dim;k++) 285 a[k]=(book->valuelist+best*dim)[k]; 286 return(best); 287} 288 289/* returns the number of bits and *modifies a* to the quantization value *****/ 290int vorbis_book_encodev(codebook *book,int best,float *a,oggpack_buffer *b){ 291 int k,dim=book->dim; 292 for(k=0;k<dim;k++) 293 a[k]=(book->valuelist+best*dim)[k]; 294 return(vorbis_book_encode(book,best,b)); 295} 296 297/* the 'eliminate the decode tree' optimization actually requires the 298 codewords to be MSb first, not LSb. This is an annoying inelegancy 299 (and one of the first places where carefully thought out design 300 turned out to be wrong; Vorbis II and future Ogg codecs should go 301 to an MSb bitpacker), but not actually the huge hit it appears to 302 be. The first-stage decode table catches most words so that 303 bitreverse is not in the main execution path. */ 304 305static ogg_uint32_t bitreverse(ogg_uint32_t x){ 306 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000); 307 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00); 308 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0); 309 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc); 310 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa); 311} 312 313STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){ 314 int read=book->dec_maxlength; 315 long lo,hi; 316 long lok = oggpack_look(b,book->dec_firsttablen); 317 318 if (lok >= 0) { 319 long entry = book->dec_firsttable[lok]; 320 if(entry&0x80000000UL){ 321 lo=(entry>>15)&0x7fff; 322 hi=book->used_entries-(entry&0x7fff); 323 }else{ 324 oggpack_adv(b, book->dec_codelengths[entry-1]); 325 return(entry-1); 326 } 327 }else{ 328 lo=0; 329 hi=book->used_entries; 330 } 331 332 lok = oggpack_look(b, read); 333 334 while(lok<0 && read>1) 335 lok = oggpack_look(b, --read); 336 if(lok<0)return -1; 337 338 /* bisect search for the codeword in the ordered list */ 339 { 340 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); 341 342 while(hi-lo>1){ 343 long p=(hi-lo)>>1; 344 long test=book->codelist[lo+p]>testword; 345 lo+=p&(test-1); 346 hi-=p&(-test); 347 } 348 349 if(book->dec_codelengths[lo]<=read){ 350 oggpack_adv(b, book->dec_codelengths[lo]); 351 return(lo); 352 } 353 } 354 355 oggpack_adv(b, read); 356 357 return(-1); 358} 359 360/* Decode side is specced and easier, because we don't need to find 361 matches using different criteria; we simply read and map. There are 362 two things we need to do 'depending': 363 364 We may need to support interleave. We don't really, but it's 365 convenient to do it here rather than rebuild the vector later. 366 367 Cascades may be additive or multiplicitive; this is not inherent in 368 the codebook, but set in the code using the codebook. Like 369 interleaving, it's easiest to do it here. 370 addmul==0 -> declarative (set the value) 371 addmul==1 -> additive 372 addmul==2 -> multiplicitive */ 373 374/* returns the [original, not compacted] entry number or -1 on eof *********/ 375long vorbis_book_decode(codebook *book, oggpack_buffer *b){ 376 if(book->used_entries>0){ 377 long packed_entry=decode_packed_entry_number(book,b); 378 if(packed_entry>=0) 379 return(book->dec_index[packed_entry]); 380 } 381 382 /* if there's no dec_index, the codebook unpacking isn't collapsed */ 383 return(-1); 384} 385 386/* returns 0 on OK or -1 on eof *************************************/ 387long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){ 388 if(book->used_entries>0){ 389 int step=n/book->dim; 390 long *entry = alloca(sizeof(*entry)*step); 391 float **t = alloca(sizeof(*t)*step); 392 int i,j,o; 393 394 for (i = 0; i < step; i++) { 395 entry[i]=decode_packed_entry_number(book,b); 396 if(entry[i]==-1)return(-1); 397 t[i] = book->valuelist+entry[i]*book->dim; 398 } 399 for(i=0,o=0;i<book->dim;i++,o+=step) 400 for (j=0;j<step;j++) 401 a[o+j]+=t[j][i]; 402 } 403 return(0); 404} 405 406long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){ 407 if(book->used_entries>0){ 408 int i,j,entry; 409 float *t; 410 411 if(book->dim>8){ 412 for(i=0;i<n;){ 413 entry = decode_packed_entry_number(book,b); 414 if(entry==-1)return(-1); 415 t = book->valuelist+entry*book->dim; 416 for (j=0;j<book->dim;) 417 a[i++]+=t[j++]; 418 } 419 }else{ 420 for(i=0;i<n;){ 421 entry = decode_packed_entry_number(book,b); 422 if(entry==-1)return(-1); 423 t = book->valuelist+entry*book->dim; 424 j=0; 425 switch((int)book->dim){ 426 case 8: 427 a[i++]+=t[j++]; 428 case 7: 429 a[i++]+=t[j++]; 430 case 6: 431 a[i++]+=t[j++]; 432 case 5: 433 a[i++]+=t[j++]; 434 case 4: 435 a[i++]+=t[j++]; 436 case 3: 437 a[i++]+=t[j++]; 438 case 2: 439 a[i++]+=t[j++]; 440 case 1: 441 a[i++]+=t[j++]; 442 case 0: 443 break; 444 } 445 } 446 } 447 } 448 return(0); 449} 450 451long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){ 452 if(book->used_entries>0){ 453 int i,j,entry; 454 float *t; 455 456 for(i=0;i<n;){ 457 entry = decode_packed_entry_number(book,b); 458 if(entry==-1)return(-1); 459 t = book->valuelist+entry*book->dim; 460 for (j=0;j<book->dim;) 461 a[i++]=t[j++]; 462 } 463 }else{ 464 int i,j; 465 466 for(i=0;i<n;){ 467 for (j=0;j<book->dim;) 468 a[i++]=0.f; 469 } 470 } 471 return(0); 472} 473 474long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch, 475 oggpack_buffer *b,int n){ 476 477 long i,j,entry; 478 int chptr=0; 479 if(book->used_entries>0){ 480 for(i=offset/ch;i<(offset+n)/ch;){ 481 entry = decode_packed_entry_number(book,b); 482 if(entry==-1)return(-1); 483 { 484 const float *t = book->valuelist+entry*book->dim; 485 for (j=0;j<book->dim;j++){ 486 a[chptr++][i]+=t[j]; 487 if(chptr==ch){ 488 chptr=0; 489 i++; 490 } 491 } 492 } 493 } 494 } 495 return(0); 496} 497 498#ifdef _V_SELFTEST 499/* Simple enough; pack a few candidate codebooks, unpack them. Code a 500 number of vectors through (keeping track of the quantized values), 501 and decode using the unpacked book. quantized version of in should 502 exactly equal out */ 503 504#include <stdio.h> 505 506#include "vorbis/book/lsp20_0.vqh" 507#include "vorbis/book/res0a_13.vqh" 508#define TESTSIZE 40 509 510float test1[TESTSIZE]={ 511 0.105939f, 512 0.215373f, 513 0.429117f, 514 0.587974f, 515 516 0.181173f, 517 0.296583f, 518 0.515707f, 519 0.715261f, 520 521 0.162327f, 522 0.263834f, 523 0.342876f, 524 0.406025f, 525 526 0.103571f, 527 0.223561f, 528 0.368513f, 529 0.540313f, 530 531 0.136672f, 532 0.395882f, 533 0.587183f, 534 0.652476f, 535 536 0.114338f, 537 0.417300f, 538 0.525486f, 539 0.698679f, 540 541 0.147492f, 542 0.324481f, 543 0.643089f, 544 0.757582f, 545 546 0.139556f, 547 0.215795f, 548 0.324559f, 549 0.399387f, 550 551 0.120236f, 552 0.267420f, 553 0.446940f, 554 0.608760f, 555 556 0.115587f, 557 0.287234f, 558 0.571081f, 559 0.708603f, 560}; 561 562float test3[TESTSIZE]={ 563 0,1,-2,3,4,-5,6,7,8,9, 564 8,-2,7,-1,4,6,8,3,1,-9, 565 10,11,12,13,14,15,26,17,18,19, 566 30,-25,-30,-1,-5,-32,4,3,-2,0}; 567 568static_codebook *testlist[]={&_vq_book_lsp20_0, 569 &_vq_book_res0a_13,NULL}; 570float *testvec[]={test1,test3}; 571 572int main(){ 573 oggpack_buffer write; 574 oggpack_buffer read; 575 long ptr=0,i; 576 oggpack_writeinit(&write); 577 578 fprintf(stderr,"Testing codebook abstraction...:\n"); 579 580 while(testlist[ptr]){ 581 codebook c; 582 static_codebook s; 583 float *qv=alloca(sizeof(*qv)*TESTSIZE); 584 float *iv=alloca(sizeof(*iv)*TESTSIZE); 585 memcpy(qv,testvec[ptr],sizeof(*qv)*TESTSIZE); 586 memset(iv,0,sizeof(*iv)*TESTSIZE); 587 588 fprintf(stderr,"\tpacking/coding %ld... ",ptr); 589 590 /* pack the codebook, write the testvector */ 591 oggpack_reset(&write); 592 vorbis_book_init_encode(&c,testlist[ptr]); /* get it into memory 593 we can write */ 594 vorbis_staticbook_pack(testlist[ptr],&write); 595 fprintf(stderr,"Codebook size %ld bytes... ",oggpack_bytes(&write)); 596 for(i=0;i<TESTSIZE;i+=c.dim){ 597 int best=_best(&c,qv+i,1); 598 vorbis_book_encodev(&c,best,qv+i,&write); 599 } 600 vorbis_book_clear(&c); 601 602 fprintf(stderr,"OK.\n"); 603 fprintf(stderr,"\tunpacking/decoding %ld... ",ptr); 604 605 /* transfer the write data to a read buffer and unpack/read */ 606 oggpack_readinit(&read,oggpack_get_buffer(&write),oggpack_bytes(&write)); 607 if(vorbis_staticbook_unpack(&read,&s)){ 608 fprintf(stderr,"Error unpacking codebook.\n"); 609 exit(1); 610 } 611 if(vorbis_book_init_decode(&c,&s)){ 612 fprintf(stderr,"Error initializing codebook.\n"); 613 exit(1); 614 } 615 616 for(i=0;i<TESTSIZE;i+=c.dim) 617 if(vorbis_book_decodev_set(&c,iv+i,&read,c.dim)==-1){ 618 fprintf(stderr,"Error reading codebook test data (EOP).\n"); 619 exit(1); 620 } 621 for(i=0;i<TESTSIZE;i++) 622 if(fabs(qv[i]-iv[i])>.000001){ 623 fprintf(stderr,"read (%g) != written (%g) at position (%ld)\n", 624 iv[i],qv[i],i); 625 exit(1); 626 } 627 628 fprintf(stderr,"OK\n"); 629 ptr++; 630 } 631 632 /* The above is the trivial stuff; now try unquantizing a log scale codebook */ 633 634 exit(0); 635} 636 637#endif 638