Home | History | Annotate | Download | only in utils 
      1 
      2 /*
      3  * Copyright 2006 The Android Open Source Project
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 #ifndef SkRandom_DEFINED
     11 #define SkRandom_DEFINED
     12 
     13 #include "Sk64.h"
     14 #include "SkScalar.h"
     15 
     16 /** \class SkRandom
     17 
     18     Utility class that implements pseudo random 32bit numbers using a fast
     19     linear equation. Unlike rand(), this class holds its own seed (initially
     20     set to 0), so that multiple instances can be used with no side-effects.
     21 */
     22 class SkRandom {
     23 public:
     24     SkRandom() : fSeed(0) {}
     25     SkRandom(uint32_t seed) : fSeed(seed) {}
     26 
     27     /** Return the next pseudo random number as an unsigned 32bit value.
     28     */
     29     uint32_t nextU() { uint32_t r = fSeed * kMul + kAdd; fSeed = r; return r; }
     30 
     31     /** Return the next pseudo random number as a signed 32bit value.
     32     */
     33     int32_t nextS() { return (int32_t)this->nextU(); }
     34 
     35     /** Return the next pseudo random number as an unsigned 16bit value.
     36     */
     37     U16CPU nextU16() { return this->nextU() >> 16; }
     38 
     39     /** Return the next pseudo random number as a signed 16bit value.
     40     */
     41     S16CPU nextS16() { return this->nextS() >> 16; }
     42 
     43     /**
     44      *  Returns value [0...1) as a float
     45      */
     46     float nextF() {
     47         // const is 1 / (2^32 - 1)
     48         return (float)(this->nextU() * 2.32830644e-10);
     49     }
     50 
     51     /**
     52      *  Returns value [min...max) as a float
     53      */
     54     float nextRangeF(float min, float max) {
     55         return min + this->nextF() * (max - min);
     56     }
     57 
     58     /** Return the next pseudo random number, as an unsigned value of
     59         at most bitCount bits.
     60         @param bitCount The maximum number of bits to be returned
     61     */
     62     uint32_t nextBits(unsigned bitCount) {
     63         SkASSERT(bitCount > 0 && bitCount <= 32);
     64         return this->nextU() >> (32 - bitCount);
     65     }
     66 
     67     /** Return the next pseudo random unsigned number, mapped to lie within
     68         [min, max] inclusive.
     69     */
     70     uint32_t nextRangeU(uint32_t min, uint32_t max) {
     71         SkASSERT(min <= max);
     72         uint32_t range = max - min + 1;
     73         if (0 == range) {
     74             return this->nextU();
     75         } else {
     76             return min + this->nextU() % range;
     77         }
     78     }
     79 
     80     /** Return the next pseudo random unsigned number, mapped to lie within
     81         [0, count).
     82      */
     83     uint32_t nextULessThan(uint32_t count) {
     84         SkASSERT(count > 0);
     85         return this->nextRangeU(0, count - 1);
     86     }
     87 
     88     /** Return the next pseudo random number expressed as an unsigned SkFixed
     89         in the range [0..SK_Fixed1).
     90     */
     91     SkFixed nextUFixed1() { return this->nextU() >> 16; }
     92 
     93     /** Return the next pseudo random number expressed as a signed SkFixed
     94         in the range (-SK_Fixed1..SK_Fixed1).
     95     */
     96     SkFixed nextSFixed1() { return this->nextS() >> 15; }
     97 
     98     /** Return the next pseudo random number expressed as a SkScalar
     99         in the range [0..SK_Scalar1).
    100     */
    101     SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
    102 
    103     /** Return the next pseudo random number expressed as a SkScalar
    104         in the range [min..max).
    105     */
    106     SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
    107         return SkScalarMul(this->nextUScalar1(), (max - min)) + min;
    108     }
    109 
    110     /** Return the next pseudo random number expressed as a SkScalar
    111         in the range (-SK_Scalar1..SK_Scalar1).
    112     */
    113     SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
    114 
    115     /** Return the next pseudo random number as a bool.
    116     */
    117     bool nextBool() { return this->nextU() >= 0x80000000; }
    118 
    119     /** A biased version of nextBool().
    120      */
    121     bool nextBiasedBool(SkScalar fractionTrue) {
    122         SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
    123         return this->nextUScalar1() <= fractionTrue;
    124     }
    125 
    126     /** Return the next pseudo random number as a signed 64bit value.
    127     */
    128     void next64(Sk64* a) {
    129         SkASSERT(a);
    130         a->set(this->nextS(), this->nextU());
    131     }
    132 
    133     /**
    134      *  Return the current seed. This allows the caller to later reset to the
    135      *  same seed (using setSeed) so it can generate the same sequence.
    136      */
    137     int32_t getSeed() const { return fSeed; }
    138 
    139     /** Set the seed of the random object. The seed is initialized to 0 when the
    140         object is first created, and is updated each time the next pseudo random
    141         number is requested.
    142     */
    143     void setSeed(int32_t seed) { fSeed = (uint32_t)seed; }
    144 
    145 private:
    146     //  See "Numerical Recipes in C", 1992 page 284 for these constants
    147     enum {
    148         kMul = 1664525,
    149         kAdd = 1013904223
    150     };
    151     uint32_t fSeed;
    152 };
    153 
    154 /** \class SkMWCRandom
    155 
    156  Utility class that implements pseudo random 32bit numbers using Marsaglia's
    157  multiply-with-carry "mother of all" algorithm. Unlike rand(), this class holds
    158  its own state, so that multiple instances can be used with no side-effects.
    159 
    160  Has a large period and all bits are well-randomized.
    161  */
    162 class SkMWCRandom {
    163 public:
    164     SkMWCRandom() { init(0); }
    165     SkMWCRandom(uint32_t seed) { init(seed); }
    166     SkMWCRandom(const SkMWCRandom& rand) : fK(rand.fK), fJ(rand.fJ) {}
    167 
    168     SkMWCRandom& operator=(const SkMWCRandom& rand) {
    169         fK = rand.fK;
    170         fJ = rand.fJ;
    171 
    172         return *this;
    173     }
    174 
    175     /** Return the next pseudo random number as an unsigned 32bit value.
    176      */
    177     uint32_t nextU() {
    178         fK = kKMul*(fK & 0xffff) + (fK >> 16);
    179         fJ = kJMul*(fJ & 0xffff) + (fJ >> 16);
    180         return (((fK << 16) | (fK >> 16)) + fJ);
    181     }
    182 
    183     /** Return the next pseudo random number as a signed 32bit value.
    184      */
    185     int32_t nextS() { return (int32_t)this->nextU(); }
    186 
    187     /** Return the next pseudo random number as an unsigned 16bit value.
    188      */
    189     U16CPU nextU16() { return this->nextU() >> 16; }
    190 
    191     /** Return the next pseudo random number as a signed 16bit value.
    192      */
    193     S16CPU nextS16() { return this->nextS() >> 16; }
    194 
    195     /**
    196      *  Returns value [0...1) as an IEEE float
    197      */
    198     float nextF() {
    199         unsigned int floatint = 0x3f800000 | (this->nextU() >> 9);
    200         float f = *(float*)(&floatint) - 1.0f;
    201         return f;
    202     }
    203 
    204     /**
    205      *  Returns value [min...max) as a float
    206      */
    207     float nextRangeF(float min, float max) {
    208         return min + this->nextF() * (max - min);
    209     }
    210 
    211     /** Return the next pseudo random number, as an unsigned value of
    212      at most bitCount bits.
    213      @param bitCount The maximum number of bits to be returned
    214      */
    215     uint32_t nextBits(unsigned bitCount) {
    216         SkASSERT(bitCount > 0 && bitCount <= 32);
    217         return this->nextU() >> (32 - bitCount);
    218     }
    219 
    220     /** Return the next pseudo random unsigned number, mapped to lie within
    221      [min, max] inclusive.
    222      */
    223     uint32_t nextRangeU(uint32_t min, uint32_t max) {
    224         SkASSERT(min <= max);
    225         uint32_t range = max - min + 1;
    226         if (0 == range) {
    227             return this->nextU();
    228         } else {
    229             return min + this->nextU() % range;
    230         }
    231     }
    232 
    233     /** Return the next pseudo random unsigned number, mapped to lie within
    234      [0, count).
    235      */
    236     uint32_t nextULessThan(uint32_t count) {
    237         SkASSERT(count > 0);
    238         return this->nextRangeU(0, count - 1);
    239     }
    240 
    241     /** Return the next pseudo random number expressed as an unsigned SkFixed
    242      in the range [0..SK_Fixed1).
    243      */
    244     SkFixed nextUFixed1() { return this->nextU() >> 16; }
    245 
    246     /** Return the next pseudo random number expressed as a signed SkFixed
    247      in the range (-SK_Fixed1..SK_Fixed1).
    248      */
    249     SkFixed nextSFixed1() { return this->nextS() >> 15; }
    250 
    251     /** Return the next pseudo random number expressed as a SkScalar
    252      in the range [0..SK_Scalar1).
    253      */
    254     SkScalar nextUScalar1() { return SkFixedToScalar(this->nextUFixed1()); }
    255 
    256     /** Return the next pseudo random number expressed as a SkScalar
    257      in the range [min..max).
    258      */
    259     SkScalar nextRangeScalar(SkScalar min, SkScalar max) {
    260         return SkScalarMul(this->nextUScalar1(), (max - min)) + min;
    261     }
    262 
    263     /** Return the next pseudo random number expressed as a SkScalar
    264      in the range (-SK_Scalar1..SK_Scalar1).
    265      */
    266     SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
    267 
    268     /** Return the next pseudo random number as a bool.
    269      */
    270     bool nextBool() { return this->nextU() >= 0x80000000; }
    271 
    272     /** A biased version of nextBool().
    273      */
    274     bool nextBiasedBool(SkScalar fractionTrue) {
    275         SkASSERT(fractionTrue >= 0 && fractionTrue <= SK_Scalar1);
    276         return this->nextUScalar1() <= fractionTrue;
    277     }
    278 
    279     /** Return the next pseudo random number as a signed 64bit value.
    280      */
    281     void next64(Sk64* a) {
    282         SkASSERT(a);
    283         a->set(this->nextS(), this->nextU());
    284     }
    285 
    286     /** Reset the random object.
    287      */
    288     void setSeed(uint32_t seed) { init(seed); }
    289 
    290 private:
    291     // Initialize state variables with LCG.
    292     // We must ensure that both J and K are non-zero, otherwise the
    293     // multiply-with-carry step will forevermore return zero.
    294     void init(uint32_t seed) {
    295         fK = NextLCG(seed);
    296         if (0 == fK) {
    297             fK = NextLCG(fK);
    298         }
    299         fJ = NextLCG(fK);
    300         if (0 == fJ) {
    301             fJ = NextLCG(fJ);
    302         }
    303         SkASSERT(0 != fK && 0 != fJ);
    304     }
    305     static uint32_t NextLCG(uint32_t seed) { return kMul*seed + kAdd; }
    306 
    307     //  See "Numerical Recipes in C", 1992 page 284 for these constants
    308     //  For the LCG that sets the initial state from a seed
    309     enum {
    310         kMul = 1664525,
    311         kAdd = 1013904223
    312     };
    313     // Constants for the multiply-with-carry steps
    314     enum {
    315         kKMul = 30345,
    316         kJMul = 18000,
    317     };
    318 
    319     uint32_t fK;
    320     uint32_t fJ;
    321 };
    322 
    323 #endif
    324