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 SkRandom
14
15 Utility class that implements pseudo random 32bit numbers using Marsaglia's
16 multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds
17 its own state, so that multiple instances can be used with no side-effects.
18
19 Has a large period and all bits are well-randomized.
20 */
21class SkRandom {
22public:
23    SkRandom() { init(0); }
24    SkRandom(uint32_t seed) { init(seed); }
25    SkRandom(const SkRandom& rand) : fK(rand.fK), fJ(rand.fJ) {}
26
27    SkRandom& operator=(const SkRandom& rand) {
28        fK = rand.fK;
29        fJ = rand.fJ;
30
31        return *this;
32    }
33
34    /** Return the next pseudo random number as an unsigned 32bit value.
35     */
36    uint32_t nextU() {
37        fK = kKMul*(fK & 0xffff) + (fK >> 16);
38        fJ = kJMul*(fJ & 0xffff) + (fJ >> 16);
39        return (((fK << 16) | (fK >> 16)) + fJ);
40    }
41
42    /** Return the next pseudo random number as a signed 32bit value.
43     */
44    int32_t nextS() { return (int32_t)this->nextU(); }
45
46    /** Return the next pseudo random number as an unsigned 16bit value.
47     */
48    U16CPU nextU16() { return this->nextU() >> 16; }
49
50    /** Return the next pseudo random number as a signed 16bit value.
51     */
52    S16CPU nextS16() { return this->nextS() >> 16; }
53
54    /**
55     *  Returns value [0...1) as an IEEE float
56     */
57    float nextF() {
58        unsigned int floatint = 0x3f800000 | (this->nextU() >> 9);
59        float f = SkBits2Float(floatint) - 1.0f;
60        return f;
61    }
62
63    /**
64     *  Returns value [min...max) as a float
65     */
66    float nextRangeF(float min, float max) {
67        return min + this->nextF() * (max - min);
68    }
69
70    /** Return the next pseudo random number, as an unsigned value of
71     at most bitCount bits.
72     @param bitCount The maximum number of bits to be returned
73     */
74    uint32_t nextBits(unsigned bitCount) {
75        SkASSERT(bitCount > 0 && bitCount <= 32);
76        return this->nextU() >> (32 - bitCount);
77    }
78
79    /** Return the next pseudo random unsigned number, mapped to lie within
80     [min, max] inclusive.
81     */
82    uint32_t nextRangeU(uint32_t min, uint32_t max) {
83        SkASSERT(min <= max);
84        uint32_t range = max - min + 1;
85        if (0 == range) {
86            return this->nextU();
87        } else {
88            return min + this->nextU() % range;
89        }
90    }
91
92    /** Return the next pseudo random unsigned number, mapped to lie within
93     [0, count).
94     */
95    uint32_t nextULessThan(uint32_t count) {
96        SkASSERT(count > 0);
97        return this->nextRangeU(0, count - 1);
98    }
99
100    /** Return the next pseudo random number expressed as an unsigned SkFixed
101     in the range [0..SK_Fixed1).
102     */
103    SkFixed nextUFixed1() { return this->nextU() >> 16; }
104
105    /** Return the next pseudo random number expressed as a signed SkFixed
106     in the range (-SK_Fixed1..SK_Fixed1).
107     */
108    SkFixed nextSFixed1() { return this->nextS() >> 15; }
109
110    /** Return the next pseudo random number expressed as a SkScalar
111     in the range [0..SK_Scalar1).
112     */
113    SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
114
115    /** Return the next pseudo random number expressed as a SkScalar
116     in the range [min..max).
117     */
118    SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
119        return this->nextUScalar1() * (max - min) + min;
120    }
121
122    /** Return the next pseudo random number expressed as a SkScalar
123     in the range (-SK_Scalar1..SK_Scalar1).
124     */
125    SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
126
127    /** Return the next pseudo random number as a bool.
128     */
129    bool nextBool() { return this->nextU() >= 0x80000000; }
130
131    /** A biased version of nextBool().
132     */
133    bool nextBiasedBool(SkScalar fractionTrue) {
134        SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
135        return this->nextUScalar1() <= fractionTrue;
136    }
137
138    /**
139     *  Return the next pseudo random number as a signed 64bit value.
140     */
141    int64_t next64() {
142        int64_t hi = this->nextS();
143        return (hi << 32) | this->nextU();
144    }
145
146    /** Reset the random object.
147     */
148    void setSeed(uint32_t seed) { init(seed); }
149
150private:
151    // Initialize state variables with LCG.
152    // We must ensure that both J and K are non-zero, otherwise the
153    // multiply-with-carry step will forevermore return zero.
154    void init(uint32_t seed) {
155        fK = NextLCG(seed);
156        if (0 == fK) {
157            fK = NextLCG(fK);
158        }
159        fJ = NextLCG(fK);
160        if (0 == fJ) {
161            fJ = NextLCG(fJ);
162        }
163        SkASSERT(0 != fK && 0 != fJ);
164    }
165    static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; }
166
167    //  See "Numerical Recipes in C", 1992 page 284 for these constants
168    //  For the LCG that sets the initial state from a seed
169    enum {
170        kMul = 1664525,
171        kAdd = 1013904223
172    };
173    // Constants for the multiply-with-carry steps
174    enum {
175        kKMul = 30345,
176        kJMul = 18000,
177    };
178
179    uint32_t fK;
180    uint32_t fJ;
181};
182
183#endif
184