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