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