res0.c 11 KB
Newer Older
Monty's avatar
   
Monty committed
1
2
3
4
5
6
7
8
9
10
11
12
13
/********************************************************************
 *                                                                  *
 * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
 * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *
 * PLEASE READ THESE TERMS DISTRIBUTING.                            *
 *                                                                  *
 * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000             *
 * by Monty <monty@xiph.org> and The XIPHOPHORUS Company            *
 * http://www.xiph.org/                                             *
 *                                                                  *
 ********************************************************************

Monty's avatar
   
Monty committed
14
 function: residue backend 0 implementation
Monty's avatar
   
Monty committed
15
 last mod: $Id: res0.c,v 1.9 2000/04/03 09:45:55 xiphmont Exp $
Monty's avatar
   
Monty committed
16
17
18

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

Monty's avatar
   
Monty committed
19
20
21
22
23
/* 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
24
25
#include <stdlib.h>
#include <string.h>
Monty's avatar
   
Monty committed
26
#include <math.h>
Monty's avatar
   
Monty committed
27
#include <stdio.h>
Monty's avatar
   
Monty committed
28
29
#include "vorbis/codec.h"
#include "bitwise.h"
Monty's avatar
   
Monty committed
30
#include "registry.h"
Monty's avatar
   
Monty committed
31
#include "scales.h"
Monty's avatar
   
Monty committed
32
33
#include "bookinternal.h"
#include "misc.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
38
39
40
41
42
43
44
45
  
  int         parts;
  codebook   *phrasebook;

  codebook ***partbooks;
  int        *partstages;

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

Monty's avatar
   
Monty committed
48
void free_info(vorbis_info_residue *i){
Monty's avatar
   
Monty committed
49
50
51
52
  if(i){
    memset(i,0,sizeof(vorbis_info_residue0));
    free(i);
  }
Monty's avatar
   
Monty committed
53
54
}

Monty's avatar
   
Monty committed
55
void free_look(vorbis_look_residue *i){
Monty's avatar
   
Monty committed
56
  int j;
Monty's avatar
   
Monty committed
57
  if(i){
Monty's avatar
   
Monty committed
58
59
60
61
62
63
64
65
    vorbis_look_residue0 *look=(vorbis_look_residue0 *)i;
    for(j=0;j<look->parts;j++)
      if(look->partbooks[j])free(look->partbooks[j]);
    free(look->partbooks);
    for(j=0;j<look->partvals;j++)
      free(look->decodemap[j]);
    free(look->decodemap);
    if(look->partstages)free(look->partstages);
Monty's avatar
   
Monty committed
66
67
68
    memset(i,0,sizeof(vorbis_look_residue0));
    free(i);
  }
Monty's avatar
   
Monty committed
69
70
71
}

void pack(vorbis_info_residue *vr,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
  vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  int j,acc=0;
  _oggpack_write(opb,info->begin,24);
  _oggpack_write(opb,info->end,24);

  _oggpack_write(opb,info->grouping-1,24);  /* residue vectors to group and 
					     code with a partitioned book */
  _oggpack_write(opb,info->partitions-1,6); /* possible partition choices */
  _oggpack_write(opb,info->groupbook,8);  /* group huffman book */
  for(j=0;j<info->partitions;j++){
    _oggpack_write(opb,info->secondstages[j],4); /* zero *is* a valid choice */
    acc+=info->secondstages[j];
  }
  for(j=0;j<acc;j++)
    _oggpack_write(opb,info->booklist[j],8);

Monty's avatar
   
Monty committed
88
89
90
91
}

/* vorbis_info is for range checking */
vorbis_info_residue *unpack(vorbis_info *vi,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
92
  int j,acc=0;
Monty's avatar
   
Monty committed
93
94
95
96
97
98
99
100
101
  vorbis_info_residue0 *info=calloc(1,sizeof(vorbis_info_residue0));

  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);
  for(j=0;j<info->partitions;j++)
    acc+=info->secondstages[j]=_oggpack_read(opb,4);
Monty's avatar
   
Monty committed
102
  for(j=0;j<acc;j++)
Monty's avatar
   
Monty committed
103
    info->booklist[j]=_oggpack_read(opb,8);
Monty's avatar
   
Monty committed
104

Monty's avatar
   
Monty committed
105
  if(info->groupbook>=vi->books)goto errout;
Monty's avatar
   
Monty committed
106
  for(j=0;j<acc;j++)
