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