examples/sfexamples/oggvorbiscodec/src/libvorbis/lib/floor1.c

00001 /********************************************************************
00002  *                                                                  *
00003  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
00004  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
00005  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
00006  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
00007  *                                                                  *
00008  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2002             *
00009  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
00010  *                                                                  *
00011  ********************************************************************
00012 
00013  function: floor backend 1 implementation
00014  last mod: $Id: floor1.c 7187 2004-07-20 07:24:27Z xiphmont $
00015 
00016  ********************************************************************/
00017 
00018 #include <stdlib.h>
00019 #include <string.h>
00020 #include <math.h>
00021 #include "ogg/ogg.h"
00022 #include "vorbis/codec.h"
00023 #include "codec_internal.h"
00024 #include "registry.h"
00025 #include "codebook.h"
00026 #include "misc.h"
00027 #include "scales.h"
00028 
00029 #include <stdio.h>
00030 
00031 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
00032 
00033 typedef struct {
00034   int sorted_index[VIF_POSIT+2];
00035   int forward_index[VIF_POSIT+2];
00036   int reverse_index[VIF_POSIT+2];
00037   
00038   int hineighbor[VIF_POSIT];
00039   int loneighbor[VIF_POSIT];
00040   int posts;
00041 
00042   int n;
00043   int quant_q;
00044   vorbis_info_floor1 *vi;
00045 
00046   long phrasebits;
00047   long postbits;
00048   long frames;
00049 } vorbis_look_floor1;
00050 
00051 typedef struct lsfit_acc{
00052   long x0;
00053   long x1;
00054 
00055   long xa;
00056   long ya;
00057   long x2a;
00058   long y2a;
00059   long xya; 
00060   long an;
00061 } lsfit_acc;
00062 
00063 /***********************************************/
00064  
00065 static void floor1_free_info(vorbis_info_floor *i){
00066   vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
00067   if(info){
00068     memset(info,0,sizeof(*info));
00069     _ogg_free(info);
00070   }
00071 }
00072 
00073 static void floor1_free_look(vorbis_look_floor *i){
00074   vorbis_look_floor1 *look=(vorbis_look_floor1 *)i;
00075   if(look){
00076     /*fprintf(stderr,"floor 1 bit usage %f:%f (%f total)\n",
00077             (float)look->phrasebits/look->frames,
00078             (float)look->postbits/look->frames,
00079             (float)(look->postbits+look->phrasebits)/look->frames);*/
00080 
00081     memset(look,0,sizeof(*look));
00082     _ogg_free(look);
00083   }
00084 }
00085 
00086 static int ilog(unsigned int v){
00087   int ret=0;
00088   while(v){
00089     ret++;
00090     v>>=1;
00091   }
00092   return(ret);
00093 }
00094 
00095 static int ilog2(unsigned int v){
00096   int ret=0;
00097   if(v)--v;
00098   while(v){
00099     ret++;
00100     v>>=1;
00101   }
00102   return(ret);
00103 }
00104 
00105 static void floor1_pack (vorbis_info_floor *i,oggpack_buffer *opb){
00106   vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
00107   int j,k;
00108   int count=0;
00109   int rangebits;
00110   int maxposit=info->postlist[1];
00111   int maxclass=-1;
00112 
00113   /* save out partitions */
00114   oggpack_write(opb,info->partitions,5); /* only 0 to 31 legal */
00115   for(j=0;j<info->partitions;j++){
00116     oggpack_write(opb,info->partitionclass[j],4); /* only 0 to 15 legal */
00117     if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
00118   }
00119 
00120   /* save out partition classes */
00121   for(j=0;j<maxclass+1;j++){
00122     oggpack_write(opb,info->class_dim[j]-1,3); /* 1 to 8 */
00123     oggpack_write(opb,info->class_subs[j],2); /* 0 to 3 */
00124     if(info->class_subs[j])oggpack_write(opb,info->class_book[j],8);
00125     for(k=0;k<(1<<info->class_subs[j]);k++)
00126       oggpack_write(opb,info->class_subbook[j][k]+1,8);
00127   }
00128 
00129   /* save out the post list */
00130   oggpack_write(opb,info->mult-1,2);     /* only 1,2,3,4 legal now */ 
00131   oggpack_write(opb,ilog2(maxposit),4);
00132   rangebits=ilog2(maxposit);
00133 
00134   for(j=0,k=0;j<info->partitions;j++){
00135     count+=info->class_dim[info->partitionclass[j]]; 
00136     for(;k<count;k++)
00137       oggpack_write(opb,info->postlist[k+2],rangebits);
00138   }
00139 }
00140 
00141 
00142 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){
00143   codec_setup_info     *ci=(codec_setup_info*)vi->codec_setup;
00144   int j,k,count=0,maxclass=-1,rangebits;
00145 
00146   vorbis_info_floor1 *info=(vorbis_info_floor1*)_ogg_calloc(1,sizeof(*info));
00147   /* read partitions */
00148   info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
00149   for(j=0;j<info->partitions;j++){
00150     info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
00151     if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
00152   }
00153 
00154   /* read partition classes */
00155   for(j=0;j<maxclass+1;j++){
00156     info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */
00157     info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */
00158     if(info->class_subs[j]<0)
00159       goto err_out;
00160     if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8);
00161     if(info->class_book[j]<0 || info->class_book[j]>=ci->books)
00162       goto err_out;
00163     for(k=0;k<(1<<info->class_subs[j]);k++){
00164       info->class_subbook[j][k]=oggpack_read(opb,8)-1;
00165       if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books)
00166         goto err_out;
00167     }
00168   }
00169 
00170   /* read the post list */
00171   info->mult=oggpack_read(opb,2)+1;     /* only 1,2,3,4 legal now */ 
00172   rangebits=oggpack_read(opb,4);
00173 
00174   for(j=0,k=0;j<info->partitions;j++){
00175     count+=info->class_dim[info->partitionclass[j]]; 
00176     for(;k<count;k++){
00177       int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
00178       if(t<0 || t>=(1<<rangebits))
00179         goto err_out;
00180     }
00181   }
00182   info->postlist[0]=0;
00183   info->postlist[1]=1<<rangebits;
00184 
00185   return(info);
00186   
00187  err_out:
00188   floor1_free_info(info);
00189   return(NULL);
00190 }
00191 
00192 static int icomp(const void *a,const void *b){
00193   return(**(int **)a-**(int **)b);
00194 }
00195 
00196 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,
00197                                       vorbis_info_floor *in){
00198 
00199   int *sortpointer[VIF_POSIT+2];
00200   vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
00201   vorbis_look_floor1 *look=(vorbis_look_floor1*)_ogg_calloc(1,sizeof(*look));
00202   int i,j,n=0;
00203 
00204   look->vi=info;
00205   look->n=info->postlist[1];
00206   vd = vd;
00207   /* we drop each position value in-between already decoded values,
00208      and use linear interpolation to predict each new value past the
00209      edges.  The positions are read in the order of the position
00210      list... we precompute the bounding positions in the lookup.  Of
00211      course, the neighbors can change (if a position is declined), but
00212      this is an initial mapping */
00213 
00214   for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
00215   n+=2;
00216   look->posts=n;
00217 
00218   /* also store a sorted position index */
00219   for(i=0;i<n;i++)sortpointer[i]=info->postlist+i;
00220   qsort(sortpointer,n,sizeof(*sortpointer),icomp);
00221 
00222   /* points from sort order back to range number */
00223   for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist;
00224   /* points from range order to sorted position */
00225   for(i=0;i<n;i++)look->reverse_index[look->forward_index[i]]=i;
00226   /* we actually need the post values too */
00227   for(i=0;i<n;i++)look->sorted_index[i]=info->postlist[look->forward_index[i]];
00228   
00229   /* quantize values to multiplier spec */
00230   switch(info->mult){
00231   case 1: /* 1024 -> 256 */
00232     look->quant_q=256;
00233     break;
00234   case 2: /* 1024 -> 128 */
00235     look->quant_q=128;
00236     break;
00237   case 3: /* 1024 -> 86 */
00238     look->quant_q=86;
00239     break;
00240   case 4: /* 1024 -> 64 */
00241     look->quant_q=64;
00242     break;
00243   }
00244 
00245   /* discover our neighbors for decode where we don't use fit flags
00246      (that would push the neighbors outward) */
00247   for(i=0;i<n-2;i++){
00248     int lo=0;
00249     int hi=1;
00250     int lx=0;
00251     int hx=look->n;
00252     int currentx=info->postlist[i+2];
00253     for(j=0;j<i+2;j++){
00254       int x=info->postlist[j];
00255       if(x>lx && x<currentx){
00256         lo=j;
00257         lx=x;
00258       }
00259       if(x<hx && x>currentx){
00260         hi=j;
00261         hx=x;
00262       }
00263     }
00264     look->loneighbor[i]=lo;
00265     look->hineighbor[i]=hi;
00266   }
00267 
00268   return(look);
00269 }
00270 
00271 static int render_point(int x0,int x1,int y0,int y1,int x){
00272   y0&=0x7fff; /* mask off flag */
00273   y1&=0x7fff;
00274     
00275   {
00276     int dy=y1-y0;
00277     int adx=x1-x0;
00278     int ady=abs(dy);
00279     int err=ady*(x-x0);
00280     
00281     int off=err/adx;
00282     if(dy<0)return(y0-off);
00283     return(y0+off);
00284   }
00285 }
00286 
00287 static int vorbis_dBquant(const float *x){
00288   int i= *x*7.3142857f+1023.5f;
00289   if(i>1023)return(1023);
00290   if(i<0)return(0);
00291   return i;
00292 }
00293 
00294 static float FLOOR1_fromdB_LOOKUP[256]={
00295   1.0649863e-07F, 1.1341951e-07F, 1.2079015e-07F, 1.2863978e-07F, 
00296   1.3699951e-07F, 1.4590251e-07F, 1.5538408e-07F, 1.6548181e-07F, 
00297   1.7623575e-07F, 1.8768855e-07F, 1.9988561e-07F, 2.128753e-07F, 
00298   2.2670913e-07F, 2.4144197e-07F, 2.5713223e-07F, 2.7384213e-07F, 
00299   2.9163793e-07F, 3.1059021e-07F, 3.3077411e-07F, 3.5226968e-07F, 
00300   3.7516214e-07F, 3.9954229e-07F, 4.2550680e-07F, 4.5315863e-07F, 
00301   4.8260743e-07F, 5.1396998e-07F, 5.4737065e-07F, 5.8294187e-07F, 
00302   6.2082472e-07F, 6.6116941e-07F, 7.0413592e-07F, 7.4989464e-07F, 
00303   7.9862701e-07F, 8.5052630e-07F, 9.0579828e-07F, 9.6466216e-07F, 
00304   1.0273513e-06F, 1.0941144e-06F, 1.1652161e-06F, 1.2409384e-06F, 
00305   1.3215816e-06F, 1.4074654e-06F, 1.4989305e-06F, 1.5963394e-06F, 
00306   1.7000785e-06F, 1.8105592e-06F, 1.9282195e-06F, 2.0535261e-06F, 
00307   2.1869758e-06F, 2.3290978e-06F, 2.4804557e-06F, 2.6416497e-06F, 
00308   2.8133190e-06F, 2.9961443e-06F, 3.1908506e-06F, 3.3982101e-06F, 
00309   3.6190449e-06F, 3.8542308e-06F, 4.1047004e-06F, 4.3714470e-06F, 
00310   4.6555282e-06F, 4.9580707e-06F, 5.2802740e-06F, 5.6234160e-06F, 
00311   5.9888572e-06F, 6.3780469e-06F, 6.7925283e-06F, 7.2339451e-06F, 
00312   7.7040476e-06F, 8.2047000e-06F, 8.7378876e-06F, 9.3057248e-06F, 
00313   9.9104632e-06F, 1.0554501e-05F, 1.1240392e-05F, 1.1970856e-05F, 
00314   1.2748789e-05F, 1.3577278e-05F, 1.4459606e-05F, 1.5399272e-05F, 
00315   1.6400004e-05F, 1.7465768e-05F, 1.8600792e-05F, 1.9809576e-05F, 
00316   2.1096914e-05F, 2.2467911e-05F, 2.3928002e-05F, 2.5482978e-05F, 
00317   2.7139006e-05F, 2.8902651e-05F, 3.0780908e-05F, 3.2781225e-05F, 
00318   3.4911534e-05F, 3.7180282e-05F, 3.9596466e-05F, 4.2169667e-05F, 
00319   4.4910090e-05F, 4.7828601e-05F, 5.0936773e-05F, 5.4246931e-05F, 
00320   5.7772202e-05F, 6.1526565e-05F, 6.5524908e-05F, 6.9783085e-05F, 
00321   7.4317983e-05F, 7.9147585e-05F, 8.4291040e-05F, 8.9768747e-05F, 
00322   9.5602426e-05F, 0.00010181521F, 0.00010843174F, 0.00011547824F, 
00323   0.00012298267F, 0.00013097477F, 0.00013948625F, 0.00014855085F, 
00324   0.00015820453F, 0.00016848555F, 0.00017943469F, 0.00019109536F, 
00325   0.00020351382F, 0.00021673929F, 0.00023082423F, 0.00024582449F, 
00326   0.00026179955F, 0.00027881276F, 0.00029693158F, 0.00031622787F, 
00327   0.00033677814F, 0.00035866388F, 0.00038197188F, 0.00040679456F, 
00328   0.00043323036F, 0.00046138411F, 0.00049136745F, 0.00052329927F, 
00329   0.00055730621F, 0.00059352311F, 0.00063209358F, 0.00067317058F, 
00330   0.00071691700F, 0.00076350630F, 0.00081312324F, 0.00086596457F, 
00331   0.00092223983F, 0.00098217216F, 0.0010459992F, 0.0011139742F, 
00332   0.0011863665F, 0.0012634633F, 0.0013455702F, 0.0014330129F, 
00333   0.0015261382F, 0.0016253153F, 0.0017309374F, 0.0018434235F, 
00334   0.0019632195F, 0.0020908006F, 0.0022266726F, 0.0023713743F, 
00335   0.0025254795F, 0.0026895994F, 0.0028643847F, 0.0030505286F, 
00336   0.0032487691F, 0.0034598925F, 0.0036847358F, 0.0039241906F, 
00337   0.0041792066F, 0.0044507950F, 0.0047400328F, 0.0050480668F, 
00338   0.0053761186F, 0.0057254891F, 0.0060975636F, 0.0064938176F, 
00339   0.0069158225F, 0.0073652516F, 0.0078438871F, 0.0083536271F, 
00340   0.0088964928F, 0.009474637F, 0.010090352F, 0.010746080F, 
00341   0.011444421F, 0.012188144F, 0.012980198F, 0.013823725F, 
00342   0.014722068F, 0.015678791F, 0.016697687F, 0.017782797F, 
00343   0.018938423F, 0.020169149F, 0.021479854F, 0.022875735F, 
00344   0.024362330F, 0.025945531F, 0.027631618F, 0.029427276F, 
00345   0.031339626F, 0.033376252F, 0.035545228F, 0.037855157F, 
00346   0.040315199F, 0.042935108F, 0.045725273F, 0.048696758F, 
00347   0.051861348F, 0.055231591F, 0.058820850F, 0.062643361F, 
00348   0.066714279F, 0.071049749F, 0.075666962F, 0.080584227F, 
00349   0.085821044F, 0.091398179F, 0.097337747F, 0.10366330F, 
00350   0.11039993F, 0.11757434F, 0.12521498F, 0.13335215F, 
00351   0.14201813F, 0.15124727F, 0.16107617F, 0.17154380F, 
00352   0.18269168F, 0.19456402F, 0.20720788F, 0.22067342F, 
00353   0.23501402F, 0.25028656F, 0.26655159F, 0.28387361F, 
00354   0.30232132F, 0.32196786F, 0.34289114F, 0.36517414F, 
00355   0.38890521F, 0.41417847F, 0.44109412F, 0.46975890F, 
00356   0.50028648F, 0.53279791F, 0.56742212F, 0.60429640F, 
00357   0.64356699F, 0.68538959F, 0.72993007F, 0.77736504F, 
00358   0.82788260F, 0.88168307F, 0.9389798F, 1.F, 
00359 };
00360 
00361 static void render_line(int x0,int x1,int y0,int y1,float *d){
00362   int dy=y1-y0;
00363   int adx=x1-x0;
00364   int ady=abs(dy);
00365   int base=dy/adx;
00366   int sy=(dy<0?base-1:base+1);
00367   int x=x0;
00368   int y=y0;
00369   int err=0;
00370 
00371   ady-=abs(base*adx);
00372 
00373   d[x]*=FLOOR1_fromdB_LOOKUP[y];
00374   while(++x<x1){
00375     err=err+ady;
00376     if(err>=adx){
00377       err-=adx;
00378       y+=sy;
00379     }else{
00380       y+=base;
00381     }
00382     d[x]*=FLOOR1_fromdB_LOOKUP[y];
00383   }
00384 }
00385 
00386 static void render_line0(int x0,int x1,int y0,int y1,int *d){
00387   int dy=y1-y0;
00388   int adx=x1-x0;
00389   int ady=abs(dy);
00390   int base=dy/adx;
00391   int sy=(dy<0?base-1:base+1);
00392   int x=x0;
00393   int y=y0;
00394   int err=0;
00395 
00396   ady-=abs(base*adx);
00397 
00398   d[x]=y;
00399   while(++x<x1){
00400     err=err+ady;
00401     if(err>=adx){
00402       err-=adx;
00403       y+=sy;
00404     }else{
00405       y+=base;
00406     }
00407     d[x]=y;
00408   }
00409 }
00410 
00411 /* the floor has already been filtered to only include relevant sections */
00412 static int accumulate_fit(const float *flr,const float *mdct,
00413                           int x0, int x1,lsfit_acc *a,
00414                           int n,vorbis_info_floor1 *info){
00415   long i;
00416   int quantized=vorbis_dBquant(flr+x0);
00417 
00418   long xa=0,ya=0,x2a=0,y2a=0,xya=0,na=0, xb=0,yb=0,x2b=0,y2b=0,xyb=0,nb=0;
00419 
00420   memset(a,0,sizeof(*a));
00421   a->x0=x0;
00422   a->x1=x1;
00423   if(x1>=n)x1=n-1;
00424 
00425   for(i=x0;i<=x1;i++){
00426     int quantized=vorbis_dBquant(flr+i);
00427     if(quantized){
00428       if(mdct[i]+info->twofitatten>=flr[i]){
00429         xa  += i;
00430         ya  += quantized;
00431         x2a += i*i;
00432         y2a += quantized*quantized;
00433         xya += i*quantized;
00434         na++;
00435       }else{
00436         xb  += i;
00437         yb  += quantized;
00438         x2b += i*i;
00439         y2b += quantized*quantized;
00440         xyb += i*quantized;
00441         nb++;
00442       }
00443     }
00444   }
00445 
00446   xb+=xa;
00447   yb+=ya;
00448   x2b+=x2a;
00449   y2b+=y2a;
00450   xyb+=xya;
00451   nb+=na;
00452 
00453   /* weight toward the actually used frequencies if we meet the threshhold */
00454   {
00455     int weight=nb*info->twofitweight/(na+1);
00456 
00457     a->xa=xa*weight+xb;
00458     a->ya=ya*weight+yb;
00459     a->x2a=x2a*weight+x2b;
00460     a->y2a=y2a*weight+y2b;
00461     a->xya=xya*weight+xyb;
00462     a->an=na*weight+nb;
00463   }
00464 
00465   return(na);
00466 }
00467 
00468 static void fit_line(lsfit_acc *a,int fits,int *y0,int *y1){
00469   long x=0,y=0,x2=0,y2=0,xy=0,an=0,i;
00470   long x0=a[0].x0;
00471   long x1=a[fits-1].x1;
00472 
00473   for(i=0;i<fits;i++){
00474     x+=a[i].xa;
00475     y+=a[i].ya;
00476     x2+=a[i].x2a;
00477     y2+=a[i].y2a;
00478     xy+=a[i].xya;
00479     an+=a[i].an;
00480   }
00481 
00482   if(*y0>=0){
00483     x+=   x0;
00484     y+=  *y0;
00485     x2+=  x0 *  x0;
00486     y2+= *y0 * *y0;
00487     xy+= *y0 *  x0;
00488     an++;
00489   }
00490 
00491   if(*y1>=0){
00492     x+=   x1;
00493     y+=  *y1;
00494     x2+=  x1 *  x1;
00495     y2+= *y1 * *y1;
00496     xy+= *y1 *  x1;
00497     an++;
00498   }
00499   
00500   if(an){
00501     /* need 64 bit multiplies, which C doesn't give portably as int */
00502     double fx=x;
00503     double fy=y;
00504     double fx2=x2;
00505     double fxy=xy;
00506     double denom=1./(an*fx2-fx*fx);
00507     double a=(fy*fx2-fxy*fx)*denom;
00508     double b=(an*fxy-fx*fy)*denom;
00509     *y0=rint(a+b*x0);
00510     *y1=rint(a+b*x1);
00511     
00512     /* limit to our range! */
00513     if(*y0>1023)*y0=1023;
00514     if(*y1>1023)*y1=1023;
00515     if(*y0<0)*y0=0;
00516     if(*y1<0)*y1=0;
00517     
00518   }else{
00519     *y0=0;
00520     *y1=0;
00521   }
00522 }
00523 
00524 /*static void fit_line_point(lsfit_acc *a,int fits,int *y0,int *y1){
00525   long y=0;
00526   int i;
00527 
00528   for(i=0;i<fits && y==0;i++)
00529     y+=a[i].ya;
00530   
00531   *y0=*y1=y;
00532   }*/
00533 
00534 static int inspect_error(int x0,int x1,int y0,int y1,const float *mask,
00535                          const float *mdct,
00536                          vorbis_info_floor1 *info){
00537   int dy=y1-y0;
00538   int adx=x1-x0;
00539   int ady=abs(dy);
00540   int base=dy/adx;
00541   int sy=(dy<0?base-1:base+1);
00542   int x=x0;
00543   int y=y0;
00544   int err=0;
00545   int val=vorbis_dBquant(mask+x);
00546   int mse=0;
00547   int n=0;
00548 
00549   ady-=abs(base*adx);
00550   
00551   mse=(y-val);
00552   mse*=mse;
00553   n++;
00554   if(mdct[x]+info->twofitatten>=mask[x]){
00555     if(y+info->maxover<val)return(1);
00556     if(y-info->maxunder>val)return(1);
00557   }
00558 
00559   while(++x<x1){
00560     err=err+ady;
00561     if(err>=adx){
00562       err-=adx;
00563       y+=sy;
00564     }else{
00565       y+=base;
00566     }
00567 
00568     val=vorbis_dBquant(mask+x);
00569     mse+=((y-val)*(y-val));
00570     n++;
00571     if(mdct[x]+info->twofitatten>=mask[x]){
00572       if(val){
00573         if(y+info->maxover<val)return(1);
00574         if(y-info->maxunder>val)return(1);
00575       }
00576     }
00577   }
00578   
00579   if(info->maxover*info->maxover/n>info->maxerr)return(0);
00580   if(info->maxunder*info->maxunder/n>info->maxerr)return(0);
00581   if(mse/n>info->maxerr)return(1);
00582   return(0);
00583 }
00584 
00585 static int post_Y(int *A,int *B,int pos){
00586   if(A[pos]<0)
00587     return B[pos];
00588   if(B[pos]<0)
00589     return A[pos];
00590 
00591   return (A[pos]+B[pos])>>1;
00592 }
00593 
00594 //static int seq=0;
00595 
00596 int *floor1_fit(vorbis_block *vb,vorbis_look_floor1 *look,
00597                           const float *logmdct,   /* in */
00598                           const float *logmask){
00599   long i,j;
00600   vorbis_info_floor1 *info=look->vi;
00601   long n=look->n;
00602   long posts=look->posts;
00603   long nonzero=0;
00604   lsfit_acc fits[VIF_POSIT+1];
00605   int fit_valueA[VIF_POSIT+2]; /* index by range list position */
00606   int fit_valueB[VIF_POSIT+2]; /* index by range list position */
00607 
00608   int loneighbor[VIF_POSIT+2]; /* sorted index of range list position (+2) */
00609   int hineighbor[VIF_POSIT+2]; 
00610   int *output=NULL;
00611   int memo[VIF_POSIT+2];
00612 
00613   for(i=0;i<posts;i++)fit_valueA[i]=-200; /* mark all unused */
00614   for(i=0;i<posts;i++)fit_valueB[i]=-200; /* mark all unused */
00615   for(i=0;i<posts;i++)loneighbor[i]=0; /* 0 for the implicit 0 post */
00616   for(i=0;i<posts;i++)hineighbor[i]=1; /* 1 for the implicit post at n */
00617   for(i=0;i<posts;i++)memo[i]=-1;      /* no neighbor yet */
00618 
00619   /* quantize the relevant floor points and collect them into line fit
00620      structures (one per minimal division) at the same time */
00621   if(posts==0){
00622     nonzero+=accumulate_fit(logmask,logmdct,0,n,fits,n,info);
00623   }else{
00624     for(i=0;i<posts-1;i++)
00625       nonzero+=accumulate_fit(logmask,logmdct,look->sorted_index[i],
00626                               look->sorted_index[i+1],fits+i,
00627                               n,info);
00628   }
00629   
00630   if(nonzero){
00631     /* start by fitting the implicit base case.... */
00632     int y0=-200;
00633     int y1=-200;
00634     fit_line(fits,posts-1,&y0,&y1);
00635 
00636     fit_valueA[0]=y0;
00637     fit_valueB[0]=y0;
00638     fit_valueB[1]=y1;
00639     fit_valueA[1]=y1;
00640 
00641     /* Non degenerate case */
00642     /* start progressive splitting.  This is a greedy, non-optimal
00643        algorithm, but simple and close enough to the best
00644        answer. */
00645     for(i=2;i<posts;i++){
00646       int sortpos=look->reverse_index[i];
00647       int ln=loneighbor[sortpos];
00648       int hn=hineighbor[sortpos];
00649       
00650       /* eliminate repeat searches of a particular range with a memo */
00651       if(memo[ln]!=hn){
00652         /* haven't performed this error search yet */
00653         int lsortpos=look->reverse_index[ln];
00654         int hsortpos=look->reverse_index[hn];
00655         memo[ln]=hn;
00656                 
00657         {
00658           /* A note: we want to bound/minimize *local*, not global, error */
00659           int lx=info->postlist[ln];
00660           int hx=info->postlist[hn];      
00661           int ly=post_Y(fit_valueA,fit_valueB,ln);
00662           int hy=post_Y(fit_valueA,fit_valueB,hn);
00663           
00664           if(ly==-1 || hy==-1){
00665             exit(1);
00666           }
00667 
00668           if(inspect_error(lx,hx,ly,hy,logmask,logmdct,info)){
00669             /* outside error bounds/begin search area.  Split it. */
00670             int ly0=-200;
00671             int ly1=-200;
00672             int hy0=-200;
00673             int hy1=-200;
00674             fit_line(fits+lsortpos,sortpos-lsortpos,&ly0,&ly1);
00675             fit_line(fits+sortpos,hsortpos-sortpos,&hy0,&hy1);
00676             
00677             /* store new edge values */
00678             fit_valueB[ln]=ly0;
00679             if(ln==0)fit_valueA[ln]=ly0;
00680             fit_valueA[i]=ly1;
00681             fit_valueB[i]=hy0;
00682             fit_valueA[hn]=hy1;
00683             if(hn==1)fit_valueB[hn]=hy1;
00684             
00685             if(ly1>=0 || hy0>=0){
00686               /* store new neighbor values */
00687               for(j=sortpos-1;j>=0;j--)
00688                 if(hineighbor[j]==hn)
00689                   hineighbor[j]=i;
00690                 else
00691                   break;
00692               for(j=sortpos+1;j<posts;j++)
00693                 if(loneighbor[j]==ln)
00694                   loneighbor[j]=i;
00695                 else
00696                   break;
00697               
00698             }
00699           }else{
00700             
00701             fit_valueA[i]=-200;
00702             fit_valueB[i]=-200;
00703           }
00704         }
00705       }
00706     }
00707   
00708     output=(int*)_vorbis_block_alloc(vb,sizeof(*output)*posts);
00709     
00710     output[0]=post_Y(fit_valueA,fit_valueB,0);
00711     output[1]=post_Y(fit_valueA,fit_valueB,1);
00712     
00713     /* fill in posts marked as not using a fit; we will zero
00714        back out to 'unused' when encoding them so long as curve
00715        interpolation doesn't force them into use */
00716     for(i=2;i<posts;i++){
00717       int ln=look->loneighbor[i-2];
00718       int hn=look->hineighbor[i-2];
00719       int x0=info->postlist[ln];
00720       int x1=info->postlist[hn];
00721       int y0=output[ln];
00722       int y1=output[hn];
00723       
00724       int predicted=render_point(x0,x1,y0,y1,info->postlist[i]);
00725       int vx=post_Y(fit_valueA,fit_valueB,i);
00726       
00727       if(vx>=0 && predicted!=vx){ 
00728         output[i]=vx;
00729       }else{
00730         output[i]= predicted|0x8000;
00731       }
00732     }
00733   }
00734 
00735   return(output);
00736   
00737 }
00738                 
00739 int *floor1_interpolate_fit(vorbis_block *vb,vorbis_look_floor1 *look,
00740                           int *A,int *B,
00741                           int del){
00742 
00743   long i;
00744   long posts=look->posts;
00745   int *output=NULL;
00746   
00747   if(A && B){
00748     output=(int*)_vorbis_block_alloc(vb,sizeof(*output)*posts);
00749     
00750     for(i=0;i<posts;i++){
00751       output[i]=((65536-del)*(A[i]&0x7fff)+del*(B[i]&0x7fff)+32768)>>16;
00752       if(A[i]&0x8000 && B[i]&0x8000)output[i]|=0x8000;
00753     }
00754   }
00755 
00756   return(output);
00757 }
00758 
00759 
00760 int floor1_encode(oggpack_buffer *opb,vorbis_block *vb,
00761                   vorbis_look_floor1 *look,
00762                   int *post,int *ilogmask){
00763 
00764   long i,j;
00765   vorbis_info_floor1 *info=look->vi;
00766   //long n=look->n; //warning
00767   long posts=look->posts;
00768   codec_setup_info *ci=(codec_setup_info*)vb->vd->vi->codec_setup;
00769   int out[VIF_POSIT+2];
00770   static_codebook **sbooks=ci->book_param;
00771   codebook *books=ci->fullbooks;
00772   static long seq=0; 
00773 
00774   /* quantize values to multiplier spec */
00775   if(post){
00776     for(i=0;i<posts;i++){
00777       int val=post[i]&0x7fff;
00778       switch(info->mult){
00779       case 1: /* 1024 -> 256 */
00780         val>>=2;
00781         break;
00782       case 2: /* 1024 -> 128 */
00783         val>>=3;
00784         break;
00785       case 3: /* 1024 -> 86 */
00786         val/=12;
00787         break;
00788       case 4: /* 1024 -> 64 */
00789         val>>=4;
00790         break;
00791       }
00792       post[i]=val | (post[i]&0x8000);
00793     }
00794 
00795     out[0]=post[0];
00796     out[1]=post[1];
00797 
00798     /* find prediction values for each post and subtract them */
00799     for(i=2;i<posts;i++){
00800       int ln=look->loneighbor[i-2];
00801       int hn=look->hineighbor[i-2];
00802       int x0=info->postlist[ln];
00803       int x1=info->postlist[hn];
00804       int y0=post[ln];
00805       int y1=post[hn];
00806       
00807       int predicted=render_point(x0,x1,y0,y1,info->postlist[i]);
00808       
00809       if((post[i]&0x8000) || (predicted==post[i])){
00810         post[i]=predicted|0x8000; /* in case there was roundoff jitter
00811                                      in interpolation */
00812         out[i]=0;
00813       }else{
00814         int headroom=(look->quant_q-predicted<predicted?
00815                       look->quant_q-predicted:predicted);
00816         
00817         int val=post[i]-predicted;
00818         
00819         /* at this point the 'deviation' value is in the range +/- max
00820            range, but the real, unique range can always be mapped to
00821            only [0-maxrange).  So we want to wrap the deviation into
00822            this limited range, but do it in the way that least screws
00823            an essentially gaussian probability distribution. */
00824         
00825         if(val<0)
00826           if(val<-headroom)
00827             val=headroom-val-1;
00828           else
00829             val=-1-(val<<1);
00830         else
00831           if(val>=headroom)
00832             val= val+headroom;
00833           else
00834             val<<=1;
00835         
00836         out[i]=val;
00837         post[ln]&=0x7fff;
00838         post[hn]&=0x7fff;
00839       }
00840     }
00841     
00842     /* we have everything we need. pack it out */
00843     /* mark nontrivial floor */
00844     oggpack_write(opb,1,1);
00845       
00846     /* beginning/end post */
00847     look->frames++;
00848     look->postbits+=ilog(look->quant_q-1)*2;
00849     oggpack_write(opb,out[0],ilog(look->quant_q-1));
00850     oggpack_write(opb,out[1],ilog(look->quant_q-1));
00851       
00852       
00853     /* partition by partition */
00854     for(i=0,j=2;i<info->partitions;i++){
00855       int nclass=info->partitionclass[i];
00856       int cdim=info->class_dim[nclass];
00857       int csubbits=info->class_subs[nclass];
00858       int csub=1<<csubbits;
00859       int bookas[8]={0,0,0,0,0,0,0,0};
00860       int cval=0;
00861       int cshift=0;
00862       int k,l;
00863 
00864       /* generate the partition's first stage cascade value */
00865       if(csubbits){
00866         int maxval[8];
00867         for(k=0;k<csub;k++){
00868           int booknum=info->class_subbook[nclass][k];
00869           if(booknum<0){
00870             maxval[k]=1;
00871           }else{
00872             maxval[k]=sbooks[info->class_subbook[nclass][k]]->entries;
00873           }
00874         }
00875         for(k=0;k<cdim;k++){
00876           for(l=0;l<csub;l++){
00877             int val=out[j+k];
00878             if(val<maxval[l]){
00879               bookas[k]=l;
00880               break;
00881             }
00882           }
00883           cval|= bookas[k]<<cshift;
00884           cshift+=csubbits;
00885         }
00886         /* write it */
00887         look->phrasebits+=
00888           vorbis_book_encode(books+info->class_book[nclass],cval,opb);
00889         
00890 #ifdef TRAIN_FLOOR1
00891         {
00892           FILE *of;
00893           char buffer[80];
00894           sprintf(buffer,"line_%dx%ld_class%d.vqd",
00895                   vb->pcmend/2,posts-2,nclass);
00896           of=fopen(buffer,"a");
00897           fprintf(of,"%d\n",cval);
00898           fclose(of);
00899         }
00900 #endif
00901       }
00902         
00903       /* write post values */
00904       for(k=0;k<cdim;k++){
00905         int book=info->class_subbook[nclass][bookas[k]];
00906         if(book>=0){
00907           /* hack to allow training with 'bad' books */
00908           if(out[j+k]<(books+book)->entries)
00909             look->postbits+=vorbis_book_encode(books+book,
00910                                                out[j+k],opb);
00911           /*else
00912             fprintf(stderr,"+!");*/
00913           
00914 #ifdef TRAIN_FLOOR1
00915           {
00916             FILE *of;
00917             char buffer[80];
00918             sprintf(buffer,"line_%dx%ld_%dsub%d.vqd",
00919                     vb->pcmend/2,posts-2,nclass,bookas[k]);
00920             of=fopen(buffer,"a");
00921             fprintf(of,"%d\n",out[j+k]);
00922             fclose(of);
00923           }
00924 #endif
00925         }
00926       }
00927       j+=cdim;
00928     }
00929     
00930     {
00931       /* generate quantized floor equivalent to what we'd unpack in decode */
00932       /* render the lines */
00933       int hx=0;
00934       int lx=0;
00935       int ly=post[0]*info->mult;
00936       for(j=1;j<look->posts;j++){
00937         int current=look->forward_index[j];
00938         int hy=post[current]&0x7fff;
00939         if(hy==post[current]){
00940           
00941           hy*=info->mult;
00942           hx=info->postlist[current];
00943         
00944           render_line0(lx,hx,ly,hy,ilogmask);
00945         
00946           lx=hx;
00947           ly=hy;
00948         }
00949       }
00950       for(j=hx;j<vb->pcmend/2;j++)ilogmask[j]=ly; /* be certain */    
00951       seq++;
00952       return(1);
00953     }
00954   }else{
00955     oggpack_write(opb,0,1);
00956     memset(ilogmask,0,vb->pcmend/2*sizeof(*ilogmask));
00957     seq++;
00958     return(0);
00959   }
00960 }
00961 
00962 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
00963   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
00964   vorbis_info_floor1 *info=look->vi;
00965   codec_setup_info   *ci=(codec_setup_info*)vb->vd->vi->codec_setup;
00966   
00967   int i,j,k;
00968   codebook *books=ci->fullbooks;   
00969 
00970   /* unpack wrapped/predicted values from stream */
00971   if(oggpack_read(&vb->opb,1)==1){
00972     int *fit_value=(int*)_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
00973 
00974     fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
00975     fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
00976 
00977     /* partition by partition */
00978     for(i=0,j=2;i<info->partitions;i++){
00979       int nclass=info->partitionclass[i];
00980       int cdim=info->class_dim[nclass];
00981       int csubbits=info->class_subs[nclass];
00982       int csub=1<<csubbits;
00983       int cval=0;
00984 
00985       /* decode the partition's first stage cascade value */
00986       if(csubbits){
00987         cval=vorbis_book_decode(books+info->class_book[nclass],&vb->opb);
00988 
00989         if(cval==-1)goto eop;
00990       }
00991 
00992       for(k=0;k<cdim;k++){
00993         int book=info->class_subbook[nclass][cval&(csub-1)];
00994         cval>>=csubbits;
00995         if(book>=0){
00996           if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
00997             goto eop;
00998         }else{
00999           fit_value[j+k]=0;
01000         }
01001       }
01002       j+=cdim;
01003     }
01004 
01005     /* unwrap positive values and reconsitute via linear interpolation */
01006     for(i=2;i<look->posts;i++){
01007       int predicted=render_point(info->postlist[look->loneighbor[i-2]],
01008                                  info->postlist[look->hineighbor[i-2]],
01009                                  fit_value[look->loneighbor[i-2]],
01010                                  fit_value[look->hineighbor[i-2]],
01011                                  info->postlist[i]);
01012       int hiroom=look->quant_q-predicted;
01013       int loroom=predicted;
01014       int room=(hiroom<loroom?hiroom:loroom)<<1;
01015       int val=fit_value[i];
01016 
01017       if(val){
01018         if(val>=room){
01019           if(hiroom>loroom){
01020             val = val-loroom;
01021           }else{
01022             val = -1-(val-hiroom);
01023           }
01024         }else{
01025           if(val&1){
01026             val= -((val+1)>>1);
01027           }else{
01028             val>>=1;
01029           }
01030         }
01031 
01032         fit_value[i]=val+predicted;
01033         fit_value[look->loneighbor[i-2]]&=0x7fff;
01034         fit_value[look->hineighbor[i-2]]&=0x7fff;
01035 
01036       }else{
01037         fit_value[i]=predicted|0x8000;
01038       }
01039         
01040     }
01041 
01042     return(fit_value);
01043   }
01044  eop:
01045   return(NULL);
01046 }
01047 
01048 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
01049                           float *out){
01050   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
01051   vorbis_info_floor1 *info=look->vi;
01052 
01053   codec_setup_info   *ci=(codec_setup_info*)vb->vd->vi->codec_setup;
01054   int                  n=ci->blocksizes[vb->W]/2;
01055   int j;
01056 
01057   if(memo){
01058     /* render the lines */
01059     int *fit_value=(int *)memo;
01060     int hx=0;
01061     int lx=0;
01062     int ly=fit_value[0]*info->mult;
01063     for(j=1;j<look->posts;j++){
01064       int current=look->forward_index[j];
01065       int hy=fit_value[current]&0x7fff;
01066       if(hy==fit_value[current]){
01067         
01068         hy*=info->mult;
01069         hx=info->postlist[current];
01070         
01071         render_line(lx,hx,ly,hy,out);
01072         
01073         lx=hx;
01074         ly=hy;
01075       }
01076     }
01077     for(j=hx;j<n;j++)out[j]*=FLOOR1_fromdB_LOOKUP[ly]; /* be certain */    
01078     return(1);
01079   }
01080   memset(out,0,sizeof(*out)*n);
01081   return(0);
01082 }
01083 
01084 /* export hooks */
01085 vorbis_func_floor floor1_exportbundle={
01086   &floor1_pack,&floor1_unpack,&floor1_look,&floor1_free_info,
01087   &floor1_free_look,&floor1_inverse1,&floor1_inverse2
01088 };
01089 
01090 

Generated by  doxygen 1.6.2