Monty's avatar
   
Monty committed
107
    if(info->booklist[j]>=vi->books)goto errout;
Monty's avatar
   
Monty committed
108

Monty's avatar
   
Monty committed
109
  return(info);
Monty's avatar
   
Monty committed
110
 errout:
Monty's avatar
   
Monty committed
111
  free_info(info);
Monty's avatar
   
Monty committed
112
  return(NULL);
Monty's avatar
   
Monty committed
113
114
}

Monty's avatar
   
Monty committed
115
vorbis_look_residue *look (vorbis_dsp_state *vd,vorbis_info_mode *vm,
Monty's avatar
   
Monty committed
116
			  vorbis_info_residue *vr){
Monty's avatar
   
Monty committed
117
118
  vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  vorbis_look_residue0 *look=calloc(1,sizeof(vorbis_look_residue0));
Monty's avatar
   
Monty committed
119
120
  int j,k,acc=0;
  int dim;
Monty's avatar
   
Monty committed
121
  look->info=info;
Monty's avatar
   
Monty committed
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

  look->parts=info->partitions;
  look->phrasebook=vd->fullbooks+info->groupbook;
  dim=look->phrasebook->dim;

  look->partbooks=calloc(look->parts,sizeof(codebook **));
  look->partstages=calloc(look->parts,sizeof(int));

  for(j=0;j<look->parts;j++){
    int stages=info->secondstages[j];
    if(stages){
      look->partbooks[j]=malloc(stages*sizeof(codebook *));
      for(k=0;k<stages;k++)
	look->partbooks[j][k]=vd->fullbooks+info->booklist[acc++];
    }
    look->partstages[j]=stages;
  }

  look->partvals=pow(look->parts,dim);
  look->decodemap=malloc(look->partvals*sizeof(int *));
  for(j=0;j<look->partvals;j++){
    long val=j;
    long mult=look->partvals/look->parts;
    look->decodemap[j]=malloc(dim*sizeof(int));
    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
152
153
154
  }

  return(look);
Monty's avatar
   
Monty committed
155
}
Monty's avatar
   
Monty committed
156

Monty's avatar
   
Monty committed
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
/* returns the distance error from encoding with this book set */
static double _testpart(double *vec,int n, int stages, codebook **books){
  int i,j;

  double *work=alloca(n*sizeof(double)),acc=0.;
  memcpy(work,vec,n*sizeof(double));

  if(stages==0){
    /* a mild hack.  We want partitions with samples values under
       fabs(.5) to be fully zeroed; if this case is met, we return an
       error of -1 (which cannot be beaten).  If the samples values
       don't meet this criteria, return the real error */
    for(i=0;i<n;i++)
      if(fabs(vec[i])>.5)break;
    if(i==n)return(-1.);
    
    /* real (squared) error */
    for(i=0;i<n;i++)
      acc+=vec[i]*vec[i];

  }else{
    for(j=0;j<stages;j++){
      acc=0.;
      for(i=0;i<n;i+=books[j]->dim)
	acc+=vorbis_book_vE(books[j],work+i);
    }
  }

  return(acc);
}

static int _testhack(double *vec,int n){
  int i;
  double acc=0.;
  double max=0.;
  for(i=0;i<n;i++)
    acc+=todB(fabs(vec[i]));
  acc=fromdB(acc/n);
  for(i=0;i<n;i++)
    max=(fabs(vec[i])>max?fabs(vec[i]):max);

  if(max<.5)return(0);
  if(max<2.5 && acc<1.5)return(1);
  if(max<6.)return(2);
  return(3);
}

static int _encodepart(oggpack_buffer *opb,double *vec, int n,
		       int stages, codebook **books){
  int i,j,bits=0;

  double *work=alloca(n*sizeof(double));
  memcpy(work,vec,n*sizeof(double));

  for(j=0;j<stages;j++)
    for(i=0;i<n;i+=books[j]->dim)
      bits+=vorbis_book_encodevE(books[j],work+i,opb);
  
  return(bits);
}

static int _decodepart(oggpack_buffer *opb,double *work,double *vec, int n,
		       int stages, codebook **books){
  int i,j;

  memset(work,0,n*sizeof(double));
  for(j=0;j<stages;j++)
    for(i=0;i<n;i+=books[j]->dim)
      vorbis_book_decodev(books[j],work+i,opb);

  for(i=0;i<n;i++)
    vec[i]*=work[i];
  
  return(0);
}

