1 /********************************************************************
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. *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001 *
9 * by the XIPHOPHORUS Company http://www.xiph.org/ *
11 ********************************************************************
13 function: residue backend 0, 1 and 2 implementation
14 last mod: $Id: res0.c,v 1.40 2001/12/19 01:08:15 xiphmont Exp $
16 ********************************************************************/
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,
27 #include "vorbis/codec.h"
28 #include "codec_internal.h"
39 vorbis_info_residue0 *info;
46 codebook ***partbooks;
55 int qoffsets[BITTRACK_DIVISOR+1];
58 long *training_data[8][64];
59 float training_max[8][64];
60 float training_min[8][64];
66 } vorbis_look_residue0;
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));
75 void res0_free_info(vorbis_info_residue *i){
76 vorbis_info_residue0 *info=(vorbis_info_residue0 *)i;
78 memset(info,0,sizeof(*info));
83 void res0_free_look(vorbis_look_residue *i){
87 vorbis_look_residue0 *look=(vorbis_look_residue0 *)i;
92 for(j=0;j<look->parts;j++){
93 fprintf(stderr,"partition %d: ",j);
95 if(look->training_data[k][j]){
98 codebook *statebook=look->partbooks[j][k];
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");
104 for(l=0;l<statebook->entries;l++)
105 fprintf(of,"%d:%ld\n",l,look->training_data[k][j][l]);
109 fprintf(stderr,"%d(%.2f|%.2f) ",k,look->training_min[k][j],look->training_max[k][j]);
111 _ogg_free(look->training_data[k][j]);
113 fprintf(stderr,"\n");
116 fprintf(stderr,"min/max residue: %g::%g\n",look->tmin,look->tmax);
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);
125 /*vorbis_info_residue0 *info=look->info;
128 "%ld frames encoded in %ld phrasebits and %ld residue bits "
129 "(%g/frame) \n",look->frames,look->phrasebits,
131 (look->phrasebits+look->resbitsflat)/(float)look->frames);
133 for(j=0;j<look->parts;j++){
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];
142 fprintf(stderr,":: (%ld vals) %1.2fbits/sample\n",look->resvals[j],
143 acc?(float)acc/(look->resvals[j]*info->grouping):0);
145 fprintf(stderr,"\n");*/
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);
154 memset(look,0,sizeof(*look));
159 static int ilog(unsigned int v){
168 static int icount(unsigned int v){
178 void res0_pack(vorbis_info_residue *vr,oggpack_buffer *opb){
179 vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
181 oggpack_write(opb,info->begin,24);
182 oggpack_write(opb,info->end,24);
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 */
189 /* secondstages is a bitmask; as encoding progresses pass by pass, a
190 bitmask of one indicates this partition class has bits to write
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);
199 oggpack_write(opb,info->secondstages[j],4); /* trailing zero */
200 acc+=icount(info->secondstages[j]);
203 oggpack_write(opb,info->booklist[j],8);
207 /* vorbis_info is for range checking */
208 vorbis_info_residue *res0_unpack(vorbis_info *vi,oggpack_buffer *opb){
210 vorbis_info_residue0 *info=_ogg_calloc(1,sizeof(*info));
211 codec_setup_info *ci=vi->codec_setup;
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);
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;
225 acc+=icount(cascade);
228 info->booklist[j]=oggpack_read(opb,8);
230 if(info->groupbook>=ci->books)goto errout;
232 if(info->booklist[j]>=ci->books)goto errout;
236 res0_free_info(info);
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;
250 look->map=vm->mapping;
252 look->parts=info->partitions;
253 look->fullbooks=be->fullbooks;
254 look->phrasebook=be->fullbooks+info->groupbook;
255 dim=look->phrasebook->dim;
257 look->partbooks=_ogg_calloc(look->parts,sizeof(*look->partbooks));
259 for(j=0;j<look->parts;j++){
260 int stages=ilog(info->secondstages[j]);
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++];
268 look->training_data[k][j]=calloc(look->partbooks[j][k]->entries,
269 sizeof(***look->training_data));
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++){
280 long mult=look->partvals/look->parts;
281 look->decodemap[j]=_ogg_malloc(dim*sizeof(*look->decodemap[j]));
286 look->decodemap[j][k]=deco;
291 int samples_per_partition=info->grouping;
292 int n=info->end-info->begin,i;
293 int partvals=n/samples_per_partition;
295 for(i=0;i<BITTRACK_DIVISOR;i++)
296 look->qoffsets[i]=partvals*(i+1)/BITTRACK_DIVISOR;
298 look->qoffsets[i]=9999999;
305 /* does not guard against invalid settings; eg, a subn of 16 and a
306 subgroup request of 32. Max subn of 128 */
307 static int _interleaved_testhack(float *vec,int n,vorbis_look_residue0 *look,
308 int auxparts,int auxpartnum){
309 vorbis_info_residue0 *info=look->info;
311 float max,localmax=0.f;
316 for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
318 /* handle case subgrp==1 outside */
320 if(temp[i]>localmax)localmax=temp[i];
323 for(i=0;i<n;i++)temp[i]=rint(temp[i]);
336 if(temp[i]>localmax)localmax=temp[i];
339 for(i=0;i<auxparts-1;i++)
340 if(auxpartnum<info->blimit[i] &&
341 entropy[info->subgrp[i]]<=info->entmax[i] &&
342 max<=info->ampmax[i])
348 static int _testhack(float *vec,int n,vorbis_look_residue0 *look,
349 int auxparts,int auxpartnum){
350 vorbis_info_residue0 *info=look->info;
357 for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
360 if(temp[i]>max)max=temp[i];
362 for(i=0;i<n;i++)temp[i]=rint(temp[i]);
367 for(i=0;i<auxparts-1;i++)
368 if(auxpartnum<info->blimit[i] &&
369 entropy<=info->entmax[i] &&
370 max<=info->ampmax[i])
376 static int _interleaved_encodepart(oggpack_buffer *opb,float *vec, int n,
377 codebook *book,long *acc){
383 int entry=vorbis_book_besterror(book,vec+i,step,0);
389 bits+=vorbis_book_encode(book,entry,opb);
395 static int _encodepart(oggpack_buffer *opb,float *vec, int n,
396 codebook *book,long *acc){
402 int entry=vorbis_book_besterror(book,vec+i*dim,1,0);
408 bits+=vorbis_book_encode(book,entry,opb);
414 static long **_01class(vorbis_block *vb,vorbis_look_residue *vl,
416 int (*classify)(float *,int,vorbis_look_residue0 *,
419 vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
420 vorbis_info_residue0 *info=look->info;
422 /* move all this setup out later */
423 int samples_per_partition=info->grouping;
424 int possible_partitions=info->partitions;
425 int n=info->end-info->begin;
427 int partvals=n/samples_per_partition;
428 long **partword=_vorbis_block_alloc(vb,ch*sizeof(*partword));
430 /* we find the partition type for each partition of each
431 channel. We'll go back and do the interleaved encoding in a
432 bit. For now, clarity */
435 partword[i]=_vorbis_block_alloc(vb,n/samples_per_partition*sizeof(*partword[i]));
436 memset(partword[i],0,n/samples_per_partition*sizeof(*partword[i]));
439 for(i=0;i<partvals;i++){
441 /* do the partition decision based on the 'entropy'
444 classify(in[j]+i*samples_per_partition+info->begin,
445 samples_per_partition,look,possible_partitions,i);
456 sprintf(buffer,"resaux_%s.vqd",(vb->mode?"long":"short"));
457 of=fopen(buffer,"a");
458 for(j=0;j<partvals;j++)
459 fprintf(of,"%ld, ",partword[i][j]);
470 static long **_2class(vorbis_block *vb,vorbis_look_residue *vl,
472 int (*classify)(float *,int,vorbis_look_residue0 *,
475 vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
476 vorbis_info_residue0 *info=look->info;
478 /* move all this setup out later */
479 int samples_per_partition=info->grouping;
480 int possible_partitions=info->partitions;
481 int n=info->end-info->begin;
483 int partvals=n/samples_per_partition;
484 long **partword=_vorbis_block_alloc(vb,sizeof(*partword));
485 float *work=alloca(sizeof(*work)*samples_per_partition);
492 partword[0]=_vorbis_block_alloc(vb,n*ch/samples_per_partition*sizeof(*partword[0]));
493 memset(partword[0],0,n*ch/samples_per_partition*sizeof(*partword[0]));
495 for(i=0,j=0,k=0,l=info->begin;i<partvals;i++){
496 for(k=0;k<samples_per_partition;k++){
506 classify(work,samples_per_partition,look,possible_partitions,i);
513 sprintf(buffer,"resaux_%s.vqd",(vb->mode?"long":"short"));
514 of=fopen(buffer,"a");
515 for(i=0;i<partvals;i++)
516 fprintf(of,"%ld, ",partword[0][i]);
526 static int _01forward(vorbis_block *vb,vorbis_look_residue *vl,
528 int pass,long **partword,
529 int (*encode)(oggpack_buffer *,float *,int,
531 ogg_uint32_t *stats){
533 vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
534 vorbis_info_residue0 *info=look->info;
536 vorbis_dsp_state *vd=vb->vd;
537 vorbis_info *vi=vd->vi;
538 codec_setup_info *ci=vi->codec_setup;
541 /* move all this setup out later */
542 int samples_per_partition=info->grouping;
543 int possible_partitions=info->partitions;
544 int partitions_per_word=look->phrasebook->dim;
545 int n=info->end-info->begin;
547 int partvals=n/samples_per_partition;
553 for(j=info->begin;j<info->end;j++){
554 if(in[i][j]>look->tmax)look->tmax=in[i][j];
555 if(in[i][j]<look->tmin)look->tmin=in[i][j];
559 memset(resbits,0,sizeof(resbits));
560 memset(resvals,0,sizeof(resvals));
562 /* we code the partition words for each channel, then the residual
563 words for a partition per channel until we've written all the
564 residual words for that partition word. Then write the next
565 partition channel words... */
567 for(s=(pass==0?0:ci->passlimit[pass-1]);s<ci->passlimit[pass];s++){
569 ogg_uint32_t *qptr=NULL;
570 if(stats)qptr=stats+s*BITTRACK_DIVISOR;
572 for(i=0;i<partvals;){
574 /* first we encode a partition codeword for each channel */
577 long val=partword[j][i];
579 for(k=1;k<partitions_per_word;k++){
580 val*=possible_partitions;
582 val+=partword[j][i+k];
586 if(val<look->phrasebook->entries)
587 ret=vorbis_book_encode(look->phrasebook,val,&vb->opb);
592 look->phrasebits+=ret;
597 /* now we encode interleaved residual values for the partitions */
598 for(k=0;k<partitions_per_word && i<partvals;k++,i++){
599 long offset=i*samples_per_partition+info->begin;
601 if(qptr)while(i>=look->qoffsets[bin])
602 qptr[bin++]=oggpack_bits(&vb->opb);
605 if(s==0)resvals[partword[j][i]]+=samples_per_partition;
606 if(info->secondstages[partword[j][i]]&(1<<s)){
607 codebook *statebook=look->partbooks[partword[j][i]][s];
610 long *accumulator=NULL;
613 accumulator=look->training_data[s][partword[j][i]];
616 float *samples=in[j]+offset;
617 for(l=0;l<samples_per_partition;l++){
618 if(samples[l]<look->training_min[s][partword[j][i]])
619 look->training_min[s][partword[j][i]]=samples[l];
620 if(samples[l]>look->training_max[s][partword[j][i]])
621 look->training_max[s][partword[j][i]]=samples[l];
626 ret=encode(&vb->opb,in[j]+offset,samples_per_partition,
627 statebook,accumulator);
630 resbits[partword[j][i]]+=ret;
635 if(qptr)while(i>=look->qoffsets[bin])
636 qptr[bin++]=oggpack_bits(&vb->opb);
643 fprintf(stderr,"%d :: ",vb->mode);
644 for(k=0;k<possible_partitions;k++){
645 fprintf(stderr,"%ld/%1.2g, ",resvals[k],(float)resbits[k]/resvals[k]);
647 totalbits+=resbits[k];
650 fprintf(stderr,":: %ld:%1.2g\n",total,(double)totalbits/total);
655 /* a truncated packet here just means 'stop working'; it's not an error */
656 static int _01inverse(vorbis_block *vb,vorbis_look_residue *vl,
658 long (*decodepart)(codebook *, float *,
659 oggpack_buffer *,int)){
662 vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
663 vorbis_info_residue0 *info=look->info;
665 /* move all this setup out later */
666 int samples_per_partition=info->grouping;
667 int partitions_per_word=look->phrasebook->dim;
668 int n=info->end-info->begin;
670 int partvals=n/samples_per_partition;
671 int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
672 int ***partword=alloca(ch*sizeof(*partword));
675 partword[j]=_vorbis_block_alloc(vb,partwords*sizeof(*partword[j]));
677 for(s=0;s<look->stages;s++){
679 /* each loop decodes on partition codeword containing
680 partitions_pre_word partitions */
681 for(i=0,l=0;i<partvals;l++){
683 /* fetch the partition word for each channel */
685 int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
686 if(temp==-1)goto eopbreak;
687 partword[j][l]=look->decodemap[temp];
688 if(partword[j][l]==NULL)goto errout;
692 /* now we decode residual values for the partitions */
693 for(k=0;k<partitions_per_word && i<partvals;k++,i++)
695 long offset=info->begin+i*samples_per_partition;
696 if(info->secondstages[partword[j][l][k]]&(1<<s)){
697 codebook *stagebook=look->partbooks[partword[j][l][k]][s];
699 if(decodepart(stagebook,in[j]+offset,&vb->opb,
700 samples_per_partition)==-1)goto eopbreak;
712 /* residue 0 and 1 are just slight variants of one another. 0 is
713 interleaved, 1 is not */
714 long **res0_class(vorbis_block *vb,vorbis_look_residue *vl,
715 float **in,int *nonzero,int ch){
716 /* we encode only the nonzero parts of a bundle */
722 /*return(_01class(vb,vl,in,used,_interleaved_testhack));*/
723 return(_01class(vb,vl,in,used,_testhack));
728 int res0_forward(vorbis_block *vb,vorbis_look_residue *vl,
729 float **in,float **out,int *nonzero,int ch,
730 int pass, long **partword,ogg_uint32_t *stats){
731 /* we encode only the nonzero parts of a bundle */
732 int i,j,used=0,n=vb->pcmend/2;
740 int ret=_01forward(vb,vl,in,used,pass,partword,
741 _interleaved_encodepart,stats);
746 out[i][j]-=in[used][j];
751 for(i=0;i<vorbis_bitrate_maxmarkers();i++)
752 stats[i]=oggpack_bits(&vb->opb);
758 int res0_inverse(vorbis_block *vb,vorbis_look_residue *vl,
759 float **in,int *nonzero,int ch){
765 return(_01inverse(vb,vl,in,used,vorbis_book_decodevs_add));
770 int res1_forward(vorbis_block *vb,vorbis_look_residue *vl,
771 float **in,float **out,int *nonzero,int ch,
772 int pass, long **partword, ogg_uint32_t *stats){
773 int i,j,used=0,n=vb->pcmend/2;
782 int ret=_01forward(vb,vl,in,used,pass,partword,_encodepart,stats);
787 out[i][j]-=in[used][j];
792 for(i=0;i<vorbis_bitrate_maxmarkers();i++)
793 stats[i]=oggpack_bits(&vb->opb);
799 long **res1_class(vorbis_block *vb,vorbis_look_residue *vl,
800 float **in,int *nonzero,int ch){
806 return(_01class(vb,vl,in,used,_testhack));
811 int res1_inverse(vorbis_block *vb,vorbis_look_residue *vl,
812 float **in,int *nonzero,int ch){
818 return(_01inverse(vb,vl,in,used,vorbis_book_decodev_add));
823 long **res2_class(vorbis_block *vb,vorbis_look_residue *vl,
824 float **in,int *nonzero,int ch){
830 return(_2class(vb,vl,in,used,_testhack));
835 /* res2 is slightly more different; all the channels are interleaved
836 into a single vector and encoded. */
838 int res2_forward(vorbis_block *vb,vorbis_look_residue *vl,
839 float **in,float **out,int *nonzero,int ch,
840 int pass,long **partword,ogg_uint32_t *stats){
841 long i,j,k,n=vb->pcmend/2,used=0;
843 /* don't duplicate the code; use a working vector hack for now and
844 reshape ourselves into a single channel res1 */
845 /* ugly; reallocs for each coupling pass :-( */
846 float *work=_vorbis_block_alloc(vb,ch*n*sizeof(*work));
849 if(nonzero[i])used++;
850 for(j=0,k=i;j<n;j++,k+=ch)
855 int ret=_01forward(vb,vl,&work,1,pass,partword,_encodepart,stats);
856 /* update the sofar vector */
860 for(j=0,k=i;j<n;j++,k+=ch)
861 sofar[j]+=pcm[j]-work[k];
866 for(i=0;i<vorbis_bitrate_maxmarkers();i++)
867 stats[i]=oggpack_bits(&vb->opb);
873 /* duplicate code here as speed is somewhat more important */
874 int res2_inverse(vorbis_block *vb,vorbis_look_residue *vl,
875 float **in,int *nonzero,int ch){
877 vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
878 vorbis_info_residue0 *info=look->info;
880 /* move all this setup out later */
881 int samples_per_partition=info->grouping;
882 int partitions_per_word=look->phrasebook->dim;
883 int n=info->end-info->begin;
885 int partvals=n/samples_per_partition;
886 int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
887 int **partword=_vorbis_block_alloc(vb,partwords*sizeof(*partword));
889 for(i=0;i<ch;i++)if(nonzero[i])break;
890 if(i==ch)return(0); /* no nonzero vectors */
892 for(s=0;s<look->stages;s++){
893 for(i=0,l=0;i<partvals;l++){
896 /* fetch the partition word */
897 int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
898 if(temp==-1)goto eopbreak;
899 partword[l]=look->decodemap[temp];
900 if(partword[l]==NULL)goto errout;
903 /* now we decode residual values for the partitions */
904 for(k=0;k<partitions_per_word && i<partvals;k++,i++)
905 if(info->secondstages[partword[l][k]]&(1<<s)){
906 codebook *stagebook=look->partbooks[partword[l][k]][s];
909 if(vorbis_book_decodevv_add(stagebook,in,
910 i*samples_per_partition+info->begin,ch,
911 &vb->opb,samples_per_partition)==-1)
924 vorbis_func_residue residue0_exportbundle={
936 vorbis_func_residue residue1_exportbundle={
948 vorbis_func_residue residue2_exportbundle={