[thirdparty/gcc.git] / libstdc++-v3 / src / c++11 / random.cc

// random -*- C++ -*-

// Copyright (C) 2012-2023 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

#define _GLIBCXX_USE_CXX11_ABI 1
#define _CRT_RAND_S // define this before including <stdlib.h> to get rand_s

#include <random>

#ifdef  _GLIBCXX_USE_C99_STDINT_TR1

#if defined __i386__ || defined __x86_64__
# include <cpuid.h>
# ifdef _GLIBCXX_X86_RDRAND
#  define USE_RDRAND 1
# endif
# ifdef _GLIBCXX_X86_RDSEED
#  define USE_RDSEED 1
# endif
#elif defined __powerpc64__ && defined __BUILTIN_CPU_SUPPORTS__
# define USE_DARN 1
#endif

#include <cerrno>
#include <cstdio>
#include <cctype> // For std::isdigit.

#if defined _GLIBCXX_HAVE_UNISTD_H && defined _GLIBCXX_HAVE_FCNTL_H
# include <unistd.h>
# include <fcntl.h>
// Use POSIX open, close, read etc. instead of ISO fopen, fclose, fread
# define USE_POSIX_FILE_IO
#endif

#ifdef _GLIBCXX_HAVE_SYS_IOCTL_H
# include <sys/ioctl.h>
#endif

#ifdef _GLIBCXX_HAVE_LINUX_TYPES_H
# include <linux/types.h>
#endif

#ifdef _GLIBCXX_HAVE_LINUX_RANDOM_H
# include <linux/random.h>
#endif

#ifdef _GLIBCXX_USE_CRT_RAND_S
# include <stdlib.h>
#endif

#ifdef _GLIBCXX_HAVE_GETENTROPY
# include <unistd.h>
#endif

#if defined _GLIBCXX_USE_CRT_RAND_S || defined _GLIBCXX_USE_DEV_RANDOM \
  || _GLIBCXX_HAVE_GETENTROPY
// The OS provides a source of randomness we can use.
# pragma GCC poison _M_mt
#elif defined USE_RDRAND || defined USE_RDSEED || defined USE_DARN
// Hardware instructions might be available, but use cpuid checks at runtime.
# pragma GCC poison _M_mt
// If the runtime cpuid checks fail we'll use a linear congruential engine.
# define USE_LCG 1
#else
// Use the mt19937 member of the union, as in previous GCC releases.
# define USE_MT19937 1
#endif

