res0.c 11.6 KB
Newer Older
Monty's avatar
 
Monty committed
1
2
/********************************************************************
 *                                                                  *
Monty's avatar
   
Monty committed
3
 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
Monty's avatar
 
Monty committed
4
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
Monty's avatar
   
Monty committed
5
6
 * THE GNU LESSER/LIBRARY PUBLIC LICENSE, WHICH IS INCLUDED WITH    *
 * THIS SOURCE. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.        *
Monty's avatar
 
Monty committed
7
 *                                                                  *
Monty's avatar
   
Monty committed
8
9
 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
 * by the XIPHOPHORUS Company http://www.xiph.org/                  *
Monty's avatar
 
Monty committed
10
11
12
 *                                                                  *
 ********************************************************************

Monty's avatar
   
Monty committed
13
 function: residue backend 0 implementation
Monty's avatar
   
Monty committed
14
 last mod: $Id: res0.c,v 1.25 2001/02/02 03:51:57 xiphmont Exp $
Monty's avatar
 
Monty committed
15
16
17

 ********************************************************************/

Monty's avatar
   
Monty committed
18
19
20
21
22
/* Slow, slow, slow, simpleminded and did I mention it was slow?  The
   encode/decode loops are coded for clarity and performance is not
   yet even a nagging little idea lurking in the shadows.  Oh and BTW,
   it's slow. */

Monty's avatar
 
Monty committed
23
24
#include <stdlib.h>
#include <string.h>
Monty's avatar
   
Monty committed
25
#include <math.h>
Monty's avatar
   
Monty committed
26
#include <stdio.h>
Monty's avatar
   
Monty committed
27
#include <ogg/ogg.h>
Monty's avatar
 
Monty committed
28
#include "vorbis/codec.h"
Monty's avatar
   
Monty committed
29
#include "codec_internal.h"
Monty's avatar
   
Monty committed
30
#include "registry.h"
Monty's avatar
   
Monty committed
31
#include "codebook.h"
Monty's avatar
   
Monty committed
32
#include "misc.h"
Monty's avatar
   
Monty committed
33
#include "os.h"
Monty's avatar
 
Monty committed
34

Monty's avatar
   
Monty committed
35
36
typedef struct {
  vorbis_info_residue0 *info;
Monty's avatar
   
Monty committed
37
  int         map;
Monty's avatar
   
Monty committed
38
39
40
41
42
43
44
  
  int         parts;
  codebook   *phrasebook;
  codebook ***partbooks;

  int         partvals;
  int       **decodemap;
Monty's avatar
   
Monty committed
45
} vorbis_look_residue0;
Monty's avatar
 
Monty committed
46

Monty's avatar
   
Monty committed
47
48
49
50
51
52
53
vorbis_info_residue *res0_copy_info(vorbis_info_residue *vr){
  vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  vorbis_info_residue0 *ret=_ogg_malloc(sizeof(vorbis_info_residue0));
  memcpy(ret,info,sizeof(vorbis_info_residue0));
  return(ret);
}

Monty's avatar
   
Monty committed
54
void res0_free_info(vorbis_info_residue *i){
Monty's avatar
   
Monty committed
55
56
  if(i){
    memset(i,0,sizeof(vorbis_info_residue0));
Monty's avatar
   
Monty committed
57
    _ogg_free(i);
Monty's avatar
   
Monty committed
58
  }
Monty's avatar
 
Monty committed
59
60
}

Monty's avatar
   
Monty committed
61
void res0_free_look(vorbis_look_residue *i){
Monty's avatar
   
Monty committed
62
  int j;
Monty's avatar
   
Monty committed
63
  if(i){
Monty's avatar
   
Monty committed
64
65
    vorbis_look_residue0 *look=(vorbis_look_residue0 *)i;
    for(j=0;j<look->parts;j++)
Monty's avatar
   
Monty committed
66
67
      if(look->partbooks[j])_ogg_free(look->partbooks[j]);
    _ogg_free(look->partbooks);
Monty's avatar
   
Monty committed
68
    for(j=0;j<look->partvals;j++)
Monty's avatar
   
Monty committed
69
70
      _ogg_free(look->decodemap[j]);
    _ogg_free(look->decodemap);
Monty's avatar
   
Monty committed
71
    memset(i,0,sizeof(vorbis_look_residue0));
Monty's avatar
   
Monty committed
72
    _ogg_free(i);
Monty's avatar
   
Monty committed
73
  }
Monty's avatar
   
Monty committed
74
75
}

