OLD | NEW |
(Empty) | |
| 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 |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include "chrome/common/metrics/entropy_provider.h" |
| 6 |
| 7 #include <algorithm> |
| 8 #include <limits> |
| 9 #include <vector> |
| 10 |
| 11 #include "base/logging.h" |
| 12 #include "base/rand_util.h" |
| 13 #include "base/sha1.h" |
| 14 #include "base/sys_byteorder.h" |
| 15 |
| 16 namespace metrics { |
| 17 |
| 18 namespace internal { |
| 19 |
| 20 SeededRandGenerator::SeededRandGenerator(uint32 seed) { |
| 21 mersenne_twister_.init_genrand(seed); |
| 22 } |
| 23 |
| 24 SeededRandGenerator::~SeededRandGenerator() { |
| 25 } |
| 26 |
| 27 uint32 SeededRandGenerator::operator()(uint32 range) { |
| 28 // Based on base::RandGenerator(). |
| 29 DCHECK_GT(range, 0u); |
| 30 |
| 31 // We must discard random results above this number, as they would |
| 32 // make the random generator non-uniform (consider e.g. if |
| 33 // MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice |
| 34 // as likely as a result of 3 or 4). |
| 35 uint32 max_acceptable_value = |
| 36 (std::numeric_limits<uint32>::max() / range) * range - 1; |
| 37 |
| 38 uint32 value; |
| 39 do { |
| 40 value = mersenne_twister_.genrand_int32(); |
| 41 } while (value > max_acceptable_value); |
| 42 |
| 43 return value % range; |
| 44 } |
| 45 |
| 46 uint32 HashName(const std::string& name) { |
| 47 // SHA-1 is designed to produce a uniformly random spread in its output space, |
| 48 // even for nearly-identical inputs. |
| 49 unsigned char sha1_hash[base::kSHA1Length]; |
| 50 base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(name.c_str()), |
| 51 name.size(), |
| 52 sha1_hash); |
| 53 |
| 54 uint32 bits; |
| 55 COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data); |
| 56 memcpy(&bits, sha1_hash, sizeof(bits)); |
| 57 |
| 58 return base::ByteSwapToLE32(bits); |
| 59 } |
| 60 |
| 61 void PermuteMappingUsingTrialName(const std::string& trial_name, |
| 62 std::vector<uint16>* mapping) { |
| 63 for (size_t i = 0; i < mapping->size(); ++i) |
| 64 (*mapping)[i] = static_cast<uint16>(i); |
| 65 |
| 66 SeededRandGenerator generator(HashName(trial_name)); |
| 67 std::random_shuffle(mapping->begin(), mapping->end(), generator); |
| 68 } |
| 69 |
| 70 } // namespace internal |
| 71 |
| 72 SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source) |
| 73 : entropy_source_(entropy_source) { |
| 74 } |
| 75 |
| 76 SHA1EntropyProvider::~SHA1EntropyProvider() { |
| 77 } |
| 78 |
| 79 double SHA1EntropyProvider::GetEntropyForTrial( |
| 80 const std::string& trial_name) const { |
| 81 // Given enough input entropy, SHA-1 will produce a uniformly random spread |
| 82 // in its output space. In this case, the input entropy that is used is the |
| 83 // combination of the original |entropy_source_| and the |trial_name|. |
| 84 // |
| 85 // Note: If |entropy_source_| has very low entropy, such as 13 bits or less, |
| 86 // it has been observed that this method does not result in a uniform |
| 87 // distribution given the same |trial_name|. When using such a low entropy |
| 88 // source, PermutedEntropyProvider should be used instead. |
| 89 std::string input(entropy_source_ + trial_name); |
| 90 unsigned char sha1_hash[base::kSHA1Length]; |
| 91 base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()), |
| 92 input.size(), |
| 93 sha1_hash); |
| 94 |
| 95 uint64 bits; |
| 96 COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data); |
| 97 memcpy(&bits, sha1_hash, sizeof(bits)); |
| 98 bits = base::ByteSwapToLE64(bits); |
| 99 |
| 100 return base::BitsToOpenEndedUnitInterval(bits); |
| 101 } |
| 102 |
| 103 PermutedEntropyProvider::PermutedEntropyProvider( |
| 104 uint16 low_entropy_source, |
| 105 size_t low_entropy_source_max) |
| 106 : low_entropy_source_(low_entropy_source), |
| 107 low_entropy_source_max_(low_entropy_source_max) { |
| 108 DCHECK_LT(low_entropy_source, low_entropy_source_max); |
| 109 DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16>::max()); |
| 110 } |
| 111 |
| 112 PermutedEntropyProvider::~PermutedEntropyProvider() { |
| 113 } |
| 114 |
| 115 double PermutedEntropyProvider::GetEntropyForTrial( |
| 116 const std::string& trial_name) const { |
| 117 std::vector<uint16> mapping(low_entropy_source_max_); |
| 118 internal::PermuteMappingUsingTrialName(trial_name, &mapping); |
| 119 |
| 120 return mapping[low_entropy_source_] / |
| 121 static_cast<double>(low_entropy_source_max_); |
| 122 } |
| 123 |
| 124 } // namespace metrics |
OLD | NEW |