#ifdef USE_LCG
# include <chrono>
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
  namespace
  {
#if USE_RDRAND
    unsigned int
    __attribute__ ((target("rdrnd")))
    __x86_rdrand(void*)
    {
      unsigned int retries = 100;
      unsigned int val;

      while (__builtin_ia32_rdrand32_step(&val) == 0) [[__unlikely__]]
	if (--retries == 0)
	  std::__throw_runtime_error(__N("random_device: rdrand failed"));

      return val;
    }
#endif

#if USE_RDSEED
    unsigned int
    __attribute__ ((target("rdseed")))
    __x86_rdseed(void* fallback)
    {
      unsigned int retries = 100;
      unsigned int val;

      while (__builtin_ia32_rdseed_si_step(&val) == 0) [[__unlikely__]]
	{
	  if (--retries == 0)
	    {
	      if (auto f = reinterpret_cast<unsigned int(*)(void*)>(fallback))
		return f(nullptr);
	      std::__throw_runtime_error(__N("random_device: rdseed failed"));
	    }
	  __builtin_ia32_pause();
	}

      return val;
    }

#if USE_RDRAND
    unsigned int
    __attribute__ ((target("rdseed,rdrnd")))
    __x86_rdseed_rdrand(void*)
    {
      return __x86_rdseed(reinterpret_cast<void*>(&__x86_rdrand));
    }
#endif
#endif

#ifdef USE_DARN
    unsigned int
    __attribute__((target("cpu=power9")))
    __ppc_darn(void*)
    {
      const uint64_t failed = -1;
      unsigned int retries = 10;
      uint64_t val = __builtin_darn();
      while (val == failed) [[__unlikely__]]
	{
	  if (--retries == 0)
	    std::__throw_runtime_error(__N("random_device: darn failed"));
	  val = __builtin_darn();
	}
      return (uint32_t)val;
    }
#endif

#ifdef _GLIBCXX_USE_CRT_RAND_S
    unsigned int
    __winxp_rand_s(void*)
    {
      unsigned int val;
      if (::rand_s(&val) != 0)
	std::__throw_runtime_error(__N("random_device: rand_s failed"));
      return val;
    }
#endif

#ifdef _GLIBCXX_HAVE_GETENTROPY
    unsigned int
    __libc_getentropy(void*)
    {
      unsigned int val;
      if (::getentropy(&val, sizeof(val)) != 0)
	std::__throw_runtime_error(__N("random_device: getentropy failed"));
      return val;
    }
#endif

#ifdef _GLIBCXX_HAVE_ARC4RANDOM
    unsigned int
    __libc_arc4random(void*)
    {
      return ::arc4random();
    }
#endif

#ifdef USE_LCG
    // TODO: use this to seed std::mt19937 engine too.
    unsigned
    bad_seed(void* p) noexcept
    {
      // Poor quality seed based on hash of the current time and the address
      // of the object being seeded. Better than using the same default seed
      // for every object though.
      const uint64_t bits[] = {
	(uint64_t) chrono::system_clock::now().time_since_epoch().count(),
	(uint64_t) reinterpret_cast<uintptr_t>(p)
      };
      auto bytes = reinterpret_cast<const unsigned char*>(bits);
      // 32-bit FNV-1a hash
      uint32_t h = 2166136261u;
      for (unsigned i = 0; i < sizeof(bits); ++i)
	{
	  h ^= *bytes++;
	  h *= 16777619u;
	}
      return h;
    }

    // Same as std::minstd_rand0 but using unsigned not uint_fast32_t.
    using lcg_type
      = linear_congruential_engine<unsigned, 16807UL, 0UL, 2147483647UL>;

    inline lcg_type*
    construct_lcg_at(void* addr) noexcept
    {
      return ::new(addr) lcg_type(bad_seed(addr));
    }

    inline void
    destroy_lcg_at(void* addr) noexcept
    {
      static_cast<lcg_type*>(addr)->~lcg_type();
    }

    unsigned int
    __lcg(void* ptr) noexcept
    {
      auto& lcg = *static_cast<lcg_type*>(ptr);
      return lcg();
    }
#endif

    enum Which : unsigned {
      device_file = 1, prng = 2, rand_s = 4, getentropy = 8, arc4random = 16,
      rdseed = 64, rdrand = 128, darn = 256,
      any = 0xffff
    };

    constexpr Which
    operator|(Which l, Which r) noexcept
    { return Which(unsigned(l) | unsigned(r)); }

    inline Which
    which_source(random_device::result_type (*func [[maybe_unused]])(void*),
		 void* file [[maybe_unused]])
    {
#ifdef _GLIBCXX_USE_CRT_RAND_S
      if (func == &__winxp_rand_s)
	return rand_s;
#endif

#ifdef USE_RDSEED
#ifdef USE_RDRAND
      if (func == &__x86_rdseed_rdrand)
	return rdseed;
#endif
      if (func == &__x86_rdseed)
	return rdseed;
#endif

#ifdef USE_RDRAND
      if (func == &__x86_rdrand)
	return rdrand;
#endif

#ifdef USE_DARN
      if (func == &__ppc_darn)
	return darn;
#endif

#ifdef _GLIBCXX_USE_DEV_RANDOM
      if (file != nullptr)
	return device_file;
#endif

#ifdef _GLIBCXX_HAVE_ARC4RANDOM
      if (func == __libc_arc4random)
	return arc4random;
#endif

#ifdef _GLIBCXX_HAVE_GETENTROPY
      if (func == __libc_getentropy)
	return getentropy;
#endif

#ifdef USE_LCG
      if (func == &__lcg)
	return prng;
#endif

#ifdef USE_MT19937
      return prng;
#endif

      return any; // should be unreachable
    }
  }

  void
  random_device::_M_init(const std::string& token)
  {
#ifdef USE_MT19937
    // If no real random device is supported then use the mt19937 engine.
    _M_init_pretr1(token);
    return;
#else

    _M_file = nullptr;
    _M_func = nullptr;
    _M_fd = -1;

    const char* fname [[gnu::unused]] = nullptr;

    Which which;

    if (token == "default")
      {
	which = any;
	fname = "/dev/urandom";
      }
#ifdef USE_RDSEED
    else if (token == "rdseed")
      which = rdseed;
#endif // USE_RDSEED
#ifdef USE_RDRAND
    else if (token == "rdrand" || token == "rdrnd")
      which = rdrand;
#endif // USE_RDRAND
#ifdef USE_DARN
    else if (token == "darn")
      which = darn;
#endif
#if defined USE_RDRAND || defined USE_RDSEED || defined USE_DARN
    else if (token == "hw" || token == "hardware")
      which = rdrand | rdseed | darn;
#endif
#ifdef _GLIBCXX_USE_CRT_RAND_S
    else if (token == "rand_s")
      which = rand_s;
#endif // _GLIBCXX_USE_CRT_RAND_S
#ifdef _GLIBCXX_HAVE_GETENTROPY
    else if (token == "getentropy")
      which = getentropy;
#endif // _GLIBCXX_HAVE_GETENTROPY
#ifdef _GLIBCXX_HAVE_ARC4RANDOM
    else if (token == "arc4random")
      which = arc4random;
#endif // _GLIBCXX_HAVE_ARC4RANDOM
#ifdef _GLIBCXX_USE_DEV_RANDOM
    else if (token == "/dev/urandom" || token == "/dev/random")
      {
	fname = token.c_str();
	which = device_file;
      }
#endif // _GLIBCXX_USE_DEV_RANDOM
#ifdef USE_LCG
    else if (token == "prng")
      which = prng;
#endif
    else
      std::__throw_runtime_error(
	  __N("random_device::random_device(const std::string&):"
	      " unsupported token"));

#ifdef _GLIBCXX_USE_CRT_RAND_S
    if (which & rand_s)
    {
      _M_func = &__winxp_rand_s;
      return;
    }
#endif // _GLIBCXX_USE_CRT_RAND_S

#ifdef USE_RDSEED
    if (which & rdseed)
    {
      unsigned int eax, ebx, ecx, edx;
      // Check availability of cpuid and, for now at least, also the
      // CPU signature for Intel and AMD.
      if (__get_cpuid_max(0, &ebx) > 0
	  && (ebx == signature_INTEL_ebx || ebx == signature_AMD_ebx))
	{
	  // CPUID.(EAX=07H, ECX=0H):EBX.RDSEED[bit 18]
	  __cpuid_count(7, 0, eax, ebx, ecx, edx);
	  if (ebx & bit_RDSEED)
	    {
#ifdef USE_RDRAND
	      // CPUID.01H:ECX.RDRAND[bit 30]
	      __cpuid(1, eax, ebx, ecx, edx);
	      if (ecx & bit_RDRND)
		{
		  _M_func = &__x86_rdseed_rdrand;
		  return;
		}
#endif
	      _M_func = &__x86_rdseed;
	      return;
	    }
	}
    }
#endif // USE_RDSEED

#ifdef USE_RDRAND
    if (which & rdrand)
    {
      unsigned int eax, ebx, ecx, edx;
      // Check availability of cpuid and, for now at least, also the
      // CPU signature for Intel and AMD.
      if (__get_cpuid_max(0, &ebx) > 0
	  && (ebx == signature_INTEL_ebx || ebx == signature_AMD_ebx))
	{
	  // CPUID.01H:ECX.RDRAND[bit 30]
	  __cpuid(1, eax, ebx, ecx, edx);
	  if (ecx & bit_RDRND)
	    {
	      _M_func = &__x86_rdrand;
	      return;
	    }
	}
    }
#endif // USE_RDRAND

#ifdef USE_DARN
    if (which & darn)
      {
	if (__builtin_cpu_supports("darn"))
	  {
	    _M_func = &__ppc_darn;
	    return;
	  }
      }
#endif // USE_DARN

#ifdef _GLIBCXX_HAVE_ARC4RANDOM
    if (which & arc4random)
      {
	_M_func = &__libc_arc4random;
	return;
      }
#endif // _GLIBCXX_HAVE_ARC4RANDOM

#ifdef _GLIBCXX_HAVE_GETENTROPY
    if (which & getentropy)
      {
	unsigned int i;
	if (::getentropy(&i, sizeof(i)) == 0) // On linux the syscall can fail.
	  {
	    _M_func = &__libc_getentropy;
	    return;
	  }
      }
#endif // _GLIBCXX_HAVE_GETENTROPY

#ifdef _GLIBCXX_USE_DEV_RANDOM
    if (which & device_file)
    {
#ifdef USE_POSIX_FILE_IO
      _M_fd = ::open(fname, O_RDONLY);
      if (_M_fd != -1)
	{
	  // Set _M_file to non-null so that _M_fini() will do clean up.
	  _M_file = &_M_fd;
	  return;
	}
#else // USE_POSIX_FILE_IO
      _M_file = static_cast<void*>(std::fopen(fname, "rb"));
      if (_M_file)
	return;
#endif // USE_POSIX_FILE_IO
    }
#endif // _GLIBCXX_USE_DEV_RANDOM

#ifdef USE_LCG
    // Either "prng" was requested explicitly, or "default" was requested
    // but nothing above worked, use a PRNG.
    if (which & prng)
    {
      static_assert(sizeof(lcg_type) <= sizeof(_M_fd), "");
      static_assert(alignof(lcg_type) <= alignof(_M_fd), "");
      _M_file = construct_lcg_at(&_M_fd);
      _M_func = &__lcg;
      return;
    }
#endif

    std::__throw_runtime_error(
	__N("random_device::random_device(const std::string&):"
	    " device not available"));
#endif // USE_MT19937
  }

  // This function is called by _M_init for targets that use mt19937 for
  // randomness, and by code compiled against old releases of libstdc++.
  void
  random_device::_M_init_pretr1(const std::string& token)
  {
#ifdef USE_MT19937
    unsigned long seed = 5489UL;
    if (token != "default" && token != "mt19937" && token != "prng")
      {
	const char* nptr = token.c_str();
	char* endptr;
	seed = std::strtoul(nptr, &endptr, 0);
	if (*nptr == '\0' || *endptr != '\0')
	  std::__throw_runtime_error(__N("random_device::_M_init_pretr1"
					 "(const std::string&)"));
      }
    _M_mt.seed(seed);
#else
    // Convert old default token "mt19937" or numeric seed tokens to "default".
    if (token == "mt19937" || std::isdigit((unsigned char)token[0]))
      _M_init("default");
    else
      _M_init(token);
#endif
  }

  // Called by old ABI version of random_device::_M_init(const std::string&).
  void
  random_device::_M_init(const char* s, size_t len)
  {
    const std::string token(s, len);
#ifdef USE_MT19937
    _M_init_pretr1(token);
#else
    _M_init(token);
#endif
  }

  void
  random_device::_M_fini()
  {
    // _M_file == nullptr means no resources to free.
    if (!_M_file)
      return;

#if USE_LCG
    if (_M_func == &__lcg)
      {
	destroy_lcg_at(_M_file);
	return;
      }
#endif

#ifdef USE_POSIX_FILE_IO
    ::close(_M_fd);
    _M_fd = -1;
#else
    std::fclose(static_cast<FILE*>(_M_file));
#endif
    _M_file = nullptr;
  }

  random_device::result_type
  random_device::_M_getval()
  {
#ifdef USE_MT19937
    return _M_mt();
#else

    if (_M_func)
      return _M_func(_M_file);

    result_type ret;
    void* p = &ret;
    size_t n = sizeof(result_type);
#ifdef USE_POSIX_FILE_IO
    do
      {
	const int e = ::read(_M_fd, p, n);
	if (e > 0)
	  {
	    n -= e;
	    p = static_cast<char*>(p) + e;
	  }
	else if (e != -1 || errno != EINTR)
	  __throw_runtime_error(__N("random_device could not be read"));
      }
    while (n > 0);
#else // USE_POSIX_FILE_IO
    const size_t e = std::fread(p, n, 1, static_cast<FILE*>(_M_file));
    if (e != 1)
      __throw_runtime_error(__N("random_device could not be read"));
#endif // USE_POSIX_FILE_IO

    return ret;
#endif // USE_MT19937
  }

  // Only called by code compiled against old releases of libstdc++.
  // Forward the call to _M_getval() and let it decide what to do.
  random_device::result_type
  random_device::_M_getval_pretr1()
  { return _M_getval(); }

  double
  random_device::_M_getentropy() const noexcept
  {
    const int max = sizeof(result_type) * __CHAR_BIT__;

    switch(which_source(_M_func, _M_file))
    {
    case rdrand:
    case rdseed:
    case darn:
      return (double) max;
    case arc4random:
    case getentropy:
      return (double) max;
    case rand_s:
    case prng:
      return 0.0;
    case device_file:
      // handled below
      break;
    default:
      return 0.0;
    }

#if defined _GLIBCXX_USE_DEV_RANDOM \
    && defined _GLIBCXX_HAVE_SYS_IOCTL_H && defined RNDGETENTCNT

#ifdef USE_POSIX_FILE_IO
    const int fd = _M_fd;
#else
    const int fd = ::fileno(static_cast<FILE*>(_M_file));
#endif
    if (fd < 0)
      return 0.0;

    int ent;
    if (::ioctl(fd, RNDGETENTCNT, &ent) < 0)
      return 0.0;

    if (ent < 0)
      return 0.0;

    if (ent > max)
      ent = max;

    return static_cast<double>(ent);
#else
    return 0.0;
#endif // _GLIBCXX_USE_DEV_RANDOM && _GLIBCXX_HAVE_SYS_IOCTL_H && RNDGETENTCNT
  }

