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 if(rangebits < 0) goto err_out;
144
145 for(j=0,k=0;j<info->partitions;j++)
146 count+=info->klass[info->partitionclass[j]].class_dim;
147 info->postlist=
148 (ogg_uint16_t *)_ogg_malloc((count+2)*sizeof(*info->postlist));
149 info->forward_index=
150 (ogg_uint8_t *)_ogg_malloc((count+2)*sizeof(*info->forward_index));
151 info->loneighbor=
152 (ogg_uint8_t *)_ogg_malloc(count*sizeof(*info->loneighbor));
153 info->hineighbor=
154 (ogg_uint8_t *)_ogg_malloc(count*sizeof(*info->hineighbor));
155
156 count=0;
157 for(j=0,k=0;j<info->partitions;j++){
158 count+=info->klass[info->partitionclass[j]].class_dim;
159 for(;k<count;k++){
160 int t=info->postlist[k+2]=(ogg_uint16_t)oggpack_read(opb,rangebits);
161 if(t>=(1<<rangebits))goto err_out;
162 }
163 }
164 if(oggpack_eop(opb))goto err_out;
165 info->postlist[0]=0;
166 info->postlist[1]=1<<rangebits;
167 info->posts=count+2;
168
169 /* also store a sorted position index */
170 for(j=0;j<info->posts;j++)info->forward_index[j]=j;
171 mergesort(info->forward_index,info->postlist,info->posts);
172
173 /* discover our neighbors for decode where we don't use fit flags
174 (that would push the neighbors outward) */
175 for(j=0;j<info->posts-2;j++){
176 int lo=0;
177 int hi=1;
178 int lx=0;
179 int hx=info->postlist[1];
180 int currentx=info->postlist[j+2];
181 for(k=0;k<j+2;k++){
182 int x=info->postlist[k];
183 if(x>lx && x<currentx){
184 lo=k;
185 lx=x;
186 }
187 if(x<hx && x>currentx){
188 hi=k;
189 hx=x;
190 }
191 }
192 info->loneighbor[j]=lo;
193 info->hineighbor[j]=hi;
194 }
195
196 return(info);
197
198 err_out:
199 floor1_free_info(info);
200 return(NULL);
201 }
202
203 #ifdef ONLY_C
204 static
205 #endif
render_point(int x0,int x1,int y0,int y1,int x)206 int render_point(int x0,int x1,int y0,int y1,int x){
207 y0&=0x7fff; /* mask off flag */
208 y1&=0x7fff;
209
210 {
211 int dy=y1-y0;
212 int adx=x1-x0;
213 int ady=abs(dy);
214 int err=ady*(x-x0);
215
216 int off=err/adx;
217 if(dy<0)return(y0-off);
218 return(y0+off);
219 }
220 }
221
222 #ifndef ONLY_C
223 void render_lineARM(int n, ogg_int32_t *d,const ogg_int32_t *floor, int base, int err, int adx, int ady);
224 #endif
225
render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t * d)226 static void render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t *d){
227 int dy;
228 int adx;
229 int ady;
230 int base;
231 int err;
232 const ogg_int32_t *floor;
233
234 if(n>x1)n=x1;
235 n -= x0;
236 if (n <= 0 || y0 < 0 || y0 > 255 || y1 < 0 || y1 > 255) {
237 return;
238 }
239 dy=y1-y0;
240 adx=x1-x0;
241 ady=abs(dy);
242 base=dy/adx;
243 err=adx-1;
244 floor=&FLOOR_fromdB_LOOKUP[y0];
245 d += x0;
246 ady-=abs(base*adx);
247
248 /* We should add base each time, and then:
249 * if dy >=0 we occasionally add 1
250 * else occasionally subtract 1.
251 * As an optimisation we say that if dy <0 we make base 1 smaller.
252 * Then we need to add 1 occassionally, rather than subtract 1 - but we
253 * need to add 1 in all the cases when we wouldn't have done so before.
254 * Previously we'd have added 1 (100*ady/adx)% of the time. Now we want
255 * to do so (100*(adx-ady)/adx)% of the time.
256 */
257 if (dy < 0){
258 base--;
259 ady = adx-ady;
260 err = 0;
261 }
262
263 //if(x<n)
264 // d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
265
266 #if defined(ONLY_C)
267 do{
268 *d = MULT31_SHIFT15(*d,*floor);
269 d++;
270 floor+=base;
271 err-=ady;
272 if(err<0){
273 err+=adx;
274 floor+=1;
275 }
276 n--;
277 } while(n>0);
278 #else
279 render_lineARM(n,d,floor,base,err,adx,ady);
280 #endif
281 }
282
floor1_memosize(vorbis_info_floor * i)283 int floor1_memosize(vorbis_info_floor *i){
284 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
285 return info->posts;
286 }
287
288 static int quant_look[4]={256,128,86,64};
289
floor1_inverse1(vorbis_dsp_state * vd,vorbis_info_floor * in,ogg_int32_t * fit_value)290 ogg_int32_t *floor1_inverse1(vorbis_dsp_state *vd,vorbis_info_floor *in,
291 ogg_int32_t *fit_value){
292 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
293 codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup;
294
295 int i,j,k;
296 codebook *books=ci->book_param;
297 int quant_q=quant_look[info->mult-1];
298
299 /* unpack wrapped/predicted values from stream */
300 if(oggpack_read(&vd->opb,1)==1){
301 fit_value[0]=oggpack_read(&vd->opb,ilog(quant_q-1));
302 fit_value[1]=oggpack_read(&vd->opb,ilog(quant_q-1));
303
304 /* partition by partition */
305 /* partition by partition */
306 for(i=0,j=2;i<info->partitions;i++){
307 int classv=info->partitionclass[i];
308 int cdim=info->klass[classv].class_dim;
309 int csubbits=info->klass[classv].class_subs;
310 int csub=1<<csubbits;
311 int cval=0;
312
313 /* decode the partition's first stage cascade value */
314 if(csubbits){
315 cval=vorbis_book_decode(books+info->klass[classv].class_book,&vd->opb);
316
317 if(cval==-1)goto eop;
318 }
319
320 for(k=0;k<cdim;k++){
321 int book=info->klass[classv].class_subbook[cval&(csub-1)];
322 cval>>=csubbits;
323 if(book!=0xff){
324 if((fit_value[j+k]=vorbis_book_decode(books+book,&vd->opb))==-1)
325 goto eop;
326 }else{
327 fit_value[j+k]=0;
328 }
329 }
330 j+=cdim;
331 }
332
333 /* unwrap positive values and reconsitute via linear interpolation */
334 for(i=2;i<info->posts;i++){
335 int predicted=render_point(info->postlist[info->loneighbor[i-2]],
336 info->postlist[info->hineighbor[i-2]],
337 fit_value[info->loneighbor[i-2]],
338 fit_value[info->hineighbor[i-2]],
339 info->postlist[i]);
340 int hiroom=quant_q-predicted;
341 int loroom=predicted;
342 int room=(hiroom<loroom?hiroom:loroom)<<1;
343 int val=fit_value[i];
344
345 if(val){
346 if(val>=room){
347 if(hiroom>loroom){
348 val = val-loroom;
349 }else{
350 val = -1-(val-hiroom);
351 }
352 }else{
353 if(val&1){
354 val= -((val+1)>>1);
355 }else{
356 val>>=1;
357 }
358 }
359
360 fit_value[i]=val+predicted;
361 fit_value[info->loneighbor[i-2]]&=0x7fff;
362 fit_value[info->hineighbor[i-2]]&=0x7fff;
363
364 }else{
365 fit_value[i]=predicted|0x8000;
366 }
367
368 }
369
370 return(fit_value);
371 }
372 eop:
373 return(NULL);
374 }
375
floor1_inverse2(vorbis_dsp_state * vd,vorbis_info_floor * in,ogg_int32_t * fit_value,ogg_int32_t * out)376 int floor1_inverse2(vorbis_dsp_state *vd,vorbis_info_floor *in,
377 ogg_int32_t *fit_value,ogg_int32_t *out){
378 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
379
380 codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup;
381 int n=ci->blocksizes[vd->W]/2;
382 int j;
383
384 if(fit_value){
385 /* render the lines */
386 int hx=0;
387 int lx=0;
388 int ly=fit_value[0]*info->mult;
389 for(j=1;j<info->posts;j++){
390 int current=info->forward_index[j];
391 int hy=fit_value[current]&0x7fff;
392 if(hy==fit_value[current]){
393
394 hy*=info->mult;
395 hx=info->postlist[current];
396
397 render_line(n,lx,hx,ly,hy,out);
398
399 lx=hx;
400 ly=hy;
401 }
402 }
403 for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
404 return(1);
405 }
406 memset(out,0,sizeof(*out)*n);
407 return(0);
408 }
409