1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "components/variations/entropy_provider.h"
#include <algorithm>
#include <limits>
#include <vector>
#include "base/logging.h"
#include "base/rand_util.h"
#include "base/sha1.h"
#include "base/sys_byteorder.h"
#include "components/variations/metrics_util.h"
namespace metrics {
namespace internal {
SeededRandGenerator::SeededRandGenerator(uint32 seed) {
mersenne_twister_.init_genrand(seed);
}
SeededRandGenerator::~SeededRandGenerator() {
}
uint32 SeededRandGenerator::operator()(uint32 range) {
// Based on base::RandGenerator().
DCHECK_GT(range, 0u);
// We must discard random results above this number, as they would
// make the random generator non-uniform (consider e.g. if
// MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice
// as likely as a result of 3 or 4).
uint32 max_acceptable_value =
(std::numeric_limits<uint32>::max() / range) * range - 1;
uint32 value;
do {
value = mersenne_twister_.genrand_int32();
} while (value > max_acceptable_value);
return value % range;
}
void PermuteMappingUsingRandomizationSeed(uint32 randomization_seed,
std::vector<uint16>* mapping) {
for (size_t i = 0; i < mapping->size(); ++i)
(*mapping)[i] = static_cast<uint16>(i);
SeededRandGenerator generator(randomization_seed);
// Do a deterministic random shuffle of the mapping using |generator|.
//
// Note: This logic is identical to the following call with libstdc++ and VS:
//
// std::random_shuffle(mapping->begin(), mapping->end(), generator);
//
// However, this is not guaranteed by the spec and some implementations (e.g.
// libc++) use a different algorithm. To ensure results are consistent
// regardless of the compiler toolchain used, use our own version.
for (size_t i = 1; i < mapping->size(); ++i) {
// Pick an element in mapping[:i+1] with which to exchange mapping[i].
size_t j = generator(i + 1);
std::swap((*mapping)[i], (*mapping)[j]);
}
}
} // namespace internal
SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source)
: entropy_source_(entropy_source) {
}
SHA1EntropyProvider::~SHA1EntropyProvider() {
}
double SHA1EntropyProvider::GetEntropyForTrial(
const std::string& trial_name,
uint32 randomization_seed) const {
// Given enough input entropy, SHA-1 will produce a uniformly random spread
// in its output space. In this case, the input entropy that is used is the
// combination of the original |entropy_source_| and the |trial_name|.
//
// Note: If |entropy_source_| has very low entropy, such as 13 bits or less,
// it has been observed that this method does not result in a uniform
// distribution given the same |trial_name|. When using such a low entropy
// source, PermutedEntropyProvider should be used instead.
std::string input(entropy_source_ + trial_name);
unsigned char sha1_hash[base::kSHA1Length];
base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()),
input.size(),
sha1_hash);
uint64 bits;
static_assert(sizeof(bits) < sizeof(sha1_hash), "more data required");
memcpy(&bits, sha1_hash, sizeof(bits));
bits = base::ByteSwapToLE64(bits);
return base::BitsToOpenEndedUnitInterval(bits);
}
PermutedEntropyProvider::PermutedEntropyProvider(
uint16 low_entropy_source,
size_t low_entropy_source_max)
: low_entropy_source_(low_entropy_source),
low_entropy_source_max_(low_entropy_source_max) {
DCHECK_LT(low_entropy_source, low_entropy_source_max);
DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16>::max());
}
PermutedEntropyProvider::~PermutedEntropyProvider() {
}
double PermutedEntropyProvider::GetEntropyForTrial(
const std::string& trial_name,
uint32 randomization_seed) const {
if (randomization_seed == 0)
randomization_seed = HashName(trial_name);
return GetPermutedValue(randomization_seed) /
static_cast<double>(low_entropy_source_max_);
}
uint16 PermutedEntropyProvider::GetPermutedValue(
uint32 randomization_seed) const {
std::vector<uint16> mapping(low_entropy_source_max_);
internal::PermuteMappingUsingRandomizationSeed(randomization_seed, &mapping);
return mapping[low_entropy_source_];
}
} // namespace metrics
|
