OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "components/variations/entropy_provider.h" | 5 #include "components/variations/entropy_provider.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <limits> | 8 #include <limits> |
9 #include <vector> | 9 #include <vector> |
10 | 10 |
11 #include "base/logging.h" | 11 #include "base/logging.h" |
12 #include "base/rand_util.h" | 12 #include "base/rand_util.h" |
13 #include "base/sha1.h" | 13 #include "base/sha1.h" |
14 #include "base/sys_byteorder.h" | 14 #include "base/sys_byteorder.h" |
15 #include "components/variations/metrics_util.h" | 15 #include "components/variations/metrics_util.h" |
16 | 16 |
17 namespace metrics { | 17 namespace metrics { |
18 | 18 |
19 namespace internal { | 19 namespace internal { |
20 | 20 |
21 SeededRandGenerator::SeededRandGenerator(uint32 seed) { | 21 SeededRandGenerator::SeededRandGenerator(uint32_t seed) { |
22 mersenne_twister_.init_genrand(seed); | 22 mersenne_twister_.init_genrand(seed); |
23 } | 23 } |
24 | 24 |
25 SeededRandGenerator::~SeededRandGenerator() { | 25 SeededRandGenerator::~SeededRandGenerator() { |
26 } | 26 } |
27 | 27 |
28 uint32 SeededRandGenerator::operator()(uint32 range) { | 28 uint32_t SeededRandGenerator::operator()(uint32_t range) { |
29 // Based on base::RandGenerator(). | 29 // Based on base::RandGenerator(). |
30 DCHECK_GT(range, 0u); | 30 DCHECK_GT(range, 0u); |
31 | 31 |
32 // We must discard random results above this number, as they would | 32 // We must discard random results above this number, as they would |
33 // make the random generator non-uniform (consider e.g. if | 33 // make the random generator non-uniform (consider e.g. if |
34 // MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice | 34 // MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice |
35 // as likely as a result of 3 or 4). | 35 // as likely as a result of 3 or 4). |
36 uint32 max_acceptable_value = | 36 uint32_t max_acceptable_value = |
37 (std::numeric_limits<uint32>::max() / range) * range - 1; | 37 (std::numeric_limits<uint32_t>::max() / range) * range - 1; |
38 | 38 |
39 uint32 value; | 39 uint32_t value; |
40 do { | 40 do { |
41 value = mersenne_twister_.genrand_int32(); | 41 value = mersenne_twister_.genrand_int32(); |
42 } while (value > max_acceptable_value); | 42 } while (value > max_acceptable_value); |
43 | 43 |
44 return value % range; | 44 return value % range; |
45 } | 45 } |
46 | 46 |
47 void PermuteMappingUsingRandomizationSeed(uint32 randomization_seed, | 47 void PermuteMappingUsingRandomizationSeed(uint32_t randomization_seed, |
48 std::vector<uint16>* mapping) { | 48 std::vector<uint16_t>* mapping) { |
49 for (size_t i = 0; i < mapping->size(); ++i) | 49 for (size_t i = 0; i < mapping->size(); ++i) |
50 (*mapping)[i] = static_cast<uint16>(i); | 50 (*mapping)[i] = static_cast<uint16_t>(i); |
51 | 51 |
52 SeededRandGenerator generator(randomization_seed); | 52 SeededRandGenerator generator(randomization_seed); |
53 | 53 |
54 // Do a deterministic random shuffle of the mapping using |generator|. | 54 // Do a deterministic random shuffle of the mapping using |generator|. |
55 // | 55 // |
56 // Note: This logic is identical to the following call with libstdc++ and VS: | 56 // Note: This logic is identical to the following call with libstdc++ and VS: |
57 // | 57 // |
58 // std::random_shuffle(mapping->begin(), mapping->end(), generator); | 58 // std::random_shuffle(mapping->begin(), mapping->end(), generator); |
59 // | 59 // |
60 // However, this is not guaranteed by the spec and some implementations (e.g. | 60 // However, this is not guaranteed by the spec and some implementations (e.g. |
(...skipping 10 matching lines...) Expand all Loading... |
71 | 71 |
72 SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source) | 72 SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source) |
73 : entropy_source_(entropy_source) { | 73 : entropy_source_(entropy_source) { |
74 } | 74 } |
75 | 75 |
76 SHA1EntropyProvider::~SHA1EntropyProvider() { | 76 SHA1EntropyProvider::~SHA1EntropyProvider() { |
77 } | 77 } |
78 | 78 |
79 double SHA1EntropyProvider::GetEntropyForTrial( | 79 double SHA1EntropyProvider::GetEntropyForTrial( |
80 const std::string& trial_name, | 80 const std::string& trial_name, |
81 uint32 randomization_seed) const { | 81 uint32_t randomization_seed) const { |
82 // Given enough input entropy, SHA-1 will produce a uniformly random spread | 82 // Given enough input entropy, SHA-1 will produce a uniformly random spread |
83 // in its output space. In this case, the input entropy that is used is the | 83 // in its output space. In this case, the input entropy that is used is the |
84 // combination of the original |entropy_source_| and the |trial_name|. | 84 // combination of the original |entropy_source_| and the |trial_name|. |
85 // | 85 // |
86 // Note: If |entropy_source_| has very low entropy, such as 13 bits or less, | 86 // Note: If |entropy_source_| has very low entropy, such as 13 bits or less, |
87 // it has been observed that this method does not result in a uniform | 87 // it has been observed that this method does not result in a uniform |
88 // distribution given the same |trial_name|. When using such a low entropy | 88 // distribution given the same |trial_name|. When using such a low entropy |
89 // source, PermutedEntropyProvider should be used instead. | 89 // source, PermutedEntropyProvider should be used instead. |
90 std::string input(entropy_source_ + trial_name); | 90 std::string input(entropy_source_ + trial_name); |
91 unsigned char sha1_hash[base::kSHA1Length]; | 91 unsigned char sha1_hash[base::kSHA1Length]; |
92 base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()), | 92 base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()), |
93 input.size(), | 93 input.size(), |
94 sha1_hash); | 94 sha1_hash); |
95 | 95 |
96 uint64 bits; | 96 uint64_t bits; |
97 static_assert(sizeof(bits) < sizeof(sha1_hash), "more data required"); | 97 static_assert(sizeof(bits) < sizeof(sha1_hash), "more data required"); |
98 memcpy(&bits, sha1_hash, sizeof(bits)); | 98 memcpy(&bits, sha1_hash, sizeof(bits)); |
99 bits = base::ByteSwapToLE64(bits); | 99 bits = base::ByteSwapToLE64(bits); |
100 | 100 |
101 return base::BitsToOpenEndedUnitInterval(bits); | 101 return base::BitsToOpenEndedUnitInterval(bits); |
102 } | 102 } |
103 | 103 |
104 PermutedEntropyProvider::PermutedEntropyProvider( | 104 PermutedEntropyProvider::PermutedEntropyProvider(uint16_t low_entropy_source, |
105 uint16 low_entropy_source, | 105 size_t low_entropy_source_max) |
106 size_t low_entropy_source_max) | |
107 : low_entropy_source_(low_entropy_source), | 106 : low_entropy_source_(low_entropy_source), |
108 low_entropy_source_max_(low_entropy_source_max) { | 107 low_entropy_source_max_(low_entropy_source_max) { |
109 DCHECK_LT(low_entropy_source, low_entropy_source_max); | 108 DCHECK_LT(low_entropy_source, low_entropy_source_max); |
110 DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16>::max()); | 109 DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16_t>::max()); |
111 } | 110 } |
112 | 111 |
113 PermutedEntropyProvider::~PermutedEntropyProvider() { | 112 PermutedEntropyProvider::~PermutedEntropyProvider() { |
114 } | 113 } |
115 | 114 |
116 double PermutedEntropyProvider::GetEntropyForTrial( | 115 double PermutedEntropyProvider::GetEntropyForTrial( |
117 const std::string& trial_name, | 116 const std::string& trial_name, |
118 uint32 randomization_seed) const { | 117 uint32_t randomization_seed) const { |
119 if (randomization_seed == 0) | 118 if (randomization_seed == 0) |
120 randomization_seed = HashName(trial_name); | 119 randomization_seed = HashName(trial_name); |
121 | 120 |
122 return GetPermutedValue(randomization_seed) / | 121 return GetPermutedValue(randomization_seed) / |
123 static_cast<double>(low_entropy_source_max_); | 122 static_cast<double>(low_entropy_source_max_); |
124 } | 123 } |
125 | 124 |
126 uint16 PermutedEntropyProvider::GetPermutedValue( | 125 uint16_t PermutedEntropyProvider::GetPermutedValue( |
127 uint32 randomization_seed) const { | 126 uint32_t randomization_seed) const { |
128 std::vector<uint16> mapping(low_entropy_source_max_); | 127 std::vector<uint16_t> mapping(low_entropy_source_max_); |
129 internal::PermuteMappingUsingRandomizationSeed(randomization_seed, &mapping); | 128 internal::PermuteMappingUsingRandomizationSeed(randomization_seed, &mapping); |
130 return mapping[low_entropy_source_]; | 129 return mapping[low_entropy_source_]; |
131 } | 130 } |
132 | 131 |
133 } // namespace metrics | 132 } // namespace metrics |
OLD | NEW |