vrshoot

annotate libs/vorbis/codebook.c @ 1:e7ca128b8713

looks nice :)
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 02 Feb 2014 00:35:22 +0200
parents
children
rev   line source
nuclear@0 1 /********************************************************************
nuclear@0 2 * *
nuclear@0 3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
nuclear@0 4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
nuclear@0 5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
nuclear@0 6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
nuclear@0 7 * *
nuclear@0 8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009 *
nuclear@0 9 * by the Xiph.Org Foundation http://www.xiph.org/ *
nuclear@0 10 * *
nuclear@0 11 ********************************************************************
nuclear@0 12
nuclear@0 13 function: basic codebook pack/unpack/code/decode operations
nuclear@0 14 last mod: $Id: codebook.c 18183 2012-02-03 20:51:27Z xiphmont $
nuclear@0 15
nuclear@0 16 ********************************************************************/
nuclear@0 17
nuclear@0 18 #include <stdlib.h>
nuclear@0 19 #include <string.h>
nuclear@0 20 #include <math.h>
nuclear@0 21 #include <ogg/ogg.h>
nuclear@0 22 #include "vorbis/codec.h"
nuclear@0 23 #include "codebook.h"
nuclear@0 24 #include "scales.h"
nuclear@0 25 #include "misc.h"
nuclear@0 26 #include "os.h"
nuclear@0 27
nuclear@0 28 /* packs the given codebook into the bitstream **************************/
nuclear@0 29
nuclear@0 30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
nuclear@0 31 long i,j;
nuclear@0 32 int ordered=0;
nuclear@0 33
nuclear@0 34 /* first the basic parameters */
nuclear@0 35 oggpack_write(opb,0x564342,24);
nuclear@0 36 oggpack_write(opb,c->dim,16);
nuclear@0 37 oggpack_write(opb,c->entries,24);
nuclear@0 38
nuclear@0 39 /* pack the codewords. There are two packings; length ordered and
nuclear@0 40 length random. Decide between the two now. */
nuclear@0 41
nuclear@0 42 for(i=1;i<c->entries;i++)
nuclear@0 43 if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
nuclear@0 44 if(i==c->entries)ordered=1;
nuclear@0 45
nuclear@0 46 if(ordered){
nuclear@0 47 /* length ordered. We only need to say how many codewords of
nuclear@0 48 each length. The actual codewords are generated
nuclear@0 49 deterministically */
nuclear@0 50
nuclear@0 51 long count=0;
nuclear@0 52 oggpack_write(opb,1,1); /* ordered */
nuclear@0 53 oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
nuclear@0 54
nuclear@0 55 for(i=1;i<c->entries;i++){
nuclear@0 56 long this=c->lengthlist[i];
nuclear@0 57 long last=c->lengthlist[i-1];
nuclear@0 58 if(this>last){
nuclear@0 59 for(j=last;j<this;j++){
nuclear@0 60 oggpack_write(opb,i-count,_ilog(c->entries-count));
nuclear@0 61 count=i;
nuclear@0 62 }
nuclear@0 63 }
nuclear@0 64 }
nuclear@0 65 oggpack_write(opb,i-count,_ilog(c->entries-count));
nuclear@0 66
nuclear@0 67 }else{
nuclear@0 68 /* length random. Again, we don't code the codeword itself, just
nuclear@0 69 the length. This time, though, we have to encode each length */
nuclear@0 70 oggpack_write(opb,0,1); /* unordered */
nuclear@0 71
nuclear@0 72 /* algortihmic mapping has use for 'unused entries', which we tag
nuclear@0 73 here. The algorithmic mapping happens as usual, but the unused
nuclear@0 74 entry has no codeword. */
nuclear@0 75 for(i=0;i<c->entries;i++)
nuclear@0 76 if(c->lengthlist[i]==0)break;
nuclear@0 77
nuclear@0 78 if(i==c->entries){
nuclear@0 79 oggpack_write(opb,0,1); /* no unused entries */
nuclear@0 80 for(i=0;i<c->entries;i++)
nuclear@0 81 oggpack_write(opb,c->lengthlist[i]-1,5);
nuclear@0 82 }else{
nuclear@0 83 oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
nuclear@0 84 for(i=0;i<c->entries;i++){
nuclear@0 85 if(c->lengthlist[i]==0){
nuclear@0 86 oggpack_write(opb,0,1);
nuclear@0 87 }else{
nuclear@0 88 oggpack_write(opb,1,1);
nuclear@0 89 oggpack_write(opb,c->lengthlist[i]-1,5);
nuclear@0 90 }
nuclear@0 91 }
nuclear@0 92 }
nuclear@0 93 }
nuclear@0 94
nuclear@0 95 /* is the entry number the desired return value, or do we have a
nuclear@0 96 mapping? If we have a mapping, what type? */
nuclear@0 97 oggpack_write(opb,c->maptype,4);
nuclear@0 98 switch(c->maptype){
nuclear@0 99 case 0:
nuclear@0 100 /* no mapping */
nuclear@0 101 break;
nuclear@0 102 case 1:case 2:
nuclear@0 103 /* implicitly populated value mapping */
nuclear@0 104 /* explicitly populated value mapping */
nuclear@0 105
nuclear@0 106 if(!c->quantlist){
nuclear@0 107 /* no quantlist? error */
nuclear@0 108 return(-1);
nuclear@0 109 }
nuclear@0 110
nuclear@0 111 /* values that define the dequantization */
nuclear@0 112 oggpack_write(opb,c->q_min,32);
nuclear@0 113 oggpack_write(opb,c->q_delta,32);
nuclear@0 114 oggpack_write(opb,c->q_quant-1,4);
nuclear@0 115 oggpack_write(opb,c->q_sequencep,1);
nuclear@0 116
nuclear@0 117 {
nuclear@0 118 int quantvals;
nuclear@0 119 switch(c->maptype){
nuclear@0 120 case 1:
nuclear@0 121 /* a single column of (c->entries/c->dim) quantized values for
nuclear@0 122 building a full value list algorithmically (square lattice) */
nuclear@0 123 quantvals=_book_maptype1_quantvals(c);
nuclear@0 124 break;
nuclear@0 125 case 2:
nuclear@0 126 /* every value (c->entries*c->dim total) specified explicitly */
nuclear@0 127 quantvals=c->entries*c->dim;
nuclear@0 128 break;
nuclear@0 129 default: /* NOT_REACHABLE */
nuclear@0 130 quantvals=-1;
nuclear@0 131 }
nuclear@0 132
nuclear@0 133 /* quantized values */
nuclear@0 134 for(i=0;i<quantvals;i++)
nuclear@0 135 oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
nuclear@0 136
nuclear@0 137 }
nuclear@0 138 break;
nuclear@0 139 default:
nuclear@0 140 /* error case; we don't have any other map types now */
nuclear@0 141 return(-1);
nuclear@0 142 }
nuclear@0 143
nuclear@0 144 return(0);
nuclear@0 145 }
nuclear@0 146
nuclear@0 147 /* unpacks a codebook from the packet buffer into the codebook struct,
nuclear@0 148 readies the codebook auxiliary structures for decode *************/
nuclear@0 149 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
nuclear@0 150 long i,j;
nuclear@0 151 static_codebook *s=_ogg_calloc(1,sizeof(*s));
nuclear@0 152 s->allocedp=1;
nuclear@0 153
nuclear@0 154 /* make sure alignment is correct */
nuclear@0 155 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
nuclear@0 156
nuclear@0 157 /* first the basic parameters */
nuclear@0 158 s->dim=oggpack_read(opb,16);
nuclear@0 159 s->entries=oggpack_read(opb,24);
nuclear@0 160 if(s->entries==-1)goto _eofout;
nuclear@0 161
nuclear@0 162 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
nuclear@0 163
nuclear@0 164 /* codeword ordering.... length ordered or unordered? */
nuclear@0 165 switch((int)oggpack_read(opb,1)){
nuclear@0 166 case 0:{
nuclear@0 167 long unused;
nuclear@0 168 /* allocated but unused entries? */
nuclear@0 169 unused=oggpack_read(opb,1);
nuclear@0 170 if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
nuclear@0 171 goto _eofout;
nuclear@0 172 /* unordered */
nuclear@0 173 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
nuclear@0 174
nuclear@0 175 /* allocated but unused entries? */
nuclear@0 176 if(unused){
nuclear@0 177 /* yes, unused entries */
nuclear@0 178
nuclear@0 179 for(i=0;i<s->entries;i++){
nuclear@0 180 if(oggpack_read(opb,1)){
nuclear@0 181 long num=oggpack_read(opb,5);
nuclear@0 182 if(num==-1)goto _eofout;
nuclear@0 183 s->lengthlist[i]=num+1;
nuclear@0 184 }else
nuclear@0 185 s->lengthlist[i]=0;
nuclear@0 186 }
nuclear@0 187 }else{
nuclear@0 188 /* all entries used; no tagging */
nuclear@0 189 for(i=0;i<s->entries;i++){
nuclear@0 190 long num=oggpack_read(opb,5);
nuclear@0 191 if(num==-1)goto _eofout;
nuclear@0 192 s->lengthlist[i]=num+1;
nuclear@0 193 }
nuclear@0 194 }
nuclear@0 195
nuclear@0 196 break;
nuclear@0 197 }
nuclear@0 198 case 1:
nuclear@0 199 /* ordered */
nuclear@0 200 {
nuclear@0 201 long length=oggpack_read(opb,5)+1;
nuclear@0 202 if(length==0)goto _eofout;
nuclear@0 203 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
nuclear@0 204
nuclear@0 205 for(i=0;i<s->entries;){
nuclear@0 206 long num=oggpack_read(opb,_ilog(s->entries-i));
nuclear@0 207 if(num==-1)goto _eofout;
nuclear@0 208 if(length>32 || num>s->entries-i ||
nuclear@0 209 (num>0 && (num-1)>>(length-1)>1)){
nuclear@0 210 goto _errout;
nuclear@0 211 }
nuclear@0 212 if(length>32)goto _errout;
nuclear@0 213 for(j=0;j<num;j++,i++)
nuclear@0 214 s->lengthlist[i]=length;
nuclear@0 215 length++;
nuclear@0 216 }
nuclear@0 217 }
nuclear@0 218 break;
nuclear@0 219 default:
nuclear@0 220 /* EOF */
nuclear@0 221 goto _eofout;
nuclear@0 222 }
nuclear@0 223
nuclear@0 224 /* Do we have a mapping to unpack? */
nuclear@0 225 switch((s->maptype=oggpack_read(opb,4))){
nuclear@0 226 case 0:
nuclear@0 227 /* no mapping */
nuclear@0 228 break;
nuclear@0 229 case 1: case 2:
nuclear@0 230 /* implicitly populated value mapping */
nuclear@0 231 /* explicitly populated value mapping */
nuclear@0 232
nuclear@0 233 s->q_min=oggpack_read(opb,32);
nuclear@0 234 s->q_delta=oggpack_read(opb,32);
nuclear@0 235 s->q_quant=oggpack_read(opb,4)+1;
nuclear@0 236 s->q_sequencep=oggpack_read(opb,1);
nuclear@0 237 if(s->q_sequencep==-1)goto _eofout;
nuclear@0 238
nuclear@0 239 {
nuclear@0 240 int quantvals=0;
nuclear@0 241 switch(s->maptype){
nuclear@0 242 case 1:
nuclear@0 243 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
nuclear@0 244 break;
nuclear@0 245 case 2:
nuclear@0 246 quantvals=s->entries*s->dim;
nuclear@0 247 break;
nuclear@0 248 }
nuclear@0 249
nuclear@0 250 /* quantized values */
nuclear@0 251 if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
nuclear@0 252 goto _eofout;
nuclear@0 253 s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
nuclear@0 254 for(i=0;i<quantvals;i++)
nuclear@0 255 s->quantlist[i]=oggpack_read(opb,s->q_quant);
nuclear@0 256
nuclear@0 257 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
nuclear@0 258 }
nuclear@0 259 break;
nuclear@0 260 default:
nuclear@0 261 goto _errout;
nuclear@0 262 }
nuclear@0 263
nuclear@0 264 /* all set */
nuclear@0 265 return(s);
nuclear@0 266
nuclear@0 267 _errout:
nuclear@0 268 _eofout:
nuclear@0 269 vorbis_staticbook_destroy(s);
nuclear@0 270 return(NULL);
nuclear@0 271 }
nuclear@0 272
nuclear@0 273 /* returns the number of bits ************************************************/
nuclear@0 274 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
nuclear@0 275 if(a<0 || a>=book->c->entries)return(0);
nuclear@0 276 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
nuclear@0 277 return(book->c->lengthlist[a]);
nuclear@0 278 }
nuclear@0 279
nuclear@0 280 /* the 'eliminate the decode tree' optimization actually requires the
nuclear@0 281 codewords to be MSb first, not LSb. This is an annoying inelegancy
nuclear@0 282 (and one of the first places where carefully thought out design
nuclear@0 283 turned out to be wrong; Vorbis II and future Ogg codecs should go
nuclear@0 284 to an MSb bitpacker), but not actually the huge hit it appears to
nuclear@0 285 be. The first-stage decode table catches most words so that
nuclear@0 286 bitreverse is not in the main execution path. */
nuclear@0 287
nuclear@0 288 static ogg_uint32_t bitreverse(ogg_uint32_t x){
nuclear@0 289 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
nuclear@0 290 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
nuclear@0 291 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
nuclear@0 292 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
nuclear@0 293 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
nuclear@0 294 }
nuclear@0 295
nuclear@0 296 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
nuclear@0 297 int read=book->dec_maxlength;
nuclear@0 298 long lo,hi;
nuclear@0 299 long lok = oggpack_look(b,book->dec_firsttablen);
nuclear@0 300
nuclear@0 301 if (lok >= 0) {
nuclear@0 302 long entry = book->dec_firsttable[lok];
nuclear@0 303 if(entry&0x80000000UL){
nuclear@0 304 lo=(entry>>15)&0x7fff;
nuclear@0 305 hi=book->used_entries-(entry&0x7fff);
nuclear@0 306 }else{
nuclear@0 307 oggpack_adv(b, book->dec_codelengths[entry-1]);
nuclear@0 308 return(entry-1);
nuclear@0 309 }
nuclear@0 310 }else{
nuclear@0 311 lo=0;
nuclear@0 312 hi=book->used_entries;
nuclear@0 313 }
nuclear@0 314
nuclear@0 315 lok = oggpack_look(b, read);
nuclear@0 316
nuclear@0 317 while(lok<0 && read>1)
nuclear@0 318 lok = oggpack_look(b, --read);
nuclear@0 319 if(lok<0)return -1;
nuclear@0 320
nuclear@0 321 /* bisect search for the codeword in the ordered list */
nuclear@0 322 {
nuclear@0 323 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
nuclear@0 324
nuclear@0 325 while(hi-lo>1){
nuclear@0 326 long p=(hi-lo)>>1;
nuclear@0 327 long test=book->codelist[lo+p]>testword;
nuclear@0 328 lo+=p&(test-1);
nuclear@0 329 hi-=p&(-test);
nuclear@0 330 }
nuclear@0 331
nuclear@0 332 if(book->dec_codelengths[lo]<=read){
nuclear@0 333 oggpack_adv(b, book->dec_codelengths[lo]);
nuclear@0 334 return(lo);
nuclear@0 335 }
nuclear@0 336 }
nuclear@0 337
nuclear@0 338 oggpack_adv(b, read);
nuclear@0 339
nuclear@0 340 return(-1);
nuclear@0 341 }
nuclear@0 342
nuclear@0 343 /* Decode side is specced and easier, because we don't need to find
nuclear@0 344 matches using different criteria; we simply read and map. There are
nuclear@0 345 two things we need to do 'depending':
nuclear@0 346
nuclear@0 347 We may need to support interleave. We don't really, but it's
nuclear@0 348 convenient to do it here rather than rebuild the vector later.
nuclear@0 349
nuclear@0 350 Cascades may be additive or multiplicitive; this is not inherent in
nuclear@0 351 the codebook, but set in the code using the codebook. Like
nuclear@0 352 interleaving, it's easiest to do it here.
nuclear@0 353 addmul==0 -> declarative (set the value)
nuclear@0 354 addmul==1 -> additive
nuclear@0 355 addmul==2 -> multiplicitive */
nuclear@0 356
nuclear@0 357 /* returns the [original, not compacted] entry number or -1 on eof *********/
nuclear@0 358 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
nuclear@0 359 if(book->used_entries>0){
nuclear@0 360 long packed_entry=decode_packed_entry_number(book,b);
nuclear@0 361 if(packed_entry>=0)
nuclear@0 362 return(book->dec_index[packed_entry]);
nuclear@0 363 }
nuclear@0 364
nuclear@0 365 /* if there's no dec_index, the codebook unpacking isn't collapsed */
nuclear@0 366 return(-1);
nuclear@0 367 }
nuclear@0 368
nuclear@0 369 /* returns 0 on OK or -1 on eof *************************************/
nuclear@0 370 /* decode vector / dim granularity gaurding is done in the upper layer */
nuclear@0 371 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
nuclear@0 372 if(book->used_entries>0){
nuclear@0 373 int step=n/book->dim;
nuclear@0 374 long *entry = alloca(sizeof(*entry)*step);
nuclear@0 375 float **t = alloca(sizeof(*t)*step);
nuclear@0 376 int i,j,o;
nuclear@0 377
nuclear@0 378 for (i = 0; i < step; i++) {
nuclear@0 379 entry[i]=decode_packed_entry_number(book,b);
nuclear@0 380 if(entry[i]==-1)return(-1);
nuclear@0 381 t[i] = book->valuelist+entry[i]*book->dim;
nuclear@0 382 }
nuclear@0 383 for(i=0,o=0;i<book->dim;i++,o+=step)
nuclear@0 384 for (j=0;j<step;j++)
nuclear@0 385 a[o+j]+=t[j][i];
nuclear@0 386 }
nuclear@0 387 return(0);
nuclear@0 388 }
nuclear@0 389
nuclear@0 390 /* decode vector / dim granularity gaurding is done in the upper layer */
nuclear@0 391 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
nuclear@0 392 if(book->used_entries>0){
nuclear@0 393 int i,j,entry;
nuclear@0 394 float *t;
nuclear@0 395
nuclear@0 396 if(book->dim>8){
nuclear@0 397 for(i=0;i<n;){
nuclear@0 398 entry = decode_packed_entry_number(book,b);
nuclear@0 399 if(entry==-1)return(-1);
nuclear@0 400 t = book->valuelist+entry*book->dim;
nuclear@0 401 for (j=0;j<book->dim;)
nuclear@0 402 a[i++]+=t[j++];
nuclear@0 403 }
nuclear@0 404 }else{
nuclear@0 405 for(i=0;i<n;){
nuclear@0 406 entry = decode_packed_entry_number(book,b);
nuclear@0 407 if(entry==-1)return(-1);
nuclear@0 408 t = book->valuelist+entry*book->dim;
nuclear@0 409 j=0;
nuclear@0 410 switch((int)book->dim){
nuclear@0 411 case 8:
nuclear@0 412 a[i++]+=t[j++];
nuclear@0 413 case 7:
nuclear@0 414 a[i++]+=t[j++];
nuclear@0 415 case 6:
nuclear@0 416 a[i++]+=t[j++];
nuclear@0 417 case 5:
nuclear@0 418 a[i++]+=t[j++];
nuclear@0 419 case 4:
nuclear@0 420 a[i++]+=t[j++];
nuclear@0 421 case 3:
nuclear@0 422 a[i++]+=t[j++];
nuclear@0 423 case 2:
nuclear@0 424 a[i++]+=t[j++];
nuclear@0 425 case 1:
nuclear@0 426 a[i++]+=t[j++];
nuclear@0 427 case 0:
nuclear@0 428 break;
nuclear@0 429 }
nuclear@0 430 }
nuclear@0 431 }
nuclear@0 432 }
nuclear@0 433 return(0);
nuclear@0 434 }
nuclear@0 435
nuclear@0 436 /* unlike the others, we guard against n not being an integer number
nuclear@0 437 of <dim> internally rather than in the upper layer (called only by
nuclear@0 438 floor0) */
nuclear@0 439 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
nuclear@0 440 if(book->used_entries>0){
nuclear@0 441 int i,j,entry;
nuclear@0 442 float *t;
nuclear@0 443
nuclear@0 444 for(i=0;i<n;){
nuclear@0 445 entry = decode_packed_entry_number(book,b);
nuclear@0 446 if(entry==-1)return(-1);
nuclear@0 447 t = book->valuelist+entry*book->dim;
nuclear@0 448 for (j=0;i<n && j<book->dim;){
nuclear@0 449 a[i++]=t[j++];
nuclear@0 450 }
nuclear@0 451 }
nuclear@0 452 }else{
nuclear@0 453 int i;
nuclear@0 454
nuclear@0 455 for(i=0;i<n;){
nuclear@0 456 a[i++]=0.f;
nuclear@0 457 }
nuclear@0 458 }
nuclear@0 459 return(0);
nuclear@0 460 }
nuclear@0 461
nuclear@0 462 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
nuclear@0 463 oggpack_buffer *b,int n){
nuclear@0 464
nuclear@0 465 long i,j,entry;
nuclear@0 466 int chptr=0;
nuclear@0 467 if(book->used_entries>0){
nuclear@0 468 for(i=offset/ch;i<(offset+n)/ch;){
nuclear@0 469 entry = decode_packed_entry_number(book,b);
nuclear@0 470 if(entry==-1)return(-1);
nuclear@0 471 {
nuclear@0 472 const float *t = book->valuelist+entry*book->dim;
nuclear@0 473 for (j=0;j<book->dim;j++){
nuclear@0 474 a[chptr++][i]+=t[j];
nuclear@0 475 if(chptr==ch){
nuclear@0 476 chptr=0;
nuclear@0 477 i++;
nuclear@0 478 }
nuclear@0 479 }
nuclear@0 480 }
nuclear@0 481 }
nuclear@0 482 }
nuclear@0 483 return(0);
nuclear@0 484 }