media/libtremor/lib/tremor_codebook.c@b8a032363ba2
media/libtremor/lib/tremor_codebook.c
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
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/ogg.h>
22 #include "ivorbiscodec.h"
23 #include "codebook.h"
24 #include "misc.h"
26 /* unpacks a codebook from the packet buffer into the codebook struct,
27 readies the codebook auxiliary structures for decode *************/
28 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
29 long i,j;
30 static_codebook *s=_ogg_calloc(1,sizeof(*s));
32 /* make sure alignment is correct */
33 if(oggpack_read(opb,24)!=0x564342)goto _eofout;
35 /* first the basic parameters */
36 s->dim=oggpack_read(opb,16);
37 s->entries=oggpack_read(opb,24);
38 if(s->entries==-1)goto _eofout;
40 if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
42 /* codeword ordering.... length ordered or unordered? */
43 switch((int)oggpack_read(opb,1)){
44 case 0:{
45 long unused;
46 /* allocated but unused entries? */
47 unused=oggpack_read(opb,1);
48 if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
49 goto _eofout;
50 /* unordered */
51 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
53 /* allocated but unused entries? */
54 if(unused){
55 /* yes, unused entries */
57 for(i=0;i<s->entries;i++){
58 if(oggpack_read(opb,1)){
59 long num=oggpack_read(opb,5);
60 if(num==-1)goto _eofout;
61 s->lengthlist[i]=num+1;
62 }else
63 s->lengthlist[i]=0;
64 }
65 }else{
66 /* all entries used; no tagging */
67 for(i=0;i<s->entries;i++){
68 long num=oggpack_read(opb,5);
69 if(num==-1)goto _eofout;
70 s->lengthlist[i]=num+1;
71 }
72 }
74 break;
75 }
76 case 1:
77 /* ordered */
78 {
79 long length=oggpack_read(opb,5)+1;
80 if(length==0)goto _eofout;
81 s->lengthlist=(long *)_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
83 for(i=0;i<s->entries;){
84 long num=oggpack_read(opb,_ilog(s->entries-i));
85 if(num==-1)goto _eofout;
86 if(length>32 || num>s->entries-i ||
87 (num>0 && (num-1)>>(length>>1)>>((length+1)>>1))>0){
88 goto _errout;
89 }
90 for(j=0;j<num;j++,i++)
91 s->lengthlist[i]=length;
92 length++;
93 }
94 }
95 break;
96 default:
97 /* EOF */
98 goto _eofout;
99 }
101 /* Do we have a mapping to unpack? */
102 switch((s->maptype=oggpack_read(opb,4))){
103 case 0:
104 /* no mapping */
105 break;
106 case 1: case 2:
107 /* implicitly populated value mapping */
108 /* explicitly populated value mapping */
110 s->q_min=oggpack_read(opb,32);
111 s->q_delta=oggpack_read(opb,32);
112 s->q_quant=oggpack_read(opb,4)+1;
113 s->q_sequencep=oggpack_read(opb,1);
114 if(s->q_sequencep==-1)goto _eofout;
116 {
117 int quantvals=0;
118 switch(s->maptype){
119 case 1:
120 quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
121 break;
122 case 2:
123 quantvals=s->entries*s->dim;
124 break;
125 }
127 /* quantized values */
128 if((quantvals*s->q_quant+7)>>3>opb->storage-oggpack_bytes(opb))
129 goto _eofout;
130 s->quantlist=(long *)_ogg_malloc(sizeof(*s->quantlist)*quantvals);
131 for(i=0;i<quantvals;i++)
132 s->quantlist[i]=oggpack_read(opb,s->q_quant);
134 if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
135 }
136 break;
137 default:
138 goto _errout;
139 }
141 /* all set */
142 return(s);
144 _errout:
145 _eofout:
146 vorbis_staticbook_destroy(s);
147 return(NULL);
148 }
150 /* the 'eliminate the decode tree' optimization actually requires the
151 codewords to be MSb first, not LSb. This is an annoying inelegancy
152 (and one of the first places where carefully thought out design
153 turned out to be wrong; Vorbis II and future Ogg codecs should go
154 to an MSb bitpacker), but not actually the huge hit it appears to
155 be. The first-stage decode table catches most words so that
156 bitreverse is not in the main execution path. */
158 static ogg_uint32_t bitreverse(ogg_uint32_t x){
159 x= ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
160 x= ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
161 x= ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
162 x= ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
163 return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
164 }
166 STIN long decode_packed_entry_number(codebook *book,
167 oggpack_buffer *b){
168 int read=book->dec_maxlength;
169 long lo,hi;
170 long lok = oggpack_look(b,book->dec_firsttablen);
172 if (lok >= 0) {
173 long entry = book->dec_firsttable[lok];
174 if(entry&0x80000000UL){
175 lo=(entry>>15)&0x7fff;
176 hi=book->used_entries-(entry&0x7fff);
177 }else{
178 oggpack_adv(b, book->dec_codelengths[entry-1]);
179 return(entry-1);
180 }
181 }else{
182 lo=0;
183 hi=book->used_entries;
184 }
186 lok = oggpack_look(b, read);
188 while(lok<0 && read>1)
189 lok = oggpack_look(b, --read);
191 if(lok<0){
192 oggpack_adv(b,1); /* force eop */
193 return -1;
194 }
196 /* bisect search for the codeword in the ordered list */
197 {
198 ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
200 while(hi-lo>1){
201 long p=(hi-lo)>>1;
202 long test=book->codelist[lo+p]>testword;
203 lo+=p&(test-1);
204 hi-=p&(-test);
205 }
207 if(book->dec_codelengths[lo]<=read){
208 oggpack_adv(b, book->dec_codelengths[lo]);
209 return(lo);
210 }
211 }
213 oggpack_adv(b, read+1);
214 return(-1);
215 }
217 /* Decode side is specced and easier, because we don't need to find
218 matches using different criteria; we simply read and map. There are
219 two things we need to do 'depending':
221 We may need to support interleave. We don't really, but it's
222 convenient to do it here rather than rebuild the vector later.
224 Cascades may be additive or multiplicitive; this is not inherent in
225 the codebook, but set in the code using the codebook. Like
226 interleaving, it's easiest to do it here.
227 addmul==0 -> declarative (set the value)
228 addmul==1 -> additive
229 addmul==2 -> multiplicitive */
231 /* returns the [original, not compacted] entry number or -1 on eof *********/
232 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
233 if(book->used_entries>0){
234 long packed_entry=decode_packed_entry_number(book,b);
235 if(packed_entry>=0)
236 return(book->dec_index[packed_entry]);
237 }
239 /* if there's no dec_index, the codebook unpacking isn't collapsed */
240 return(-1);
241 }
243 /* returns 0 on OK or -1 on eof *************************************/
244 /* decode vector / dim granularity gaurding is done in the upper layer */
245 long vorbis_book_decodevs_add(codebook *book,ogg_int32_t *a,
246 oggpack_buffer *b,int n,int point){
247 if(book->used_entries>0){
248 int step=n/book->dim;
249 long *entry = (long *)alloca(sizeof(*entry)*step);
250 ogg_int32_t **t = (ogg_int32_t **)alloca(sizeof(*t)*step);
251 int i,j,o;
252 int shift=point-book->binarypoint;
254 if(shift>=0){
255 for (i = 0; i < step; i++) {
256 entry[i]=decode_packed_entry_number(book,b);
257 if(entry[i]==-1)return(-1);
258 t[i] = book->valuelist+entry[i]*book->dim;
259 }
260 for(i=0,o=0;i<book->dim;i++,o+=step)
261 for (j=0;j<step;j++)
262 a[o+j]+=t[j][i]>>shift;
263 }else{
264 for (i = 0; i < step; i++) {
265 entry[i]=decode_packed_entry_number(book,b);
266 if(entry[i]==-1)return(-1);
267 t[i] = book->valuelist+entry[i]*book->dim;
268 }
269 for(i=0,o=0;i<book->dim;i++,o+=step)
270 for (j=0;j<step;j++)
271 a[o+j]+=t[j][i]<<-shift;
272 }
273 }
274 return(0);
275 }
277 /* decode vector / dim granularity gaurding is done in the upper layer */
278 long vorbis_book_decodev_add(codebook *book,ogg_int32_t *a,
279 oggpack_buffer *b,int n,int point){
280 if(book->used_entries>0){
281 int i,j,entry;
282 ogg_int32_t *t;
283 int shift=point-book->binarypoint;
285 if(shift>=0){
286 for(i=0;i<n;){
287 entry = decode_packed_entry_number(book,b);
288 if(entry==-1)return(-1);
289 t = book->valuelist+entry*book->dim;
290 for (j=0;j<book->dim;)
291 a[i++]+=t[j++]>>shift;
292 }
293 }else{
294 for(i=0;i<n;){
295 entry = decode_packed_entry_number(book,b);
296 if(entry==-1)return(-1);
297 t = book->valuelist+entry*book->dim;
298 for (j=0;j<book->dim;)
299 a[i++]+=t[j++]<<-shift;
300 }
301 }
302 }
303 return(0);
304 }
306 /* unlike the others, we guard against n not being an integer number
307 of <dim> internally rather than in the upper layer (called only by
308 floor0) */
309 long vorbis_book_decodev_set(codebook *book,ogg_int32_t *a,
310 oggpack_buffer *b,int n,int point){
311 if(book->used_entries>0){
312 int i,j,entry;
313 ogg_int32_t *t;
314 int shift=point-book->binarypoint;
316 if(shift>=0){
318 for(i=0;i<n;){
319 entry = decode_packed_entry_number(book,b);
320 if(entry==-1)return(-1);
321 t = book->valuelist+entry*book->dim;
322 for (j=0;i<n && j<book->dim;){
323 a[i++]=t[j++]>>shift;
324 }
325 }
326 }else{
328 for(i=0;i<n;){
329 entry = decode_packed_entry_number(book,b);
330 if(entry==-1)return(-1);
331 t = book->valuelist+entry*book->dim;
332 for (j=0;i<n && j<book->dim;){
333 a[i++]=t[j++]<<-shift;
334 }
335 }
336 }
337 }else{
339 int i,j;
340 for(i=0;i<n;){
341 a[i++]=0;
342 }
343 }
344 return(0);
345 }
347 /* decode vector / dim granularity gaurding is done in the upper layer */
348 long vorbis_book_decodevv_add(codebook *book,ogg_int32_t **a,\
349 long offset,int ch,
350 oggpack_buffer *b,int n,int point){
351 if(book->used_entries>0){
352 long i,j,entry;
353 int chptr=0;
354 int shift=point-book->binarypoint;
356 if(shift>=0){
358 for(i=offset;i<offset+n;){
359 entry = decode_packed_entry_number(book,b);
360 if(entry==-1)return(-1);
361 {
362 const ogg_int32_t *t = book->valuelist+entry*book->dim;
363 for (j=0;j<book->dim;j++){
364 a[chptr++][i]+=t[j]>>shift;
365 if(chptr==ch){
366 chptr=0;
367 i++;
368 }
369 }
370 }
371 }
372 }else{
374 for(i=offset;i<offset+n;){
375 entry = decode_packed_entry_number(book,b);
376 if(entry==-1)return(-1);
377 {
378 const ogg_int32_t *t = book->valuelist+entry*book->dim;
379 for (j=0;j<book->dim;j++){
380 a[chptr++][i]+=t[j]<<-shift;
381 if(chptr==ch){
382 chptr=0;
383 i++;
384 }
385 }
386 }
387 }
388 }
389 }
390 return(0);
391 }
