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