stat.c

srtp 1.0.1 比较适用于头一次看。其他版本的有需要也可以传上来。

/*
 * stats.c
 *
 * statistical tests for randomness (FIPS 140-2, Section 4.9)
 * 
 * David A. McGrew
 * Cisco Systems, Inc.
 */

#include "datatypes.h"
#include "err.h"


#define PRINT_DEBUG 0

#if PRINT_DEBUG
#include <stdio.h>
#endif

/*
 * each test assumes that 20,000 bits (2500 octets) of data is
 * provided as input
 */

#define STAT_TEST_DATA_LEN 2500

err_status_t
stat_test_monobit(octet_t *data) {
  octet_t *data_end = data + STAT_TEST_DATA_LEN;
  uint16_t ones_count;

  ones_count = 0;
  while (data < data_end) {
    ones_count += octet_get_weight(*data);
    data++;
  }

#if PRINT_DEBUG
  printf("bit count: %d out of %d\n", ones_count, STAT_TEST_DATA_LEN*8);
#endif
  
  if ((ones_count < 9725) || (ones_count > 10275))
    return err_status_algo_fail;

  return err_status_ok;
}

err_status_t
stat_test_poker(octet_t *data) {
  int i;
  octet_t *data_end = data + STAT_TEST_DATA_LEN;
  double poker;
  uint16_t f[16] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0
  };
  
  while (data < data_end) {
    f[*data & 0x0f]++;    /* increment freq. count for low nibble  */
    f[(*data) >> 4]++;    /* increment freq. count for high nibble */
    data++;
  }

  poker = 0.0;
  for (i=0; i < 16; i++) 
    poker += (double) f[i] * f[i];

  poker *= (16.0 / 5000.0);
  poker -= 5000.0;

#if PRINT_DEBUG
    printf("poker test: %f\n", poker);
#endif
    
  if ((poker < 2.16) || (poker > 46.17))
    return err_status_algo_fail;
  
  return err_status_ok;
}


/*
 * runs[i] holds the number of runs of size (i-1)
 */

err_status_t
stat_test_runs(octet_t *data) {
  octet_t *data_end = data + STAT_TEST_DATA_LEN;
  uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 
  uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
  uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
  uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
  int16_t  state = 0;
  uint16_t mask;
  int i;
  
  /*
   * the state variable holds the number of bits in the
   * current run (or gap, if negative)
   */
  
  while (data < data_end) {

    /* loop over the bits of this byte */
    for (mask = 1; mask < 256; mask <<= 1) {
      if (*data & mask) {

 	/* next bit is a one  */
	if (state > 0) {

	  /* prefix is a run, so increment the run-count  */
	  state++;                          

	  /* check for long runs */ 
	  if (state > 25)
	    return err_status_algo_fail;

	} else if (state < 0) {

	  /* prefix is a gap  */
	  if (state < -25) {
	    return err_status_algo_fail;    /* long-runs test failed   */
	  }
	  if (state < -6) {
	    state = -6;                     /* group together gaps > 5 */
	  }
	  gaps[-1-state]++;                 /* increment gap count      */
          state = 1;                        /* set state at one set bit */
	} else {

	  /* state is zero; this happens only at initialization        */
	  state = 1;            
	}
      } else {

	/* next bit is a zero  */
	if (state > 0) {

	  /* prefix is a run */
	  if (state > 25) {
	    return err_status_algo_fail;    /* long-runs test failed   */
	  }
	  if (state > 6) {
	    state = 6;                      /* group together runs > 5 */
	  }
	  runs[state-1]++;                  /* increment run count       */
          state = -1;                       /* set state at one zero bit */
	} else if (state < 0) {

	  /* prefix is a gap, so increment gap-count (decrement state) */
	  state--;

	  /* check for long gaps */ 
	  if (state < -25)
	    return err_status_algo_fail;

	} else {

	  /* state is zero; this happens only at initialization        */
	  state = -1;
	}
      }
    }

    /* move along to next octet */
    data++;
  }

#if PRINT_DEBUG
    printf("runs test\n");
    for (i=0; i < 6; i++)
      printf("\truns[%d]: %d\tgaps[%d]: %d\n",
	     i, runs[i], i, gaps[i]);
#endif
    
  /* check run and gap counts against the fixed limits */
  for (i=0; i < 6; i++) 
    if (   (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
	|| (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i]))
      return err_status_algo_fail;

  
  return err_status_ok;
}



/*
 * the loop-over-bits can be unrolled with a slight bit of work by
 * considering one nibble (four-bit) value at a time
 *
 * state < 0          
 * ------------------------------------------------------------------- 
 * 0000                                         state -= 4;
 * 0001  gaps[3-state]++;                       state =  1;
 * 0010  gaps[2-state]++; runs[0]++;            state = -1;
 * 0011  gaps[1-state]++;                       state =  2; 
 * 0100  gaps[1-state]++; runs[0]++;            state = -2;
 * 0101  gaps[1-state]++; gaps[0]++; runs[0]++; state =  1;
 * 0110  gaps[1-state]++; runs[1]++; 
 * 0111  
 * 1000
 * 1000 
 * 1001
 * 1010
 * 1011
 * 1100
 * 1101
 * 1110
 * 1111 gaps[-state]++; state = 4;
 *
 */