Monty's avatar
   
Monty committed
76
void res0_pack(vorbis_info_residue *vr,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
77
78
  vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  int j,acc=0;
Monty's avatar
   
Monty committed
79
80
  oggpack_write(opb,info->begin,24);
  oggpack_write(opb,info->end,24);
Monty's avatar
   
Monty committed
81

Monty's avatar
   
Monty committed
82
  oggpack_write(opb,info->grouping-1,24);  /* residue vectors to group and 
Monty's avatar
   
Monty committed
83
					     code with a partitioned book */
Monty's avatar
   
Monty committed
84
85
  oggpack_write(opb,info->partitions-1,6); /* possible partition choices */
  oggpack_write(opb,info->groupbook,8);  /* group huffman book */
Monty's avatar
   
Monty committed
86
  for(j=0;j<info->partitions;j++){
Monty's avatar
   
Monty committed
87
    oggpack_write(opb,info->secondstages[j],4); /* zero *is* a valid choice */
Monty's avatar
   
Monty committed
88
89
90
    acc+=info->secondstages[j];
  }
  for(j=0;j<acc;j++)
Monty's avatar
   
Monty committed
91
    oggpack_write(opb,info->booklist[j],8);
Monty's avatar
   
Monty committed
92

Monty's avatar
   
Monty committed
93
94
95
}

/* vorbis_info is for range checking */
Monty's avatar
   
Monty committed
96
vorbis_info_residue *res0_unpack(vorbis_info *vi,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
97
  int j,acc=0;
Monty's avatar
   
Monty committed
98
99
  vorbis_info_residue0 *info=_ogg_calloc(1,sizeof(vorbis_info_residue0));
  codec_setup_info     *ci=vi->codec_setup;
Monty's avatar
   
Monty committed
100

Monty's avatar
   
Monty committed
101
102
103
104
105
  info->begin=oggpack_read(opb,24);
  info->end=oggpack_read(opb,24);
  info->grouping=oggpack_read(opb,24)+1;
  info->partitions=oggpack_read(opb,6)+1;
  info->groupbook=oggpack_read(opb,8);
Monty's avatar
   
Monty committed
106
  for(j=0;j<info->partitions;j++){
Monty's avatar
   
Monty committed
107
    int cascade=info->secondstages[j]=oggpack_read(opb,4);
Monty's avatar
   
Monty committed
108
109
110
111
    if(cascade>1)goto errout; /* temporary!  when cascading gets
                                 reworked and actually used, we don't
                                 want old code to DTWT */
    acc+=cascade;
Monty's avatar
   
Monty committed
112
  }
Monty's avatar
   
Monty committed
113
  for(j=0;j<acc;j++){
Monty's avatar
   
Monty committed
114
    info->booklist[j]=oggpack_read(opb,8);
Monty's avatar
   
Monty committed
115
116
    if(info->booklist[j]==255)info->booklist[j]=-1;
  }
Monty's avatar
   
Monty committed
117

Monty's avatar
   
Monty committed
118
  if(info->groupbook>=ci->books)goto errout;
Monty's avatar
   
Monty committed
119
  for(j=0;j<acc;j++)
Monty's avatar
   
Monty committed
120
    if(info->booklist[j]>=ci->books)goto errout;
Monty's avatar
   
Monty committed
121

Monty's avatar
   
Monty committed
122
  return(info);
Monty's avatar
   
Monty committed
123
 errout:
Monty's avatar
   
Monty committed
124
  res0_free_info(info);
Monty's avatar
   
Monty committed
125
  return(NULL);
Monty's avatar
 
Monty committed
126
127
}