#ifdef USE_MT19937
  template class mersenne_twister_engine<
    uint_fast32_t,
    32, 624, 397, 31,
    0x9908b0dfUL, 11,
    0xffffffffUL, 7,
    0x9d2c5680UL, 15,
    0xefc60000UL, 18, 1812433253UL>;
#endif // USE_MT19937

#ifdef USE_LCG
  template class
    linear_congruential_engine<unsigned, 16807UL, 0UL, 2147483647UL>;
  template struct __detail::_Mod<unsigned, 2147483647UL, 16807UL, 0UL>;
#endif
}
#endif // _GLIBCXX_USE_C99_STDINT_TR1
Commit	Line	Data
a8c3f4c9 UD	1	// random -- C++ --
a8c3f4c9 UD	2
83ffe9cd	3	// Copyright (C) 2012-2023 Free Software Foundation, Inc.
a8c3f4c9 UD	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 3, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
	24
34a2b755	25	#define _GLIBCXX_USE_CXX11_ABI 1
b0c0d878 JW	26	#define _CRT_RAND_S // define this before including <stdlib.h> to get rand_s
b0c0d878 JW	27
a8c3f4c9 UD	28	#include <random>
a8c3f4c9 UD	29
645708ab JW	30	#ifdef _GLIBCXX_USE_C99_STDINT_TR1
645708ab JW	31
a8c3f4c9 UD	32	#if defined __i386__ \|\| defined __x86_64__
a8c3f4c9 UD	33	# include <cpuid.h>
b0c0d878 JW	34	# ifdef _GLIBCXX_X86_RDRAND
	35	# define USE_RDRAND 1
	36	# endif
	37	# ifdef _GLIBCXX_X86_RDSEED
	38	# define USE_RDSEED 1
	39	# endif
