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 /** 49 * Returns value [0...1) as an IEEE float 50 */ nextF()51 float nextF() { 52 unsigned int floatint = 0x3f800000 | (this->nextU() >> 9); 53 float f = SkBits2Float(floatint) - 1.0f; 54 return f; 55 } 56 57 /** 58 * Returns value [min...max) as a float 59 */ nextRangeF(float min,float max)60 float nextRangeF(float min, float max) { 61 return min + this->nextF() * (max - min); 62 } 63 64 /** Return the next pseudo random number, as an unsigned value of 65 at most bitCount bits. 66 @param bitCount The maximum number of bits to be returned 67 */ nextBits(unsigned bitCount)68 uint32_t nextBits(unsigned bitCount) { 69 SkASSERT(bitCount > 0 && bitCount <= 32); 70 return this->nextU() >> (32 - bitCount); 71 } 72 73 /** Return the next pseudo random unsigned number, mapped to lie within 74 [min, max] inclusive. 75 */ nextRangeU(uint32_t min,uint32_t max)76 uint32_t nextRangeU(uint32_t min, uint32_t max) { 77 SkASSERT(min <= max); 78 uint32_t range = max - min + 1; 79 if (0 == range) { 80 return this->nextU(); 81 } else { 82 return min + this->nextU() % range; 83 } 84 } 85 86 /** Return the next pseudo random unsigned number, mapped to lie within 87 [0, count). 88 */ nextULessThan(uint32_t count)89 uint32_t nextULessThan(uint32_t count) { 90 SkASSERT(count > 0); 91 return this->nextRangeU(0, count - 1); 92 } 93 94 /** Return the next pseudo random number expressed as a SkScalar 95 in the range [0..SK_Scalar1). 96 */ nextUScalar1()97 SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); } 98 99 /** Return the next pseudo random number expressed as a SkScalar 100 in the range [min..max). 101 */ nextRangeScalar(SkScalar min,SkScalar max)102 SkScalar nextRangeScalar(SkScalar min, SkScalar max) { 103 return this->nextUScalar1() * (max - min) + min; 104 } 105 106 /** Return the next pseudo random number expressed as a SkScalar 107 in the range [-SK_Scalar1..SK_Scalar1). 108 */ nextSScalar1()109 SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); } 110 111 /** Return the next pseudo random number as a bool. 112 */ nextBool()113 bool nextBool() { return this->nextU() >= 0x80000000; } 114 115 /** A biased version of nextBool(). 116 */ nextBiasedBool(SkScalar fractionTrue)117 bool nextBiasedBool(SkScalar fractionTrue) { 118 SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1); 119 return this->nextUScalar1() <= fractionTrue; 120 } 121 122 /** Reset the random object. 123 */ setSeed(uint32_t seed)124 void setSeed(uint32_t seed) { init(seed); } 125 126 private: 127 // Initialize state variables with LCG. 128 // We must ensure that both J and K are non-zero, otherwise the 129 // multiply-with-carry step will forevermore return zero. init(uint32_t seed)130 void init(uint32_t seed) { 131 fK = NextLCG(seed); 132 if (0 == fK) { 133 fK = NextLCG(fK); 134 } 135 fJ = NextLCG(fK); 136 if (0 == fJ) { 137 fJ = NextLCG(fJ); 138 } 139 SkASSERT(0 != fK && 0 != fJ); 140 } NextLCG(uint32_t seed)141 static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; } 142 143 /** Return the next pseudo random number expressed as an unsigned SkFixed 144 in the range [0..SK_Fixed1). 145 */ nextUFixed1()146 SkFixed nextUFixed1() { return this->nextU() >> 16; } 147 148 /** Return the next pseudo random number expressed as a signed SkFixed 149 in the range [-SK_Fixed1..SK_Fixed1). 150 */ nextSFixed1()151 SkFixed nextSFixed1() { return this->nextS() >> 15; } 152 153 // See "Numerical Recipes in C", 1992 page 284 for these constants 154 // For the LCG that sets the initial state from a seed 155 enum { 156 kMul = 1664525, 157 kAdd = 1013904223 158 }; 159 // Constants for the multiply-with-carry steps 160 enum { 161 kKMul = 30345, 162 kJMul = 18000, 163 }; 164 165 uint32_t fK; 166 uint32_t fJ; 167 }; 168 169 #endif 170