components/variations/entropy_provider.cc

   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