Monty's avatar
   
Monty committed
128
vorbis_look_residue *res0_look (vorbis_dsp_state *vd,vorbis_info_mode *vm,
Monty's avatar
   
Monty committed
129
			  vorbis_info_residue *vr){
Monty's avatar
   
Monty committed
130
  vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
Monty's avatar
   
Monty committed
131
132
133
  vorbis_look_residue0 *look=_ogg_calloc(1,sizeof(vorbis_look_residue0));
  backend_lookup_state *be=vd->backend_state;

Monty's avatar
   
Monty committed
134
135
  int j,k,acc=0;
  int dim;
Monty's avatar
   
Monty committed
136
  look->info=info;
Monty's avatar
   
Monty committed
137
  look->map=vm->mapping;
Monty's avatar
   
Monty committed
138
139

  look->parts=info->partitions;
Monty's avatar
   
Monty committed
140
  look->phrasebook=be->fullbooks+info->groupbook;
Monty's avatar
   
Monty committed
141
142
  dim=look->phrasebook->dim;

Monty's avatar
   
Monty committed
143
  look->partbooks=_ogg_calloc(look->parts,sizeof(codebook **));
Monty's avatar
   
Monty committed
144
145
146
147

  for(j=0;j<look->parts;j++){
    int stages=info->secondstages[j];
    if(stages){
Monty's avatar
   
Monty committed
148
      look->partbooks[j]=_ogg_malloc(stages*sizeof(codebook *));
Monty's avatar
   
Monty committed
149
      look->partbooks[j][0]=be->fullbooks+info->booklist[acc++];
Monty's avatar
   
Monty committed
150
151
152
    }
  }

Monty's avatar
   
Monty committed
153
  look->partvals=rint(pow(look->parts,dim));
Monty's avatar
   
Monty committed
154
  look->decodemap=_ogg_malloc(look->partvals*sizeof(int *));
Monty's avatar
   
Monty committed
155
156
157
  for(j=0;j<look->partvals;j++){
    long val=j;
    long mult=look->partvals/look->parts;
Monty's avatar
   
Monty committed
158
    look->decodemap[j]=_ogg_malloc(dim*sizeof(int));
Monty's avatar
   
Monty committed
159
160
161
162
163
164
    for(k=0;k<dim;k++){
      long deco=val/mult;
      val-=deco*mult;
      mult/=look->parts;
      look->decodemap[j][k]=deco;
    }
Monty's avatar
   
Monty committed
165
166
167
  }

  return(look);
Monty's avatar
 
Monty committed
168
}
Monty's avatar
   
Monty committed
169

Monty's avatar
   
Monty committed
170
171
172

/* does not guard against invalid settings; eg, a subn of 16 and a
   subgroup request of 32.  Max subn of 128 */
Monty's avatar
   
Monty committed
173
static int _testhack(float *vec,int n,vorbis_look_residue0 *look,
Monty's avatar
   
Monty committed
174
		     int auxparts,int auxpartnum){
Monty's avatar
   
Monty committed
175
  vorbis_info_residue0 *info=look->info;
Monty's avatar
   
Monty committed
176
  int i,j=0;
Monty's avatar
   
Monty committed
177
  float max,localmax=0.f;
Monty's avatar
   
Monty committed
178
179
  float temp[128];
  float entropy[8];
Monty's avatar
   
Monty committed
180
181

  /* setup */
Monty's avatar
   
Monty committed
182
  for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
Monty's avatar
   
Monty committed
183
184

  /* handle case subgrp==1 outside */
Monty's avatar
   
Monty committed
185
  for(i=0;i<n;i++)
Monty's avatar
   
Monty committed
186
187
    if(temp[i]>localmax)localmax=temp[i];
  max=localmax;
Monty's avatar
   
Monty committed
188
189

  for(i=0;i<n;i++)temp[i]=rint(temp[i]);
Monty's avatar
   
Monty committed
190
  
Monty's avatar
   
Monty committed
191
192
193
194
195
196
197
198
199
  while(1){
    entropy[j]=localmax;
    n>>=1;
    j++;

    if(n<=0)break;
    for(i=0;i<n;i++){
      temp[i]+=temp[i+n];
    }
Monty's avatar
   
Monty committed
200
    localmax=0.f;
Monty's avatar
   
Monty committed
201
202
203
204
205
    for(i=0;i<n;i++)
      if(temp[i]>localmax)localmax=temp[i];
  }

  for(i=0;i<auxparts-1;i++)
Monty's avatar
   
Monty committed
206
207
    if(auxpartnum<info->blimit[i] &&
       entropy[info->subgrp[i]]<=info->entmax[i] &&
Monty's avatar
   
Monty committed
208
       max<=info->ampmax[i])
Monty's avatar
   
Monty committed
209
      break;
Monty's avatar
   
Monty committed
210

Monty's avatar
   
Monty committed
211
  return(i);
Monty's avatar
   
Monty committed
212
213
}

