1// { dg-options "-std=gnu++11" } 2// { dg-options "-DNTESTS=1 -DNSTRINGS=100 -DSTRSIZE=21 -std=gnu++11" { target simulator } } 3 4// Copyright (C) 2010-2015 Free Software Foundation, Inc. 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 28using namespace std; 29 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 40const unsigned int num_quality_tests = NTESTS; 41const unsigned int num_strings_for_quality_tests = NSTRINGS; 42const unsigned int string_size = STRSIZE; 43 44vector<string> 45random_strings(unsigned int n, unsigned int len) 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 59double 60score_from_varying_position(string s, unsigned int index) 61{ 62 bool test __attribute__((unused)) = true; 63 unsigned int bits_in_hash_code = sizeof(size_t) * 8; 64 65 // We'll iterate through all 256 vals for s[index], leaving the rest 66 // of s fixed. Then, for example, out of the 128 times that 67 // s[index] has its 3rd bit equal to 0 we would like roughly half 1s 68 // and half 0s in bit 9 of the hash codes. 69 // 70 // Bookkeeping: Conceptually we want a 3D array of ints. We want to 71 // count the number of times each output position (of which there are 72 // bits_in_hash_code) is 1 for each bit position within s[index] (of 73 // which there are 8) and value of that bit (of which there are 2). 74 const unsigned int jj = 2; 75 const unsigned int kk = jj * bits_in_hash_code; 76 const unsigned int array_size = 8 * kk; 77 vector<int> ones(array_size, 0); 78 79 for (int i = 0; i < 256; i++) 80 { 81 s[index] = i; 82 size_t h = hash<string>()(s); 83 for (int j = 0; h != 0; j++, h >>= 1) 84 { 85 if (h & 1) 86 { 87 for (int k = 0; k < 8; k++) 88 ++ones[k * kk + j * jj + ((i >> k) & 1)]; 89 } 90 } 91 } 92 93 // At most, the innermost statement in the above loop nest can 94 // execute 256 * bits_in_hash_code * 8 times. If the hash is good, 95 // it'll execute about half that many times, with a pretty even 96 // spread across the elements of ones[]. 97 VERIFY( 256 * bits_in_hash_code * 8 / array_size == 128 ); 98 int max_ones_possible = 128; 99 int good = 0, bad = 0; 100 for (int bit = 0; bit <= 1; bit++) 101 { 102 for (unsigned int j = 0; j < bits_in_hash_code; j++) 103 { 104 for (int bitpos = 0; bitpos < 8; bitpos++) 105 { 106 int z = ones[bitpos * kk + j * jj + bit]; 107 if (z <= max_ones_possible / 6 108 || z >= max_ones_possible * 5 / 6) 109 { 110 // The hash function screwed up, or was just unlucky, 111 // as 128 flips of a perfect coin occasionally yield 112 // far from 64 heads. 113 bad++; 114 } 115 else 116 good++; 117 } 118 } 119 } 120 return good / (double)(good + bad); 121} 122 123double 124score_from_varying_position(const vector<string>& v, unsigned int index) 125{ 126 double score = 0; 127 for (unsigned int i = 0; i < v.size(); i++) 128 score += score_from_varying_position(v[i], index); 129 return score / v.size(); 130} 131 132double 133quality_test(unsigned int num_strings, unsigned int string_size) 134{ 135 // Construct random strings. 136 vector<string> v = random_strings(num_strings, string_size); 137 double sum_of_scores = 0; 138 for (unsigned int i = 0; i < string_size; i++) 139 sum_of_scores += score_from_varying_position(v, i); 140 141 // A good hash function should have a score very close to 1, and a bad 142 // hash function will have a score close to 0. 143 return sum_of_scores / string_size; 144} 145 146void 147quality_test() 148{ 149 bool test __attribute__((unused)) = true; 150 srand(137); 151 double sum_of_scores = 0; 152 for (unsigned int i = 0; i < num_quality_tests; i++) 153 { 154 double score = quality_test(num_strings_for_quality_tests, 155 string_size); 156 sum_of_scores += score; 157 VERIFY( score > 0.99 ); 158 } 159 160 if (num_quality_tests > 1) 161 { 162 double mean_quality = sum_of_scores / num_quality_tests; 163 VERIFY( mean_quality > 0.9999 ); 164 } 165} 166 167int 168main() 169{ 170 quality_test(); 171 return 0; 172} 173