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: floor backend 1 implementation
15
16 ********************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include <ogg/ogg.h>
22 #include "ivorbiscodec.h"
23 #include "codec_internal.h"
24 #include "registry.h"
25 #include "codebook.h"
26 #include "misc.h"
27 #include "block.h"
28
29 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
30
31 typedef struct {
32 int forward_index[VIF_POSIT+2];
33
34 int hineighbor[VIF_POSIT];
35 int loneighbor[VIF_POSIT];
36 int posts;
37
38 int n;
39 int quant_q;
40 vorbis_info_floor1 *vi;
41
42 } vorbis_look_floor1;
43
44 /***********************************************/
45
floor1_free_info(vorbis_info_floor * i)46 static void floor1_free_info(vorbis_info_floor *i){
47 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
48 if(info){
49 memset(info,0,sizeof(*info));
50 _ogg_free(info);
51 }
52 }
53
floor1_free_look(vorbis_look_floor * i)54 static void floor1_free_look(vorbis_look_floor *i){
55 vorbis_look_floor1 *look=(vorbis_look_floor1 *)i;
56 if(look){
57 memset(look,0,sizeof(*look));
58 _ogg_free(look);
59 }
60 }
61
ilog(unsigned int v)62 static int ilog(unsigned int v){
63 int ret=0;
64 while(v){
65 ret++;
66 v>>=1;
67 }
68 return(ret);
69 }
70
icomp(const void * a,const void * b)71 static int icomp(const void *a,const void *b){
72 return(**(int **)a-**(int **)b);
73 }
74
floor1_unpack(vorbis_info * vi,oggpack_buffer * opb)75 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){
76 codec_setup_info *ci=(codec_setup_info *)vi->codec_setup;
77 int j,k,count=0,maxclass=-1,rangebits;
78
79 vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
80 /* read partitions */
81 info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
82 for(j=0;j<info->partitions;j++){
83 info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
84 if(info->partitionclass[j]<0)goto err_out;
85 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
86 }
87
88 /* read partition classes */
89 for(j=0;j<maxclass+1;j++){
90 info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */
91 info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */
92 if(info->class_subs[j]<0)
93 goto err_out;
94 if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8);
95 if(info->class_book[j]<0 || info->class_book[j]>=ci->books)
96 goto err_out;
97 for(k=0;k<(1<<info->class_subs[j]);k++){
98 info->class_subbook[j][k]=oggpack_read(opb,8)-1;
99 if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books)
100 goto err_out;
101 }
102 }
103
104 /* read the post list */
105 info->mult=oggpack_read(opb,2)+1; /* only 1,2,3,4 legal now */
106 rangebits=oggpack_read(opb,4);
107 if(rangebits<0)goto err_out;
108
109 for(j=0,k=0;j<info->partitions;j++){
110 count+=info->class_dim[info->partitionclass[j]];
111 if(count>VIF_POSIT)goto err_out;
112 for(;k<count;k++){
113 int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
114 if(t<0 || t>=(1<<rangebits))
115 goto err_out;
116 }
117 }
118 info->postlist[0]=0;
119 info->postlist[1]=1<<rangebits;
120
121 /* don't allow repeated values in post list as they'd result in
122 zero-length segments */
123 {
124 int *sortpointer[VIF_POSIT+2];
125 for(j=0;j<count+2;j++)sortpointer[j]=info->postlist+j;
126 qsort(sortpointer,count+2,sizeof(*sortpointer),icomp);
127
128 for(j=1;j<count+2;j++)
129 if(*sortpointer[j-1]==*sortpointer[j])goto err_out;
130 }
131
132 return(info);
133
134 err_out:
135 floor1_free_info(info);
136 return(NULL);
137 }
138
floor1_look(vorbis_dsp_state * vd,vorbis_info_mode * mi,vorbis_info_floor * in)139 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,vorbis_info_mode *mi,
140 vorbis_info_floor *in){
141
142 int *sortpointer[VIF_POSIT+2];
143 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
144 vorbis_look_floor1 *look=(vorbis_look_floor1 *)_ogg_calloc(1,sizeof(*look));
145 int i,j,n=0;
146
147 look->vi=info;
148 look->n=info->postlist[1];
149
150 /* we drop each position value in-between already decoded values,
151 and use linear interpolation to predict each new value past the
152 edges. The positions are read in the order of the position
153 list... we precompute the bounding positions in the lookup. Of
154 course, the neighbors can change (if a position is declined), but
155 this is an initial mapping */
156
157 for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
158 n+=2;
159 look->posts=n;
160
161 /* also store a sorted position index */
162 for(i=0;i<n;i++)sortpointer[i]=info->postlist+i;
163 qsort(sortpointer,n,sizeof(*sortpointer),icomp);
164
165 /* points from sort order back to range number */
166 for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist;
167
168 /* quantize values to multiplier spec */
169 switch(info->mult){
170 case 1: /* 1024 -> 256 */
171 look->quant_q=256;
172 break;
173 case 2: /* 1024 -> 128 */
174 look->quant_q=128;
175 break;
176 case 3: /* 1024 -> 86 */
177 look->quant_q=86;
178 break;
179 case 4: /* 1024 -> 64 */
180 look->quant_q=64;
181 break;
182 }
183
184 /* discover our neighbors for decode where we don't use fit flags
185 (that would push the neighbors outward) */
186 for(i=0;i<n-2;i++){
187 int lo=0;
188 int hi=1;
189 int lx=0;
190 int hx=look->n;
191 int currentx=info->postlist[i+2];
192 for(j=0;j<i+2;j++){
193 int x=info->postlist[j];
194 if(x>lx && x<currentx){
195 lo=j;
196 lx=x;
197 }
198 if(x<hx && x>currentx){
199 hi=j;
200 hx=x;
201 }
202 }
203 look->loneighbor[i]=lo;
204 look->hineighbor[i]=hi;
205 }
206
207 return(look);
208 }
209
render_point(int x0,int x1,int y0,int y1,int x)210 static int render_point(int x0,int x1,int y0,int y1,int x){
211 y0&=0x7fff; /* mask off flag */
212 y1&=0x7fff;
213
214 {
215 int dy=y1-y0;
216 int adx=x1-x0;
217 int ady=abs(dy);
218 int err=ady*(x-x0);
219
220 int off=err/adx;
221 if(dy<0)return(y0-off);
222 return(y0+off);
223 }
224 }
225
226 #ifdef _LOW_ACCURACY_
227 # define XdB(n) ((((n)>>8)+1)>>1)
228 #else
229 # define XdB(n) (n)
230 #endif
231
232 static const ogg_int32_t FLOOR_fromdB_LOOKUP[256]={
233 XdB(0x000000e5), XdB(0x000000f4), XdB(0x00000103), XdB(0x00000114),
234 XdB(0x00000126), XdB(0x00000139), XdB(0x0000014e), XdB(0x00000163),
235 XdB(0x0000017a), XdB(0x00000193), XdB(0x000001ad), XdB(0x000001c9),
236 XdB(0x000001e7), XdB(0x00000206), XdB(0x00000228), XdB(0x0000024c),
237 XdB(0x00000272), XdB(0x0000029b), XdB(0x000002c6), XdB(0x000002f4),
238 XdB(0x00000326), XdB(0x0000035a), XdB(0x00000392), XdB(0x000003cd),
239 XdB(0x0000040c), XdB(0x00000450), XdB(0x00000497), XdB(0x000004e4),
240 XdB(0x00000535), XdB(0x0000058c), XdB(0x000005e8), XdB(0x0000064a),
241 XdB(0x000006b3), XdB(0x00000722), XdB(0x00000799), XdB(0x00000818),
242 XdB(0x0000089e), XdB(0x0000092e), XdB(0x000009c6), XdB(0x00000a69),
243 XdB(0x00000b16), XdB(0x00000bcf), XdB(0x00000c93), XdB(0x00000d64),
244 XdB(0x00000e43), XdB(0x00000f30), XdB(0x0000102d), XdB(0x0000113a),
245 XdB(0x00001258), XdB(0x0000138a), XdB(0x000014cf), XdB(0x00001629),
246 XdB(0x0000179a), XdB(0x00001922), XdB(0x00001ac4), XdB(0x00001c82),
247 XdB(0x00001e5c), XdB(0x00002055), XdB(0x0000226f), XdB(0x000024ac),
248 XdB(0x0000270e), XdB(0x00002997), XdB(0x00002c4b), XdB(0x00002f2c),
249 XdB(0x0000323d), XdB(0x00003581), XdB(0x000038fb), XdB(0x00003caf),
250 XdB(0x000040a0), XdB(0x000044d3), XdB(0x0000494c), XdB(0x00004e10),
251 XdB(0x00005323), XdB(0x0000588a), XdB(0x00005e4b), XdB(0x0000646b),
252 XdB(0x00006af2), XdB(0x000071e5), XdB(0x0000794c), XdB(0x0000812e),
253 XdB(0x00008993), XdB(0x00009283), XdB(0x00009c09), XdB(0x0000a62d),
254 XdB(0x0000b0f9), XdB(0x0000bc79), XdB(0x0000c8b9), XdB(0x0000d5c4),
255 XdB(0x0000e3a9), XdB(0x0000f274), XdB(0x00010235), XdB(0x000112fd),
256 XdB(0x000124dc), XdB(0x000137e4), XdB(0x00014c29), XdB(0x000161bf),
257 XdB(0x000178bc), XdB(0x00019137), XdB(0x0001ab4a), XdB(0x0001c70e),
258 XdB(0x0001e4a1), XdB(0x0002041f), XdB(0x000225aa), XdB(0x00024962),
259 XdB(0x00026f6d), XdB(0x000297f0), XdB(0x0002c316), XdB(0x0002f109),
260 XdB(0x000321f9), XdB(0x00035616), XdB(0x00038d97), XdB(0x0003c8b4),
261 XdB(0x000407a7), XdB(0x00044ab2), XdB(0x00049218), XdB(0x0004de23),
262 XdB(0x00052f1e), XdB(0x0005855c), XdB(0x0005e135), XdB(0x00064306),
263 XdB(0x0006ab33), XdB(0x00071a24), XdB(0x0007904b), XdB(0x00080e20),
264 XdB(0x00089422), XdB(0x000922da), XdB(0x0009bad8), XdB(0x000a5cb6),
265 XdB(0x000b091a), XdB(0x000bc0b1), XdB(0x000c8436), XdB(0x000d5471),
266 XdB(0x000e3233), XdB(0x000f1e5f), XdB(0x001019e4), XdB(0x001125c1),
267 XdB(0x00124306), XdB(0x001372d5), XdB(0x0014b663), XdB(0x00160ef7),
268 XdB(0x00177df0), XdB(0x001904c1), XdB(0x001aa4f9), XdB(0x001c603d),
269 XdB(0x001e384f), XdB(0x00202f0f), XdB(0x0022467a), XdB(0x002480b1),
270 XdB(0x0026dff7), XdB(0x002966b3), XdB(0x002c1776), XdB(0x002ef4fc),
271 XdB(0x0032022d), XdB(0x00354222), XdB(0x0038b828), XdB(0x003c67c2),
272 XdB(0x004054ae), XdB(0x004482e8), XdB(0x0048f6af), XdB(0x004db488),
273 XdB(0x0052c142), XdB(0x005821ff), XdB(0x005ddc33), XdB(0x0063f5b0),
274 XdB(0x006a74a7), XdB(0x00715faf), XdB(0x0078bdce), XdB(0x0080967f),
275 XdB(0x0088f1ba), XdB(0x0091d7f9), XdB(0x009b5247), XdB(0x00a56a41),
276 XdB(0x00b02a27), XdB(0x00bb9ce2), XdB(0x00c7ce12), XdB(0x00d4ca17),
277 XdB(0x00e29e20), XdB(0x00f15835), XdB(0x0101074b), XdB(0x0111bb4e),
278 XdB(0x01238531), XdB(0x01367704), XdB(0x014aa402), XdB(0x016020a7),
279 XdB(0x017702c3), XdB(0x018f6190), XdB(0x01a955cb), XdB(0x01c4f9cf),
280 XdB(0x01e269a8), XdB(0x0201c33b), XdB(0x0223265a), XdB(0x0246b4ea),
281 XdB(0x026c9302), XdB(0x0294e716), XdB(0x02bfda13), XdB(0x02ed9793),
282 XdB(0x031e4e09), XdB(0x03522ee4), XdB(0x03896ed0), XdB(0x03c445e2),
283 XdB(0x0402efd6), XdB(0x0445ac4b), XdB(0x048cbefc), XdB(0x04d87013),
284 XdB(0x05290c67), XdB(0x057ee5ca), XdB(0x05da5364), XdB(0x063bb204),
285 XdB(0x06a36485), XdB(0x0711d42b), XdB(0x0787710e), XdB(0x0804b299),
286 XdB(0x088a17ef), XdB(0x0918287e), XdB(0x09af747c), XdB(0x0a50957e),
287 XdB(0x0afc2f19), XdB(0x0bb2ef7f), XdB(0x0c759034), XdB(0x0d44d6ca),
288 XdB(0x0e2195bc), XdB(0x0f0cad0d), XdB(0x10070b62), XdB(0x1111aeea),
289 XdB(0x122da66c), XdB(0x135c120f), XdB(0x149e24d9), XdB(0x15f525b1),
290 XdB(0x176270e3), XdB(0x18e7794b), XdB(0x1a85c9ae), XdB(0x1c3f06d1),
291 XdB(0x1e14f07d), XdB(0x200963d7), XdB(0x221e5ccd), XdB(0x2455f870),
292 XdB(0x26b2770b), XdB(0x29363e2b), XdB(0x2be3db5c), XdB(0x2ebe06b6),
293 XdB(0x31c7a55b), XdB(0x3503ccd4), XdB(0x3875c5aa), XdB(0x3c210f44),
294 XdB(0x4009632b), XdB(0x4432b8cf), XdB(0x48a149bc), XdB(0x4d59959e),
295 XdB(0x52606733), XdB(0x57bad899), XdB(0x5d6e593a), XdB(0x6380b298),
296 XdB(0x69f80e9a), XdB(0x70dafda8), XdB(0x78307d76), XdB(0x7fffffff),
297 };
298
render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t * d)299 static void render_line(int n, int x0,int x1,int y0,int y1,ogg_int32_t *d){
300 int dy=y1-y0;
301 int adx=x1-x0;
302 int ady=abs(dy);
303 int base=dy/adx;
304 int sy=(dy<0?base-1:base+1);
305 int x=x0;
306 int y=y0;
307 int err=0;
308
309 if(n>x1)n=x1;
310 ady-=abs(base*adx);
311
312 if(x<n)
313 d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
314
315 while(++x<n){
316 err=err+ady;
317 if(err>=adx){
318 err-=adx;
319 y+=sy;
320 }else{
321 y+=base;
322 }
323 d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
324 }
325 }
326
floor1_inverse1(vorbis_block * vb,vorbis_look_floor * in)327 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
328 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
329 vorbis_info_floor1 *info=look->vi;
330 codec_setup_info *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
331
332 int i,j,k;
333 codebook *books=ci->fullbooks;
334
335 /* unpack wrapped/predicted values from stream */
336 if(oggpack_read(&vb->opb,1)==1){
337 int *fit_value=(int *)_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
338
339 fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
340 fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
341
342 /* partition by partition */
343 /* partition by partition */
344 for(i=0,j=2;i<info->partitions;i++){
345 int classv=info->partitionclass[i];
346 int cdim=info->class_dim[classv];
347 int csubbits=info->class_subs[classv];
348 int csub=1<<csubbits;
349 int cval=0;
350
351 /* decode the partition's first stage cascade value */
352 if(csubbits){
353 cval=vorbis_book_decode(books+info->class_book[classv],&vb->opb);
354
355 if(cval==-1)goto eop;
356 }
357
358 for(k=0;k<cdim;k++){
359 int book=info->class_subbook[classv][cval&(csub-1)];
360 cval>>=csubbits;
361 if(book>=0){
362 if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
363 goto eop;
364 }else{
365 fit_value[j+k]=0;
366 }
367 }
368 j+=cdim;
369 }
370
371 /* unwrap positive values and reconsitute via linear interpolation */
372 for(i=2;i<look->posts;i++){
373 int predicted=render_point(info->postlist[look->loneighbor[i-2]],
374 info->postlist[look->hineighbor[i-2]],
375 fit_value[look->loneighbor[i-2]],
376 fit_value[look->hineighbor[i-2]],
377 info->postlist[i]);
378 int hiroom=look->quant_q-predicted;
379 int loroom=predicted;
380 int room=(hiroom<loroom?hiroom:loroom)<<1;
381 int val=fit_value[i];
382
383 if(val){
384 if(val>=room){
385 if(hiroom>loroom){
386 val = val-loroom;
387 }else{
388 val = -1-(val-hiroom);
389 }
390 }else{
391 if(val&1){
392 val= -((val+1)>>1);
393 }else{
394 val>>=1;
395 }
396 }
397
398 fit_value[i]=(val+predicted)&0x7fff;;
399 fit_value[look->loneighbor[i-2]]&=0x7fff;
400 fit_value[look->hineighbor[i-2]]&=0x7fff;
401
402 }else{
403 fit_value[i]=predicted|0x8000;
404 }
405
406 }
407
408 return(fit_value);
409 }
410 eop:
411 return(NULL);
412 }
413
floor1_inverse2(vorbis_block * vb,vorbis_look_floor * in,void * memo,ogg_int32_t * out)414 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
415 ogg_int32_t *out){
416 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
417 vorbis_info_floor1 *info=look->vi;
418
419 codec_setup_info *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
420 int n=ci->blocksizes[vb->W]/2;
421 int j;
422
423 if(memo){
424 /* render the lines */
425 int *fit_value=(int *)memo;
426 int hx=0;
427 int lx=0;
428 int ly=fit_value[0]*info->mult;
429 /* guard lookup against out-of-range values */
430 ly=(ly<0?0:ly>255?255:ly);
431
432 for(j=1;j<look->posts;j++){
433 int current=look->forward_index[j];
434 int hy=fit_value[current]&0x7fff;
435 if(hy==fit_value[current]){
436
437 hx=info->postlist[current];
438 hy*=info->mult;
439 /* guard lookup against out-of-range values */
440 hy=(hy<0?0:hy>255?255:hy);
441
442 render_line(n,lx,hx,ly,hy,out);
443
444 lx=hx;
445 ly=hy;
446 }
447 }
448 for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
449 return(1);
450 }
451 memset(out,0,sizeof(*out)*n);
452 return(0);
453 }
454
455 /* export hooks */
456 vorbis_func_floor floor1_exportbundle={
457 &floor1_unpack,&floor1_look,&floor1_free_info,
458 &floor1_free_look,&floor1_inverse1,&floor1_inverse2
459 };
460
461