1 // Copyright 2011 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "partition_alloc/partition_alloc_base/rand_util.h" 6 7 #include <limits.h> 8 #include <math.h> 9 #include <stdint.h> 10 11 #include <limits> 12 13 #include "partition_alloc/partition_alloc_base/check.h" 14 15 namespace partition_alloc::internal::base { 16 RandUint64()17uint64_t RandUint64() { 18 uint64_t number; 19 RandBytes(&number, sizeof(number)); 20 return number; 21 } 22 RandGenerator(uint64_t range)23uint64_t RandGenerator(uint64_t range) { 24 PA_BASE_DCHECK(range > 0u); 25 // We must discard random results above this number, as they would 26 // make the random generator non-uniform (consider e.g. if 27 // MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice 28 // as likely as a result of 3 or 4). 29 uint64_t max_acceptable_value = 30 (std::numeric_limits<uint64_t>::max() / range) * range - 1; 31 32 uint64_t value; 33 do { 34 value = base::RandUint64(); 35 } while (value > max_acceptable_value); 36 37 return value % range; 38 } 39 InsecureRandomGenerator()40InsecureRandomGenerator::InsecureRandomGenerator() { 41 a_ = base::RandUint64(); 42 b_ = base::RandUint64(); 43 } 44 ReseedForTesting(uint64_t seed)45void InsecureRandomGenerator::ReseedForTesting(uint64_t seed) { 46 a_ = seed; 47 b_ = seed; 48 } 49 RandUint64()50uint64_t InsecureRandomGenerator::RandUint64() { 51 // Using XorShift128+, which is simple and widely used. See 52 // https://en.wikipedia.org/wiki/Xorshift#xorshift+ for details. 53 uint64_t t = a_; 54 const uint64_t s = b_; 55 56 a_ = s; 57 t ^= t << 23; 58 t ^= t >> 17; 59 t ^= s ^ (s >> 26); 60 b_ = t; 61 62 return t + s; 63 } 64 RandUint32()65uint32_t InsecureRandomGenerator::RandUint32() { 66 // The generator usually returns an uint64_t, truncate it. 67 // 68 // It is noted in this paper (https://arxiv.org/abs/1810.05313) that the 69 // lowest 32 bits fail some statistical tests from the Big Crush 70 // suite. Use the higher ones instead. 71 return this->RandUint64() >> 32; 72 } 73 74 } // namespace partition_alloc::internal::base 75