michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef SkRandom_DEFINED
michael@0: #define SkRandom_DEFINED
michael@0: 
michael@0: #include "SkScalar.h"
michael@0: 
michael@0: /** \class SkLCGRandom
michael@0: 
michael@0:     Utility class that implements pseudo random 32bit numbers using a fast
michael@0:     linear equation. Unlike rand(), this class holds its own seed (initially
michael@0:     set to 0), so that multiple instances can be used with no side-effects.
michael@0: */
michael@0: class SkLCGRandom {
michael@0: public:
michael@0:     SkLCGRandom() : fSeed(0) {}
michael@0:     SkLCGRandom(uint32_t seed) : fSeed(seed) {}
michael@0: 
michael@0:     /** Return the next pseudo random number as an unsigned 32bit value.
michael@0:     */
michael@0:     uint32_t nextU() { uint32_t r = fSeed * kMul + kAdd; fSeed = r; return r; }
michael@0: 
michael@0:     /** Return the next pseudo random number as a signed 32bit value.
michael@0:     */
michael@0:     int32_t nextS() { return (int32_t)this->nextU(); }
michael@0: 
michael@0:     /** Return the next pseudo random number as an unsigned 16bit value.
michael@0:     */
michael@0:     U16CPU nextU16() { return this->nextU() >> 16; }
michael@0: 
michael@0:     /** Return the next pseudo random number as a signed 16bit value.
michael@0:     */
michael@0:     S16CPU nextS16() { return this->nextS() >> 16; }
michael@0: 
michael@0:     /**
michael@0:      *  Returns value [0...1) as a float
michael@0:      */
michael@0:     float nextF() {
michael@0:         // const is 1 / (2^32 - 1)
michael@0:         return (float)(this->nextU() * 2.32830644e-10);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Returns value [min...max) as a float
michael@0:      */
michael@0:     float nextRangeF(float min, float max) {
michael@0:         return min + this->nextF() * (max - min);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number, as an unsigned value of
michael@0:         at most bitCount bits.
michael@0:         @param bitCount The maximum number of bits to be returned
michael@0:     */
michael@0:     uint32_t nextBits(unsigned bitCount) {
michael@0:         SkASSERT(bitCount > 0 && bitCount <= 32);
michael@0:         return this->nextU() >> (32 - bitCount);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random unsigned number, mapped to lie within
michael@0:         [min, max] inclusive.
michael@0:     */
michael@0:     uint32_t nextRangeU(uint32_t min, uint32_t max) {
michael@0:         SkASSERT(min <= max);
michael@0:         uint32_t range = max - min + 1;
michael@0:         if (0 == range) {
michael@0:             return this->nextU();
michael@0:         } else {
michael@0:             return min + this->nextU() % range;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random unsigned number, mapped to lie within
michael@0:         [0, count).
michael@0:      */
michael@0:     uint32_t nextULessThan(uint32_t count) {
michael@0:         SkASSERT(count > 0);
michael@0:         return this->nextRangeU(0, count - 1);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as an unsigned SkFixed
michael@0:         in the range [0..SK_Fixed1).
michael@0:     */
michael@0:     SkFixed nextUFixed1() { return this->nextU() >> 16; }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a signed SkFixed
michael@0:         in the range (-SK_Fixed1..SK_Fixed1).
michael@0:     */
michael@0:     SkFixed nextSFixed1() { return this->nextS() >> 15; }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a SkScalar
michael@0:         in the range [0..SK_Scalar1).
michael@0:     */
michael@0:     SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a SkScalar
michael@0:         in the range [min..max).
michael@0:     */
michael@0:     SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
michael@0:         return this->nextUScalar1() * (max - min) + min;
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a SkScalar
michael@0:         in the range (-SK_Scalar1..SK_Scalar1).
michael@0:     */
michael@0:     SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
michael@0: 
michael@0:     /** Return the next pseudo random number as a bool.
michael@0:     */
michael@0:     bool nextBool() { return this->nextU() >= 0x80000000; }
michael@0: 
michael@0:     /** A biased version of nextBool().
michael@0:      */
michael@0:     bool nextBiasedBool(SkScalar fractionTrue) {
michael@0:         SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
michael@0:         return this->nextUScalar1() <= fractionTrue;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Return the next pseudo random number as a signed 64bit value.
michael@0:      */
michael@0:     int64_t next64() {
michael@0:         int64_t hi = this->nextS();
michael@0:         return (hi << 32) | this->nextU();
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Return the current seed. This allows the caller to later reset to the
michael@0:      *  same seed (using setSeed) so it can generate the same sequence.
michael@0:      */
michael@0:     int32_t getSeed() const { return fSeed; }
michael@0: 
michael@0:     /** Set the seed of the random object. The seed is initialized to 0 when the
michael@0:         object is first created, and is updated each time the next pseudo random
michael@0:         number is requested.
michael@0:     */
michael@0:     void setSeed(int32_t seed) { fSeed = (uint32_t)seed; }
michael@0: 
michael@0: private:
michael@0:     //  See "Numerical Recipes in C", 1992 page 284 for these constants
michael@0:     enum {
michael@0:         kMul = 1664525,
michael@0:         kAdd = 1013904223
michael@0:     };
michael@0:     uint32_t fSeed;
michael@0: };
michael@0: 
michael@0: /** \class SkRandom
michael@0: 
michael@0:  Utility class that implements pseudo random 32bit numbers using Marsaglia's
michael@0:  multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds
michael@0:  its own state, so that multiple instances can be used with no side-effects.
michael@0: 
michael@0:  Has a large period and all bits are well-randomized.
michael@0:  */
michael@0: class SkRandom {
michael@0: public:
michael@0:     SkRandom() { init(0); }
michael@0:     SkRandom(uint32_t seed) { init(seed); }
michael@0:     SkRandom(const SkRandom& rand) : fK(rand.fK), fJ(rand.fJ) {}
michael@0: 
michael@0:     SkRandom& operator=(const SkRandom& rand) {
michael@0:         fK = rand.fK;
michael@0:         fJ = rand.fJ;
michael@0: 
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number as an unsigned 32bit value.
michael@0:      */
michael@0:     uint32_t nextU() {
michael@0:         fK = kKMul*(fK & 0xffff) + (fK >> 16);
michael@0:         fJ = kJMul*(fJ & 0xffff) + (fJ >> 16);
michael@0:         return (((fK << 16) | (fK >> 16)) + fJ);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number as a signed 32bit value.
michael@0:      */
michael@0:     int32_t nextS() { return (int32_t)this->nextU(); }
michael@0: 
michael@0:     /** Return the next pseudo random number as an unsigned 16bit value.
michael@0:      */
michael@0:     U16CPU nextU16() { return this->nextU() >> 16; }
michael@0: 
michael@0:     /** Return the next pseudo random number as a signed 16bit value.
michael@0:      */
michael@0:     S16CPU nextS16() { return this->nextS() >> 16; }
michael@0: 
michael@0:     /**
michael@0:      *  Returns value [0...1) as an IEEE float
michael@0:      */
michael@0:     float nextF() {
michael@0:         unsigned int floatint = 0x3f800000 | (this->nextU() >> 9);
michael@0:         float f = SkBits2Float(floatint) - 1.0f;
michael@0:         return f;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Returns value [min...max) as a float
michael@0:      */
michael@0:     float nextRangeF(float min, float max) {
michael@0:         return min + this->nextF() * (max - min);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number, as an unsigned value of
michael@0:      at most bitCount bits.
michael@0:      @param bitCount The maximum number of bits to be returned
michael@0:      */
michael@0:     uint32_t nextBits(unsigned bitCount) {
michael@0:         SkASSERT(bitCount > 0 && bitCount <= 32);
michael@0:         return this->nextU() >> (32 - bitCount);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random unsigned number, mapped to lie within
michael@0:      [min, max] inclusive.
michael@0:      */
michael@0:     uint32_t nextRangeU(uint32_t min, uint32_t max) {
michael@0:         SkASSERT(min <= max);
michael@0:         uint32_t range = max - min + 1;
michael@0:         if (0 == range) {
michael@0:             return this->nextU();
michael@0:         } else {
michael@0:             return min + this->nextU() % range;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random unsigned number, mapped to lie within
michael@0:      [0, count).
michael@0:      */
michael@0:     uint32_t nextULessThan(uint32_t count) {
michael@0:         SkASSERT(count > 0);
michael@0:         return this->nextRangeU(0, count - 1);
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as an unsigned SkFixed
michael@0:      in the range [0..SK_Fixed1).
michael@0:      */
michael@0:     SkFixed nextUFixed1() { return this->nextU() >> 16; }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a signed SkFixed
michael@0:      in the range (-SK_Fixed1..SK_Fixed1).
michael@0:      */
michael@0:     SkFixed nextSFixed1() { return this->nextS() >> 15; }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a SkScalar
michael@0:      in the range [0..SK_Scalar1).
michael@0:      */
michael@0:     SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a SkScalar
michael@0:      in the range [min..max).
michael@0:      */
michael@0:     SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
michael@0:         return this->nextUScalar1() * (max - min) + min;
michael@0:     }
michael@0: 
michael@0:     /** Return the next pseudo random number expressed as a SkScalar
michael@0:      in the range (-SK_Scalar1..SK_Scalar1).
michael@0:      */
michael@0:     SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
michael@0: 
michael@0:     /** Return the next pseudo random number as a bool.
michael@0:      */
michael@0:     bool nextBool() { return this->nextU() >= 0x80000000; }
michael@0: 
michael@0:     /** A biased version of nextBool().
michael@0:      */
michael@0:     bool nextBiasedBool(SkScalar fractionTrue) {
michael@0:         SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
michael@0:         return this->nextUScalar1() <= fractionTrue;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Return the next pseudo random number as a signed 64bit value.
michael@0:      */
michael@0:     int64_t next64() {
michael@0:         int64_t hi = this->nextS();
michael@0:         return (hi << 32) | this->nextU();
michael@0:     }
michael@0: 
michael@0:     /** Reset the random object.
michael@0:      */
michael@0:     void setSeed(uint32_t seed) { init(seed); }
michael@0: 
michael@0: private:
michael@0:     // Initialize state variables with LCG.
michael@0:     // We must ensure that both J and K are non-zero, otherwise the
michael@0:     // multiply-with-carry step will forevermore return zero.
michael@0:     void init(uint32_t seed) {
michael@0:         fK = NextLCG(seed);
michael@0:         if (0 == fK) {
michael@0:             fK = NextLCG(fK);
michael@0:         }
michael@0:         fJ = NextLCG(fK);
michael@0:         if (0 == fJ) {
michael@0:             fJ = NextLCG(fJ);
michael@0:         }
michael@0:         SkASSERT(0 != fK && 0 != fJ);
michael@0:     }
michael@0:     static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; }
michael@0: 
michael@0:     //  See "Numerical Recipes in C", 1992 page 284 for these constants
michael@0:     //  For the LCG that sets the initial state from a seed
michael@0:     enum {
michael@0:         kMul = 1664525,
michael@0:         kAdd = 1013904223
michael@0:     };
michael@0:     // Constants for the multiply-with-carry steps
michael@0:     enum {
michael@0:         kKMul = 30345,
michael@0:         kJMul = 18000,
michael@0:     };
michael@0: 
michael@0:     uint32_t fK;
michael@0:     uint32_t fJ;
michael@0: };
michael@0: 
michael@0: #endif