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