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 "include/core/SkScalar.h" |
12 | #include "include/private/SkFixed.h" |
13 | #include "include/private/SkFloatBits.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: |
25 | SkRandom() { init(0); } |
26 | SkRandom(uint32_t seed) { init(seed); } |
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 | */ |
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 | */ |
46 | int32_t nextS() { return (int32_t)this->nextU(); } |
47 | |
48 | /** |
49 | * Returns value [0...1) as an IEEE float |
50 | */ |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
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 | */ |
109 | SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); } |
110 | |
111 | /** Return the next pseudo random number as a bool. |
112 | */ |
113 | bool nextBool() { return this->nextU() >= 0x80000000; } |
114 | |
115 | /** A biased version of nextBool(). |
116 | */ |
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 | */ |
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. |
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 | } |
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 | */ |
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 | */ |
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 | |