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
main(int _argc,char ** _argv)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 }
383