SkRandom.h 4.8 KB

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