entropy_provider.cc 3.5 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
  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. #include "components/variations/entropy_provider.h"
  5. #include <algorithm>
  6. #include <limits>
  7. #include "base/check_op.h"
  8. #include "base/hash/sha1.h"
  9. #include "base/rand_util.h"
  10. #include "base/strings/strcat.h"
  11. #include "base/strings/string_number_conversions.h"
  12. #include "base/sys_byteorder.h"
  13. #include "components/variations/hashing.h"
  14. #include "components/variations/variations_murmur_hash.h"
  15. namespace variations {
  16. SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source)
  17. : entropy_source_(entropy_source) {
  18. }
  19. SHA1EntropyProvider::~SHA1EntropyProvider() {
  20. }
  21. double SHA1EntropyProvider::GetEntropyForTrial(
  22. base::StringPiece trial_name,
  23. uint32_t randomization_seed) const {
  24. // Given enough input entropy, SHA-1 will produce a uniformly random spread
  25. // in its output space. In this case, the input entropy that is used is the
  26. // combination of the original |entropy_source_| and the |trial_name|.
  27. //
  28. // Note: If |entropy_source_| has very low entropy, such as 13 bits or less,
  29. // it has been observed that this method does not result in a uniform
  30. // distribution given the same |trial_name|. When using such a low entropy
  31. // source, NormalizedMurmurHashEntropyProvider should be used instead.
  32. std::string input = base::StrCat(
  33. {entropy_source_, randomization_seed == 0
  34. ? trial_name
  35. : base::NumberToString(randomization_seed)});
  36. unsigned char sha1_hash[base::kSHA1Length];
  37. base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()),
  38. input.size(),
  39. sha1_hash);
  40. uint64_t bits;
  41. static_assert(sizeof(bits) < sizeof(sha1_hash), "more data required");
  42. memcpy(&bits, sha1_hash, sizeof(bits));
  43. bits = base::ByteSwapToLE64(bits);
  44. return base::BitsToOpenEndedUnitInterval(bits);
  45. }
  46. NormalizedMurmurHashEntropyProvider::NormalizedMurmurHashEntropyProvider(
  47. uint16_t low_entropy_source,
  48. size_t low_entropy_source_max)
  49. : low_entropy_source_(low_entropy_source),
  50. low_entropy_source_max_(low_entropy_source_max) {
  51. DCHECK_LT(low_entropy_source, low_entropy_source_max);
  52. DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16_t>::max());
  53. }
  54. NormalizedMurmurHashEntropyProvider::~NormalizedMurmurHashEntropyProvider() {}
  55. double NormalizedMurmurHashEntropyProvider::GetEntropyForTrial(
  56. base::StringPiece trial_name,
  57. uint32_t randomization_seed) const {
  58. if (randomization_seed == 0) {
  59. randomization_seed = internal::VariationsMurmurHash::Hash(
  60. internal::VariationsMurmurHash::StringToLE32(trial_name),
  61. trial_name.length());
  62. }
  63. uint32_t x = internal::VariationsMurmurHash::Hash16(randomization_seed,
  64. low_entropy_source_);
  65. int x_ordinal = 0;
  66. for (uint32_t i = 0; i < low_entropy_source_max_; i++) {
  67. uint32_t y = internal::VariationsMurmurHash::Hash16(randomization_seed, i);
  68. x_ordinal += (y < x);
  69. }
  70. DCHECK_GE(x_ordinal, 0);
  71. // There must have been at least one iteration where |x| == |y|, because
  72. // |i| == |low_entropy_source_|, and |x_ordinal| was not incremented in that
  73. // iteration, so |x_ordinal| < |low_entropy_source_max_|.
  74. DCHECK_LT(static_cast<size_t>(x_ordinal), low_entropy_source_max_);
  75. return static_cast<double>(x_ordinal) / low_entropy_source_max_;
  76. }
  77. } // namespace variations