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