res0.c 11.2 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.18 2000/10/12 03:12:53 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
#include <ogg/ogg.h>
Monty's avatar
 
Monty committed
29
#include "vorbis/codec.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
  int         map;
Monty's avatar
   
Monty committed
39
40
41
42
43
44
45
  
  int         parts;
  codebook   *phrasebook;
  codebook ***partbooks;

  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 res0_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 res0_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
    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
65
66
67
    memset(i,0,sizeof(vorbis_look_residue0));
    free(i);
  }
Monty's avatar
   
Monty committed
68
69
}

Monty's avatar
   
Monty committed
70
void res0_pack(vorbis_info_residue *vr,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
71
72
  vorbis_info_residue0 *info=(vorbis_info_residue0 *)vr;
  int j,acc=0;
Monty's avatar
   
Monty committed
73
74
  oggpack_write(opb,info->begin,24);
  oggpack_write(opb,info->end,24);
Monty's avatar
   
Monty committed
75

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

Monty's avatar
   
Monty committed
87
88
89
}

/* vorbis_info is for range checking */
Monty's avatar
   
Monty committed
90
vorbis_info_residue *res0_unpack(vorbis_info *vi,oggpack_buffer *opb){
Monty's avatar
   
Monty committed
91
  int j,acc=0;
Monty's avatar
   
Monty committed
92
93
  vorbis_info_residue0 *info=calloc(1,sizeof(vorbis_info_residue0));

Monty's avatar
   
Monty committed
94
95
96
97
98
  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
99
  for(j=0;j<info->partitions;j++){
Monty's avatar
   
Monty committed
100
    int cascade=info->secondstages[j]=oggpack_read(opb,4);
Monty's avatar
   
Monty committed
101
102
103
104
    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
105
  }
Monty's avatar
   
Monty committed
106
  for(j=0;j<acc;j++)
Monty's avatar
   
Monty committed
107
    info->booklist[j]=oggpack_read(opb,8);
Monty's avatar
   
Monty committed
108

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

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

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

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

  return(look);
Monty's avatar
 
Monty committed
158
}
Monty's avatar
   
Monty committed
159

Monty's avatar
   
Monty committed
160
161
162

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

  /* setup */
Monty's avatar
   
Monty committed
172
  for(i=0;i<n;i++)temp[i]=fabs(vec[i]);
Monty's avatar
   
Monty committed
173
174

  /* handle case subgrp==1 outside */
Monty's avatar
   
Monty committed
175
  for(i=0;i<n;i++)
Monty's avatar
   
Monty committed
176
177
    if(temp[i]>localmax)localmax=temp[i];
  max=localmax;
Monty's avatar
   
Monty committed
178
179

  for(i=0;i<n;i++)temp[i]=rint(temp[i]);
Monty's avatar
   
Monty committed
180
  
Monty's avatar
   
Monty committed
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
  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
196
197
    if(auxpartnum<info->blimit[i] &&
       entropy[info->subgrp[i]]<=info->entmax[i] &&
Monty's avatar
   
Monty committed
198
       max<=info->ampmax[i])
Monty's avatar
   
Monty committed
199
      break;
Monty's avatar
   
Monty committed
200

Monty's avatar
   
Monty committed
201
  return(i);
Monty's avatar
   
Monty committed
202
203
}

Monty's avatar
   
Monty committed
204
static int _encodepart(oggpack_buffer *opb,float *vec, int n,
Monty's avatar
   
Monty committed
205
		       int stages, codebook **books,int mode,int part){
Monty's avatar
   
Monty committed
206
207
  int i,j,bits=0;

Monty's avatar
   
Monty committed
208
209
210
  for(j=0;j<stages;j++){
    int dim=books[j]->dim;
    int step=n/dim;
Monty's avatar
   
Monty committed
211
212
213
214
215
216
217
218
219
220
221
222
223
224
    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
      bits+=vorbis_book_encode(books[j],entry,opb);
    }
Monty's avatar
   
Monty committed
225
  }
Monty's avatar
   
Monty committed
226
227
228
229

  return(bits);
}

Monty's avatar
   
Monty committed
230
static int _decodepart(oggpack_buffer *opb,float *work,float *vec, int n,
Monty's avatar
   
Monty committed
231
		       int stages, codebook **books){
Monty's avatar
   
Monty committed
232
  int i;
Monty's avatar
   
Monty committed
233
  
Monty's avatar
   
Monty committed
234
235
236
  memset(work,0,sizeof(float)*n);
  for(i=0;i<stages;i++){
    int dim=books[i]->dim;
Monty's avatar
   
Monty committed
237
    int step=n/dim;
Monty's avatar
   
Monty committed
238
239
    if(s_vorbis_book_decodevs(books[i],work,opb,step,0)==-1)
      return(-1);
Monty's avatar
   
Monty committed
240
241
  }
  
Monty's avatar
   
Monty committed
242
243
244
245
246
247
  for(i=0;i<n;i++)
    vec[i]*=work[i];
  
  return(0);
}

Monty's avatar
   
