Tremor/floor1.c

   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