1 /* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SkRandom_DEFINED 9 #define SkRandom_DEFINED 10 11 #include "include/private/base/SkAssert.h" 12 #include "include/private/base/SkFixed.h" 13 #include "src/base/SkFloatBits.h" 14 15 #include <cstdint> 16 17 typedef float SkScalar; 18 19 /** \class SkRandom 20 21 Utility class that implements pseudo random 32bit numbers using Marsaglia's 22 multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds 23 its own state, so that multiple instances can be used with no side-effects. 24 25 Has a large period and all bits are well-randomized. 26 */ 27 class SkRandom { 28 public: SkRandom()29 SkRandom() { init(0); } SkRandom(uint32_t seed)30 SkRandom(uint32_t seed) { init(seed); } SkRandom(const SkRandom & rand)31 SkRandom(const SkRandom& rand) : fK(rand.fK), fJ(rand.fJ) {} 32 33 SkRandom& operator=(const SkRandom& rand) { 34 fK = rand.fK; 35 fJ = rand.fJ; 36 37 return *this; 38 } 39 40 /** Return the next pseudo random number as an unsigned 32bit value. 41 */ nextU()42 uint32_t nextU() { 43 fK = kKMul*(fK & 0xffff) + (fK >> 16); 44 fJ = kJMul*(fJ & 0xffff) + (fJ >> 16); 45 return (((fK << 16) | (fK >> 16)) + fJ); 46 } 47 48 /** Return the next pseudo random number as a signed 32bit value. 49 */ nextS()50 int32_t nextS() { return (int32_t)this->nextU(); } 51 52 /** 53 * Returns value [0...1) as an IEEE float 54 */ nextF()55 float nextF() { 56 uint32_t floatint = 0x3f800000 | (this->nextU() >> 9); 57 float f = SkBits2Float(floatint) - 1.0f; 58 return f; 59 } 60 61 /** 62 * Returns value [min...max) as a float 63 */ nextRangeF(float min,float max)64 float nextRangeF(float min, float max) { 65 return min + this->nextF() * (max - min); 66 } 67 68 /** Return the next pseudo random number, as an unsigned value of 69 at most bitCount bits. 70 @param bitCount The maximum number of bits to be returned 71 */ nextBits(unsigned bitCount)72 uint32_t nextBits(unsigned bitCount) { 73 SkASSERT(bitCount > 0 && bitCount <= 32); 74 return this->nextU() >> (32 - bitCount); 75 } 76 77 /** Return the next pseudo random unsigned number, mapped to lie within 78 [min, max] inclusive. 79 */ nextRangeU(uint32_t min,uint32_t max)80 uint32_t nextRangeU(uint32_t min, uint32_t max) { 81 SkASSERT(min <= max); 82 uint32_t range = max - min + 1; 83 if (0 == range) { 84 return this->nextU(); 85 } else { 86 return min + this->nextU() % range; 87 } 88 } 89 90 /** Return the next pseudo random unsigned number, mapped to lie within 91 [0, count). 92 */ nextULessThan(uint32_t count)93 uint32_t nextULessThan(uint32_t count) { 94 SkASSERT(count > 0); 95 return this->nextRangeU(0, count - 1); 96 } 97 98 /** Return the next pseudo random number expressed as a SkScalar 99 in the range [0..SK_Scalar1). 100 */ nextUScalar1()101 SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); } 102 103 /** Return the next pseudo random number expressed as a SkScalar 104 in the range [min..max). 105 */ nextRangeScalar(SkScalar min,SkScalar max)106 SkScalar nextRangeScalar(SkScalar min, SkScalar max) { 107 return this->nextUScalar1() * (max - min) + min; 108 } 109 110 /** Return the next pseudo random number expressed as a SkScalar 111 in the range [-SK_Scalar1..SK_Scalar1). 112 */ nextSScalar1()113 SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); } 114 115 /** Return the next pseudo random number as a bool. 116 */ nextBool()117 bool nextBool() { return this->nextU() >= 0x80000000; } 118 119 /** A biased version of nextBool(). 120 */ nextBiasedBool(SkScalar fractionTrue)121 bool nextBiasedBool(SkScalar fractionTrue) { 122 SkASSERT(fractionTrue >= 0 && fractionTrue <= 1); 123 return this->nextUScalar1() <= fractionTrue; 124 } 125 126 /** Reset the random object. 127 */ setSeed(uint32_t seed)128 void setSeed(uint32_t seed) { init(seed); } 129 130 private: 131 // Initialize state variables with LCG. 132 // We must ensure that both J and K are non-zero, otherwise the 133 // multiply-with-carry step will forevermore return zero. init(uint32_t seed)134 void init(uint32_t seed) { 135 fK = NextLCG(seed); 136 if (0 == fK) { 137 fK = NextLCG(fK); 138 } 139 fJ = NextLCG(fK); 140 if (0 == fJ) { 141 fJ = NextLCG(fJ); 142 } 143 SkASSERT(0 != fK && 0 != fJ); 144 } NextLCG(uint32_t seed)145 static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; } 146 147 /** Return the next pseudo random number expressed as an unsigned SkFixed 148 in the range [0..SK_Fixed1). 149 */ nextUFixed1()150 SkFixed nextUFixed1() { return this->nextU() >> 16; } 151 152 /** Return the next pseudo random number expressed as a signed SkFixed 153 in the range [-SK_Fixed1..SK_Fixed1). 154 */ nextSFixed1()155 SkFixed nextSFixed1() { return this->nextS() >> 15; } 156 157 // See "Numerical Recipes in C", 1992 page 284 for these constants 158 // For the LCG that sets the initial state from a seed 159 enum { 160 kMul = 1664525, 161 kAdd = 1013904223 162 }; 163 // Constants for the multiply-with-carry steps 164 enum { 165 kKMul = 30345, 166 kJMul = 18000, 167 }; 168 169 uint32_t fK; 170 uint32_t fJ; 171 }; 172 173 #endif 174