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-2002             *
   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.45 2002/01/22 08:06:07 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 <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   codec_setup_info     *ci=vd->vi->codec_setup;
 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=ci->fullbooks;
 254   look->phrasebook=ci->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]=ci->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((float)look->parts,(float)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           for(k=1;k<partitions_per_word;k++){
 582             val*=possible_partitions;
 583             if(i+k<partvals)
 584               val+=partword[j][i+k];
 585           }
 586
 587           /* training hack */
 588           if(val<look->phrasebook->entries)
 589             look->phrasebits+=vorbis_book_encode(look->phrasebook,val,&vb->opb);
 590 #ifdef TRAIN_RES
 591           else
 592             fprintf(stderr,"!");
 593 #endif
 594
 595         }
 596       }
 597
 598       /* now we encode interleaved residual values for the partitions */
 599       for(k=0;k<partitions_per_word && i<partvals;k++,i++){
 600         long offset=i*samples_per_partition+info->begin;
 601
 602         if(qptr)while(i>=look->qoffsets[bin])
 603           qptr[bin++]=oggpack_bits(&vb->opb);
 604
 605         for(j=0;j<ch;j++){
 606           if(s==0)resvals[partword[j][i]]+=samples_per_partition;
 607           if(info->secondstages[partword[j][i]]&(1<<s)){
 608             codebook *statebook=look->partbooks[partword[j][i]][s];
 609             if(statebook){
 610               int ret;
 611               long *accumulator=NULL;
 612
 613 #ifdef TRAIN_RES
 614               accumulator=look->training_data[s][partword[j][i]];
 615               {
 616                 int l;
 617                 float *samples=in[j]+offset;
 618                 for(l=0;l<samples_per_partition;l++){
 619                   if(samples[l]<look->training_min[s][partword[j][i]])
 620                     look->training_min[s][partword[j][i]]=samples[l];
 621                   if(samples[l]>look->training_max[s][partword[j][i]])
 622                     look->training_max[s][partword[j][i]]=samples[l];
 623                 }
 624               }
 625 #endif
 626
 627               ret=encode(&vb->opb,in[j]+offset,samples_per_partition,
 628                          statebook,accumulator);
 629
 630               look->postbits+=ret;
 631               resbits[partword[j][i]]+=ret;
 632             }
 633           }
 634         }
 635       }
 636       if(qptr)while(i>=look->qoffsets[bin])
 637         qptr[bin++]=oggpack_bits(&vb->opb);
 638     }
 639   }
 640
 641   /*{
 642     long total=0;
 643     long totalbits=0;
 644     fprintf(stderr,"%d :: ",vb->mode);
 645     for(k=0;k<possible_partitions;k++){
 646       fprintf(stderr,"%ld/%1.2g, ",resvals[k],(float)resbits[k]/resvals[k]);
 647       total+=resvals[k];
 648       totalbits+=resbits[k];
 649       }
 650
 651     fprintf(stderr,":: %ld:%1.2g\n",total,(double)totalbits/total);
 652     }*/
 653   return(0);
 654 }
 655
 656 /* a truncated packet here just means 'stop working'; it's not an error */
 657 static int _01inverse(vorbis_block *vb,vorbis_look_residue *vl,
 658                       float **in,int ch,
 659                       long (*decodepart)(codebook *, float *,
 660                                          oggpack_buffer *,int)){
 661
 662   long i,j,k,l,s;
 663   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 664   vorbis_info_residue0 *info=look->info;
 665
 666   /* move all this setup out later */
 667   int samples_per_partition=info->grouping;
 668   int partitions_per_word=look->phrasebook->dim;
 669   int n=info->end-info->begin;
 670
 671   int partvals=n/samples_per_partition;
 672   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 673   int ***partword=alloca(ch*sizeof(*partword));
 674
 675   for(j=0;j<ch;j++)
 676     partword[j]=_vorbis_block_alloc(vb,partwords*sizeof(*partword[j]));
 677
 678   for(s=0;s<look->stages;s++){
 679
 680     /* each loop decodes on partition codeword containing
 681        partitions_pre_word partitions */
 682     for(i=0,l=0;i<partvals;l++){
 683       if(s==0){
 684         /* fetch the partition word for each channel */
 685         for(j=0;j<ch;j++){
 686           int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 687           if(temp==-1)goto eopbreak;
 688           partword[j][l]=look->decodemap[temp];
 689           if(partword[j][l]==NULL)goto errout;
 690         }
 691       }
 692
 693       /* now we decode residual values for the partitions */
 694       for(k=0;k<partitions_per_word && i<partvals;k++,i++)
 695         for(j=0;j<ch;j++){
 696           long offset=info->begin+i*samples_per_partition;
 697           if(info->secondstages[partword[j][l][k]]&(1<<s)){
 698             codebook *stagebook=look->partbooks[partword[j][l][k]][s];
 699             if(stagebook){
 700               if(decodepart(stagebook,in[j]+offset,&vb->opb,
 701                             samples_per_partition)==-1)goto eopbreak;
 702             }
 703           }
 704         }
 705     }
 706   }
 707
 708  errout:
 709  eopbreak:
 710   return(0);
 711 }
 712
 713 /* residue 0 and 1 are just slight variants of one another. 0 is
 714    interleaved, 1 is not */
 715 long **res0_class(vorbis_block *vb,vorbis_look_residue *vl,
 716                   float **in,int *nonzero,int ch){
 717   /* we encode only the nonzero parts of a bundle */
 718   int i,used=0;
 719   for(i=0;i<ch;i++)
 720     if(nonzero[i])
 721       in[used++]=in[i];
 722   if(used)
 723     /*return(_01class(vb,vl,in,used,_interleaved_testhack));*/
 724     return(_01class(vb,vl,in,used,_testhack));
 725   else
 726     return(0);
 727 }
 728
 729 int res0_forward(vorbis_block *vb,vorbis_look_residue *vl,
 730                  float **in,float **out,int *nonzero,int ch,
 731                  int pass, long **partword,ogg_uint32_t *stats){
 732   /* we encode only the nonzero parts of a bundle */
 733   int i,j,used=0,n=vb->pcmend/2;
 734   for(i=0;i<ch;i++)
 735     if(nonzero[i]){
 736       for(j=0;j<n;j++)
 737         out[i][j]+=in[i][j];
 738       in[used++]=in[i];
 739     }
 740   if(used){
 741     int ret=_01forward(vb,vl,in,used,pass,partword,
 742                       _interleaved_encodepart,stats);
 743     used=0;
 744     for(i=0;i<ch;i++)
 745       if(nonzero[i]){
 746         for(j=0;j<n;j++)
 747           out[i][j]-=in[used][j];
 748         used++;
 749       }
 750     return(ret);
 751   }else{
 752     for(i=0;i<vorbis_bitrate_maxmarkers();i++)
 753       stats[i]=oggpack_bits(&vb->opb);
 754
 755     return(0);
 756   }
 757 }
 758
 759 int res0_inverse(vorbis_block *vb,vorbis_look_residue *vl,
 760                  float **in,int *nonzero,int ch){
 761   int i,used=0;
 762   for(i=0;i<ch;i++)
 763     if(nonzero[i])
 764       in[used++]=in[i];
 765   if(used)
 766     return(_01inverse(vb,vl,in,used,vorbis_book_decodevs_add));
 767   else
 768     return(0);
 769 }
 770
 771 int res1_forward(vorbis_block *vb,vorbis_look_residue *vl,
 772                  float **in,float **out,int *nonzero,int ch,
 773                  int pass, long **partword, ogg_uint32_t *stats){
 774   int i,j,used=0,n=vb->pcmend/2;
 775   for(i=0;i<ch;i++)
 776     if(nonzero[i]){
 777       for(j=0;j<n;j++)
 778         out[i][j]+=in[i][j];
 779       in[used++]=in[i];
 780     }
 781
 782   if(used){
 783     int ret=_01forward(vb,vl,in,used,pass,partword,_encodepart,stats);
 784     used=0;
 785     for(i=0;i<ch;i++)
 786       if(nonzero[i]){
 787         for(j=0;j<n;j++)
 788           out[i][j]-=in[used][j];
 789         used++;
 790       }
 791     return(ret);
 792   }else{
 793     for(i=0;i<vorbis_bitrate_maxmarkers();i++)
 794       stats[i]=oggpack_bits(&vb->opb);
 795
 796     return(0);
 797   }
 798 }
 799
 800 long **res1_class(vorbis_block *vb,vorbis_look_residue *vl,
 801                   float **in,int *nonzero,int ch){
 802   int i,used=0;
 803   for(i=0;i<ch;i++)
 804     if(nonzero[i])
 805       in[used++]=in[i];
 806   if(used)
 807     return(_01class(vb,vl,in,used,_testhack));
 808   else
 809     return(0);
 810 }
 811
 812 int res1_inverse(vorbis_block *vb,vorbis_look_residue *vl,
 813                  float **in,int *nonzero,int ch){
 814   int i,used=0;
 815   for(i=0;i<ch;i++)
 816     if(nonzero[i])
 817       in[used++]=in[i];
 818   if(used)
 819     return(_01inverse(vb,vl,in,used,vorbis_book_decodev_add));
 820   else
 821     return(0);
 822 }
 823
 824 long **res2_class(vorbis_block *vb,vorbis_look_residue *vl,
 825                   float **in,int *nonzero,int ch){
 826   int i,used=0;
 827   for(i=0;i<ch;i++)
 828     if(nonzero[i])
 829       in[used++]=in[i];
 830   if(used)
 831     return(_2class(vb,vl,in,used,_testhack));
 832   else
 833     return(0);
 834 }
 835
 836 /* res2 is slightly more different; all the channels are interleaved
 837    into a single vector and encoded. */
 838
 839 int res2_forward(vorbis_block *vb,vorbis_look_residue *vl,
 840                  float **in,float **out,int *nonzero,int ch,
 841                  int pass,long **partword,ogg_uint32_t *stats){
 842   long i,j,k,n=vb->pcmend/2,used=0;
 843
 844   /* don't duplicate the code; use a working vector hack for now and
 845      reshape ourselves into a single channel res1 */
 846   /* ugly; reallocs for each coupling pass :-( */
 847   float *work=_vorbis_block_alloc(vb,ch*n*sizeof(*work));
 848   for(i=0;i<ch;i++){
 849     float *pcm=in[i];
 850     if(nonzero[i])used++;
 851     for(j=0,k=i;j<n;j++,k+=ch)
 852       work[k]=pcm[j];
 853   }
 854
 855   if(used){
 856     int ret=_01forward(vb,vl,&work,1,pass,partword,_encodepart,stats);
 857     /* update the sofar vector */
 858     for(i=0;i<ch;i++){
 859       float *pcm=in[i];
 860       float *sofar=out[i];
 861       for(j=0,k=i;j<n;j++,k+=ch)
 862         sofar[j]+=pcm[j]-work[k];
 863
 864     }
 865     return(ret);
 866   }else{
 867     for(i=0;i<vorbis_bitrate_maxmarkers();i++)
 868       stats[i]=oggpack_bits(&vb->opb);
 869
 870     return(0);
 871   }
 872 }
 873
 874 /* duplicate code here as speed is somewhat more important */
 875 int res2_inverse(vorbis_block *vb,vorbis_look_residue *vl,
 876                  float **in,int *nonzero,int ch){
 877   long i,k,l,s;
 878   vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
 879   vorbis_info_residue0 *info=look->info;
 880
 881   /* move all this setup out later */
 882   int samples_per_partition=info->grouping;
 883   int partitions_per_word=look->phrasebook->dim;
 884   int n=info->end-info->begin;
 885
 886   int partvals=n/samples_per_partition;
 887   int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
 888   int **partword=_vorbis_block_alloc(vb,partwords*sizeof(*partword));
 889
 890   for(i=0;i<ch;i++)if(nonzero[i])break;
 891   if(i==ch)return(0); /* no nonzero vectors */
 892
 893   for(s=0;s<look->stages;s++){
 894     for(i=0,l=0;i<partvals;l++){
 895
 896       if(s==0){
 897         /* fetch the partition word */
 898         int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
 899         if(temp==-1)goto eopbreak;
 900         partword[l]=look->decodemap[temp];
 901         if(partword[l]==NULL)goto errout;
 902       }
 903
 904       /* now we decode residual values for the partitions */
 905       for(k=0;k<partitions_per_word && i<partvals;k++,i++)
 906         if(info->secondstages[partword[l][k]]&(1<<s)){
 907           codebook *stagebook=look->partbooks[partword[l][k]][s];
 908
 909           if(stagebook){
 910             if(vorbis_book_decodevv_add(stagebook,in,
 911                                         i*samples_per_partition+info->begin,ch,
 912                                         &vb->opb,samples_per_partition)==-1)
 913               goto eopbreak;
 914           }
 915         }
 916     }
 917   }
 918
 919  errout:
 920  eopbreak:
 921   return(0);
 922 }
 923
 924
 925 vorbis_func_residue residue0_exportbundle={
 926   &res0_pack,
 927   &res0_unpack,
 928   &res0_look,
 929   &res0_copy_info,
 930   &res0_free_info,
 931   &res0_free_look,
 932   &res0_class,
 933   &res0_forward,
 934   &res0_inverse
 935 };
 936
 937 vorbis_func_residue residue1_exportbundle={
 938   &res0_pack,
 939   &res0_unpack,
 940   &res0_look,
 941   &res0_copy_info,
 942   &res0_free_info,
 943   &res0_free_look,
 944   &res1_class,
 945   &res1_forward,
 946   &res1_inverse
 947 };
 948
 949 vorbis_func_residue residue2_exportbundle={
 950   &res0_pack,
 951   &res0_unpack,
 952   &res0_look,
 953   &res0_copy_info,
 954   &res0_free_info,
 955   &res0_free_look,
 956   &res2_class,
 957   &res2_forward,
 958   &res2_inverse
 959 };