← Back to branch summary

~ubuntu-branches/ubuntu/utopic/hedgewars/utopic

« back to all changes in this revision

Viewing changes to misc/libtremor/tremor/sharedbook.c

  • Committer: Package Import Robot
  • Author(s): Gianfranco Costamagna
  • Date: 2014-01-02 12:37:23 UTC
  • mfrom: (19.1.5 sid)
  • Revision ID: package-import@ubuntu.com-20140102123723-6pdhmyj8tb5y8xbg
Tags: 0.9.20.3-1
New upstream minor release, suitable for unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
misc/libtremor/tremor/sharedbook.c
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 ******************************************/
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
 
 
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) */
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 */
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
 
 
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
 
 
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
 
 
291
 
void vorbis_staticbook_destroy(static_codebook *b){
292
 
  vorbis_staticbook_clear(b);
293
 
  _ogg_free(b);
294
 
}
295
 
 
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
 
 
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
 
 
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 */
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