1 /*
2 *=========================================================
3 * DAB Fill Tree Test
4 * This test fills small binary trees of fixed depth with
5 * words from the the RNG. When a word cannot be inserted
6 * into the tree, the current count of words in the tree is
7 * recorded, along with the position at which the word
8 * would have been inserted.
9 *
10 * The words from the RNG are rotated (in long cycles) to
11 * better detect RNGs that may bias only the high, middle,
12 * or low bytes.
13 *
14 * The test returns two p-values. The first is a Pearson
15 * chi-sq test against the expected values (which were
16 * estimated empirically). The second is a Pearson chi-sq
17 * test for a uniform distribution of the positions at
18 * which the insert failed.
19 *
20 * Because of the target data for the first p-value,
21 * ntuple must be kept at the default (32).
22 */
23 #include <dieharder/libdieharder.h>
24
25 #define RotL(x,N) (rmax_mask & (((x) << (N)) | ((x) >> (rmax_bits-(N)))))
26 #define CYCLES 4
27
28 static double targetData1[] __attribute__((unused)) = {
29 0,0,0,0,0.00000000,0.04446648,0.08890238,0.11821510,0.13166032,0.13135398,0.12074333,0.10339043,0.08300095,0.06272901,0.04470878,0.02987510,0.01872015,0.01095902,0.00597167,0.00298869,0.00138878,0.00059125,0.00022524,0.00007782,0.00002346,0.00000634,0.00000133,0.00000035,0.00000003,0.00000001,0.00000000,0.00000000
30 };
31 // n = 64, 0, 0.04446648, 0.08890238, ....
32
33 static double targetData[] = {
34 0.0, 0.0, 0.0, 0.0, 0.13333333, 0.20000000, 0.20634921, 0.17857143, 0.13007085, 0.08183633, 0.04338395, 0.01851828, 0.00617270, 0.00151193, 0.00023520, 0.00001680, 0.00000000, 0.00000000, 0.00000000, 0.00000000
35 };
36
37 inline int insert(double x, double *array, unsigned int startVal);
38
dab_filltree(Test ** test,int irun)39 int dab_filltree(Test **test,int irun) {
40 int size = (ntuple == 0) ? 32 : ntuple;
41 unsigned int target = sizeof(targetData)/sizeof(double);
42 int startVal = (size / 2) - 1;
43 double *array = (double *) malloc(sizeof(double) * size);
44 double *counts, *expected;
45 int i, j;
46 double x;
47 unsigned int start = 0;
48 unsigned int end = 0;
49 unsigned int rotAmount = 0;
50 double *positionCounts;
51
52 counts = (double *) malloc(sizeof(double) * target);
53 expected = (double *) malloc(sizeof(double) * target);
54 memset(counts, 0, sizeof(double) * target);
55
56 positionCounts = (double *) malloc(sizeof(double) * size/2);
57 memset(positionCounts, 0, sizeof(double) * size/2);
58
59 test[0]->ntuple = size;
60 test[1]->ntuple = size;
61
62 /* Calculate expected counts. */
63 for (i = 0; i < target; i++) {
64 expected[i] = targetData[i] * test[0]->tsamples;
65 if (expected[i] < 4) {
66 if (end == 0) start = i;
67 } else if (expected[i] > 4) end = i;
68 }
69 start++;
70
71
72 for (j = 0; j < test[0]->tsamples; j++) {
73 int ret;
74 memset(array, 0, sizeof(double) * size);
75 i = 0;
76 do {
77 unsigned int v = gsl_rng_get(rng);
78
79 x = ((double) RotL(v, rotAmount)) / rmax_mask;
80 i++;
81 if (i > size * 2) {
82 test[0]->pvalues[irun] = 0;
83 return(0);
84 }
85 ret = insert(x, array, startVal);
86 } while (ret == -1);
87 positionCounts[ret/2]++;
88
89 counts[i-1]++;
90 if (j % (test[0]->tsamples/CYCLES) == 0) rotAmount++;
91 }
92
93 test[0]->pvalues[irun] = chisq_pearson(counts + start, expected + start, end - start);
94
95 for (i = 0; i < size/2; i++) expected[i] = test[0]->tsamples/(size/2);
96 test[1]->pvalues[irun] = chisq_pearson(positionCounts, expected, size/2);
97
98
99 nullfree(positionCounts);
100 nullfree(expected);
101 nullfree(counts);
102 nullfree(array);
103
104 return(0);
105 }
106
107
insert(double x,double * array,unsigned int startVal)108 inline int insert(double x, double *array, unsigned int startVal) {
109 uint d = (startVal + 1) / 2;
110 uint i = startVal;
111 while (d > 0) {
112 if (array[i] == 0) {
113 array[i] = x;
114 return -1;
115 }
116 if (array[i] < x) {
117 i += d;
118 } else {
119 i -= d;
120 }
121 d /= 2;
122 }
123 return i;
124 }
125
126 #include<time.h>
127
main_filltree(int argc,char ** argv)128 int main_filltree(int argc, char **argv) {
129 int size = 64;
130 int startVal = (size / 2) - 1;
131 double *array = (double *) malloc(sizeof(double) * size);
132 int i, j;
133 double x;
134
135 i = time(NULL);
136 if (argc > 1) srand((i ^ (atoi(argv[1])<<7)) + (i<<4));
137 else srand(i);
138
139 for (j = 0; j < 10000000; j++) {
140 memset(array, 0, sizeof(double) * size);
141 i = 0;
142 do {
143 x = (double) rand() / RAND_MAX;
144 i++;
145 } while (insert(x, array, startVal) == 0);
146
147 printf("%d\n", i);
148 }
149
150 // for (i = 0; i < size; i++) printf("%f\n", array[i]);
151 nullfree(array);
152
153 return(0);
154 }
155
156