Use a different algorithm with the low entropy source for field trials.

chrome/common/metrics/entropy_provider.cc

+// 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 "chrome/common/metrics/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"
+
+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;
+}
+
+uint32 HashName(const std::string& name) {
+  // SHA-1 is designed to produce a uniformly random spread in its output space,
+  // even for nearly-identical inputs.
+  unsigned char sha1_hash[base::kSHA1Length];
+  base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(name.c_str()),

[jar (doing other things), 2012/08/17 19:06:19]

Can we get away with a static_cast here?

[Alexei Svitkine (slow), 2012/08/20 15:57:40]

Doesn't look like it. This is what the compiler says:

 error: static_cast from 'const char *' to 'const unsigned char *' is not
allowed

+                      name.size(),
+                      sha1_hash);
+
+  uint32 bits;
+  COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data);
+  memcpy(&bits, sha1_hash, sizeof(bits));
+
+  return base::ByteSwapToLE32(bits);
+}
+
+}  // namespace internal
+
+SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source)
+    : entropy_source_(entropy_source) {
+}
+
+SHA1EntropyProvider::~SHA1EntropyProvider() {
+}
+
+double SHA1EntropyProvider::GetEntropyForTrial(
+    const std::string& trial_name) const {
+  // SHA-1 is designed to produce a uniformly random spread in its output space,
+  // even for nearly-identical inputs, so it helps massage whatever client_id
+  // and trial_name we get into something with a uniform distribution, which
+  // is desirable so that we don't skew any part of the 0-100% spectrum.

[hfung, 2012/08/17 17:35:40]

Mention that it doesn't work as well when there's less entropy (since the
comment seems to imply otherwise)?

[Alexei Svitkine (slow), 2012/08/17 17:57:40]

Updated the comment.

+  std::string input(entropy_source_ + trial_name);
+  unsigned char sha1_hash[base::kSHA1Length];
+  base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()),

[jar (doing other things), 2012/08/17 19:06:19]

Would static_cast work here?

[Alexei Svitkine (slow), 2012/08/20 15:57:40]

Same as above.

+                      input.size(),
+                      sha1_hash);
+
+  uint64 bits;
+  COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data);
+  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),

[jar (doing other things), 2012/08/17 19:06:19]

nit: indent ":" 4 spaces from the "P" in "Permuted..."

[Alexei Svitkine (slow), 2012/08/20 15:57:40]

Done.

+          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) const {
+  std::vector<uint16> mapping(low_entropy_source_max_);
+  for (size_t i = 0; i < mapping.size(); ++i)
+    mapping[i] = static_cast<uint16>(i);
+
+  internal::SeededRandGenerator generator(internal::HashName(trial_name));
+  std::random_shuffle(mapping.begin(), mapping.end(), generator);
+
+  return mapping[low_entropy_source_] /
+         static_cast<double>(low_entropy_source_max_);
+}