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

chrome/common/metrics/entropy_provider.h

Index: chrome/common/metrics/entropy_provider.h
===================================================================
--- chrome/common/metrics/entropy_provider.h	(revision 0)
+++ chrome/common/metrics/entropy_provider.h	(revision 0)
@@ -0,0 +1,81 @@
+// 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.
+
+#ifndef CHROME_COMMON_METRICS_ENTROPY_PROVIDER_H_
+#define CHROME_COMMON_METRICS_ENTROPY_PROVIDER_H_
+
+#include <functional>
+#include <string>
+
+#include "base/base_export.h"
+#include "base/basictypes.h"
+#include "base/compiler_specific.h"
+#include "base/metrics/field_trial.h"
+#include "third_party/mt19937ar/mt19937ar.h"
+
+// Internals of entropy_provider.cc exposed for testing.
+namespace internal {
+
+// A functor that generates random numbers based on a seed, using the Mersenne
+// Twister algorithm. Suitable for use with std::random_shuffle().
+struct SeededRandGenerator : std::unary_function<uint32, uint32> {
+  explicit SeededRandGenerator(uint32 seed);
+  ~SeededRandGenerator();
+
+  // Returns a random number in range [0, range).
+  uint32 operator()(uint32 range);
+
+  MersenneTwister mersenne_twister_;
+};
+
+// Creates unique identifier for the trial by hashing a name string, whether
+// it's for the field trial or the group name.
+// TODO(asvitkine): Share the implementation with variations_util.cc.

[SteveT, 2012/08/16 20:55:42]

Recently I saw a comment in a CL about how bugs are preferred over TODOs. Do you
think HashName is something that would be useful in base? If so, log a bug about
moving it out there. Otherwise you can ignore this comment :)

[Alexei Svitkine (slow), 2012/08/16 21:27:11]

I'm not convinced it needs to be in base. I think we can just expose it in
variations_util.cc - the reason I didn't do this already is to make merging this
patch to earlier branches easier (if it gets approved for merge) - since
variations_util.cc has been refactored recently.

+uint32 HashName(const std::string& name);
+
+}  // namespace internal
+
+// SHA1EntropyProvider is an entropy provider suitable for high entropy
+// sources. It works by taking the first 64 bits of the SHA1 hash of the
+// entropy source concatenated with the trial name and using that for the
+// final entropy value.
+class SHA1EntropyProvider : public base::FieldTrial::EntropyProvider {
+ public:
+  // Creates a SHA1EntropyProvider with the given |entropy_source|, which
+  // should contain a large amount of entropy - for example a textual

[SteveT, 2012/08/16 20:55:42]

nit: for example -> for example.

[Alexei Svitkine (slow), 2012/08/17 14:08:59]

Done.

+  // representation of a persistent randomly-generated 64-bit value.
+  explicit SHA1EntropyProvider(const std::string& entropy_source);
+  virtual ~SHA1EntropyProvider();
+
+  // base::FieldTrial::EntropyProvider implementation:
+  virtual double GetEntropyForTrial(const std::string& trial_name) OVERRIDE;
+
+ private:
+  std::string entropy_source_;
+
+  DISALLOW_COPY_AND_ASSIGN(SHA1EntropyProvider);
+};
+
+// PermutedEntropyProvider is an entropy provider suitable for low entropy
+// sources (below 16 bits). It uses the field trial name to generate a

[SteveT, 2012/08/16 20:55:42]

Curious: Did we test this 16 bits assertion?

[Alexei Svitkine (slow), 2012/08/17 14:08:59]

I guess it's kind of arbitrary - the thing is that the performance of this
entropy provider is O(n^2) where n = number of bits in the entropy source. So
using a high entropy source would just make this extremely slow. (I've now added
a comment about this).

The 16 bits specifically isn't enforced anywhere except in the fact that I'm
using a uint16 for |low_entropy_source|.

I've now also added some DCHECKs() in the implementation of the constructor that
assert this too.

+// permutation of a mapping array from an initial entropy value to a new value.
+class PermutedEntropyProvider : public base::FieldTrial::EntropyProvider {
+ public:
+  // Creates a PermutedEntropyProvider with the given |low_entropy_source|,
+  // which should have a value in the range of [0, low_entropy_source_max).
+  PermutedEntropyProvider(uint16 low_entropy_source,
+                          size_t low_entropy_source_max);
+  virtual ~PermutedEntropyProvider();
+
+  // base::FieldTrial::EntropyProvider implementation:
+  virtual double GetEntropyForTrial(const std::string& trial_name) OVERRIDE;
+
+ private:
+  uint16 low_entropy_source_;
+  size_t low_entropy_source_max_;
+
+  DISALLOW_COPY_AND_ASSIGN(PermutedEntropyProvider);
+};
+
+#endif  // CHROME_COMMON_METRICS_ENTROPY_PROVIDER_H_