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