Fixes a bug in ec_enc_done when no range coded data was coded and adds test cases...
[opus.git] / celt / tests / test_unit_entropy.c
1 #ifdef HAVE_CONFIG_H
2 #include "config.h"
3 #endif
4
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include <math.h>
8 #include <time.h>
9 #include "entcode.h"
10 #include "entenc.h"
11 #include "entdec.h"
12 #include <string.h>
13
14 #include "entenc.c"
15 #include "entdec.c"
16 #include "entcode.c"
17
18 #ifndef M_LOG2E
19 # define M_LOG2E    1.4426950408889634074
20 #endif
21 #define DATA_SIZE 10000000
22 #define DATA_SIZE2 10000
23
24 int main(int _argc,char **_argv){
25   ec_enc         enc;
26   ec_dec         dec;
27   long           nbits;
28   long           nbits2;
29   double         entropy;
30   int            ft;
31   int            ftb;
32   int            sz;
33   int            i;
34   int            ret;
35   unsigned int   sym;
36   unsigned int   seed;
37   unsigned char *ptr;
38   ret=0;
39   entropy=0;
40     if (_argc > 2) {
41         fprintf(stderr, "Usage: %s [<seed>]\n", _argv[0]);
42         return 1;
43     }
44     if (_argc > 1)
45         seed = atoi(_argv[1]);
46     else
47         seed = time(NULL);
48   /*Testing encoding of raw bit values.*/
49   ptr = (unsigned char *)malloc(DATA_SIZE);
50   ec_enc_init(&enc,ptr, DATA_SIZE);
51   for(ft=2;ft<1024;ft++){
52     for(i=0;i<ft;i++){
53       entropy+=log(ft)*M_LOG2E;
54       ec_enc_uint(&enc,i,ft);
55     }
56   }
57   /*Testing encoding of raw bit values.*/
58   for(ftb=1;ftb<16;ftb++){
59     for(i=0;i<(1<<ftb);i++){
60       entropy+=ftb;
61       nbits=ec_tell(&enc);
62       ec_enc_bits(&enc,i,ftb);
63       nbits2=ec_tell(&enc);
64       if(nbits2-nbits!=ftb){
65         fprintf(stderr,"Used %li bits to encode %i bits directly.\n",
66          nbits2-nbits,ftb);
67         ret=-1;
68       }
69     }
70   }
71   nbits=ec_tell_frac(&enc);
72   ec_enc_done(&enc);
73   fprintf(stderr,
74    "Encoded %0.2lf bits of entropy to %0.2lf bits (%0.3lf%% wasted).\n",
75    entropy,ldexp(nbits,-3),100*(nbits-ldexp(entropy,3))/nbits);
76   fprintf(stderr,"Packed to %li bytes.\n",(long)ec_range_bytes(&enc));
77   ec_dec_init(&dec,ptr,DATA_SIZE);
78   for(ft=2;ft<1024;ft++){
79     for(i=0;i<ft;i++){
80       sym=ec_dec_uint(&dec,ft);
81       if(sym!=(unsigned)i){
82         fprintf(stderr,"Decoded %i instead of %i with ft of %i.\n",sym,i,ft);
83         ret=-1;
84       }
85     }
86   }
87   for(ftb=1;ftb<16;ftb++){
88     for(i=0;i<(1<<ftb);i++){
89       sym=ec_dec_bits(&dec,ftb);
90       if(sym!=(unsigned)i){
91         fprintf(stderr,"Decoded %i instead of %i with ftb of %i.\n",sym,i,ftb);
92         ret=-1;
93       }
94     }
95   }
96   nbits2=ec_tell_frac(&dec);
97   if(nbits!=nbits2){
98     fprintf(stderr,
99      "Reported number of bits used was %0.2lf, should be %0.2lf.\n",
100      ldexp(nbits2,-3),ldexp(nbits,-3));
101     ret=-1;
102   }
103   /*Testing an encoder bust prefers range coder data over raw bits.
104     This isn't a general guarantee, will only work for data that is buffered in
105      the encoder state and not yet stored in the user buffer, and should never
106      get used in practice.
107     It's mostly here for code coverage completeness.*/
108   /*Start with a 16-bit buffer.*/
109   ec_enc_init(&enc,ptr,2);
110   /*Write 7 raw bits.*/
111   ec_enc_bits(&enc,0x55,7);
112   /*Write 12.3 bits of range coder data.*/
113   ec_enc_uint(&enc,1,2);
114   ec_enc_uint(&enc,1,3);
115   ec_enc_uint(&enc,1,4);
116   ec_enc_uint(&enc,1,5);
117   ec_enc_uint(&enc,2,6);
118   ec_enc_uint(&enc,6,7);
119   ec_enc_done(&enc);
120   ec_dec_init(&dec,ptr,2);
121   if(!enc.error
122    /*The raw bits should have been overwritten by the range coder data.*/
123    ||ec_dec_bits(&dec,7)!=0x05
124    /*And all the range coder data should have been encoded correctly.*/
125    ||ec_dec_uint(&dec,2)!=1
126    ||ec_dec_uint(&dec,3)!=1
127    ||ec_dec_uint(&dec,4)!=1
128    ||ec_dec_uint(&dec,5)!=1
129    ||ec_dec_uint(&dec,6)!=2
130    ||ec_dec_uint(&dec,7)!=6){
131     fprintf(stderr,"Encoder bust overwrote range coder data with raw bits.\n");
132     ret=-1;
133   }
134   srand(seed);
135   fprintf(stderr,"Testing random streams... Random seed: %u (%.4X)\n", seed, rand() % 65536);
136   for(i=0;i<409600;i++){
137     unsigned *data;
138     unsigned *tell;
139     unsigned tell_bits;
140     int       j;
141     int zeros;
142     ft=rand()/((RAND_MAX>>(rand()%11U))+1U)+10;
143     sz=rand()/((RAND_MAX>>(rand()%9U))+1U);
144     data=(unsigned *)malloc(sz*sizeof(*data));
145     tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
146     ec_enc_init(&enc,ptr,DATA_SIZE2);
147     zeros = rand()%13==0;
148     tell[0]=ec_tell_frac(&enc);
149     for(j=0;j<sz;j++){
150       if (zeros)
151         data[j]=0;
152       else
153         data[j]=rand()%ft;
154       ec_enc_uint(&enc,data[j],ft);
155       tell[j+1]=ec_tell_frac(&enc);
156     }
157     if (rand()%2==0)
158       while(ec_tell(&enc)%8 != 0)
159         ec_enc_uint(&enc, rand()%2, 2);
160     tell_bits = ec_tell(&enc);
161     ec_enc_done(&enc);
162     if(tell_bits!=(unsigned)ec_tell(&enc)){
163       fprintf(stderr,"ec_tell() changed after ec_enc_done(): %i instead of %i (Random seed: %u)\n",
164        ec_tell(&enc),tell_bits,seed);
165       ret=-1;
166     }
167     if ((tell_bits+7)/8 < ec_range_bytes(&enc))
168     {
169       fprintf (stderr, "ec_tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
170                ec_range_bytes(&enc), (tell_bits+7)/8,seed);
171       ret=-1;
172     }
173     ec_dec_init(&dec,ptr,DATA_SIZE2);
174     if(ec_tell_frac(&dec)!=tell[0]){
175       fprintf(stderr,
176        "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
177        0,ec_tell_frac(&dec),tell[0],seed);
178     }
179     for(j=0;j<sz;j++){
180       sym=ec_dec_uint(&dec,ft);
181       if(sym!=data[j]){
182         fprintf(stderr,
183          "Decoded %i instead of %i with ft of %i at position %i of %i (Random seed: %u).\n",
184          sym,data[j],ft,j,sz,seed);
185         ret=-1;
186       }
187       if(ec_tell_frac(&dec)!=tell[j+1]){
188         fprintf(stderr,
189          "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
190          j+1,ec_tell_frac(&dec),tell[j+1],seed);
191       }
192     }
193     free(tell);
194     free(data);
195   }
196   /*Test compatibility between multiple different encode/decode routines.*/
197   for(i=0;i<409600;i++){
198     unsigned *logp1;
199     unsigned *data;
200     unsigned *tell;
201     unsigned *enc_method;
202     int       j;
203     sz=rand()/((RAND_MAX>>(rand()%9U))+1U);
204     logp1=(unsigned *)malloc(sz*sizeof(*logp1));
205     data=(unsigned *)malloc(sz*sizeof(*data));
206     tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
207     enc_method=(unsigned *)malloc(sz*sizeof(*enc_method));
208     ec_enc_init(&enc,ptr,DATA_SIZE2);
209     tell[0]=ec_tell_frac(&enc);
210     for(j=0;j<sz;j++){
211       data[j]=rand()/((RAND_MAX>>1)+1);
212       logp1[j]=(rand()%15)+1;
213       enc_method[j]=rand()/((RAND_MAX>>2)+1);
214       switch(enc_method[j]){
215         case 0:{
216           ec_encode(&enc,data[j]?(1<<logp1[j])-1:0,
217            (1<<logp1[j])-(data[j]?0:1),1<<logp1[j]);
218         }break;
219         case 1:{
220           ec_encode_bin(&enc,data[j]?(1<<logp1[j])-1:0,
221            (1<<logp1[j])-(data[j]?0:1),logp1[j]);
222         }break;
223         case 2:{
224           ec_enc_bit_logp(&enc,data[j],logp1[j]);
225         }break;
226         case 3:{
227           unsigned char icdf[2];
228           icdf[0]=1;
229           icdf[1]=0;
230           ec_enc_icdf(&enc,data[j],icdf,logp1[j]);
231         }break;
232       }
233       tell[j+1]=ec_tell_frac(&enc);
234     }
235     ec_enc_done(&enc);
236     if((ec_tell(&enc)+7U)/8U<ec_range_bytes(&enc)){
237       fprintf(stderr,"tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
238        ec_range_bytes(&enc),(ec_tell(&enc)+7)/8,seed);
239       ret=-1;
240     }
241     ec_dec_init(&dec,ptr,DATA_SIZE2);
242     if(ec_tell_frac(&dec)!=tell[0]){
243       fprintf(stderr,
244        "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
245        0,ec_tell_frac(&dec),tell[0],seed);
246     }
247     for(j=0;j<sz;j++){
248       int fs;
249       int dec_method;
250       dec_method=rand()/((RAND_MAX>>2)+1);
251       switch(dec_method){
252         case 0:{
253           fs=ec_decode(&dec,1<<logp1[j]);
254           sym=fs>=(1<<logp1[j])-1;
255           ec_dec_update(&dec,sym?(1<<logp1[j])-1:0,
256            (1<<logp1[j])-(sym?0:1),1<<logp1[j]);
257         }break;
258         case 1:{
259           fs=ec_decode_bin(&dec,logp1[j]);
260           sym=fs>=(1<<logp1[j])-1;
261           ec_dec_update(&dec,sym?(1<<logp1[j])-1:0,
262            (1<<logp1[j])-(sym?0:1),1<<logp1[j]);
263         }break;
264         case 2:{
265           sym=ec_dec_bit_logp(&dec,logp1[j]);
266         }break;
267         case 3:{
268           unsigned char icdf[2];
269           icdf[0]=1;
270           icdf[1]=0;
271           sym=ec_dec_icdf(&dec,icdf,logp1[j]);
272         }break;
273       }
274       if(sym!=data[j]){
275         fprintf(stderr,
276          "Decoded %i instead of %i with logp1 of %i at position %i of %i (Random seed: %u).\n",
277          sym,data[j],logp1[j],j,sz,seed);
278         fprintf(stderr,"Encoding method: %i, decoding method: %i\n",
279          enc_method[j],dec_method);
280         ret=-1;
281       }
282       if(ec_tell_frac(&dec)!=tell[j+1]){
283         fprintf(stderr,
284          "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
285          j+1,ec_tell_frac(&dec),tell[j+1],seed);
286       }
287     }
288     free(enc_method);
289     free(tell);
290     free(data);
291     free(logp1);
292   }
293   ec_enc_init(&enc,ptr,DATA_SIZE2);
294   ec_enc_bit_logp(&enc,0,1);
295   ec_enc_bit_logp(&enc,0,1);
296   ec_enc_bit_logp(&enc,0,1);
297   ec_enc_bit_logp(&enc,0,1);
298   ec_enc_bit_logp(&enc,0,2);
299   ec_enc_patch_initial_bits(&enc,3,2);
300   if(enc.error){
301     fprintf(stderr,"patch_initial_bits failed");
302     ret=-1;
303   }
304   ec_enc_patch_initial_bits(&enc,0,5);
305   if(!enc.error){
306     fprintf(stderr,"patch_initial_bits didn't fail when it should have");
307     ret=-1;
308   }
309   ec_enc_done(&enc);
310   if(ec_range_bytes(&enc)!=1||ptr[0]!=192){
311     fprintf(stderr,"Got %d when expecting 192 for patch_initial_bits",ptr[0]);
312     ret=-1;
313   }
314   ec_enc_init(&enc,ptr,DATA_SIZE2);
315   ec_enc_bit_logp(&enc,0,1);
316   ec_enc_bit_logp(&enc,0,1);
317   ec_enc_bit_logp(&enc,1,6);
318   ec_enc_bit_logp(&enc,0,2);
319   ec_enc_patch_initial_bits(&enc,0,2);
320   if(enc.error){
321     fprintf(stderr,"patch_initial_bits failed");
322     ret=-1;
323   }
324   ec_enc_done(&enc);
325   if(ec_range_bytes(&enc)!=2||ptr[0]!=63){
326     fprintf(stderr,"Got %d when expecting 63 for patch_initial_bits",ptr[0]);
327     ret=-1;
328   }
329   ec_enc_init(&enc,ptr,2);
330   ec_enc_bit_logp(&enc,0,2);
331   for(i=0;i<48;i++){
332     ec_enc_bits(&enc,0,1);
333   }
334   ec_enc_done(&enc);
335   if(!enc.error){
336     fprintf(stderr,"Raw bits overfill didn't fail when it should have");
337     ret=-1;
338   }
339   ec_enc_init(&enc,ptr,2);
340   for(i=0;i<17;i++){
341     ec_enc_bits(&enc,0,1);
342   }
343   ec_enc_done(&enc);
344   if(!enc.error){
345     fprintf(stderr,"17 raw bits encoded in two bytes");
346     ret=-1;
347   }
348   free(ptr);
349   return ret;
350 }