Mercurial > mplayer.hg
annotate tremor/sharedbook.c @ 30811:50e0f6942e43
Implement Win32 mutexes.
Implement Win32 mutexes; they used to just be mapped on top of events, which
is not the same thing at all.
The implementation is pretty much the obvious one, similar to the
current critical section implementation and the semaphore implementation;
a single lock count protected by a pthread mutex, and an event lockers can
sleep on to know when the mutex is available.
Also make CreateMutexA and ReleaseMutex available even if QuickTime codecs
support is not configured.
author | sesse |
---|---|
date | Sat, 06 Mar 2010 10:13:37 +0000 |
parents | e83eef58b30a |
children |
rev | line source |
---|---|
14280 | 1 /******************************************************************** |
2 * * | |
3 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE. * | |
4 * * | |
19251
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
16266
diff
changeset
|
5 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
16266
diff
changeset
|
6 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
16266
diff
changeset
|
7 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
16266
diff
changeset
|
8 * * |
14280 | 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 "os.h" | |
23 #include "misc.h" | |
24 #include "ivorbiscodec.h" | |
25 #include "codebook.h" | |
26 | |
27 /**** pack/unpack helpers ******************************************/ | |
28 int _ilog(unsigned int v){ | |
29 int ret=0; | |
30 while(v){ | |
31 ret++; | |
32 v>>=1; | |
33 } | |
34 return(ret); | |
35 } | |
36 | |
37 /* 32 bit float (not IEEE; nonnormalized mantissa + | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
38 biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm |
14280 | 39 Why not IEEE? It's just not that important here. */ |
40 | |
41 #define VQ_FEXP 10 | |
42 #define VQ_FMAN 21 | |
43 #define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */ | |
44 | |
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; | |
49 | |
50 exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS; | |
51 | |
52 if(mant){ | |
53 while(!(mant&0x40000000)){ | |
54 mant<<=1; | |
55 exp-=1; | |
56 } | |
57 | |
58 if(sign)mant= -mant; | |
59 }else{ | |
60 sign=0; | |
61 exp=-9999; | |
62 } | |
63 | |
64 *point=exp; | |
65 return mant; | |
66 } | |
67 | |
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)); | |
76 | |
77 for(i=0;i<n;i++){ | |
78 long length=l[i]; | |
79 if(length>0){ | |
80 ogg_uint32_t entry=marker[length]; | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
81 |
14280 | 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 */ | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
86 |
14280 | 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); | |
92 } | |
93 r[count++]=entry; | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
94 |
14280 | 95 /* Look to see if the next shorter marker points to the node |
96 above. if so, update it and repeat. */ | |
97 { | |
98 for(j=length;j>0;j--){ | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
99 |
14280 | 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 */ | |
108 } | |
109 marker[j]++; | |
110 } | |
111 } | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
112 |
14280 | 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++; | |
124 } | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
125 |
14280 | 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; | |
133 } | |
134 | |
135 if(sparsecount){ | |
136 if(l[i]) | |
137 r[count++]=temp; | |
138 }else | |
139 r[count++]=temp; | |
140 } | |
141 | |
142 return(r); | |
143 } | |
144 | |
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); | |
152 | |
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; | |
160 } | |
161 if(acc<=b->entries && acc1>b->entries){ | |
162 return(vals); | |
163 }else{ | |
164 if(acc>b->entries){ | |
165 vals--; | |
166 }else{ | |
167 vals++; | |
168 } | |
169 } | |
170 } | |
171 } | |
172 | |
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 */ | |
176 | |
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 */ | |
181 | |
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)); | |
192 | |
193 *maxpoint=minpoint; | |
194 | |
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; | |
19254
5930a8dbebb1
Restore a local diff lost during license fix at r19256
rtogni
parents:
19251
diff
changeset
|
214 ogg_int32_t point; |
14280 | 215 int val=VFLOAT_MULTI(delta,delpoint, |
216 abs(b->quantlist[index]),&point); | |
217 | |
218 val=VFLOAT_ADD(mindel,minpoint,val,point,&point); | |
219 val=VFLOAT_ADD(last,lastpoint,val,point,&point); | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
220 |
14280 | 221 if(b->q_sequencep){ |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
222 last=val; |
14280 | 223 lastpoint=point; |
224 } | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
225 |
14280 | 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; | |
232 } | |
233 if(*maxpoint<point)*maxpoint=point; | |
234 indexdiv*=quantvals; | |
235 } | |
236 count++; | |
237 } | |
238 | |
239 } | |
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; | |
246 | |
247 for(k=0;k<b->dim;k++){ | |
19254
5930a8dbebb1
Restore a local diff lost during license fix at r19256
rtogni
parents:
19251
diff
changeset
|
248 ogg_int32_t point; |
14280 | 249 int val=VFLOAT_MULTI(delta,delpoint, |
250 abs(b->quantlist[j*b->dim+k]),&point); | |
251 | |
252 val=VFLOAT_ADD(mindel,minpoint,val,point,&point); | |
253 val=VFLOAT_ADD(last,lastpoint,val,point,&point); | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
254 |
14280 | 255 if(b->q_sequencep){ |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
256 last=val; |
14280 | 257 lastpoint=point; |
258 } | |
259 | |
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; | |
266 } | |
267 if(*maxpoint<point)*maxpoint=point; | |
268 } | |
269 count++; | |
270 } | |
271 } | |
272 break; | |
273 } | |
274 | |
275 for(j=0;j<n*b->dim;j++) | |
276 if(rp[j]<*maxpoint) | |
277 r[j]>>=*maxpoint-rp[j]; | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
278 |
14280 | 279 _ogg_free(rp); |
280 return(r); | |
281 } | |
282 return(NULL); | |
283 } | |
284 | |
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)); | |
289 | |
290 } | |
291 | |
292 void vorbis_staticbook_destroy(static_codebook *b){ | |
293 vorbis_staticbook_clear(b); | |
294 _ogg_free(b); | |
295 } | |
296 | |
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); | |
302 | |
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); | |
306 | |
307 memset(b,0,sizeof(*b)); | |
308 } | |
309 | |
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); | |
316 } | |
317 | |
318 static int sort32a(const void *a,const void *b){ | |
19251
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
16266
diff
changeset
|
319 return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)- |
cd6b211be811
Replace tremor files that had old headers saying "ALL REDISTRIBUTION
uau
parents:
16266
diff
changeset
|
320 (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b); |
14280 | 321 } |
322 | |
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)); | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
328 |
14280 | 329 /* count actually used entries */ |
330 for(i=0;i<s->entries;i++) | |
331 if(s->lengthlist[i]>0) | |
332 n++; | |
333 | |
334 c->entries=s->entries; | |
335 c->used_entries=n; | |
336 c->dim=s->dim; | |
337 | |
338 c->q_min=s->q_min; | |
339 c->q_delta=s->q_delta; | |
340 | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
341 /* two different remappings go on here. |
14280 | 342 |
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. | |
347 | |
348 Second, we reorder all vectors, including the entry index above, | |
349 by sorted bitreversed codeword to allow treeless decode. */ | |
350 | |
351 { | |
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); | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
355 |
14280 | 356 if(codes==NULL)goto err_out; |
357 | |
358 for(i=0;i<n;i++){ | |
359 codes[i]=bitreverse(codes[i]); | |
360 codep[i]=codes+i; | |
361 } | |
362 | |
363 qsort(codep,n,sizeof(*codep),sort32a); | |
364 | |
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; | |
371 } | |
372 | |
373 for(i=0;i<n;i++) | |
374 c->codelist[sortindex[i]]=codes[i]; | |
375 _ogg_free(codes); | |
376 } | |
377 | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
378 |
14280 | 379 c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint); |
380 c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index)); | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
381 |
14280 | 382 for(n=0,i=0;i<s->entries;i++) |
383 if(s->lengthlist[i]>0) | |
384 c->dec_index[sortindex[n++]]=i; | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
385 |
14280 | 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]; | |
390 | |
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; | |
394 | |
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; | |
398 | |
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; | |
406 } | |
407 } | |
408 | |
409 /* now fill in 'unused' entries in the firsttable with hi/lo search | |
410 hints for the non-direct-hits */ | |
411 { | |
412 ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen); | |
413 long lo=0,hi=0; | |
414 | |
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++; | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
420 |
14280 | 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. */ | |
424 { | |
425 unsigned long loval=lo; | |
426 unsigned long hival=n-hi; | |
427 | |
428 if(loval>0x7fff)loval=0x7fff; | |
429 if(hival>0x7fff)hival=0x7fff; | |
430 c->dec_firsttable[bitreverse(word)]= | |
431 0x80000000UL | (loval<<15) | hival; | |
432 } | |
433 } | |
434 } | |
435 } | |
29264
e83eef58b30a
Remove all kind of trailing whitespaces from all MPlayer's files.
bircoph
parents:
28240
diff
changeset
|
436 |
14280 | 437 |
438 return(0); | |
439 err_out: | |
440 vorbis_book_clear(c); | |
441 return(-1); | |
442 } | |
443 |