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