1 /********************************************************************
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. *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009 *
9 * by the Xiph.Org Foundation http://www.xiph.org/ *
11 ********************************************************************
13 function: basic codebook pack/unpack/code/decode operations
14 last mod: $Id: codebook.c 17553 2010-10-21 17:54:26Z tterribe $
16 ********************************************************************/
21 #include <ext/libogg/ogg.h>
28 /* packs the given codebook into the bitstream **************************/
30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
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);
39 /* pack the codewords. There are two packings; length ordered and
40 length random. Decide between the two now. */
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;
47 /* length ordered. We only need to say how many codewords of
48 each length. The actual codewords are generated
52 oggpack_write(opb,1,1); /* ordered */
53 oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
55 for(i=1;i<c->entries;i++){
56 long this=c->lengthlist[i];
57 long last=c->lengthlist[i-1];
59 for(j=last;j<this;j++){
60 oggpack_write(opb,i-count,_ilog(c->entries-count));
65 oggpack_write(opb,i-count,_ilog(c->entries-count));
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 */
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;
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);
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);
88 oggpack_write(opb,1,1);
89 oggpack_write(opb,c->lengthlist[i]-1,5);
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);
103 /* implicitly populated value mapping */
104 /* explicitly populated value mapping */
107 /* no quantlist? error */
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);
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);
126 /* every value (c->entries*c->dim total) specified explicitly */
127 quantvals=c->entries*c->dim;
129 default: /* NOT_REACHABLE */
133 /* quantized values */
134 for(i=0;i<quantvals;i++)
135 oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
140 /* error case; we don't have any other map types now */
147 /* unpacks a codebook from the packet buffer into the codebook struct,
148 readies the codebook auxiliary structures for decode *************/
149 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
151 static_codebook *s=_ogg_calloc(1,sizeof(*s));
154 /* make sure alignment is correct */
155 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
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;
162 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
164 /* codeword ordering.... length ordered or unordered? */
165 switch((int)oggpack_read(opb,1)){
168 /* allocated but unused entries? */
169 unused=oggpack_read(opb,1);
170 if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
173 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
175 /* allocated but unused entries? */
177 /* yes, unused entries */
179 for(i=0;i<s->entries;i++){
180 if(oggpack_read(opb,1)){
181 long num=oggpack_read(opb,5);
182 if(num==-1)goto _eofout;
183 s->lengthlist[i]=num+1;
188 /* all entries used; no tagging */
189 for(i=0;i<s->entries;i++){
190 long num=oggpack_read(opb,5);
191 if(num==-1)goto _eofout;
192 s->lengthlist[i]=num+1;
201 long length=oggpack_read(opb,5)+1;
202 if(length==0)goto _eofout;
203 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
205 for(i=0;i<s->entries;){
206 long num=oggpack_read(opb,_ilog(s->entries-i));
207 if(num==-1)goto _eofout;
208 if(length>32 || num>s->entries-i ||
209 (num>0 && (num-1)>>(length-1)>1)){
212 if(length>32)goto _errout;
213 for(j=0;j<num;j++,i++)
214 s->lengthlist[i]=length;
224 /* Do we have a mapping to unpack? */
225 switch((s->maptype=oggpack_read(opb,4))){
230 /* implicitly populated value mapping */
231 /* explicitly populated value mapping */
233 s->q_min=oggpack_read(opb,32);
234 s->q_delta=oggpack_read(opb,32);
235 s->q_quant=oggpack_read(opb,4)+1;
236 s->q_sequencep=oggpack_read(opb,1);
237 if(s->q_sequencep==-1)goto _eofout;
243 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
246 quantvals=s->entries*s->dim;
250 /* quantized values */
251 if((quantvals*s->q_quant+7>>3)>opb->storage-oggpack_bytes(opb))
253 s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
254 for(i=0;i<quantvals;i++)
255 s->quantlist[i]=oggpack_read(opb,s->q_quant);
257 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
269 vorbis_staticbook_destroy(s);
273 /* returns the number of bits ************************************************/
274 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
275 if(a<0 || a>=book->c->entries)return(0);
276 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
277 return(book->c->lengthlist[a]);
280 /* the 'eliminate the decode tree' optimization actually requires the
281 codewords to be MSb first, not LSb. This is an annoying inelegancy
282 (and one of the first places where carefully thought out design
283 turned out to be wrong; Vorbis II and future Ogg codecs should go
284 to an MSb bitpacker), but not actually the huge hit it appears to
285 be. The first-stage decode table catches most words so that
286 bitreverse is not in the main execution path. */
288 static ogg_uint32_t bitreverse(ogg_uint32_t x){
289 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
290 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
291 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
292 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
293 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
296 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
297 int read=book->dec_maxlength;
299 long lok = oggpack_look(b,book->dec_firsttablen);
302 long entry = book->dec_firsttable[lok];
303 if(entry&0x80000000UL){
304 lo=(entry>>15)&0x7fff;
305 hi=book->used_entries-(entry&0x7fff);
307 oggpack_adv(b, book->dec_codelengths[entry-1]);
312 hi=book->used_entries;
315 lok = oggpack_look(b, read);
317 while(lok<0 && read>1)
318 lok = oggpack_look(b, --read);
321 /* bisect search for the codeword in the ordered list */
323 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
327 long test=book->codelist[lo+p]>testword;
332 if(book->dec_codelengths[lo]<=read){
333 oggpack_adv(b, book->dec_codelengths[lo]);
338 oggpack_adv(b, read);
343 /* Decode side is specced and easier, because we don't need to find
344 matches using different criteria; we simply read and map. There are
345 two things we need to do 'depending':
347 We may need to support interleave. We don't really, but it's
348 convenient to do it here rather than rebuild the vector later.
350 Cascades may be additive or multiplicitive; this is not inherent in
351 the codebook, but set in the code using the codebook. Like
352 interleaving, it's easiest to do it here.
353 addmul==0 -> declarative (set the value)
354 addmul==1 -> additive
355 addmul==2 -> multiplicitive */
357 /* returns the [original, not compacted] entry number or -1 on eof *********/
358 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
359 if(book->used_entries>0){
360 long packed_entry=decode_packed_entry_number(book,b);
362 return(book->dec_index[packed_entry]);
365 /* if there's no dec_index, the codebook unpacking isn't collapsed */
369 /* returns 0 on OK or -1 on eof *************************************/
370 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
371 if(book->used_entries>0){
372 int step=n/book->dim;
373 long *entry = alloca(sizeof(*entry)*step);
374 float **t = alloca(sizeof(*t)*step);
377 for (i = 0; i < step; i++) {
378 entry[i]=decode_packed_entry_number(book,b);
379 if(entry[i]==-1)return(-1);
380 t[i] = book->valuelist+entry[i]*book->dim;
382 for(i=0,o=0;i<book->dim;i++,o+=step)
389 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
390 if(book->used_entries>0){
396 entry = decode_packed_entry_number(book,b);
397 if(entry==-1)return(-1);
398 t = book->valuelist+entry*book->dim;
399 for (j=0;j<book->dim;)
404 entry = decode_packed_entry_number(book,b);
405 if(entry==-1)return(-1);
406 t = book->valuelist+entry*book->dim;
408 switch((int)book->dim){
434 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
435 if(book->used_entries>0){
440 entry = decode_packed_entry_number(book,b);
441 if(entry==-1)return(-1);
442 t = book->valuelist+entry*book->dim;
443 for (j=0;j<book->dim;)
450 for (j=0;j<book->dim;)
457 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
458 oggpack_buffer *b,int n){
462 if(book->used_entries>0){
463 for(i=offset/ch;i<(offset+n)/ch;){
464 entry = decode_packed_entry_number(book,b);
465 if(entry==-1)return(-1);
467 const float *t = book->valuelist+entry*book->dim;
468 for (j=0;j<book->dim;j++){