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 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 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 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 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 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 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 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 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 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
