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  */
21 class SkRandom {
22 public:
SkRandom()23     SkRandom() { init(0); }
SkRandom(uint32_t seed)24     SkRandom(uint32_t seed) { init(seed); }
SkRandom(const SkRandom & rand)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      */
nextU()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      */
nextS()44     int32_t nextS() { return (int32_t)this->nextU(); }
45 
46     /** Return the next pseudo random number as an unsigned 16bit value.
47      */
nextU16()48     U16CPU nextU16() { return this->nextU() >> 16; }
49 
50     /** Return the next pseudo random number as a signed 16bit value.
51      */
nextS16()52     S16CPU nextS16() { return this->nextS() >> 16; }
53 
54     /**
55      *  Returns value [0...1) as an IEEE float
56      */
nextF()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      */
nextRangeF(float min,float max)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      */
nextBits(unsigned bitCount)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      */
nextRangeU(uint32_t min,uint32_t max)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      */
nextULessThan(uint32_t count)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      */
nextUFixed1()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      */
nextSFixed1()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      */
nextUScalar1()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      */
nextRangeScalar(SkScalar min,SkScalar max)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      */
nextSScalar1()125     SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
126 
127     /** Return the next pseudo random number as a bool.
128      */
nextBool()129     bool nextBool() { return this->nextU() >= 0x80000000; }
130 
131     /** A biased version of nextBool().
132      */
nextBiasedBool(SkScalar fractionTrue)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      */
next64()141     int64_t next64() {
142         int64_t hi = this->nextS();
143         return (hi << 32) | this->nextU();
144     }
145 
146     /** Reset the random object.
147      */
setSeed(uint32_t seed)148     void setSeed(uint32_t seed) { init(seed); }
149 
150 private:
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.
init(uint32_t seed)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     }
NextLCG(uint32_t seed)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