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