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