]>
Commit | Line | Data |
---|---|---|
18a20f3f JW |
1 | // { dg-options "-DNTESTS=1 -DNSTRINGS=100 -DSTRSIZE=21" { target simulator } } |
2 | // { dg-do run { target c++11 } } | |
2e9c3ef3 | 3 | |
a5544970 | 4 | // Copyright (C) 2010-2019 Free Software Foundation, Inc. |
2e9c3ef3 MA |
5 | // |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
9 | // Free Software Foundation; either version 3, or (at your option) | |
10 | // any later version. | |
11 | // | |
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | // | |
17 | // You should have received a copy of the GNU General Public License | |
18 | // along with this library; see the file COPYING3. If not see | |
19 | // <http://www.gnu.org/licenses/>. | |
20 | ||
21 | #include <cstdlib> | |
22 | #include <unordered_set> | |
23 | #include <string> | |
24 | #include <functional> | |
25 | #include <vector> | |
26 | #include <testsuite_hooks.h> | |
27 | ||
28 | using namespace std; | |
29 | ||
2e9c3ef3 MA |
30 | #ifndef NTESTS |
31 | #define NTESTS 5 | |
32 | #endif | |
33 | #ifndef NSTRINGS | |
34 | #define NSTRINGS 200 | |
35 | #endif | |
36 | #ifndef STRSIZE | |
37 | #define STRSIZE 42 | |
38 | #endif | |
39 | ||
19fd9833 PC |
40 | const unsigned int num_quality_tests = NTESTS; |
41 | const unsigned int num_strings_for_quality_tests = NSTRINGS; | |
42 | const unsigned int string_size = STRSIZE; | |
2e9c3ef3 MA |
43 | |
44 | vector<string> | |
19fd9833 | 45 | random_strings(unsigned int n, unsigned int len) |
2e9c3ef3 MA |
46 | { |
47 | string s(len, '\0'); | |
48 | unordered_set<string> result_set; | |
49 | while (result_set.size() < n) | |
50 | { | |
51 | result_set.insert(s); | |
52 | unsigned int tmp = rand(); | |
53 | tmp %= len * 256; | |
54 | s[tmp / 256] = tmp % 256; | |
55 | } | |
56 | return vector<string>(result_set.begin(), result_set.end()); | |
57 | } | |
58 | ||
59 | double | |
19fd9833 | 60 | score_from_varying_position(string s, unsigned int index) |
2e9c3ef3 | 61 | { |
19fd9833 | 62 | unsigned int bits_in_hash_code = sizeof(size_t) * 8; |
2e9c3ef3 MA |
63 | |
64 | // We'll iterate through all 256 vals for s[index], leaving the rest | |
65 | // of s fixed. Then, for example, out of the 128 times that | |
66 | // s[index] has its 3rd bit equal to 0 we would like roughly half 1s | |
67 | // and half 0s in bit 9 of the hash codes. | |
68 | // | |
69 | // Bookkeeping: Conceptually we want a 3D array of ints. We want to | |
70 | // count the number of times each output position (of which there are | |
71 | // bits_in_hash_code) is 1 for each bit position within s[index] (of | |
72 | // which there are 8) and value of that bit (of which there are 2). | |
19fd9833 PC |
73 | const unsigned int jj = 2; |
74 | const unsigned int kk = jj * bits_in_hash_code; | |
75 | const unsigned int array_size = 8 * kk; | |
2e9c3ef3 MA |
76 | vector<int> ones(array_size, 0); |
77 | ||
78 | for (int i = 0; i < 256; i++) | |
79 | { | |
80 | s[index] = i; | |
81 | size_t h = hash<string>()(s); | |
82 | for (int j = 0; h != 0; j++, h >>= 1) | |
83 | { | |
84 | if (h & 1) | |
85 | { | |
86 | for (int k = 0; k < 8; k++) | |
87 | ++ones[k * kk + j * jj + ((i >> k) & 1)]; | |
88 | } | |
89 | } | |
90 | } | |
91 | ||
92 | // At most, the innermost statement in the above loop nest can | |
93 | // execute 256 * bits_in_hash_code * 8 times. If the hash is good, | |
94 | // it'll execute about half that many times, with a pretty even | |
95 | // spread across the elements of ones[]. | |
96 | VERIFY( 256 * bits_in_hash_code * 8 / array_size == 128 ); | |
97 | int max_ones_possible = 128; | |
98 | int good = 0, bad = 0; | |
99 | for (int bit = 0; bit <= 1; bit++) | |
100 | { | |
19fd9833 | 101 | for (unsigned int j = 0; j < bits_in_hash_code; j++) |
2e9c3ef3 MA |
102 | { |
103 | for (int bitpos = 0; bitpos < 8; bitpos++) | |
104 | { | |
105 | int z = ones[bitpos * kk + j * jj + bit]; | |
106 | if (z <= max_ones_possible / 6 | |
107 | || z >= max_ones_possible * 5 / 6) | |
108 | { | |
109 | // The hash function screwed up, or was just unlucky, | |
110 | // as 128 flips of a perfect coin occasionally yield | |
111 | // far from 64 heads. | |
112 | bad++; | |
113 | } | |
114 | else | |
115 | good++; | |
116 | } | |
117 | } | |
118 | } | |
119 | return good / (double)(good + bad); | |
120 | } | |
121 | ||
122 | double | |
19fd9833 | 123 | score_from_varying_position(const vector<string>& v, unsigned int index) |
2e9c3ef3 MA |
124 | { |
125 | double score = 0; | |
19fd9833 | 126 | for (unsigned int i = 0; i < v.size(); i++) |
2e9c3ef3 MA |
127 | score += score_from_varying_position(v[i], index); |
128 | return score / v.size(); | |
129 | } | |
130 | ||
131 | double | |
19fd9833 | 132 | quality_test(unsigned int num_strings, unsigned int string_size) |
2e9c3ef3 MA |
133 | { |
134 | // Construct random strings. | |
135 | vector<string> v = random_strings(num_strings, string_size); | |
136 | double sum_of_scores = 0; | |
19fd9833 | 137 | for (unsigned int i = 0; i < string_size; i++) |
2e9c3ef3 MA |
138 | sum_of_scores += score_from_varying_position(v, i); |
139 | ||
140 | // A good hash function should have a score very close to 1, and a bad | |
141 | // hash function will have a score close to 0. | |
142 | return sum_of_scores / string_size; | |
143 | } | |
144 | ||
145 | void | |
146 | quality_test() | |
147 | { | |
2e9c3ef3 MA |
148 | srand(137); |
149 | double sum_of_scores = 0; | |
19fd9833 | 150 | for (unsigned int i = 0; i < num_quality_tests; i++) |
2e9c3ef3 MA |
151 | { |
152 | double score = quality_test(num_strings_for_quality_tests, | |
153 | string_size); | |
154 | sum_of_scores += score; | |
155 | VERIFY( score > 0.99 ); | |
156 | } | |
157 | ||
158 | if (num_quality_tests > 1) | |
159 | { | |
160 | double mean_quality = sum_of_scores / num_quality_tests; | |
161 | VERIFY( mean_quality > 0.9999 ); | |
162 | } | |
163 | } | |
164 | ||
165 | int | |
166 | main() | |
167 | { | |
168 | quality_test(); | |
169 | return 0; | |
170 | } |