Monty's avatar
   
Monty committed
214
static int _encodepart(oggpack_buffer *opb,float *vec, int n,
Monty's avatar
   
Monty committed
215
		       int stages, codebook **books,int mode,int part){
Monty's avatar
   
Monty committed
216
217
  int i,j=0,bits=0;
  if(stages){
Monty's avatar
   
Monty committed
218
219
    int dim=books[j]->dim;
    int step=n/dim;
Monty's avatar
   
Monty committed
220
221
222
223
224
225
226
227
228
229
230
231
    for(i=0;i<step;i++){
      int entry=vorbis_book_besterror(books[j],vec+i,step,0);
#ifdef TRAIN_RESENT      
      {
	char buf[80];
	FILE *f;
	sprintf(buf,"res0_%da%d_%d.vqd",mode,j,part);
	f=fopen(buf,"a");
	fprintf(f,"%d\n",entry);
	fclose(f);
      }
#endif
Monty's avatar
   
Monty committed
232
      bits+=vorbis_book_encode(books[j],entry,opb);
Monty's avatar
   
Monty committed
233
    }
Monty's avatar
   
Monty committed
234
  }
Monty's avatar
   
Monty committed
235
  return(bits);
Monty's avatar
   
Monty committed
236
237
}

Monty's avatar
   
Monty committed
238
static int _decodepart(oggpack_buffer *opb,float *work,float *vec, int n,
Monty's avatar
   
Monty committed
239
		       int stages, codebook **books){
Monty's avatar
   
Monty committed
240
  int i;
Monty's avatar
   
Monty committed
241
  
Monty's avatar
   
Monty committed
242
  memset(work,0,sizeof(float)*n);
Monty's avatar
   
Monty committed
243
244
  if(stages){
    int dim=books[0]->dim;
Monty's avatar
   
Monty committed
245
    int step=n/dim;
Monty's avatar
   
Monty committed
246
    if(s_vorbis_book_decodevs(books[0],work,opb,step,0)==-1)
Monty's avatar
   
Monty committed
247
      return(-1);
Monty's avatar
   
Monty committed
248
249
  }
  
Monty's avatar
   
Monty committed
250
251
252
253
254
255
  for(i=0;i<n;i++)
    vec[i]*=work[i];
  
  return(0);
}

Monty's avatar
   
