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
SeededRandGenerator(uint32 seed)21 SeededRandGenerator::SeededRandGenerator(uint32 seed) {
22 mersenne_twister_.init_genrand(seed);
23 }
24
~SeededRandGenerator()25 SeededRandGenerator::~SeededRandGenerator() {
26 }
27
operator ()(uint32 range)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
PermuteMappingUsingRandomizationSeed(uint32 randomization_seed,std::vector<uint16> * mapping)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
54 // Do a deterministic random shuffle of the mapping using |generator|.
55 //
56 // Note: This logic is identical to the following call with libstdc++ and VS:
57 //
58 // std::random_shuffle(mapping->begin(), mapping->end(), generator);
59 //
60 // However, this is not guaranteed by the spec and some implementations (e.g.
61 // libc++) use a different algorithm. To ensure results are consistent
62 // regardless of the compiler toolchain used, use our own version.
63 for (size_t i = 1; i < mapping->size(); ++i) {
64 // Pick an element in mapping[:i+1] with which to exchange mapping[i].
65 size_t j = generator(i + 1);
66 std::swap((*mapping)[i], (*mapping)[j]);
67 }
68 }
69
70 } // namespace internal
71
SHA1EntropyProvider(const std::string & entropy_source)72 SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source)
73 : entropy_source_(entropy_source) {
74 }
75
~SHA1EntropyProvider()76 SHA1EntropyProvider::~SHA1EntropyProvider() {
77 }
78
GetEntropyForTrial(const std::string & trial_name,uint32 randomization_seed) const79 double SHA1EntropyProvider::GetEntropyForTrial(
80 const std::string& trial_name,
81 uint32 randomization_seed) const {
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
84 // combination of the original |entropy_source_| and the |trial_name|.
85 //
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
88 // distribution given the same |trial_name|. When using such a low entropy
89 // source, PermutedEntropyProvider should be used instead.
90 std::string input(entropy_source_ + trial_name);
91 unsigned char sha1_hash[base::kSHA1Length];
92 base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()),
93 input.size(),
94 sha1_hash);
95
96 uint64 bits;
97 COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data);
98 memcpy(&bits, sha1_hash, sizeof(bits));
99 bits = base::ByteSwapToLE64(bits);
100
101 return base::BitsToOpenEndedUnitInterval(bits);
102 }
103
PermutedEntropyProvider(uint16 low_entropy_source,size_t low_entropy_source_max)104 PermutedEntropyProvider::PermutedEntropyProvider(
105 uint16 low_entropy_source,
106 size_t low_entropy_source_max)
107 : low_entropy_source_(low_entropy_source),
108 low_entropy_source_max_(low_entropy_source_max) {
109 DCHECK_LT(low_entropy_source, low_entropy_source_max);
110 DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16>::max());
111 }
112
~PermutedEntropyProvider()113 PermutedEntropyProvider::~PermutedEntropyProvider() {
114 }
115
GetEntropyForTrial(const std::string & trial_name,uint32 randomization_seed) const116 double PermutedEntropyProvider::GetEntropyForTrial(
117 const std::string& trial_name,
118 uint32 randomization_seed) const {
119 if (randomization_seed == 0)
120 randomization_seed = HashName(trial_name);
121
122 return GetPermutedValue(randomization_seed) /
123 static_cast<double>(low_entropy_source_max_);
124 }
125
GetPermutedValue(uint32 randomization_seed) const126 uint16 PermutedEntropyProvider::GetPermutedValue(
127 uint32 randomization_seed) const {
128 std::vector<uint16> mapping(low_entropy_source_max_);
129 internal::PermuteMappingUsingRandomizationSeed(randomization_seed, &mapping);
130 return mapping[low_entropy_source_];
131 }
132
133 } // namespace metrics
134