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