Monty committed
256
int res0_forward(vorbis_block *vb,vorbis_look_residue *vl,
Monty's avatar
   
Monty committed
257
	    float **in,int ch){
Monty's avatar
   
Monty committed
258
259
  long i,j,k,l;
  vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
Monty's avatar
   
Monty committed
260
  vorbis_info_residue0 *info=look->info;
Monty's avatar
   
Monty committed
261
262
263
264
265
266
267
268
269
270
271
272
273

  /* move all this setup out later */
  int samples_per_partition=info->grouping;
  int possible_partitions=info->partitions;
  int partitions_per_word=look->phrasebook->dim;
  int n=info->end-info->begin;
  long phrasebits=0,resbitsT=0;
  long *resbits=alloca(sizeof(long)*possible_partitions);
  long *resvals=alloca(sizeof(long)*possible_partitions);

  int partvals=n/samples_per_partition;
  int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
  long **partword=_vorbis_block_alloc(vb,ch*sizeof(long *));
Monty's avatar
   
Monty committed
274

Monty's avatar
   
Monty committed
275
276
  partvals=partwords*partitions_per_word;

Monty's avatar
   
Monty committed
277
  /* we find the patition type for each partition of each
Monty's avatar
   
Monty committed
278
279
280
281
282
283
284
285
286
287
288
     channel.  We'll go back and do the interleaved encoding in a
     bit.  For now, clarity */
  
  memset(resbits,0,sizeof(long)*possible_partitions);
  memset(resvals,0,sizeof(long)*possible_partitions);

  for(i=0;i<ch;i++){
    partword[i]=_vorbis_block_alloc(vb,n/samples_per_partition*sizeof(long));
    memset(partword[i],0,n/samples_per_partition*sizeof(long));
  }

Monty's avatar
   
Monty committed
289
  for(i=info->begin,l=0;i<info->end;i+=samples_per_partition,l++){
Monty's avatar
   
Monty committed
290
291
292
    for(j=0;j<ch;j++)
      /* do the partition decision based on the number of 'bits'
         needed to encode the block */
Monty's avatar
   
Monty committed
293
      partword[j][l]=
Monty's avatar
   
Monty committed
294
	_testhack(in[j]+i,samples_per_partition,look,possible_partitions,l);
Monty's avatar
   
Monty committed
295
  
Monty's avatar
   
Monty committed
296
  }
Monty's avatar
   
Monty committed
297
298
  /* we code the partition words for each channel, then the residual
     words for a partition per channel until we've written all the
Monty's avatar
   
Monty committed
299
     residual words for that partition word.  Then write the next
Monty's avatar
   
Monty committed
300
     partition channel words... */
Monty's avatar
   
Monty committed
301
302
  
  for(i=info->begin,l=0;i<info->end;){
Monty's avatar
   
Monty committed
303
    
Monty's avatar
   
Monty committed
304
305
306
307
308
    /* first we encode a partition codeword for each channel */
    for(j=0;j<ch;j++){
      long val=partword[j][l];
      for(k=1;k<partitions_per_word;k++)
	val= val*possible_partitions+partword[j][l+k];
Monty's avatar
   
Monty committed
309
      phrasebits+=vorbis_book_encode(look->phrasebook,val,&vb->opb);
Monty's avatar
   
Monty committed
310
311
312
313
    }
    /* now we encode interleaved residual values for the partitions */
    for(k=0;k<partitions_per_word;k++,l++,i+=samples_per_partition)
      for(j=0;j<ch;j++){
Monty's avatar
   
Monty committed
314
	/*resbits[partword[j][l]]+=*/
Monty's avatar
   
Monty committed
315
	resbitsT+=_encodepart(&vb->opb,in[j]+i,samples_per_partition,
Monty's avatar
   
Monty committed
316
317
			      info->secondstages[partword[j][l]],
			      look->partbooks[partword[j][l]],look->map,partword[j][l]);
Monty's avatar
   
Monty committed
318
319
320
321
322
	resvals[partword[j][l]]+=samples_per_partition;
      }
      
  }

Monty's avatar
   
Monty committed
323
  for(i=0;i<possible_partitions;i++)resbitsT+=resbits[i];
Monty's avatar
   
Monty committed
324
  /*fprintf(stderr,
Monty's avatar
   
Monty committed
325
326
327
    "Encoded %ld res vectors in %ld phrasing and %ld res bits\n\t",
    ch*(info->end-info->begin),phrasebits,resbitsT);
    for(i=0;i<possible_partitions;i++)
Monty's avatar
   
Monty committed
328
    fprintf(stderr,"%ld(%ld):%ld ",i,resvals[i],resbits[i]);
Monty's avatar
   
Monty committed
329
    fprintf(stderr,"\n");*/
Monty's avatar
   
Monty committed
330
 
Monty's avatar
   
Monty committed
331
  return(0);
Monty's avatar
   
Monty committed
332
}
Monty's avatar
   
