misc/libtremor/floor1.c
branchhedgeroid
changeset 6043 9bd2d6b1ba52
parent 6041 04bbe344b8d3
child 6045 9a7cc0f29430
equal deleted inserted replaced
6041:04bbe344b8d3 6043:9bd2d6b1ba52
     1 /********************************************************************
       
     2  *                                                                  *
       
     3  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
       
     4  *                                                                  *
       
     5  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
       
     6  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
       
     7  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
       
     8  *                                                                  *
       
     9  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
       
    10  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
       
    11  *                                                                  *
       
    12  ********************************************************************
       
    13 
       
    14  function: floor backend 1 implementation
       
    15 
       
    16  ********************************************************************/
       
    17 
       
    18 #include <stdlib.h>
       
    19 #include <string.h>
       
    20 #include <math.h>
       
    21 #include "ogg.h"
       
    22 #include "ivorbiscodec.h"
       
    23 #include "codec_internal.h"
       
    24 #include "registry.h"
       
    25 #include "codebook.h"
       
    26 #include "misc.h"
       
    27 #include "block.h"
       
    28 
       
    29 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
       
    30 
       
    31 typedef struct {
       
    32   int forward_index[VIF_POSIT+2];
       
    33   
       
    34   int hineighbor[VIF_POSIT];
       
    35   int loneighbor[VIF_POSIT];
       
    36   int posts;
       
    37 
       
    38   int n;
       
    39   int quant_q;
       
    40   vorbis_info_floor1 *vi;
       
    41 
       
    42 } vorbis_look_floor1;
       
    43 
       
    44 /***********************************************/
       
    45  
       
    46 static void floor1_free_info(vorbis_info_floor *i){
       
    47   vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
       
    48   if(info){
       
    49     memset(info,0,sizeof(*info));
       
    50     _ogg_free(info);
       
    51   }
       
    52 }
       
    53 
       
    54 static void floor1_free_look(vorbis_look_floor *i){
       
    55   vorbis_look_floor1 *look=(vorbis_look_floor1 *)i;
       
    56   if(look){
       
    57     memset(look,0,sizeof(*look));
       
    58     _ogg_free(look);
       
    59   }
       
    60 }
       
    61 
       
    62 static int ilog(unsigned int v){
       
    63   int ret=0;
       
    64   while(v){
       
    65     ret++;
       
    66     v>>=1;
       
    67   }
       
    68   return(ret);
       
    69 }
       
    70 
       
    71 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){
       
    72   codec_setup_info     *ci=(codec_setup_info *)vi->codec_setup;
       
    73   int j,k,count=0,maxclass=-1,rangebits;
       
    74 
       
    75   vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
       
    76   /* read partitions */
       
    77   info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
       
    78   for(j=0;j<info->partitions;j++){
       
    79     info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
       
    80     if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
       
    81   }
       
    82 
       
    83   /* read partition classes */
       
    84   for(j=0;j<maxclass+1;j++){
       
    85     info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */
       
    86     info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */
       
    87     if(info->class_subs[j]<0)
       
    88       goto err_out;
       
    89     if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8);
       
    90     if(info->class_book[j]<0 || info->class_book[j]>=ci->books)
       
    91       goto err_out;
       
    92     for(k=0;k<(1<<info->class_subs[j]);k++){
       
    93       info->class_subbook[j][k]=oggpack_read(opb,8)-1;
       
    94       if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books)
       
    95 	goto err_out;
       
    96     }
       
    97   }
       
    98 
       
    99   /* read the post list */
       
   100   info->mult=oggpack_read(opb,2)+1;     /* only 1,2,3,4 legal now */ 
       
   101   rangebits=oggpack_read(opb,4);
       
   102 
       
   103   for(j=0,k=0;j<info->partitions;j++){
       
   104     count+=info->class_dim[info->partitionclass[j]]; 
       
   105     for(;k<count;k++){
       
   106       int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
       
   107       if(t<0 || t>=(1<<rangebits))
       
   108 	goto err_out;
       
   109     }
       
   110   }
       
   111   info->postlist[0]=0;
       
   112   info->postlist[1]=1<<rangebits;
       
   113 
       
   114   return(info);
       
   115   
       
   116  err_out:
       
   117   floor1_free_info(info);
       
   118   return(NULL);
       
   119 }
       
   120 
       
   121 static int icomp(const void *a,const void *b){
       
   122   return(**(int **)a-**(int **)b);
       
   123 }
       
   124 
       
   125 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,vorbis_info_mode *mi,
       
   126                               vorbis_info_floor *in){
       
   127 
       
   128   int *sortpointer[VIF_POSIT+2];
       
   129   vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
       
   130   vorbis_look_floor1 *look=(vorbis_look_floor1 *)_ogg_calloc(1,sizeof(*look));
       
   131   int i,j,n=0;
       
   132 
       
   133   look->vi=info;
       
   134   look->n=info->postlist[1];
       
   135  
       
   136   /* we drop each position value in-between already decoded values,
       
   137      and use linear interpolation to predict each new value past the
       
   138      edges.  The positions are read in the order of the position
       
   139      list... we precompute the bounding positions in the lookup.  Of
       
   140      course, the neighbors can change (if a position is declined), but
       
   141      this is an initial mapping */
       
   142 
       
   143   for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
       
   144   n+=2;
       
   145   look->posts=n;
       
   146 
       
   147   /* also store a sorted position index */
       
   148   for(i=0;i<n;i++)sortpointer[i]=info->postlist+i;
       
   149   qsort(sortpointer,n,sizeof(*sortpointer),icomp);
       
   150 
       
   151   /* points from sort order back to range number */
       
   152   for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist;
       
   153   
       
   154   /* quantize values to multiplier spec */
       
   155   switch(info->mult){
       
   156   case 1: /* 1024 -> 256 */
       
   157     look->quant_q=256;
       
   158     break;
       
   159   case 2: /* 1024 -> 128 */
       
   160     look->quant_q=128;
       
   161     break;
       
   162   case 3: /* 1024 -> 86 */
       
   163     look->quant_q=86;
       
   164     break;
       
   165   case 4: /* 1024 -> 64 */
       
   166     look->quant_q=64;
       
   167     break;
       
   168   }
       
   169 
       
   170   /* discover our neighbors for decode where we don't use fit flags
       
   171      (that would push the neighbors outward) */
       
   172   for(i=0;i<n-2;i++){
       
   173     int lo=0;
       
   174     int hi=1;
       
   175     int lx=0;
       
   176     int hx=look->n;
       
   177     int currentx=info->postlist[i+2];
       
   178     for(j=0;j<i+2;j++){
       
   179       int x=info->postlist[j];
       
   180       if(x>lx && x<currentx){
       
   181 	lo=j;
       
   182 	lx=x;
       
   183       }
       
   184       if(x<hx && x>currentx){
       
   185 	hi=j;
       
   186 	hx=x;
       
   187       }
       
   188     }
       
   189     look->loneighbor[i]=lo;
       
   190     look->hineighbor[i]=hi;
       
   191   }
       
   192 
       
   193   return(look);
       
   194 }
       
   195 
       
   196 static int render_point(int x0,int x1,int y0,int y1,int x){
       
   197   y0&=0x7fff; /* mask off flag */
       
   198   y1&=0x7fff;
       
   199     
       
   200   {
       
   201     int dy=y1-y0;
       
   202     int adx=x1-x0;
       
   203     int ady=abs(dy);
       
   204     int err=ady*(x-x0);
       
   205     
       
   206     int off=err/adx;
       
   207     if(dy<0)return(y0-off);
       
   208     return(y0+off);
       
   209   }
       
   210 }
       
   211 
       
   212 #ifdef _LOW_ACCURACY_
       
   213 #  define XdB(n) ((((n)>>8)+1)>>1)
       
   214 #else
       
   215 #  define XdB(n) (n)
       
   216 #endif
       
   217 
       
   218 static const ogg_int32_t FLOOR_fromdB_LOOKUP[256]={
       
   219   XdB(0x000000e5), XdB(0x000000f4), XdB(0x00000103), XdB(0x00000114),
       
   220   XdB(0x00000126), XdB(0x00000139), XdB(0x0000014e), XdB(0x00000163),
       
   221   XdB(0x0000017a), XdB(0x00000193), XdB(0x000001ad), XdB(0x000001c9),
       
   222   XdB(0x000001e7), XdB(0x00000206), XdB(0x00000228), XdB(0x0000024c),
       
   223   XdB(0x00000272), XdB(0x0000029b), XdB(0x000002c6), XdB(0x000002f4),
       
   224   XdB(0x00000326), XdB(0x0000035a), XdB(0x00000392), XdB(0x000003cd),
       
   225   XdB(0x0000040c), XdB(0x00000450), XdB(0x00000497), XdB(0x000004e4),
       
   226   XdB(0x00000535), XdB(0x0000058c), XdB(0x000005e8), XdB(0x0000064a),
       
   227   XdB(0x000006b3), XdB(0x00000722), XdB(0x00000799), XdB(0x00000818),
       
   228   XdB(0x0000089e), XdB(0x0000092e), XdB(0x000009c6), XdB(0x00000a69),
       
   229   XdB(0x00000b16), XdB(0x00000bcf), XdB(0x00000c93), XdB(0x00000d64),
       
   230   XdB(0x00000e43), XdB(0x00000f30), XdB(0x0000102d), XdB(0x0000113a),
       
   231   XdB(0x00001258), XdB(0x0000138a), XdB(0x000014cf), XdB(0x00001629),
       
   232   XdB(0x0000179a), XdB(0x00001922), XdB(0x00001ac4), XdB(0x00001c82),
       
   233   XdB(0x00001e5c), XdB(0x00002055), XdB(0x0000226f), XdB(0x000024ac),
       
   234   XdB(0x0000270e), XdB(0x00002997), XdB(0x00002c4b), XdB(0x00002f2c),
       
   235   XdB(0x0000323d), XdB(0x00003581), XdB(0x000038fb), XdB(0x00003caf),
       
   236   XdB(0x000040a0), XdB(0x000044d3), XdB(0x0000494c), XdB(0x00004e10),
       
   237   XdB(0x00005323), XdB(0x0000588a), XdB(0x00005e4b), XdB(0x0000646b),
       
   238   XdB(0x00006af2), XdB(0x000071e5), XdB(0x0000794c), XdB(0x0000812e),
       
   239   XdB(0x00008993), XdB(0x00009283), XdB(0x00009c09), XdB(0x0000a62d),
       
   240   XdB(0x0000b0f9), XdB(0x0000bc79), XdB(0x0000c8b9), XdB(0x0000d5c4),
       
   241   XdB(0x0000e3a9), XdB(0x0000f274), XdB(0x00010235), XdB(0x000112fd),
       
   242   XdB(0x000124dc), XdB(0x000137e4), XdB(0x00014c29), XdB(0x000161bf),
       
   243   XdB(0x000178bc), XdB(0x00019137), XdB(0x0001ab4a), XdB(0x0001c70e),
       
   244   XdB(0x0001e4a1), XdB(0x0002041f), XdB(0x000225aa), XdB(0x00024962),
       
   245   XdB(0x00026f6d), XdB(0x000297f0), XdB(0x0002c316), XdB(0x0002f109),
       
   246   XdB(0x000321f9), XdB(0x00035616), XdB(0x00038d97), XdB(0x0003c8b4),
       
   247   XdB(0x000407a7), XdB(0x00044ab2), XdB(0x00049218), XdB(0x0004de23),
       
   248   XdB(0x00052f1e), XdB(0x0005855c), XdB(0x0005e135), XdB(0x00064306),
       
   249   XdB(0x0006ab33), XdB(0x00071a24), XdB(0x0007904b), XdB(0x00080e20),
       
   250   XdB(0x00089422), XdB(0x000922da), XdB(0x0009bad8), XdB(0x000a5cb6),
       
   251   XdB(0x000b091a), XdB(0x000bc0b1), XdB(0x000c8436), XdB(0x000d5471),
       
   252   XdB(0x000e3233), XdB(0x000f1e5f), XdB(0x001019e4), XdB(0x001125c1),
       
   253   XdB(0x00124306), XdB(0x001372d5), XdB(0x0014b663), XdB(0x00160ef7),
       
   254   XdB(0x00177df0), XdB(0x001904c1), XdB(0x001aa4f9), XdB(0x001c603d),
       
   255   XdB(0x001e384f), XdB(0x00202f0f), XdB(0x0022467a), XdB(0x002480b1),
       
   256   XdB(0x0026dff7), XdB(0x002966b3), XdB(0x002c1776), XdB(0x002ef4fc),
       
   257   XdB(0x0032022d), XdB(0x00354222), XdB(0x0038b828), XdB(0x003c67c2),
       
   258   XdB(0x004054ae), XdB(0x004482e8), XdB(0x0048f6af), XdB(0x004db488),
       
   259   XdB(0x0052c142), XdB(0x005821ff), XdB(0x005ddc33), XdB(0x0063f5b0),
       
   260   XdB(0x006a74a7), XdB(0x00715faf), XdB(0x0078bdce), XdB(0x0080967f),
       
   261   XdB(0x0088f1ba), XdB(0x0091d7f9), XdB(0x009b5247), XdB(0x00a56a41),
       
   262   XdB(0x00b02a27), XdB(0x00bb9ce2), XdB(0x00c7ce12), XdB(0x00d4ca17),
       
   263   XdB(0x00e29e20), XdB(0x00f15835), XdB(0x0101074b), XdB(0x0111bb4e),
       
   264   XdB(0x01238531), XdB(0x01367704), XdB(0x014aa402), XdB(0x016020a7),
       
   265   XdB(0x017702c3), XdB(0x018f6190), XdB(0x01a955cb), XdB(0x01c4f9cf),
       
   266   XdB(0x01e269a8), XdB(0x0201c33b), XdB(0x0223265a), XdB(0x0246b4ea),
       
   267   XdB(0x026c9302), XdB(0x0294e716), XdB(0x02bfda13), XdB(0x02ed9793),
       
   268   XdB(0x031e4e09), XdB(0x03522ee4), XdB(0x03896ed0), XdB(0x03c445e2),
       
   269   XdB(0x0402efd6), XdB(0x0445ac4b), XdB(0x048cbefc), XdB(0x04d87013),
       
   270   XdB(0x05290c67), XdB(0x057ee5ca), XdB(0x05da5364), XdB(0x063bb204),
       
   271   XdB(0x06a36485), XdB(0x0711d42b), XdB(0x0787710e), XdB(0x0804b299),
       
   272   XdB(0x088a17ef), XdB(0x0918287e), XdB(0x09af747c), XdB(0x0a50957e),
       
   273   XdB(0x0afc2f19), XdB(0x0bb2ef7f), XdB(0x0c759034), XdB(0x0d44d6ca),
       
   274   XdB(0x0e2195bc), XdB(0x0f0cad0d), XdB(0x10070b62), XdB(0x1111aeea),
       
   275   XdB(0x122da66c), XdB(0x135c120f), XdB(0x149e24d9), XdB(0x15f525b1),
       
   276   XdB(0x176270e3), XdB(0x18e7794b), XdB(0x1a85c9ae), XdB(0x1c3f06d1),
       
   277   XdB(0x1e14f07d), XdB(0x200963d7), XdB(0x221e5ccd), XdB(0x2455f870),
       
   278   XdB(0x26b2770b), XdB(0x29363e2b), XdB(0x2be3db5c), XdB(0x2ebe06b6),
       
   279   XdB(0x31c7a55b), XdB(0x3503ccd4), XdB(0x3875c5aa), XdB(0x3c210f44),
       
   280   XdB(0x4009632b), XdB(0x4432b8cf), XdB(0x48a149bc), XdB(0x4d59959e),
       
   281   XdB(0x52606733), XdB(0x57bad899), XdB(0x5d6e593a), XdB(0x6380b298),
       
   282   XdB(0x69f80e9a), XdB(0x70dafda8), XdB(0x78307d76), XdB(0x7fffffff),
       
   283 };
       
   284   
       
   285 static void render_line(int n, int x0,int x1,int y0,int y1,ogg_int32_t *d){
       
   286   int dy=y1-y0;
       
   287   int adx=x1-x0;
       
   288   int ady=abs(dy);
       
   289   int base=dy/adx;
       
   290   int sy=(dy<0?base-1:base+1);
       
   291   int x=x0;
       
   292   int y=y0;
       
   293   int err=0;
       
   294 
       
   295   if(n>x1)n=x1;
       
   296   ady-=abs(base*adx);
       
   297 
       
   298   if(x<n)
       
   299     d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
       
   300 
       
   301   while(++x<n){
       
   302     err=err+ady;
       
   303     if(err>=adx){
       
   304       err-=adx;
       
   305       y+=sy;
       
   306     }else{
       
   307       y+=base;
       
   308     }
       
   309     d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
       
   310   }
       
   311 }
       
   312 
       
   313 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
       
   314   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
       
   315   vorbis_info_floor1 *info=look->vi;
       
   316   codec_setup_info   *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
       
   317   
       
   318   int i,j,k;
       
   319   codebook *books=ci->fullbooks;   
       
   320   
       
   321   /* unpack wrapped/predicted values from stream */
       
   322   if(oggpack_read(&vb->opb,1)==1){
       
   323     int *fit_value=(int *)_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
       
   324     
       
   325     fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
       
   326     fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
       
   327     
       
   328     /* partition by partition */
       
   329     /* partition by partition */
       
   330     for(i=0,j=2;i<info->partitions;i++){
       
   331       int classv=info->partitionclass[i];
       
   332       int cdim=info->class_dim[classv];
       
   333       int csubbits=info->class_subs[classv];
       
   334       int csub=1<<csubbits;
       
   335       int cval=0;
       
   336 
       
   337       /* decode the partition's first stage cascade value */
       
   338       if(csubbits){
       
   339 	cval=vorbis_book_decode(books+info->class_book[classv],&vb->opb);
       
   340 
       
   341 	if(cval==-1)goto eop;
       
   342       }
       
   343 
       
   344       for(k=0;k<cdim;k++){
       
   345 	int book=info->class_subbook[classv][cval&(csub-1)];
       
   346 	cval>>=csubbits;
       
   347 	if(book>=0){
       
   348 	  if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
       
   349 	    goto eop;
       
   350 	}else{
       
   351 	  fit_value[j+k]=0;
       
   352 	}
       
   353       }
       
   354       j+=cdim;
       
   355     }
       
   356 
       
   357     /* unwrap positive values and reconsitute via linear interpolation */
       
   358     for(i=2;i<look->posts;i++){
       
   359       int predicted=render_point(info->postlist[look->loneighbor[i-2]],
       
   360 				 info->postlist[look->hineighbor[i-2]],
       
   361 				 fit_value[look->loneighbor[i-2]],
       
   362 				 fit_value[look->hineighbor[i-2]],
       
   363 				 info->postlist[i]);
       
   364       int hiroom=look->quant_q-predicted;
       
   365       int loroom=predicted;
       
   366       int room=(hiroom<loroom?hiroom:loroom)<<1;
       
   367       int val=fit_value[i];
       
   368 
       
   369       if(val){
       
   370 	if(val>=room){
       
   371 	  if(hiroom>loroom){
       
   372 	    val = val-loroom;
       
   373 	  }else{
       
   374 	  val = -1-(val-hiroom);
       
   375 	  }
       
   376 	}else{
       
   377 	  if(val&1){
       
   378 	    val= -((val+1)>>1);
       
   379 	  }else{
       
   380 	    val>>=1;
       
   381 	  }
       
   382 	}
       
   383 
       
   384 	fit_value[i]=val+predicted;
       
   385 	fit_value[look->loneighbor[i-2]]&=0x7fff;
       
   386 	fit_value[look->hineighbor[i-2]]&=0x7fff;
       
   387 
       
   388       }else{
       
   389 	fit_value[i]=predicted|0x8000;
       
   390       }
       
   391 	
       
   392     }
       
   393 
       
   394     return(fit_value);
       
   395   }
       
   396  eop:
       
   397   return(NULL);
       
   398 }
       
   399 
       
   400 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
       
   401 			  ogg_int32_t *out){
       
   402   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
       
   403   vorbis_info_floor1 *info=look->vi;
       
   404 
       
   405   codec_setup_info   *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
       
   406   int                  n=ci->blocksizes[vb->W]/2;
       
   407   int j;
       
   408 
       
   409   if(memo){
       
   410     /* render the lines */
       
   411     int *fit_value=(int *)memo;
       
   412     int hx=0;
       
   413     int lx=0;
       
   414     int ly=fit_value[0]*info->mult;
       
   415     for(j=1;j<look->posts;j++){
       
   416       int current=look->forward_index[j];
       
   417       int hy=fit_value[current]&0x7fff;
       
   418       if(hy==fit_value[current]){
       
   419 	
       
   420 	hy*=info->mult;
       
   421 	hx=info->postlist[current];
       
   422 	
       
   423 	render_line(n,lx,hx,ly,hy,out);
       
   424 	
       
   425 	lx=hx;
       
   426 	ly=hy;
       
   427       }
       
   428     }
       
   429     for(j=hx;j<n;j++)out[j]*=ly; /* be certain */    
       
   430     return(1);
       
   431   }
       
   432   memset(out,0,sizeof(*out)*n);
       
   433   return(0);
       
   434 }
       
   435 
       
   436 /* export hooks */
       
   437 vorbis_func_floor floor1_exportbundle={
       
   438   &floor1_unpack,&floor1_look,&floor1_free_info,
       
   439   &floor1_free_look,&floor1_inverse1,&floor1_inverse2
       
   440 };
       
   441