1 | /* |
---|---|

2 | * Copyright (C) 2009, 2015 Apple Inc. All rights reserved. |

3 | * |

4 | * Redistribution and use in source and binary forms, with or without |

5 | * modification, are permitted provided that the following conditions |

6 | * are met: |

7 | * 1. Redistributions of source code must retain the above copyright |

8 | * notice, this list of conditions and the following disclaimer. |

9 | * 2. Redistributions in binary form must reproduce the above copyright |

10 | * notice, this list of conditions and the following disclaimer in the |

11 | * documentation and/or other materials provided with the distribution. |

12 | * |

13 | * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |

14 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |

15 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |

16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |

17 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |

18 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |

19 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |

20 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |

21 | * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |

22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |

23 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |

24 | * |

25 | * Vigna, Sebastiano (2014). "Further scramblings of Marsaglia's xorshift |

26 | * generators". arXiv:1404.0390 (http://arxiv.org/abs/1404.0390) |

27 | * |

28 | * See also https://en.wikipedia.org/wiki/Xorshift. |

29 | */ |

30 | |

31 | #ifndef WeakRandom_h |

32 | #define WeakRandom_h |

33 | |

34 | #include <limits.h> |

35 | #include <wtf/CryptographicallyRandomNumber.h> |

36 | #include <wtf/StdLibExtras.h> |

37 | |

38 | namespace WTF { |

39 | |

40 | // The code used to generate random numbers are inlined manually in JIT code. |

41 | // So it needs to stay in sync with the JIT one. |

42 | class WeakRandom { |

43 | public: |

44 | WeakRandom(unsigned seed = cryptographicallyRandomNumber()) |

45 | { |

46 | setSeed(seed); |

47 | } |

48 | |

49 | void setSeed(unsigned seed) |

50 | { |

51 | m_seed = seed; |

52 | |

53 | // A zero seed would cause an infinite series of zeroes. |

54 | if (!seed) |

55 | seed = 1; |

56 | |

57 | m_low = seed; |

58 | m_high = seed; |

59 | advance(); |

60 | } |

61 | |

62 | unsigned seed() const { return m_seed; } |

63 | |

64 | double get() |

65 | { |

66 | uint64_t value = advance() & ((1ULL << 53) - 1); |

67 | return value * (1.0 / (1ULL << 53)); |

68 | } |

69 | |

70 | unsigned getUint32() |

71 | { |

72 | return static_cast<unsigned>(advance()); |

73 | } |

74 | |

75 | unsigned getUint32(unsigned limit) |

76 | { |

77 | if (limit <= 1) |

78 | return 0; |

79 | uint64_t cutoff = (static_cast<uint64_t>(std::numeric_limits<unsigned>::max()) + 1) / limit * limit; |

80 | for (;;) { |

81 | uint64_t value = getUint32(); |

82 | if (value >= cutoff) |

83 | continue; |

84 | return value % limit; |

85 | } |

86 | } |

87 | |

88 | static unsigned lowOffset() { return OBJECT_OFFSETOF(WeakRandom, m_low); } |

89 | static unsigned highOffset() { return OBJECT_OFFSETOF(WeakRandom, m_high); } |

90 | |

91 | private: |

92 | uint64_t advance() |

93 | { |

94 | uint64_t x = m_low; |

95 | uint64_t y = m_high; |

96 | m_low = y; |

97 | x ^= x << 23; |

98 | x ^= x >> 17; |

99 | x ^= y ^ (y >> 26); |

100 | m_high = x; |

101 | return x + y; |

102 | } |

103 | |

104 | unsigned m_seed; |

105 | uint64_t m_low; |

106 | uint64_t m_high; |

107 | }; |

108 | |

109 | } // namespace WTF |

110 | |

111 | using WTF::WeakRandom; |

112 | |

113 | #endif // WeakRandom_h |

114 |