test/support/constexpr_random.h

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef TEST_SUPPORT_CONSTEXPR_RANDOM_H
#define TEST_SUPPORT_CONSTEXPR_RANDOM_H

#include <climits>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <type_traits>
#include <utility>

#include "test_macros.h"

namespace support {

namespace detail {

template <class>
struct is_valid_integer_type_for_random : std::false_type {};
template <>
struct is_valid_integer_type_for_random<std::int8_t> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<short> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<int> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<long> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<long long> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<std::uint8_t> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<unsigned short> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<unsigned int> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<unsigned long> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<unsigned long long> : std::true_type {};

#ifndef TEST_HAS_NO_INT128
template <>
struct is_valid_integer_type_for_random<__int128_t> : std::true_type {};
template <>
struct is_valid_integer_type_for_random<__uint128_t> : std::true_type {};
#endif // TEST_HAS_NO_INT128

template <class, class = void>
struct is_valid_urng : std::false_type {};
template <class Gen>
struct is_valid_urng<
    Gen,
    typename std::enable_if<std::is_unsigned<typename Gen::result_type>::value &&
                            std::is_same<decltype(std::declval<Gen&>()()), typename Gen::result_type>::value>::type>
    : std::true_type {};

template <class UIntType, UIntType N, std::size_t R>
struct meta_log2_imp;

template <unsigned long long N, std::size_t R>
struct meta_log2_imp<unsigned long long, N, R> {
  static const std::size_t value =
      N & ((unsigned long long)(1) << R) ? R : meta_log2_imp<unsigned long long, N, R - 1>::value;
};

template <unsigned long long N>
struct meta_log2_imp<unsigned long long, N, 0> {
  static const std::size_t value = 0;
};

template <size_t R>
struct meta_log2_imp<unsigned long long, 0, R> {
  static const std::size_t value = R + 1;
};

#ifndef TEST_HAS_NO_INT128
template <__uint128_t N, std::size_t R>
struct meta_log2_imp<__uint128_t, N, R> {
  static const size_t value =
      (N >> 64) ? (64 + meta_log2_imp<unsigned long long, (N >> 64), 63>::value)
                : meta_log2_imp<unsigned long long, N, 63>::value;
};
#endif // TEST_HAS_NO_INT128

template <class UIntType, UIntType N>
struct meta_log2 {
  static const size_t value = meta_log2_imp<
#ifndef TEST_HAS_NO_INT128
      typename std::conditional<sizeof(UIntType) <= sizeof(unsigned long long), unsigned long long, __uint128_t>::type,
#else
      unsigned long long,
#endif // TEST_HAS_NO_INT128
      N,
      sizeof(UIntType) * CHAR_BIT - 1 >::value;
};

#ifdef TEST_COMPILER_MSVC
template <int Width, class T, typename std::enable_if<(Width <= 1), int>::type = 0>
TEST_CONSTEXPR int countl_zero_div_conq(T n) TEST_NOEXCEPT {
  return static_cast<int>(~n) & 1;
}

template <int Width, class T, typename std::enable_if<(Width > 1), int>::type = 0>
TEST_CONSTEXPR int countl_zero_div_conq(T n) TEST_NOEXCEPT {
  return n >= (static_cast<T>(1) << (Width / 2))
           ? detail::countl_zero_div_conq<Width / 2>(n >> (Width / 2))
           : detail::countl_zero_div_conq<Width / 2>(n) + Width / 2;
}
#endif

template <class T, typename std::enable_if<std::is_same<T, unsigned int>::value, int>::type = 0>
TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {
#ifdef TEST_COMPILER_MSVC
  return detail::countl_zero_div_conq<std::numeric_limits<T>::digits>(n);
#else
  return __builtin_clz(n);
#endif
}

template <class T, typename std::enable_if<std::is_same<T, unsigned long>::value, int>::type = 0>
TEST_CONSTEXPR_CXX14 int countl_zero(T n) TEST_NOEXCEPT {
#ifdef TEST_COMPILER_MSVC
  return detail::countl_zero_div_conq<std::numeric_limits<T>::digits>(n);
#else
  return __builtin_clzl(n);
#endif
}

template <class T, typename std::enable_if<std::is_same<T, unsigned long long>::value, int>::type = 0>
TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {
#ifdef TEST_COMPILER_MSVC
  return detail::countl_zero_div_conq<std::numeric_limits<T>::digits>(n);
#else
  return __builtin_clzll(n);
#endif
}

#ifndef TEST_HAS_NO_INT128
template <class T, typename std::enable_if<std::is_same<T, __uint128_t>::value, int>::type = 0>
TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {
  return n > std::numeric_limits<std::uint64_t>::max()
           ? detail::countl_zero(static_cast<std::uint64_t>(n >> 64))
           : detail::countl_zero(static_cast<std::uint64_t>(n)) + 64;
}
#endif // TEST_HAS_NO_INT128

template <class T,
          typename std::enable_if<std::is_same<T, unsigned char>::value || std::is_same<T, unsigned short>::value,
                                  int>::type = 0>
TEST_CONSTEXPR int countl_zero(T n) TEST_NOEXCEPT {
  return detail::countl_zero(static_cast<unsigned int>(n)) -
         (std::numeric_limits<unsigned int>::digits - std::numeric_limits<T>::digits);
}

template <class Engine, class UIntType>
class independent_bits_engine {
public:
  typedef UIntType result_type;

private:
  typedef typename Engine::result_type engine_result_type;
  typedef
      typename std::conditional<sizeof(engine_result_type) <= sizeof(result_type), result_type, engine_result_type>::
          type working_result_type;

