Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(179)

Side by Side Diff: base/rand_util.cc

Issue 7080005: Fix base::RandGenerator bug (it had non-uniform random distribution). (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Switch to bitwise operations. Max to 1000. Created 9 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « no previous file | base/rand_util_unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "base/rand_util.h" 5 #include "base/rand_util.h"
6 6
7 #include <math.h> 7 #include <math.h>
8 8
9 #include <limits> 9 #include <limits>
10 10
(...skipping 27 matching lines...) Expand all
38 static const int kBits = std::numeric_limits<double>::digits; 38 static const int kBits = std::numeric_limits<double>::digits;
39 uint64 random_bits = bits & ((GG_UINT64_C(1) << kBits) - 1); 39 uint64 random_bits = bits & ((GG_UINT64_C(1) << kBits) - 1);
40 double result = ldexp(static_cast<double>(random_bits), -1 * kBits); 40 double result = ldexp(static_cast<double>(random_bits), -1 * kBits);
41 DCHECK_GE(result, 0.0); 41 DCHECK_GE(result, 0.0);
42 DCHECK_LT(result, 1.0); 42 DCHECK_LT(result, 1.0);
43 return result; 43 return result;
44 } 44 }
45 45
46 uint64 RandGenerator(uint64 max) { 46 uint64 RandGenerator(uint64 max) {
47 DCHECK_GT(max, 0ULL); 47 DCHECK_GT(max, 0ULL);
48 return base::RandUint64() % max; 48
49 // We must discard random results above this number, as they would
50 // make the random generator non-uniform (consider e.g. if
51 // MAX_UINT64 was 4 and max was 3, then a result of 1 would be twice
52 // as likely as a result of 0 or 2).
53 uint64 max_acceptable_value =
54 (std::numeric_limits<uint64>::max() / max) * max;
55
56 uint64 value;
57 do {
58 value = base::RandUint64();
59 } while (value >= max_acceptable_value);
60
61 return value % max;
49 } 62 }
50 63
51 void RandBytes(void* output, size_t output_length) { 64 void RandBytes(void* output, size_t output_length) {
52 uint64 random_int; 65 uint64 random_int;
53 size_t random_int_size = sizeof(random_int); 66 size_t random_int_size = sizeof(random_int);
54 for (size_t i = 0; i < output_length; i += random_int_size) { 67 for (size_t i = 0; i < output_length; i += random_int_size) {
55 random_int = base::RandUint64(); 68 random_int = base::RandUint64();
56 size_t copy_count = std::min(output_length - i, random_int_size); 69 size_t copy_count = std::min(output_length - i, random_int_size);
57 memcpy(((uint8*)output) + i, &random_int, copy_count); 70 memcpy(((uint8*)output) + i, &random_int, copy_count);
58 } 71 }
59 } 72 }
60 73
61 std::string RandBytesAsString(size_t length) { 74 std::string RandBytesAsString(size_t length) {
62 std::string result; 75 std::string result;
63 RandBytes(WriteInto(&result, length + 1), length); 76 RandBytes(WriteInto(&result, length + 1), length);
64 return result; 77 return result;
65 } 78 }
66 79
67 } // namespace base 80 } // namespace base
OLDNEW
« no previous file with comments | « no previous file | base/rand_util_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698