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
16 ********************************************************************/
22 #include "vorbis/codec.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 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
170 /* allocated but unused entries? */
171 if(oggpack_read(opb,1)){
172 /* yes, unused entries */
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;
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;
195 long length=oggpack_read(opb,5)+1;
196 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
198 for(i=0;i<s->entries;){
199 long num=oggpack_read(opb,_ilog(s->entries-i));
200 if(num==-1)goto _eofout;
201 if(length>32)goto _errout;
202 for(j=0;j<num && i<s->entries;j++,i++)
203 s->lengthlist[i]=length;
213 /* Do we have a mapping to unpack? */
214 switch((s->maptype=oggpack_read(opb,4))){
219 /* implicitly populated value mapping */
220 /* explicitly populated value mapping */
222 s->q_min=oggpack_read(opb,32);
223 s->q_delta=oggpack_read(opb,32);
224 s->q_quant=oggpack_read(opb,4)+1;
225 s->q_sequencep=oggpack_read(opb,1);
226 if(s->q_sequencep==-1)goto _eofout;
232 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
235 quantvals=s->entries*s->dim;
239 /* quantized values */
240 s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
241 for(i=0;i<quantvals;i++)
242 s->quantlist[i]=oggpack_read(opb,s->q_quant);
244 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
256 vorbis_staticbook_destroy(s);
260 /* returns the number of bits ************************************************/
261 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
262 if(a<0 || a>=book->c->entries)return(0);
263 oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
264 return(book->c->lengthlist[a]);
267 /* the 'eliminate the decode tree' optimization actually requires the
268 codewords to be MSb first, not LSb. This is an annoying inelegancy
269 (and one of the first places where carefully thought out design
270 turned out to be wrong; Vorbis II and future Ogg codecs should go
271 to an MSb bitpacker), but not actually the huge hit it appears to
272 be. The first-stage decode table catches most words so that
273 bitreverse is not in the main execution path. */
275 static ogg_uint32_t bitreverse(ogg_uint32_t x){
276 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
277 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
278 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
279 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
280 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
283 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
284 int read=book->dec_maxlength;
286 long lok = oggpack_look(b,book->dec_firsttablen);
289 long entry = book->dec_firsttable[lok];
290 if(entry&0x80000000UL){
291 lo=(entry>>15)&0x7fff;
292 hi=book->used_entries-(entry&0x7fff);
294 oggpack_adv(b, book->dec_codelengths[entry-1]);
299 hi=book->used_entries;
302 lok = oggpack_look(b, read);
304 while(lok<0 && read>1)
305 lok = oggpack_look(b, --read);
308 /* bisect search for the codeword in the ordered list */
310 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
314 long test=book->codelist[lo+p]>testword;
319 if(book->dec_codelengths[lo]<=read){
320 oggpack_adv(b, book->dec_codelengths[lo]);
325 oggpack_adv(b, read);
330 /* Decode side is specced and easier, because we don't need to find
331 matches using different criteria; we simply read and map. There are
332 two things we need to do 'depending':
334 We may need to support interleave. We don't really, but it's
335 convenient to do it here rather than rebuild the vector later.
337 Cascades may be additive or multiplicitive; this is not inherent in
338 the codebook, but set in the code using the codebook. Like
339 interleaving, it's easiest to do it here.
340 addmul==0 -> declarative (set the value)
341 addmul==1 -> additive
342 addmul==2 -> multiplicitive */
344 /* returns the [original, not compacted] entry number or -1 on eof *********/
345 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
346 if(book->used_entries>0){
347 long packed_entry=decode_packed_entry_number(book,b);
349 return(book->dec_index[packed_entry]);
352 /* if there's no dec_index, the codebook unpacking isn't collapsed */
356 /* returns 0 on OK or -1 on eof *************************************/
357 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
358 if(book->used_entries>0){
359 int step=n/book->dim;
360 long *entry = alloca(sizeof(*entry)*step);
361 float **t = alloca(sizeof(*t)*step);
364 for (i = 0; i < step; i++) {
365 entry[i]=decode_packed_entry_number(book,b);
366 if(entry[i]==-1)return(-1);
367 t[i] = book->valuelist+entry[i]*book->dim;
369 for(i=0,o=0;i<book->dim;i++,o+=step)
376 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
377 if(book->used_entries>0){
383 entry = decode_packed_entry_number(book,b);
384 if(entry==-1)return(-1);
385 t = book->valuelist+entry*book->dim;
386 for (j=0;j<book->dim;)
391 entry = decode_packed_entry_number(book,b);
392 if(entry==-1)return(-1);
393 t = book->valuelist+entry*book->dim;
395 switch((int)book->dim){
421 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
422 if(book->used_entries>0){
427 entry = decode_packed_entry_number(book,b);
428 if(entry==-1)return(-1);
429 t = book->valuelist+entry*book->dim;
430 for (j=0;j<book->dim;)
437 for (j=0;j<book->dim;)
444 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
445 oggpack_buffer *b,int n){
449 if(book->used_entries>0){
450 for(i=offset/ch;i<(offset+n)/ch;){
451 entry = decode_packed_entry_number(book,b);
452 if(entry==-1)return(-1);
454 const float *t = book->valuelist+entry*book->dim;
455 for (j=0;j<book->dim;j++){