Home | History | Annotate | Download | only in Tremolo
      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