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(char *index,ogg_uint16_t *vals,ogg_uint16_t n){ 77 ogg_uint16_t i,j; 78 char *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 (char *)_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 (char *)_ogg_malloc((count+2)*sizeof(*info->forward_index)); 150 info->loneighbor= 151 (char *)_ogg_malloc(count*sizeof(*info->loneighbor)); 152 info->hineighbor= 153 (char *)_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) 236 return; 237 dy=y1-y0; 238 adx=x1-x0; 239 ady=abs(dy); 240 base=dy/adx; 241 err=adx-1; 242 floor=&FLOOR_fromdB_LOOKUP[y0]; 243 d += x0; 244 ady-=abs(base*adx); 245 246 /* We should add base each time, and then: 247 * if dy >=0 we occasionally add 1 248 * else occasionally subtract 1. 249 * As an optimisation we say that if dy <0 we make base 1 smaller. 250 * Then we need to add 1 occassionally, rather than subtract 1 - but we 251 * need to add 1 in all the cases when we wouldn't have done so before. 252 * Previously we'd have added 1 (100*ady/adx)% of the time. Now we want 253 * to do so (100*(adx-ady)/adx)% of the time. 254 */ 255 if (dy < 0){ 256 base--; 257 ady = adx-ady; 258 err = 0; 259 } 260 261 //if(x<n) 262 // d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]); 263 264 #if defined(ONLY_C) 265 do{ 266 *d = MULT31_SHIFT15(*d,*floor); 267 d++; 268 floor+=base; 269 err-=ady; 270 if(err<0){ 271 err+=adx; 272 floor+=1; 273 } 274 n--; 275 } while(n>0); 276 #else 277 render_lineARM(n,d,floor,base,err,adx,ady); 278 #endif 279 } 280 281 int floor1_memosize(vorbis_info_floor *i){ 282 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i; 283 return info->posts; 284 } 285 286 static int quant_look[4]={256,128,86,64}; 287 288 ogg_int32_t *floor1_inverse1(vorbis_dsp_state *vd,vorbis_info_floor *in, 289 ogg_int32_t *fit_value){ 290 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in; 291 codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup; 292 293 int i,j,k; 294 codebook *books=ci->book_param; 295 int quant_q=quant_look[info->mult-1]; 296 297 /* unpack wrapped/predicted values from stream */ 298 if(oggpack_read(&vd->opb,1)==1){ 299 fit_value[0]=oggpack_read(&vd->opb,ilog(quant_q-1)); 300 fit_value[1]=oggpack_read(&vd->opb,ilog(quant_q-1)); 301 302 /* partition by partition */ 303 /* partition by partition */ 304 for(i=0,j=2;i<info->partitions;i++){ 305 int classv=info->partitionclass[i]; 306 int cdim=info->klass[classv].class_dim; 307 int csubbits=info->klass[classv].class_subs; 308 int csub=1<<csubbits; 309 int cval=0; 310 311 /* decode the partition's first stage cascade value */ 312 if(csubbits){ 313 cval=vorbis_book_decode(books+info->klass[classv].class_book,&vd->opb); 314 315 if(cval==-1)goto eop; 316 } 317 318 for(k=0;k<cdim;k++){ 319 int book=info->klass[classv].class_subbook[cval&(csub-1)]; 320 cval>>=csubbits; 321 if(book!=0xff){ 322 if((fit_value[j+k]=vorbis_book_decode(books+book,&vd->opb))==-1) 323 goto eop; 324 }else{ 325 fit_value[j+k]=0; 326 } 327 } 328 j+=cdim; 329 } 330 331 /* unwrap positive values and reconsitute via linear interpolation */ 332 for(i=2;i<info->posts;i++){ 333 int predicted=render_point(info->postlist[info->loneighbor[i-2]], 334 info->postlist[info->hineighbor[i-2]], 335 fit_value[info->loneighbor[i-2]], 336 fit_value[info->hineighbor[i-2]], 337 info->postlist[i]); 338 int hiroom=quant_q-predicted; 339 int loroom=predicted; 340 int room=(hiroom<loroom?hiroom:loroom)<<1; 341 int val=fit_value[i]; 342 343 if(val){ 344 if(val>=room){ 345 if(hiroom>loroom){ 346 val = val-loroom; 347 }else{ 348 val = -1-(val-hiroom); 349 } 350 }else{ 351 if(val&1){ 352 val= -((val+1)>>1); 353 }else{ 354 val>>=1; 355 } 356 } 357 358 fit_value[i]=val+predicted; 359 fit_value[info->loneighbor[i-2]]&=0x7fff; 360 fit_value[info->hineighbor[i-2]]&=0x7fff; 361 362 }else{ 363 fit_value[i]=predicted|0x8000; 364 } 365 366 } 367 368 return(fit_value); 369 } 370 eop: 371 return(NULL); 372 } 373 374 int floor1_inverse2(vorbis_dsp_state *vd,vorbis_info_floor *in, 375 ogg_int32_t *fit_value,ogg_int32_t *out){ 376 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in; 377 378 codec_setup_info *ci=(codec_setup_info *)vd->vi->codec_setup; 379 int n=ci->blocksizes[vd->W]/2; 380 int j; 381 382 if(fit_value){ 383 /* render the lines */ 384 int hx=0; 385 int lx=0; 386 int ly=fit_value[0]*info->mult; 387 for(j=1;j<info->posts;j++){ 388 int current=info->forward_index[j]; 389 int hy=fit_value[current]&0x7fff; 390 if(hy==fit_value[current]){ 391 392 hy*=info->mult; 393 hx=info->postlist[current]; 394 395 render_line(n,lx,hx,ly,hy,out); 396 397 lx=hx; 398 ly=hy; 399 } 400 } 401 for(j=hx;j<n;j++)out[j]*=ly; /* be certain */ 402 return(1); 403 } 404 memset(out,0,sizeof(*out)*n); 405 return(0); 406 } 407
