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