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-2003 *
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.h"
22 #include "ivorbiscodec.h"
23 #include "codec_internal.h"
24 #include "codebook.h"
25 #include "misc.h"
26
27 extern const ogg_int32_t FLOOR_fromdB_LOOKUP[];
28 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
29 #define VIF_POSIT 63
30
31 /***********************************************/
32
floor1_free_info(vorbis_info_floor * i)33 void floor1_free_info(vorbis_info_floor *i){
34 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
35 if(info){
36 if(info->class)_ogg_free(info->class);
37 if(info->partitionclass)_ogg_free(info->partitionclass);
38 if(info->postlist)_ogg_free(info->postlist);
39 if(info->forward_index)_ogg_free(info->forward_index);
40 if(info->hineighbor)_ogg_free(info->hineighbor);
41 if(info->loneighbor)_ogg_free(info->loneighbor);
42 memset(info,0,sizeof(*info));
43 _ogg_free(info);
44 }
45 }
46
ilog(unsigned int v)47 static int ilog(unsigned int v){
48 int ret=0;
49 while(v){
50 ret++;
51 v>>=1;
52 }
53 return(ret);
54 }
55
mergesort(char * index,ogg_uint16_t * vals,ogg_uint16_t n)56 static void mergesort(char *index,ogg_uint16_t *vals,ogg_uint16_t n){
57 ogg_uint16_t i,j;
58 char *temp,*A=index,*B=_ogg_malloc(n*sizeof(*B));
59
60 for(i=1;i<n;i<<=1){
61 for(j=0;j+i<n;){
62 int k1=j;
63 int mid=j+i;
64 int k2=mid;
65 int end=(j+i*2<n?j+i*2:n);
66 while(k1<mid && k2<end){
67 if(vals[A[k1]]<vals[A[k2]])
68 B[j++]=A[k1++];
69 else
70 B[j++]=A[k2++];
71 }
72 while(k1<mid) B[j++]=A[k1++];
73 while(k2<end) B[j++]=A[k2++];
74 }
75 for(;j<n;j++)B[j]=A[j];
76 temp=A;A=B;B=temp;
77 }
78
79 if(B==index){
80 for(j=0;j<n;j++)B[j]=A[j];
81 _ogg_free(A);
82 }else
83 _ogg_free(B);
84 }
85
86
floor1_info_unpack(vorbis_info * vi,oggpack_buffer * opb)87 vorbis_info_floor *floor1_info_unpack (vorbis_info *vi,oggpack_buffer *opb){
88 codec_setup_info *ci=(codec_setup_info *)vi->codec_setup;
89 int j,k,count=0,maxclass=-1,rangebits;
90
91 vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
92 /* read partitions */
93 info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
94 info->partitionclass=
95 (char *)_ogg_malloc(info->partitions*sizeof(*info->partitionclass));
96 for(j=0;j<info->partitions;j++){
97 info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
98 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
99 }
100
101 /* read partition classes */
102 info->class=
103 (floor1class *)_ogg_malloc((maxclass+1)*sizeof(*info->class));
104 for(j=0;j<maxclass+1;j++){
105 info->class[j].class_dim=oggpack_read(opb,3)+1; /* 1 to 8 */
106 info->class[j].class_subs=oggpack_read(opb,2); /* 0,1,2,3 bits */
107 if(oggpack_eop(opb)<0) goto err_out;
108 if(info->class[j].class_subs)
109 info->class[j].class_book=oggpack_read(opb,8);
110 else
111 info->class[j].class_book=0;
112 if(info->class[j].class_book>=ci->books)goto err_out;
113 for(k=0;k<(1<<info->class[j].class_subs);k++){
114 info->class[j].class_subbook[k]=oggpack_read(opb,8)-1;
115 if(info->class[j].class_subbook[k]>=ci->books &&
116 info->class[j].class_subbook[k]!=0xff)goto err_out;
117 }
118 }
119
120 /* read the post list */
121 info->mult=oggpack_read(opb,2)+1; /* only 1,2,3,4 legal now */
122 rangebits=oggpack_read(opb,4);
123
124 for(j=0,k=0;j<info->partitions;j++)
125 count+=info->class[info->partitionclass[j]].class_dim;
126 info->postlist=
127 (ogg_uint16_t *)_ogg_malloc((count+2)*sizeof(*info->postlist));
128 info->forward_index=
129 (char *)_ogg_malloc((count+2)*sizeof(*info->forward_index));
130 info->loneighbor=
131 (char *)_ogg_malloc(count*sizeof(*info->loneighbor));
132 info->hineighbor=
133 (char *)_ogg_malloc(count*sizeof(*info->hineighbor));
134
135 count=0;
136 for(j=0,k=0;j<info->partitions;j++){
137 count+=info->class[info->partitionclass[j]].class_dim;
138 for(;k<count;k++){
139 int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
140 if(t>=(1<<rangebits))goto err_out;
141 }
142 }
143 if(oggpack_eop(opb))goto err_out;
144 info->postlist[0]=0;
145 info->postlist[1]=1<<rangebits;
146 info->posts=count+2;
147
148 /* also store a sorted position index */
149 for(j=0;j<info->posts;j++)info->forward_index[j]=j;
150 mergesort(info->forward_index,info->postlist,info->posts);
151
152 /* discover our neighbors for decode where we don't use fit flags
153 (that would push the neighbors outward) */
154 for(j=0;j<info->posts-2;j++){
155 int lo=0;
156 int hi=1;
157 int lx=0;
158 int hx=info->postlist[1];
159 int currentx=info->postlist[j+2];
160 for(k=0;k<j+2;k++){
161 int x=info->postlist[k];
162 if(x>lx && x<currentx){
163 lo=k;
164 lx=x;
165 }
166 if(x<hx && x>currentx){
167 hi=k;
168 hx=x;
169 }
170 }
171 info->loneighbor[j]=lo;
172 info->hineighbor[j]=hi;
173 }
174
175 return(info);
176
177 err_out:
178 floor1_free_info(info);
179 return(NULL);
180 }
181
render_point(int x0,int x1,int y0,int y1,int x)182 static int render_point(int x0,int x1,int y0,int y1,int x){
183 y0&=0x7fff; /* mask off flag */
184 y1&=0x7fff;
185
186 {
187 int dy=y1-y0;
188 int adx=x1-x0;
189 int ady=abs(dy);
190 int err=ady*(x-x0);
191
192 int off=err/adx;
193 if(dy<0)return(y0-off);
194 return(y0+off);
195 }
196 }
197
render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t * d)198 static void render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t *d){
199 int dy=y1-y0;
200 int adx=x1-x0;
201 int ady=abs(dy);
202 int base=dy/adx;
203 int sy=(dy<0?base-1:base+1);
204 int x=x0;
205 int y=y0;
206 int err=0;
207
208 if(n>x1)n=x1;
209 ady-=abs(base*adx);
210
211 if(x<n)
212 d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
213
214 while(++x<n){
215 err=err+ady;
216 if(err>=adx){
217 err-=adx;
218 y+=sy;
219 }else{
220 y+=base;
221 }
222 d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
223 }
224 }
225
floor1_memosize(vorbis_info_floor * i)226 int floor1_memosize(vorbis_info_floor *i){
227 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
228 return info->posts;
229 }
230
231 static int quant_look[4]={256,128,86,64};
232
floor1_inverse1(vorbis_dsp_state * vd,vorbis_info_floor * in,ogg_int32_t * fit_value)233 ogg_int32_t *floor1_inverse1(vorbis_dsp_state *vd,vorbis_info_floor *in,
234 ogg_int32_t *fit_value){
235 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
236 codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup;
237
238 int i,j,k;
239 codebook *books=ci->book_param;
240 int quant_q=quant_look[info->mult-1];
241
242 /* unpack wrapped/predicted values from stream */
243 if(oggpack_read(&vd->opb,1)==1){
244 fit_value[0]=oggpack_read(&vd->opb,ilog(quant_q-1));
245 fit_value[1]=oggpack_read(&vd->opb,ilog(quant_q-1));
246
247 /* partition by partition */
248 /* partition by partition */
249 for(i=0,j=2;i<info->partitions;i++){
250 int classv=info->partitionclass[i];
251 int cdim=info->class[classv].class_dim;
252 int csubbits=info->class[classv].class_subs;
253 int csub=1<<csubbits;
254 int cval=0;
255
256 /* decode the partition's first stage cascade value */
257 if(csubbits){
258 cval=vorbis_book_decode(books+info->class[classv].class_book,&vd->opb);
259
260 if(cval==-1)goto eop;
261 }
262
263 for(k=0;k<cdim;k++){
264 int book=info->class[classv].class_subbook[cval&(csub-1)];
265 cval>>=csubbits;
266 if(book!=0xff){
267 if((fit_value[j+k]=vorbis_book_decode(books+book,&vd->opb))==-1)
268 goto eop;
269 }else{
270 fit_value[j+k]=0;
271 }
272 }
273 j+=cdim;
274 }
275
276 /* unwrap positive values and reconsitute via linear interpolation */
277 for(i=2;i<info->posts;i++){
278 int predicted=render_point(info->postlist[info->loneighbor[i-2]],
279 info->postlist[info->hineighbor[i-2]],
280 fit_value[info->loneighbor[i-2]],
281 fit_value[info->hineighbor[i-2]],
282 info->postlist[i]);
283 int hiroom=quant_q-predicted;
284 int loroom=predicted;
285 int room=(hiroom<loroom?hiroom:loroom)<<1;
286 int val=fit_value[i];
287
288 if(val){
289 if(val>=room){
290 if(hiroom>loroom){
291 val = val-loroom;
292 }else{
293 val = -1-(val-hiroom);
294 }
295 }else{
296 if(val&1){
297 val= -((val+1)>>1);
298 }else{
299 val>>=1;
300 }
301 }
302
303 fit_value[i]=val+predicted;
304 fit_value[info->loneighbor[i-2]]&=0x7fff;
305 fit_value[info->hineighbor[i-2]]&=0x7fff;
306
307 }else{
308 fit_value[i]=predicted|0x8000;
309 }
310
311 }
312
313 return(fit_value);
314 }
315 eop:
316 return(NULL);
317 }
318
floor1_inverse2(vorbis_dsp_state * vd,vorbis_info_floor * in,ogg_int32_t * fit_value,ogg_int32_t * out)319 int floor1_inverse2(vorbis_dsp_state *vd,vorbis_info_floor *in,
320 ogg_int32_t *fit_value,ogg_int32_t *out){
321 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
322
323 codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup;
324 int n=ci->blocksizes[vd->W]/2;
325 int j;
326
327 if(fit_value){
328 /* render the lines */
329 int hx=0;
330 int lx=0;
331 int ly=fit_value[0]*info->mult;
332 for(j=1;j<info->posts;j++){
333 int current=info->forward_index[j];
334 int hy=fit_value[current]&0x7fff;
335 if(hy==fit_value[current]){
336
337 hy*=info->mult;
338 hx=info->postlist[current];
339
340 render_line(n,lx,hx,ly,hy,out);
341
342 lx=hx;
343 ly=hy;
344 }
345 }
346 for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
347 return(1);
348 }
349 memset(out,0,sizeof(*out)*n);
350 return(0);
351 }
352