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

2 | ** |

3 | ** Copyright (C) 2017 Intel Corporation. |

4 | ** Contact: https://www.qt.io/licensing/ |

5 | ** |

6 | ** This file is part of the QtCore module of the Qt Toolkit. |

7 | ** |

8 | ** $QT_BEGIN_LICENSE:LGPL$ |

9 | ** Commercial License Usage |

10 | ** Licensees holding valid commercial Qt licenses may use this file in |

11 | ** accordance with the commercial license agreement provided with the |

12 | ** Software or, alternatively, in accordance with the terms contained in |

13 | ** a written agreement between you and The Qt Company. For licensing terms |

14 | ** and conditions see https://www.qt.io/terms-conditions. For further |

15 | ** information use the contact form at https://www.qt.io/contact-us. |

16 | ** |

17 | ** GNU Lesser General Public License Usage |

18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |

19 | ** General Public License version 3 as published by the Free Software |

20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |

21 | ** packaging of this file. Please review the following information to |

22 | ** ensure the GNU Lesser General Public License version 3 requirements |

23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |

24 | ** |

25 | ** GNU General Public License Usage |

26 | ** Alternatively, this file may be used under the terms of the GNU |

27 | ** General Public License version 2.0 or (at your option) the GNU General |

28 | ** Public license version 3 or any later version approved by the KDE Free |

29 | ** Qt Foundation. The licenses are as published by the Free Software |

30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |

31 | ** included in the packaging of this file. Please review the following |

32 | ** information to ensure the GNU General Public License requirements will |

33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |

34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |

35 | ** |

36 | ** $QT_END_LICENSE$ |

37 | ** |

38 | ****************************************************************************/ |

39 | |

40 | #ifndef QRANDOM_H |

41 | #define QRANDOM_H |

42 | |

43 | #include <QtCore/qglobal.h> |

44 | #include <algorithm> // for std::generate |

45 | #include <random> // for std::mt19937 |

46 | |

47 | #ifdef min |

48 | # undef min |

49 | #endif |

50 | #ifdef max |

51 | # undef max |

52 | #endif |

53 | |

54 | QT_BEGIN_NAMESPACE |

55 | |

56 | class QRandomGenerator |

