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