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 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   ady-=abs(base*adx);
 296
 297   d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
 298
 299   while(++x<x1){
 300     err=err+ady;
 301     if(err>=adx){
 302       err-=adx;
 303       y+=sy;
 304     }else{
 305       y+=base;
 306     }
 307     d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
 308   }
 309 }
 310
 311 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
 312   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
 313   vorbis_info_floor1 *info=look->vi;
 314   codec_setup_info   *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
 315
 316   int i,j,k;
 317   codebook *books=ci->fullbooks;
 318
 319   /* unpack wrapped/predicted values from stream */
 320   if(oggpack_read(&vb->opb,1)==1){
 321     int *fit_value=(int *)_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
 322
 323     fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
 324     fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
 325
 326     /* partition by partition */
 327     /* partition by partition */
 328     for(i=0,j=2;i<info->partitions;i++){
 329       int classv=info->partitionclass[i];
 330       int cdim=info->class_dim[classv];
 331       int csubbits=info->class_subs[classv];
 332       int csub=1<<csubbits;
 333       int cval=0;
 334
 335       /* decode the partition's first stage cascade value */
 336       if(csubbits){
 337         cval=vorbis_book_decode(books+info->class_book[classv],&vb->opb);
 338
 339         if(cval==-1)goto eop;
 340       }
 341
 342       for(k=0;k<cdim;k++){
 343         int book=info->class_subbook[classv][cval&(csub-1)];
 344         cval>>=csubbits;
 345         if(book>=0){
 346           if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
 347             goto eop;
 348         }else{
 349           fit_value[j+k]=0;
 350         }
 351       }
 352       j+=cdim;
 353     }
 354
 355     /* unwrap positive values and reconsitute via linear interpolation */
 356     for(i=2;i<look->posts;i++){
 357       int predicted=render_point(info->postlist[look->loneighbor[i-2]],
 358                                  info->postlist[look->hineighbor[i-2]],
 359                                  fit_value[look->loneighbor[i-2]],
 360                                  fit_value[look->hineighbor[i-2]],
 361                                  info->postlist[i]);
 362       int hiroom=look->quant_q-predicted;
 363       int loroom=predicted;
 364       int room=(hiroom<loroom?hiroom:loroom)<<1;
 365       int val=fit_value[i];
 366
 367       if(val){
 368         if(val>=room){
 369           if(hiroom>loroom){
 370             val = val-loroom;
 371           }else{
 372           val = -1-(val-hiroom);
 373           }
 374         }else{
 375           if(val&1){
 376             val= -((val+1)>>1);
 377           }else{
 378             val>>=1;
 379           }
 380         }
 381
 382         fit_value[i]=val+predicted;
 383         fit_value[look->loneighbor[i-2]]&=0x7fff;
 384         fit_value[look->hineighbor[i-2]]&=0x7fff;
 385
 386       }else{
 387         fit_value[i]=predicted|0x8000;
 388       }
 389
 390     }
 391
 392     return(fit_value);
 393   }
 394  eop:
 395   return(NULL);
 396 }
 397
 398 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
 399                           ogg_int32_t *out){
 400   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
 401   vorbis_info_floor1 *info=look->vi;
 402
 403   codec_setup_info   *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
 404   int                  n=ci->blocksizes[vb->W]/2;
 405   int j;
 406
 407   if(memo){
 408     /* render the lines */
 409     int *fit_value=(int *)memo;
 410     int hx=0;
 411     int lx=0;
 412     int ly=fit_value[0]*info->mult;
 413     for(j=1;j<look->posts;j++){
 414       int current=look->forward_index[j];
 415       int hy=fit_value[current]&0x7fff;
 416       if(hy==fit_value[current]){
 417
 418         hy*=info->mult;
 419         hx=info->postlist[current];
 420
 421         render_line(lx,hx,ly,hy,out);
 422
 423         lx=hx;
 424         ly=hy;
 425       }
 426     }
 427     for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
 428     return(1);
 429   }
 430   memset(out,0,sizeof(*out)*n);
 431   return(0);
 432 }
 433
 434 /* export hooks */
 435 vorbis_func_floor floor1_exportbundle={
 436   &floor1_unpack,&floor1_look,&floor1_free_info,
 437   &floor1_free_look,&floor1_inverse1,&floor1_inverse2
 438 };
 439