d9ebf0ce	40	#elif defined __powerpc64__ && defined __BUILTIN_CPU_SUPPORTS__
5997e6a6	41	# define USE_DARN 1
a8c3f4c9 UD	42	#endif
a8c3f4c9 UD	43
0b546684	44	#include <cerrno>
821f6f1b	45	#include <cstdio>
8bc19959	46	#include <cctype> // For std::isdigit.
821f6f1b	47
b0c0d878	48	#if defined _GLIBCXX_HAVE_UNISTD_H && defined _GLIBCXX_HAVE_FCNTL_H
94e7477f	49	# include <unistd.h>
b0c0d878 JW	50	# include <fcntl.h>
	51	// Use POSIX open, close, read etc. instead of ISO fopen, fclose, fread
	52	# define USE_POSIX_FILE_IO
94e7477f	53	#endif
a8c3f4c9	54
78aa76df XR	55	#ifdef _GLIBCXX_HAVE_SYS_IOCTL_H
	56	# include <sys/ioctl.h>
	57	#endif
	58
dac867c9 UB	59	#ifdef _GLIBCXX_HAVE_LINUX_TYPES_H
	60	# include <linux/types.h>
	61	#endif
	62
78aa76df XR	63	#ifdef _GLIBCXX_HAVE_LINUX_RANDOM_H
	64	# include <linux/random.h>
	65	#endif
	66
b0c0d878 JW	67	#ifdef _GLIBCXX_USE_CRT_RAND_S
	68	# include <stdlib.h>
	69	#endif
	70
3439657b JW	71	#ifdef _GLIBCXX_HAVE_GETENTROPY
	72	# include <unistd.h>
	73	#endif
	74
	75	#if defined _GLIBCXX_USE_CRT_RAND_S \|\| defined _GLIBCXX_USE_DEV_RANDOM \
	76	\|\| _GLIBCXX_HAVE_GETENTROPY
5f070ba2	77	// The OS provides a source of randomness we can use.
b0c0d878	78	# pragma GCC poison _M_mt
5997e6a6	79	#elif defined USE_RDRAND \|\| defined USE_RDSEED \|\| defined USE_DARN
5f070ba2 JW	80	// Hardware instructions might be available, but use cpuid checks at runtime.
	81	# pragma GCC poison _M_mt
	82	// If the runtime cpuid checks fail we'll use a linear congruential engine.
	83	# define USE_LCG 1
b0c0d878 JW	84	#else
	85	// Use the mt19937 member of the union, as in previous GCC releases.
	86	# define USE_MT19937 1
	87	#endif
	88
5f070ba2 JW	89	#ifdef USE_LCG
	90	# include <chrono>
	91	#endif
	92
