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