  Engine& eng_;
  std::size_t width_;
  std::size_t wid0_;
  std::size_t round_count_all_;
  std::size_t round_count_regular_;
  working_result_type y0_;
  working_result_type y1_;
  engine_result_type mask0_;
  engine_result_type mask1_;

#if TEST_STD_VER >= 11
  static constexpr working_result_type rp = Engine::max() - Engine::min() + working_result_type(1);
#else
  static const working_result_type rp = Engine::max_value - Engine::min_value + working_result_type(1);
#endif
  static TEST_CONSTEXPR const std::size_t rp_log2  = meta_log2<working_result_type, rp>::value;
  static TEST_CONSTEXPR const std::size_t w_digits = std::numeric_limits<working_result_type>::digits;
  static TEST_CONSTEXPR const std::size_t e_digits = std::numeric_limits<engine_result_type>::digits;

public:
  // constructors and seeding functions
  TEST_CONSTEXPR_CXX14 independent_bits_engine(Engine& eng, std::size_t width)
      : eng_(eng),
        width_(width),
        wid0_(),
        round_count_all_(),
        round_count_regular_(),
        y0_(),
        y1_(),
        mask0_(),
        mask1_() {
    round_count_all_ = width_ / rp_log2 + (width_ % rp_log2 != 0);
    wid0_            = width_ / round_count_all_;
    if TEST_CONSTEXPR_CXX17 (rp == 0) {
      y0_ = rp;
    } else {
      if (wid0_ < w_digits)
        y0_ = (rp >> wid0_) << wid0_;
      else
        y0_ = 0;
    }
    if (rp - y0_ > y0_ / round_count_all_) {
      ++round_count_all_;
      wid0_ = width_ / round_count_all_;
      if (wid0_ < w_digits)
        y0_ = (rp >> wid0_) << wid0_;
      else
        y0_ = 0;
    }
    round_count_regular_ = round_count_all_ - width_ % round_count_all_;
    if (wid0_ < w_digits - 1)
      y1_ = (rp >> (wid0_ + 1)) << (wid0_ + 1);
    else
      y1_ = 0;
    mask0_ = wid0_ > 0 ? static_cast<engine_result_type>(engine_result_type(~0) >> (e_digits - wid0_))
                       : engine_result_type(0);
    mask1_ = wid0_ < e_digits - 1 ? static_cast<engine_result_type>(engine_result_type(~0) >> (e_digits - (wid0_ + 1)))
                                  : engine_result_type(~0);
  }