57 | { |

58 | // restrict the template parameters to unsigned integers 32 bits wide or larger |

59 | template <typename UInt> using IfValidUInt = |

60 | typename std::enable_if<std::is_unsigned<UInt>::value && sizeof(UInt) >= sizeof(uint), bool>::type; |

61 | public: |

62 | QRandomGenerator(quint32 seedValue = 1) |

63 | : QRandomGenerator(&seedValue, 1) |

64 | {} |

65 | template <qsizetype N> QRandomGenerator(const quint32 (&seedBuffer)[N]) |

66 | : QRandomGenerator(seedBuffer, seedBuffer + N) |

67 | {} |

68 | QRandomGenerator(const quint32 *seedBuffer, qsizetype len) |

69 | : QRandomGenerator(seedBuffer, seedBuffer + len) |

70 | {} |

71 | Q_CORE_EXPORT QRandomGenerator(std::seed_seq &sseq) noexcept; |

72 | Q_CORE_EXPORT QRandomGenerator(const quint32 *begin, const quint32 *end); |

73 | |

74 | // copy constructor & assignment operator (move unnecessary) |

75 | Q_CORE_EXPORT QRandomGenerator(const QRandomGenerator &other); |

76 | Q_CORE_EXPORT QRandomGenerator &operator=(const QRandomGenerator &other); |

77 | |

78 | friend Q_CORE_EXPORT bool operator==(const QRandomGenerator &rng1, const QRandomGenerator &rng2); |

79 | friend bool operator!=(const QRandomGenerator &rng1, const QRandomGenerator &rng2) |

80 | { |

81 | return !(rng1 == rng2); |

82 | } |

83 | |

84 | quint32 generate() |

85 | { |

86 | quint32 ret; |

87 | fillRange(&ret, 1); |

88 | return ret; |

89 | } |

90 | |

91 | quint64 generate64() |

92 | { |

93 | quint32 buf[2]; |

94 | fillRange(buf); |

95 | return buf[0] | (quint64(buf[1]) << 32); |

96 | } |

97 | |

98 | double generateDouble() |

99 | { |

100 | // IEEE 754 double precision has: |

101 | // 1 bit sign |

102 | // 10 bits exponent |

103 | // 53 bits mantissa |

104 | // In order for our result to be normalized in the range [0, 1), we |

105 | // need exactly 53 bits of random data. Use generate64() to get enough. |

106 | quint64 x = generate64(); |

107 | quint64 limit = Q_UINT64_C(1) << std::numeric_limits<double>::digits; |

108 | x >>= std::numeric_limits<quint64>::digits - std::numeric_limits<double>::digits; |

109 | return double(x) / double(limit); |

110 | } |

111 | |

112 | double bounded(double highest) |

113 | { |

114 | return generateDouble() * highest; |

115 | } |

116 | |

117 | quint32 bounded(quint32 highest) |

118 | { |

119 | quint64 value = generate(); |

120 | value *= highest; |

121 | value /= (max)() + quint64(1); |

122 | return quint32(value); |

123 | } |

124 | |

125 | quint32 bounded(quint32 lowest, quint32 highest) |

126 | { |

127 | Q_ASSERT(highest > lowest); |

128 | return bounded(highest - lowest) + lowest; |

129 | } |

130 | |

131 | int bounded(int highest) |

132 | { |

133 | Q_ASSERT(highest > 0); |

134 | return int(bounded(0U, quint32(highest))); |

135 | } |

136 | |

137 | int bounded(int lowest, int highest) |

138 | { |

139 | return bounded(highest - lowest) + lowest; |

140 | } |

141 | |

142 | template <typename UInt, IfValidUInt<UInt> = true> |

143 | void fillRange(UInt *buffer, qsizetype count) |

144 | { |

145 | _fillRange(buffer, buffer + count); |

146 | } |

147 | |

148 | template <typename UInt, size_t N, IfValidUInt<UInt> = true> |

149 | void fillRange(UInt (&buffer)[N]) |

150 | { |

151 | _fillRange(buffer, buffer + N); |

152 | } |

153 | |

154 | // API like std::seed_seq |

155 | template <typename ForwardIterator> |

156 | void generate(ForwardIterator begin, ForwardIterator end) |

157 | { |

158 | std::generate(begin, end, [this]() { return generate(); }); |

159 | } |

160 | |

161 | void generate(quint32 *begin, quint32 *end) |

162 | { |

163 | _fillRange(begin, end); |

164 | } |

165 | |

166 | // API like std:: random engines |

167 | typedef quint32 result_type; |

168 | result_type operator()() { return generate(); } |

169 | void seed(quint32 s = 1) { *this = { s }; } |

170 | void seed(std::seed_seq &sseq) noexcept { *this = { sseq }; } |

171 | Q_CORE_EXPORT void discard(unsigned long long z); |

172 | static Q_DECL_CONSTEXPR result_type min() { return std::numeric_limits<result_type>::min(); } |

173 | static Q_DECL_CONSTEXPR result_type max() { return std::numeric_limits<result_type>::max(); } |

174 | |

175 | static inline Q_DECL_CONST_FUNCTION QRandomGenerator *system(); |

176 | static inline Q_DECL_CONST_FUNCTION QRandomGenerator *global(); |

177 | static inline QRandomGenerator securelySeeded(); |

178 | |

179 | protected: |

180 | enum System {}; |

181 | QRandomGenerator(System); |

182 | |

183 | private: |

184 | Q_CORE_EXPORT void _fillRange(void *buffer, void *bufferEnd); |

185 | |

186 | friend class QRandomGenerator64; |

187 | struct SystemGenerator; |

188 | struct SystemAndGlobalGenerators; |

189 | using RandomEngine = std::mersenne_twister_engine<quint32, |

190 | 32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253>; |

191 | |

192 | union Storage { |

193 | uint dummy; |

194 | #ifdef Q_COMPILER_UNRESTRICTED_UNIONS |

195 | RandomEngine twister; |

196 | RandomEngine &engine() { return twister; } |

197 | const RandomEngine &engine() const { return twister; } |

198 | #else |

199 | std::aligned_storage<sizeof(RandomEngine), Q_ALIGNOF(RandomEngine)>::type buffer; |

200 | RandomEngine &engine() { return reinterpret_cast<RandomEngine &>(buffer); } |

201 | const RandomEngine &engine() const { return reinterpret_cast<const RandomEngine &>(buffer); } |

202 | #endif |

203 | |

204 | Q_STATIC_ASSERT_X(std::is_trivially_destructible<RandomEngine>::value, |

205 | "std::mersenne_twister not trivially destructible as expected"); |

206 | Q_DECL_CONSTEXPR Storage(); |

207 | }; |

208 | uint type; |

209 | Storage storage; |

210 | }; |

