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 "SkScalar.h"
12
13/** \class SkLCGRandom
14
15    Utility class that implements pseudo random 32bit numbers using a fast
16    linear equation. Unlike rand(), this class holds its own seed (initially
17    set to 0), so that multiple instances can be used with no side-effects.
18*/
19class SkLCGRandom {
20public:
21    SkLCGRandom() : fSeed(0) {}
22    SkLCGRandom(uint32_t seed) : fSeed(seed) {}
23
24    /** Return the next pseudo random number as an unsigned 32bit value.
25    */
26    uint32_t nextU() { uint32_t r = fSeed * kMul + kAdd; fSeed = r; return r; }
27
28    /** Return the next pseudo random number as a signed 32bit value.
29    */
30    int32_t nextS() { return (int32_t)this->nextU(); }
31
32    /** Return the next pseudo random number as an unsigned 16bit value.
33    */
34    U16CPU nextU16() { return this->nextU() >> 16; }
35
36    /** Return the next pseudo random number as a signed 16bit value.
37    */
38    S16CPU nextS16() { return this->nextS() >> 16; }
39
40    /**
41     *  Returns value [0...1) as a float
42     */
43    float nextF() {
44        // const is 1 / (2^32 - 1)
45        return (float)(this->nextU() * 2.32830644e-10);
46    }
47
48    /**
49     *  Returns value [min...max) as a float
50     */
51    float nextRangeF(float min, float max) {
52        return min + this->nextF() * (max - min);
53    }
54
55    /** Return the next pseudo random number, as an unsigned value of
56        at most bitCount bits.
57        @param bitCount The maximum number of bits to be returned
58    */
59    uint32_t nextBits(unsigned bitCount) {
60        SkASSERT(bitCount > 0 && bitCount <= 32);
61        return this->nextU() >> (32 - bitCount);
62    }
63
64    /** Return the next pseudo random unsigned number, mapped to lie within
65        [min, max] inclusive.
66    */
67    uint32_t nextRangeU(uint32_t min, uint32_t max) {
68        SkASSERT(min <= max);
69        uint32_t range = max - min + 1;
70        if (0 == range) {
71            return this->nextU();
72        } else {
73            return min + this->nextU() % range;
74        }
75    }
76
77    /** Return the next pseudo random unsigned number, mapped to lie within
78        [0, count).
79     */
80    uint32_t nextULessThan(uint32_t count) {
81        SkASSERT(count > 0);
82        return this->nextRangeU(0, count - 1);
83    }
84
85    /** Return the next pseudo random number expressed as an unsigned SkFixed
86        in the range [0..SK_Fixed1).
87    */
88    SkFixed nextUFixed1() { return this->nextU() >> 16; }
89
90    /** Return the next pseudo random number expressed as a signed SkFixed
91        in the range (-SK_Fixed1..SK_Fixed1).
92    */
93    SkFixed nextSFixed1() { return this->nextS() >> 15; }
94
95    /** Return the next pseudo random number expressed as a SkScalar
96        in the range [0..SK_Scalar1).
97    */
98    SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
99
100    /** Return the next pseudo random number expressed as a SkScalar
101        in the range [min..max).
102    */
103    SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
104        return this->nextUScalar1() * (max - min) + min;
105    }
106
107    /** Return the next pseudo random number expressed as a SkScalar
108        in the range (-SK_Scalar1..SK_Scalar1).
109    */
110    SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
111
112    /** Return the next pseudo random number as a bool.
113    */
114    bool nextBool() { return this->nextU() >= 0x80000000; }
115
116    /** A biased version of nextBool().
117     */
118    bool nextBiasedBool(SkScalar fractionTrue) {
119        SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
120        return this->nextUScalar1() <= fractionTrue;
121    }
122
123    /**
124     *  Return the next pseudo random number as a signed 64bit value.
125     */
126    int64_t next64() {
127        int64_t hi = this->nextS();
128        return (hi << 32) | this->nextU();
129    }
130
131    /**
132     *  Return the current seed. This allows the caller to later reset to the
133     *  same seed (using setSeed) so it can generate the same sequence.
134     */
135    int32_t getSeed() const { return fSeed; }
136
137    /** Set the seed of the random object. The seed is initialized to 0 when the
138        object is first created, and is updated each time the next pseudo random
139        number is requested.
140    */
141    void setSeed(int32_t seed) { fSeed = (uint32_t)seed; }
142
143private:
144    //  See "Numerical Recipes in C", 1992 page 284 for these constants
145    enum {
146        kMul = 1664525,
147        kAdd = 1013904223
148    };
149    uint32_t fSeed;
150};
151
152/** \class SkRandom
153
154 Utility class that implements pseudo random 32bit numbers using Marsaglia's
155 multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds
156 its own state, so that multiple instances can be used with no side-effects.
157
158 Has a large period and all bits are well-randomized.
159 */
160class SkRandom {
161public:
162    SkRandom() { init(0); }
163    SkRandom(uint32_t seed) { init(seed); }
164    SkRandom(const SkRandom& rand) : fK(rand.fK), fJ(rand.fJ) {}
165
166    SkRandom& operator=(const SkRandom& rand) {
167        fK = rand.fK;
168        fJ = rand.fJ;
169
170        return *this;
171    }
172
173    /** Return the next pseudo random number as an unsigned 32bit value.
174     */
175    uint32_t nextU() {
176        fK = kKMul*(fK & 0xffff) + (fK >> 16);
177        fJ = kJMul*(fJ & 0xffff) + (fJ >> 16);
178        return (((fK << 16) | (fK >> 16)) + fJ);
179    }
180
181    /** Return the next pseudo random number as a signed 32bit value.
182     */
183    int32_t nextS() { return (int32_t)this->nextU(); }
184
185    /** Return the next pseudo random number as an unsigned 16bit value.
186     */
187    U16CPU nextU16() { return this->nextU() >> 16; }
188
189    /** Return the next pseudo random number as a signed 16bit value.
190     */
191    S16CPU nextS16() { return this->nextS() >> 16; }
192
193    /**
194     *  Returns value [0...1) as an IEEE float
195     */
196    float nextF() {
197        unsigned int floatint = 0x3f800000 | (this->nextU() >> 9);
198        float f = SkBits2Float(floatint) - 1.0f;
199        return f;
200    }
201
202    /**
203     *  Returns value [min...max) as a float
204     */
205    float nextRangeF(float min, float max) {
206        return min + this->nextF() * (max - min);
207    }
208
209    /** Return the next pseudo random number, as an unsigned value of
210     at most bitCount bits.
211     @param bitCount The maximum number of bits to be returned
212     */
213    uint32_t nextBits(unsigned bitCount) {
214        SkASSERT(bitCount > 0 && bitCount <= 32);
215        return this->nextU() >> (32 - bitCount);
216    }
217
218    /** Return the next pseudo random unsigned number, mapped to lie within
219     [min, max] inclusive.
220     */
221    uint32_t nextRangeU(uint32_t min, uint32_t max) {
222        SkASSERT(min <= max);
223        uint32_t range = max - min + 1;
224        if (0 == range) {
225            return this->nextU();
226        } else {
227            return min + this->nextU() % range;
228        }
229    }
230
231    /** Return the next pseudo random unsigned number, mapped to lie within
232     [0, count).
233     */
234    uint32_t nextULessThan(uint32_t count) {
235        SkASSERT(count > 0);
236        return this->nextRangeU(0, count - 1);
237    }
238
239    /** Return the next pseudo random number expressed as an unsigned SkFixed
240     in the range [0..SK_Fixed1).
241     */
242    SkFixed nextUFixed1() { return this->nextU() >> 16; }
243
244    /** Return the next pseudo random number expressed as a signed SkFixed
245     in the range (-SK_Fixed1..SK_Fixed1).
246     */
247    SkFixed nextSFixed1() { return this->nextS() >> 15; }
248
249    /** Return the next pseudo random number expressed as a SkScalar
250     in the range [0..SK_Scalar1).
251     */
252    SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
253
254    /** Return the next pseudo random number expressed as a SkScalar
255     in the range [min..max).
256     */
257    SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
258        return this->nextUScalar1() * (max - min) + min;
259    }
260
261    /** Return the next pseudo random number expressed as a SkScalar
262     in the range (-SK_Scalar1..SK_Scalar1).
263     */
264    SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
265
266    /** Return the next pseudo random number as a bool.
267     */
268    bool nextBool() { return this->nextU() >= 0x80000000; }
269
270    /** A biased version of nextBool().
271     */
272    bool nextBiasedBool(SkScalar fractionTrue) {
273        SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
274        return this->nextUScalar1() <= fractionTrue;
275    }
276
277    /**
278     *  Return the next pseudo random number as a signed 64bit value.
279     */
280    int64_t next64() {
281        int64_t hi = this->nextS();
282        return (hi << 32) | this->nextU();
283    }
284
285    /** Reset the random object.
286     */
287    void setSeed(uint32_t seed) { init(seed); }
288
289private:
290    // Initialize state variables with LCG.
291    // We must ensure that both J and K are non-zero, otherwise the
292    // multiply-with-carry step will forevermore return zero.
293    void init(uint32_t seed) {
294        fK = NextLCG(seed);
295        if (0 == fK) {
296            fK = NextLCG(fK);
297        }
298        fJ = NextLCG(fK);
299        if (0 == fJ) {
300            fJ = NextLCG(fJ);
301        }
302        SkASSERT(0 != fK && 0 != fJ);
303    }
304    static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; }
305
306    //  See "Numerical Recipes in C", 1992 page 284 for these constants
307    //  For the LCG that sets the initial state from a seed
308    enum {
309        kMul = 1664525,
310        kAdd = 1013904223
311    };
312    // Constants for the multiply-with-carry steps
313    enum {
314        kKMul = 30345,
315        kJMul = 18000,
316    };
317
318    uint32_t fK;
319    uint32_t fJ;
320};
321
322#endif
323