1 /******************************************************************** 2 * * 3 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. * 4 * * 5 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * 6 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * 7 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * 8 * * 9 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002 * 10 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/ * 11 * * 12 ******************************************************************** 13 14 function: basic codebook pack/unpack/code/decode operations 15 16 ********************************************************************/ 17 18 #include <stdlib.h> 19 #include <string.h> 20 #include <math.h> 21 #include <ogg/ogg.h> 22 #include "ivorbiscodec.h" 23 #include "codebook.h" 24 #include "misc.h" 25 26 /* unpacks a codebook from the packet buffer into the codebook struct, 27 readies the codebook auxiliary structures for decode *************/ 28 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){ 29 long i,j; 30 static_codebook *s=_ogg_calloc(1,sizeof(*s)); 31 32 /* make sure alignment is correct */ 33 if(oggpack_read(opb,24)!=0x564342)goto _eofout; 34 35 /* first the basic parameters */ 36 s->dim=oggpack_read(opb,16); 37 s->entries=oggpack_read(opb,24); 38 if(s->entries==-1)goto _eofout; strip_trailoptnull39 40 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout; 41 42 /* codeword ordering.... length ordered or unordered? */ 43 switch((int)oggpack_read(opb,1)){ 44 case 0:{ 45 long unused; 46 /* allocated but unused entries? */ 47 unused=oggpack_read(opb,1); 48 if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb)) 49 goto _eofout; 50 /* unordered */ 51 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); 52 53 /* allocated but unused entries? */ 54 if(unused){ 55 /* yes, unused entries */ 56 57 for(i=0;i<s->entries;i++){ 58 if(oggpack_read(opb,1)){ 59 long num=oggpack_read(opb,5); 60 if(num==-1)goto _eofout; 61 s->lengthlist[i]=num+1; 62 }else 63 s->lengthlist[i]=0; 64 } 65 }else{ 66 /* all entries used; no tagging */ 67 for(i=0;i<s->entries;i++){ 68 long num=oggpack_read(opb,5); 69 if(num==-1)goto _eofout; 70 s->lengthlist[i]=num+1; 71 } 72 } 73 74 break; 75 } 76 case 1: 77 /* ordered */ 78 { 79 long length=oggpack_read(opb,5)+1; 80 if(length==0)goto _eofout; 81 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries); 82 83 for(i=0;i<s->entries;){ 84 long num=oggpack_read(opb,_ilog(s->entries-i)); 85 if(num==-1)goto _eofout; 86 if(length>32 || num>s->entries-i || 87 (num>0 && (num-1)>>(length>>1)>>((length+1)>>1))>0){ 88 goto _errout; 89 } 90 for(j=0;j<num;j++,i++) 91 s->lengthlist[i]=length; 92 length++; 93 } 94 } 95 break; 96 default: 97 /* EOF */ 98 goto _eofout; 99 } 100 101 /* Do we have a mapping to unpack? */ 102 switch((s->maptype=oggpack_read(opb,4))){ 103 case 0: 104 /* no mapping */ 105 break; 106 case 1: case 2: 107 /* implicitly populated value mapping */ 108 /* explicitly populated value mapping */ 109 110 s->q_min=oggpack_read(opb,32); 111 s->q_delta=oggpack_read(opb,32); 112 s->q_quant=oggpack_read(opb,4)+1; 113 s->q_sequencep=oggpack_read(opb,1); 114 if(s->q_sequencep==-1)goto _eofout; 115 116 { 117 int quantvals=0; 118 switch(s->maptype){ 119 case 1: 120 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s)); 121 break; 122 case 2: 123 quantvals=s->entries*s->dim; 124 break; 125 } 126 127 /* quantized values */ 128 if((quantvals*s->q_quant+7)>>3>opb->storage-oggpack_bytes(opb)) 129 goto _eofout; 130 s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals); 131 for(i=0;i<quantvals;i++) 132 s->quantlist[i]=oggpack_read(opb,s->q_quant); 133 134 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; 135 } 136 break; 137 default: 138 goto _errout; 139 } 140 141 /* all set */ 142 return(s); 143 144 _errout: 145 _eofout: 146 vorbis_staticbook_destroy(s); 147 return(NULL); 148 } 149 150 /* the 'eliminate the decode tree' optimization actually requires the 151 codewords to be MSb first, not LSb. This is an annoying inelegancy 152 (and one of the first places where carefully thought out design 153 turned out to be wrong; Vorbis II and future Ogg codecs should go 154 to an MSb bitpacker), but not actually the huge hit it appears to 155 be. The first-stage decode table catches most words so that 156 bitreverse is not in the main execution path. */ 157 158 static ogg_uint32_t bitreverse(ogg_uint32_t x){ 159 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000); 160 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00); 161 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0); 162 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc); 163 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa); 164 } 165 166 STIN long decode_packed_entry_number(codebook *book, 167 oggpack_buffer *b){ 168 int read=book->dec_maxlength; 169 long lo,hi; 170 long lok = oggpack_look(b,book->dec_firsttablen); 171 172 if (lok >= 0) { 173 long entry = book->dec_firsttable[lok]; 174 if(entry&0x80000000UL){ 175 lo=(entry>>15)&0x7fff; 176 hi=book->used_entries-(entry&0x7fff); 177 }else{ 178 oggpack_adv(b, book->dec_codelengths[entry-1]); 179 return(entry-1); 180 } 181 }else{ 182 lo=0; 183 hi=book->used_entries; 184 } 185 186 lok = oggpack_look(b, read); 187 188 while(lok<0 && read>1) 189 lok = oggpack_look(b, --read); 190 191 if(lok<0){ 192 oggpack_adv(b,1); /* force eop */ 193 return -1; 194 } 195 196 /* bisect search for the codeword in the ordered list */ 197 { 198 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); 199 200 while(hi-lo>1){ 201 long p=(hi-lo)>>1; 202 long test=book->codelist[lo+p]>testword; 203 lo+=p&(test-1); 204 hi-=p&(-test); 205 } 206 207 if(book->dec_codelengths[lo]<=read){ 208 oggpack_adv(b, book->dec_codelengths[lo]); 209 return(lo); 210 } 211 } 212 213 oggpack_adv(b, read+1); 214 return(-1); 215 } 216 217 /* Decode side is specced and easier, because we don't need to find 218 matches using different criteria; we simply read and map. There are 219 two things we need to do 'depending': 220 221 We may need to support interleave. We don't really, but it's 222 convenient to do it here rather than rebuild the vector later. 223 224 Cascades may be additive or multiplicitive; this is not inherent in 225 the codebook, but set in the code using the codebook. Like 226 interleaving, it's easiest to do it here. 227 addmul==0 -> declarative (set the value) 228 addmul==1 -> additive 229 addmul==2 -> multiplicitive */ 230 231 /* returns the [original, not compacted] entry number or -1 on eof *********/ 232 long vorbis_book_decode(codebook *book, oggpack_buffer *b){ 233 if(book->used_entries>0){ 234 long packed_entry=decode_packed_entry_number(book,b); 235 if(packed_entry>=0) 236 return(book->dec_index[packed_entry]); 237 } 238 239 /* if there's no dec_index, the codebook unpacking isn't collapsed */ 240 return(-1); 241 } 242 243 /* returns 0 on OK or -1 on eof *************************************/ 244 /* decode vector / dim granularity gaurding is done in the upper layer */ 245 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a, 246 oggpack_buffer *b,int n,int point){ 247 if(book->used_entries>0){ 248 int step=n/book->dim; 249 long *entry = (long *)alloca(sizeof(*entry)*step); 250 ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step); 251 int i,j,o; 252 int shift=point-book->binarypoint; 253 254 if(shift>=0){ 255 for (i = 0; i < step; i++) { 256 entry[i]=decode_packed_entry_number(book,b); 257 if(entry[i]==-1)return(-1); 258 t[i] = book->valuelist+entry[i]*book->dim; 259 } 260 for(i=0,o=0;i<book->dim;i++,o+=step) 261 for (j=0;j<step;j++) 262 a[o+j]+=t[j][i]>>shift; 263 }else{ 264 for (i = 0; i < step; i++) { 265 entry[i]=decode_packed_entry_number(book,b); 266 if(entry[i]==-1)return(-1); 267 t[i] = book->valuelist+entry[i]*book->dim; 268 } 269 for(i=0,o=0;i<book->dim;i++,o+=step) 270 for (j=0;j<step;j++) 271 a[o+j]+=t[j][i]<<-shift; 272 } 273 } 274 return(0); 275 } 276 277 /* decode vector / dim granularity gaurding is done in the upper layer */ 278 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a, 279 oggpack_buffer *b,int n,int point){ 280 if(book->used_entries>0){ 281 int i,j,entry; 282 ogg_int32_t *t; 283 int shift=point-book->binarypoint; 284 285 if(shift>=0){ 286 for(i=0;i<n;){ 287 entry = decode_packed_entry_number(book,b); 288 if(entry==-1)return(-1); 289 t = book->valuelist+entry*book->dim; 290 for (j=0;j<book->dim;) 291 a[i++]+=t[j++]>>shift; 292 } 293 }else{ 294 for(i=0;i<n;){ 295 entry = decode_packed_entry_number(book,b); 296 if(entry==-1)return(-1); 297 t = book->valuelist+entry*book->dim; 298 for (j=0;j<book->dim;) 299 a[i++]+=t[j++]<<-shift; 300 } 301 } 302 } 303 return(0); 304 } 305 306 /* unlike the others, we guard against n not being an integer number 307 of <dim> internally rather than in the upper layer (called only by 308 floor0) */ 309 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a, 310 oggpack_buffer *b,int n,int point){ 311 if(book->used_entries>0){ 312 int i,j,entry; 313 ogg_int32_t *t; 314 int shift=point-book->binarypoint; 315 316 if(shift>=0){ 317 318 for(i=0;i<n;){ 319 entry = decode_packed_entry_number(book,b); 320 if(entry==-1)return(-1); 321 t = book->valuelist+entry*book->dim; 322 for (j=0;i<n && j<book->dim;){ 323 a[i++]=t[j++]>>shift; 324 } 325 } 326 }else{ 327 328 for(i=0;i<n;){ 329 entry = decode_packed_entry_number(book,b); 330 if(entry==-1)return(-1); 331 t = book->valuelist+entry*book->dim; 332 for (j=0;i<n && j<book->dim;){ 333 a[i++]=t[j++]<<-shift; 334 } 335 } 336 } 337 }else{ 338 339 int i,j; 340 for(i=0;i<n;){ 341 a[i++]=0; 342 } 343 } 344 return(0); 345 } 346 347 /* decode vector / dim granularity gaurding is done in the upper layer */ 348 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\ 349 long offset,int ch, 350 oggpack_buffer *b,int n,int point){ 351 if(book->used_entries>0){ 352 long i,j,entry; 353 int chptr=0; 354 int shift=point-book->binarypoint; 355 356 if(shift>=0){ 357 358 for(i=offset;i<offset+n;){ 359 entry = decode_packed_entry_number(book,b); 360 if(entry==-1)return(-1); 361 { 362 const ogg_int32_t *t = book->valuelist+entry*book->dim; 363 for (j=0;j<book->dim;j++){ 364 a[chptr++][i]+=t[j]>>shift; 365 if(chptr==ch){ 366 chptr=0; 367 i++; 368 } 369 } 370 } 371 } 372 }else{ 373 374 for(i=offset;i<offset+n;){ 375 entry = decode_packed_entry_number(book,b); 376 if(entry==-1)return(-1); 377 { 378 const ogg_int32_t *t = book->valuelist+entry*book->dim; 379 for (j=0;j<book->dim;j++){ 380 a[chptr++][i]+=t[j]<<-shift; 381 if(chptr==ch){ 382 chptr=0; 383 i++; 384 } 385 } 386 } 387 } 388 } 389 } 390 return(0); 391 } 392