Monty committed
248
249
int res0_forward(vorbis_block *vb,vorbis_look_residue *vl,
	    float **in,int ch){
Monty's avatar
   
Monty committed
250
251
  long i,j,k,l;
  vorbis_look_residue0 *look=(vorbis_look_residue0 *)vl;
Monty's avatar
   
Monty committed
252
  vorbis_info_residue0 *info=look->info;
Monty's avatar
   
Monty committed
253
254
255
256
257
258
259
260
261
262
263
264
265

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

Monty's avatar
   
Monty committed
267
268
  partvals=partwords*partitions_per_word;

Monty's avatar
   
Monty committed
269
  /* we find the patition type for each partition of each
Monty's avatar
   
Monty committed
270
271
272
273
274
275
276
277
278
279
280
     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
281
  for(i=info->begin,l=0;i<info->end;i+=samples_per_partition,l++){
Monty's avatar
   
Monty committed
282
283
284
    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
285
      partword[j][l]=
Monty's avatar
   
Monty committed
286
	_testhack(in[j]+i,samples_per_partition,look,possible_partitions,l);
Monty's avatar
   
Monty committed
287
  
Monty's avatar
   
Monty committed
288
  }
Monty's avatar
   
Monty committed
289
290
  /* 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
291
     residual words for that partition word.  Then write the next
Monty's avatar
   
Monty committed
292
     partition channel words... */
Monty's avatar
   
Monty committed
293
294
295
296
297
298
299
300
301
302
303
304
305
306
  
  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
307
		      info->secondstages[partword[j][l]],
Monty's avatar
   
Monty committed
308
		      look->partbooks[partword[j][l]],look->map,partword[j][l]);
Monty's avatar
   
Monty committed
309
310
311
312
313
314
	resvals[partword[j][l]]+=samples_per_partition;
      }
      
  }

  for(i=0;i<possible_partitions;i++)resbitsT+=resbits[i];
Monty's avatar
   
Monty committed
315
  /*fprintf(stderr,
Monty's avatar
   
Monty committed
316
	  "Encoded %ld res vectors in %ld phrasing and %ld res bits\n\t",
Monty's avatar
   
Monty committed
317
318
319
	  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
320
    fprintf(stderr,"\n");*/
Monty's avatar
   
Monty committed
321
 
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
/* a truncated packet here just means 'stop working'; it's not an error */
Monty's avatar
   
Monty committed
326
int res0_inverse(vorbis_block *vb,vorbis_look_residue *vl,float **in,int ch){
Monty's avatar
   
Monty committed
327
  long i,j,k,l,transend=vb->pcmend/2;
Monty's avatar
   
Monty committed
328
329
330
331
332
333
334
335
336
337
338
  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
339
  float *work=alloca(sizeof(float)*samples_per_partition);
Monty's avatar
   
Monty committed
340
341
  partvals=partwords*partitions_per_word;

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

Monty's avatar
   
Monty committed
346
347
  for(i=info->begin,l=0;i<info->end;){
    /* fetch the partition word for each channel */
Monty's avatar
   
Monty committed
348
349
    for(j=0;j<ch;j++){
      int temp=vorbis_book_decode(look->phrasebook,&vb->opb);
Monty's avatar
   
Monty committed
350
      if(temp==-1)goto eopbreak;
Monty's avatar
   
Monty committed
351
      partword[j]=look->decodemap[temp];
Monty's avatar
   
Monty committed
352
      if(partword[j]==NULL)goto errout;
Monty's avatar
   
Monty committed
353
    }
Monty's avatar
   
Monty committed
354
    
Monty's avatar
   
Monty committed
355
    /* now we decode interleaved residual values for the partitions */
Monty's avatar
   
Monty committed
356
357
358
    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
359
	if(_decodepart(&vb->opb,work,in[j]+i,samples_per_partition,
Monty's avatar
   
Monty committed
360
		    info->secondstages[part],
Monty's avatar
   
Monty committed
361
		       look->partbooks[part])==-1)goto eopbreak;
Monty's avatar
   
Monty committed
362
363
364
      }
  }

Monty's avatar
   
Monty committed
365
366
367
 eopbreak:
  if(i<transend){
    for(j=0;j<ch;j++)
Monty's avatar
   
Monty committed
368
      memset(in[j]+i,0,sizeof(float)*(transend-i));
Monty's avatar
   
Monty committed
369
370
371
372
373
374
  }

  return(0);

 errout:
  for(j=0;j<ch;j++)
Monty's avatar
   
Monty committed
375
    memset(in[j],0,sizeof(float)*transend);
Monty's avatar
   
Monty committed
376
  return(0);
Monty's avatar
   
Monty committed
377
378
379
}

vorbis_func_residue residue0_exportbundle={
Monty's avatar
   
Monty committed
380
381
382
383
384
385
386
  &res0_pack,
  &res0_unpack,
  &res0_look,
  &res0_free_info,
  &res0_free_look,
  &res0_forward,
  &res0_inverse
Monty's avatar
   
Monty committed
387
};