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