vo_corevideo.m: remote useless parentheses and casts
[mplayer/glamo.git] / tremor / codebook.c
blob655746c68ac20c70e8584cdbc88a8930b7912827
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 codebook pack/unpack/code/decode operations
16 ********************************************************************/
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include "ogg.h"
22 #include "ivorbiscodec.h"
23 #include "codebook.h"
24 #include "misc.h"
25 #include "os.h"
27 /* unpacks a codebook from the packet buffer into the codebook struct,
28 readies the codebook auxiliary structures for decode *************/
29 int vorbis_staticbook_unpack(oggpack_buffer *opb,static_codebook *s){
30 long i,j;
31 memset(s,0,sizeof(*s));
33 /* make sure alignment is correct */
34 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
36 /* first the basic parameters */
37 s->dim=oggpack_read(opb,16);
38 s->entries=oggpack_read(opb,24);
39 if(s->entries==-1)goto _eofout;
41 /* codeword ordering.... length ordered or unordered? */
42 switch((int)oggpack_read(opb,1)){
43 case 0:
44 /* unordered */
45 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
47 /* allocated but unused entries? */
48 if(oggpack_read(opb,1)){
49 /* yes, unused entries */
51 for(i=0;i<s->entries;i++){
52 if(oggpack_read(opb,1)){
53 long num=oggpack_read(opb,5);
54 if(num==-1)goto _eofout;
55 s->lengthlist[i]=num+1;
56 }else
57 s->lengthlist[i]=0;
59 }else{
60 /* all entries used; no tagging */
61 for(i=0;i<s->entries;i++){
62 long num=oggpack_read(opb,5);
63 if(num==-1)goto _eofout;
64 s->lengthlist[i]=num+1;
68 break;
69 case 1:
70 /* ordered */
72 long length=oggpack_read(opb,5)+1;
73 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
75 for(i=0;i<s->entries;){
76 long num=oggpack_read(opb,_ilog(s->entries-i));
77 if(num==-1)goto _eofout;
78 for(j=0;j<num && i<s->entries;j++,i++)
79 s->lengthlist[i]=length;
80 length++;
83 break;
84 default:
85 /* EOF */
86 return(-1);
89 /* Do we have a mapping to unpack? */
90 switch((s->maptype=oggpack_read(opb,4))){
91 case 0:
92 /* no mapping */
93 break;
94 case 1: case 2:
95 /* implicitly populated value mapping */
96 /* explicitly populated value mapping */
98 s->q_min=oggpack_read(opb,32);
99 s->q_delta=oggpack_read(opb,32);
100 s->q_quant=oggpack_read(opb,4)+1;
101 s->q_sequencep=oggpack_read(opb,1);
104 int quantvals=0;
105 switch(s->maptype){
106 case 1:
107 quantvals=_book_maptype1_quantvals(s);
108 break;
109 case 2:
110 quantvals=s->entries*s->dim;
111 break;
114 /* quantized values */
115 s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);
116 for(i=0;i<quantvals;i++)
117 s->quantlist[i]=oggpack_read(opb,s->q_quant);
119 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
121 break;
122 default:
123 goto _errout;
126 /* all set */
127 return(0);
129 _errout:
130 _eofout:
131 vorbis_staticbook_clear(s);
132 return(-1);
135 /* the 'eliminate the decode tree' optimization actually requires the
136 codewords to be MSb first, not LSb. This is an annoying inelegancy
137 (and one of the first places where carefully thought out design
138 turned out to be wrong; Vorbis II and future Ogg codecs should go
139 to an MSb bitpacker), but not actually the huge hit it appears to
140 be. The first-stage decode table catches most words so that
141 bitreverse is not in the main execution path. */
143 static ogg_uint32_t bitreverse(ogg_uint32_t x){
144 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
145 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
146 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
147 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
148 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
151 static inline long decode_packed_entry_number(codebook *book,
152 oggpack_buffer *b){
153 int read=book->dec_maxlength;
154 long lo,hi;
155 long lok = oggpack_look(b,book->dec_firsttablen);
157 if (lok >= 0) {
158 long entry = book->dec_firsttable[lok];
159 if(entry&0x80000000UL){
160 lo=(entry>>15)&0x7fff;
161 hi=book->used_entries-(entry&0x7fff);
162 }else{
163 oggpack_adv(b, book->dec_codelengths[entry-1]);
164 return(entry-1);
166 }else{
167 lo=0;
168 hi=book->used_entries;
171 lok = oggpack_look(b, read);
173 while(lok<0 && read>1)
174 lok = oggpack_look(b, --read);
175 if(lok<0)return -1;
177 /* bisect search for the codeword in the ordered list */
179 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
181 while(hi-lo>1){
182 long p=(hi-lo)>>1;
183 long test=book->codelist[lo+p]>testword;
184 lo+=p&(test-1);
185 hi-=p&(-test);
188 if(book->dec_codelengths[lo]<=read){
189 oggpack_adv(b, book->dec_codelengths[lo]);
190 return(lo);
194 oggpack_adv(b, read);
195 return(-1);
198 /* Decode side is specced and easier, because we don't need to find
199 matches using different criteria; we simply read and map. There are
200 two things we need to do 'depending':
202 We may need to support interleave. We don't really, but it's
203 convenient to do it here rather than rebuild the vector later.
205 Cascades may be additive or multiplicitive; this is not inherent in
206 the codebook, but set in the code using the codebook. Like
207 interleaving, it's easiest to do it here.
208 addmul==0 -> declarative (set the value)
209 addmul==1 -> additive
210 addmul==2 -> multiplicitive */
212 /* returns the [original, not compacted] entry number or -1 on eof *********/
213 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
214 long packed_entry=decode_packed_entry_number(book,b);
215 if(packed_entry>=0)
216 return(book->dec_index[packed_entry]);
218 /* if there's no dec_index, the codebook unpacking isn't collapsed */
219 return(packed_entry);
222 /* returns 0 on OK or -1 on eof *************************************/
223 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
224 oggpack_buffer *b,int n,int point){
225 int step=n/book->dim;
226 long *entry = (long *)alloca(sizeof(*entry)*step);
227 ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
228 int i,j,o;
229 int shift=point-book->binarypoint;
231 if(shift>=0){
232 for (i = 0; i < step; i++) {
233 entry[i]=decode_packed_entry_number(book,b);
234 if(entry[i]==-1)return(-1);
235 t[i] = book->valuelist+entry[i]*book->dim;
237 for(i=0,o=0;i<book->dim;i++,o+=step)
238 for (j=0;j<step;j++)
239 a[o+j]+=t[j][i]>>shift;
240 }else{
241 for (i = 0; i < step; i++) {
242 entry[i]=decode_packed_entry_number(book,b);
243 if(entry[i]==-1)return(-1);
244 t[i] = book->valuelist+entry[i]*book->dim;
246 for(i=0,o=0;i<book->dim;i++,o+=step)
247 for (j=0;j<step;j++)
248 a[o+j]+=t[j][i]<<-shift;
250 return(0);
253 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
254 oggpack_buffer *b,int n,int point){
255 int i,j,entry;
256 ogg_int32_t *t;
257 int shift=point-book->binarypoint;
259 if(shift>=0){
260 for(i=0;i<n;){
261 entry = decode_packed_entry_number(book,b);
262 if(entry==-1)return(-1);
263 t = book->valuelist+entry*book->dim;
264 for (j=0;j<book->dim;)
265 a[i++]+=t[j++]>>shift;
267 }else{
268 for(i=0;i<n;){
269 entry = decode_packed_entry_number(book,b);
270 if(entry==-1)return(-1);
271 t = book->valuelist+entry*book->dim;
272 for (j=0;j<book->dim;)
273 a[i++]+=t[j++]<<-shift;
276 return(0);
279 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
280 oggpack_buffer *b,int n,int point){
281 int i,j,entry;
282 ogg_int32_t *t;
283 int shift=point-book->binarypoint;
285 if(shift>=0){
287 for(i=0;i<n;){
288 entry = decode_packed_entry_number(book,b);
289 if(entry==-1)return(-1);
290 t = book->valuelist+entry*book->dim;
291 for (j=0;j<book->dim;){
292 a[i++]=t[j++]>>shift;
295 }else{
297 for(i=0;i<n;){
298 entry = decode_packed_entry_number(book,b);
299 if(entry==-1)return(-1);
300 t = book->valuelist+entry*book->dim;
301 for (j=0;j<book->dim;){
302 a[i++]=t[j++]<<-shift;
306 return(0);
309 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
310 long offset,int ch,
311 oggpack_buffer *b,int n,int point){
312 long i,j,entry;
313 int chptr=0;
314 int shift=point-book->binarypoint;
316 if(shift>=0){
318 for(i=offset;i<offset+n;){
319 entry = decode_packed_entry_number(book,b);
320 if(entry==-1)return(-1);
322 const ogg_int32_t *t = book->valuelist+entry*book->dim;
323 for (j=0;j<book->dim;j++){
324 a[chptr++][i]+=t[j]>>shift;
325 if(chptr==ch){
326 chptr=0;
327 i++;
332 }else{
334 for(i=offset;i<offset+n;){
335 entry = decode_packed_entry_number(book,b);
336 if(entry==-1)return(-1);
338 const ogg_int32_t *t = book->valuelist+entry*book->dim;
339 for (j=0;j<book->dim;j++){
340 a[chptr++][i]+=t[j]<<-shift;
341 if(chptr==ch){
342 chptr=0;
343 i++;
349 return(0);