Fix for an assertion when running the fixed point tests
[opus.git] / celt / tests / test_unit_entropy.c
1 /* Copyright (c) 2007-2011 Xiph.Org Foundation, Mozilla Corporation,
2                            Gregory Maxwell
3    Written by Jean-Marc Valin, Gregory Maxwell, and Timothy B. Terriberry */
4 /*
5    Redistribution and use in source and binary forms, with or without
6    modification, are permitted provided that the following conditions
7    are met:
8
9    - Redistributions of source code must retain the above copyright
10    notice, this list of conditions and the following disclaimer.
11
12    - Redistributions in binary form must reproduce the above copyright
13    notice, this list of conditions and the following disclaimer in the
14    documentation and/or other materials provided with the distribution.
15
16    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
20    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #ifdef HAVE_CONFIG_H
30 #include "config.h"
31 #endif
32
33 #include <stdlib.h>
34 #include <stdio.h>
35 #include <math.h>
36 #include <time.h>
37 #define CELT_C
38 #include "entcode.h"
39 #include "entenc.h"
40 #include "entdec.h"
41 #include <string.h>
42
43 #include "entenc.c"
44 #include "entdec.c"
45 #include "entcode.c"
46
47 #ifndef M_LOG2E
48 # define M_LOG2E    1.4426950408889634074
49 #endif
50 #define DATA_SIZE 10000000
51 #define DATA_SIZE2 10000
52
53 int main(int _argc,char **_argv){
54   ec_enc         enc;
55   ec_dec         dec;
56   long           nbits;
57   long           nbits2;
58   double         entropy;
59   int            ft;
60   int            ftb;
61   int            sz;
62   int            i;
63   int            ret;
64   unsigned int   sym;
65   unsigned int   seed;
66   unsigned char *ptr;
67   const char    *env_seed;
68   ret=0;
69   entropy=0;
70   if (_argc > 2) {
71     fprintf(stderr, "Usage: %s [<seed>]\n", _argv[0]);
72     return 1;
73   }
74   env_seed = getenv("SEED");
75   if (_argc > 1)
76     seed = atoi(_argv[1]);
77   else if (env_seed)
78     seed = atoi(env_seed);
79   else
80     seed = time(NULL);
81   /*Testing encoding of raw bit values.*/
82   ptr = (unsigned char *)malloc(DATA_SIZE);
83   ec_enc_init(&enc,ptr, DATA_SIZE);
84   for(ft=2;ft<1024;ft++){
85     for(i=0;i<ft;i++){
86       entropy+=log(ft)*M_LOG2E;
87       ec_enc_uint(&enc,i,ft);
88     }
89   }
90   /*Testing encoding of raw bit values.*/
91   for(ftb=1;ftb<16;ftb++){
92     for(i=0;i<(1<<ftb);i++){
93       entropy+=ftb;
94       nbits=ec_tell(&enc);
95       ec_enc_bits(&enc,i,ftb);
96       nbits2=ec_tell(&enc);
97       if(nbits2-nbits!=ftb){
98         fprintf(stderr,"Used %li bits to encode %i bits directly.\n",
99          nbits2-nbits,ftb);
100         ret=-1;
101       }
102     }
103   }
104   nbits=ec_tell_frac(&enc);
105   ec_enc_done(&enc);
106   fprintf(stderr,
107    "Encoded %0.2lf bits of entropy to %0.2lf bits (%0.3lf%% wasted).\n",
108    entropy,ldexp(nbits,-3),100*(nbits-ldexp(entropy,3))/nbits);
109   fprintf(stderr,"Packed to %li bytes.\n",(long)ec_range_bytes(&enc));
110   ec_dec_init(&dec,ptr,DATA_SIZE);
111   for(ft=2;ft<1024;ft++){
112     for(i=0;i<ft;i++){
113       sym=ec_dec_uint(&dec,ft);
114       if(sym!=(unsigned)i){
115         fprintf(stderr,"Decoded %i instead of %i with ft of %i.\n",sym,i,ft);
116         ret=-1;
117       }
118     }
119   }
120   for(ftb=1;ftb<16;ftb++){
121     for(i=0;i<(1<<ftb);i++){
122       sym=ec_dec_bits(&dec,ftb);
123       if(sym!=(unsigned)i){
124         fprintf(stderr,"Decoded %i instead of %i with ftb of %i.\n",sym,i,ftb);
125         ret=-1;
126       }
127     }
128   }
129   nbits2=ec_tell_frac(&dec);
130   if(nbits!=nbits2){
131     fprintf(stderr,
132      "Reported number of bits used was %0.2lf, should be %0.2lf.\n",
133      ldexp(nbits2,-3),ldexp(nbits,-3));
134     ret=-1;
135   }
136   /*Testing an encoder bust prefers range coder data over raw bits.
137     This isn't a general guarantee, will only work for data that is buffered in
138      the encoder state and not yet stored in the user buffer, and should never
139      get used in practice.
140     It's mostly here for code coverage completeness.*/
141   /*Start with a 16-bit buffer.*/
142   ec_enc_init(&enc,ptr,2);
143   /*Write 7 raw bits.*/
144   ec_enc_bits(&enc,0x55,7);
145   /*Write 12.3 bits of range coder data.*/
146   ec_enc_uint(&enc,1,2);
147   ec_enc_uint(&enc,1,3);
148   ec_enc_uint(&enc,1,4);
149   ec_enc_uint(&enc,1,5);
150   ec_enc_uint(&enc,2,6);
151   ec_enc_uint(&enc,6,7);
152   ec_enc_done(&enc);
153   ec_dec_init(&dec,ptr,2);
154   if(!enc.error
155    /*The raw bits should have been overwritten by the range coder data.*/
156    ||ec_dec_bits(&dec,7)!=0x05
157    /*And all the range coder data should have been encoded correctly.*/
158    ||ec_dec_uint(&dec,2)!=1
159    ||ec_dec_uint(&dec,3)!=1
160    ||ec_dec_uint(&dec,4)!=1
161    ||ec_dec_uint(&dec,5)!=1
162    ||ec_dec_uint(&dec,6)!=2
163    ||ec_dec_uint(&dec,7)!=6){
164     fprintf(stderr,"Encoder bust overwrote range coder data with raw bits.\n");
165     ret=-1;
166   }
167   srand(seed);
168   fprintf(stderr,"Testing random streams... Random seed: %u (%.4X)\n", seed, rand() % 65536);
169   for(i=0;i<409600;i++){
170     unsigned *data;
171     unsigned *tell;
172     unsigned tell_bits;
173     int       j;
174     int zeros;
175     ft=rand()/((RAND_MAX>>(rand()%11U))+1U)+10;
176     sz=rand()/((RAND_MAX>>(rand()%9U))+1U);
177     data=(unsigned *)malloc(sz*sizeof(*data));
178     tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
179     ec_enc_init(&enc,ptr,DATA_SIZE2);
180     zeros = rand()%13==0;
181     tell[0]=ec_tell_frac(&enc);
182     for(j=0;j<sz;j++){
183       if (zeros)
184         data[j]=0;
185       else
186         data[j]=rand()%ft;
187       ec_enc_uint(&enc,data[j],ft);
188       tell[j+1]=ec_tell_frac(&enc);
189     }
190     if (rand()%2==0)
191       while(ec_tell(&enc)%8 != 0)
192         ec_enc_uint(&enc, rand()%2, 2);
193     tell_bits = ec_tell(&enc);
194     ec_enc_done(&enc);
195     if(tell_bits!=(unsigned)ec_tell(&enc)){
196       fprintf(stderr,"ec_tell() changed after ec_enc_done(): %i instead of %i (Random seed: %u)\n",
197        ec_tell(&enc),tell_bits,seed);
198       ret=-1;
199     }
200     if ((tell_bits+7)/8 < ec_range_bytes(&enc))
201     {
202       fprintf (stderr, "ec_tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
203                ec_range_bytes(&enc), (tell_bits+7)/8,seed);
204       ret=-1;
205     }
206     ec_dec_init(&dec,ptr,DATA_SIZE2);
207     if(ec_tell_frac(&dec)!=tell[0]){
208       fprintf(stderr,
209        "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
210        0,ec_tell_frac(&dec),tell[0],seed);
211     }
212     for(j=0;j<sz;j++){
213       sym=ec_dec_uint(&dec,ft);
214       if(sym!=data[j]){
215         fprintf(stderr,
216          "Decoded %i instead of %i with ft of %i at position %i of %i (Random seed: %u).\n",
217          sym,data[j],ft,j,sz,seed);
218         ret=-1;
219       }
220       if(ec_tell_frac(&dec)!=tell[j+1]){
221         fprintf(stderr,
222          "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
223          j+1,ec_tell_frac(&dec),tell[j+1],seed);
224       }
225     }
226     free(tell);
227     free(data);
228   }
229   /*Test compatibility between multiple different encode/decode routines.*/
230   for(i=0;i<409600;i++){
231     unsigned *logp1;
232     unsigned *data;
233     unsigned *tell;
234     unsigned *enc_method;
235     int       j;
236     sz=rand()/((RAND_MAX>>(rand()%9U))+1U);
237     logp1=(unsigned *)malloc(sz*sizeof(*logp1));
238     data=(unsigned *)malloc(sz*sizeof(*data));
239     tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
240     enc_method=(unsigned *)malloc(sz*sizeof(*enc_method));
241     ec_enc_init(&enc,ptr,DATA_SIZE2);
242     tell[0]=ec_tell_frac(&enc);
243     for(j=0;j<sz;j++){
244       data[j]=rand()/((RAND_MAX>>1)+1);
245       logp1[j]=(rand()%15)+1;
246       enc_method[j]=rand()/((RAND_MAX>>2)+1);
247       switch(enc_method[j]){
248         case 0:{
249           ec_encode(&enc,data[j]?(1<<logp1[j])-1:0,
250            (1<<logp1[j])-(data[j]?0:1),1<<logp1[j]);
251         }break;
252         case 1:{
253           ec_encode_bin(&enc,data[j]?(1<<logp1[j])-1:0,
254            (1<<logp1[j])-(data[j]?0:1),logp1[j]);
255         }break;
256         case 2:{
257           ec_enc_bit_logp(&enc,data[j],logp1[j]);
258         }break;
259         case 3:{
260           unsigned char icdf[2];
261           icdf[0]=1;
262           icdf[1]=0;
263           ec_enc_icdf(&enc,data[j],icdf,logp1[j]);
264         }break;
265       }
266       tell[j+1]=ec_tell_frac(&enc);
267     }
268     ec_enc_done(&enc);
269     if((ec_tell(&enc)+7U)/8U<ec_range_bytes(&enc)){
270       fprintf(stderr,"tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
271        ec_range_bytes(&enc),(ec_tell(&enc)+7)/8,seed);
272       ret=-1;
273     }
274     ec_dec_init(&dec,ptr,DATA_SIZE2);
275     if(ec_tell_frac(&dec)!=tell[0]){
276       fprintf(stderr,
277        "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
278        0,ec_tell_frac(&dec),tell[0],seed);
279     }
280     for(j=0;j<sz;j++){
281       int fs;
282       int dec_method;
283       dec_method=rand()/((RAND_MAX>>2)+1);
284       switch(dec_method){
285         case 0:{
286           fs=ec_decode(&dec,1<<logp1[j]);
287           sym=fs>=(1<<logp1[j])-1;
288           ec_dec_update(&dec,sym?(1<<logp1[j])-1:0,
289            (1<<logp1[j])-(sym?0:1),1<<logp1[j]);
290         }break;
291         case 1:{
292           fs=ec_decode_bin(&dec,logp1[j]);
293           sym=fs>=(1<<logp1[j])-1;
294           ec_dec_update(&dec,sym?(1<<logp1[j])-1:0,
295            (1<<logp1[j])-(sym?0:1),1<<logp1[j]);
296         }break;
297         case 2:{
298           sym=ec_dec_bit_logp(&dec,logp1[j]);
299         }break;
300         case 3:{
301           unsigned char icdf[2];
302           icdf[0]=1;
303           icdf[1]=0;
304           sym=ec_dec_icdf(&dec,icdf,logp1[j]);
305         }break;
306       }
307       if(sym!=data[j]){
308         fprintf(stderr,
309          "Decoded %i instead of %i with logp1 of %i at position %i of %i (Random seed: %u).\n",
310          sym,data[j],logp1[j],j,sz,seed);
311         fprintf(stderr,"Encoding method: %i, decoding method: %i\n",
312          enc_method[j],dec_method);
313         ret=-1;
314       }
315       if(ec_tell_frac(&dec)!=tell[j+1]){
316         fprintf(stderr,
317          "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
318          j+1,ec_tell_frac(&dec),tell[j+1],seed);
319       }
320     }
321     free(enc_method);
322     free(tell);
323     free(data);
324     free(logp1);
325   }
326   ec_enc_init(&enc,ptr,DATA_SIZE2);
327   ec_enc_bit_logp(&enc,0,1);
328   ec_enc_bit_logp(&enc,0,1);
329   ec_enc_bit_logp(&enc,0,1);
330   ec_enc_bit_logp(&enc,0,1);
331   ec_enc_bit_logp(&enc,0,2);
332   ec_enc_patch_initial_bits(&enc,3,2);
333   if(enc.error){
334     fprintf(stderr,"patch_initial_bits failed");
335     ret=-1;
336   }
337   ec_enc_patch_initial_bits(&enc,0,5);
338   if(!enc.error){
339     fprintf(stderr,"patch_initial_bits didn't fail when it should have");
340     ret=-1;
341   }
342   ec_enc_done(&enc);
343   if(ec_range_bytes(&enc)!=1||ptr[0]!=192){
344     fprintf(stderr,"Got %d when expecting 192 for patch_initial_bits",ptr[0]);
345     ret=-1;
346   }
347   ec_enc_init(&enc,ptr,DATA_SIZE2);
348   ec_enc_bit_logp(&enc,0,1);
349   ec_enc_bit_logp(&enc,0,1);
350   ec_enc_bit_logp(&enc,1,6);
351   ec_enc_bit_logp(&enc,0,2);
352   ec_enc_patch_initial_bits(&enc,0,2);
353   if(enc.error){
354     fprintf(stderr,"patch_initial_bits failed");
355     ret=-1;
356   }
357   ec_enc_done(&enc);
358   if(ec_range_bytes(&enc)!=2||ptr[0]!=63){
359     fprintf(stderr,"Got %d when expecting 63 for patch_initial_bits",ptr[0]);
360     ret=-1;
361   }
362   ec_enc_init(&enc,ptr,2);
363   ec_enc_bit_logp(&enc,0,2);
364   for(i=0;i<48;i++){
365     ec_enc_bits(&enc,0,1);
366   }
367   ec_enc_done(&enc);
368   if(!enc.error){
369     fprintf(stderr,"Raw bits overfill didn't fail when it should have");
370     ret=-1;
371   }
372   ec_enc_init(&enc,ptr,2);
373   for(i=0;i<17;i++){
374     ec_enc_bits(&enc,0,1);
375   }
376   ec_enc_done(&enc);
377   if(!enc.error){
378     fprintf(stderr,"17 raw bits encoded in two bytes");
379     ret=-1;
380   }
381   free(ptr);
382   return ret;
383 }