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