1 /********************************************************************
2 * *
3 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. *
4 * *
5 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
6 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
7 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
8 * *
9 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002 *
10 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/ *
11 * *
12 ********************************************************************
13
14 function: basic shared codebook operations
15
16 ********************************************************************/
17
18 #include <stdlib.h>
19 #include <math.h>
20 #include <string.h>
21 #include "ogg.h"
22 #include "misc.h"
23 #include "ivorbiscodec.h"
24 #include "codebook.h"
25
26 /**** pack/unpack helpers ******************************************/
_ilog(unsigned int v)27 int _ilog(unsigned int v){
28 int ret=0;
29 while(v){
30 ret++;
31 v>>=1;
32 }
33 return(ret);
34 }
35
36 /* 32 bit float (not IEEE; nonnormalized mantissa +
37 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm
38 Why not IEEE? It's just not that important here. */
39
40 #define VQ_FEXP 10
41 #define VQ_FMAN 21
42 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
43
_float32_unpack(long val,int * point)44 static ogg_int32_t _float32_unpack(long val,int *point){
45 long mant=val&0x1fffff;
46 int sign=val&0x80000000;
47 long exp =(val&0x7fe00000L)>>VQ_FMAN;
48
49 exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS;
50
51 if(mant){
52 while(!(mant&0x40000000)){
53 mant<<=1;
54 exp-=1;
55 }
56
57 if(sign)mant= -mant;
58 }else{
59 sign=0;
60 exp=-9999;
61 }
62
63 *point=exp;
64 return mant;
65 }
66
67 /* given a list of word lengths, generate a list of codewords. Works
68 for length ordered or unordered, always assigns the lowest valued
69 codewords first. Extended to handle unused entries (length 0) */
_make_words(long * l,long n,long sparsecount)70 ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
71 long i,j,count=0;
72 ogg_uint32_t marker[33];
73 ogg_uint32_t *r=(ogg_uint32_t *)_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
74 memset(marker,0,sizeof(marker));
75
76 for(i=0;i<n;i++){
77 long length=l[i];
78 if(length>0){
79 ogg_uint32_t entry=marker[length];
80
81 /* when we claim a node for an entry, we also claim the nodes
82 below it (pruning off the imagined tree that may have dangled
83 from it) as well as blocking the use of any nodes directly
84 above for leaves */
85
86 /* update ourself */
87 if(length<32 && (entry>>length)){
88 /* error condition; the lengths must specify an overpopulated tree */
89 _ogg_free(r);
90 return(NULL);
91 }
92 r[count++]=entry;
93
94 /* Look to see if the next shorter marker points to the node
95 above. if so, update it and repeat. */
96 {
97 for(j=length;j>0;j--){
98
99 if(marker[j]&1){
100 /* have to jump branches */
101 if(j==1)
102 marker[1]++;
103 else
104 marker[j]=marker[j-1]<<1;
105 break; /* invariant says next upper marker would already
106 have been moved if it was on the same path */
107 }
108 marker[j]++;
109 }
110 }
111
112 /* prune the tree; the implicit invariant says all the longer
113 markers were dangling from our just-taken node. Dangle them
114 from our *new* node. */
115 for(j=length+1;j<33;j++)
116 if((marker[j]>>1) == entry){
117 entry=marker[j];
118 marker[j]=marker[j-1]<<1;
119 }else
120 break;
121 }else
122 if(sparsecount==0)count++;
123 }
124
125 /* bitreverse the words because our bitwise packer/unpacker is LSb
126 endian */
127 for(i=0,count=0;i<n;i++){
128 ogg_uint32_t temp=0;
129 for(j=0;j<l[i];j++){
130 temp<<=1;
131 temp|=(r[count]>>j)&1;
132 }
133
134 if(sparsecount){
135 if(l[i])
136 r[count++]=temp;
137 }else
138 r[count++]=temp;
139 }
140
141 return(r);
142 }
143
144 /* there might be a straightforward one-line way to do the below
145 that's portable and totally safe against roundoff, but I haven't
146 thought of it. Therefore, we opt on the side of caution */
_book_maptype1_quantvals(const static_codebook * b)147 long _book_maptype1_quantvals(const static_codebook *b){
148 /* get us a starting hint, we'll polish it below */
149 int bits=_ilog(b->entries);
150 int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
151
152 while(1){
153 long acc=1;
154 long acc1=1;
155 int i;
156 for(i=0;i<b->dim;i++){
157 acc*=vals;
158 acc1*=vals+1;
159 }
160 if(acc<=b->entries && acc1>b->entries){
161 return(vals);
162 }else{
163 if(acc>b->entries){
164 vals--;
165 }else{
166 vals++;
167 }
168 }
169 }
170 }
171
172 /* different than what _book_unquantize does for mainline:
173 we repack the book in a fixed point format that shares the same
174 binary point. Upon first use, we can shift point if needed */
175
176 /* we need to deal with two map types: in map type 1, the values are
177 generated algorithmically (each column of the vector counts through
178 the values in the quant vector). in map type 2, all the values came
179 in in an explicit list. Both value lists must be unpacked */
180
_book_unquantize(const static_codebook * b,int n,int * sparsemap,int * maxpoint)181 ogg_int32_t *_book_unquantize(const static_codebook *b,int n,int *sparsemap,
182 int *maxpoint){
183 long j,k,count=0;
184 if(b->maptype==1 || b->maptype==2){
185 int quantvals;
186 int minpoint,delpoint;
187 ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint);
188 ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint);
189 ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r));
190 int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp));
191
192 *maxpoint=minpoint;
193
194 /* maptype 1 and 2 both use a quantized value vector, but
195 different sizes */
196 switch(b->maptype){
197 case 1:
198 /* most of the time, entries%dimensions == 0, but we need to be
199 well defined. We define that the possible vales at each
200 scalar is values == entries/dim. If entries%dim != 0, we'll
201 have 'too few' values (values*dim<entries), which means that
202 we'll have 'left over' entries; left over entries use zeroed
203 values (and are wasted). So don't generate codebooks like
204 that */
205 quantvals=_book_maptype1_quantvals(b);
206 for(j=0;j<b->entries;j++){
207 if((sparsemap && b->lengthlist[j]) || !sparsemap){
208 ogg_int32_t last=0;
209 int lastpoint=0;
210 int indexdiv=1;
211 for(k=0;k<b->dim;k++){
212 int index= (j/indexdiv)%quantvals;
213 int point=0;
214 int val=VFLOAT_MULTI(delta,delpoint,
215 abs(b->quantlist[index]),&point);
216
217 val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
218 val=VFLOAT_ADD(last,lastpoint,val,point,&point);
219
220 if(b->q_sequencep){
221 last=val;
222 lastpoint=point;
223 }
224
225 if(sparsemap){
226 r[sparsemap[count]*b->dim+k]=val;
227 rp[sparsemap[count]*b->dim+k]=point;
228 }else{
229 r[count*b->dim+k]=val;
230 rp[count*b->dim+k]=point;
231 }
232 if(*maxpoint<point)*maxpoint=point;
233 indexdiv*=quantvals;
234 }
235 count++;
236 }
237
238 }
239 break;
240 case 2:
241 for(j=0;j<b->entries;j++){
242 if((sparsemap && b->lengthlist[j]) || !sparsemap){
243 ogg_int32_t last=0;
244 int lastpoint=0;
245
246 for(k=0;k<b->dim;k++){
247 int point=0;
248 int val=VFLOAT_MULTI(delta,delpoint,
249 abs(b->quantlist[j*b->dim+k]),&point);
250
251 val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
252 val=VFLOAT_ADD(last,lastpoint,val,point,&point);
253
254 if(b->q_sequencep){
255 last=val;
256 lastpoint=point;
257 }
258
259 if(sparsemap){
260 r[sparsemap[count]*b->dim+k]=val;
261 rp[sparsemap[count]*b->dim+k]=point;
262 }else{
263 r[count*b->dim+k]=val;
264 rp[count*b->dim+k]=point;
265 }
266 if(*maxpoint<point)*maxpoint=point;
267 }
268 count++;
269 }
270 }
271 break;
272 }
273
274 for(j=0;j<n*b->dim;j++)
275 if(rp[j]<*maxpoint)
276 r[j]>>=*maxpoint-rp[j];
277
278 _ogg_free(rp);
279 return(r);
280 }
281 return(NULL);
282 }
283
vorbis_staticbook_clear(static_codebook * b)284 void vorbis_staticbook_clear(static_codebook *b){
285 if(b->quantlist)_ogg_free(b->quantlist);
286 if(b->lengthlist)_ogg_free(b->lengthlist);
287 memset(b,0,sizeof(*b));
288
289 }
290
vorbis_staticbook_destroy(static_codebook * b)291 void vorbis_staticbook_destroy(static_codebook *b){
292 vorbis_staticbook_clear(b);
293 _ogg_free(b);
294 }
295
vorbis_book_clear(codebook * b)296 void vorbis_book_clear(codebook *b){
297 /* static book is not cleared; we're likely called on the lookup and
298 the static codebook belongs to the info struct */
299 if(b->valuelist)_ogg_free(b->valuelist);
300 if(b->codelist)_ogg_free(b->codelist);
301
302 if(b->dec_index)_ogg_free(b->dec_index);
303 if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
304 if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
305
306 memset(b,0,sizeof(*b));
307 }
308
bitreverse(ogg_uint32_t x)309 static ogg_uint32_t bitreverse(ogg_uint32_t x){
310 x= ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
311 x= ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
312 x= ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
313 x= ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
314 return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
315 }
316
sort32a(const void * a,const void * b)317 static int sort32a(const void *a,const void *b){
318 return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
319 (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
320 }
321
322 /* decode codebook arrangement is more heavily optimized than encode */
vorbis_book_init_decode(codebook * c,const static_codebook * s)323 int vorbis_book_init_decode(codebook *c,const static_codebook *s){
324 int i,j,n=0,tabn;
325 int *sortindex;
326 memset(c,0,sizeof(*c));
327
328 /* count actually used entries */
329 for(i=0;i<s->entries;i++)
330 if(s->lengthlist[i]>0)
331 n++;
332
333 c->entries=s->entries;
334 c->used_entries=n;
335 c->dim=s->dim;
336
337 if(n>0){
338 /* two different remappings go on here.
339
340 First, we collapse the likely sparse codebook down only to
341 actually represented values/words. This collapsing needs to be
342 indexed as map-valueless books are used to encode original entry
343 positions as integers.
344
345 Second, we reorder all vectors, including the entry index above,
346 by sorted bitreversed codeword to allow treeless decode. */
347
348 /* perform sort */
349 ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
350 ogg_uint32_t **codep=(ogg_uint32_t **)alloca(sizeof(*codep)*n);
351
352 if(codes==NULL)goto err_out;
353
354 for(i=0;i<n;i++){
355 codes[i]=bitreverse(codes[i]);
356 codep[i]=codes+i;
357 }
358
359 qsort(codep,n,sizeof(*codep),sort32a);
360
361 sortindex=(int *)alloca(n*sizeof(*sortindex));
362 c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist));
363 /* the index is a reverse index */
364 for(i=0;i<n;i++){
365 int position=codep[i]-codes;
366 sortindex[position]=i;
367 }
368
369 for(i=0;i<n;i++)
370 c->codelist[sortindex[i]]=codes[i];
371 _ogg_free(codes);
372
373
374
375 c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint);
376 c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index));
377
378 for(n=0,i=0;i<s->entries;i++)
379 if(s->lengthlist[i]>0)
380 c->dec_index[sortindex[n++]]=i;
381
382 c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths));
383 for(n=0,i=0;i<s->entries;i++)
384 if(s->lengthlist[i]>0)
385 c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
386
387 c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
388 if(c->dec_firsttablen<5)c->dec_firsttablen=5;
389 if(c->dec_firsttablen>8)c->dec_firsttablen=8;
390
391 tabn=1<<c->dec_firsttablen;
392 c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
393 c->dec_maxlength=0;
394
395 for(i=0;i<n;i++){
396 if(c->dec_maxlength<c->dec_codelengths[i])
397 c->dec_maxlength=c->dec_codelengths[i];
398 if(c->dec_codelengths[i]<=c->dec_firsttablen){
399 ogg_uint32_t orig=bitreverse(c->codelist[i]);
400 for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
401 c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
402 }
403 }
404
405 /* now fill in 'unused' entries in the firsttable with hi/lo search
406 hints for the non-direct-hits */
407 {
408 ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
409 long lo=0,hi=0;
410
411 for(i=0;i<tabn;i++){
412 ogg_uint32_t word=i<<(32-c->dec_firsttablen);
413 if(c->dec_firsttable[bitreverse(word)]==0){
414 while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
415 while( hi<n && word>=(c->codelist[hi]&mask))hi++;
416
417 /* we only actually have 15 bits per hint to play with here.
418 In order to overflow gracefully (nothing breaks, efficiency
419 just drops), encode as the difference from the extremes. */
420 {
421 unsigned long loval=lo;
422 unsigned long hival=n-hi;
423
424 if(loval>0x7fff)loval=0x7fff;
425 if(hival>0x7fff)hival=0x7fff;
426 c->dec_firsttable[bitreverse(word)]=
427 0x80000000UL | (loval<<15) | hival;
428 }
429 }
430 }
431 }
432 }
433
434 return(0);
435 err_out:
436 vorbis_book_clear(c);
437 return(-1);
438 }
439
440