Monty committed
333

Monty's avatar
   
Monty committed
334
/* a truncated packet here just means 'stop working'; it's not an error */
Monty's avatar
   
Monty committed
335
int res0_inverse(vorbis_block *vb,vorbis_look_residue *vl,float **in,int ch){
Monty's avatar
   
Monty committed
336
  long i,j,k,l,transend=vb->pcmend/2;
Monty's avatar
   
Monty committed
337
338
339
340
341
342
343
344
345
346
347
  vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
  vorbis_info_residue0 *info=look->info;

  /* move all this setup out later */
  int samples_per_partition=info->grouping;
  int partitions_per_word=look->phrasebook->dim;
  int n=info->end-info->begin;

  int partvals=n/samples_per_partition;
  int partwords=(partvals+partitions_per_word-1)/partitions_per_word;
  int **partword=alloca(ch*sizeof(long *));
Monty's avatar
   
Monty committed
348
  float *work=alloca(sizeof(float)*samples_per_partition);
Monty's avatar
   
Monty committed
349
350
  partvals=partwords*partitions_per_word;

Monty's avatar
   
Monty committed
351
352
  /* make sure we're zeroed up to the start */
  for(j=0;j<ch;j++)
Monty's avatar
   
Monty committed
353
    memset(in[j],0,sizeof(float)*info->begin);
Monty's avatar
   
Monty committed
354

Monty's avatar
   
Monty committed
355
356
  for(i=info->begin,l=0;i<info->end;){
    /* fetch the partition word for each channel */
Monty's avatar
   
Monty committed
357
358
    for(j=0;j<ch;j++){
      int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
Monty's avatar
   
Monty committed
359
      if(temp==-1)goto eopbreak;
Monty's avatar
   
Monty committed
360
      partword[j]=look->decodemap[temp];
Monty's avatar
   
Monty committed
361
      if(partword[j]==NULL)goto errout;
Monty's avatar
   
Monty committed
362
    }
Monty's avatar
   
Monty committed
363
    
Monty's avatar
   
Monty committed
364
    /* now we decode interleaved residual values for the partitions */
Monty's avatar
   
Monty committed
365
366
367
    for(k=0;k<partitions_per_word;k++,l++,i+=samples_per_partition)
      for(j=0;j<ch;j++){
	int part=partword[j][k];
Monty's avatar
   
Monty committed
368
	if(_decodepart(&vb->opb,work,in[j]+i,samples_per_partition,
Monty's avatar
   
Monty committed
369
		    info->secondstages[part],
Monty's avatar
   
Monty committed
370
		       look->partbooks[part])==-1)goto eopbreak;
Monty's avatar
   
Monty committed
371
372
373
      }
  }

Monty's avatar
   
Monty committed
374
375
376
 eopbreak:
  if(i<transend){
    for(j=0;j<ch;j++)
Monty's avatar
   
Monty committed
377
      memset(in[j]+i,0,sizeof(float)*(transend-i));
Monty's avatar
   
Monty committed
378
379
380
381
382
383
  }

  return(0);

 errout:
  for(j=0;j<ch;j++)
Monty's avatar
   
Monty committed
384
    memset(in[j],0,sizeof(float)*transend);
Monty's avatar
   
Monty committed
385
  return(0);
Monty's avatar
   
Monty committed
386
387
388
}

vorbis_func_residue residue0_exportbundle={
Monty's avatar
   
Monty committed
389
390
391
  &res0_pack,
  &res0_unpack,
  &res0_look,
Monty's avatar
   
Monty committed
392
  &res0_copy_info,
Monty's avatar
   
Monty committed
393
394
395
396
  &res0_free_info,
  &res0_free_look,
  &res0_forward,
  &res0_inverse
Monty's avatar
   
Monty committed
397
};