lib/res0.c

   1 /********************************************************************
   2  *                                                                  *
   3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
   4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
   5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
   6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
   7  *                                                                  *
   8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
   9  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
  10  *                                                                  *
  11  ********************************************************************
  12
  13  function: residue backend 0, 1 and 2 implementation
  14  last mod: $Id: res0.c,v 1.31 2001/06/15 21:15:40 xiphmont Exp $
  15
  16  ********************************************************************/
  17
  18 /* Slow, slow, slow, simpleminded and did I mention it was slow?  The
  19    encode/decode loops are coded for clarity and performance is not
  20    yet even a nagging little idea lurking in the shadows.  Oh and BTW,
  21    it's slow. */
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <math.h>
  26 #include <stdio.h>
  27 #include <ogg/ogg.h>
  28 #include "vorbis/codec.h"
  29 #include "codec_internal.h"
  30 #include "registry.h"
  31 #include "codebook.h"
  32 #include "misc.h"
  33 #include "os.h"
  34
  35 typedef struct {
  36   vorbis_info_residue0 *info;
  37   int         map;
  38
  39   int         parts;
  40   int         stages;
  41   codebook   *fullbooks;
  42   codebook   *phrasebook;
  43   codebook ***partbooks;
  44
  45   int         partvals;
  46   int       **decodemap;
  47
  48   /*long      resbits[32][32];
  49   long      resbitsflat;
  50   long      resvals[32];
  51   long      phrasebits;
  52   long      frames;*/
  53
  54 } vorbis_look_residue0;
  55
  56 vorbis_info_residue *res0_copy_info(vorbis_info_residue *vr){
  57   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  58   vorbis_info_residue0 *ret=_ogg_malloc(sizeof(vorbis_info_residue0));
  59   memcpy(ret,info,sizeof(vorbis_info_residue0));
  60   return(ret);
  61 }
  62
  63 void res0_free_info(vorbis_info_residue *i){
  64   if(i){
  65     memset(i,0,sizeof(vorbis_info_residue0));
  66     _ogg_free(i);
  67   }
  68 }
  69
  70 void res0_free_look(vorbis_look_residue *i){
  71   int j,k;
  72   if(i){
  73
  74     vorbis_look_residue0 *look=(vorbis_look_residue0 *)i;
  75     vorbis_info_residue0 *info=look->info;
  76
  77     /*fprintf(stderr,
  78             "%ld frames encoded in %ld phrasebits and %ld residue bits "
  79             "(%g/frame) \n",look->frames,look->phrasebits,
  80             look->resbitsflat,
  81             (look->phrasebits+look->resbitsflat)/(float)look->frames);
  82
  83     for(j=0;j<look->parts;j++){
  84       long acc=0;
  85       fprintf(stderr,"\t[%d] == ",j);
  86       for(k=0;k<look->stages;k++)
  87         if((info->secondstages[j]>>k)&1){
  88           fprintf(stderr,"%ld,",look->resbits[j][k]);
  89           acc+=look->resbits[j][k];
  90         }
  91
  92       fprintf(stderr,":: (%ld vals) %1.2fbits/sample\n",look->resvals[j],
  93               acc?(float)acc/(look->resvals[j]*info->grouping):0);
  94     }
  95     fprintf(stderr,"\n");*/
  96
  97     for(j=0;j<look->parts;j++)
  98       if(look->partbooks[j])_ogg_free(look->partbooks[j]);
  99     _ogg_free(look->partbooks);
 100     for(j=0;j<look->partvals;j++)
 101       _ogg_free(look->decodemap[j]);
 102     _ogg_free(look->decodemap);
 103     memset(i,0,sizeof(vorbis_look_residue0));
 104     _ogg_free(i);
 105   }
 106 }
 107
 108 static int ilog(unsigned int v){
 109   int ret=0;
 110   while(v){
 111     ret++;
 112     v>>=1;
 113   }
 114   return(ret);
 115 }
 116
 117 static int icount(unsigned int v){
 118   int ret=0;
 119   while(v){
 120     ret+=v&1;
 121     v>>=1;
 122   }
 123   return(ret);
 124 }
 125
 126
 127 void res0_pack(vorbis_info_residue *vr,oggpack_buffer *opb){
 128   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
 129   int j,acc=0;
 130   oggpack_write(opb,info->begin,24);
 131   oggpack_write(opb,info->end,24);
 132
 133   oggpack_write(opb,info->grouping-1,24);  /* residue vectors to group and
 134                                              code with a partitioned book */
 135   oggpack_write(opb,info->partitions-1,6); /* possible partition choices */
 136   oggpack_write(opb,info->groupbook,8);  /* group huffman book */
 137
 138   /* secondstages is a bitmask; as encoding progresses pass by pass, a
 139      bitmask of one indicates this partition class has bits to write
 140      this pass */
 141   for(j=0;j<info->partitions;j++){
 142     if(ilog(info->secondstages[j])>3){
 143       /* yes, this is a minor hack due to not thinking ahead */
 144       oggpack_write(opb,info->secondstages[j],3);
 145       oggpack_write(opb,1,1);
 146       oggpack_write(opb,info->secondstages[j]>>3,5);
 147     }else
 148       oggpack_write(opb,info->secondstages[j],4); /* trailing zero */
 149     acc+=icount(info->secondstages[j]);
 150   }
 151   for(j=0;j<acc;j++)
 152     oggpack_write(opb,info->booklist[j],8);
 153
 154 }
 155
 156 /* vorbis_info is for range checking */
 157 vorbis_info_residue *res0_unpack(vorbis_info *vi,oggpack_buffer *opb){
 158   int j,acc=0;
 159   vorbis_info_residue0 *info=_ogg_calloc(1,sizeof(vorbis_info_residue0));
 160   codec_setup_info     *ci=vi->codec_setup;
 161
 162   info->begin=oggpack_read(opb,24);
 163   info->end=oggpack_read(opb,24);
 164   info->grouping=oggpack_read(opb,24)+1;
 165   info->partitions=oggpack_read(opb,6)+1;
 166   info->groupbook=oggpack_read(opb,8);
 167
 168   for(j=0;j<info->partitions;j++){
 169     int cascade=oggpack_read(opb,3);
 170     if(oggpack_read(opb,1))
 171       cascade|=(oggpack_read(opb,5)<<3);
 172     info->secondstages[j]=cascade;
 173
 174     acc+=icount(cascade);
 175   }
 176   for(j=0;j<acc;j++)
 177     info->booklist[j]=oggpack_read(opb,8);
 178
 179   if(info->groupbook>=ci->books)goto errout;
 180   for(j=0;j<acc;j++)
 181     if(info->booklist[j]>=ci->books)goto errout;
 182
 183   return(info);
 184  errout:
 185   res0_free_info(info);
 186   return(NULL);
 187 }
 188
 189 vorbis_look_residue *res0_look (vorbis_dsp_state *vd,vorbis_info_mode *vm,
 190                           vorbis_info_residue *vr){
 191   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
 192   vorbis_look_residue0 *look=_ogg_calloc(1,sizeof(vorbis_look_residue0));
 193   backend_lookup_state *be=vd->backend_state;
 194
 195   int j,k,acc=0;
 196   int dim;
 197   int maxstage=0;
 198   look->info=info;
 199   look->map=vm->mapping;
 200
 201   look->parts=info->partitions;
 202   look->fullbooks=be->fullbooks;
 203   look->phrasebook=be->fullbooks+info->groupbook;
 204   dim=look->phrasebook->dim;
 205
 206   look->partbooks=_ogg_calloc(look->parts,sizeof(codebook **));
 207
 208   for(j=0;j<look->parts;j++){
 209     int stages=ilog(info->secondstages[j]);
 210     if(stages){
 211       if(stages>maxstage)maxstage=stages;
 212       look->partbooks[j]=_ogg_calloc(stages,sizeof(codebook *));
 213       for(k=0;k<stages;k++)
 214         if(info->secondstages[j]&(1<<k))
 215           look->partbooks[j][k]=be->fullbooks+info->booklist[acc++];
 216     }
 217   }
 218
 219   look->partvals=rint(pow(look->parts,dim));
 220   look->stages=maxstage;
 221   look->decodemap=_ogg_malloc(look->partvals*sizeof(int *));
 222   for(j=0;j<look->partvals;j++){
 223     long val=j;
 224     long mult=look->partvals/look->parts;
 225     look->decodemap[j]=_ogg_malloc(dim*sizeof(int));
 226     for(k=0;k<dim;k++){
 227       long deco=val/mult;
 228       val-=deco*mult;
 229       mult/=look->parts;
 230       look->decodemap[j][k]=deco;
 231     }
 232   }
 233
 234   return(look);
 235 }
 236
 237
 238 /* does not guard against invalid settings; eg, a subn of 16 and a
 239    subgroup request of 32.  Max subn of 128 */
 240 static int _interleaved_testhack(float *vec,int n,vorbis_look_residue0 *look,
 241                                  int auxparts,int auxpartnum){
 242   vorbis_info_residue0 *info=look->info;
 243   int i,j=0;
 244   float max,localmax=0.f;
 245   float temp[128];
 246   float entropy[8];
 247
 248   /* setup */
 249   for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
 250
 251   /* handle case subgrp==1 outside */
 252   for(i=0;i<n;i++)
 253     if(temp[i]>localmax)localmax=temp[i];
 254   max=localmax;
 255
 256   for(i=0;i<n;i++)temp[i]=rint(temp[i]);
 257
 258   while(1){
 259     entropy[j]=localmax;
 260     n>>=1;
 261     if(!n)break;
 262     j++;
 263
 264     for(i=0;i<n;i++){
 265       temp[i]+=temp[i+n];
 266     }
 267     localmax=0.f;
 268     for(i=0;i<n;i++)
 269       if(temp[i]>localmax)localmax=temp[i];
 270   }
 271
 272   for(i=0;i<auxparts-1;i++)
 273     if(auxpartnum<info->blimit[i] &&
 274        entropy[info->subgrp[i]]<=info->entmax[i] &&
 275        max<=info->ampmax[i])
 276       break;
 277
 278   return(i);
 279 }
 280
 281 static int _testhack(float *vec,int n,vorbis_look_residue0 *look,
 282                      int auxparts,int auxpartnum){
 283   vorbis_info_residue0 *info=look->info;
 284   int i,j=0;
 285   float max,localmax=0.f;
 286   float temp[128];
 287   float entropy[8];
 288
 289   /* setup */
 290   for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
 291
 292   /* handle case subgrp==1 outside */
 293   for(i=0;i<n;i++)
 294     if(temp[i]>localmax)localmax=temp[i];
 295   max=localmax;
 296
 297   for(i=0;i<n;i++)temp[i]=rint(temp[i]);
 298
 299   while(n){
 300     entropy[j]=localmax;
 301     n>>=1;
 302     j++;
 303     if(!n)break;
 304     for(i=0;i<n;i++){
 305       temp[i]=temp[i*2]+temp[i*2+1];
 306     }
 307     localmax=0.f;
 308     for(i=0;i<n;i++)
 309       if(temp[i]>localmax)localmax=temp[i];
 310   }
 311
 312   for(i=0;i<auxparts-1;i++)
 313     if(auxpartnum<info->blimit[i] &&
 314        entropy[info->subgrp[i]]<=info->entmax[i] &&
 315        max<=info->ampmax[i])
 316       break;
 317
 318   return(i);
 319 }
 320
 321 static int _interleaved_encodepart(oggpack_buffer *opb,float *vec, int n,
 322                                    codebook *book,vorbis_look_residue0 *look){
 323   int i,bits=0;
 324   int dim=book->dim;
 325   int step=n/dim;
 326 #ifdef TRAIN_RESENT
 327   char buf[80];
 328   FILE *f;
 329   sprintf(buf,"res0_b%d.vqd",book-look->fullbooks);
 330   f=fopen(buf,"a");
 331 #endif
 332
 333   for(i=0;i<step;i++){
 334     int entry=vorbis_book_besterror(book,vec+i,step,0);
 335
 336 #ifdef TRAIN_RESENT
 337     fprintf(f,"%d\n",entry);
 338 #endif
 339
 340     bits+=vorbis_book_encode(book,entry,opb);
 341   }
 342
 343 #ifdef TRAIN_RESENT
 344   fclose(f);
 345 #endif
 346   return(bits);
 347 }
 348
 349 static int _encodepart(oggpack_buffer *opb,float *vec, int n,
 350                        codebook *book,vorbis_look_residue0 *look){
 351   int i,bits=0;
 352   int dim=book->dim;
 353   int step=n/dim;
 354 #ifdef TRAIN_RESENT
 355   char buf[80];
 356   FILE *f;
 357   sprintf(buf,"res0_b%d.vqd",book-look->fullbooks);
 358   f=fopen(buf,"a");
 359 #endif
 360
 361   for(i=0;i<step;i++){
 362     int entry=vorbis_book_besterror(book,vec+i*dim,1,0);
 363
 364 #ifdef TRAIN_RESENT
 365     fprintf(f,"%d\n",entry);
 366 #endif
 367
 368     bits+=vorbis_book_encode(book,entry,opb);
 369   }
 370
 371 #ifdef TRAIN_RESENT
 372   fclose(f);
 373 #endif
 374   return(bits);
 375 }
 376
 377 static int _01forward(vorbis_block *vb,vorbis_look_residue *vl,
 378                       float **in,int ch,
 379                       int (*classify)(float *,int,vorbis_look_residue0 *,
 380                                       int,int),
 381                       int (*encode)(oggpack_buffer *,float *,int,
 382                                     codebook *,vorbis_look_residue0 *)){
 383   long i,j,k,l,s;
 384   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 385   vorbis_info_residue0 *info=look->info;
 386
 387   /* move all this setup out later */
 388   int samples_per_partition=info->grouping;
 389   int possible_partitions=info->partitions;
 390   int partitions_per_word=look->phrasebook->dim;
 391   int n=info->end-info->begin;
 392
 393   int partvals=n/samples_per_partition;
 394   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 395   long **partword=_vorbis_block_alloc(vb,ch*sizeof(long *));
 396
 397 #ifdef TRAIN_RES
 398   FILE *of;
 399   char buffer[80];
 400   int m;
 401
 402   for(i=0;i<ch;i++){
 403     sprintf(buffer,"residue_%d.vqd",vb->mode);
 404     of=fopen(buffer,"a");
 405     for(m=0;m<info->end;m++)
 406       fprintf(of,"%.2f, ",in[i][m]);
 407     fprintf(of,"\n");
 408     fclose(of);
 409   }
 410
 411 #endif
 412
 413   partvals=partwords*partitions_per_word;
 414
 415   /* we find the patition type for each partition of each
 416      channel.  We'll go back and do the interleaved encoding in a
 417      bit.  For now, clarity */
 418
 419   for(i=0;i<ch;i++){
 420     partword[i]=_vorbis_block_alloc(vb,n/samples_per_partition*sizeof(long));
 421     memset(partword[i],0,n/samples_per_partition*sizeof(long));
 422   }
 423
 424   for(i=info->begin,l=0;i<info->end;i+=samples_per_partition,l++){
 425     for(j=0;j<ch;j++)
 426       /* do the partition decision based on the 'entropy'
 427          int the block */
 428       partword[j][l]=
 429         classify(in[j]+i,samples_per_partition,look,possible_partitions,l);
 430
 431   }
 432
 433   /* we code the partition words for each channel, then the residual
 434      words for a partition per channel until we've written all the
 435      residual words for that partition word.  Then write the next
 436      partition channel words... */
 437
 438   /*look->frames++;*/
 439   for(s=0;s<look->stages;s++){
 440     for(i=info->begin,l=0;i<info->end;){
 441
 442       /* first we encode a partition codeword for each channel */
 443       if(s==0){
 444         for(j=0;j<ch;j++){
 445           long val=partword[j][l];
 446           long ret;
 447           for(k=1;k<partitions_per_word;k++)
 448             val= val*possible_partitions+partword[j][l+k];
 449           ret=vorbis_book_encode(look->phrasebook,val,&vb->opb);
 450           /*look->phrasebits+=ret;*/
 451         }
 452       }
 453
 454       /* now we encode interleaved residual values for the partitions */
 455       for(k=0;k<partitions_per_word;k++,l++,i+=samples_per_partition){
 456
 457         for(j=0;j<ch;j++){
 458           /*if(s==0)look->resvals[partword[j][l]]++;*/
 459           if(info->secondstages[partword[j][l]]&(1<<s)){
 460             codebook *statebook=look->partbooks[partword[j][l]][s];
 461             if(statebook){
 462               int ret=encode(&vb->opb,in[j]+i,samples_per_partition,
 463                              statebook,look);
 464               /*look->resbits[partword[j][l]][s]+=ret;
 465                 look->resbitsflat+=ret;*/
 466
 467             }
 468           }
 469         }
 470       }
 471     }
 472   }
 473
 474   return(0);
 475 }
 476
 477 /* a truncated packet here just means 'stop working'; it's not an error */
 478 static int _01inverse(vorbis_block *vb,vorbis_look_residue *vl,
 479                       float **in,int ch,
 480                       long (*decodepart)(codebook *, float *,
 481                                          oggpack_buffer *,int)){
 482
 483   long i,j,k,l,s;
 484   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 485   vorbis_info_residue0 *info=look->info;
 486
 487   /* move all this setup out later */
 488   int samples_per_partition=info->grouping;
 489   int partitions_per_word=look->phrasebook->dim;
 490   int n=info->end-info->begin;
 491
 492   int partvals=n/samples_per_partition;
 493   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 494   int ***partword=alloca(ch*sizeof(int **));
 495   partvals=partwords*partitions_per_word;
 496
 497   for(j=0;j<ch;j++)
 498     partword[j]=_vorbis_block_alloc(vb,partwords*sizeof(int *));
 499
 500   for(s=0;s<look->stages;s++){
 501     for(i=info->begin,l=0;i<info->end;l++){
 502
 503       if(s==0){
 504         /* fetch the partition word for each channel */
 505         for(j=0;j<ch;j++){
 506           int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 507           if(temp==-1)goto eopbreak;
 508           partword[j][l]=look->decodemap[temp];
 509           if(partword[j][l]==NULL)goto errout;
 510         }
 511       }
 512
 513       /* now we decode residual values for the partitions */
 514       for(k=0;k<partitions_per_word;k++,i+=samples_per_partition)
 515         for(j=0;j<ch;j++){
 516           if(info->secondstages[partword[j][l][k]]&(1<<s)){
 517             codebook *stagebook=look->partbooks[partword[j][l][k]][s];
 518             if(stagebook){
 519               if(decodepart(stagebook,in[j]+i,&vb->opb,
 520                             samples_per_partition)==-1)goto eopbreak;
 521             }
 522           }
 523         }
 524     }
 525   }
 526
 527  errout:
 528  eopbreak:
 529   return(0);
 530 }
 531
 532 /* residue 0 and 1 are just slight variants of one another. 0 is
 533    interleaved, 1 is not */
 534 int res0_forward(vorbis_block *vb,vorbis_look_residue *vl,
 535             float **in,int ch){
 536   return(_01forward(vb,vl,in,ch,_interleaved_testhack,_interleaved_encodepart));
 537 }
 538
 539 int res0_inverse(vorbis_block *vb,vorbis_look_residue *vl,float **in,int ch){
 540   return(_01inverse(vb,vl,in,ch,vorbis_book_decodevs_add));
 541 }
 542
 543 int res1_forward(vorbis_block *vb,vorbis_look_residue *vl,
 544                  float **in,int ch){
 545   return(_01forward(vb,vl,in,ch,_testhack,_encodepart));
 546 }
 547
 548 int res1_inverse(vorbis_block *vb,vorbis_look_residue *vl,float **in,int ch){
 549   return(_01inverse(vb,vl,in,ch,vorbis_book_decodev_add));
 550 }
 551
 552 /* res2 is slightly more different; all the channels are interleaved
 553    into a single vector and encoded. */
 554 int res2_forward(vorbis_block *vb,vorbis_look_residue *vl,
 555             float **in,int ch){
 556   long i,j,k,n=vb->pcmend/2;
 557
 558   /* don't duplicate the code; use a working vector hack for now and
 559      reshape ourselves into a single channel res1 */
 560   float *work=_vorbis_block_alloc(vb,ch*n*sizeof(float));
 561   for(i=0;i<ch;i++){
 562     float *pcm=vb->pcm[i];
 563     for(j=0,k=i;j<n;j++,k+=ch)
 564       work[k]=pcm[j];
 565   }
 566
 567   return(_01forward(vb,vl,&work,1,_testhack,_encodepart));
 568 }
 569
 570 /* duplicate code here as speed is somewhat more important */
 571 int res2_inverse(vorbis_block *vb,vorbis_look_residue *vl,float **in,int ch){
 572   long i,k,l,s;
 573   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 574   vorbis_info_residue0 *info=look->info;
 575
 576   /* move all this setup out later */
 577   int samples_per_partition=info->grouping;
 578   int partitions_per_word=look->phrasebook->dim;
 579   int n=info->end-info->begin;
 580
 581   int partvals=n/samples_per_partition;
 582   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 583   int **partword=_vorbis_block_alloc(vb,partwords*sizeof(int *));
 584   partvals=partwords*partitions_per_word;
 585
 586   for(s=0;s<look->stages;s++){
 587     for(i=info->begin,l=0;i<info->end;l++){
 588
 589       if(s==0){
 590         /* fetch the partition word */
 591         int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 592         if(temp==-1)goto eopbreak;
 593         partword[l]=look->decodemap[temp];
 594         if(partword[l]==NULL)goto errout;
 595       }
 596
 597       /* now we decode residual values for the partitions */
 598       for(k=0;k<partitions_per_word;k++,i+=samples_per_partition)
 599         if(info->secondstages[partword[l][k]]&(1<<s)){
 600           codebook *stagebook=look->partbooks[partword[l][k]][s];
 601
 602           if(stagebook){
 603             if(vorbis_book_decodevv_add(stagebook,in,i,ch,
 604                                         &vb->opb,samples_per_partition)==-1)
 605               goto eopbreak;
 606           }
 607         }
 608     }
 609   }
 610
 611  errout:
 612  eopbreak:
 613   return(0);
 614 }
 615
 616
 617 vorbis_func_residue residue0_exportbundle={
 618   &res0_pack,
 619   &res0_unpack,
 620   &res0_look,
 621   &res0_copy_info,
 622   &res0_free_info,
 623   &res0_free_look,
 624   &res0_forward,
 625   &res0_inverse
 626 };
 627
 628 vorbis_func_residue residue1_exportbundle={
 629   &res0_pack,
 630   &res0_unpack,
 631   &res0_look,
 632   &res0_copy_info,
 633   &res0_free_info,
 634   &res0_free_look,
 635   &res1_forward,
 636   &res1_inverse
 637 };
 638
 639 vorbis_func_residue residue2_exportbundle={
 640   &res0_pack,
 641   &res0_unpack,
 642   &res0_look,
 643   &res0_copy_info,
 644   &res0_free_info,
 645   &res0_free_look,
 646   &res2_forward,
 647   &res2_inverse
 648 };