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