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.41 2001/12/19 23:13:33 segher 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 <ogg/ogg.h>
  27 #include "vorbis/codec.h"
  28 #include "codec_internal.h"
  29 #include "registry.h"
  30 #include "codebook.h"
  31 #include "misc.h"
  32 #include "os.h"
  33
  34 #ifdef TRAIN_RES
  35 #include <stdio.h>
  36 #endif
  37
  38 typedef struct {
  39   vorbis_info_residue0 *info;
  40   int         map;
  41
  42   int         parts;
  43   int         stages;
  44   codebook   *fullbooks;
  45   codebook   *phrasebook;
  46   codebook ***partbooks;
  47
  48   int         partvals;
  49   int       **decodemap;
  50
  51   long      postbits;
  52   long      phrasebits;
  53   long      frames;
  54
  55   int       qoffsets[BITTRACK_DIVISOR+1];
  56
  57 #ifdef TRAIN_RES
  58   long      *training_data[8][64];
  59   float      training_max[8][64];
  60   float      training_min[8][64];
  61   int       longp;
  62   float     tmin;
  63   float     tmax;
  64 #endif
  65
  66 } vorbis_look_residue0;
  67
  68 vorbis_info_residue *res0_copy_info(vorbis_info_residue *vr){
  69   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  70   vorbis_info_residue0 *ret=_ogg_malloc(sizeof(*ret));
  71   memcpy(ret,info,sizeof(*ret));
  72   return(ret);
  73 }
  74
  75 void res0_free_info(vorbis_info_residue *i){
  76   vorbis_info_residue0 *info=(vorbis_info_residue0 *)i;
  77   if(info){
  78     memset(info,0,sizeof(*info));
  79     _ogg_free(info);
  80   }
  81 }
  82
  83 void res0_free_look(vorbis_look_residue *i){
  84   int j;
  85   if(i){
  86
  87     vorbis_look_residue0 *look=(vorbis_look_residue0 *)i;
  88
  89 #ifdef TRAIN_RES
  90     {
  91       int j,k,l;
  92       for(j=0;j<look->parts;j++){
  93         fprintf(stderr,"partition %d: ",j);
  94         for(k=0;k<8;k++)
  95           if(look->training_data[k][j]){
  96             char buffer[80];
  97             FILE *of;
  98             codebook *statebook=look->partbooks[j][k];
  99
 100             /* long and short into the same bucket by current convention */
 101             sprintf(buffer,"res_part%d_pass%d.vqd",j,k);
 102             of=fopen(buffer,"a");
 103
 104             for(l=0;l<statebook->entries;l++)
 105               fprintf(of,"%d:%ld\n",l,look->training_data[k][j][l]);
 106
 107             fclose(of);
 108
 109             fprintf(stderr,"%d(%.2f|%.2f) ",k,look->training_min[k][j],look->training_max[k][j]);
 110
 111             _ogg_free(look->training_data[k][j]);
 112           }
 113         fprintf(stderr,"\n");
 114       }
 115     }
 116     fprintf(stderr,"min/max residue: %g::%g\n",look->tmin,look->tmax);
 117
 118     fprintf(stderr,"residue bit usage %f:%f (%f total)\n",
 119             (float)look->phrasebits/look->frames,
 120             (float)look->postbits/look->frames,
 121             (float)(look->postbits+look->phrasebits)/look->frames);
 122 #endif
 123
 124
 125     /*vorbis_info_residue0 *info=look->info;
 126
 127     fprintf(stderr,
 128             "%ld frames encoded in %ld phrasebits and %ld residue bits "
 129             "(%g/frame) \n",look->frames,look->phrasebits,
 130             look->resbitsflat,
 131             (look->phrasebits+look->resbitsflat)/(float)look->frames);
 132
 133     for(j=0;j<look->parts;j++){
 134       long acc=0;
 135       fprintf(stderr,"\t[%d] == ",j);
 136       for(k=0;k<look->stages;k++)
 137         if((info->secondstages[j]>>k)&1){
 138           fprintf(stderr,"%ld,",look->resbits[j][k]);
 139           acc+=look->resbits[j][k];
 140         }
 141
 142       fprintf(stderr,":: (%ld vals) %1.2fbits/sample\n",look->resvals[j],
 143               acc?(float)acc/(look->resvals[j]*info->grouping):0);
 144     }
 145     fprintf(stderr,"\n");*/
 146
 147     for(j=0;j<look->parts;j++)
 148       if(look->partbooks[j])_ogg_free(look->partbooks[j]);
 149     _ogg_free(look->partbooks);
 150     for(j=0;j<look->partvals;j++)
 151       _ogg_free(look->decodemap[j]);
 152     _ogg_free(look->decodemap);
 153
 154     memset(look,0,sizeof(*look));
 155     _ogg_free(look);
 156   }
 157 }
 158
 159 static int ilog(unsigned int v){
 160   int ret=0;
 161   while(v){
 162     ret++;
 163     v>>=1;
 164   }
 165   return(ret);
 166 }
 167
 168 static int icount(unsigned int v){
 169   int ret=0;
 170   while(v){
 171     ret+=v&1;
 172     v>>=1;
 173   }
 174   return(ret);
 175 }
 176
 177
 178 void res0_pack(vorbis_info_residue *vr,oggpack_buffer *opb){
 179   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
 180   int j,acc=0;
 181   oggpack_write(opb,info->begin,24);
 182   oggpack_write(opb,info->end,24);
 183
 184   oggpack_write(opb,info->grouping-1,24);  /* residue vectors to group and
 185                                              code with a partitioned book */
 186   oggpack_write(opb,info->partitions-1,6); /* possible partition choices */
 187   oggpack_write(opb,info->groupbook,8);  /* group huffman book */
 188
 189   /* secondstages is a bitmask; as encoding progresses pass by pass, a
 190      bitmask of one indicates this partition class has bits to write
 191      this pass */
 192   for(j=0;j<info->partitions;j++){
 193     if(ilog(info->secondstages[j])>3){
 194       /* yes, this is a minor hack due to not thinking ahead */
 195       oggpack_write(opb,info->secondstages[j],3);
 196       oggpack_write(opb,1,1);
 197       oggpack_write(opb,info->secondstages[j]>>3,5);
 198     }else
 199       oggpack_write(opb,info->secondstages[j],4); /* trailing zero */
 200     acc+=icount(info->secondstages[j]);
 201   }
 202   for(j=0;j<acc;j++)
 203     oggpack_write(opb,info->booklist[j],8);
 204
 205 }
 206
 207 /* vorbis_info is for range checking */
 208 vorbis_info_residue *res0_unpack(vorbis_info *vi,oggpack_buffer *opb){
 209   int j,acc=0;
 210   vorbis_info_residue0 *info=_ogg_calloc(1,sizeof(*info));
 211   codec_setup_info     *ci=vi->codec_setup;
 212
 213   info->begin=oggpack_read(opb,24);
 214   info->end=oggpack_read(opb,24);
 215   info->grouping=oggpack_read(opb,24)+1;
 216   info->partitions=oggpack_read(opb,6)+1;
 217   info->groupbook=oggpack_read(opb,8);
 218
 219   for(j=0;j<info->partitions;j++){
 220     int cascade=oggpack_read(opb,3);
 221     if(oggpack_read(opb,1))
 222       cascade|=(oggpack_read(opb,5)<<3);
 223     info->secondstages[j]=cascade;
 224
 225     acc+=icount(cascade);
 226   }
 227   for(j=0;j<acc;j++)
 228     info->booklist[j]=oggpack_read(opb,8);
 229
 230   if(info->groupbook>=ci->books)goto errout;
 231   for(j=0;j<acc;j++)
 232     if(info->booklist[j]>=ci->books)goto errout;
 233
 234   return(info);
 235  errout:
 236   res0_free_info(info);
 237   return(NULL);
 238 }
 239
 240 vorbis_look_residue *res0_look(vorbis_dsp_state *vd,vorbis_info_mode *vm,
 241                           vorbis_info_residue *vr){
 242   vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
 243   vorbis_look_residue0 *look=_ogg_calloc(1,sizeof(*look));
 244   backend_lookup_state *be=vd->backend_state;
 245
 246   int j,k,acc=0;
 247   int dim;
 248   int maxstage=0;
 249   look->info=info;
 250   look->map=vm->mapping;
 251
 252   look->parts=info->partitions;
 253   look->fullbooks=be->fullbooks;
 254   look->phrasebook=be->fullbooks+info->groupbook;
 255   dim=look->phrasebook->dim;
 256
 257   look->partbooks=_ogg_calloc(look->parts,sizeof(*look->partbooks));
 258
 259   for(j=0;j<look->parts;j++){
 260     int stages=ilog(info->secondstages[j]);
 261     if(stages){
 262       if(stages>maxstage)maxstage=stages;
 263       look->partbooks[j]=_ogg_calloc(stages,sizeof(*look->partbooks[j]));
 264       for(k=0;k<stages;k++)
 265         if(info->secondstages[j]&(1<<k)){
 266           look->partbooks[j][k]=be->fullbooks+info->booklist[acc++];
 267 #ifdef TRAIN_RES
 268           look->training_data[k][j]=calloc(look->partbooks[j][k]->entries,
 269                                            sizeof(***look->training_data));
 270 #endif
 271         }
 272     }
 273   }
 274
 275   look->partvals=rint(pow(look->parts,dim));
 276   look->stages=maxstage;
 277   look->decodemap=_ogg_malloc(look->partvals*sizeof(*look->decodemap));
 278   for(j=0;j<look->partvals;j++){
 279     long val=j;
 280     long mult=look->partvals/look->parts;
 281     look->decodemap[j]=_ogg_malloc(dim*sizeof(*look->decodemap[j]));
 282     for(k=0;k<dim;k++){
 283       long deco=val/mult;
 284       val-=deco*mult;
 285       mult/=look->parts;
 286       look->decodemap[j][k]=deco;
 287     }
 288   }
 289
 290   {
 291     int samples_per_partition=info->grouping;
 292     int n=info->end-info->begin,i;
 293     int partvals=n/samples_per_partition;
 294
 295     for(i=0;i<BITTRACK_DIVISOR;i++)
 296       look->qoffsets[i]=partvals*(i+1)/BITTRACK_DIVISOR;
 297
 298     look->qoffsets[i]=9999999;
 299   }
 300
 301   return(look);
 302 }
 303
 304
 305 #if 0
 306 /* does not guard against invalid settings; eg, a subn of 16 and a
 307    subgroup request of 32.  Max subn of 128 */
 308 static int _interleaved_testhack(float *vec,int n,vorbis_look_residue0 *look,
 309                                  int auxparts,int auxpartnum){
 310   vorbis_info_residue0 *info=look->info;
 311   int i,j=0;
 312   float max,localmax=0.f;
 313   float temp[128];
 314   float entropy[8];
 315
 316   /* setup */
 317   for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
 318
 319   /* handle case subgrp==1 outside */
 320   for(i=0;i<n;i++)
 321     if(temp[i]>localmax)localmax=temp[i];
 322   max=localmax;
 323
 324   for(i=0;i<n;i++)temp[i]=rint(temp[i]);
 325
 326   while(1){
 327     entropy[j]=localmax;
 328     n>>=1;
 329     if(!n)break;
 330     j++;
 331
 332     for(i=0;i<n;i++){
 333       temp[i]+=temp[i+n];
 334     }
 335     localmax=0.f;
 336     for(i=0;i<n;i++)
 337       if(temp[i]>localmax)localmax=temp[i];
 338   }
 339
 340   for(i=0;i<auxparts-1;i++)
 341     if(auxpartnum<info->blimit[i] &&
 342        entropy[info->subgrp[i]]<=info->entmax[i] &&
 343        max<=info->ampmax[i])
 344       break;
 345
 346   return(i);
 347 }
 348 #endif
 349
 350
 351 static int _testhack(float *vec,int n,vorbis_look_residue0 *look,
 352                      int auxparts,int auxpartnum){
 353   vorbis_info_residue0 *info=look->info;
 354   int i;
 355   float max=0.f;
 356   float temp[128];
 357   float entropy=0.f;
 358
 359   /* setup */
 360   for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
 361
 362   for(i=0;i<n;i++)
 363     if(temp[i]>max)max=temp[i];
 364
 365   for(i=0;i<n;i++)temp[i]=rint(temp[i]);
 366
 367   for(i=0;i<n;i++)
 368     entropy+=temp[i];
 369
 370   for(i=0;i<auxparts-1;i++)
 371     if(auxpartnum<info->blimit[i] &&
 372        entropy<=info->entmax[i] &&
 373        max<=info->ampmax[i])
 374       break;
 375
 376   return(i);
 377 }
 378
 379 static int _interleaved_encodepart(oggpack_buffer *opb,float *vec, int n,
 380                                    codebook *book,long *acc){
 381   int i,bits=0;
 382   int dim=book->dim;
 383   int step=n/dim;
 384
 385   for(i=0;i<step;i++){
 386     int entry=vorbis_book_besterror(book,vec+i,step,0);
 387
 388 #ifdef TRAIN_RES
 389     acc[entry]++;
 390 #endif
 391
 392     bits+=vorbis_book_encode(book,entry,opb);
 393   }
 394
 395   return(bits);
 396 }
 397
 398 static int _encodepart(oggpack_buffer *opb,float *vec, int n,
 399                        codebook *book,long *acc){
 400   int i,bits=0;
 401   int dim=book->dim;
 402   int step=n/dim;
 403
 404   for(i=0;i<step;i++){
 405     int entry=vorbis_book_besterror(book,vec+i*dim,1,0);
 406
 407 #ifdef TRAIN_RES
 408     acc[entry]++;
 409 #endif
 410
 411     bits+=vorbis_book_encode(book,entry,opb);
 412   }
 413
 414   return(bits);
 415 }
 416
 417 static long **_01class(vorbis_block *vb,vorbis_look_residue *vl,
 418                        float **in,int ch,
 419                        int (*classify)(float *,int,vorbis_look_residue0 *,
 420                                        int,int)){
 421   long i,j;
 422   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 423   vorbis_info_residue0 *info=look->info;
 424
 425   /* move all this setup out later */
 426   int samples_per_partition=info->grouping;
 427   int possible_partitions=info->partitions;
 428   int n=info->end-info->begin;
 429
 430   int partvals=n/samples_per_partition;
 431   long **partword=_vorbis_block_alloc(vb,ch*sizeof(*partword));
 432
 433   /* we find the partition type for each partition of each
 434      channel.  We'll go back and do the interleaved encoding in a
 435      bit.  For now, clarity */
 436
 437   for(i=0;i<ch;i++){
 438     partword[i]=_vorbis_block_alloc(vb,n/samples_per_partition*sizeof(*partword[i]));
 439     memset(partword[i],0,n/samples_per_partition*sizeof(*partword[i]));
 440   }
 441
 442   for(i=0;i<partvals;i++){
 443     for(j=0;j<ch;j++)
 444       /* do the partition decision based on the 'entropy'
 445          int the block */
 446       partword[j][i]=
 447         classify(in[j]+i*samples_per_partition+info->begin,
 448                  samples_per_partition,look,possible_partitions,i);
 449
 450   }
 451
 452 #ifdef TRAIN_RES
 453   look->longp=vb->W;
 454   {
 455     FILE *of;
 456     char buffer[80];
 457
 458     for(i=0;i<ch;i++){
 459       sprintf(buffer,"resaux_%s.vqd",(vb->mode?"long":"short"));
 460       of=fopen(buffer,"a");
 461       for(j=0;j<partvals;j++)
 462         fprintf(of,"%ld, ",partword[i][j]);
 463       fprintf(of,"\n");
 464       fclose(of);
 465     }
 466   }
 467 #endif
 468   look->frames++;
 469
 470   return(partword);
 471 }
 472
 473 static long **_2class(vorbis_block *vb,vorbis_look_residue *vl,
 474                        float **in,int ch,
 475                        int (*classify)(float *,int,vorbis_look_residue0 *,
 476                                        int,int)){
 477   long i,j,k,l;
 478   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 479   vorbis_info_residue0 *info=look->info;
 480
 481   /* move all this setup out later */
 482   int samples_per_partition=info->grouping;
 483   int possible_partitions=info->partitions;
 484   int n=info->end-info->begin;
 485
 486   int partvals=n/samples_per_partition;
 487   long **partword=_vorbis_block_alloc(vb,sizeof(*partword));
 488   float *work=alloca(sizeof(*work)*samples_per_partition);
 489
 490 #ifdef TRAIN_RES
 491   FILE *of;
 492   char buffer[80];
 493 #endif
 494
 495   partword[0]=_vorbis_block_alloc(vb,n*ch/samples_per_partition*sizeof(*partword[0]));
 496   memset(partword[0],0,n*ch/samples_per_partition*sizeof(*partword[0]));
 497
 498   for(i=0,j=0,k=0,l=info->begin;i<partvals;i++){
 499     for(k=0;k<samples_per_partition;k++){
 500       work[k]=in[j][l];
 501       j++;
 502       if(j>=ch){
 503         j=0;
 504         l++;
 505       }
 506     }
 507
 508     partword[0][i]=
 509       classify(work,samples_per_partition,look,possible_partitions,i);
 510
 511
 512   }
 513
 514 #ifdef TRAIN_RES
 515   look->longp=vb->W;
 516   sprintf(buffer,"resaux_%s.vqd",(vb->mode?"long":"short"));
 517   of=fopen(buffer,"a");
 518   for(i=0;i<partvals;i++)
 519     fprintf(of,"%ld, ",partword[0][i]);
 520   fprintf(of,"\n");
 521   fclose(of);
 522 #endif
 523
 524   look->frames++;
 525
 526   return(partword);
 527 }
 528
 529 static int _01forward(vorbis_block *vb,vorbis_look_residue *vl,
 530                       float **in,int ch,
 531                       int pass,long **partword,
 532                       int (*encode)(oggpack_buffer *,float *,int,
 533                                     codebook *,long *),
 534                       ogg_uint32_t *stats){
 535   long i,j,k,s;
 536   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 537   vorbis_info_residue0 *info=look->info;
 538
 539   vorbis_dsp_state      *vd=vb->vd;
 540   vorbis_info           *vi=vd->vi;
 541   codec_setup_info      *ci=vi->codec_setup;
 542
 543
 544   /* move all this setup out later */
 545   int samples_per_partition=info->grouping;
 546   int possible_partitions=info->partitions;
 547   int partitions_per_word=look->phrasebook->dim;
 548   int n=info->end-info->begin;
 549
 550   int partvals=n/samples_per_partition;
 551   long resbits[128];
 552   long resvals[128];
 553
 554 #ifdef TRAIN_RES
 555   for(i=0;i<ch;i++)
 556     for(j=info->begin;j<info->end;j++){
 557       if(in[i][j]>look->tmax)look->tmax=in[i][j];
 558       if(in[i][j]<look->tmin)look->tmin=in[i][j];
 559     }
 560 #endif
 561
 562   memset(resbits,0,sizeof(resbits));
 563   memset(resvals,0,sizeof(resvals));
 564
 565   /* we code the partition words for each channel, then the residual
 566      words for a partition per channel until we've written all the
 567      residual words for that partition word.  Then write the next
 568      partition channel words... */
 569
 570   for(s=(pass==0?0:ci->passlimit[pass-1]);s<ci->passlimit[pass];s++){
 571     int bin=0;
 572     ogg_uint32_t *qptr=NULL;
 573     if(stats)qptr=stats+s*BITTRACK_DIVISOR;
 574
 575     for(i=0;i<partvals;){
 576
 577       /* first we encode a partition codeword for each channel */
 578       if(s==0){
 579         for(j=0;j<ch;j++){
 580           long val=partword[j][i];
 581           long ret;
 582           for(k=1;k<partitions_per_word;k++){
 583             val*=possible_partitions;
 584             if(i+k<partvals)
 585               val+=partword[j][i+k];
 586           }
 587
 588           /* training hack */
 589           if(val<look->phrasebook->entries)
 590             look->phrasebits+=vorbis_book_encode(look->phrasebook,val,&vb->opb);
 591 #ifdef TRAIN_RES
 592           else
 593             fprintf(stderr,"!");
 594 #endif
 595
 596         }
 597       }
 598
 599       /* now we encode interleaved residual values for the partitions */
 600       for(k=0;k<partitions_per_word && i<partvals;k++,i++){
 601         long offset=i*samples_per_partition+info->begin;
 602
 603         if(qptr)while(i>=look->qoffsets[bin])
 604           qptr[bin++]=oggpack_bits(&vb->opb);
 605
 606         for(j=0;j<ch;j++){
 607           if(s==0)resvals[partword[j][i]]+=samples_per_partition;
 608           if(info->secondstages[partword[j][i]]&(1<<s)){
 609             codebook *statebook=look->partbooks[partword[j][i]][s];
 610             if(statebook){
 611               int ret;
 612               long *accumulator=NULL;
 613
 614 #ifdef TRAIN_RES
 615               accumulator=look->training_data[s][partword[j][i]];
 616               {
 617                 int l;
 618                 float *samples=in[j]+offset;
 619                 for(l=0;l<samples_per_partition;l++){
 620                   if(samples[l]<look->training_min[s][partword[j][i]])
 621                     look->training_min[s][partword[j][i]]=samples[l];
 622                   if(samples[l]>look->training_max[s][partword[j][i]])
 623                     look->training_max[s][partword[j][i]]=samples[l];
 624                 }
 625               }
 626 #endif
 627
 628               ret=encode(&vb->opb,in[j]+offset,samples_per_partition,
 629                          statebook,accumulator);
 630
 631               look->postbits+=ret;
 632               resbits[partword[j][i]]+=ret;
 633             }
 634           }
 635         }
 636       }
 637       if(qptr)while(i>=look->qoffsets[bin])
 638         qptr[bin++]=oggpack_bits(&vb->opb);
 639     }
 640   }
 641
 642   /*{
 643     long total=0;
 644     long totalbits=0;
 645     fprintf(stderr,"%d :: ",vb->mode);
 646     for(k=0;k<possible_partitions;k++){
 647       fprintf(stderr,"%ld/%1.2g, ",resvals[k],(float)resbits[k]/resvals[k]);
 648       total+=resvals[k];
 649       totalbits+=resbits[k];
 650       }
 651
 652     fprintf(stderr,":: %ld:%1.2g\n",total,(double)totalbits/total);
 653     }*/
 654   return(0);
 655 }
 656
 657 /* a truncated packet here just means 'stop working'; it's not an error */
 658 static int _01inverse(vorbis_block *vb,vorbis_look_residue *vl,
 659                       float **in,int ch,
 660                       long (*decodepart)(codebook *, float *,
 661                                          oggpack_buffer *,int)){
 662
 663   long i,j,k,l,s;
 664   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 665   vorbis_info_residue0 *info=look->info;
 666
 667   /* move all this setup out later */
 668   int samples_per_partition=info->grouping;
 669   int partitions_per_word=look->phrasebook->dim;
 670   int n=info->end-info->begin;
 671
 672   int partvals=n/samples_per_partition;
 673   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 674   int ***partword=alloca(ch*sizeof(*partword));
 675
 676   for(j=0;j<ch;j++)
 677     partword[j]=_vorbis_block_alloc(vb,partwords*sizeof(*partword[j]));
 678
 679   for(s=0;s<look->stages;s++){
 680
 681     /* each loop decodes on partition codeword containing
 682        partitions_pre_word partitions */
 683     for(i=0,l=0;i<partvals;l++){
 684       if(s==0){
 685         /* fetch the partition word for each channel */
 686         for(j=0;j<ch;j++){
 687           int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 688           if(temp==-1)goto eopbreak;
 689           partword[j][l]=look->decodemap[temp];
 690           if(partword[j][l]==NULL)goto errout;
 691         }
 692       }
 693
 694       /* now we decode residual values for the partitions */
 695       for(k=0;k<partitions_per_word && i<partvals;k++,i++)
 696         for(j=0;j<ch;j++){
 697           long offset=info->begin+i*samples_per_partition;
 698           if(info->secondstages[partword[j][l][k]]&(1<<s)){
 699             codebook *stagebook=look->partbooks[partword[j][l][k]][s];
 700             if(stagebook){
 701               if(decodepart(stagebook,in[j]+offset,&vb->opb,
 702                             samples_per_partition)==-1)goto eopbreak;
 703             }
 704           }
 705         }
 706     }
 707   }
 708
 709  errout:
 710  eopbreak:
 711   return(0);
 712 }
 713
 714 /* residue 0 and 1 are just slight variants of one another. 0 is
 715    interleaved, 1 is not */
 716 long **res0_class(vorbis_block *vb,vorbis_look_residue *vl,
 717                   float **in,int *nonzero,int ch){
 718   /* we encode only the nonzero parts of a bundle */
 719   int i,used=0;
 720   for(i=0;i<ch;i++)
 721     if(nonzero[i])
 722       in[used++]=in[i];
 723   if(used)
 724     /*return(_01class(vb,vl,in,used,_interleaved_testhack));*/
 725     return(_01class(vb,vl,in,used,_testhack));
 726   else
 727     return(0);
 728 }
 729
 730 int res0_forward(vorbis_block *vb,vorbis_look_residue *vl,
 731                  float **in,float **out,int *nonzero,int ch,
 732                  int pass, long **partword,ogg_uint32_t *stats){
 733   /* we encode only the nonzero parts of a bundle */
 734   int i,j,used=0,n=vb->pcmend/2;
 735   for(i=0;i<ch;i++)
 736     if(nonzero[i]){
 737       for(j=0;j<n;j++)
 738         out[i][j]+=in[i][j];
 739       in[used++]=in[i];
 740     }
 741   if(used){
 742     int ret=_01forward(vb,vl,in,used,pass,partword,
 743                       _interleaved_encodepart,stats);
 744     used=0;
 745     for(i=0;i<ch;i++)
 746       if(nonzero[i]){
 747         for(j=0;j<n;j++)
 748           out[i][j]-=in[used][j];
 749         used++;
 750       }
 751     return(ret);
 752   }else{
 753     for(i=0;i<vorbis_bitrate_maxmarkers();i++)
 754       stats[i]=oggpack_bits(&vb->opb);
 755
 756     return(0);
 757   }
 758 }
 759
 760 int res0_inverse(vorbis_block *vb,vorbis_look_residue *vl,
 761                  float **in,int *nonzero,int ch){
 762   int i,used=0;
 763   for(i=0;i<ch;i++)
 764     if(nonzero[i])
 765       in[used++]=in[i];
 766   if(used)
 767     return(_01inverse(vb,vl,in,used,vorbis_book_decodevs_add));
 768   else
 769     return(0);
 770 }
 771
 772 int res1_forward(vorbis_block *vb,vorbis_look_residue *vl,
 773                  float **in,float **out,int *nonzero,int ch,
 774                  int pass, long **partword, ogg_uint32_t *stats){
 775   int i,j,used=0,n=vb->pcmend/2;
 776   for(i=0;i<ch;i++)
 777     if(nonzero[i]){
 778       for(j=0;j<n;j++)
 779         out[i][j]+=in[i][j];
 780       in[used++]=in[i];
 781     }
 782
 783   if(used){
 784     int ret=_01forward(vb,vl,in,used,pass,partword,_encodepart,stats);
 785     used=0;
 786     for(i=0;i<ch;i++)
 787       if(nonzero[i]){
 788         for(j=0;j<n;j++)
 789           out[i][j]-=in[used][j];
 790         used++;
 791       }
 792     return(ret);
 793   }else{
 794     for(i=0;i<vorbis_bitrate_maxmarkers();i++)
 795       stats[i]=oggpack_bits(&vb->opb);
 796
 797     return(0);
 798   }
 799 }
 800
 801 long **res1_class(vorbis_block *vb,vorbis_look_residue *vl,
 802                   float **in,int *nonzero,int ch){
 803   int i,used=0;
 804   for(i=0;i<ch;i++)
 805     if(nonzero[i])
 806       in[used++]=in[i];
 807   if(used)
 808     return(_01class(vb,vl,in,used,_testhack));
 809   else
 810     return(0);
 811 }
 812
 813 int res1_inverse(vorbis_block *vb,vorbis_look_residue *vl,
 814                  float **in,int *nonzero,int ch){
 815   int i,used=0;
 816   for(i=0;i<ch;i++)
 817     if(nonzero[i])
 818       in[used++]=in[i];
 819   if(used)
 820     return(_01inverse(vb,vl,in,used,vorbis_book_decodev_add));
 821   else
 822     return(0);
 823 }
 824
 825 long **res2_class(vorbis_block *vb,vorbis_look_residue *vl,
 826                   float **in,int *nonzero,int ch){
 827   int i,used=0;
 828   for(i=0;i<ch;i++)
 829     if(nonzero[i])
 830       in[used++]=in[i];
 831   if(used)
 832     return(_2class(vb,vl,in,used,_testhack));
 833   else
 834     return(0);
 835 }
 836
 837 /* res2 is slightly more different; all the channels are interleaved
 838    into a single vector and encoded. */
 839
 840 int res2_forward(vorbis_block *vb,vorbis_look_residue *vl,
 841                  float **in,float **out,int *nonzero,int ch,
 842                  int pass,long **partword,ogg_uint32_t *stats){
 843   long i,j,k,n=vb->pcmend/2,used=0;
 844
 845   /* don't duplicate the code; use a working vector hack for now and
 846      reshape ourselves into a single channel res1 */
 847   /* ugly; reallocs for each coupling pass :-( */
 848   float *work=_vorbis_block_alloc(vb,ch*n*sizeof(*work));
 849   for(i=0;i<ch;i++){
 850     float *pcm=in[i];
 851     if(nonzero[i])used++;
 852     for(j=0,k=i;j<n;j++,k+=ch)
 853       work[k]=pcm[j];
 854   }
 855
 856   if(used){
 857     int ret=_01forward(vb,vl,&work,1,pass,partword,_encodepart,stats);
 858     /* update the sofar vector */
 859     for(i=0;i<ch;i++){
 860       float *pcm=in[i];
 861       float *sofar=out[i];
 862       for(j=0,k=i;j<n;j++,k+=ch)
 863         sofar[j]+=pcm[j]-work[k];
 864
 865     }
 866     return(ret);
 867   }else{
 868     for(i=0;i<vorbis_bitrate_maxmarkers();i++)
 869       stats[i]=oggpack_bits(&vb->opb);
 870
 871     return(0);
 872   }
 873 }
 874
 875 /* duplicate code here as speed is somewhat more important */
 876 int res2_inverse(vorbis_block *vb,vorbis_look_residue *vl,
 877                  float **in,int *nonzero,int ch){
 878   long i,k,l,s;
 879   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 880   vorbis_info_residue0 *info=look->info;
 881
 882   /* move all this setup out later */
 883   int samples_per_partition=info->grouping;
 884   int partitions_per_word=look->phrasebook->dim;
 885   int n=info->end-info->begin;
 886
 887   int partvals=n/samples_per_partition;
 888   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 889   int **partword=_vorbis_block_alloc(vb,partwords*sizeof(*partword));
 890
 891   for(i=0;i<ch;i++)if(nonzero[i])break;
 892   if(i==ch)return(0); /* no nonzero vectors */
 893
 894   for(s=0;s<look->stages;s++){
 895     for(i=0,l=0;i<partvals;l++){
 896
 897       if(s==0){
 898         /* fetch the partition word */
 899         int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 900         if(temp==-1)goto eopbreak;
 901         partword[l]=look->decodemap[temp];
 902         if(partword[l]==NULL)goto errout;
 903       }
 904
 905       /* now we decode residual values for the partitions */
 906       for(k=0;k<partitions_per_word && i<partvals;k++,i++)
 907         if(info->secondstages[partword[l][k]]&(1<<s)){
 908           codebook *stagebook=look->partbooks[partword[l][k]][s];
 909
 910           if(stagebook){
 911             if(vorbis_book_decodevv_add(stagebook,in,
 912                                         i*samples_per_partition+info->begin,ch,
 913                                         &vb->opb,samples_per_partition)==-1)
 914               goto eopbreak;
 915           }
 916         }
 917     }
 918   }
 919
 920  errout:
 921  eopbreak:
 922   return(0);
 923 }
 924
 925
 926 vorbis_func_residue residue0_exportbundle={
 927   &res0_pack,
 928   &res0_unpack,
 929   &res0_look,
 930   &res0_copy_info,
 931   &res0_free_info,
 932   &res0_free_look,
 933   &res0_class,
 934   &res0_forward,
 935   &res0_inverse
 936 };
 937
 938 vorbis_func_residue residue1_exportbundle={
 939   &res0_pack,
 940   &res0_unpack,
 941   &res0_look,
 942   &res0_copy_info,
 943   &res0_free_info,
 944   &res0_free_look,
 945   &res1_class,
 946   &res1_forward,
 947   &res1_inverse
 948 };
 949
 950 vorbis_func_residue residue2_exportbundle={
 951   &res0_pack,
 952   &res0_unpack,
 953   &res0_look,
 954   &res0_copy_info,
 955   &res0_free_info,
 956   &res0_free_look,
 957   &res2_class,
 958   &res2_forward,
 959   &res2_inverse
 960 };