  // generating functions
  TEST_CONSTEXPR_CXX14 result_type operator()() { return generate(std::integral_constant<bool, (rp != 0)>()); }

private:
  TEST_CONSTEXPR_CXX14 result_type generate(std::false_type) { return static_cast<result_type>(eng_() & mask0_); }

  TEST_CONSTEXPR_CXX14 result_type generate(std::true_type) {
    const std::size_t r_digits = std::numeric_limits<result_type>::digits;
    result_type result         = 0;
    for (std::size_t k = 0; k < round_count_regular_; ++k) {
      engine_result_type eng_result = 0;
      do {
        eng_result = static_cast<engine_result_type>(eng_() - Engine::min());
      } while (eng_result >= y0_);
      if (wid0_ < r_digits)
        result <<= wid0_;
      else
        result = 0;
      result += eng_result & mask0_;
    }
    for (std::size_t k = round_count_regular_; k < round_count_all_; ++k) {
      engine_result_type eng_result = 0;
      do {
        eng_result = static_cast<engine_result_type>(eng_() - Engine::min());
      } while (eng_result >= y1_);
      if (wid0_ < r_digits - 1)
        result <<= wid0_ + 1;
      else
        result = 0;
      result += eng_result & mask1_;
    }
    return result;
  }
};

} // namespace detail

template <class IntType = int>
class uniform_int_distribution {
  static_assert(detail::is_valid_integer_type_for_random<IntType>::value, "IntType must be a supported integer type");

public:
  // types
  typedef IntType result_type;

  class param_type {
    result_type a_;
    result_type b_;

  public:
    typedef uniform_int_distribution distribution_type;

#if TEST_STD_VER >= 11
    constexpr param_type() : param_type(0) {}
#else
    param_type() : a_(0), b_(std::numeric_limits<result_type>::max()) {}
#endif
    TEST_CONSTEXPR explicit param_type(result_type ax, result_type bx = std::numeric_limits<result_type>::max())
        : a_(ax), b_(bx) {}

    TEST_CONSTEXPR result_type a() const { return a_; }
    TEST_CONSTEXPR result_type b() const { return b_; }

#if TEST_STD_VER >= 20
    friend bool operator==(const param_type&, const param_type&) = default;
#else
    TEST_CONSTEXPR friend bool operator==(const param_type& lhs, const param_type& rhs) {
      return lhs.a_ == rhs.a_ && lhs.b_ == rhs.b_;
    }
    TEST_CONSTEXPR friend bool operator!=(const param_type& lhs, const param_type& rhs) { return !(lhs == rhs); }
#endif
  };

private:
  param_type param_;

public:
  // constructors and reset functions
#if TEST_STD_VER >= 11
  uniform_int_distribution() = default;
#else
  uniform_int_distribution() {}
#endif
  TEST_CONSTEXPR explicit uniform_int_distribution(result_type ax,
                                                   result_type bx = std::numeric_limits<result_type>::max())
      : param_(ax, bx) {}
  TEST_CONSTEXPR explicit uniform_int_distribution(const param_type& param) : param_(param) {}
  TEST_CONSTEXPR_CXX14 void reset() {}

