1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/random/internal/entropy_pool.h"
16
17 #include <bitset>
18 #include <cmath>
19 #include <cstddef>
20 #include <cstdint>
21 #include <thread> // NOLINT
22 #include <utility>
23 #include <vector>
24
25 #include "gtest/gtest.h"
26 #include "absl/container/flat_hash_set.h"
27 #include "absl/synchronization/mutex.h"
28
29 namespace {
30
31 using ::absl::random_internal::GetEntropyFromRandenPool;
32
TEST(EntropyPoolTest,DistinctSequencesPerThread)33 TEST(EntropyPoolTest, DistinctSequencesPerThread) {
34 using result_type = uint32_t;
35 constexpr int kNumThreads = 12;
36 constexpr size_t kValuesPerThread = 32;
37
38 // Acquire entropy from multiple threads.
39 std::vector<std::vector<result_type>> data;
40 {
41 absl::Mutex mu;
42 std::vector<std::thread> threads;
43 for (int i = 0; i < kNumThreads; i++) {
44 threads.emplace_back([&]() {
45 std::vector<result_type> v(kValuesPerThread);
46 GetEntropyFromRandenPool(v.data(), sizeof(result_type) * v.size());
47 absl::MutexLock l(&mu);
48 data.push_back(std::move(v));
49 });
50 }
51 for (auto& t : threads) t.join();
52 }
53
54 EXPECT_EQ(data.size(), kNumThreads);
55
56 // There should be essentially no duplicates in the sequences.
57 size_t expected_size = 0;
58 absl::flat_hash_set<result_type> seen;
59 for (const auto& v : data) {
60 expected_size += v.size();
61 for (result_type x : v) seen.insert(x);
62 }
63 EXPECT_GE(seen.size(), expected_size - 1);
64 }
65
66 // This validates that sequences are independent.
TEST(EntropyPoolTest,ValidateDistribution)67 TEST(EntropyPoolTest, ValidateDistribution) {
68 using result_type = uint32_t;
69 constexpr int kNumOutputs = 16;
70 std::vector<result_type> a(kNumOutputs);
71 std::vector<result_type> b(kNumOutputs);
72
73 GetEntropyFromRandenPool(a.data(), sizeof(a[0]) * a.size());
74 GetEntropyFromRandenPool(b.data(), sizeof(b[0]) * b.size());
75
76 // Compare the two sequences, counting the number of bits that are different,
77 // then verify using a normal-approximation of the binomial distribution.
78 size_t changed_bits = 0;
79 size_t total_set = 0;
80 size_t equal_count = 0;
81 size_t zero_count = 0;
82 for (size_t i = 0; i < a.size(); ++i) {
83 std::bitset<sizeof(result_type) * 8> changed_set(a[i] ^ b[i]);
84 changed_bits += changed_set.count();
85
86 std::bitset<sizeof(result_type) * 8> a_set(a[i]);
87 std::bitset<sizeof(result_type) * 8> b_set(b[i]);
88 total_set += a_set.count() + b_set.count();
89
90 equal_count += (a[i] == b[i]) ? 1 : 0;
91
92 zero_count += (a[i] == 0) ? 1 : 0;
93 zero_count += (b[i] == 0) ? 1 : 0;
94 }
95
96 constexpr size_t kNBits = kNumOutputs * sizeof(result_type) * 8;
97
98 // This should be a binomial distribution with:
99 // p = 0.5
100 // n = kNBits
101 // sigma =~ 11.3 (sqrt(n * 0.5 * 0.5))
102 // So we expect the number of changed bits to be within 5 standard deviations
103 // of the mean; this should fail less than one in 3 million times.
104 EXPECT_NEAR(changed_bits, kNBits * 0.5, 5 * std::sqrt(kNBits))
105 << "@" << changed_bits / static_cast<double>(kNBits);
106
107 // Verify that the number of set bits is also within the expected range;
108 // Note that this is summed over the two sequences, so the number of trials
109 // is twice the number of bits.
110 EXPECT_NEAR(total_set, kNBits, 5 * std::sqrt(2 * kNBits))
111 << "@" << total_set / static_cast<double>(2 * kNBits);
112
113 // A[i] == B[i] with probability ~= 16 * 1/2^32; certainly less than 1.
114 EXPECT_LE(equal_count, 1);
115
116 // Zeros values must be rare; 32 / 2^32 is certainly less than 1.
117 EXPECT_LE(zero_count, 1);
118 }
119 } // namespace
120