int forward(vorbis_block *vb,vorbis_look_residue *vl,
Monty's avatar
   
Monty committed
234
	    double **in,int ch){
Monty's avatar
   
Monty committed
235
236
  long i,j,k,l;
  vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
Monty's avatar
   
Monty committed
237
  vorbis_info_residue0 *info=look->info;
Monty's avatar
   
Monty committed
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315

  /* 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 *));
  partvals=partwords*partitions_per_word;

  /* we find/encode the patition type for each partition of each
     channel.  We'll go back and do the interleaved encoding in a
     bit.  For now, clarity */
  
  if(ch)_analysis_output("a_res",vb->sequence,in[0],n);
  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));
  }

  for(i=info->begin,l=0;i<info->end;i+=samples_per_partition,l++){
    for(j=0;j<ch;j++){
      
      /* find the best encoding for the partition using each possible
         book.  Use the book that had lowest error (we arrange the
         books to make optimal choice very obvious and not even think
         about bits) */
      partword[j][l]=_testhack(in[j]+i,samples_per_partition);

#if 0
      double best=_testpart(in[j]+i,samples_per_partition,
			    look->partstages[0],look->partbooks[0]);
      for(k=1;k<info->partitions;k++){
	double this=_testpart(in[j]+i,samples_per_partition,
			      look->partstages[k],look->partbooks[k]);
	if(this<best){
	  best=this;
	  partword[j][l]=k;
	}
      }
#endif
    }
  }
  
  /* we code the partition words for each channel, then the residual
     words for a partition per channel until we've written all the
     partitions for that partition word.  Then write the next parition
     channel words... */
  
  for(i=info->begin,l=0;i<info->end;){
    /* 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];
      phrasebits+=vorbis_book_encode(look->phrasebook,val,&vb->opb);
    }
    /* 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++){
	resbits[partword[j][l]]+=
	  _encodepart(&vb->opb,in[j]+i,samples_per_partition,
		      look->partstages[partword[j][l]],
		      look->partbooks[partword[j][l]]);
	resvals[partword[j][l]]+=samples_per_partition;
      }
      
  }

  for(i=0;i<possible_partitions;i++)resbitsT+=resbits[i];
Monty's avatar
   
Monty committed
316
  fprintf(stderr,"Encoded %ld res vectors in %ld phrasing and %ld res bits\n\t",
Monty's avatar
   
Monty committed
317
318
319
320
321
	  ch*(info->end-info->begin),phrasebits,resbitsT);
  for(i=0;i<possible_partitions;i++)
    fprintf(stderr,"%ld(%ld):%ld ",i,resvals[i],resbits[i]);
  fprintf(stderr,"\n");

Monty's avatar
   
Monty committed
322
  return(0);
Monty's avatar
   
Monty committed
323
}
Monty's avatar
   
Monty committed
324

Monty's avatar
   
Monty committed
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
int inverse(vorbis_block *vb,vorbis_look_residue *vl,double **in,int ch){
  long i,j,k,l;
  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 *));
  double *work=alloca(sizeof(double)*samples_per_partition);
  partvals=partwords*partitions_per_word;

  for(i=info->begin,l=0;i<info->end;){
    /* fetch the partition word for each channel */
Monty's avatar
   
Monty committed
343
344
345
346
347
    for(j=0;j<ch;j++){
      int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
      partword[j]=look->decodemap[temp];
      if(partword[j]==NULL)exit(1);
    }
Monty's avatar
   
Monty committed
348
    
Monty's avatar
   
Monty committed
349
    /* now we decode interleaved residual values for the partitions */
Monty's avatar
   
Monty committed
350
351
352
353
354
355
356
357
358
359
360
    for(k=0;k<partitions_per_word;k++,l++,i+=samples_per_partition)
      for(j=0;j<ch;j++){
	int part=partword[j][k];
	_decodepart(&vb->opb,work,in[j]+i,samples_per_partition,
		    look->partstages[part],
		    look->partbooks[part]);
      }
  }

  if(ch)_analysis_output("s_res",vb->sequence,in[0],n);

Monty's avatar
   
Monty committed
361
  return(0);
Monty's avatar
   
Monty committed
362
363
364
365
366
367
368
369
370
371
372
}

vorbis_func_residue residue0_exportbundle={
  &pack,
  &unpack,
  &look,
  &free_info,
  &free_look,
  &forward,
  &inverse
};