reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 2 | * Copyright 2006 The Android Open Source Project |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 3 | * |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 6 | */ |
| 7 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 8 | #ifndef SkRandom_DEFINED |
| 9 | #define SkRandom_DEFINED |
| 10 | |
benjaminwagner | 6c71e0a | 2016-04-07 08:49:31 -0700 | [diff] [blame] | 11 | #include "../private/SkFixed.h" |
Mike Reed | 35ee0e0 | 2017-08-06 22:29:57 -0400 | [diff] [blame] | 12 | #include "../private/SkFloatBits.h" |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 13 | #include "SkScalar.h" |
| 14 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 15 | /** \class SkRandom |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 16 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 17 | Utility class that implements pseudo random 32bit numbers using Marsaglia's |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 18 | multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 19 | its own state, so that multiple instances can be used with no side-effects. |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 20 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 21 | Has a large period and all bits are well-randomized. |
| 22 | */ |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 23 | class SkRandom { |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 24 | public: |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 25 | SkRandom() { init(0); } |
| 26 | SkRandom(uint32_t seed) { init(seed); } |
| 27 | SkRandom(const SkRandom& rand) : fK(rand.fK), fJ(rand.fJ) {} |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 28 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 29 | SkRandom& operator=(const SkRandom& rand) { |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 30 | fK = rand.fK; |
| 31 | fJ = rand.fJ; |
| 32 | |
| 33 | return *this; |
| 34 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 35 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 36 | /** Return the next pseudo random number as an unsigned 32bit value. |
| 37 | */ |
| 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 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 43 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 44 | /** Return the next pseudo random number as a signed 32bit value. |
| 45 | */ |
| 46 | int32_t nextS() { return (int32_t)this->nextU(); } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 47 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 48 | /** Return the next pseudo random number as an unsigned 16bit value. |
| 49 | */ |
| 50 | U16CPU nextU16() { return this->nextU() >> 16; } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 51 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 52 | /** Return the next pseudo random number as a signed 16bit value. |
| 53 | */ |
| 54 | S16CPU nextS16() { return this->nextS() >> 16; } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 55 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 56 | /** |
| 57 | * Returns value [0...1) as an IEEE float |
| 58 | */ |
| 59 | float nextF() { |
| 60 | unsigned int floatint = 0x3f800000 | (this->nextU() >> 9); |
bsalomon@google.com | 753a362 | 2013-02-07 19:52:30 +0000 | [diff] [blame] | 61 | float f = SkBits2Float(floatint) - 1.0f; |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 62 | return f; |
| 63 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 64 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 65 | /** |
| 66 | * Returns value [min...max) as a float |
| 67 | */ |
| 68 | float nextRangeF(float min, float max) { |
| 69 | return min + this->nextF() * (max - min); |
| 70 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 71 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 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 | */ |
| 76 | uint32_t nextBits(unsigned bitCount) { |
| 77 | SkASSERT(bitCount > 0 && bitCount <= 32); |
| 78 | return this->nextU() >> (32 - bitCount); |
| 79 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 80 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 81 | /** Return the next pseudo random unsigned number, mapped to lie within |
| 82 | [min, max] inclusive. |
| 83 | */ |
| 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 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 93 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 94 | /** Return the next pseudo random unsigned number, mapped to lie within |
| 95 | [0, count). |
| 96 | */ |
| 97 | uint32_t nextULessThan(uint32_t count) { |
| 98 | SkASSERT(count > 0); |
| 99 | return this->nextRangeU(0, count - 1); |
| 100 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 101 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 102 | /** Return the next pseudo random number expressed as a SkScalar |
| 103 | in the range [0..SK_Scalar1). |
| 104 | */ |
| 105 | SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 106 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 107 | /** Return the next pseudo random number expressed as a SkScalar |
| 108 | in the range [min..max). |
| 109 | */ |
| 110 | SkScalar nextRangeScalar(SkScalar min, SkScalar max) { |
mike@reedtribe.org | d173b87 | 2014-01-23 02:02:45 +0000 | [diff] [blame] | 111 | return this->nextUScalar1() * (max - min) + min; |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 112 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 113 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 114 | /** Return the next pseudo random number expressed as a SkScalar |
benjaminwagner | 1263448 | 2016-03-31 06:13:22 -0700 | [diff] [blame] | 115 | in the range [-SK_Scalar1..SK_Scalar1). |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 116 | */ |
| 117 | SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 118 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 119 | /** Return the next pseudo random number as a bool. |
| 120 | */ |
| 121 | bool nextBool() { return this->nextU() >= 0x80000000; } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 122 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 123 | /** A biased version of nextBool(). |
| 124 | */ |
| 125 | bool nextBiasedBool(SkScalar fractionTrue) { |
| 126 | SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1); |
| 127 | return this->nextUScalar1() <= fractionTrue; |
| 128 | } |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 129 | |
reed@google.com | 57212f9 | 2013-12-30 14:40:38 +0000 | [diff] [blame] | 130 | /** |
| 131 | * Return the next pseudo random number as a signed 64bit value. |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 132 | */ |
reed@google.com | 57212f9 | 2013-12-30 14:40:38 +0000 | [diff] [blame] | 133 | int64_t next64() { |
| 134 | int64_t hi = this->nextS(); |
| 135 | return (hi << 32) | this->nextU(); |
| 136 | } |
skia.committer@gmail.com | f5e1f63 | 2013-12-31 07:01:36 +0000 | [diff] [blame] | 137 | |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 138 | /** Reset the random object. |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 139 | */ |
| 140 | void setSeed(uint32_t seed) { init(seed); } |
| 141 | |
| 142 | private: |
| 143 | // Initialize state variables with LCG. |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 144 | // We must ensure that both J and K are non-zero, otherwise the |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 145 | // multiply-with-carry step will forevermore return zero. |
| 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 | } |
| 157 | static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; } |
| 158 | |
benjaminwagner | 1263448 | 2016-03-31 06:13:22 -0700 | [diff] [blame] | 159 | /** Return the next pseudo random number expressed as an unsigned SkFixed |
| 160 | in the range [0..SK_Fixed1). |
| 161 | */ |
| 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 | */ |
| 167 | SkFixed nextSFixed1() { return this->nextS() >> 15; } |
| 168 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 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 | }; |
skia.committer@gmail.com | 24d5ee4 | 2013-01-31 07:06:15 +0000 | [diff] [blame] | 180 | |
jvanverth@google.com | a8e66f7 | 2013-01-30 15:42:19 +0000 | [diff] [blame] | 181 | uint32_t fK; |
| 182 | uint32_t fJ; |
| 183 | }; |
| 184 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 185 | #endif |