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