Home | History | Annotate | Download | only in utils 
      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:
     23     SkRandom() { init(0); }
     24     SkRandom(uint32_t seed) { init(seed); }
     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      */
     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      */
     44     int32_t nextS() { return (int32_t)this->nextU(); }
     45 
     46     /** Return the next pseudo random number as an unsigned 16bit value.
     47      */
     48     U16CPU nextU16() { return this->nextU() >> 16; }
     49 
     50     /** Return the next pseudo random number as a signed 16bit value.
     51      */
     52     S16CPU nextS16() { return this->nextS() >> 16; }
     53 
     54     /**
     55      *  Returns value [0...1) as an IEEE float
     56      */
     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      */
     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      */
     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      */
     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      */
     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      */
    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      */
    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      */
    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      */
    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      */
    125     SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
    126 
    127     /** Return the next pseudo random number as a bool.
    128      */
    129     bool nextBool() { return this->nextU() >= 0x80000000; }
    130 
    131     /** A biased version of nextBool().
    132      */
    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      */
    141     int64_t next64() {
    142         int64_t hi = this->nextS();
    143         return (hi << 32) | this->nextU();
    144     }
    145 
    146     /** Reset the random object.
    147      */
    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.
    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     }
    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