diff options
| author | joi@chromium.org <joi@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2011-05-30 17:39:09 +0000 |
|---|---|---|
| committer | joi@chromium.org <joi@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2011-05-30 17:39:09 +0000 |
| commit | af2e192b4a8d5ff0270b54bda694254e5cd5f8fa (patch) | |
| tree | d194a9bbbc1e5f9a51ec22a6d2a74aa1485e6e13 /base/rand_util.cc | |
| parent | dcc60711b9c1e8358cc6c961db4e6b5cf05e1472 (diff) | |
| download | chromium_src-af2e192b4a8d5ff0270b54bda694254e5cd5f8fa.zip chromium_src-af2e192b4a8d5ff0270b54bda694254e5cd5f8fa.tar.gz chromium_src-af2e192b4a8d5ff0270b54bda694254e5cd5f8fa.tar.bz2 | |
Fix base::RandGenerator bug (it had non-uniform random distribution). Add test that would have caught bug. Also add a test to verify that our random generators are at least somewhat random.
BUG=84221
TEST=base_unittests --gtest_filter=RandUtilTest.*
Review URL: http://codereview.chromium.org/7080005
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@87244 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'base/rand_util.cc')
| -rw-r--r-- | base/rand_util.cc | 15 |
1 files changed, 14 insertions, 1 deletions
diff --git a/base/rand_util.cc b/base/rand_util.cc index 4140e9a..e556c07 100644 --- a/base/rand_util.cc +++ b/base/rand_util.cc @@ -45,7 +45,20 @@ double BitsToOpenEndedUnitInterval(uint64 bits) { uint64 RandGenerator(uint64 max) { DCHECK_GT(max, 0ULL); - return base::RandUint64() % max; + + // We must discard random results above this number, as they would + // make the random generator non-uniform (consider e.g. if + // MAX_UINT64 was 4 and max was 3, then a result of 1 would be twice + // as likely as a result of 0 or 2). + uint64 max_acceptable_value = + (std::numeric_limits<uint64>::max() / max) * max; + + uint64 value; + do { + value = base::RandUint64(); + } while (value >= max_acceptable_value); + + return value % max; } void RandBytes(void* output, size_t output_length) { |