211 | |

212 | class QRandomGenerator64 : public QRandomGenerator |

213 | { |

214 | QRandomGenerator64(System); |

215 | public: |

216 | // unshadow generate() overloads, since we'll override. |

217 | using QRandomGenerator::generate; |

218 | quint64 generate() { return generate64(); } |

219 | |

220 | typedef quint64 result_type; |

221 | result_type operator()() { return generate64(); } |

222 | |

223 | #ifndef Q_QDOC |

224 | QRandomGenerator64(quint32 seedValue = 1) |

225 | : QRandomGenerator(seedValue) |

226 | {} |

227 | template <qsizetype N> QRandomGenerator64(const quint32 (&seedBuffer)[N]) |

228 | : QRandomGenerator(seedBuffer) |

229 | {} |

230 | QRandomGenerator64(const quint32 *seedBuffer, qsizetype len) |

231 | : QRandomGenerator(seedBuffer, len) |

232 | {} |

233 | QRandomGenerator64(std::seed_seq &sseq) noexcept |

234 | : QRandomGenerator(sseq) |

235 | {} |

236 | QRandomGenerator64(const quint32 *begin, const quint32 *end) |

237 | : QRandomGenerator(begin, end) |

238 | {} |

239 | QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {} |

240 | |

241 | void discard(unsigned long long z) |

242 | { |

243 | Q_ASSERT_X(z * 2 > z, "QRandomGenerator64::discard", |

244 | "Overflow. Are you sure you want to skip over 9 quintillion samples?"); |

245 | QRandomGenerator::discard(z * 2); |

246 | } |

247 | |

248 | static Q_DECL_CONSTEXPR result_type min() { return std::numeric_limits<result_type>::min(); } |

249 | static Q_DECL_CONSTEXPR result_type max() { return std::numeric_limits<result_type>::max(); } |

250 | static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *system(); |

251 | static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *global(); |

252 | static Q_CORE_EXPORT QRandomGenerator64 securelySeeded(); |

253 | #endif // Q_QDOC |

254 | }; |

255 | |

256 | inline QRandomGenerator *QRandomGenerator::system() |

257 | { |

258 | return QRandomGenerator64::system(); |

259 | } |

260 | |

261 | inline QRandomGenerator *QRandomGenerator::global() |

262 | { |

263 | return QRandomGenerator64::global(); |

264 | } |

265 | |

266 | QRandomGenerator QRandomGenerator::securelySeeded() |

267 | { |

268 | return QRandomGenerator64::securelySeeded(); |

269 | } |

270 | |

271 | QT_END_NAMESPACE |

272 | |

273 | #endif // QRANDOM_H |

274 |