1 /******************************************************************** 2 * * 3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. * 4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * 5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * 6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * 7 * * 8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009 * 9 * by the Xiph.Org Foundation http://www.xiph.org/ * 10 * * 11 ******************************************************************** 12 13 function: floor backend 1 implementation 14 last mod: $Id: floor1.c 19031 2013-12-03 19:20:50Z tterribe $ 15 16 ********************************************************************/ 17 18 #include <stdlib.h> 19 #include <string.h> 20 #include <math.h> 21 #include <ogg/ogg.h> 22 #include "vorbis/codec.h" 23 #include "codec_internal.h" 24 #include "registry.h" 25 #include "codebook.h" 26 #include "misc.h" 27 #include "scales.h" 28 29 #include <stdio.h> 30 31 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */ 32 33 typedef struct lsfit_acc{ 34 int x0; 35 int x1; 36 37 int xa; 38 int ya; 39 int x2a; 40 int y2a; 41 int xya; 42 int an; 43 44 int xb; 45 int yb; 46 int x2b; 47 int y2b; 48 int xyb; 49 int bn; 50 } lsfit_acc; 51 52 /***********************************************/ 53 54 static void floor1_free_info(vorbis_info_floor *i){ 55 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i; 56 if(info){ 57 memset(info,0,sizeof(*info)); 58 _ogg_free(info); 59 } 60 } 61 62 static void floor1_free_look(vorbis_look_floor *i){ 63 vorbis_look_floor1 *look=(vorbis_look_floor1 *)i; 64 if(look){ 65 /*fprintf(stderr,"floor 1 bit usage %f:%f (%f total)\n", 66 (float)look->phrasebits/look->frames, 67 (float)look->postbits/look->frames, 68 (float)(look->postbits+look->phrasebits)/look->frames);*/ 69 70 memset(look,0,sizeof(*look)); 71 _ogg_free(look); 72 } 73 } 74 75 static int ilog(unsigned int v){ 76 int ret=0; 77 while(v){ 78 ret++; 79 v>>=1; 80 } 81 return(ret); 82 } 83 84 static int ilog2(unsigned int v){ 85 int ret=0; 86 if(v)--v; 87 while(v){ 88 ret++; 89 v>>=1; 90 } 91 return(ret); 92 } 93 94 static void floor1_pack (vorbis_info_floor *i,oggpack_buffer *opb){ 95 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i; 96 int j,k; 97 int count=0; 98 int rangebits; 99 int maxposit=info->postlist[1]; 100 int maxclass=-1; 101 102 /* save out partitions */ 103 oggpack_write(opb,info->partitions,5); /* only 0 to 31 legal */ 104 for(j=0;j<info->partitions;j++){ 105 oggpack_write(opb,info->partitionclass[j],4); /* only 0 to 15 legal */ 106 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j]; 107 } 108 109 /* save out partition classes */ 110 for(j=0;j<maxclass+1;j++){ 111 oggpack_write(opb,info->class_dim[j]-1,3); /* 1 to 8 */ 112 oggpack_write(opb,info->class_subs[j],2); /* 0 to 3 */ 113 if(info->class_subs[j])oggpack_write(opb,info->class_book[j],8); 114 for(k=0;k<(1<<info->class_subs[j]);k++) 115 oggpack_write(opb,info->class_subbook[j][k]+1,8); 116 } 117 118 /* save out the post list */ 119 oggpack_write(opb,info->mult-1,2); /* only 1,2,3,4 legal now */ 120 oggpack_write(opb,ilog2(maxposit),4); 121 rangebits=ilog2(maxposit); 122 123 for(j=0,k=0;j<info->partitions;j++){ 124 count+=info->class_dim[info->partitionclass[j]]; 125 for(;k<count;k++) 126 oggpack_write(opb,info->postlist[k+2],rangebits); 127 } 128 } 129 130 static int icomp(const void *a,const void *b){ 131 return(**(int **)a-**(int **)b); 132 } 133 134 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){ 135 codec_setup_info *ci=vi->codec_setup; 136 int j,k,count=0,maxclass=-1,rangebits; 137 138 vorbis_info_floor1 *info=_ogg_calloc(1,sizeof(*info)); 139 /* read partitions */ 140 info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */ 141 for(j=0;j<info->partitions;j++){ 142 info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */ 143 if(info->partitionclass[j]<0)goto err_out; 144 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j]; 145 } 146 147 /* read partition classes */ 148 for(j=0;j<maxclass+1;j++){ 149 info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */ 150 info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */ 151 if(info->class_subs[j]<0) 152 goto err_out; 153 if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8); 154 if(info->class_book[j]<0 || info->class_book[j]>=ci->books) 155 goto err_out; 156 for(k=0;k<(1<<info->class_subs[j]);k++){ 157 info->class_subbook[j][k]=oggpack_read(opb,8)-1; 158 if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books) 159 goto err_out; 160 } 161 } 162 163 /* read the post list */ 164 info->mult=oggpack_read(opb,2)+1; /* only 1,2,3,4 legal now */ 165 rangebits=oggpack_read(opb,4); 166 if(rangebits<0)goto err_out; 167 168 for(j=0,k=0;j<info->partitions;j++){ 169 count+=info->class_dim[info->partitionclass[j]]; 170 if(count>VIF_POSIT) goto err_out; 171 for(;k<count;k++){ 172 int t=info->postlist[k+2]=oggpack_read(opb,rangebits); 173 if(t<0 || t>=(1<<rangebits)) 174 goto err_out; 175 } 176 } 177 info->postlist[0]=0; 178 info->postlist[1]=1<<rangebits; 179 180 /* don't allow repeated values in post list as they'd result in 181 zero-length segments */ 182 { 183 int *sortpointer[VIF_POSIT+2]; 184 for(j=0;j<count+2;j++)sortpointer[j]=info->postlist+j; 185 qsort(sortpointer,count+2,sizeof(*sortpointer),icomp); 186 187 for(j=1;j<count+2;j++) 188 if(*sortpointer[j-1]==*sortpointer[j])goto err_out; 189 } 190 191 return(info); 192 193 err_out: 194 floor1_free_info(info); 195 return(NULL); 196 } 197 198 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd, 199 vorbis_info_floor *in){ 200 201 int *sortpointer[VIF_POSIT+2]; 202 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in; 203 vorbis_look_floor1 *look=_ogg_calloc(1,sizeof(*look)); 204 int i,j,n=0; 205 206 (void)vd; 207 208 look->vi=info; 209 look->n=info->postlist[1]; 210 211 /* we drop each position value in-between already decoded values, 212 and use linear interpolation to predict each new value past the 213 edges. The positions are read in the order of the position 214 list... we precompute the bounding positions in the lookup. Of 215 course, the neighbors can change (if a position is declined), but 216 this is an initial mapping */ 217 218 for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]]; 219 n+=2; 220 look->posts=n; 221 222 /* also store a sorted position index */ 223 for(i=0;i<n;i++)sortpointer[i]=info->postlist+i; 224 qsort(sortpointer,n,sizeof(*sortpointer),icomp); 225 226 /* points from sort order back to range number */ 227 for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist; 228 /* points from range order to sorted position */ 229 for(i=0;i<n;i++)look->reverse_index[look->forward_index[i]]=i; 230 /* we actually need the post values too */ 231 for(i=0;i<n;i++)look->sorted_index[i]=info->postlist[look->forward_index[i]]; 232 233 /* quantize values to multiplier spec */ 234 switch(info->mult){ 235 case 1: /* 1024 -> 256 */ 236 look->quant_q=256; 237 break; 238 case 2: /* 1024 -> 128 */ 239 look->quant_q=128; 240 break; 241 case 3: /* 1024 -> 86 */ 242 look->quant_q=86; 243 break; 244 case 4: /* 1024 -> 64 */ 245 look->quant_q=64; 246 break; 247 } 248 249 /* discover our neighbors for decode where we don't use fit flags 250 (that would push the neighbors outward) */ 251 for(i=0;i<n-2;i++){ 252 int lo=0; 253 int hi=1; 254 int lx=0; 255 int hx=look->n; 256 int currentx=info->postlist[i+2]; 257 for(j=0;j<i+2;j++){ 258 int x=info->postlist[j]; 259 if(x>lx && x<currentx){ 260 lo=j; 261 lx=x; 262 } 263 if(x<hx && x>currentx){ 264 hi=j; 265 hx=x; 266 } 267 } 268 look->loneighbor[i]=lo; 269 look->hineighbor[i]=hi; 270 } 271 272 return(look); 273 } 274 275 static int render_point(int x0,int x1,int y0,int y1,int x){ 276 y0&=0x7fff; /* mask off flag */ 277 y1&=0x7fff; 278 279 { 280 int dy=y1-y0; 281 int adx=x1-x0; 282 int ady=abs(dy); 283 int err=ady*(x-x0); 284 285 int off=err/adx; 286 if(dy<0)return(y0-off); 287 return(y0+off); 288 } 289 } 290 291 static int vorbis_dBquant(const float *x){ 292 int i= *x*7.3142857f+1023.5f; 293 if(i>1023)return(1023); 294 if(i<0)return(0); 295 return i; 296 } 297 298 static const float FLOOR1_fromdB_LOOKUP[256]={ 299 1.0649863e-07F, 1.1341951e-07F, 1.2079015e-07F, 1.2863978e-07F, 300 1.3699951e-07F, 1.4590251e-07F, 1.5538408e-07F, 1.6548181e-07F, 301 1.7623575e-07F, 1.8768855e-07F, 1.9988561e-07F, 2.128753e-07F, 302 2.2670913e-07F, 2.4144197e-07F, 2.5713223e-07F, 2.7384213e-07F, 303 2.9163793e-07F, 3.1059021e-07F, 3.3077411e-07F, 3.5226968e-07F, 304 3.7516214e-07F, 3.9954229e-07F, 4.2550680e-07F, 4.5315863e-07F, 305 4.8260743e-07F, 5.1396998e-07F, 5.4737065e-07F, 5.8294187e-07F, 306 6.2082472e-07F, 6.6116941e-07F, 7.0413592e-07F, 7.4989464e-07F, 307 7.9862701e-07F, 8.5052630e-07F, 9.0579828e-07F, 9.6466216e-07F, 308 1.0273513e-06F, 1.0941144e-06F, 1.1652161e-06F, 1.2409384e-06F, 309 1.3215816e-06F, 1.4074654e-06F, 1.4989305e-06F, 1.5963394e-06F, 310 1.7000785e-06F, 1.8105592e-06F, 1.9282195e-06F, 2.0535261e-06F, 311 2.1869758e-06F, 2.3290978e-06F, 2.4804557e-06F, 2.6416497e-06F, 312 2.8133190e-06F, 2.9961443e-06F, 3.1908506e-06F, 3.3982101e-06F, 313 3.6190449e-06F, 3.8542308e-06F, 4.1047004e-06F, 4.3714470e-06F, 314 4.6555282e-06F, 4.9580707e-06F, 5.2802740e-06F, 5.6234160e-06F, 315 5.9888572e-06F, 6.3780469e-06F, 6.7925283e-06F, 7.2339451e-06F, 316 7.7040476e-06F, 8.2047000e-06F, 8.7378876e-06F, 9.3057248e-06F, 317 9.9104632e-06F, 1.0554501e-05F, 1.1240392e-05F, 1.1970856e-05F, 318 1.2748789e-05F, 1.3577278e-05F, 1.4459606e-05F, 1.5399272e-05F, 319 1.6400004e-05F, 1.7465768e-05F, 1.8600792e-05F, 1.9809576e-05F, 320 2.1096914e-05F, 2.2467911e-05F, 2.3928002e-05F, 2.5482978e-05F, 321 2.7139006e-05F, 2.8902651e-05F, 3.0780908e-05F, 3.2781225e-05F, 322 3.4911534e-05F, 3.7180282e-05F, 3.9596466e-05F, 4.2169667e-05F, 323 4.4910090e-05F, 4.7828601e-05F, 5.0936773e-05F, 5.4246931e-05F, 324 5.7772202e-05F, 6.1526565e-05F, 6.5524908e-05F, 6.9783085e-05F, 325 7.4317983e-05F, 7.9147585e-05F, 8.4291040e-05F, 8.9768747e-05F, 326 9.5602426e-05F, 0.00010181521F, 0.00010843174F, 0.00011547824F, 327 0.00012298267F, 0.00013097477F, 0.00013948625F, 0.00014855085F, 328 0.00015820453F, 0.00016848555F, 0.00017943469F, 0.00019109536F, 329 0.00020351382F, 0.00021673929F, 0.00023082423F, 0.00024582449F, 330 0.00026179955F, 0.00027881276F, 0.00029693158F, 0.00031622787F, 331 0.00033677814F, 0.00035866388F, 0.00038197188F, 0.00040679456F, 332 0.00043323036F, 0.00046138411F, 0.00049136745F, 0.00052329927F, 333 0.00055730621F, 0.00059352311F, 0.00063209358F, 0.00067317058F, 334 0.00071691700F, 0.00076350630F, 0.00081312324F, 0.00086596457F, 335 0.00092223983F, 0.00098217216F, 0.0010459992F, 0.0011139742F, 336 0.0011863665F, 0.0012634633F, 0.0013455702F, 0.0014330129F, 337 0.0015261382F, 0.0016253153F, 0.0017309374F, 0.0018434235F, 338 0.0019632195F, 0.0020908006F, 0.0022266726F, 0.0023713743F, 339 0.0025254795F, 0.0026895994F, 0.0028643847F, 0.0030505286F, 340 0.0032487691F, 0.0034598925F, 0.0036847358F, 0.0039241906F, 341 0.0041792066F, 0.0044507950F, 0.0047400328F, 0.0050480668F, 342 0.0053761186F, 0.0057254891F, 0.0060975636F, 0.0064938176F, 343 0.0069158225F, 0.0073652516F, 0.0078438871F, 0.0083536271F, 344 0.0088964928F, 0.009474637F, 0.010090352F, 0.010746080F, 345 0.011444421F, 0.012188144F, 0.012980198F, 0.013823725F, 346 0.014722068F, 0.015678791F, 0.016697687F, 0.017782797F, 347 0.018938423F, 0.020169149F, 0.021479854F, 0.022875735F, 348 0.024362330F, 0.025945531F, 0.027631618F, 0.029427276F, 349 0.031339626F, 0.033376252F, 0.035545228F, 0.037855157F, 350 0.040315199F, 0.042935108F, 0.045725273F, 0.048696758F, 351 0.051861348F, 0.055231591F, 0.058820850F, 0.062643361F, 352 0.066714279F, 0.071049749F, 0.075666962F, 0.080584227F, 353 0.085821044F, 0.091398179F, 0.097337747F, 0.10366330F, 354 0.11039993F, 0.11757434F, 0.12521498F, 0.13335215F, 355 0.14201813F, 0.15124727F, 0.16107617F, 0.17154380F, 356 0.18269168F, 0.19456402F, 0.20720788F, 0.22067342F, 357 0.23501402F, 0.25028656F, 0.26655159F, 0.28387361F, 358 0.30232132F, 0.32196786F, 0.34289114F, 0.36517414F, 359 0.38890521F, 0.41417847F, 0.44109412F, 0.46975890F, 360 0.50028648F, 0.53279791F, 0.56742212F, 0.60429640F, 361 0.64356699F, 0.68538959F, 0.72993007F, 0.77736504F, 362 0.82788260F, 0.88168307F, 0.9389798F, 1.F, 363 }; 364 365 static void render_line(int n, int x0,int x1,int y0,int y1,float *d){ 366 int dy=y1-y0; 367 int adx=x1-x0; 368 int ady=abs(dy); 369 int base=dy/adx; 370 int sy=(dy<0?base-1:base+1); 371 int x=x0; 372 int y=y0; 373 int err=0; 374 375 ady-=abs(base*adx); 376 377 if(n>x1)n=x1; 378 379 if(x<n) 380 d[x]*=FLOOR1_fromdB_LOOKUP[y]; 381 382 while(++x<n){ 383 err=err+ady; 384 if(err>=adx){ 385 err-=adx; 386 y+=sy; 387 }else{ 388 y+=base; 389 } 390 d[x]*=FLOOR1_fromdB_LOOKUP[y]; 391 } 392 } 393 394 static void render_line0(int n, int x0,int x1,int y0,int y1,int *d){ 395 int dy=y1-y0; 396 int adx=x1-x0; 397 int ady=abs(dy); 398 int base=dy/adx; 399 int sy=(dy<0?base-1:base+1); 400 int x=x0; 401 int y=y0; 402 int err=0; 403 404 ady-=abs(base*adx); 405 406 if(n>x1)n=x1; 407 408 if(x<n) 409 d[x]=y; 410 411 while(++x<n){ 412 err=err+ady; 413 if(err>=adx){ 414 err-=adx; 415 y+=sy; 416 }else{ 417 y+=base; 418 } 419 d[x]=y; 420 } 421 } 422 423 /* the floor has already been filtered to only include relevant sections */ 424 static int accumulate_fit(const float *flr,const float *mdct, 425 int x0, int x1,lsfit_acc *a, 426 int n,vorbis_info_floor1 *info){ 427 long i; 428 429 int xa=0,ya=0,x2a=0,y2a=0,xya=0,na=0, xb=0,yb=0,x2b=0,y2b=0,xyb=0,nb=0; 430 431 memset(a,0,sizeof(*a)); 432 a->x0=x0; 433 a->x1=x1; 434 if(x1>=n)x1=n-1; 435 436 for(i=x0;i<=x1;i++){ 437 int quantized=vorbis_dBquant(flr+i); 438 if(quantized){ 439 if(mdct[i]+info->twofitatten>=flr[i]){ 440 xa += i; 441 ya += quantized; 442 x2a += i*i; 443 y2a += quantized*quantized; 444 xya += i*quantized; 445 na++; 446 }else{ 447 xb += i; 448 yb += quantized; 449 x2b += i*i; 450 y2b += quantized*quantized; 451 xyb += i*quantized; 452 nb++; 453 } 454 } 455 } 456 457 a->xa=xa; 458 a->ya=ya; 459 a->x2a=x2a; 460 a->y2a=y2a; 461 a->xya=xya; 462 a->an=na; 463 464 a->xb=xb; 465 a->yb=yb; 466 a->x2b=x2b; 467 a->y2b=y2b; 468 a->xyb=xyb; 469 a->bn=nb; 470 471 return(na); 472 } 473 474 static int fit_line(lsfit_acc *a,int fits,int *y0,int *y1, 475 vorbis_info_floor1 *info){ 476 double xb=0,yb=0,x2b=0,y2b=0,xyb=0,bn=0; 477 int i; 478 int x0=a[0].x0; 479 int x1=a[fits-1].x1; 480 481 for(i=0;i<fits;i++){ 482 double weight = (a[i].bn+a[i].an)*info->twofitweight/(a[i].an+1)+1.; 483 484 xb+=a[i].xb + a[i].xa * weight; 485 yb+=a[i].yb + a[i].ya * weight; 486 x2b+=a[i].x2b + a[i].x2a * weight; 487 y2b+=a[i].y2b + a[i].y2a * weight; 488 xyb+=a[i].xyb + a[i].xya * weight; 489 bn+=a[i].bn + a[i].an * weight; 490 } 491 492 if(*y0>=0){ 493 xb+= x0; 494 yb+= *y0; 495 x2b+= x0 * x0; 496 y2b+= *y0 * *y0; 497 xyb+= *y0 * x0; 498 bn++; 499 } 500 501 if(*y1>=0){ 502 xb+= x1; 503 yb+= *y1; 504 x2b+= x1 * x1; 505 y2b+= *y1 * *y1; 506 xyb+= *y1 * x1; 507 bn++; 508 } 509 510 { 511 double denom=(bn*x2b-xb*xb); 512 513 if(denom>0.){ 514 double a=(yb*x2b-xyb*xb)/denom; 515 double b=(bn*xyb-xb*yb)/denom; 516 *y0=rint(a+b*x0); 517 *y1=rint(a+b*x1); 518 519 /* limit to our range! */ 520 if(*y0>1023)*y0=1023; 521 if(*y1>1023)*y1=1023; 522 if(*y0<0)*y0=0; 523 if(*y1<0)*y1=0; 524 525 return 0; 526 }else{ 527 *y0=0; 528 *y1=0; 529 return 1; 530 } 531 } 532 } 533 534 static int inspect_error(int x0,int x1,int y0,int y1,const float *mask, 535 const float *mdct, 536 vorbis_info_floor1 *info){ 537 int dy=y1-y0; 538 int adx=x1-x0; 539 int ady=abs(dy); 540 int base=dy/adx; 541 int sy=(dy<0?base-1:base+1); 542 int x=x0; 543 int y=y0; 544 int err=0; 545 int val=vorbis_dBquant(mask+x); 546 int mse=0; 547 int n=0; 548 549 ady-=abs(base*adx); 550 551 mse=(y-val); 552 mse*=mse; 553 n++; 554 if(mdct[x]+info->twofitatten>=mask[x]){ 555 if(y+info->maxover<val)return(1); 556 if(y-info->maxunder>val)return(1); 557 } 558 559 while(++x<x1){ 560 err=err+ady; 561 if(err>=adx){ 562 err-=adx; 563 y+=sy; 564 }else{ 565 y+=base; 566 } 567 568 val=vorbis_dBquant(mask+x); 569 mse+=((y-val)*(y-val)); 570 n++; 571 if(mdct[x]+info->twofitatten>=mask[x]){ 572 if(val){ 573 if(y+info->maxover<val)return(1); 574 if(y-info->maxunder>val)return(1); 575 } 576 } 577 } 578 579 if(info->maxover*info->maxover/n>info->maxerr)return(0); 580 if(info->maxunder*info->maxunder/n>info->maxerr)return(0); 581 if(mse/n>info->maxerr)return(1); 582 return(0); 583 } 584 585 static int post_Y(int *A,int *B,int pos){ 586 if(A[pos]<0) 587 return B[pos]; 588 if(B[pos]<0) 589 return A[pos]; 590 591 return (A[pos]+B[pos])>>1; 592 } 593 594 int *floor1_fit(vorbis_block *vb,vorbis_look_floor1 *look, 595 const float *logmdct, /* in */ 596 const float *logmask){ 597 long i,j; 598 vorbis_info_floor1 *info=look->vi; 599 long n=look->n; 600 long posts=look->posts; 601 long nonzero=0; 602 lsfit_acc fits[VIF_POSIT+1]; 603 int fit_valueA[VIF_POSIT+2]; /* index by range list position */ 604 int fit_valueB[VIF_POSIT+2]; /* index by range list position */ 605 606 int loneighbor[VIF_POSIT+2]; /* sorted index of range list position (+2) */ 607 int hineighbor[VIF_POSIT+2]; 608 int *output=NULL; 609 int memo[VIF_POSIT+2]; 610 611 for(i=0;i<posts;i++)fit_valueA[i]=-200; /* mark all unused */ 612 for(i=0;i<posts;i++)fit_valueB[i]=-200; /* mark all unused */ 613 for(i=0;i<posts;i++)loneighbor[i]=0; /* 0 for the implicit 0 post */ 614 for(i=0;i<posts;i++)hineighbor[i]=1; /* 1 for the implicit post at n */ 615 for(i=0;i<posts;i++)memo[i]=-1; /* no neighbor yet */ 616 617 /* quantize the relevant floor points and collect them into line fit 618 structures (one per minimal division) at the same time */ 619 if(posts==0){ 620 nonzero+=accumulate_fit(logmask,logmdct,0,n,fits,n,info); 621 }else{ 622 for(i=0;i<posts-1;i++) 623 nonzero+=accumulate_fit(logmask,logmdct,look->sorted_index[i], 624 look->sorted_index[i+1],fits+i, 625 n,info); 626 } 627 628 if(nonzero){ 629 /* start by fitting the implicit base case.... */ 630 int y0=-200; 631 int y1=-200; 632 fit_line(fits,posts-1,&y0,&y1,info); 633 634 fit_valueA[0]=y0; 635 fit_valueB[0]=y0; 636 fit_valueB[1]=y1; 637 fit_valueA[1]=y1; 638 639 /* Non degenerate case */ 640 /* start progressive splitting. This is a greedy, non-optimal 641 algorithm, but simple and close enough to the best 642 answer. */ 643 for(i=2;i<posts;i++){ 644 int sortpos=look->reverse_index[i]; 645 int ln=loneighbor[sortpos]; 646 int hn=hineighbor[sortpos]; 647 648 /* eliminate repeat searches of a particular range with a memo */ 649 if(memo[ln]!=hn){ 650 /* haven't performed this error search yet */ 651 int lsortpos=look->reverse_index[ln]; 652 int hsortpos=look->reverse_index[hn]; 653 memo[ln]=hn; 654 655 { 656 /* A note: we want to bound/minimize *local*, not global, error */ 657 int lx=info->postlist[ln]; 658 int hx=info->postlist[hn]; 659 int ly=post_Y(fit_valueA,fit_valueB,ln); 660 int hy=post_Y(fit_valueA,fit_valueB,hn); 661 662 if(ly==-1 || hy==-1){ 663 exit(1); 664 } 665 666 if(inspect_error(lx,hx,ly,hy,logmask,logmdct,info)){ 667 /* outside error bounds/begin search area. Split it. */ 668 int ly0=-200; 669 int ly1=-200; 670 int hy0=-200; 671 int hy1=-200; 672 int ret0=fit_line(fits+lsortpos,sortpos-lsortpos,&ly0,&ly1,info); 673 int ret1=fit_line(fits+sortpos,hsortpos-sortpos,&hy0,&hy1,info); 674 675 if(ret0){ 676 ly0=ly; 677 ly1=hy0; 678 } 679 if(ret1){ 680 hy0=ly1; 681 hy1=hy; 682 } 683 684 if(ret0 && ret1){ 685 fit_valueA[i]=-200; 686 fit_valueB[i]=-200; 687 }else{ 688 /* store new edge values */ 689 fit_valueB[ln]=ly0; 690 if(ln==0)fit_valueA[ln]=ly0; 691 fit_valueA[i]=ly1; 692 fit_valueB[i]=hy0; 693 fit_valueA[hn]=hy1; 694 if(hn==1)fit_valueB[hn]=hy1; 695 696 if(ly1>=0 || hy0>=0){ 697 /* store new neighbor values */ 698 for(j=sortpos-1;j>=0;j--) 699 if(hineighbor[j]==hn) 700 hineighbor[j]=i; 701 else 702 break; 703 for(j=sortpos+1;j<posts;j++) 704 if(loneighbor[j]==ln) 705 loneighbor[j]=i; 706 else 707 break; 708 } 709 } 710 }else{ 711 fit_valueA[i]=-200; 712 fit_valueB[i]=-200; 713 } 714 } 715 } 716 } 717 718 output=_vorbis_block_alloc(vb,sizeof(*output)*posts); 719 720 output[0]=post_Y(fit_valueA,fit_valueB,0); 721 output[1]=post_Y(fit_valueA,fit_valueB,1); 722 723 /* fill in posts marked as not using a fit; we will zero 724 back out to 'unused' when encoding them so long as curve 725 interpolation doesn't force them into use */ 726 for(i=2;i<posts;i++){ 727 int ln=look->loneighbor[i-2]; 728 int hn=look->hineighbor[i-2]; 729 int x0=info->postlist[ln]; 730 int x1=info->postlist[hn]; 731 int y0=output[ln]; 732 int y1=output[hn]; 733 734 int predicted=render_point(x0,x1,y0,y1,info->postlist[i]); 735 int vx=post_Y(fit_valueA,fit_valueB,i); 736 737 if(vx>=0 && predicted!=vx){ 738 output[i]=vx; 739 }else{ 740 output[i]= predicted|0x8000; 741 } 742 } 743 } 744 745 return(output); 746 747 } 748 749 int *floor1_interpolate_fit(vorbis_block *vb,vorbis_look_floor1 *look, 750 int *A,int *B, 751 int del){ 752 753 long i; 754 long posts=look->posts; 755 int *output=NULL; 756 757 if(A && B){ 758 output=_vorbis_block_alloc(vb,sizeof(*output)*posts); 759 760 /* overly simpleminded--- look again post 1.2 */ 761 for(i=0;i<posts;i++){ 762 output[i]=((65536-del)*(A[i]&0x7fff)+del*(B[i]&0x7fff)+32768)>>16; 763 if(A[i]&0x8000 && B[i]&0x8000)output[i]|=0x8000; 764 } 765 } 766 767 return(output); 768 } 769 770 771 int floor1_encode(oggpack_buffer *opb,vorbis_block *vb, 772 vorbis_look_floor1 *look, 773 int *post,int *ilogmask){ 774 775 long i,j; 776 vorbis_info_floor1 *info=look->vi; 777 long posts=look->posts; 778 codec_setup_info *ci=vb->vd->vi->codec_setup; 779 int out[VIF_POSIT+2]; 780 static_codebook **sbooks=ci->book_param; 781 codebook *books=ci->fullbooks; 782 783 /* quantize values to multiplier spec */ 784 if(post){ 785 for(i=0;i<posts;i++){ 786 int val=post[i]&0x7fff; 787 switch(info->mult){ 788 case 1: /* 1024 -> 256 */ 789 val>>=2; 790 break; 791 case 2: /* 1024 -> 128 */ 792 val>>=3; 793 break; 794 case 3: /* 1024 -> 86 */ 795 val/=12; 796 break; 797 case 4: /* 1024 -> 64 */ 798 val>>=4; 799 break; 800 } 801 post[i]=val | (post[i]&0x8000); 802 } 803 804 out[0]=post[0]; 805 out[1]=post[1]; 806 807 /* find prediction values for each post and subtract them */ 808 for(i=2;i<posts;i++){ 809 int ln=look->loneighbor[i-2]; 810 int hn=look->hineighbor[i-2]; 811 int x0=info->postlist[ln]; 812 int x1=info->postlist[hn]; 813 int y0=post[ln]; 814 int y1=post[hn]; 815 816 int predicted=render_point(x0,x1,y0,y1,info->postlist[i]); 817 818 if((post[i]&0x8000) || (predicted==post[i])){ 819 post[i]=predicted|0x8000; /* in case there was roundoff jitter 820 in interpolation */ 821 out[i]=0; 822 }else{ 823 int headroom=(look->quant_q-predicted<predicted? 824 look->quant_q-predicted:predicted); 825 826 int val=post[i]-predicted; 827 828 /* at this point the 'deviation' value is in the range +/- max 829 range, but the real, unique range can always be mapped to 830 only [0-maxrange). So we want to wrap the deviation into 831 this limited range, but do it in the way that least screws 832 an essentially gaussian probability distribution. */ 833 834 if(val<0) 835 if(val<-headroom) 836 val=headroom-val-1; 837 else 838 val=-1-(val<<1); 839 else 840 if(val>=headroom) 841 val= val+headroom; 842 else 843 val<<=1; 844 845 out[i]=val; 846 post[ln]&=0x7fff; 847 post[hn]&=0x7fff; 848 } 849 } 850 851 /* we have everything we need. pack it out */ 852 /* mark nontrivial floor */ 853 oggpack_write(opb,1,1); 854 855 /* beginning/end post */ 856 look->frames++; 857 look->postbits+=ilog(look->quant_q-1)*2; 858 oggpack_write(opb,out[0],ilog(look->quant_q-1)); 859 oggpack_write(opb,out[1],ilog(look->quant_q-1)); 860 861 862 /* partition by partition */ 863 for(i=0,j=2;i<info->partitions;i++){ 864 int class=info->partitionclass[i]; 865 int cdim=info->class_dim[class]; 866 int csubbits=info->class_subs[class]; 867 int csub=1<<csubbits; 868 int bookas[8]={0,0,0,0,0,0,0,0}; 869 int cval=0; 870 int cshift=0; 871 int k,l; 872 873 /* generate the partition's first stage cascade value */ 874 if(csubbits){ 875 int maxval[8]; 876 for(k=0;k<csub;k++){ 877 int booknum=info->class_subbook[class][k]; 878 if(booknum<0){ 879 maxval[k]=1; 880 }else{ 881 maxval[k]=sbooks[info->class_subbook[class][k]]->entries; 882 } 883 } 884 for(k=0;k<cdim;k++){ 885 for(l=0;l<csub;l++){ 886 int val=out[j+k]; 887 if(val<maxval[l]){ 888 bookas[k]=l; 889 break; 890 } 891 } 892 cval|= bookas[k]<<cshift; 893 cshift+=csubbits; 894 } 895 /* write it */ 896 look->phrasebits+= 897 vorbis_book_encode(books+info->class_book[class],cval,opb); 898 899 #ifdef TRAIN_FLOOR1 900 { 901 FILE *of; 902 char buffer[80]; 903 sprintf(buffer,"line_%dx%ld_class%d.vqd", 904 vb->pcmend/2,posts-2,class); 905 of=fopen(buffer,"a"); 906 fprintf(of,"%d\n",cval); 907 fclose(of); 908 } 909 #endif 910 } 911 912 /* write post values */ 913 for(k=0;k<cdim;k++){ 914 int book=info->class_subbook[class][bookas[k]]; 915 if(book>=0){ 916 /* hack to allow training with 'bad' books */ 917 if(out[j+k]<(books+book)->entries) 918 look->postbits+=vorbis_book_encode(books+book, 919 out[j+k],opb); 920 /*else 921 fprintf(stderr,"+!");*/ 922 923 #ifdef TRAIN_FLOOR1 924 { 925 FILE *of; 926 char buffer[80]; 927 sprintf(buffer,"line_%dx%ld_%dsub%d.vqd", 928 vb->pcmend/2,posts-2,class,bookas[k]); 929 of=fopen(buffer,"a"); 930 fprintf(of,"%d\n",out[j+k]); 931 fclose(of); 932 } 933 #endif 934 } 935 } 936 j+=cdim; 937 } 938 939 { 940 /* generate quantized floor equivalent to what we'd unpack in decode */ 941 /* render the lines */ 942 int hx=0; 943 int lx=0; 944 int ly=post[0]*info->mult; 945 int n=ci->blocksizes[vb->W]/2; 946 947 for(j=1;j<look->posts;j++){ 948 int current=look->forward_index[j]; 949 int hy=post[current]&0x7fff; 950 if(hy==post[current]){ 951 952 hy*=info->mult; 953 hx=info->postlist[current]; 954 955 render_line0(n,lx,hx,ly,hy,ilogmask); 956 957 lx=hx; 958 ly=hy; 959 } 960 } 961 for(j=hx;j<vb->pcmend/2;j++)ilogmask[j]=ly; /* be certain */ 962 return(1); 963 } 964 }else{ 965 oggpack_write(opb,0,1); 966 memset(ilogmask,0,vb->pcmend/2*sizeof(*ilogmask)); 967 return(0); 968 } 969 } 970 971 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){ 972 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in; 973 vorbis_info_floor1 *info=look->vi; 974 codec_setup_info *ci=vb->vd->vi->codec_setup; 975 976 int i,j,k; 977 codebook *books=ci->fullbooks; 978 979 /* unpack wrapped/predicted values from stream */ 980 if(oggpack_read(&vb->opb,1)==1){ 981 int *fit_value=_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value)); 982 983 fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1)); 984 fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1)); 985 986 /* partition by partition */ 987 for(i=0,j=2;i<info->partitions;i++){ 988 int class=info->partitionclass[i]; 989 int cdim=info->class_dim[class]; 990 int csubbits=info->class_subs[class]; 991 int csub=1<<csubbits; 992 int cval=0; 993 994 /* decode the partition's first stage cascade value */ 995 if(csubbits){ 996 cval=vorbis_book_decode(books+info->class_book[class],&vb->opb); 997 998 if(cval==-1)goto eop; 999 } 1000 1001 for(k=0;k<cdim;k++){ 1002 int book=info->class_subbook[class][cval&(csub-1)]; 1003 cval>>=csubbits; 1004 if(book>=0){ 1005 if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1) 1006 goto eop; 1007 }else{ 1008 fit_value[j+k]=0; 1009 } 1010 } 1011 j+=cdim; 1012 } 1013 1014 /* unwrap positive values and reconsitute via linear interpolation */ 1015 for(i=2;i<look->posts;i++){ 1016 int predicted=render_point(info->postlist[look->loneighbor[i-2]], 1017 info->postlist[look->hineighbor[i-2]], 1018 fit_value[look->loneighbor[i-2]], 1019 fit_value[look->hineighbor[i-2]], 1020 info->postlist[i]); 1021 int hiroom=look->quant_q-predicted; 1022 int loroom=predicted; 1023 int room=(hiroom<loroom?hiroom:loroom)<<1; 1024 int val=fit_value[i]; 1025 1026 if(val){ 1027 if(val>=room){ 1028 if(hiroom>loroom){ 1029 val = val-loroom; 1030 }else{ 1031 val = -1-(val-hiroom); 1032 } 1033 }else{ 1034 if(val&1){ 1035 val= -((val+1)>>1); 1036 }else{ 1037 val>>=1; 1038 } 1039 } 1040 1041 fit_value[i]=(val+predicted)&0x7fff; 1042 fit_value[look->loneighbor[i-2]]&=0x7fff; 1043 fit_value[look->hineighbor[i-2]]&=0x7fff; 1044 1045 }else{ 1046 fit_value[i]=predicted|0x8000; 1047 } 1048 1049 } 1050 1051 return(fit_value); 1052 } 1053 eop: 1054 return(NULL); 1055 } 1056 1057 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo, 1058 float *out){ 1059 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in; 1060 vorbis_info_floor1 *info=look->vi; 1061 1062 codec_setup_info *ci=vb->vd->vi->codec_setup; 1063 int n=ci->blocksizes[vb->W]/2; 1064 int j; 1065 1066 if(memo){ 1067 /* render the lines */ 1068 int *fit_value=(int *)memo; 1069 int hx=0; 1070 int lx=0; 1071 int ly=fit_value[0]*info->mult; 1072 /* guard lookup against out-of-range values */ 1073 ly=(ly<0?0:ly>255?255:ly); 1074 1075 for(j=1;j<look->posts;j++){ 1076 int current=look->forward_index[j]; 1077 int hy=fit_value[current]&0x7fff; 1078 if(hy==fit_value[current]){ 1079 1080 hx=info->postlist[current]; 1081 hy*=info->mult; 1082 /* guard lookup against out-of-range values */ 1083 hy=(hy<0?0:hy>255?255:hy); 1084 1085 render_line(n,lx,hx,ly,hy,out); 1086 1087 lx=hx; 1088 ly=hy; 1089 } 1090 } 1091 for(j=hx;j<n;j++)out[j]*=FLOOR1_fromdB_LOOKUP[ly]; /* be certain */ 1092 return(1); 1093 } 1094 memset(out,0,sizeof(*out)*n); 1095 return(0); 1096 } 1097 1098 /* export hooks */ 1099 const vorbis_func_floor floor1_exportbundle={ 1100 &floor1_pack,&floor1_unpack,&floor1_look,&floor1_free_info, 1101 &floor1_free_look,&floor1_inverse1,&floor1_inverse2 1102 }; 1103