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
17namespace metrics {
18
19namespace internal {
20
21SeededRandGenerator::SeededRandGenerator(uint32 seed) {
22  mersenne_twister_.init_genrand(seed);
23}
24
25SeededRandGenerator::~SeededRandGenerator() {
26}
27
28uint32 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
47void 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
72SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source)
73    : entropy_source_(entropy_source) {
74}
75
76SHA1EntropyProvider::~SHA1EntropyProvider() {
77}
78
79double 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
104PermutedEntropyProvider::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
113PermutedEntropyProvider::~PermutedEntropyProvider() {
114}
115
116double 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
126uint16 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