res0.c 10.9 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.16 2000/08/14 21:53:49 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 "bookinternal.h"
Monty's avatar
   
Monty committed
32
#include "sharedbook.h"
Monty's avatar
   
Monty committed
33
#include "misc.h"
Monty's avatar
   
Monty committed
34
#include "os.h"
Monty's avatar
 
Monty committed
35

Monty's avatar
   
Monty committed
36
37
typedef struct {
  vorbis_info_residue0 *info;
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
void free_info(vorbis_info_residue *i){
Monty's avatar
   
Monty committed
48
49
50
51
  if(i){
    memset(i,0,sizeof(vorbis_info_residue0));
    free(i);
  }
Monty's avatar
 
Monty committed
52
53
}

Monty's avatar
   
Monty committed
54
void free_look(vorbis_look_residue *i){
Monty's avatar
   
Monty committed
55
  int j;
Monty's avatar
   
Monty committed
56
  if(i){
Monty's avatar
   
Monty committed
57
58
59
60
61
62
63
    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);
Monty's avatar
   
Monty committed
64
65
66
    memset(i,0,sizeof(vorbis_look_residue0));
    free(i);
  }
Monty's avatar
   
Monty committed
67
68
69
}

void pack(vorbis_info_residue *vr,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
  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
86
87
88
89
}

/* vorbis_info is for range checking */
vorbis_info_residue *unpack(vorbis_info *vi,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
90
  int j,acc=0;
Monty's avatar
   
Monty committed
91
92
93
94
95
96
97
  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);
Monty's avatar
   
Monty committed
98
  for(j=0;j<info->partitions;j++){
Monty's avatar
   
Monty committed
99
100
101
102
103
    int cascade=info->secondstages[j]=_oggpack_read(opb,4);
    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
104
  }
Monty's avatar
   
Monty committed
105
  for(j=0;j<acc;j++)
Monty's avatar
   
Monty committed
106
    info->booklist[j]=_oggpack_read(opb,8);
Monty's avatar
   
Monty committed
107

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

Monty's avatar
   
Monty committed
112
  return(info);
Monty's avatar
   
Monty committed
113
 errout:
Monty's avatar
   
Monty committed
114
  free_info(info);
Monty's avatar
   
Monty committed
115
  return(NULL);
Monty's avatar
 
Monty committed
116
117
}

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

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

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

  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++];
    }
  }

Monty's avatar
   
Monty committed
141
  look->partvals=rint(pow(look->parts,dim));
Monty's avatar
   
Monty committed
142
143
144
145
146
147
148
149
150
151
152
  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
153
154
155
  }

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

Monty's avatar
   
Monty committed
158
159
160

/* 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
161
162
static int _testhack(double *vec,int n,vorbis_look_residue0 *look,
		     int auxparts,int auxpartnum){
Monty's avatar
   
Monty committed
163
  vorbis_info_residue0 *info=look->info;
Monty's avatar
   
Monty committed
164
165
166
167
168
169
170
171
172
  int i,j=0;
  double max,localmax=0.;
  double temp[128];
  double entropy[8];

  /* setup */
  for(i=0;i<n;i++)temp[i]=fabs(rint(vec[i]));

  /* handle case subgrp==1 outside */
Monty's avatar
   
Monty committed
173
  for(i=0;i<n;i++)
Monty's avatar
   
Monty committed
174
175
    if(temp[i]>localmax)localmax=temp[i];
  max=localmax;
Monty's avatar
   
Monty committed
176
  
Monty's avatar
   
Monty committed
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
  while(1){
    entropy[j]=localmax;
    n>>=1;
    j++;

    if(n<=0)break;
    for(i=0;i<n;i++){
      temp[i]+=temp[i+n];
    }
    localmax=0.;
    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
192
193
    if(auxpartnum<info->blimit[i] &&
       entropy[info->subgrp[i]]<=info->entmax[i] &&
Monty's avatar
   
Monty committed
194
       max<=info->ampmax[i])
Monty's avatar
   
Monty committed
195
      break;
Monty's avatar
   
Monty committed
196

Monty's avatar
   
Monty committed
197
  return(i);
Monty's avatar
   
Monty committed
198
199
200
201
202
203
}

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

Monty's avatar
   
Monty committed
204
205
206
207
208
209
210
  for(j=0;j<stages;j++){
    int dim=books[j]->dim;
    int step=n/dim;
    for(i=0;i<step;i++)
      bits+=vorbis_book_encodevs(books[j],vec+i,opb,step,0);
 
  }
Monty's avatar
   
Monty committed
211
212
213
214
215
216
217

  return(bits);
}

