Home | History | Annotate | Download | only in variations 
      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 
     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 
     72 SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source)
     73     : entropy_source_(entropy_source) {
     74 }
     75 
     76 SHA1EntropyProvider::~SHA1EntropyProvider() {
     77 }
     78 
     79 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 
    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 
    113 PermutedEntropyProvider::~PermutedEntropyProvider() {
    114 }
    115 
    116 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 
    126 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