Line data Source code
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$
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 :
30 0 : int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
31 : long i,j;
32 0 : int ordered=0;
33 :
34 : /* first the basic parameters */
35 0 : oggpack_write(opb,0x564342,24);
36 0 : oggpack_write(opb,c->dim,16);
37 0 : 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 0 : for(i=1;i<c->entries;i++)
43 0 : if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
44 0 : if(i==c->entries)ordered=1;
45 :
46 0 : 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 0 : long count=0;
52 0 : oggpack_write(opb,1,1); /* ordered */
53 0 : oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
54 :
55 0 : for(i=1;i<c->entries;i++){
56 0 : char this=c->lengthlist[i];
57 0 : char last=c->lengthlist[i-1];
58 0 : if(this>last){
59 0 : for(j=last;j<this;j++){
60 0 : oggpack_write(opb,i-count,ov_ilog(c->entries-count));
61 0 : count=i;
62 : }
63 : }
64 : }
65 0 : 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 0 : 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 0 : for(i=0;i<c->entries;i++)
76 0 : if(c->lengthlist[i]==0)break;
77 :
78 0 : if(i==c->entries){
79 0 : oggpack_write(opb,0,1); /* no unused entries */
80 0 : for(i=0;i<c->entries;i++)
81 0 : oggpack_write(opb,c->lengthlist[i]-1,5);
82 : }else{
83 0 : oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
84 0 : for(i=0;i<c->entries;i++){
85 0 : if(c->lengthlist[i]==0){
86 0 : oggpack_write(opb,0,1);
87 : }else{
88 0 : oggpack_write(opb,1,1);
89 0 : 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 0 : oggpack_write(opb,c->maptype,4);
98 0 : switch(c->maptype){
99 : case 0:
100 : /* no mapping */
101 0 : break;
102 : case 1:case 2:
103 : /* implicitly populated value mapping */
104 : /* explicitly populated value mapping */
105 :
106 0 : if(!c->quantlist){
107 : /* no quantlist? error */
108 0 : return(-1);
109 : }
110 :
111 : /* values that define the dequantization */
112 0 : oggpack_write(opb,c->q_min,32);
113 0 : oggpack_write(opb,c->q_delta,32);
114 0 : oggpack_write(opb,c->q_quant-1,4);
115 0 : oggpack_write(opb,c->q_sequencep,1);
116 :
117 : {
118 : int quantvals;
119 0 : 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 0 : quantvals=_book_maptype1_quantvals(c);
124 0 : break;
125 : case 2:
126 : /* every value (c->entries*c->dim total) specified explicitly */
127 0 : quantvals=c->entries*c->dim;
128 0 : break;
129 : default: /* NOT_REACHABLE */
130 0 : quantvals=-1;
131 : }
132 :
133 : /* quantized values */
134 0 : for(i=0;i<quantvals;i++)
135 0 : oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
136 :
137 : }
138 0 : break;
139 : default:
140 : /* error case; we don't have any other map types now */
141 0 : return(-1);
142 : }
143 :
144 0 : return(0);
145 : }
146 :
147 : /* unpacks a codebook from the packet buffer into the codebook struct,
148 : readies the codebook auxiliary structures for decode *************/
149 0 : static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
150 : long i,j;
151 0 : static_codebook *s=_ogg_calloc(1,sizeof(*s));
152 0 : s->allocedp=1;
153 :
154 : /* make sure alignment is correct */
155 0 : if(oggpack_read(opb,24)!=0x564342)goto _eofout;
156 :
157 : /* first the basic parameters */
158 0 : s->dim=oggpack_read(opb,16);
159 0 : s->entries=oggpack_read(opb,24);
160 0 : if(s->entries==-1)goto _eofout;
161 :
162 0 : if(ov_ilog(s->dim)+ov_ilog(s->entries)>24)goto _eofout;
163 :
164 : /* codeword ordering.... length ordered or unordered? */
165 0 : switch((int)oggpack_read(opb,1)){
166 : case 0:{
167 : long unused;
168 : /* allocated but unused entries? */
169 0 : unused=oggpack_read(opb,1);
170 0 : if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
171 0 : goto _eofout;
172 : /* unordered */
173 0 : s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
174 :
175 : /* allocated but unused entries? */
176 0 : if(unused){
177 : /* yes, unused entries */
178 :
179 0 : for(i=0;i<s->entries;i++){
180 0 : if(oggpack_read(opb,1)){
181 0 : long num=oggpack_read(opb,5);
182 0 : if(num==-1)goto _eofout;
183 0 : s->lengthlist[i]=num+1;
184 : }else
185 0 : s->lengthlist[i]=0;
186 : }
187 : }else{
188 : /* all entries used; no tagging */
189 0 : for(i=0;i<s->entries;i++){
190 0 : long num=oggpack_read(opb,5);
191 0 : if(num==-1)goto _eofout;
192 0 : s->lengthlist[i]=num+1;
193 : }
194 : }
195 :
196 0 : break;
197 : }
198 : case 1:
199 : /* ordered */
200 : {
201 0 : long length=oggpack_read(opb,5)+1;
202 0 : if(length==0)goto _eofout;
203 0 : s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
204 :
205 0 : for(i=0;i<s->entries;){
206 0 : long num=oggpack_read(opb,ov_ilog(s->entries-i));
207 0 : if(num==-1)goto _eofout;
208 0 : if(length>32 || num>s->entries-i ||
209 0 : (num>0 && (num-1)>>(length-1)>1)){
210 : goto _errout;
211 : }
212 0 : if(length>32)goto _errout;
213 0 : for(j=0;j<num;j++,i++)
214 0 : s->lengthlist[i]=length;
215 0 : length++;
216 : }
217 : }
218 0 : break;
219 : default:
220 : /* EOF */
221 0 : goto _eofout;
222 : }
223 :
224 : /* Do we have a mapping to unpack? */
225 0 : switch((s->maptype=oggpack_read(opb,4))){
226 : case 0:
227 : /* no mapping */
228 0 : break;
229 : case 1: case 2:
230 : /* implicitly populated value mapping */
231 : /* explicitly populated value mapping */
232 :
233 0 : s->q_min=oggpack_read(opb,32);
234 0 : s->q_delta=oggpack_read(opb,32);
235 0 : s->q_quant=oggpack_read(opb,4)+1;
236 0 : s->q_sequencep=oggpack_read(opb,1);
237 0 : if(s->q_sequencep==-1)goto _eofout;
238 :
239 : {
240 0 : int quantvals=0;
241 0 : switch(s->maptype){
242 : case 1:
243 0 : quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
244 0 : break;
245 : case 2:
246 0 : quantvals=s->entries*s->dim;
247 0 : break;
248 : }
249 :
250 : /* quantized values */
251 0 : if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
252 0 : goto _eofout;
253 0 : s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
254 0 : for(i=0;i<quantvals;i++)
255 0 : s->quantlist[i]=oggpack_read(opb,s->q_quant);
256 :
257 0 : if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
258 : }
259 0 : break;
260 : default:
261 0 : goto _errout;
262 : }
263 :
264 : /* all set */
265 0 : return(s);
266 :
267 : _errout:
268 : _eofout:
269 0 : vorbis_staticbook_destroy(s);
270 0 : return(NULL);
271 : }
272 :
273 : /* returns the number of bits ************************************************/
274 0 : int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
275 0 : if(a<0 || a>=book->c->entries)return(0);
276 0 : oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
277 0 : 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 :
288 0 : static ogg_uint32_t bitreverse(ogg_uint32_t x){
289 0 : x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
290 0 : x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
291 0 : x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
292 0 : x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
293 0 : return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
294 : }
295 :
296 0 : STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
297 0 : int read=book->dec_maxlength;
298 : long lo,hi;
299 0 : long lok = oggpack_look(b,book->dec_firsttablen);
300 :
301 0 : if (lok >= 0) {
302 0 : long entry = book->dec_firsttable[lok];
303 0 : if(entry&0x80000000UL){
304 0 : lo=(entry>>15)&0x7fff;
305 0 : hi=book->used_entries-(entry&0x7fff);
306 : }else{
307 0 : oggpack_adv(b, book->dec_codelengths[entry-1]);
308 0 : return(entry-1);
309 : }
310 : }else{
311 0 : lo=0;
312 0 : 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 0 : lok = oggpack_look(b, read);
322 :
323 0 : while(lok<0 && read>1)
324 0 : lok = oggpack_look(b, --read);
325 0 : if(lok<0)return -1;
326 :
327 : /* bisect search for the codeword in the ordered list */
328 : {
329 0 : ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
330 :
331 0 : while(hi-lo>1){
332 0 : long p=(hi-lo)>>1;
333 0 : long test=book->codelist[lo+p]>testword;
334 0 : lo+=p&(test-1);
335 0 : hi-=p&(-test);
336 : }
337 :
338 0 : if(book->dec_codelengths[lo]<=read){
339 0 : oggpack_adv(b, book->dec_codelengths[lo]);
340 0 : return(lo);
341 : }
342 : }
343 :
344 0 : oggpack_adv(b, read);
345 :
346 0 : 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 *********/
364 0 : long vorbis_book_decode(codebook *book, oggpack_buffer *b){
365 0 : if(book->used_entries>0){
366 0 : long packed_entry=decode_packed_entry_number(book,b);
367 0 : if(packed_entry>=0)
368 0 : return(book->dec_index[packed_entry]);
369 : }
370 :
371 : /* if there's no dec_index, the codebook unpacking isn't collapsed */
372 0 : 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 */
377 0 : long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
378 0 : if(book->used_entries>0){
379 0 : int step=n/book->dim;
380 0 : long *entry = alloca(sizeof(*entry)*step);
381 0 : float **t = alloca(sizeof(*t)*step);
382 : int i,j,o;
383 :
384 0 : for (i = 0; i < step; i++) {
385 0 : entry[i]=decode_packed_entry_number(book,b);
386 0 : if(entry[i]==-1)return(-1);
387 0 : t[i] = book->valuelist+entry[i]*book->dim;
388 : }
389 0 : for(i=0,o=0;i<book->dim;i++,o+=step)
390 0 : for (j=0;j<step;j++)
391 0 : a[o+j]+=t[j][i];
392 : }
393 0 : return(0);
394 : }
395 :
396 : /* decode vector / dim granularity gaurding is done in the upper layer */
397 0 : long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
398 0 : if(book->used_entries>0){
399 : int i,j,entry;
400 : float *t;
401 :
402 0 : if(book->dim>8){
403 0 : for(i=0;i<n;){
404 0 : entry = decode_packed_entry_number(book,b);
405 0 : if(entry==-1)return(-1);
406 0 : t = book->valuelist+entry*book->dim;
407 0 : for (j=0;j<book->dim;)
408 0 : a[i++]+=t[j++];
409 : }
410 : }else{
411 0 : for(i=0;i<n;){
412 0 : entry = decode_packed_entry_number(book,b);
413 0 : if(entry==-1)return(-1);
414 0 : t = book->valuelist+entry*book->dim;
415 0 : j=0;
416 0 : switch((int)book->dim){
417 : case 8:
418 0 : a[i++]+=t[j++];
419 : case 7:
420 0 : a[i++]+=t[j++];
421 : case 6:
422 0 : a[i++]+=t[j++];
423 : case 5:
424 0 : a[i++]+=t[j++];
425 : case 4:
426 0 : a[i++]+=t[j++];
427 : case 3:
428 0 : a[i++]+=t[j++];
429 : case 2:
430 0 : a[i++]+=t[j++];
431 : case 1:
432 0 : a[i++]+=t[j++];
433 : case 0:
434 0 : break;
435 : }
436 : }
437 : }
438 : }
439 0 : 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) */
445 0 : long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
446 0 : if(book->used_entries>0){
447 : int i,j,entry;
448 : float *t;
449 :
450 0 : for(i=0;i<n;){
451 0 : entry = decode_packed_entry_number(book,b);
452 0 : if(entry==-1)return(-1);
453 0 : t = book->valuelist+entry*book->dim;
454 0 : for (j=0;i<n && j<book->dim;){
455 0 : a[i++]=t[j++];
456 : }
457 : }
458 : }else{
459 : int i;
460 :
461 0 : for(i=0;i<n;){
462 0 : a[i++]=0.f;
463 : }
464 : }
465 0 : return(0);
466 : }
467 :
468 0 : 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 0 : int chptr=0;
473 0 : if(book->used_entries>0){
474 0 : for(i=offset/ch;i<(offset+n)/ch;){
475 0 : entry = decode_packed_entry_number(book,b);
476 0 : if(entry==-1)return(-1);
477 : {
478 0 : const float *t = book->valuelist+entry*book->dim;
479 0 : for (j=0;j<book->dim;j++){
480 0 : a[chptr++][i]+=t[j];
481 0 : if(chptr==ch){
482 0 : chptr=0;
483 0 : i++;
484 : }
485 : }
486 : }
487 : }
488 : }
489 0 : return(0);
490 : }
|
