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-2015 *
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 19457 2015-03-03 00:15:29Z giles $
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
vorbis_staticbook_pack(const static_codebook * c,oggpack_buffer * opb)30 int 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 char this=c->lengthlist[i];
57 char last=c->lengthlist[i-1];
58 if(this>last){
59 for(j=last;j<this;j++){
60 oggpack_write(opb,i-count,ov_ilog(c->entries-count));
61 count=i;
62 }
63 }
64 }
65 oggpack_write(opb,i-count,ov_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 *************/
vorbis_staticbook_unpack(oggpack_buffer * opb)149 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
150 long i,j;
151 static_codebook *s=_ogg_calloc(1,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(ov_ilog(s->dim)+ov_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 long unused;
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))
171 goto _eofout;
172 /* unordered */
173 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
174
175 /* allocated but unused entries? */
176 if(unused){
177 /* yes, unused entries */
178
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;
184 }else
185 s->lengthlist[i]=0;
186 }
187 }else{
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;
193 }
194 }
195
196 break;
197 }
198 case 1:
199 /* ordered */
200 {
201 long length=oggpack_read(opb,5)+1;
202 if(length==0)goto _eofout;
203 s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
204
205 for(i=0;i<s->entries;){
206 long num=oggpack_read(opb,ov_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)){
210 goto _errout;
211 }
212 if(length>32)goto _errout;
213 for(j=0;j<num;j++,i++)
214 s->lengthlist[i]=length;
215 length++;
216 }
217 }
218 break;
219 default:
220 /* EOF */
221 goto _eofout;
222 }
223
224 /* Do we have a mapping to unpack? */
225 switch((s->maptype=oggpack_read(opb,4))){
226 case 0:
227 /* no mapping */
228 break;
229 case 1: case 2:
230 /* implicitly populated value mapping */
231 /* explicitly populated value mapping */
232
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;
238
239 {
240 int quantvals=0;
241 switch(s->maptype){
242 case 1:
243 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
244 break;
245 case 2:
246 quantvals=s->entries*s->dim;
247 break;
248 }
249
250 /* quantized values */
251 if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
252 goto _eofout;
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);
256
257 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
258 }
259 break;
260 default:
261 goto _errout;
262 }
263
264 /* all set */
265 return(s);
266
267 _errout:
268 _eofout:
269 vorbis_staticbook_destroy(s);
270 return(NULL);
271 }
272
273 /* returns the number of bits ************************************************/
vorbis_book_encode(codebook * book,int a,oggpack_buffer * b)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]);
278 }
279
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. */
287
bitreverse(ogg_uint32_t x)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);
294 }
295
decode_packed_entry_number(codebook * book,oggpack_buffer * b)296 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
297 int read=book->dec_maxlength;
298 long lo,hi;
299 long lok = oggpack_look(b,book->dec_firsttablen);
300
301 if (lok >= 0) {
302 long entry = book->dec_firsttable[lok];
303 if(entry&0x80000000UL){
304 lo=(entry>>15)&0x7fff;
305 hi=book->used_entries-(entry&0x7fff);
306 }else{
307 oggpack_adv(b, book->dec_codelengths[entry-1]);
308 return(entry-1);
309 }
310 }else{
311 lo=0;
312 hi=book->used_entries;
313 }
314
315 /* Single entry codebooks use a firsttablen of 1 and a
316 dec_maxlength of 1. If a single-entry codebook gets here (due to
317 failure to read one bit above), the next look attempt will also
318 fail and we'll correctly kick out instead of trying to walk the
319 underformed tree */
320
321 lok = oggpack_look(b, read);
322
323 while(lok<0 && read>1)
324 lok = oggpack_look(b, --read);
325 if(lok<0)return -1;
326
327 /* bisect search for the codeword in the ordered list */
328 {
329 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
330
331 while(hi-lo>1){
332 long p=(hi-lo)>>1;
333 long test=book->codelist[lo+p]>testword;
334 lo+=p&(test-1);
335 hi-=p&(-test);
336 }
337
338 if(book->dec_codelengths[lo]<=read){
339 oggpack_adv(b, book->dec_codelengths[lo]);
340 return(lo);
341 }
342 }
343
344 oggpack_adv(b, read);
345
346 return(-1);
347 }
348
349 /* Decode side is specced and easier, because we don't need to find
350 matches using different criteria; we simply read and map. There are
351 two things we need to do 'depending':
352
353 We may need to support interleave. We don't really, but it's
354 convenient to do it here rather than rebuild the vector later.
355
356 Cascades may be additive or multiplicitive; this is not inherent in
357 the codebook, but set in the code using the codebook. Like
358 interleaving, it's easiest to do it here.
359 addmul==0 -> declarative (set the value)
360 addmul==1 -> additive
361 addmul==2 -> multiplicitive */
362
363 /* returns the [original, not compacted] entry number or -1 on eof *********/
vorbis_book_decode(codebook * book,oggpack_buffer * b)364 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
365 if(book->used_entries>0){
366 long packed_entry=decode_packed_entry_number(book,b);
367 if(packed_entry>=0)
368 return(book->dec_index[packed_entry]);
369 }
370
371 /* if there's no dec_index, the codebook unpacking isn't collapsed */
372 return(-1);
373 }
374
375 /* returns 0 on OK or -1 on eof *************************************/
376 /* decode vector / dim granularity gaurding is done in the upper layer */
vorbis_book_decodevs_add(codebook * book,float * a,oggpack_buffer * b,int n)377 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
378 if(book->used_entries>0){
379 int step=n/book->dim;
380 long *entry = alloca(sizeof(*entry)*step);
381 float **t = alloca(sizeof(*t)*step);
382 int i,j,o;
383
384 for (i = 0; i < step; i++) {
385 entry[i]=decode_packed_entry_number(book,b);
386 if(entry[i]==-1)return(-1);
387 t[i] = book->valuelist+entry[i]*book->dim;
388 }
389 for(i=0,o=0;i<book->dim;i++,o+=step)
390 for (j=0;j<step;j++)
391 a[o+j]+=t[j][i];
392 }
393 return(0);
394 }
395
396 /* decode vector / dim granularity gaurding is done in the upper layer */
vorbis_book_decodev_add(codebook * book,float * a,oggpack_buffer * b,int n)397 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
398 if(book->used_entries>0){
399 int i,j,entry;
400 float *t;
401
402 if(book->dim>8){
403 for(i=0;i<n;){
404 entry = decode_packed_entry_number(book,b);
405 if(entry==-1)return(-1);
406 t = book->valuelist+entry*book->dim;
407 for (j=0;j<book->dim;)
408 a[i++]+=t[j++];
409 }
410 }else{
411 for(i=0;i<n;){
412 entry = decode_packed_entry_number(book,b);
413 if(entry==-1)return(-1);
414 t = book->valuelist+entry*book->dim;
415 j=0;
416 switch((int)book->dim){
417 case 8:
418 a[i++]+=t[j++];
419 case 7:
420 a[i++]+=t[j++];
421 case 6:
422 a[i++]+=t[j++];
423 case 5:
424 a[i++]+=t[j++];
425 case 4:
426 a[i++]+=t[j++];
427 case 3:
428 a[i++]+=t[j++];
429 case 2:
430 a[i++]+=t[j++];
431 case 1:
432 a[i++]+=t[j++];
433 case 0:
434 break;
435 }
436 }
437 }
438 }
439 return(0);
440 }
441
442 /* unlike the others, we guard against n not being an integer number
443 of <dim> internally rather than in the upper layer (called only by
444 floor0) */
vorbis_book_decodev_set(codebook * book,float * a,oggpack_buffer * b,int n)445 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
446 if(book->used_entries>0){
447 int i,j,entry;
448 float *t;
449
450 for(i=0;i<n;){
451 entry = decode_packed_entry_number(book,b);
452 if(entry==-1)return(-1);
453 t = book->valuelist+entry*book->dim;
454 for (j=0;i<n && j<book->dim;){
455 a[i++]=t[j++];
456 }
457 }
458 }else{
459 int i;
460
461 for(i=0;i<n;){
462 a[i++]=0.f;
463 }
464 }
465 return(0);
466 }
467
vorbis_book_decodevv_add(codebook * book,float ** a,long offset,int ch,oggpack_buffer * b,int n)468 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
469 oggpack_buffer *b,int n){
470
471 long i,j,entry;
472 int chptr=0;
473 if(book->used_entries>0){
474 for(i=offset/ch;i<(offset+n)/ch;){
475 entry = decode_packed_entry_number(book,b);
476 if(entry==-1)return(-1);
477 {
478 const float *t = book->valuelist+entry*book->dim;
479 for (j=0;j<book->dim;j++){
480 a[chptr++][i]+=t[j];
481 if(chptr==ch){
482 chptr=0;
483 i++;
484 }
485 }
486 }
487 }
488 }
489 return(0);
490 }
491