1 /************************************************************************
2  * Copyright (C) 2002-2009, Xiph.org Foundation
3  * Copyright (C) 2010, Robin Watts for Pinknoise Productions Ltd
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  *     * Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *     * Redistributions in binary form must reproduce the above
13  * copyright notice, this list of conditions and the following disclaimer
14  * in the documentation and/or other materials provided with the
15  * distribution.
16  *     * Neither the names of the Xiph.org Foundation nor Pinknoise
17  * Productions Ltd nor the names of its contributors may be used to
18  * endorse or promote products derived from this software without
19  * specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  ************************************************************************
33 
34  function: floor backend 1 implementation
35 
36  ************************************************************************/
37 
38 #include <stdlib.h>
39 #include <string.h>
40 #include <math.h>
41 #include "ogg.h"
42 #include "ivorbiscodec.h"
43 #include "codec_internal.h"
44 #include "codebook.h"
45 #include "misc.h"
46 
47 extern const ogg_int32_t FLOOR_fromdB_LOOKUP[];
48 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
49 #define VIF_POSIT 63
50 
51 /***********************************************/
52 
floor1_free_info(vorbis_info_floor * i)53 void floor1_free_info(vorbis_info_floor *i){
54   vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
55   if(info){
56     if(info->klass)_ogg_free(info->klass);
57     if(info->partitionclass)_ogg_free(info->partitionclass);
58     if(info->postlist)_ogg_free(info->postlist);
59     if(info->forward_index)_ogg_free(info->forward_index);
60     if(info->hineighbor)_ogg_free(info->hineighbor);
61     if(info->loneighbor)_ogg_free(info->loneighbor);
62     memset(info,0,sizeof(*info));
63     _ogg_free(info);
64   }
65 }
66 
ilog(unsigned int v)67 static int ilog(unsigned int v){
68   int ret=0;
69   while(v){
70     ret++;
71     v>>=1;
72   }
73   return(ret);
74 }
75 
mergesort(ogg_uint8_t * index,ogg_uint16_t * vals,ogg_uint16_t n)76 static void mergesort(ogg_uint8_t *index,ogg_uint16_t *vals,ogg_uint16_t n){
77   ogg_uint16_t i,j;
78   ogg_uint8_t *temp,*A=index,*B=_ogg_malloc(n*sizeof(*B));
79 
80   for(i=1;i<n;i<<=1){
81     for(j=0;j+i<n;){
82       int k1=j;
83       int mid=j+i;
84       int k2=mid;
85       int end=(j+i*2<n?j+i*2:n);
86       while(k1<mid && k2<end){
87 	if(vals[A[k1]]<vals[A[k2]])
88 	  B[j++]=A[k1++];
89 	else
90 	  B[j++]=A[k2++];
91       }
92       while(k1<mid) B[j++]=A[k1++];
93       while(k2<end) B[j++]=A[k2++];
94     }
95     for(;j<n;j++)B[j]=A[j];
96     temp=A;A=B;B=temp;
97   }
98 
99   if(B==index){
100     for(j=0;j<n;j++)B[j]=A[j];
101     _ogg_free(A);
102   }else
103     _ogg_free(B);
104 }
105 
106 
floor1_info_unpack(vorbis_info * vi,oggpack_buffer * opb)107 vorbis_info_floor *floor1_info_unpack (vorbis_info *vi,oggpack_buffer *opb){
108   codec_setup_info     *ci=(codec_setup_info *)vi->codec_setup;
109   int j,k,count=0,maxclass=-1,rangebits;
110 
111   vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
112   /* read partitions */
113   info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
114   info->partitionclass=
115     (ogg_uint8_t *)_ogg_malloc(info->partitions*sizeof(*info->partitionclass));
116   for(j=0;j<info->partitions;j++){
117     info->partitionclass[j]=(char)oggpack_read(opb,4); /* only 0 to 15 legal */
118     if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
119   }
120 
121   /* read partition classes */
122   info->klass=
123     (floor1class *)_ogg_malloc((maxclass+1)*sizeof(*info->klass));
124   for(j=0;j<maxclass+1;j++){
125     info->klass[j].class_dim=(char)oggpack_read(opb,3)+1; /* 1 to 8 */
126     info->klass[j].class_subs=(char)oggpack_read(opb,2); /* 0,1,2,3 bits */
127     if(oggpack_eop(opb)<0) goto err_out;
128     if(info->klass[j].class_subs)
129       info->klass[j].class_book=(unsigned char)oggpack_read(opb,8);
130     else
131       info->klass[j].class_book=0;
132     if(info->klass[j].class_book>=ci->books)goto err_out;
133     for(k=0;k<(1<<info->klass[j].class_subs);k++){
134       info->klass[j].class_subbook[k]=(unsigned char)(oggpack_read(opb,8)-1);
135       if(info->klass[j].class_subbook[k]>=ci->books &&
136 	 info->klass[j].class_subbook[k]!=0xff)goto err_out;
137     }
138   }
139 
140   /* read the post list */
141   info->mult=oggpack_read(opb,2)+1;     /* only 1,2,3,4 legal now */
142   rangebits=oggpack_read(opb,4);
143 
144   for(j=0,k=0;j<info->partitions;j++)
145     count+=info->klass[info->partitionclass[j]].class_dim;
146   info->postlist=
147     (ogg_uint16_t *)_ogg_malloc((count+2)*sizeof(*info->postlist));
148   info->forward_index=
149     (ogg_uint8_t *)_ogg_malloc((count+2)*sizeof(*info->forward_index));
150   info->loneighbor=
151     (ogg_uint8_t *)_ogg_malloc(count*sizeof(*info->loneighbor));
152   info->hineighbor=
153     (ogg_uint8_t *)_ogg_malloc(count*sizeof(*info->hineighbor));
154 
155   count=0;
156   for(j=0,k=0;j<info->partitions;j++){
157     count+=info->klass[info->partitionclass[j]].class_dim;
158     for(;k<count;k++){
159       int t=info->postlist[k+2]=(ogg_uint16_t)oggpack_read(opb,rangebits);
160       if(t>=(1<<rangebits))goto err_out;
161     }
162   }
163   if(oggpack_eop(opb))goto err_out;
164   info->postlist[0]=0;
165   info->postlist[1]=1<<rangebits;
166   info->posts=count+2;
167 
168   /* also store a sorted position index */
169   for(j=0;j<info->posts;j++)info->forward_index[j]=j;
170   mergesort(info->forward_index,info->postlist,info->posts);
171 
172   /* discover our neighbors for decode where we don't use fit flags
173      (that would push the neighbors outward) */
174   for(j=0;j<info->posts-2;j++){
175     int lo=0;
176     int hi=1;
177     int lx=0;
178     int hx=info->postlist[1];
179     int currentx=info->postlist[j+2];
180     for(k=0;k<j+2;k++){
181       int x=info->postlist[k];
182       if(x>lx && x<currentx){
183 	lo=k;
184 	lx=x;
185       }
186       if(x<hx && x>currentx){
187 	hi=k;
188 	hx=x;
189       }
190     }
191     info->loneighbor[j]=lo;
192     info->hineighbor[j]=hi;
193   }
194 
195   return(info);
196 
197  err_out:
198   floor1_free_info(info);
199   return(NULL);
200 }
201 
202 #ifdef ONLY_C
203 static
204 #endif
render_point(int x0,int x1,int y0,int y1,int x)205 int render_point(int x0,int x1,int y0,int y1,int x){
206   y0&=0x7fff; /* mask off flag */
207   y1&=0x7fff;
208 
209   {
210     int dy=y1-y0;
211     int adx=x1-x0;
212     int ady=abs(dy);
213     int err=ady*(x-x0);
214 
215     int off=err/adx;
216     if(dy<0)return(y0-off);
217     return(y0+off);
218   }
219 }
220 
221 #ifndef ONLY_C
222 void render_lineARM(int n, ogg_int32_t *d,const ogg_int32_t *floor, int base, int err, int adx, int ady);
223 #endif
224 
render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t * d)225 static void render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t *d){
226   int dy;
227   int adx;
228   int ady;
229   int base;
230   int err;
231   const ogg_int32_t *floor;
232 
233   if(n>x1)n=x1;
234   n -= x0;
235   if (n <= 0 || y0 < 0 || y0 > 255 || y1 < 0 || y1 > 255) {
236     return;
237   }
238   dy=y1-y0;
239   adx=x1-x0;
240   ady=abs(dy);
241   base=dy/adx;
242   err=adx-1;
243   floor=&FLOOR_fromdB_LOOKUP[y0];
244   d += x0;
245   ady-=abs(base*adx);
246 
247   /* We should add base each time, and then:
248    *   if dy >=0 we occasionally add 1
249    *   else         occasionally subtract 1.
250    * As an optimisation we say that if dy <0 we make base 1 smaller.
251    * Then we need to add 1 occassionally, rather than subtract 1 - but we
252    * need to add 1 in all the cases when we wouldn't have done so before.
253    * Previously we'd have added 1 (100*ady/adx)% of the time. Now we want
254    * to do so (100*(adx-ady)/adx)% of the time.
255    */
256   if (dy < 0){
257     base--;
258     ady = adx-ady;
259     err = 0;
260   }
261 
262   //if(x<n)
263   //  d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
264 
265 #if defined(ONLY_C)
266   do{
267     *d = MULT31_SHIFT15(*d,*floor);
268     d++;
269     floor+=base;
270     err-=ady;
271     if(err<0){
272       err+=adx;
273       floor+=1;
274     }
275     n--;
276   } while(n>0);
277 #else
278   render_lineARM(n,d,floor,base,err,adx,ady);
279 #endif
280 }
281 
floor1_memosize(vorbis_info_floor * i)282 int floor1_memosize(vorbis_info_floor *i){
283   vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
284   return info->posts;
285 }
286 
287 static int quant_look[4]={256,128,86,64};
288 
floor1_inverse1(vorbis_dsp_state * vd,vorbis_info_floor * in,ogg_int32_t * fit_value)289 ogg_int32_t *floor1_inverse1(vorbis_dsp_state *vd,vorbis_info_floor *in,
290 			     ogg_int32_t *fit_value){
291   vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
292   codec_setup_info   *ci=(codec_setup_info *)vd->vi->codec_setup;
293 
294   int i,j,k;
295   codebook *books=ci->book_param;
296   int quant_q=quant_look[info->mult-1];
297 
298   /* unpack wrapped/predicted values from stream */
299   if(oggpack_read(&vd->opb,1)==1){
300     fit_value[0]=oggpack_read(&vd->opb,ilog(quant_q-1));
301     fit_value[1]=oggpack_read(&vd->opb,ilog(quant_q-1));
302 
303     /* partition by partition */
304     /* partition by partition */
305     for(i=0,j=2;i<info->partitions;i++){
306       int classv=info->partitionclass[i];
307       int cdim=info->klass[classv].class_dim;
308       int csubbits=info->klass[classv].class_subs;
309       int csub=1<<csubbits;
310       int cval=0;
311 
312       /* decode the partition's first stage cascade value */
313       if(csubbits){
314 	cval=vorbis_book_decode(books+info->klass[classv].class_book,&vd->opb);
315 
316 	if(cval==-1)goto eop;
317       }
318 
319       for(k=0;k<cdim;k++){
320 	int book=info->klass[classv].class_subbook[cval&(csub-1)];
321 	cval>>=csubbits;
322 	if(book!=0xff){
323 	  if((fit_value[j+k]=vorbis_book_decode(books+book,&vd->opb))==-1)
324 	    goto eop;
325 	}else{
326 	  fit_value[j+k]=0;
327 	}
328       }
329       j+=cdim;
330     }
331 
332     /* unwrap positive values and reconsitute via linear interpolation */
333     for(i=2;i<info->posts;i++){
334       int predicted=render_point(info->postlist[info->loneighbor[i-2]],
335 				 info->postlist[info->hineighbor[i-2]],
336 				 fit_value[info->loneighbor[i-2]],
337 				 fit_value[info->hineighbor[i-2]],
338 				 info->postlist[i]);
339       int hiroom=quant_q-predicted;
340       int loroom=predicted;
341       int room=(hiroom<loroom?hiroom:loroom)<<1;
342       int val=fit_value[i];
343 
344       if(val){
345 	if(val>=room){
346 	  if(hiroom>loroom){
347 	    val = val-loroom;
348 	  }else{
349 	  val = -1-(val-hiroom);
350 	  }
351 	}else{
352 	  if(val&1){
353 	    val= -((val+1)>>1);
354 	  }else{
355 	    val>>=1;
356 	  }
357 	}
358 
359 	fit_value[i]=val+predicted;
360 	fit_value[info->loneighbor[i-2]]&=0x7fff;
361 	fit_value[info->hineighbor[i-2]]&=0x7fff;
362 
363       }else{
364 	fit_value[i]=predicted|0x8000;
365       }
366 
367     }
368 
369     return(fit_value);
370   }
371  eop:
372   return(NULL);
373 }
374 
floor1_inverse2(vorbis_dsp_state * vd,vorbis_info_floor * in,ogg_int32_t * fit_value,ogg_int32_t * out)375 int floor1_inverse2(vorbis_dsp_state *vd,vorbis_info_floor *in,
376 		    ogg_int32_t *fit_value,ogg_int32_t *out){
377   vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
378 
379   codec_setup_info   *ci=(codec_setup_info *)vd->vi->codec_setup;
380   int                  n=ci->blocksizes[vd->W]/2;
381   int j;
382 
383   if(fit_value){
384     /* render the lines */
385     int hx=0;
386     int lx=0;
387     int ly=fit_value[0]*info->mult;
388     for(j=1;j<info->posts;j++){
389       int current=info->forward_index[j];
390       int hy=fit_value[current]&0x7fff;
391       if(hy==fit_value[current]){
392 
393 	hy*=info->mult;
394 	hx=info->postlist[current];
395 
396 	render_line(n,lx,hx,ly,hy,out);
397 
398 	lx=hx;
399 	ly=hy;
400       }
401     }
402     for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
403     return(1);
404   }
405   memset(out,0,sizeof(*out)*n);
406   return(0);
407 }
408