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