  // generating functions
  template <class URNG>
  TEST_CONSTEXPR_CXX14 result_type operator()(URNG& gen) {
    return (*this)(gen, param_);
  }

#if TEST_HAS_FEATURE(no_sanitize) && !defined(TEST_COMPILER_GCC)
#  define TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK __attribute__((__no_sanitize__("unsigned-integer-overflow")))
#else
#  define TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
#endif
  template <class URNG>
  TEST_CONSTEXPR_CXX14 result_type operator()(URNG& gen, const param_type& param)
      TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
    static_assert(detail::is_valid_urng<URNG>::value, "invalid uniform random bit generator used");
    typedef typename std::conditional<sizeof(result_type) <= sizeof(std::uint32_t),
                                      std::uint32_t,
                                      typename std::make_unsigned<result_type>::type>::type UIntType;
    const UIntType rp = UIntType(param.b()) - UIntType(param.a()) + UIntType(1);
    if (rp == 1)
      return param.a();
    const std::size_t ur_digits = std::numeric_limits<UIntType>::digits;
    typedef detail::independent_bits_engine<URNG, UIntType> Eng;
    if (rp == 0)
      return static_cast<result_type>(Eng(gen, ur_digits)());
    std::size_t width = ur_digits - detail::countl_zero(rp) - 1;
    if ((rp & (std::numeric_limits<UIntType>::max() >> (ur_digits - width))) != 0)
      ++width;
    Eng eng(gen, width);
    UIntType eng_result = 0;
    do {
      eng_result = eng();
    } while (eng_result >= rp);
    return static_cast<result_type>(eng_result + param.a());
  }
#undef TEST_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK

  // property functions
  TEST_CONSTEXPR result_type a() const { return param_.a(); }
  TEST_CONSTEXPR result_type b() const { return param_.b(); }

  TEST_CONSTEXPR param_type param() const { return param_; }
  TEST_CONSTEXPR_CXX14 void param(const param_type& param) { param_ = param; }

  TEST_CONSTEXPR result_type min() const { return a(); }
  TEST_CONSTEXPR result_type max() const { return b(); }

#if TEST_STD_VER >= 20
  friend bool operator==(const uniform_int_distribution&, const uniform_int_distribution&) = default;
#else
  TEST_CONSTEXPR friend bool operator==(const uniform_int_distribution& lhs, const uniform_int_distribution& rhs) {
    return lhs.param_ == rhs.param_;
  }
  TEST_CONSTEXPR friend bool operator!=(const uniform_int_distribution& lhs, const uniform_int_distribution& rhs) {
    return !(lhs == rhs);
  }
#endif
};

class simple_random_generator { // A linear congruential generator, using the constants used by MS UCRT.
private:
  std::uint32_t status_;

public:
  typedef std::uint16_t result_type;

  static TEST_CONSTEXPR result_type min() TEST_NOEXCEPT { return 0; }
  static TEST_CONSTEXPR result_type max() TEST_NOEXCEPT { return static_cast<result_type>(-1); }
#if TEST_STD_VER < 11
  static const result_type min_value = 0;
  static const result_type max_value = static_cast<result_type>(-1);
#endif
  static TEST_CONSTEXPR const result_type default_seed = 19937;

#if TEST_STD_VER >= 11
  constexpr simple_random_generator() noexcept : simple_random_generator(default_seed) {}
#else
  simple_random_generator() throw() : status_(default_seed) {}
#endif
  TEST_CONSTEXPR explicit simple_random_generator(std::uint16_t s) TEST_NOEXCEPT : status_(s) {}

  TEST_CONSTEXPR_CXX14 result_type operator()() TEST_NOEXCEPT {
    status_ = status_ * 214013u + 2531011u;
    return static_cast<result_type>(status_ >> 16);
  }
};

template <class RandomAccessIterator, class UniformRandomNumberGenerator>
TEST_CONSTEXPR_CXX14 void
#if TEST_STD_VER >= 11
shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& gen)
#else
shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator& gen)
#endif
{
  typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
  typedef uniform_int_distribution<ptrdiff_t> dist;
  typedef typename dist::param_type param_type;

  RandomAccessIterator last_iter = last;
  difference_type diff           = last_iter - first;
  if (diff > 1) {
    dist uid;
    for (--last_iter, (void)--diff; first < last; ++first, (void)--diff) {
      difference_type index = uid(gen, param_type(0, diff));
      if (index != difference_type(0)) {
        using std::swap;
        swap(*first, *(first + index));
      }
    }
  }
}

} // namespace support

#endif // TEST_SUPPORT_CONSTEXPR_RANDOM_H