entropy_pool_test.cc (4017B)
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 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. 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