fast.h 2.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  1. #pragma once
  2. #include "lcg_engine.h"
  3. #include "common_ops.h"
  4. #include <util/generic/bitops.h>
  5. #include <util/system/platform.h>
  6. // based on http://www.pcg-random.org/. See T*FastRng* family below.
  7. struct TPCGMixer {
  8. static inline ui32 Mix(ui64 x) noexcept {
  9. const ui32 xorshifted = ((x >> 18u) ^ x) >> 27u;
  10. const ui32 rot = x >> 59u;
  11. return RotateBitsRight(xorshifted, rot);
  12. }
  13. };
  14. using TFastRng32Base = TLcgRngBase<TLcgIterator<ui64, ULL(6364136223846793005)>, TPCGMixer>;
  15. using TReallyFastRng32Base = TLcgRngBase<TFastLcgIterator<ui64, ULL(6364136223846793005), ULL(1)>, TPCGMixer>;
  16. class IInputStream;
  17. struct TFastRng32: public TCommonRNG<ui32, TFastRng32>, public TFastRng32Base {
  18. inline TFastRng32(ui64 seed, ui32 seq)
  19. : TFastRng32Base(seed, seq)
  20. {
  21. }
  22. TFastRng32(IInputStream& entropy);
  23. };
  24. // faster than TFastRng32, but have only one possible stream sequence
  25. struct TReallyFastRng32: public TCommonRNG<ui32, TReallyFastRng32>, public TReallyFastRng32Base {
  26. inline TReallyFastRng32(ui64 seed)
  27. : TReallyFastRng32Base(seed)
  28. {
  29. }
  30. TReallyFastRng32(IInputStream& entropy);
  31. };
  32. class TFastRng64: public TCommonRNG<ui64, TFastRng64> {
  33. public:
  34. struct TArgs {
  35. TArgs(ui64 seed) noexcept;
  36. TArgs(IInputStream& entropy);
  37. ui64 Seed1;
  38. ui64 Seed2;
  39. ui32 Seq1;
  40. ui32 Seq2;
  41. };
  42. TFastRng64(ui64 seed1, ui32 seq1, ui64 seed2, ui32 seq2) noexcept;
  43. /*
  44. * simplify constructions like
  45. * TFastRng64 rng(17);
  46. * TFastRng64 rng(Seek()); //from any IInputStream
  47. */
  48. inline TFastRng64(const TArgs& args) noexcept
  49. : TFastRng64(args.Seed1, args.Seq1, args.Seed2, args.Seq2)
  50. {
  51. }
  52. inline ui64 GenRand() noexcept {
  53. const ui64 x = R1_.GenRand();
  54. const ui64 y = R2_.GenRand();
  55. return (x << 32) | y;
  56. }
  57. inline void Advance(ui64 delta) noexcept {
  58. R1_.Advance(delta);
  59. R2_.Advance(delta);
  60. }
  61. private:
  62. TFastRng32Base R1_;
  63. TFastRng32Base R2_;
  64. };
  65. namespace NPrivate {
  66. template <typename T>
  67. struct TFastRngTraits;
  68. template <>
  69. struct TFastRngTraits<ui32> {
  70. using TResult = TReallyFastRng32;
  71. };
  72. template <>
  73. struct TFastRngTraits<ui64> {
  74. using TResult = TFastRng64;
  75. };
  76. } // namespace NPrivate
  77. template <typename T>
  78. using TFastRng = typename ::NPrivate::TFastRngTraits<T>::TResult;