Line data Source code
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:
24 0 : SkRandom() { init(0); }
25 : SkRandom(uint32_t seed) { init(seed); }
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 : */
37 0 : uint32_t nextU() {
38 0 : fK = kKMul*(fK & 0xffff) + (fK >> 16);
39 0 : fJ = kJMul*(fJ & 0xffff) + (fJ >> 16);
40 0 : return (((fK << 16) | (fK >> 16)) + fJ);
41 : }
42 :
43 : /** Return the next pseudo random number as a signed 32bit value.
44 : */
45 0 : int32_t nextS() { return (int32_t)this->nextU(); }
46 :
47 : /** Return the next pseudo random number as an unsigned 16bit value.
48 : */
49 : U16CPU nextU16() { return this->nextU() >> 16; }
50 :
51 : /** Return the next pseudo random number as a signed 16bit value.
52 : */
53 : S16CPU nextS16() { return this->nextS() >> 16; }
54 :
55 : /**
56 : * Returns value [0...1) as an IEEE float
57 : */
58 0 : float nextF() {
59 0 : unsigned int floatint = 0x3f800000 | (this->nextU() >> 9);
60 0 : float f = SkBits2Float(floatint) - 1.0f;
61 0 : return f;
62 : }
63 :
64 : /**
65 : * Returns value [min...max) as a float
66 : */
67 0 : float nextRangeF(float min, float max) {
68 0 : 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 : */
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 : */
83 0 : uint32_t nextRangeU(uint32_t min, uint32_t max) {
84 0 : SkASSERT(min <= max);
85 0 : uint32_t range = max - min + 1;
86 0 : if (0 == range) {
87 0 : return this->nextU();
88 : } else {
89 0 : return min + this->nextU() % range;
90 : }
91 : }
92 :
93 : /** Return the next pseudo random unsigned number, mapped to lie within
94 : [0, count).
95 : */
96 0 : uint32_t nextULessThan(uint32_t count) {
97 0 : SkASSERT(count > 0);
98 0 : 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 : */
104 0 : 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 : */
109 0 : SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
110 0 : 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 : */
116 0 : SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
117 :
118 : /** Return the next pseudo random number as a bool.
119 : */
120 0 : bool nextBool() { return this->nextU() >= 0x80000000; }
121 :
122 : /** A biased version of nextBool().
123 : */
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 : */
132 : int64_t next64() {
133 : int64_t hi = this->nextS();
134 : return (hi << 32) | this->nextU();
135 : }
136 :
137 : /** Reset the random object.
138 : */
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.
145 0 : void init(uint32_t seed) {
146 0 : fK = NextLCG(seed);
147 0 : if (0 == fK) {
148 0 : fK = NextLCG(fK);
149 : }
150 0 : fJ = NextLCG(fK);
151 0 : if (0 == fJ) {
152 0 : fJ = NextLCG(fJ);
153 : }
154 0 : SkASSERT(0 != fK && 0 != fJ);
155 0 : }
156 0 : 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 : */
161 0 : 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 : */
166 0 : 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
|