kerneltest/e32utils/nistsecurerng/src/linearComplexity.cpp
changeset 152 657f875b013e
equal deleted inserted replaced
139:95f71bcdcdb7 152:657f875b013e
       
     1 /*
       
     2 * Portions Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).
       
     3 * All rights reserved.
       
     4 * This component and the accompanying materials are made available
       
     5 * under the terms of "Eclipse Public License v1.0"
       
     6 * which accompanies this distribution, and is available
       
     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".
       
     8 *
       
     9 * Initial Contributors:
       
    10 * Nokia Corporation - initial contribution.
       
    11 *
       
    12 * Contributors:
       
    13 *
       
    14 * Description: 
       
    15 * The original NIST Statistical Test Suite code is placed in public domain.
       
    16 * (http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html) 
       
    17 * 
       
    18 * This software was developed at the National Institute of Standards and Technology by 
       
    19 * employees of the Federal Government in the course of their official duties. Pursuant
       
    20 * to title 17 Section 105 of the United States Code this software is not subject to 
       
    21 * copyright protection and is in the public domain. The NIST Statistical Test Suite is
       
    22 * an experimental system. NIST assumes no responsibility whatsoever for its use by other 
       
    23 * parties, and makes no guarantees, expressed or implied, about its quality, reliability, 
       
    24 * or any other characteristic. We would appreciate acknowledgment if the software is used.
       
    25 */
       
    26 
       
    27 #include "openc.h"
       
    28 #include "../include/externs.h"
       
    29 #include "../include/cephes.h"  
       
    30 
       
    31 void
       
    32 LinearComplexity(int M, int n)
       
    33 {
       
    34 	int       i, ii, j, d, N, L, m, N_, sign, K = 6;
       
    35 	double    p_value, T_, mean, nu[7], chi2;
       
    36 	double    pi[7] = { 0.01047, 0.03125, 0.12500, 0.50000, 0.25000, 0.06250, 0.020833 };
       
    37 	BitSequence*   T = NULL;
       
    38 	BitSequence*   P = NULL;
       
    39 	BitSequence*   B_ = NULL;
       
    40 	BitSequence*   C = NULL;
       
    41 	
       
    42 	N = (int)floor(n/M);
       
    43 	if ( ((B_ = (BitSequence *) calloc(M, sizeof(BitSequence))) == NULL) ||
       
    44 		 ((C  = (BitSequence *) calloc(M, sizeof(BitSequence))) == NULL) ||
       
    45 		 ((P  = (BitSequence *) calloc(M, sizeof(BitSequence))) == NULL) ||
       
    46 		 ((T  = (BitSequence *) calloc(M, sizeof(BitSequence))) == NULL) ) {
       
    47 		printf("Insufficient Memory for Work Space:: Linear Complexity Test\n");
       
    48 		if ( B_!= NULL )
       
    49 			free(B_);
       
    50 		if ( C != NULL )
       
    51 			free(C);
       
    52 		if ( P != NULL )
       
    53 			free(P);
       
    54 		if ( T != NULL )
       
    55 			free(T);
       
    56 		return;
       
    57 	}
       
    58 
       
    59 
       
    60 	fprintf(stats[TEST_LINEARCOMPLEXITY], "-----------------------------------------------------\n");
       
    61 	fprintf(stats[TEST_LINEARCOMPLEXITY], "\tL I N E A R  C O M P L E X I T Y\n");
       
    62 	fprintf(stats[TEST_LINEARCOMPLEXITY], "-----------------------------------------------------\n");
       
    63 	fprintf(stats[TEST_LINEARCOMPLEXITY], "\tM (substring length)     = %d\n", M);
       
    64 	fprintf(stats[TEST_LINEARCOMPLEXITY], "\tN (number of substrings) = %d\n", N);
       
    65 	fprintf(stats[TEST_LINEARCOMPLEXITY], "-----------------------------------------------------\n");
       
    66 	fprintf(stats[TEST_LINEARCOMPLEXITY], "        F R E Q U E N C Y                            \n");
       
    67 	fprintf(stats[TEST_LINEARCOMPLEXITY], "-----------------------------------------------------\n");
       
    68 	fprintf(stats[TEST_LINEARCOMPLEXITY], "  C0   C1   C2   C3   C4   C5   C6    CHI2    P-value\n");
       
    69 	fprintf(stats[TEST_LINEARCOMPLEXITY], "-----------------------------------------------------\n");
       
    70 	fprintf(stats[TEST_LINEARCOMPLEXITY], "\tNote: %d bits were discarded!\n", n%M);
       
    71 
       
    72 	for ( i=0; i<K+1; i++ )
       
    73 		nu[i] = 0.00;
       
    74 	for ( ii=0; ii<N; ii++ ) {
       
    75 		for ( i=0; i<M; i++ ) {
       
    76 			B_[i] = 0;
       
    77 			C[i] = 0;
       
    78 			T[i] = 0;
       
    79 			P[i] = 0;
       
    80 		}
       
    81 		L = 0;
       
    82 		m = -1;
       
    83 		d = 0;
       
    84 		C[0] = 1;
       
    85 		B_[0] = 1;
       
    86 		
       
    87 		/* DETERMINE LINEAR COMPLEXITY */
       
    88 		N_ = 0;
       
    89 		while ( N_ < M ) {
       
    90 			d = (int)epsilon[ii*M+N_];
       
    91 			for ( i=1; i<=L; i++ )
       
    92 				d += C[i] * epsilon[ii*M+N_-i];
       
    93 			d = d%2;
       
    94 			if ( d == 1 ) {
       
    95 				for ( i=0; i<M; i++ ) {
       
    96 					T[i] = C[i];
       
    97 					P[i] = 0;
       
    98 				}
       
    99 				for ( j=0; j<M; j++ )
       
   100 					if ( B_[j] == 1 )
       
   101 						P[j+N_-m] = 1;
       
   102 				for ( i=0; i<M; i++ )
       
   103 					C[i] = (BitSequence)((C[i] + P[i])%2);
       
   104 				if ( L <= N_/2 ) {
       
   105 					L = N_ + 1 - L;
       
   106 					m = N_;
       
   107 					for ( i=0; i<M; i++ )
       
   108 						B_[i] = T[i];
       
   109 				}
       
   110 			}
       
   111 			N_++;
       
   112 		}
       
   113 		if (((M+1)%2) == 0 ) 
       
   114 			sign = -1;
       
   115 		else 
       
   116 			sign = 1;
       
   117 		mean = M/2.0 + (9.0+sign)/36.0 - 1.0/pow(2, M) * (M/3.0 + 2.0/9.0);
       
   118 		if ( (M%2) == 0 )
       
   119 			sign = 1;
       
   120 		else 
       
   121 			sign = -1;
       
   122 		T_ = sign * (L - mean) + 2.0/9.0;
       
   123 		
       
   124 		if ( T_ <= -2.5 )
       
   125 			nu[0]++;
       
   126 		else if ( T_ > -2.5 && T_ <= -1.5 )
       
   127 			nu[1]++;
       
   128 		else if ( T_ > -1.5 && T_ <= -0.5 )
       
   129 			nu[2]++;
       
   130 		else if ( T_ > -0.5 && T_ <= 0.5 )
       
   131 			nu[3]++;
       
   132 		else if ( T_ > 0.5 && T_ <= 1.5 )
       
   133 			nu[4]++;
       
   134 		else if ( T_ > 1.5 && T_ <= 2.5 )
       
   135 			nu[5]++;
       
   136 		else
       
   137 			nu[6]++;
       
   138 	}
       
   139 	chi2 = 0.00;
       
   140 	for ( i=0; i<K+1; i++ ) 
       
   141 		fprintf(stats[TEST_LINEARCOMPLEXITY], "%4d ", (int)nu[i]);
       
   142 	for ( i=0; i<K+1; i++ )
       
   143 		chi2 += pow(nu[i]-N*pi[i], 2) / (N*pi[i]);
       
   144 	p_value = cephes_igamc(K/2.0, chi2/2.0);
       
   145 
       
   146 	fprintf(stats[TEST_LINEARCOMPLEXITY], "%9.6f%9.6f\n", chi2, p_value);
       
   147 	fprintf(results[TEST_LINEARCOMPLEXITY], "%f\n", p_value);
       
   148 
       
   149 	free(B_);
       
   150 	free(P);
       
   151 	free(C);
       
   152 	free(T);
       
   153 }