/src/vorbis/lib/codebook.c
Line | Count | Source (jump to first uncovered line) |
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 https://xiph.org/ * |
10 | | * * |
11 | | ******************************************************************** |
12 | | |
13 | | function: basic codebook pack/unpack/code/decode operations |
14 | | |
15 | | ********************************************************************/ |
16 | | |
17 | | #include <stdlib.h> |
18 | | #include <string.h> |
19 | | #include <math.h> |
20 | | #include <ogg/ogg.h> |
21 | | #include "vorbis/codec.h" |
22 | | #include "codebook.h" |
23 | | #include "scales.h" |
24 | | #include "misc.h" |
25 | | #include "os.h" |
26 | | |
27 | | /* packs the given codebook into the bitstream **************************/ |
28 | | |
29 | 0 | int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){ |
30 | 0 | long i,j; |
31 | 0 | int ordered=0; |
32 | | |
33 | | /* first the basic parameters */ |
34 | 0 | oggpack_write(opb,0x564342,24); |
35 | 0 | oggpack_write(opb,c->dim,16); |
36 | 0 | oggpack_write(opb,c->entries,24); |
37 | | |
38 | | /* pack the codewords. There are two packings; length ordered and |
39 | | length random. Decide between the two now. */ |
40 | |
|
41 | 0 | for(i=1;i<c->entries;i++) |
42 | 0 | if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break; |
43 | 0 | if(i==c->entries)ordered=1; |
44 | |
|
45 | 0 | if(ordered){ |
46 | | /* length ordered. We only need to say how many codewords of |
47 | | each length. The actual codewords are generated |
48 | | deterministically */ |
49 | |
|
50 | 0 | long count=0; |
51 | 0 | oggpack_write(opb,1,1); /* ordered */ |
52 | 0 | oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */ |
53 | |
|
54 | 0 | for(i=1;i<c->entries;i++){ |
55 | 0 | char this=c->lengthlist[i]; |
56 | 0 | char last=c->lengthlist[i-1]; |
57 | 0 | if(this>last){ |
58 | 0 | for(j=last;j<this;j++){ |
59 | 0 | oggpack_write(opb,i-count,ov_ilog(c->entries-count)); |
60 | 0 | count=i; |
61 | 0 | } |
62 | 0 | } |
63 | 0 | } |
64 | 0 | oggpack_write(opb,i-count,ov_ilog(c->entries-count)); |
65 | |
|
66 | 0 | }else{ |
67 | | /* length random. Again, we don't code the codeword itself, just |
68 | | the length. This time, though, we have to encode each length */ |
69 | 0 | oggpack_write(opb,0,1); /* unordered */ |
70 | | |
71 | | /* algortihmic mapping has use for 'unused entries', which we tag |
72 | | here. The algorithmic mapping happens as usual, but the unused |
73 | | entry has no codeword. */ |
74 | 0 | for(i=0;i<c->entries;i++) |
75 | 0 | if(c->lengthlist[i]==0)break; |
76 | |
|
77 | 0 | if(i==c->entries){ |
78 | 0 | oggpack_write(opb,0,1); /* no unused entries */ |
79 | 0 | for(i=0;i<c->entries;i++) |
80 | 0 | oggpack_write(opb,c->lengthlist[i]-1,5); |
81 | 0 | }else{ |
82 | 0 | oggpack_write(opb,1,1); /* we have unused entries; thus we tag */ |
83 | 0 | for(i=0;i<c->entries;i++){ |
84 | 0 | if(c->lengthlist[i]==0){ |
85 | 0 | oggpack_write(opb,0,1); |
86 | 0 | }else{ |
87 | 0 | oggpack_write(opb,1,1); |
88 | 0 | oggpack_write(opb,c->lengthlist[i]-1,5); |
89 | 0 | } |
90 | 0 | } |
91 | 0 | } |
92 | 0 | } |
93 | | |
94 | | /* is the entry number the desired return value, or do we have a |
95 | | mapping? If we have a mapping, what type? */ |
96 | 0 | oggpack_write(opb,c->maptype,4); |
97 | 0 | switch(c->maptype){ |
98 | 0 | case 0: |
99 | | /* no mapping */ |
100 | 0 | break; |
101 | 0 | case 1:case 2: |
102 | | /* implicitly populated value mapping */ |
103 | | /* explicitly populated value mapping */ |
104 | |
|
105 | 0 | if(!c->quantlist){ |
106 | | /* no quantlist? error */ |
107 | 0 | return(-1); |
108 | 0 | } |
109 | | |
110 | | /* values that define the dequantization */ |
111 | 0 | oggpack_write(opb,c->q_min,32); |
112 | 0 | oggpack_write(opb,c->q_delta,32); |
113 | 0 | oggpack_write(opb,c->q_quant-1,4); |
114 | 0 | oggpack_write(opb,c->q_sequencep,1); |
115 | |
|
116 | 0 | { |
117 | 0 | int quantvals; |
118 | 0 | switch(c->maptype){ |
119 | 0 | case 1: |
120 | | /* a single column of (c->entries/c->dim) quantized values for |
121 | | building a full value list algorithmically (square lattice) */ |
122 | 0 | quantvals=_book_maptype1_quantvals(c); |
123 | 0 | break; |
124 | 0 | case 2: |
125 | | /* every value (c->entries*c->dim total) specified explicitly */ |
126 | 0 | quantvals=c->entries*c->dim; |
127 | 0 | break; |
128 | 0 | default: /* NOT_REACHABLE */ |
129 | 0 | quantvals=-1; |
130 | 0 | } |
131 | | |
132 | | /* quantized values */ |
133 | 0 | for(i=0;i<quantvals;i++) |
134 | 0 | oggpack_write(opb,labs(c->quantlist[i]),c->q_quant); |
135 | |
|
136 | 0 | } |
137 | 0 | break; |
138 | 0 | default: |
139 | | /* error case; we don't have any other map types now */ |
140 | 0 | return(-1); |
141 | 0 | } |
142 | | |
143 | 0 | return(0); |
144 | 0 | } |
145 | | |
146 | | /* unpacks a codebook from the packet buffer into the codebook struct, |
147 | | readies the codebook auxiliary structures for decode *************/ |
148 | 0 | static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){ |
149 | 0 | long i,j; |
150 | 0 | static_codebook *s=_ogg_calloc(1,sizeof(*s)); |
151 | 0 | s->allocedp=1; |
152 | | |
153 | | /* make sure alignment is correct */ |
154 | 0 | if(oggpack_read(opb,24)!=0x564342)goto _eofout; |
155 | | |
156 | | /* first the basic parameters */ |
157 | 0 | s->dim=oggpack_read(opb,16); |
158 | 0 | s->entries=oggpack_read(opb,24); |
159 | 0 | if(s->entries==-1)goto _eofout; |
160 | | |
161 | 0 | if(ov_ilog(s->dim)+ov_ilog(s->entries)>24)goto _eofout; |
162 | | |
163 | | /* codeword ordering.... length ordered or unordered? */ |
164 | 0 | switch((int)oggpack_read(opb,1)){ |
165 | 0 | case 0:{ |
166 | 0 | long unused; |
167 | | /* allocated but unused entries? */ |
168 | 0 | unused=oggpack_read(opb,1); |
169 | 0 | if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb)) |
170 | 0 | goto _eofout; |
171 | | /* unordered */ |
172 | 0 | s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries); |
173 | | |
174 | | /* allocated but unused entries? */ |
175 | 0 | if(unused){ |
176 | | /* yes, unused entries */ |
177 | |
|
178 | 0 | for(i=0;i<s->entries;i++){ |
179 | 0 | if(oggpack_read(opb,1)){ |
180 | 0 | long num=oggpack_read(opb,5); |
181 | 0 | if(num==-1)goto _eofout; |
182 | 0 | s->lengthlist[i]=num+1; |
183 | 0 | }else |
184 | 0 | s->lengthlist[i]=0; |
185 | 0 | } |
186 | 0 | }else{ |
187 | | /* all entries used; no tagging */ |
188 | 0 | for(i=0;i<s->entries;i++){ |
189 | 0 | long num=oggpack_read(opb,5); |
190 | 0 | if(num==-1)goto _eofout; |
191 | 0 | s->lengthlist[i]=num+1; |
192 | 0 | } |
193 | 0 | } |
194 | | |
195 | 0 | break; |
196 | 0 | } |
197 | 0 | case 1: |
198 | | /* ordered */ |
199 | 0 | { |
200 | 0 | long length=oggpack_read(opb,5)+1; |
201 | 0 | if(length==0)goto _eofout; |
202 | 0 | s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries); |
203 | |
|
204 | 0 | for(i=0;i<s->entries;){ |
205 | 0 | long num=oggpack_read(opb,ov_ilog(s->entries-i)); |
206 | 0 | if(num==-1)goto _eofout; |
207 | 0 | if(length>32 || num>s->entries-i || |
208 | 0 | (num>0 && (num-1)>>(length-1)>1)){ |
209 | 0 | goto _errout; |
210 | 0 | } |
211 | 0 | if(length>32)goto _errout; |
212 | 0 | for(j=0;j<num;j++,i++) |
213 | 0 | s->lengthlist[i]=length; |
214 | 0 | length++; |
215 | 0 | } |
216 | 0 | } |
217 | 0 | break; |
218 | 0 | default: |
219 | | /* EOF */ |
220 | 0 | goto _eofout; |
221 | 0 | } |
222 | | |
223 | | /* Do we have a mapping to unpack? */ |
224 | 0 | switch((s->maptype=oggpack_read(opb,4))){ |
225 | 0 | case 0: |
226 | | /* no mapping */ |
227 | 0 | break; |
228 | 0 | case 1: case 2: |
229 | | /* implicitly populated value mapping */ |
230 | | /* explicitly populated value mapping */ |
231 | |
|
232 | 0 | s->q_min=oggpack_read(opb,32); |
233 | 0 | s->q_delta=oggpack_read(opb,32); |
234 | 0 | s->q_quant=oggpack_read(opb,4)+1; |
235 | 0 | s->q_sequencep=oggpack_read(opb,1); |
236 | 0 | if(s->q_sequencep==-1)goto _eofout; |
237 | | |
238 | 0 | { |
239 | 0 | int quantvals=0; |
240 | 0 | switch(s->maptype){ |
241 | 0 | case 1: |
242 | 0 | quantvals=(s->dim==0?0:_book_maptype1_quantvals(s)); |
243 | 0 | break; |
244 | 0 | case 2: |
245 | 0 | quantvals=s->entries*s->dim; |
246 | 0 | break; |
247 | 0 | } |
248 | | |
249 | | /* quantized values */ |
250 | 0 | if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb)) |
251 | 0 | goto _eofout; |
252 | 0 | s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals); |
253 | 0 | for(i=0;i<quantvals;i++) |
254 | 0 | s->quantlist[i]=oggpack_read(opb,s->q_quant); |
255 | |
|
256 | 0 | if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout; |
257 | 0 | } |
258 | 0 | break; |
259 | 0 | default: |
260 | 0 | goto _errout; |
261 | 0 | } |
262 | | |
263 | | /* all set */ |
264 | 0 | return(s); |
265 | | |
266 | 0 | _errout: |
267 | 0 | _eofout: |
268 | 0 | vorbis_staticbook_destroy(s); |
269 | 0 | return(NULL); |
270 | 0 | } |
271 | | |
272 | | /* returns the number of bits ************************************************/ |
273 | 0 | int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){ |
274 | 0 | if(a<0 || a>=book->c->entries)return(0); |
275 | 0 | oggpack_write(b,book->codelist[a],book->c->lengthlist[a]); |
276 | 0 | return(book->c->lengthlist[a]); |
277 | 0 | } |
278 | | |
279 | | /* the 'eliminate the decode tree' optimization actually requires the |
280 | | codewords to be MSb first, not LSb. This is an annoying inelegancy |
281 | | (and one of the first places where carefully thought out design |
282 | | turned out to be wrong; Vorbis II and future Ogg codecs should go |
283 | | to an MSb bitpacker), but not actually the huge hit it appears to |
284 | | be. The first-stage decode table catches most words so that |
285 | | bitreverse is not in the main execution path. */ |
286 | | |
287 | 0 | static ogg_uint32_t bitreverse(ogg_uint32_t x){ |
288 | 0 | x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000); |
289 | 0 | x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00); |
290 | 0 | x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0); |
291 | 0 | x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc); |
292 | 0 | return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa); |
293 | 0 | } |
294 | | |
295 | 0 | STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){ |
296 | 0 | int read=book->dec_maxlength; |
297 | 0 | long lo,hi; |
298 | 0 | long lok = oggpack_look(b,book->dec_firsttablen); |
299 | |
|
300 | 0 | if (lok >= 0) { |
301 | 0 | long entry = book->dec_firsttable[lok]; |
302 | 0 | if(entry&0x80000000UL){ |
303 | 0 | lo=(entry>>15)&0x7fff; |
304 | 0 | hi=book->used_entries-(entry&0x7fff); |
305 | 0 | }else{ |
306 | 0 | oggpack_adv(b, book->dec_codelengths[entry-1]); |
307 | 0 | return(entry-1); |
308 | 0 | } |
309 | 0 | }else{ |
310 | 0 | lo=0; |
311 | 0 | hi=book->used_entries; |
312 | 0 | } |
313 | | |
314 | | /* Single entry codebooks use a firsttablen of 1 and a |
315 | | dec_maxlength of 1. If a single-entry codebook gets here (due to |
316 | | failure to read one bit above), the next look attempt will also |
317 | | fail and we'll correctly kick out instead of trying to walk the |
318 | | underformed tree */ |
319 | | |
320 | 0 | lok = oggpack_look(b, read); |
321 | |
|
322 | 0 | while(lok<0 && read>1) |
323 | 0 | lok = oggpack_look(b, --read); |
324 | 0 | if(lok<0)return -1; |
325 | | |
326 | | /* bisect search for the codeword in the ordered list */ |
327 | 0 | { |
328 | 0 | ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok); |
329 | |
|
330 | 0 | while(hi-lo>1){ |
331 | 0 | long p=(hi-lo)>>1; |
332 | 0 | long test=book->codelist[lo+p]>testword; |
333 | 0 | lo+=p&(test-1); |
334 | 0 | hi-=p&(-test); |
335 | 0 | } |
336 | |
|
337 | 0 | if(book->dec_codelengths[lo]<=read){ |
338 | 0 | oggpack_adv(b, book->dec_codelengths[lo]); |
339 | 0 | return(lo); |
340 | 0 | } |
341 | 0 | } |
342 | | |
343 | 0 | oggpack_adv(b, read); |
344 | |
|
345 | 0 | return(-1); |
346 | 0 | } |
347 | | |
348 | | /* Decode side is specced and easier, because we don't need to find |
349 | | matches using different criteria; we simply read and map. There are |
350 | | two things we need to do 'depending': |
351 | | |
352 | | We may need to support interleave. We don't really, but it's |
353 | | convenient to do it here rather than rebuild the vector later. |
354 | | |
355 | | Cascades may be additive or multiplicitive; this is not inherent in |
356 | | the codebook, but set in the code using the codebook. Like |
357 | | interleaving, it's easiest to do it here. |
358 | | addmul==0 -> declarative (set the value) |
359 | | addmul==1 -> additive |
360 | | addmul==2 -> multiplicitive */ |
361 | | |
362 | | /* returns the [original, not compacted] entry number or -1 on eof *********/ |
363 | 0 | long vorbis_book_decode(codebook *book, oggpack_buffer *b){ |
364 | 0 | if(book->used_entries>0){ |
365 | 0 | long packed_entry=decode_packed_entry_number(book,b); |
366 | 0 | if(packed_entry>=0) |
367 | 0 | return(book->dec_index[packed_entry]); |
368 | 0 | } |
369 | | |
370 | | /* if there's no dec_index, the codebook unpacking isn't collapsed */ |
371 | 0 | return(-1); |
372 | 0 | } |
373 | | |
374 | | /* returns 0 on OK or -1 on eof *************************************/ |
375 | | /* decode vector / dim granularity gaurding is done in the upper layer */ |
376 | 0 | long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){ |
377 | 0 | if(book->used_entries>0){ |
378 | 0 | int step=n/book->dim; |
379 | 0 | long *entry = alloca(sizeof(*entry)*step); |
380 | 0 | float **t = alloca(sizeof(*t)*step); |
381 | 0 | int i,j,o; |
382 | |
|
383 | 0 | for (i = 0; i < step; i++) { |
384 | 0 | entry[i]=decode_packed_entry_number(book,b); |
385 | 0 | if(entry[i]==-1)return(-1); |
386 | 0 | t[i] = book->valuelist+entry[i]*book->dim; |
387 | 0 | } |
388 | 0 | for(i=0,o=0;i<book->dim;i++,o+=step) |
389 | 0 | for (j=0;o+j<n && j<step;j++) |
390 | 0 | a[o+j]+=t[j][i]; |
391 | 0 | } |
392 | 0 | return(0); |
393 | 0 | } |
394 | | |
395 | | /* decode vector / dim granularity gaurding is done in the upper layer */ |
396 | 0 | long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){ |
397 | 0 | if(book->used_entries>0){ |
398 | 0 | int i,j,entry; |
399 | 0 | float *t; |
400 | |
|
401 | 0 | for(i=0;i<n;){ |
402 | 0 | entry = decode_packed_entry_number(book,b); |
403 | 0 | if(entry==-1)return(-1); |
404 | 0 | t = book->valuelist+entry*book->dim; |
405 | 0 | for(j=0;i<n && j<book->dim;) |
406 | 0 | a[i++]+=t[j++]; |
407 | 0 | } |
408 | 0 | } |
409 | 0 | return(0); |
410 | 0 | } |
411 | | |
412 | | /* unlike the others, we guard against n not being an integer number |
413 | | of <dim> internally rather than in the upper layer (called only by |
414 | | floor0) */ |
415 | 0 | long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){ |
416 | 0 | if(book->used_entries>0){ |
417 | 0 | int i,j,entry; |
418 | 0 | float *t; |
419 | |
|
420 | 0 | for(i=0;i<n;){ |
421 | 0 | entry = decode_packed_entry_number(book,b); |
422 | 0 | if(entry==-1)return(-1); |
423 | 0 | t = book->valuelist+entry*book->dim; |
424 | 0 | for (j=0;i<n && j<book->dim;){ |
425 | 0 | a[i++]=t[j++]; |
426 | 0 | } |
427 | 0 | } |
428 | 0 | }else{ |
429 | 0 | int i; |
430 | |
|
431 | 0 | for(i=0;i<n;){ |
432 | 0 | a[i++]=0.f; |
433 | 0 | } |
434 | 0 | } |
435 | 0 | return(0); |
436 | 0 | } |
437 | | |
438 | | long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch, |
439 | 0 | oggpack_buffer *b,int n){ |
440 | |
|
441 | 0 | long i,j,entry; |
442 | 0 | int chptr=0; |
443 | 0 | if(book->used_entries>0){ |
444 | 0 | int m=(offset+n)/ch; |
445 | 0 | for(i=offset/ch;i<m;){ |
446 | 0 | entry = decode_packed_entry_number(book,b); |
447 | 0 | if(entry==-1)return(-1); |
448 | 0 | { |
449 | 0 | const float *t = book->valuelist+entry*book->dim; |
450 | 0 | for (j=0;i<m && j<book->dim;j++){ |
451 | 0 | a[chptr++][i]+=t[j]; |
452 | 0 | if(chptr==ch){ |
453 | 0 | chptr=0; |
454 | 0 | i++; |
455 | 0 | } |
456 | 0 | } |
457 | 0 | } |
458 | 0 | } |
459 | 0 | } |
460 | 0 | return(0); |
461 | 0 | } |