static int _decodepart(oggpack_buffer *opb,double *work,double *vec, int n,
		       int stages, codebook **books){
  int i,j;
Monty's avatar
   
Monty committed
218
219
220
221
222
223
  
  memset(work,0,sizeof(double)*n);
  for(j=0;j<stages;j++){
    int dim=books[j]->dim;
    int step=n/dim;
    for(i=0;i<step;i++)
Monty's avatar
   
Monty committed
224
225
      if(vorbis_book_decodevs(books[j],work+i,opb,step,0)==-1)
	return(-1);
Monty's avatar
   
Monty committed
226
227
  }
  
Monty's avatar
   
Monty committed
228
229
230
231
232
233
234
  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
235
	    double **in,int ch){
Monty's avatar
   
Monty committed
236
237
  long i,j,k,l;
  vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
Monty's avatar
   
Monty committed
238
  vorbis_info_residue0 *info=look->info;
Monty's avatar
   
Monty committed
239
240
241
242
243
244
245
246
247
248
249
250
251

  /* 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
252

Monty's avatar
   
Monty committed
253
254
  partvals=partwords*partitions_per_word;

Monty's avatar
   
Monty committed
255
  /* we find the patition type for each partition of each
Monty's avatar
   
Monty committed
256
257
258
259
260
261
262
263
264
265
266
     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
267
  for(i=info->begin,l=0;i<info->end;i+=samples_per_partition,l++){
Monty's avatar
   
Monty committed
268
269
270
    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
271
      partword[j][l]=
Monty's avatar
   
Monty committed
272
	_testhack(in[j]+i,samples_per_partition,look,possible_partitions,l);
Monty's avatar
   
Monty committed
273
  
Monty's avatar
   
Monty committed
274
  }
Monty's avatar
   
Monty committed
275
276
  /* 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
277
278
     residual words for that partition word.  Then write the next
     parition channel words... */
Monty's avatar
   
Monty committed
279
280
281
282
283
284
285
286
287
288
289
290
291
292
  
  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,
Monty's avatar
   
Monty committed
293
		      info->secondstages[partword[j][l]],
Monty's avatar
   
Monty committed
294
295
296
297
298
299
300
		      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
301
  /*fprintf(stderr,
Monty's avatar
   
Monty committed
302
	  "Encoded %ld res vectors in %ld phrasing and %ld res bits\n\t",
Monty's avatar
   
Monty committed
303
304
305
	  ch*(info->end-info->begin),phrasebits,resbitsT);
  for(i=0;i<possible_partitions;i++)
    fprintf(stderr,"%ld(%ld):%ld ",i,resvals[i],resbits[i]);
Monty's avatar
   
Monty committed
306
    fprintf(stderr,"\n");*/
Monty's avatar
   
Monty committed
307
 
Monty's avatar
   
Monty committed
308
  return(0);
Monty's avatar
   
Monty committed
309
}
Monty's avatar
   
Monty committed
310

Monty's avatar
   
Monty committed
311
/* a truncated packet here just means 'stop working'; it's not an error */
Monty's avatar
   
Monty committed
312
int inverse(vorbis_block *vb,vorbis_look_residue *vl,double **in,int ch){
Monty's avatar
   
Monty committed
313
  long i,j,k,l,transend=vb->pcmend/2;
Monty's avatar
   
Monty committed
314
315
316
317
318
319
320
321
322
323
324
325
326
327
  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;

Monty's avatar
   
Monty committed
328
329
330
331
  /* make sure we're zeroed up to the start */
  for(j=0;j<ch;j++)
    memset(in[j],0,sizeof(double)*info->begin);

Monty's avatar
   
Monty committed
332
333
  for(i=info->begin,l=0;i<info->end;){
    /* fetch the partition word for each channel */
Monty's avatar
   
Monty committed
334
335
    for(j=0;j<ch;j++){
      int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
Monty's avatar
   
Monty committed
336
      if(temp==-1)goto eopbreak;
Monty's avatar
   
Monty committed
337
      partword[j]=look->decodemap[temp];
Monty's avatar
   
Monty committed
338
      if(partword[j]==NULL)goto errout;
Monty's avatar
   
Monty committed
339
    }
Monty's avatar
   
Monty committed
340
    
Monty's avatar
   
Monty committed
341
    /* now we decode interleaved residual values for the partitions */
Monty's avatar
   
Monty committed
342
343
344
    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
345
	if(_decodepart(&vb->opb,work,in[j]+i,samples_per_partition,
Monty's avatar
   
Monty committed
346
		    info->secondstages[part],
Monty's avatar
   
Monty committed
347
		       look->partbooks[part])==-1)goto eopbreak;
Monty's avatar
   
Monty committed
348
349
350
      }
  }

Monty's avatar
   
Monty committed
351
352
353
354
355
356
357
358
359
360
361
 eopbreak:
  if(i<transend){
    for(j=0;j<ch;j++)
      memset(in[j]+i,0,sizeof(double)*(transend-i));
  }

  return(0);

 errout:
  for(j=0;j<ch;j++)
    memset(in[j],0,sizeof(double)*transend);
Monty's avatar
   
Monty committed
362
  return(0);
Monty's avatar
   
Monty committed
363
364
365
366
367
368
369
370
371
372
373
}

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