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