a8c3f4c9 UD	93	namespace std _GLIBCXX_VISIBILITY(default)
a8c3f4c9 UD	94	{
a8c3f4c9 UD	95	namespace
a8c3f4c9 UD	96	{
b0c0d878	97	#if USE_RDRAND
a8c3f4c9 UD	98	unsigned int
a8c3f4c9 UD	99	__attribute__ ((target("rdrnd")))
b0c0d878	100	__x86_rdrand(void*)
a8c3f4c9 UD	101	{
	102	unsigned int retries = 100;
	103	unsigned int val;
	104
2627e3b7	105	while (__builtin_ia32_rdrand32_step(&val) == 0) [[__unlikely__]]
a8c3f4c9	106	if (--retries == 0)
b0c0d878	107	std::__throw_runtime_error(__N("random_device: rdrand failed"));
a8c3f4c9 UD	108
	109	return val;
	110	}
	111	#endif
b0c0d878 JW	112
	113	#if USE_RDSEED
	114	unsigned int
	115	__attribute__ ((target("rdseed")))
a2d196e7	116	__x86_rdseed(void* fallback)
b0c0d878 JW	117	{
	118	unsigned int retries = 100;
	119	unsigned int val;
	120
2627e3b7	121	while (__builtin_ia32_rdseed_si_step(&val) == 0) [[__unlikely__]]
b0c0d878 JW	122	{
b0c0d878 JW	123	if (--retries == 0)
a2d196e7 JW	124	{
	125	if (auto f = reinterpret_cast<unsigned int()(void)>(fallback))
	126	return f(nullptr);
	127	std::__throw_runtime_error(__N("random_device: rdseed failed"));
	128	}
b0c0d878 JW	129	__builtin_ia32_pause();
	130	}
	131
	132	return val;
	133	}
a2d196e7 JW	134
	135	#if USE_RDRAND
	136	unsigned int
	137	__attribute__ ((target("rdseed,rdrnd")))
	138	__x86_rdseed_rdrand(void*)
	139	{
	140	return __x86_rdseed(reinterpret_cast<void*>(&__x86_rdrand));
	141	}
	142	#endif
b0c0d878 JW	143	#endif
b0c0d878 JW	144
5997e6a6 JW	145	#ifdef USE_DARN
	146	unsigned int
	147	__attribute__((target("cpu=power9")))
	148	__ppc_darn(void*)
	149	{
	150	const uint64_t failed = -1;
	151	unsigned int retries = 10;
	152	uint64_t val = __builtin_darn();
	153	while (val == failed) [[__unlikely__]]
	154	{
	155	if (--retries == 0)
	156	std::__throw_runtime_error(__N("random_device: darn failed"));
	157	val = __builtin_darn();
	158	}
	159	return (uint32_t)val;
	160	}
	161	#endif
	162
b0c0d878 JW	163	#ifdef _GLIBCXX_USE_CRT_RAND_S
	164	unsigned int
	165	__winxp_rand_s(void*)
	166	{
	167	unsigned int val;
	168	if (::rand_s(&val) != 0)
	169	std::__throw_runtime_error(__N("random_device: rand_s failed"));
	170	return val;
	171	}
	172	#endif
5f070ba2	173
3439657b JW	174	#ifdef _GLIBCXX_HAVE_GETENTROPY
	175	unsigned int
	176	__libc_getentropy(void*)
	177	{
	178	unsigned int val;
	179	if (::getentropy(&val, sizeof(val)) != 0)
	180	std::__throw_runtime_error(__N("random_device: getentropy failed"));
	181	return val;
	182	}
	183	#endif
	184
	185	#ifdef _GLIBCXX_HAVE_ARC4RANDOM
	186	unsigned int
	187	__libc_arc4random(void*)
	188	{
	189	return ::arc4random();
	190	}
	191	#endif
	192
5f070ba2 JW	193	#ifdef USE_LCG
	194	// TODO: use this to seed std::mt19937 engine too.
	195	unsigned
	196	bad_seed(void* p) noexcept
	197	{
	198	// Poor quality seed based on hash of the current time and the address
	199	// of the object being seeded. Better than using the same default seed
	200	// for every object though.
	201	const uint64_t bits[] = {
	202	(uint64_t) chrono::system_clock::now().time_since_epoch().count(),
	203	(uint64_t) reinterpret_cast<uintptr_t>(p)
	204	};
	205	auto bytes = reinterpret_cast<const unsigned char*>(bits);
	206	// 32-bit FNV-1a hash
	207	uint32_t h = 2166136261u;
	208	for (unsigned i = 0; i < sizeof(bits); ++i)
	209	{
	210	h ^= *bytes++;
	211	h *= 16777619u;
	212	}
	213	return h;
	214	}
	215
	216	// Same as std::minstd_rand0 but using unsigned not uint_fast32_t.
	217	using lcg_type
	218	= linear_congruential_engine<unsigned, 16807UL, 0UL, 2147483647UL>;
	219
	220	inline lcg_type*
	221	construct_lcg_at(void* addr) noexcept
	222	{
	223	return ::new(addr) lcg_type(bad_seed(addr));
	224	}
	225
	226	inline void
	227	destroy_lcg_at(void* addr) noexcept
	228	{
	229	static_cast<lcg_type*>(addr)->~lcg_type();
	230	}
	231
	232	unsigned int
	233	__lcg(void* ptr) noexcept
	234	{
	235	auto& lcg = static_cast<lcg_type>(ptr);
	236	return lcg();
	237	}
	238	#endif
58f339fc	239
5997e6a6	240	enum Which : unsigned {
3439657b	241	device_file = 1, prng = 2, rand_s = 4, getentropy = 8, arc4random = 16,
5997e6a6	242	rdseed = 64, rdrand = 128, darn = 256,
58f339fc JW	243	any = 0xffff
	244	};
	245
5997e6a6 JW	246	constexpr Which
	247	operator\|(Which l, Which r) noexcept
	248	{ return Which(unsigned(l) \| unsigned(r)); }
	249
58f339fc JW	250	inline Which
	251	which_source(random_device::result_type (func [[maybe_unused]])(void),
	252	void* file [[maybe_unused]])
	253	{
	254	#ifdef _GLIBCXX_USE_CRT_RAND_S
	255	if (func == &__winxp_rand_s)
	256	return rand_s;
	257	#endif
	258
	259	#ifdef USE_RDSEED
	260	#ifdef USE_RDRAND
	261	if (func == &__x86_rdseed_rdrand)
	262	return rdseed;
	263	#endif
	264	if (func == &__x86_rdseed)
	265	return rdseed;
	266	#endif
	267
	268	#ifdef USE_RDRAND
	269	if (func == &__x86_rdrand)
	270	return rdrand;
	271	#endif
	272
5997e6a6 JW	273	#ifdef USE_DARN
	274	if (func == &__ppc_darn)
	275	return darn;
	276	#endif
	277
58f339fc JW	278	#ifdef _GLIBCXX_USE_DEV_RANDOM
	279	if (file != nullptr)
	280	return device_file;
	281	#endif
	282
3439657b JW	283	#ifdef _GLIBCXX_HAVE_ARC4RANDOM
	284	if (func == __libc_arc4random)
	285	return arc4random;
	286	#endif
	287
	288	#ifdef _GLIBCXX_HAVE_GETENTROPY
	289	if (func == __libc_getentropy)
	290	return getentropy;
	291	#endif
	292
58f339fc JW	293	#ifdef USE_LCG
	294	if (func == &__lcg)
	295	return prng;
	296	#endif
	297
	298	#ifdef USE_MT19937
	299	return prng;
	300	#endif
	301
	302	return any; // should be unreachable
	303	}
a8c3f4c9 UD	304	}
a8c3f4c9 UD	305
a8c3f4c9 UD	306	void
	307	random_device::_M_init(const std::string& token)
	308	{
b0c0d878 JW	309	#ifdef USE_MT19937
	310	// If no real random device is supported then use the mt19937 engine.
	311	_M_init_pretr1(token);
	312	return;
	313	#else
	314
	315	_M_file = nullptr;
	316	_M_func = nullptr;
	317	_M_fd = -1;
	318
	319	const char* fname [[gnu::unused]] = nullptr;
b0c0d878	320
58f339fc	321	Which which;
a8c3f4c9 UD	322
	323	if (token == "default")
	324	{
5f070ba2	325	which = any;
b0c0d878	326	fname = "/dev/urandom";
b0c0d878 JW	327	}
	328	#ifdef USE_RDSEED
	329	else if (token == "rdseed")
	330	which = rdseed;
	331	#endif // USE_RDSEED
	332	#ifdef USE_RDRAND
	333	else if (token == "rdrand" \|\| token == "rdrnd")
	334	which = rdrand;
	335	#endif // USE_RDRAND
5997e6a6 JW	336	#ifdef USE_DARN
	337	else if (token == "darn")
	338	which = darn;
	339	#endif
	340	#if defined USE_RDRAND \|\| defined USE_RDSEED \|\| defined USE_DARN
	341	else if (token == "hw" \|\| token == "hardware")
	342	which = rdrand \| rdseed \| darn;
	343	#endif
b0c0d878 JW	344	#ifdef _GLIBCXX_USE_CRT_RAND_S
	345	else if (token == "rand_s")
	346	which = rand_s;
	347	#endif // _GLIBCXX_USE_CRT_RAND_S
3439657b JW	348	#ifdef _GLIBCXX_HAVE_GETENTROPY
	349	else if (token == "getentropy")
	350	which = getentropy;
	351	#endif // _GLIBCXX_HAVE_GETENTROPY
	352	#ifdef _GLIBCXX_HAVE_ARC4RANDOM
	353	else if (token == "arc4random")
	354	which = arc4random;
	355	#endif // _GLIBCXX_HAVE_ARC4RANDOM
b0c0d878 JW	356	#ifdef _GLIBCXX_USE_DEV_RANDOM
	357	else if (token == "/dev/urandom" \|\| token == "/dev/random")
	358	{
	359	fname = token.c_str();
	360	which = device_file;
	361	}
	362	#endif // _GLIBCXX_USE_DEV_RANDOM
5f070ba2 JW	363	#ifdef USE_LCG
	364	else if (token == "prng")
	365	which = prng;
	366	#endif
b0c0d878 JW	367	else
	368	std::__throw_runtime_error(
	369	__N("random_device::random_device(const std::string&):"
	370	" unsupported token"));
	371
b0c0d878	372	#ifdef _GLIBCXX_USE_CRT_RAND_S
5f070ba2 JW	373	if (which & rand_s)
	374	{
	375	_M_func = &__winxp_rand_s;
	376	return;
	377	}
b0c0d878	378	#endif // _GLIBCXX_USE_CRT_RAND_S
5f070ba2	379
b0c0d878	380	#ifdef USE_RDSEED
5f070ba2 JW	381	if (which & rdseed)
	382	{
	383	unsigned int eax, ebx, ecx, edx;
	384	// Check availability of cpuid and, for now at least, also the
	385	// CPU signature for Intel and AMD.
	386	if (__get_cpuid_max(0, &ebx) > 0
	387	&& (ebx == signature_INTEL_ebx \|\| ebx == signature_AMD_ebx))
	388	{
	389	// CPUID.(EAX=07H, ECX=0H):EBX.RDSEED[bit 18]
	390	__cpuid_count(7, 0, eax, ebx, ecx, edx);
	391	if (ebx & bit_RDSEED)
	392	{
a2d196e7	393	#ifdef USE_RDRAND
5f070ba2 JW	394	// CPUID.01H:ECX.RDRAND[bit 30]
	395	__cpuid(1, eax, ebx, ecx, edx);
	396	if (ecx & bit_RDRND)
	397	{
	398	_M_func = &__x86_rdseed_rdrand;
	399	return;
	400	}
a2d196e7	401	#endif
5f070ba2 JW	402	_M_func = &__x86_rdseed;
	403	return;
	404	}
	405	}
	406	}
b0c0d878	407	#endif // USE_RDSEED
5f070ba2	408
b0c0d878	409	#ifdef USE_RDRAND
5f070ba2 JW	410	if (which & rdrand)
	411	{
	412	unsigned int eax, ebx, ecx, edx;
	413	// Check availability of cpuid and, for now at least, also the
	414	// CPU signature for Intel and AMD.
	415	if (__get_cpuid_max(0, &ebx) > 0
	416	&& (ebx == signature_INTEL_ebx \|\| ebx == signature_AMD_ebx))
	417	{
	418	// CPUID.01H:ECX.RDRAND[bit 30]
	419	__cpuid(1, eax, ebx, ecx, edx);
	420	if (ecx & bit_RDRND)
	421	{
	422	_M_func = &__x86_rdrand;
	423	return;
	424	}
	425	}
	426	}
b0c0d878	427	#endif // USE_RDRAND
5f070ba2	428
5997e6a6 JW	429	#ifdef USE_DARN
	430	if (which & darn)
	431	{
	432	if (__builtin_cpu_supports("darn"))
	433	{
	434	_M_func = &__ppc_darn;
	435	return;
	436	}
	437	}
	438	#endif // USE_DARN
	439
3439657b JW	440	#ifdef _GLIBCXX_HAVE_ARC4RANDOM
	441	if (which & arc4random)
	442	{
	443	_M_func = &__libc_arc4random;
	444	return;
	445	}
	446	#endif // _GLIBCXX_HAVE_ARC4RANDOM
	447
	448	#ifdef _GLIBCXX_HAVE_GETENTROPY
	449	if (which & getentropy)
	450	{
	451	unsigned int i;
	452	if (::getentropy(&i, sizeof(i)) == 0) // On linux the syscall can fail.
	453	{
	454	_M_func = &__libc_getentropy;
	455	return;
	456	}
	457	}
	458	#endif // _GLIBCXX_HAVE_GETENTROPY
	459
b0c0d878	460	#ifdef _GLIBCXX_USE_DEV_RANDOM
5f070ba2 JW	461	if (which & device_file)
5f070ba2 JW	462	{
b0c0d878	463	#ifdef USE_POSIX_FILE_IO
5f070ba2 JW	464	_M_fd = ::open(fname, O_RDONLY);
	465	if (_M_fd != -1)
	466	{
	467	// Set _M_file to non-null so that _M_fini() will do clean up.
	468	_M_file = &_M_fd;
b0c0d878	469	return;
5f070ba2 JW	470	}
	471	#else // USE_POSIX_FILE_IO
	472	_M_file = static_cast<void*>(std::fopen(fname, "rb"));
	473	if (_M_file)
	474	return;
b0c0d878	475	#endif // USE_POSIX_FILE_IO
5f070ba2	476	}
b0c0d878	477	#endif // _GLIBCXX_USE_DEV_RANDOM
5f070ba2 JW	478
	479	#ifdef USE_LCG
	480	// Either "prng" was requested explicitly, or "default" was requested
	481	// but nothing above worked, use a PRNG.
	482	if (which & prng)
	483	{
	484	static_assert(sizeof(lcg_type) <= sizeof(_M_fd), "");
	485	static_assert(alignof(lcg_type) <= alignof(_M_fd), "");
	486	_M_file = construct_lcg_at(&_M_fd);
	487	_M_func = &__lcg;
	488	return;
b0c0d878	489	}
5f070ba2 JW	490	#endif
5f070ba2 JW	491
b0c0d878 JW	492	std::__throw_runtime_error(
	493	__N("random_device::random_device(const std::string&):"
	494	" device not available"));
	495	#endif // USE_MT19937
a8c3f4c9 UD	496	}
a8c3f4c9 UD	497
b0c0d878 JW	498	// This function is called by _M_init for targets that use mt19937 for
b0c0d878 JW	499	// randomness, and by code compiled against old releases of libstdc++.
a8c3f4c9 UD	500	void
a8c3f4c9 UD	501	random_device::_M_init_pretr1(const std::string& token)
a8c3f4c9	502	{
b0c0d878 JW	503	#ifdef USE_MT19937
b0c0d878 JW	504	unsigned long seed = 5489UL;
5f070ba2	505	if (token != "default" && token != "mt19937" && token != "prng")
b0c0d878 JW	506	{
	507	const char* nptr = token.c_str();
	508	char* endptr;
	509	seed = std::strtoul(nptr, &endptr, 0);
	510	if (nptr == '\0' \|\| endptr != '\0')
	511	std::__throw_runtime_error(__N("random_device::_M_init_pretr1"
	512	"(const std::string&)"));
	513	}
	514	_M_mt.seed(seed);
	515	#else
	516	// Convert old default token "mt19937" or numeric seed tokens to "default".
8bc19959	517	if (token == "mt19937" \|\| std::isdigit((unsigned char)token[0]))
b0c0d878 JW	518	_M_init("default");
	519	else
	520	_M_init(token);
	521	#endif
a8c3f4c9 UD	522	}
a8c3f4c9 UD	523
aeedf077 JW	524	// Called by old ABI version of random_device::_M_init(const std::string&).
	525	void
	526	random_device::_M_init(const char* s, size_t len)
	527	{
	528	const std::string token(s, len);
	529	#ifdef USE_MT19937
	530	_M_init_pretr1(token);
	531	#else
	532	_M_init(token);
	533	#endif
	534	}
	535
a8c3f4c9 UD	536	void
	537	random_device::_M_fini()
	538	{
b0c0d878 JW	539	// _M_file == nullptr means no resources to free.
	540	if (!_M_file)
	541	return;
	542
5f070ba2 JW	543	#if USE_LCG
	544	if (_M_func == &__lcg)
	545	{
	546	destroy_lcg_at(_M_file);
	547	return;
	548	}
	549	#endif
	550
b0c0d878 JW	551	#ifdef USE_POSIX_FILE_IO
	552	::close(_M_fd);
	553	_M_fd = -1;
	554	#else
	555	std::fclose(static_cast<FILE*>(_M_file));
	556	#endif
	557	_M_file = nullptr;
a8c3f4c9 UD	558	}
	559
	560	random_device::result_type
	561	random_device::_M_getval()
	562	{
b0c0d878 JW	563	#ifdef USE_MT19937
	564	return _M_mt();
	565	#else
	566
b0c0d878	567	if (_M_func)
5f070ba2	568	return _M_func(_M_file);
a8c3f4c9	569
b0c0d878 JW	570	result_type ret;
b0c0d878 JW	571	void* p = &ret;
a2b4d73d	572	size_t n = sizeof(result_type);
b0c0d878	573	#ifdef USE_POSIX_FILE_IO
a2b4d73d JW	574	do
a2b4d73d JW	575	{
b0c0d878	576	const int e = ::read(_M_fd, p, n);
a2b4d73d JW	577	if (e > 0)
	578	{
	579	n -= e;
	580	p = static_cast<char*>(p) + e;
	581	}
	582	else if (e != -1 \|\| errno != EINTR)
	583	__throw_runtime_error(__N("random_device could not be read"));
	584	}
	585	while (n > 0);
b0c0d878	586	#else // USE_POSIX_FILE_IO
a2b4d73d JW	587	const size_t e = std::fread(p, n, 1, static_cast<FILE*>(_M_file));
	588	if (e != 1)
	589	__throw_runtime_error(__N("random_device could not be read"));
b0c0d878	590	#endif // USE_POSIX_FILE_IO
42b6aad9	591
b0c0d878 JW	592	return ret;
b0c0d878 JW	593	#endif // USE_MT19937
a8c3f4c9 UD	594	}
a8c3f4c9 UD	595
b0c0d878 JW	596	// Only called by code compiled against old releases of libstdc++.
b0c0d878 JW	597	// Forward the call to _M_getval() and let it decide what to do.
a8c3f4c9 UD	598	random_device::result_type
a8c3f4c9 UD	599	random_device::_M_getval_pretr1()
b0c0d878	600	{ return _M_getval(); }
a8c3f4c9	601
78aa76df XR	602	double
	603	random_device::_M_getentropy() const noexcept
	604	{
58f339fc JW	605	const int max = sizeof(result_type) * __CHAR_BIT__;
	606
	607	switch(which_source(_M_func, _M_file))
	608	{
	609	case rdrand:
	610	case rdseed:
5997e6a6	611	case darn:
58f339fc	612	return (double) max;
3439657b JW	613	case arc4random:
	614	case getentropy:
	615	return (double) max;
58f339fc JW	616	case rand_s:
	617	case prng:
	618	return 0.0;
	619	case device_file:
	620	// handled below
	621	break;
	622	default:
	623	return 0.0;
	624	}
	625
b0c0d878 JW	626	#if defined _GLIBCXX_USE_DEV_RANDOM \
b0c0d878 JW	627	&& defined _GLIBCXX_HAVE_SYS_IOCTL_H && defined RNDGETENTCNT
78aa76df	628
b0c0d878 JW	629	#ifdef USE_POSIX_FILE_IO
	630	const int fd = _M_fd;
	631	#else
	632	const int fd = ::fileno(static_cast<FILE*>(_M_file));
	633	#endif
78aa76df XR	634	if (fd < 0)
	635	return 0.0;
	636
	637	int ent;
b0c0d878	638	if (::ioctl(fd, RNDGETENTCNT, &ent) < 0)
78aa76df XR	639	return 0.0;
	640
	641	if (ent < 0)
	642	return 0.0;
	643
b6784361 JW	644	if (ent > max)
b6784361 JW	645	ent = max;
78aa76df XR	646
	647	return static_cast<double>(ent);
	648	#else
	649	return 0.0;
b0c0d878	650	#endif // _GLIBCXX_USE_DEV_RANDOM && _GLIBCXX_HAVE_SYS_IOCTL_H && RNDGETENTCNT
78aa76df XR	651	}
78aa76df XR	652
b0c0d878	653	#ifdef USE_MT19937
a8c3f4c9 UD	654	template class mersenne_twister_engine<
	655	uint_fast32_t,
	656	32, 624, 397, 31,
	657	0x9908b0dfUL, 11,
	658	0xffffffffUL, 7,
	659	0x9d2c5680UL, 15,
	660	0xefc60000UL, 18, 1812433253UL>;
b0c0d878	661	#endif // USE_MT19937
5f070ba2 JW	662
	663	#ifdef USE_LCG
	664	template class
	665	linear_congruential_engine<unsigned, 16807UL, 0UL, 2147483647UL>;
	666	template struct __detail::_Mod<unsigned, 2147483647UL, 16807UL, 0UL>;
	667	#endif
a8c3f4c9	668	}
b0c0d878	669	#endif // _GLIBCXX_USE_C99_STDINT_TR1