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 } 384
