Alexandre Lision | 744f742 | 2013-09-25 11:39:37 -0400 | [diff] [blame] | 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 | } |