439 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef TEST_SUPPORT_CONSTEXPR_RANDOM_H10#define TEST_SUPPORT_CONSTEXPR_RANDOM_H11 12#include <climits>13#include <cstddef>14#include <cstdint>15#include <iterator>16#include <limits>17#include <type_traits>18#include <utility>19 20#include "test_macros.h"21 22namespace support {23 24namespace detail {25 26template <class>27struct is_valid_integer_type_for_random : std::false_type {};28template <>29struct is_valid_integer_type_for_random<std::int8_t> : std::true_type {};30template <>31struct is_valid_integer_type_for_random<short> : std::true_type {};32template <>33struct is_valid_integer_type_for_random<int> : std::true_type {};34template <>35struct is_valid_integer_type_for_random<long> : std::true_type {};36template <>37struct is_valid_integer_type_for_random<long long> : std::true_type {};38template <>39struct is_valid_integer_type_for_random<std::uint8_t> : std::true_type {};40template <>41struct is_valid_integer_type_for_random<unsigned short> : std::true_type {};42template <>43struct is_valid_integer_type_for_random<unsigned int> : std::true_type {};44template <>45struct is_valid_integer_type_for_random<unsigned long> : std::true_type {};46template <>47struct is_valid_integer_type_for_random<unsigned long long> : std::true_type {};48 49#ifndef TEST_HAS_NO_INT12850template <>51struct is_valid_integer_type_for_random<__int128_t> : std::true_type {};52template <>53struct is_valid_integer_type_for_random<__uint128_t> : std::true_type {};54#endif // TEST_HAS_NO_INT12855 56template <class, class = void>57struct is_valid_urng : std::false_type {};58template <class Gen>59struct is_valid_urng<60 Gen,61 typename std::enable_if<std::is_unsigned<typename Gen::result_type>::value &&62 std::is_same<decltype(std::declval<Gen&>()()), typename Gen::result_type>::value>::type>63 : std::true_type {};64 65template <class UIntType, UIntType N, std::size_t R>66struct meta_log2_imp;67 68template <unsigned long long N, std::size_t R>69struct meta_log2_imp<unsigned long long, N, R> {70 static const std::size_t value =71 N & ((unsigned long long)(1) << R) ? R : meta_log2_imp<unsigned long long, N, R - 1>::value;72};73 74template <unsigned long long N>75struct meta_log2_imp<unsigned long long, N, 0> {76 static const std::size_t value = 0;77};78 79template <size_t R>80struct meta_log2_imp<unsigned long long, 0, R> {81 static const std::size_t value = R + 1;82};83 84#ifndef TEST_HAS_NO_INT12885template <__uint128_t N, std::size_t R>86struct meta_log2_imp<__uint128_t, N, R> {87 static const size_t value =88 (N >> 64) ? (64 + meta_log2_imp<unsigned long long, (N >> 64), 63>::value)89 : meta_log2_imp<unsigned long long, N, 63>::value;90};91#endif // TEST_HAS_NO_INT12892 93template <class UIntType, UIntType N>94struct meta_log2 {95 static const size_t value = meta_log2_imp<96#ifndef TEST_HAS_NO_INT12897 typename std::conditional<sizeof(UIntType) <= sizeof(unsigned long long), unsigned long long, __uint128_t>::type,98#else99 unsigned long long,100#endif // TEST_HAS_NO_INT128101 N,102 sizeof(UIntType) * CHAR_BIT - 1 >::value;103};104 105#ifdef TEST_COMPILER_MSVC106template <int Width, class T, typename std::enable_if<(Width <= 1), int>::type = 0>107TEST_CONSTEXPR int countl_zero_div_conq(T n) TEST_NOEXCEPT {108 return static_cast<int>(~n) & 1;109}110 111template <int Width, class T, typename std::enable_if<(Width > 1), int>::type = 0>112TEST_CONSTEXPR int countl_zero_div_conq(T n) TEST_NOEXCEPT {113 return n >= (static_cast<T>(1) << (Width / 2))114 ? detail::countl_zero_div_conq<Width / 2>(n >> (Width / 2))115 : detail::countl_zero_div_conq<Width / 2>(n) + Width / 2;116}117#endif118 119template <class T, typename std::enable_if<std::is_same<T, unsigned int>::value, int>::type = 0>120TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {121#ifdef TEST_COMPILER_MSVC122 return detail::countl_zero_div_conq<std::numeric_limits<T>::digits>(n);123#else124 return __builtin_clz(n);125#endif126}127 128template <class T, typename std::enable_if<std::is_same<T, unsigned long>::value, int>::type = 0>129TEST_CONSTEXPR_CXX14 int countl_zero(T n) TEST_NOEXCEPT {130#ifdef TEST_COMPILER_MSVC131 return detail::countl_zero_div_conq<std::numeric_limits<T>::digits>(n);132#else133 return __builtin_clzl(n);134#endif135}136 137template <class T, typename std::enable_if<std::is_same<T, unsigned long long>::value, int>::type = 0>138TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {139#ifdef TEST_COMPILER_MSVC140 return detail::countl_zero_div_conq<std::numeric_limits<T>::digits>(n);141#else142 return __builtin_clzll(n);143#endif144}145 146#ifndef TEST_HAS_NO_INT128147template <class T, typename std::enable_if<std::is_same<T, __uint128_t>::value, int>::type = 0>148TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {149 return n > std::numeric_limits<std::uint64_t>::max()150 ? detail::countl_zero(static_cast<std::uint64_t>(n >> 64))151 : detail::countl_zero(static_cast<std::uint64_t>(n)) + 64;152}153#endif // TEST_HAS_NO_INT128154 155template <class T,156 typename std::enable_if<std::is_same<T, unsigned char>::value || std::is_same<T, unsigned short>::value,157 int>::type = 0>158TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {159 return detail::countl_zero(static_cast<unsigned int>(n)) -160 (std::numeric_limits<unsigned int>::digits - std::numeric_limits<T>::digits);161}162 163template <class Engine, class UIntType>164class independent_bits_engine {165public:166 typedef UIntType result_type;167 168private:169 typedef typename Engine::result_type engine_result_type;170 typedef171 typename std::conditional<sizeof(engine_result_type) <= sizeof(result_type), result_type, engine_result_type>::172 type working_result_type;173 174 Engine& eng_;175 std::size_t width_;176 std::size_t wid0_;177 std::size_t round_count_all_;178 std::size_t round_count_regular_;179 working_result_type y0_;180 working_result_type y1_;181 engine_result_type mask0_;182 engine_result_type mask1_;183 184#if TEST_STD_VER >= 11185 static constexpr working_result_type rp = Engine::max() - Engine::min() + working_result_type(1);186#else187 static const working_result_type rp = Engine::max_value - Engine::min_value + working_result_type(1);188#endif189 static TEST_CONSTEXPR const std::size_t rp_log2 = meta_log2<working_result_type, rp>::value;190 static TEST_CONSTEXPR const std::size_t w_digits = std::numeric_limits<working_result_type>::digits;191 static TEST_CONSTEXPR const std::size_t e_digits = std::numeric_limits<engine_result_type>::digits;192 193public:194 // constructors and seeding functions195 TEST_CONSTEXPR_CXX14 independent_bits_engine(Engine& eng, std::size_t width)196 : eng_(eng),197 width_(width),198 wid0_(),199 round_count_all_(),200 round_count_regular_(),201 y0_(),202 y1_(),203 mask0_(),204 mask1_() {205 round_count_all_ = width_ / rp_log2 + (width_ % rp_log2 != 0);206 wid0_ = width_ / round_count_all_;207 if TEST_CONSTEXPR_CXX17 (rp == 0) {208 y0_ = rp;209 } else {210 if (wid0_ < w_digits)211 y0_ = (rp >> wid0_) << wid0_;212 else213 y0_ = 0;214 }215 if (rp - y0_ > y0_ / round_count_all_) {216 ++round_count_all_;217 wid0_ = width_ / round_count_all_;218 if (wid0_ < w_digits)219 y0_ = (rp >> wid0_) << wid0_;220 else221 y0_ = 0;222 }223 round_count_regular_ = round_count_all_ - width_ % round_count_all_;224 if (wid0_ < w_digits - 1)225 y1_ = (rp >> (wid0_ + 1)) << (wid0_ + 1);226 else227 y1_ = 0;228 mask0_ = wid0_ > 0 ? static_cast<engine_result_type>(engine_result_type(~0) >> (e_digits - wid0_))229 : engine_result_type(0);230 mask1_ = wid0_ < e_digits - 1 ? static_cast<engine_result_type>(engine_result_type(~0) >> (e_digits - (wid0_ + 1)))231 : engine_result_type(~0);232 }233 234 // generating functions235 TEST_CONSTEXPR_CXX14 result_type operator()() { return generate(std::integral_constant<bool, (rp != 0)>()); }236 237private:238 TEST_CONSTEXPR_CXX14 result_type generate(std::false_type) { return static_cast<result_type>(eng_() & mask0_); }239 240 TEST_CONSTEXPR_CXX14 result_type generate(std::true_type) {241 const std::size_t r_digits = std::numeric_limits<result_type>::digits;242 result_type result = 0;243 for (std::size_t k = 0; k < round_count_regular_; ++k) {244 engine_result_type eng_result = 0;245 do {246 eng_result = static_cast<engine_result_type>(eng_() - Engine::min());247 } while (eng_result >= y0_);248 if (wid0_ < r_digits)249 result <<= wid0_;250 else251 result = 0;252 result += eng_result & mask0_;253 }254 for (std::size_t k = round_count_regular_; k < round_count_all_; ++k) {255 engine_result_type eng_result = 0;256 do {257 eng_result = static_cast<engine_result_type>(eng_() - Engine::min());258 } while (eng_result >= y1_);259 if (wid0_ < r_digits - 1)260 result <<= wid0_ + 1;261 else262 result = 0;263 result += eng_result & mask1_;264 }265 return result;266 }267};268 269} // namespace detail270 271template <class IntType = int>272class uniform_int_distribution {273 static_assert(detail::is_valid_integer_type_for_random<IntType>::value, "IntType must be a supported integer type");274 275public:276 // types277 typedef IntType result_type;278 279 class param_type {280 result_type a_;281 result_type b_;282 283 public:284 typedef uniform_int_distribution distribution_type;285 286#if TEST_STD_VER >= 11287 constexpr param_type() : param_type(0) {}288#else289 param_type() : a_(0), b_(std::numeric_limits<result_type>::max()) {}290#endif291 TEST_CONSTEXPR explicit param_type(result_type ax, result_type bx = std::numeric_limits<result_type>::max())292 : a_(ax), b_(bx) {}293 294 TEST_CONSTEXPR result_type a() const { return a_; }295 TEST_CONSTEXPR result_type b() const { return b_; }296 297#if TEST_STD_VER >= 20298 friend bool operator==(const param_type&, const param_type&) = default;299#else300 TEST_CONSTEXPR friend bool operator==(const param_type& lhs, const param_type& rhs) {301 return lhs.a_ == rhs.a_ && lhs.b_ == rhs.b_;302 }303 TEST_CONSTEXPR friend bool operator!=(const param_type& lhs, const param_type& rhs) { return !(lhs == rhs); }304#endif305 };306 307private:308 param_type param_;309 310public:311 // constructors and reset functions312#if TEST_STD_VER >= 11313 uniform_int_distribution() = default;314#else315 uniform_int_distribution() {}316#endif317 TEST_CONSTEXPR explicit uniform_int_distribution(result_type ax,318 result_type bx = std::numeric_limits<result_type>::max())319 : param_(ax, bx) {}320 TEST_CONSTEXPR explicit uniform_int_distribution(const param_type& param) : param_(param) {}321 TEST_CONSTEXPR_CXX14 void reset() {}322 323 // generating functions324 template <class URNG>325 TEST_CONSTEXPR_CXX14 result_type operator()(URNG& gen) {326 return (*this)(gen, param_);327 }328 329#if TEST_HAS_FEATURE(no_sanitize) && !defined(TEST_COMPILER_GCC)330# define TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK __attribute__((__no_sanitize__("unsigned-integer-overflow")))331#else332# define TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK333#endif334 template <class URNG>335 TEST_CONSTEXPR_CXX14 result_type operator()(URNG& gen, const param_type& param)336 TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {337 static_assert(detail::is_valid_urng<URNG>::value, "invalid uniform random bit generator used");338 typedef typename std::conditional<sizeof(result_type) <= sizeof(std::uint32_t),339 std::uint32_t,340 typename std::make_unsigned<result_type>::type>::type UIntType;341 const UIntType rp = UIntType(param.b()) - UIntType(param.a()) + UIntType(1);342 if (rp == 1)343 return param.a();344 const std::size_t ur_digits = std::numeric_limits<UIntType>::digits;345 typedef detail::independent_bits_engine<URNG, UIntType> Eng;346 if (rp == 0)347 return static_cast<result_type>(Eng(gen, ur_digits)());348 std::size_t width = ur_digits - detail::countl_zero(rp) - 1;349 if ((rp & (std::numeric_limits<UIntType>::max() >> (ur_digits - width))) != 0)350 ++width;351 Eng eng(gen, width);352 UIntType eng_result = 0;353 do {354 eng_result = eng();355 } while (eng_result >= rp);356 return static_cast<result_type>(eng_result + param.a());357 }358#undef TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK359 360 // property functions361 TEST_CONSTEXPR result_type a() const { return param_.a(); }362 TEST_CONSTEXPR result_type b() const { return param_.b(); }363 364 TEST_CONSTEXPR param_type param() const { return param_; }365 TEST_CONSTEXPR_CXX14 void param(const param_type& param) { param_ = param; }366 367 TEST_CONSTEXPR result_type min() const { return a(); }368 TEST_CONSTEXPR result_type max() const { return b(); }369 370#if TEST_STD_VER >= 20371 friend bool operator==(const uniform_int_distribution&, const uniform_int_distribution&) = default;372#else373 TEST_CONSTEXPR friend bool operator==(const uniform_int_distribution& lhs, const uniform_int_distribution& rhs) {374 return lhs.param_ == rhs.param_;375 }376 TEST_CONSTEXPR friend bool operator!=(const uniform_int_distribution& lhs, const uniform_int_distribution& rhs) {377 return !(lhs == rhs);378 }379#endif380};381 382class simple_random_generator { // A linear congruential generator, using the constants used by MS UCRT.383private:384 std::uint32_t status_;385 386public:387 typedef std::uint16_t result_type;388 389 static TEST_CONSTEXPR result_type min() TEST_NOEXCEPT { return 0; }390 static TEST_CONSTEXPR result_type max() TEST_NOEXCEPT { return static_cast<result_type>(-1); }391#if TEST_STD_VER < 11392 static const result_type min_value = 0;393 static const result_type max_value = static_cast<result_type>(-1);394#endif395 static TEST_CONSTEXPR const result_type default_seed = 19937;396 397#if TEST_STD_VER >= 11398 constexpr simple_random_generator() noexcept : simple_random_generator(default_seed) {}399#else400 simple_random_generator() throw() : status_(default_seed) {}401#endif402 TEST_CONSTEXPR explicit simple_random_generator(std::uint16_t s) TEST_NOEXCEPT : status_(s) {}403 404 TEST_CONSTEXPR_CXX14 result_type operator()() TEST_NOEXCEPT {405 status_ = status_ * 214013u + 2531011u;406 return static_cast<result_type>(status_ >> 16);407 }408};409 410template <class RandomAccessIterator, class UniformRandomNumberGenerator>411TEST_CONSTEXPR_CXX14 void412#if TEST_STD_VER >= 11413shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& gen)414#else415shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator& gen)416#endif417{418 typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;419 typedef uniform_int_distribution<ptrdiff_t> dist;420 typedef typename dist::param_type param_type;421 422 RandomAccessIterator last_iter = last;423 difference_type diff = last_iter - first;424 if (diff > 1) {425 dist uid;426 for (--last_iter, (void)--diff; first < last; ++first, (void)--diff) {427 difference_type index = uid(gen, param_type(0, diff));428 if (index != difference_type(0)) {429 using std::swap;430 swap(*first, *(first + index));431 }432 }433 }434}435 436} // namespace support437 438#endif // TEST_SUPPORT_CONSTEXPR_RANDOM_H439