|
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/utilities.h" |
|
30 #include "../include/cephes.h" |
|
31 |
|
32 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * |
|
33 U N I V E R S A L T E S T |
|
34 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
|
35 |
|
36 void |
|
37 Universal(int n) |
|
38 { |
|
39 int i, j, p, L, Q, K; |
|
40 double arg, sqrt2, sigma, phi, sum, p_value, c; |
|
41 long *T, decRep; |
|
42 double expected_value[17] = { 0, 0, 0, 0, 0, 0, 5.2177052, 6.1962507, 7.1836656, |
|
43 8.1764248, 9.1723243, 10.170032, 11.168765, |
|
44 12.168070, 13.167693, 14.167488, 15.167379 }; |
|
45 double variance[17] = { 0, 0, 0, 0, 0, 0, 2.954, 3.125, 3.238, 3.311, 3.356, 3.384, |
|
46 3.401, 3.410, 3.416, 3.419, 3.421 }; |
|
47 |
|
48 /* * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * |
|
49 * THE FOLLOWING REDEFINES L, SHOULD THE CONDITION: n >= 1010*2^L*L * |
|
50 * NOT BE MET, FOR THE BLOCK LENGTH L. * |
|
51 * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
|
52 L = 5; |
|
53 if ( n >= 387840 ) L = 6; |
|
54 if ( n >= 904960 ) L = 7; |
|
55 if ( n >= 2068480 ) L = 8; |
|
56 if ( n >= 4654080 ) L = 9; |
|
57 if ( n >= 10342400 ) L = 10; |
|
58 if ( n >= 22753280 ) L = 11; |
|
59 if ( n >= 49643520 ) L = 12; |
|
60 if ( n >= 107560960 ) L = 13; |
|
61 if ( n >= 231669760 ) L = 14; |
|
62 if ( n >= 496435200 ) L = 15; |
|
63 if ( n >= 1059061760 ) L = 16; |
|
64 |
|
65 Q = 10*(int)pow(2, L); |
|
66 K = (int) (floor(n/L) - (double)Q); /* BLOCKS TO TEST */ |
|
67 |
|
68 p = (int)pow(2, L); |
|
69 if ( (L < 6) || (L > 16) || ((double)Q < 10*pow(2, L)) || |
|
70 ((T = (long *)calloc(p, sizeof(long))) == NULL) ) { |
|
71 fprintf(stats[TEST_UNIVERSAL], "\t\tUNIVERSAL STATISTICAL TEST\n"); |
|
72 fprintf(stats[TEST_UNIVERSAL], "\t\t---------------------------------------------\n"); |
|
73 fprintf(stats[TEST_UNIVERSAL], "\t\tERROR: L IS OUT OF RANGE.\n"); |
|
74 fprintf(stats[TEST_UNIVERSAL], "\t\t-OR- : Q IS LESS THAN %f.\n", 10*pow(2, L)); |
|
75 fprintf(stats[TEST_UNIVERSAL], "\t\t-OR- : Unable to allocate T.\n"); |
|
76 return; |
|
77 } |
|
78 |
|
79 /* COMPUTE THE EXPECTED: Formula 16, in Marsaglia's Paper */ |
|
80 c = 0.7 - 0.8/(double)L + (4 + 32/(double)L)*pow(K, -3/(double)L)/15; |
|
81 sigma = c * sqrt(variance[L]/(double)K); |
|
82 sqrt2 = sqrt(2); |
|
83 sum = 0.0; |
|
84 for ( i=0; i<p; i++ ) |
|
85 T[i] = 0; |
|
86 for ( i=1; i<=Q; i++ ) { /* INITIALIZE TABLE */ |
|
87 decRep = 0; |
|
88 for ( j=0; j<L; j++ ) |
|
89 decRep += epsilon[(i-1)*L+j] * (long)pow(2, L-1-j); |
|
90 T[decRep] = i; |
|
91 } |
|
92 for ( i=Q+1; i<=Q+K; i++ ) { /* PROCESS BLOCKS */ |
|
93 decRep = 0; |
|
94 for ( j=0; j<L; j++ ) |
|
95 decRep += epsilon[(i-1)*L+j] * (long)pow(2, L-1-j); |
|
96 sum += log(i - T[decRep])/log(2); |
|
97 T[decRep] = i; |
|
98 } |
|
99 phi = (double)(sum/(double)K); |
|
100 |
|
101 fprintf(stats[TEST_UNIVERSAL], "\t\tUNIVERSAL STATISTICAL TEST\n"); |
|
102 fprintf(stats[TEST_UNIVERSAL], "\t\t--------------------------------------------\n"); |
|
103 fprintf(stats[TEST_UNIVERSAL], "\t\tCOMPUTATIONAL INFORMATION:\n"); |
|
104 fprintf(stats[TEST_UNIVERSAL], "\t\t--------------------------------------------\n"); |
|
105 fprintf(stats[TEST_UNIVERSAL], "\t\t(a) L = %d\n", L); |
|
106 fprintf(stats[TEST_UNIVERSAL], "\t\t(b) Q = %d\n", Q); |
|
107 fprintf(stats[TEST_UNIVERSAL], "\t\t(c) K = %d\n", K); |
|
108 fprintf(stats[TEST_UNIVERSAL], "\t\t(d) sum = %f\n", sum); |
|
109 fprintf(stats[TEST_UNIVERSAL], "\t\t(e) sigma = %f\n", sigma); |
|
110 fprintf(stats[TEST_UNIVERSAL], "\t\t(f) variance = %f\n", variance[L]); |
|
111 fprintf(stats[TEST_UNIVERSAL], "\t\t(g) exp_value = %f\n", expected_value[L]); |
|
112 fprintf(stats[TEST_UNIVERSAL], "\t\t(h) phi = %f\n", phi); |
|
113 fprintf(stats[TEST_UNIVERSAL], "\t\t(i) WARNING: %d bits were discarded.\n", n-(Q+K)*L); |
|
114 fprintf(stats[TEST_UNIVERSAL], "\t\t-----------------------------------------\n"); |
|
115 |
|
116 arg = fabs(phi-expected_value[L])/(sqrt2 * sigma); |
|
117 p_value = erfc(arg); |
|
118 if ( isNegative(p_value) || isGreaterThanOne(p_value) ) |
|
119 fprintf(stats[TEST_UNIVERSAL], "\t\tWARNING: P_VALUE IS OUT OF RANGE\n"); |
|
120 |
|
121 fprintf(stats[TEST_UNIVERSAL], "%s\t\tp_value = %f\n\n", p_value < ALPHA ? "FAILURE" : "SUCCESS", p_value); |
|
122 fprintf(results[TEST_UNIVERSAL], "%f\n", p_value); |
|
123 |
|
124 free(T); |
|
125 } |