1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/utils/SkRandom.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,322 @@
1.4 +/*
1.5 + * Copyright 2006 The Android Open Source Project
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef SkRandom_DEFINED
1.12 +#define SkRandom_DEFINED
1.13 +
1.14 +#include "SkScalar.h"
1.15 +
1.16 +/** \class SkLCGRandom
1.17 +
1.18 + Utility class that implements pseudo random 32bit numbers using a fast
1.19 + linear equation. Unlike rand(), this class holds its own seed (initially
1.20 + set to 0), so that multiple instances can be used with no side-effects.
1.21 +*/
1.22 +class SkLCGRandom {
1.23 +public:
1.24 + SkLCGRandom() : fSeed(0) {}
1.25 + SkLCGRandom(uint32_t seed) : fSeed(seed) {}
1.26 +
1.27 + /** Return the next pseudo random number as an unsigned 32bit value.
1.28 + */
1.29 + uint32_t nextU() { uint32_t r = fSeed * kMul + kAdd; fSeed = r; return r; }
1.30 +
1.31 + /** Return the next pseudo random number as a signed 32bit value.
1.32 + */
1.33 + int32_t nextS() { return (int32_t)this->nextU(); }
1.34 +
1.35 + /** Return the next pseudo random number as an unsigned 16bit value.
1.36 + */
1.37 + U16CPU nextU16() { return this->nextU() >> 16; }
1.38 +
1.39 + /** Return the next pseudo random number as a signed 16bit value.
1.40 + */
1.41 + S16CPU nextS16() { return this->nextS() >> 16; }
1.42 +
1.43 + /**
1.44 + * Returns value [0...1) as a float
1.45 + */
1.46 + float nextF() {
1.47 + // const is 1 / (2^32 - 1)
1.48 + return (float)(this->nextU() * 2.32830644e-10);
1.49 + }
1.50 +
1.51 + /**
1.52 + * Returns value [min...max) as a float
1.53 + */
1.54 + float nextRangeF(float min, float max) {
1.55 + return min + this->nextF() * (max - min);
1.56 + }
1.57 +
1.58 + /** Return the next pseudo random number, as an unsigned value of
1.59 + at most bitCount bits.
1.60 + @param bitCount The maximum number of bits to be returned
1.61 + */
1.62 + uint32_t nextBits(unsigned bitCount) {
1.63 + SkASSERT(bitCount > 0 && bitCount <= 32);
1.64 + return this->nextU() >> (32 - bitCount);
1.65 + }
1.66 +
1.67 + /** Return the next pseudo random unsigned number, mapped to lie within
1.68 + [min, max] inclusive.
1.69 + */
1.70 + uint32_t nextRangeU(uint32_t min, uint32_t max) {
1.71 + SkASSERT(min <= max);
1.72 + uint32_t range = max - min + 1;
1.73 + if (0 == range) {
1.74 + return this->nextU();
1.75 + } else {
1.76 + return min + this->nextU() % range;
1.77 + }
1.78 + }
1.79 +
1.80 + /** Return the next pseudo random unsigned number, mapped to lie within
1.81 + [0, count).
1.82 + */
1.83 + uint32_t nextULessThan(uint32_t count) {
1.84 + SkASSERT(count > 0);
1.85 + return this->nextRangeU(0, count - 1);
1.86 + }
1.87 +
1.88 + /** Return the next pseudo random number expressed as an unsigned SkFixed
1.89 + in the range [0..SK_Fixed1).
1.90 + */
1.91 + SkFixed nextUFixed1() { return this->nextU() >> 16; }
1.92 +
1.93 + /** Return the next pseudo random number expressed as a signed SkFixed
1.94 + in the range (-SK_Fixed1..SK_Fixed1).
1.95 + */
1.96 + SkFixed nextSFixed1() { return this->nextS() >> 15; }
1.97 +
1.98 + /** Return the next pseudo random number expressed as a SkScalar
1.99 + in the range [0..SK_Scalar1).
1.100 + */
1.101 + SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
1.102 +
1.103 + /** Return the next pseudo random number expressed as a SkScalar
1.104 + in the range [min..max).
1.105 + */
1.106 + SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
1.107 + return this->nextUScalar1() * (max - min) + min;
1.108 + }
1.109 +
1.110 + /** Return the next pseudo random number expressed as a SkScalar
1.111 + in the range (-SK_Scalar1..SK_Scalar1).
1.112 + */
1.113 + SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
1.114 +
1.115 + /** Return the next pseudo random number as a bool.
1.116 + */
1.117 + bool nextBool() { return this->nextU() >= 0x80000000; }
1.118 +
1.119 + /** A biased version of nextBool().
1.120 + */
1.121 + bool nextBiasedBool(SkScalar fractionTrue) {
1.122 + SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
1.123 + return this->nextUScalar1() <= fractionTrue;
1.124 + }
1.125 +
1.126 + /**
1.127 + * Return the next pseudo random number as a signed 64bit value.
1.128 + */
1.129 + int64_t next64() {
1.130 + int64_t hi = this->nextS();
1.131 + return (hi << 32) | this->nextU();
1.132 + }
1.133 +
1.134 + /**
1.135 + * Return the current seed. This allows the caller to later reset to the
1.136 + * same seed (using setSeed) so it can generate the same sequence.
1.137 + */
1.138 + int32_t getSeed() const { return fSeed; }
1.139 +
1.140 + /** Set the seed of the random object. The seed is initialized to 0 when the
1.141 + object is first created, and is updated each time the next pseudo random
1.142 + number is requested.
1.143 + */
1.144 + void setSeed(int32_t seed) { fSeed = (uint32_t)seed; }
1.145 +
1.146 +private:
1.147 + // See "Numerical Recipes in C", 1992 page 284 for these constants
1.148 + enum {
1.149 + kMul = 1664525,
1.150 + kAdd = 1013904223
1.151 + };
1.152 + uint32_t fSeed;
1.153 +};
1.154 +
1.155 +/** \class SkRandom
1.156 +
1.157 + Utility class that implements pseudo random 32bit numbers using Marsaglia's
1.158 + multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds
1.159 + its own state, so that multiple instances can be used with no side-effects.
1.160 +
1.161 + Has a large period and all bits are well-randomized.
1.162 + */
1.163 +class SkRandom {
1.164 +public:
1.165 + SkRandom() { init(0); }
1.166 + SkRandom(uint32_t seed) { init(seed); }
1.167 + SkRandom(const SkRandom& rand) : fK(rand.fK), fJ(rand.fJ) {}
1.168 +
1.169 + SkRandom& operator=(const SkRandom& rand) {
1.170 + fK = rand.fK;
1.171 + fJ = rand.fJ;
1.172 +
1.173 + return *this;
1.174 + }
1.175 +
1.176 + /** Return the next pseudo random number as an unsigned 32bit value.
1.177 + */
1.178 + uint32_t nextU() {
1.179 + fK = kKMul*(fK & 0xffff) + (fK >> 16);
1.180 + fJ = kJMul*(fJ & 0xffff) + (fJ >> 16);
1.181 + return (((fK << 16) | (fK >> 16)) + fJ);
1.182 + }
1.183 +
1.184 + /** Return the next pseudo random number as a signed 32bit value.
1.185 + */
1.186 + int32_t nextS() { return (int32_t)this->nextU(); }
1.187 +
1.188 + /** Return the next pseudo random number as an unsigned 16bit value.
1.189 + */
1.190 + U16CPU nextU16() { return this->nextU() >> 16; }
1.191 +
1.192 + /** Return the next pseudo random number as a signed 16bit value.
1.193 + */
1.194 + S16CPU nextS16() { return this->nextS() >> 16; }
1.195 +
1.196 + /**
1.197 + * Returns value [0...1) as an IEEE float
1.198 + */
1.199 + float nextF() {
1.200 + unsigned int floatint = 0x3f800000 | (this->nextU() >> 9);
1.201 + float f = SkBits2Float(floatint) - 1.0f;
1.202 + return f;
1.203 + }
1.204 +
1.205 + /**
1.206 + * Returns value [min...max) as a float
1.207 + */
1.208 + float nextRangeF(float min, float max) {
1.209 + return min + this->nextF() * (max - min);
1.210 + }
1.211 +
1.212 + /** Return the next pseudo random number, as an unsigned value of
1.213 + at most bitCount bits.
1.214 + @param bitCount The maximum number of bits to be returned
1.215 + */
1.216 + uint32_t nextBits(unsigned bitCount) {
1.217 + SkASSERT(bitCount > 0 && bitCount <= 32);
1.218 + return this->nextU() >> (32 - bitCount);
1.219 + }
1.220 +
1.221 + /** Return the next pseudo random unsigned number, mapped to lie within
1.222 + [min, max] inclusive.
1.223 + */
1.224 + uint32_t nextRangeU(uint32_t min, uint32_t max) {
1.225 + SkASSERT(min <= max);
1.226 + uint32_t range = max - min + 1;
1.227 + if (0 == range) {
1.228 + return this->nextU();
1.229 + } else {
1.230 + return min + this->nextU() % range;
1.231 + }
1.232 + }
1.233 +
1.234 + /** Return the next pseudo random unsigned number, mapped to lie within
1.235 + [0, count).
1.236 + */
1.237 + uint32_t nextULessThan(uint32_t count) {
1.238 + SkASSERT(count > 0);
1.239 + return this->nextRangeU(0, count - 1);
1.240 + }
1.241 +
1.242 + /** Return the next pseudo random number expressed as an unsigned SkFixed
1.243 + in the range [0..SK_Fixed1).
1.244 + */
1.245 + SkFixed nextUFixed1() { return this->nextU() >> 16; }
1.246 +
1.247 + /** Return the next pseudo random number expressed as a signed SkFixed
1.248 + in the range (-SK_Fixed1..SK_Fixed1).
1.249 + */
1.250 + SkFixed nextSFixed1() { return this->nextS() >> 15; }
1.251 +
1.252 + /** Return the next pseudo random number expressed as a SkScalar
1.253 + in the range [0..SK_Scalar1).
1.254 + */
1.255 + SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
1.256 +
1.257 + /** Return the next pseudo random number expressed as a SkScalar
1.258 + in the range [min..max).
1.259 + */
1.260 + SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
1.261 + return this->nextUScalar1() * (max - min) + min;
1.262 + }
1.263 +
1.264 + /** Return the next pseudo random number expressed as a SkScalar
1.265 + in the range (-SK_Scalar1..SK_Scalar1).
1.266 + */
1.267 + SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
1.268 +
1.269 + /** Return the next pseudo random number as a bool.
1.270 + */
1.271 + bool nextBool() { return this->nextU() >= 0x80000000; }
1.272 +
1.273 + /** A biased version of nextBool().
1.274 + */
1.275 + bool nextBiasedBool(SkScalar fractionTrue) {
1.276 + SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
1.277 + return this->nextUScalar1() <= fractionTrue;
1.278 + }
1.279 +
1.280 + /**
1.281 + * Return the next pseudo random number as a signed 64bit value.
1.282 + */
1.283 + int64_t next64() {
1.284 + int64_t hi = this->nextS();
1.285 + return (hi << 32) | this->nextU();
1.286 + }
1.287 +
1.288 + /** Reset the random object.
1.289 + */
1.290 + void setSeed(uint32_t seed) { init(seed); }
1.291 +
1.292 +private:
1.293 + // Initialize state variables with LCG.
1.294 + // We must ensure that both J and K are non-zero, otherwise the
1.295 + // multiply-with-carry step will forevermore return zero.
1.296 + void init(uint32_t seed) {
1.297 + fK = NextLCG(seed);
1.298 + if (0 == fK) {
1.299 + fK = NextLCG(fK);
1.300 + }
1.301 + fJ = NextLCG(fK);
1.302 + if (0 == fJ) {
1.303 + fJ = NextLCG(fJ);
1.304 + }
1.305 + SkASSERT(0 != fK && 0 != fJ);
1.306 + }
1.307 + static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; }
1.308 +
1.309 + // See "Numerical Recipes in C", 1992 page 284 for these constants
1.310 + // For the LCG that sets the initial state from a seed
1.311 + enum {
1.312 + kMul = 1664525,
1.313 + kAdd = 1013904223
1.314 + };
1.315 + // Constants for the multiply-with-carry steps
1.316 + enum {
1.317 + kKMul = 30345,
1.318 + kJMul = 18000,
1.319 + };
1.320 +
1.321 + uint32_t fK;
1.322 + uint32_t fJ;
1.323 +};
1.324 +
1.325 +#endif
