| 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 |