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