cannam@154: /* Copyright (c) 2007-2011 Xiph.Org Foundation, Mozilla Corporation,
cannam@154:                            Gregory Maxwell
cannam@154:    Written by Jean-Marc Valin, Gregory Maxwell, and Timothy B. Terriberry */
cannam@154: /*
cannam@154:    Redistribution and use in source and binary forms, with or without
cannam@154:    modification, are permitted provided that the following conditions
cannam@154:    are met:
cannam@154: 
cannam@154:    - Redistributions of source code must retain the above copyright
cannam@154:    notice, this list of conditions and the following disclaimer.
cannam@154: 
cannam@154:    - Redistributions in binary form must reproduce the above copyright
cannam@154:    notice, this list of conditions and the following disclaimer in the
cannam@154:    documentation and/or other materials provided with the distribution.
cannam@154: 
cannam@154:    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
cannam@154:    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
cannam@154:    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
cannam@154:    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
cannam@154:    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
cannam@154:    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
cannam@154:    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
cannam@154:    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
cannam@154:    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
cannam@154:    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
cannam@154:    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
cannam@154: */
cannam@154: 
cannam@154: #ifdef HAVE_CONFIG_H
cannam@154: #include "config.h"
cannam@154: #endif
cannam@154: 
cannam@154: #include <stdlib.h>
cannam@154: #include <stdio.h>
cannam@154: #include <math.h>
cannam@154: #include <time.h>
cannam@154: #define CELT_C
cannam@154: #include "entcode.h"
cannam@154: #include "entenc.h"
cannam@154: #include "entdec.h"
cannam@154: #include <string.h>
cannam@154: 
cannam@154: #include "entenc.c"
cannam@154: #include "entdec.c"
cannam@154: #include "entcode.c"
cannam@154: 
cannam@154: #ifndef M_LOG2E
cannam@154: # define M_LOG2E    1.4426950408889634074
cannam@154: #endif
cannam@154: #define DATA_SIZE 10000000
cannam@154: #define DATA_SIZE2 10000
cannam@154: 
cannam@154: int main(int _argc,char **_argv){
cannam@154:   ec_enc         enc;
cannam@154:   ec_dec         dec;
cannam@154:   long           nbits;
cannam@154:   long           nbits2;
cannam@154:   double         entropy;
cannam@154:   int            ft;
cannam@154:   int            ftb;
cannam@154:   int            sz;
cannam@154:   int            i;
cannam@154:   int            ret;
cannam@154:   unsigned int   sym;
cannam@154:   unsigned int   seed;
cannam@154:   unsigned char *ptr;
cannam@154:   const char    *env_seed;
cannam@154:   ret=0;
cannam@154:   entropy=0;
cannam@154:   if (_argc > 2) {
cannam@154:     fprintf(stderr, "Usage: %s [<seed>]\n", _argv[0]);
cannam@154:     return 1;
cannam@154:   }
cannam@154:   env_seed = getenv("SEED");
cannam@154:   if (_argc > 1)
cannam@154:     seed = atoi(_argv[1]);
cannam@154:   else if (env_seed)
cannam@154:     seed = atoi(env_seed);
cannam@154:   else
cannam@154:     seed = time(NULL);
cannam@154:   /*Testing encoding of raw bit values.*/
cannam@154:   ptr = (unsigned char *)malloc(DATA_SIZE);
cannam@154:   ec_enc_init(&enc,ptr, DATA_SIZE);
cannam@154:   for(ft=2;ft<1024;ft++){
cannam@154:     for(i=0;i<ft;i++){
cannam@154:       entropy+=log(ft)*M_LOG2E;
cannam@154:       ec_enc_uint(&enc,i,ft);
cannam@154:     }
cannam@154:   }
cannam@154:   /*Testing encoding of raw bit values.*/
cannam@154:   for(ftb=1;ftb<16;ftb++){
cannam@154:     for(i=0;i<(1<<ftb);i++){
cannam@154:       entropy+=ftb;
cannam@154:       nbits=ec_tell(&enc);
cannam@154:       ec_enc_bits(&enc,i,ftb);
cannam@154:       nbits2=ec_tell(&enc);
cannam@154:       if(nbits2-nbits!=ftb){
cannam@154:         fprintf(stderr,"Used %li bits to encode %i bits directly.\n",
cannam@154:          nbits2-nbits,ftb);
cannam@154:         ret=-1;
cannam@154:       }
cannam@154:     }
cannam@154:   }
cannam@154:   nbits=ec_tell_frac(&enc);
cannam@154:   ec_enc_done(&enc);
cannam@154:   fprintf(stderr,
cannam@154:    "Encoded %0.2lf bits of entropy to %0.2lf bits (%0.3lf%% wasted).\n",
cannam@154:    entropy,ldexp(nbits,-3),100*(nbits-ldexp(entropy,3))/nbits);
cannam@154:   fprintf(stderr,"Packed to %li bytes.\n",(long)ec_range_bytes(&enc));
cannam@154:   ec_dec_init(&dec,ptr,DATA_SIZE);
cannam@154:   for(ft=2;ft<1024;ft++){
cannam@154:     for(i=0;i<ft;i++){
cannam@154:       sym=ec_dec_uint(&dec,ft);
cannam@154:       if(sym!=(unsigned)i){
cannam@154:         fprintf(stderr,"Decoded %i instead of %i with ft of %i.\n",sym,i,ft);
cannam@154:         ret=-1;
cannam@154:       }
cannam@154:     }
cannam@154:   }
cannam@154:   for(ftb=1;ftb<16;ftb++){
cannam@154:     for(i=0;i<(1<<ftb);i++){
cannam@154:       sym=ec_dec_bits(&dec,ftb);
cannam@154:       if(sym!=(unsigned)i){
cannam@154:         fprintf(stderr,"Decoded %i instead of %i with ftb of %i.\n",sym,i,ftb);
cannam@154:         ret=-1;
cannam@154:       }
cannam@154:     }
cannam@154:   }
cannam@154:   nbits2=ec_tell_frac(&dec);
cannam@154:   if(nbits!=nbits2){
cannam@154:     fprintf(stderr,
cannam@154:      "Reported number of bits used was %0.2lf, should be %0.2lf.\n",
cannam@154:      ldexp(nbits2,-3),ldexp(nbits,-3));
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   /*Testing an encoder bust prefers range coder data over raw bits.
cannam@154:     This isn't a general guarantee, will only work for data that is buffered in
cannam@154:      the encoder state and not yet stored in the user buffer, and should never
cannam@154:      get used in practice.
cannam@154:     It's mostly here for code coverage completeness.*/
cannam@154:   /*Start with a 16-bit buffer.*/
cannam@154:   ec_enc_init(&enc,ptr,2);
cannam@154:   /*Write 7 raw bits.*/
cannam@154:   ec_enc_bits(&enc,0x55,7);
cannam@154:   /*Write 12.3 bits of range coder data.*/
cannam@154:   ec_enc_uint(&enc,1,2);
cannam@154:   ec_enc_uint(&enc,1,3);
cannam@154:   ec_enc_uint(&enc,1,4);
cannam@154:   ec_enc_uint(&enc,1,5);
cannam@154:   ec_enc_uint(&enc,2,6);
cannam@154:   ec_enc_uint(&enc,6,7);
cannam@154:   ec_enc_done(&enc);
cannam@154:   ec_dec_init(&dec,ptr,2);
cannam@154:   if(!enc.error
cannam@154:    /*The raw bits should have been overwritten by the range coder data.*/
cannam@154:    ||ec_dec_bits(&dec,7)!=0x05
cannam@154:    /*And all the range coder data should have been encoded correctly.*/
cannam@154:    ||ec_dec_uint(&dec,2)!=1
cannam@154:    ||ec_dec_uint(&dec,3)!=1
cannam@154:    ||ec_dec_uint(&dec,4)!=1
cannam@154:    ||ec_dec_uint(&dec,5)!=1
cannam@154:    ||ec_dec_uint(&dec,6)!=2
cannam@154:    ||ec_dec_uint(&dec,7)!=6){
cannam@154:     fprintf(stderr,"Encoder bust overwrote range coder data with raw bits.\n");
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   srand(seed);
cannam@154:   fprintf(stderr,"Testing random streams... Random seed: %u (%.4X)\n", seed, rand() % 65536);
cannam@154:   for(i=0;i<409600;i++){
cannam@154:     unsigned *data;
cannam@154:     unsigned *tell;
cannam@154:     unsigned tell_bits;
cannam@154:     int       j;
cannam@154:     int zeros;
cannam@154:     ft=rand()/((RAND_MAX>>(rand()%11U))+1U)+10;
cannam@154:     sz=rand()/((RAND_MAX>>(rand()%9U))+1U);
cannam@154:     data=(unsigned *)malloc(sz*sizeof(*data));
cannam@154:     tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
cannam@154:     ec_enc_init(&enc,ptr,DATA_SIZE2);
cannam@154:     zeros = rand()%13==0;
cannam@154:     tell[0]=ec_tell_frac(&enc);
cannam@154:     for(j=0;j<sz;j++){
cannam@154:       if (zeros)
cannam@154:         data[j]=0;
cannam@154:       else
cannam@154:         data[j]=rand()%ft;
cannam@154:       ec_enc_uint(&enc,data[j],ft);
cannam@154:       tell[j+1]=ec_tell_frac(&enc);
cannam@154:     }
cannam@154:     if (rand()%2==0)
cannam@154:       while(ec_tell(&enc)%8 != 0)
cannam@154:         ec_enc_uint(&enc, rand()%2, 2);
cannam@154:     tell_bits = ec_tell(&enc);
cannam@154:     ec_enc_done(&enc);
cannam@154:     if(tell_bits!=(unsigned)ec_tell(&enc)){
cannam@154:       fprintf(stderr,"ec_tell() changed after ec_enc_done(): %i instead of %i (Random seed: %u)\n",
cannam@154:        ec_tell(&enc),tell_bits,seed);
cannam@154:       ret=-1;
cannam@154:     }
cannam@154:     if ((tell_bits+7)/8 < ec_range_bytes(&enc))
cannam@154:     {
cannam@154:       fprintf (stderr, "ec_tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
cannam@154:                ec_range_bytes(&enc), (tell_bits+7)/8,seed);
cannam@154:       ret=-1;
cannam@154:     }
cannam@154:     ec_dec_init(&dec,ptr,DATA_SIZE2);
cannam@154:     if(ec_tell_frac(&dec)!=tell[0]){
cannam@154:       fprintf(stderr,
cannam@154:        "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
cannam@154:        0,ec_tell_frac(&dec),tell[0],seed);
cannam@154:     }
cannam@154:     for(j=0;j<sz;j++){
cannam@154:       sym=ec_dec_uint(&dec,ft);
cannam@154:       if(sym!=data[j]){
cannam@154:         fprintf(stderr,
cannam@154:          "Decoded %i instead of %i with ft of %i at position %i of %i (Random seed: %u).\n",
cannam@154:          sym,data[j],ft,j,sz,seed);
cannam@154:         ret=-1;
cannam@154:       }
cannam@154:       if(ec_tell_frac(&dec)!=tell[j+1]){
cannam@154:         fprintf(stderr,
cannam@154:          "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
cannam@154:          j+1,ec_tell_frac(&dec),tell[j+1],seed);
cannam@154:       }
cannam@154:     }
cannam@154:     free(tell);
cannam@154:     free(data);
cannam@154:   }
cannam@154:   /*Test compatibility between multiple different encode/decode routines.*/
cannam@154:   for(i=0;i<409600;i++){
cannam@154:     unsigned *logp1;
cannam@154:     unsigned *data;
cannam@154:     unsigned *tell;
cannam@154:     unsigned *enc_method;
cannam@154:     int       j;
cannam@154:     sz=rand()/((RAND_MAX>>(rand()%9U))+1U);
cannam@154:     logp1=(unsigned *)malloc(sz*sizeof(*logp1));
cannam@154:     data=(unsigned *)malloc(sz*sizeof(*data));
cannam@154:     tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
cannam@154:     enc_method=(unsigned *)malloc(sz*sizeof(*enc_method));
cannam@154:     ec_enc_init(&enc,ptr,DATA_SIZE2);
cannam@154:     tell[0]=ec_tell_frac(&enc);
cannam@154:     for(j=0;j<sz;j++){
cannam@154:       data[j]=rand()/((RAND_MAX>>1)+1);
cannam@154:       logp1[j]=(rand()%15)+1;
cannam@154:       enc_method[j]=rand()/((RAND_MAX>>2)+1);
cannam@154:       switch(enc_method[j]){
cannam@154:         case 0:{
cannam@154:           ec_encode(&enc,data[j]?(1<<logp1[j])-1:0,
cannam@154:            (1<<logp1[j])-(data[j]?0:1),1<<logp1[j]);
cannam@154:         }break;
cannam@154:         case 1:{
cannam@154:           ec_encode_bin(&enc,data[j]?(1<<logp1[j])-1:0,
cannam@154:            (1<<logp1[j])-(data[j]?0:1),logp1[j]);
cannam@154:         }break;
cannam@154:         case 2:{
cannam@154:           ec_enc_bit_logp(&enc,data[j],logp1[j]);
cannam@154:         }break;
cannam@154:         case 3:{
cannam@154:           unsigned char icdf[2];
cannam@154:           icdf[0]=1;
cannam@154:           icdf[1]=0;
cannam@154:           ec_enc_icdf(&enc,data[j],icdf,logp1[j]);
cannam@154:         }break;
cannam@154:       }
cannam@154:       tell[j+1]=ec_tell_frac(&enc);
cannam@154:     }
cannam@154:     ec_enc_done(&enc);
cannam@154:     if((ec_tell(&enc)+7U)/8U<ec_range_bytes(&enc)){
cannam@154:       fprintf(stderr,"tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
cannam@154:        ec_range_bytes(&enc),(ec_tell(&enc)+7)/8,seed);
cannam@154:       ret=-1;
cannam@154:     }
cannam@154:     ec_dec_init(&dec,ptr,DATA_SIZE2);
cannam@154:     if(ec_tell_frac(&dec)!=tell[0]){
cannam@154:       fprintf(stderr,
cannam@154:        "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
cannam@154:        0,ec_tell_frac(&dec),tell[0],seed);
cannam@154:     }
cannam@154:     for(j=0;j<sz;j++){
cannam@154:       int fs;
cannam@154:       int dec_method;
cannam@154:       dec_method=rand()/((RAND_MAX>>2)+1);
cannam@154:       switch(dec_method){
cannam@154:         case 0:{
cannam@154:           fs=ec_decode(&dec,1<<logp1[j]);
cannam@154:           sym=fs>=(1<<logp1[j])-1;
cannam@154:           ec_dec_update(&dec,sym?(1<<logp1[j])-1:0,
cannam@154:            (1<<logp1[j])-(sym?0:1),1<<logp1[j]);
cannam@154:         }break;
cannam@154:         case 1:{
cannam@154:           fs=ec_decode_bin(&dec,logp1[j]);
cannam@154:           sym=fs>=(1<<logp1[j])-1;
cannam@154:           ec_dec_update(&dec,sym?(1<<logp1[j])-1:0,
cannam@154:            (1<<logp1[j])-(sym?0:1),1<<logp1[j]);
cannam@154:         }break;
cannam@154:         case 2:{
cannam@154:           sym=ec_dec_bit_logp(&dec,logp1[j]);
cannam@154:         }break;
cannam@154:         case 3:{
cannam@154:           unsigned char icdf[2];
cannam@154:           icdf[0]=1;
cannam@154:           icdf[1]=0;
cannam@154:           sym=ec_dec_icdf(&dec,icdf,logp1[j]);
cannam@154:         }break;
cannam@154:       }
cannam@154:       if(sym!=data[j]){
cannam@154:         fprintf(stderr,
cannam@154:          "Decoded %i instead of %i with logp1 of %i at position %i of %i (Random seed: %u).\n",
cannam@154:          sym,data[j],logp1[j],j,sz,seed);
cannam@154:         fprintf(stderr,"Encoding method: %i, decoding method: %i\n",
cannam@154:          enc_method[j],dec_method);
cannam@154:         ret=-1;
cannam@154:       }
cannam@154:       if(ec_tell_frac(&dec)!=tell[j+1]){
cannam@154:         fprintf(stderr,
cannam@154:          "Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
cannam@154:          j+1,ec_tell_frac(&dec),tell[j+1],seed);
cannam@154:       }
cannam@154:     }
cannam@154:     free(enc_method);
cannam@154:     free(tell);
cannam@154:     free(data);
cannam@154:     free(logp1);
cannam@154:   }
cannam@154:   ec_enc_init(&enc,ptr,DATA_SIZE2);
cannam@154:   ec_enc_bit_logp(&enc,0,1);
cannam@154:   ec_enc_bit_logp(&enc,0,1);
cannam@154:   ec_enc_bit_logp(&enc,0,1);
cannam@154:   ec_enc_bit_logp(&enc,0,1);
cannam@154:   ec_enc_bit_logp(&enc,0,2);
cannam@154:   ec_enc_patch_initial_bits(&enc,3,2);
cannam@154:   if(enc.error){
cannam@154:     fprintf(stderr,"patch_initial_bits failed");
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   ec_enc_patch_initial_bits(&enc,0,5);
cannam@154:   if(!enc.error){
cannam@154:     fprintf(stderr,"patch_initial_bits didn't fail when it should have");
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   ec_enc_done(&enc);
cannam@154:   if(ec_range_bytes(&enc)!=1||ptr[0]!=192){
cannam@154:     fprintf(stderr,"Got %d when expecting 192 for patch_initial_bits",ptr[0]);
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   ec_enc_init(&enc,ptr,DATA_SIZE2);
cannam@154:   ec_enc_bit_logp(&enc,0,1);
cannam@154:   ec_enc_bit_logp(&enc,0,1);
cannam@154:   ec_enc_bit_logp(&enc,1,6);
cannam@154:   ec_enc_bit_logp(&enc,0,2);
cannam@154:   ec_enc_patch_initial_bits(&enc,0,2);
cannam@154:   if(enc.error){
cannam@154:     fprintf(stderr,"patch_initial_bits failed");
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   ec_enc_done(&enc);
cannam@154:   if(ec_range_bytes(&enc)!=2||ptr[0]!=63){
cannam@154:     fprintf(stderr,"Got %d when expecting 63 for patch_initial_bits",ptr[0]);
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   ec_enc_init(&enc,ptr,2);
cannam@154:   ec_enc_bit_logp(&enc,0,2);
cannam@154:   for(i=0;i<48;i++){
cannam@154:     ec_enc_bits(&enc,0,1);
cannam@154:   }
cannam@154:   ec_enc_done(&enc);
cannam@154:   if(!enc.error){
cannam@154:     fprintf(stderr,"Raw bits overfill didn't fail when it should have");
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   ec_enc_init(&enc,ptr,2);
cannam@154:   for(i=0;i<17;i++){
cannam@154:     ec_enc_bits(&enc,0,1);
cannam@154:   }
cannam@154:   ec_enc_done(&enc);
cannam@154:   if(!enc.error){
cannam@154:     fprintf(stderr,"17 raw bits encoded in two bytes");
cannam@154:     ret=-1;
cannam@154:   }
cannam@154:   free(ptr);
cannam@154:   return ret;
cannam@154: }