Seekable xoshiro256++

seek_xoshiro256pp.cpp

#include <cstdint>
#include <array>
#include <cstdio>
#include <cassert>

#include <iostream>

namespace {

uint64_t GetRdRand() noexcept
{
    uint8_t ok;
    uint64_t r1 = 0;
    for (int i = 0; i < 10; ++i) {
        __asm__ volatile (".byte 0x48, 0x0f, 0xc7, 0xf0; setc %1" : "=a"(r1), "=q"(ok) :: "cc"); // rdrand %rax
        if (ok) break;
        __asm__ volatile ("pause");
    }
    return r1;
}

template<int N>
constexpr inline uint64_t Rotl(uint64_t x) noexcept { return (x << N) | (x >> (64 - N)); }

/** Xoshiro256++, see https://prng.di.unimi.it/ */
class XoShiRo256PP
{
    /** The internal state (4 64-bit integers). */
    std::array<uint64_t, 4> m_s;

    /** SplitMix64 RNG, used to initialize the state. */
    static inline uint64_t SplitMix64(uint64_t& x) noexcept
    {
        uint64_t z = (x += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

public:
    /** Initialization from a seed. */
    explicit XoShiRo256PP(uint64_t seed) noexcept
    {
        m_s[0] = SplitMix64(seed);
        m_s[1] = SplitMix64(seed);
        m_s[2] = SplitMix64(seed);
        m_s[3] = SplitMix64(seed);
    }

    /** Generate the next pseudorandom number. */
    uint64_t operator()() noexcept
    {
        const uint64_t result = Rotl<32>(m_s[0] + m_s[3]) + m_s[0];
        const uint64_t t = m_s[1] << 17;
        m_s[2] ^= m_s[0];
        m_s[3] ^= m_s[1];
        m_s[1] ^= m_s[2];
        m_s[0] ^= m_s[3];
        m_s[2] ^= t;
        m_s[3] = Rotl<45>(m_s[3]);
        return result;
    }

private:
    /** State transition multiplication-by-256 matrix.
     *
     * To implement jumps, we observe that the xoshiro256++ state transition function is
     * effectively a multiplication of a GF(2) 256*256 matrix M with the vector of state bits.
     * Repeated state transitions are multiplications with powers of M.
     *
     * This matrix M has a characteristic polynomial:
     *
     * p(x) = x^256 + x^241 + x^240 + x^239 + x^238 + x^229 + x^228 + x^227 + x^226 + x^221 +
     *        x^220 + x^219 + x^218 + x^217 + x^216 + x^213 + x^212 + x^211 + x^210 + x^209 +
     *        x^207 + x^206 + x^203 + x^201 + x^200 + x^196 + x^195 + x^192 + x^186 + x^183 +
     *        x^181 + x^180 + x^178 + x^175 + x^174 + x^173 + x^171 + x^170 + x^168 + x^167 +
     *        x^166 + x^163 + x^162 + x^161 + x^160 + x^157 + x^154 + x^153 + x^149 + x^146 +
     *        x^144 + x^143 + x^140 + x^139 + x^138 + x^137 + x^136 + x^135 + x^130 + x^128 +
     *        x^121 + x^119 + x^101 + x^99  + x^97  + x^96  + x^95  + x^94  + x^91  + x^90  +
     *        x^89  + x^87  + x^86  + x^85  + x^84  + x^83  + x^82  + x^80  + x^76  + x^75  +
     *        x^73  + x^70  + x^68  + x^67  + x^66  + x^65  + x^63  + x^60  + x^59  + x^58  +
     *        x^56  + x^52  + x^48  + x^46  + x^45  + x^43  + x^42  + x^41  + x^40  + x^37  +
     *        x^35  + x^33  + x^32  + x^31  + x^29  + x^28  + x^23  + x^22  + x^21  + x^20  +
     *        x^15  + x^14  + x^13  + x^12  + 1
     *
     * By the Cayley-Hamilton theorem, p(M) = 0. This means M^256 + M^241 + ... + M^12 + 1 = 0,
     * allowing us to rewrite M^256 as M^241 + ... + M^12 + 1, and by extension, any (sum of)
     * powers of M as a sum of just the 0th through 255th powers. In other words, we can represent
     * the powers of M as vectors with basis B = <I, M, M^2, ..., M^255>.
     *
     * Given a vector over B for M^i, we can find the vector for M^(i+1) by shifting every
     * coefficient up by one, and if the M^255 coefficient was a 1, adding p(M) - M^256 back in.
     * This is effectively a linear feedback shift register (LFSR). We can also define
     * multiplication between these vectors as the equivalent polynomial operation: interpret as
     * polynomials in x, multiply them, and reduce modulo p(x). As p(x) is an irreducible
     * polynomial, this results in a degree-256 field extension of GF(2), and we see that the space
     * spanned by powers of M is isomorphic to GF(2^256).
     *
     * As a characteristic-2 field, it has the property that squaring is a GF(2)-linear operation;
     * e.g. (M^a + M^b)^2 = M^(2*a) + M^(2*b), also known as the Freshman's dream. From that it
     * follows that repeated squaring is also linear, and in the table below we make use of that:
     * MUL256 is the matrix whose row i contains (M^i)^(2^8) = M^(256*i), written as integers whose
     * bits contain the coefficients over basis B. Thus, given a vector v over B representing M^i,
     * MUL256*v gives the vector representing M^(256*i).
     */
    static constexpr std::array<uint64_t, 4> MUL256[256] = {
        {0x0000000000000001, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000},
        {0x9d116f2bb0f0f001, 0x0280002bcefd1a5e, 0x04b4edcf26259f85, 0x0003c03c3f3ecb19},
        {0xc7327d130e34b489, 0x81f675e7a4ef7d84, 0x6dd49b656055c9da, 0xbe7976372e930435},
        {0x1546163553a8bf4e, 0xdf8408bef0866758, 0x7eca03f4f6b1e60b, 0x8cff57fe55c5f06d},
        {0x060106bbbe4ff028, 0x1be1d76854ddda93, 0x8456faeb6230d984, 0x65507439cf43f0e2},
        {0x9d5a8918f488052a, 0xbf212ebaceea061a, 0xde401c7651ed7ea9, 0x705bd66c3b2b58de},
        {0x2f121b2b79c58914, 0xdca1a0f9e89ab189, 0x0dd3ee7079a6dd3f, 0xbaaf47861466c19f},
        {0xd1d35253d56559ff, 0x9e6507a719b531eb, 0x3abacfbce94448fe, 0xdc997ccb62e3d354},
        {0x876c2301125a85c0, 0x15fe822628b16f04, 0x3c8ca36ec9a74fa7, 0x51edef31819e01ff},
        {0xf3f6d08dbec2f0b5, 0xa7e71d8a120470fe, 0x3c4478b7ec545bc7, 0x3a49176ee90676c1},
        {0x1ec5f22cf9282570, 0x7a35edaef9692623, 0x73a4cf99b14b622b, 0x93b8c505f25cb0be},
        {0x0573f5e43baf0c0a, 0x25dd6ea130acaa3e, 0x7fa2d54e9872d80d, 0x04153a2acc6b090f},
        {0x195f824bdd4cd00a, 0xb162081eba5f7a35, 0x9fead7e44eafdb96, 0x3611b9c8607b74a9},
        {0xb8763f5d93c0d709, 0x1becba890be71139, 0x22dad55ac2252366, 0xa356f53e02c2c991},
        {0xc1c3da7f588e1172, 0xb0478674c36c9e18, 0xac2c9fc00bd5bcaa, 0xb33bbb70d42480d0},
        {0x0357b77957de437f, 0xa502f2cb45e45865, 0x97b8f9bdbc62f61c, 0xdabfebe24293e393},
        {0xd7f4e8da7e228b85, 0xd638d47ec5bcf595, 0xaa6eb691cbf9ce10, 0x0f41cce3698fad39},
        {0x3c07937f3896a086, 0x2779f2793d5e0421, 0x813a072f65fc3e9b, 0x8d7575d606822f53},
        {0x3d15ed410790c557, 0xe0e1879f8696e349, 0x0ea7ffba4df42f39, 0x69f71727c4f86832},
        {0xefdb3f40e71ee4f3, 0x36dbd2554f30e45e, 0xb126c3b381b83a42, 0x819b1d3455275f7e},
        {0xaf056e9f5d528839, 0x86e35ae447b22aaa, 0x4713afd93b637af0, 0xb7b79be926c70e9c},
        {0x56a444547a838fc1, 0x6fc47060f5525186, 0x7f2e18e3e86a6e54, 0x1022d1f61421c28a},
        {0x52c5d1508aef2c7e, 0x5c9ba70f2cd3f92e, 0x6a2cd3f2f2494b51, 0x0e9420642c021775},
        {0xfbe1815e603d450c, 0xa880d9c2f558987b, 0x40ae8e720f68d2ca, 0x86bbb9d017aaf539},
        {0xa82bd707a5c0bbcd, 0x557d6bd4a66701d2, 0x27e81077d42d6234, 0x70b2bd03010451a7},
        {0x96001ec856ecad1e, 0x02a2b752ef9b18ef, 0xe1a18545ee2463ee, 0xffa54b37520d6ef3},
        {0x8f66f19f35a6f5c7, 0x07374ac3e72a26d0, 0x9f496a85c61485ff, 0xcfd30a2e551a56be},
        {0xb4ee202b89c858d1, 0xf0cbf71586da6e65, 0xaa98651848063422, 0x2e67669a24b37880},
        {0x65d0b5d6d3a4d7d0, 0x1d1d60bcd2d09eb4, 0xc9337102457d65f7, 0xff41296d258343e3},
        {0xd3eea4a28c496a02, 0xfa2172b4ada58cb8, 0x26ba5c2581486c35, 0x3e56dddb50694038},
        {0xf9e1520a24777a2a, 0x105ab923b1acbf10, 0x15a948a05722fa9f, 0x54799b7c19c8de2e},
        {0x8a7ad878d7f15ec3, 0xdf24d1a351ed9b58, 0x9e99e0af7e21922c, 0x143fbcd91cb71ded},
        {0x669da12373880674, 0xb1df898a4a6f1548, 0x32104b94fe2534d3, 0xda66e09e52b341d1},
        {0xf7671672ee26abab, 0xdc166e37849117c0, 0x1ffad81a82464f7c, 0x259d5b23b52cbebf},
        {0x5c3b9d6fd42716d3, 0x25d5b90b3754a7c9, 0x918b06a70ec7c08b, 0x855fe4b6979125c9},
        {0x9803d0f16654bcb9, 0x5c2b3a55df70c45e, 0x5db0fedf9a21ff3d, 0xdbcbcbae092e368b},
        {0x7d62314b75eefa48, 0x84819fcd89386b0b, 0x76740e452c49241e, 0xeb612f9b530b2252},
        {0x8b70d2157934af4a, 0x8f61835574070299, 0x2c0046be35eea904, 0xa073bd5c8f9e2371},
        {0x72bcd1dc4fbed43c, 0xdd3b7be9a73e0afc, 0xdcdc40403931abd0, 0x1b9784963ec6e6f8},
        {0x0fb43adb3518749b, 0x738c7550674f7d7d, 0x742a5324e8d0180a, 0x43b449fb359e85f2},
        {0x0d62783cbb52918c, 0x6e84ce91fe2e29d7, 0xd74a28cef5a8be79, 0x90479e96a10c1e56},
        {0x1b3d82d60695d9d2, 0x05290bccffe3a1a7, 0xff194729f937be41, 0xf211983b5fcaa9f6},
        {0x478d523b3f673b5b, 0x11f4ddb66f5049f0, 0xd9e7db300652ff3e, 0x9143dda8b1b071f3},
        {0x77eba103dc8a64d2, 0x52940c7c59a6b6e7, 0x8a5f571738646fa7, 0x6d2f9ca2cab74e49},
        {0xcc5bcc0907656522, 0xa6346d21ed4a08e0, 0xb128bf15e78bac54, 0x4d7b32638cc09e0c},
        {0xfa041feca111dedd, 0x2e6215fd2b017e1c, 0xe34bd92e65305eaa, 0xdc8dc45c7a2220d7},
        {0x5e33660ea984cc99, 0x72c039ea5c211487, 0x4423046015f9a9c4, 0x8cc08acf3a2625ef},
        {0x730f3bd6fd090d62, 0x53c5b412972e0ee1, 0xdee7deb5814d98e2, 0x0f39c662e91a307e},
        {0x2f8694c414ab14d4, 0xb9aa0df930906447, 0x8d238798b0472623, 0x47038a0bcd5cad87},
        {0xd280ce9fea591d08, 0xaa404542a9462e62, 0x7d99513bd0d4eb74, 0x8c9c0c4eed8b7bba},
        {0x6594a40aff725baa, 0xe55c0be3058b1487, 0x2928e5417d145fbb, 0x17e11b27376efe27},
        {0xcad0f51a9840d667, 0x67b7aabfcf9ba78e, 0x33a542cea6508fca, 0xeb57490bd25d2658},
        {0xe75756177ab9c56d, 0xd47a11df53aeecc7, 0xa5753448ec01cc25, 0x8ea1703f6e53a268},
        {0xfea6063f9b0769bc, 0x2cc69a0af546688d, 0xbd4199aa6a13f062, 0xa27f077219d2822c},
        {0xde647513e5e96a99, 0x460415d5b06f0b02, 0x5920d0edc9f55029, 0xad32190798d96789},
        {0x1067aea4f4e97576, 0x97bd8c42f1f61d5d, 0x501f1f1747f42381, 0x60f897ee7d2bf447},
        {0x2feb50ab077bac1a, 0xa9b302d307a6d345, 0x64dcf3fb942666ef, 0x3972a4b76a145204},
        {0x0356bc48ceb75a3a, 0xd8f94b0a96b5c970, 0xb27bc0c52eb81f7a, 0xaeae31b2e63114d1},
        {0x3af403ad3617d9a0, 0x953052ceaa5d840f, 0xae1615ea7488bd48, 0x400e576f899776f1},
        {0x91493362a4c28040, 0x961b554ea31829db, 0xca4a1463df185a48, 0xfe00960840abca5f},
        {0x3d2afe40f946e351, 0x0e12ce3b21db887c, 0xc8e142b2266db54d, 0xe51f7ba517aa347a},
        {0x9250ab1ccd1cb90e, 0x246385fa11ccc590, 0x1714cc3a4aeaa8ab, 0xc8c3111203d2ea3a},
        {0x1e7c041232e4087b, 0x090c9a65a7934f3e, 0x061da9ea588dc7b3, 0xf7ead4bac59f91e6},
        {0xf7a8341b4a7e187d, 0x33d6c1ea6a9252bd, 0x4c2321a8faa8f2f4, 0x5e0d77d2d0edeca1},
        {0x4f20eb915e780231, 0x3886af219b885248, 0x023ecbee3f717fce, 0x3cec2c375bef249c},
        {0x25538ddb147dd218, 0x9c6282f0158e56b0, 0x34303b574d4a374e, 0x64fe5b2d7c463918},
        {0x65d4393828a84e44, 0x4cfce571e4b92336, 0x866610457781f352, 0xd452d943d62b4acf},
        {0xe8e98a4564b91e0e, 0xdaa0c9c98089059a, 0x63bb25aaa8ed7a29, 0x81f4f3d5d3b49712},
        {0xfc8145d2114c1f04, 0x9b5868cd1dffa061, 0x2b7a66d2e3a87897, 0x11b9cbb1997452b0},
        {0x6766526c895d4d56, 0x4f56ec2c47522245, 0xb56821517a2ffd71, 0x9430b8312d098d04},
        {0x90d76cdc95066e2a, 0xda15693a1f222de3, 0xd1acbf3fdec71deb, 0xabeba601447ed6e1},
        {0x671f7eaef295ad88, 0x4a738567038e7a81, 0x08341b7c3d24f3d6, 0x49596a0b2dc9bdb7},
        {0x700eeae93502e8ed, 0xb282158785ab86ae, 0x16f1d7d4bd2c1a85, 0x3f4ec0fa56f94891},
        {0x823408a63d29b5cd, 0xcaa340601b8b08bc, 0xac2b02a44d248102, 0x0b3deb9884828350},
        {0xfbfac64005e869ec, 0x03fc3d4521c9ce3b, 0xaee18c68a78c36eb, 0xf152fe304dd3cc84},
        {0x9bc884fad5765611, 0xbba8b8a10dea274a, 0x7e405e392af078a8, 0x1bad5e77bc43c745},
        {0x7acad89602ba5a5d, 0x17e7069cf2953d8a, 0x193c95c6e2cd5b54, 0xa169f915754cd633},
        {0xc818c37e7a4eb3da, 0x6b066372a0b2e5d5, 0xdf97a82a09056f7f, 0x756d532b4e978888},
        {0xfbbde6403c9b123c, 0x12ad3a5375f8e560, 0x9c2bc0d048bd1dba, 0xfa6aa8951053ac4f},
        {0xd23e2cd6d09d7cde, 0x7b74760c368b9cdf, 0xf7d5cf4d83dedadb, 0x94e7966e92e9fc90},
        {0x16cdc7c2405806d1, 0xe327175dddf96c76, 0x02708019a1bca727, 0x8e0ee0a81a0ece4b},
        {0x17f4c2a61a65a8e2, 0x99be494c03b6a174, 0x47a0768dff261304, 0xa2bb049debfe5aa0},
        {0x3ee186fea1df895b, 0x22173c164c49a78d, 0xf82130122dbc5015, 0x49fc17a62f906fb1},
        {0x24814fd179b071f4, 0x8554124304132067, 0x62c9f31ec1fe16bb, 0x58d58c6261be4b45},
        {0xdf1b47963815bf68, 0x702cce8dc0664350, 0x88d8dddad49991af, 0xa042ab290705dc59},
        {0x07bf88ab1c893609, 0x93435269e68e08fd, 0x1e24f3cba239949f, 0xd8f63619ae6864ae},
        {0x8a192a6c5c06b425, 0x50d246b826139162, 0x132792e1c5767a15, 0x4ba8f7c99cf9bcff},
        {0x39198d7bdc621cda, 0x79087a517ec38abb, 0xa44955ce71893a99, 0x8aef5c98acfc7efb},
        {0xe5ff5dbc9e7d1494, 0xde673bf6d47b69da, 0xfa3d2770f93a4d0b, 0x7aac85eb8e83753e},
        {0x599b9189a0a2b073, 0xb0adb31ca8448a38, 0xe2d20f4ae2cd81aa, 0x3c21a35c70d53714},
        {0xc87e948919a630f1, 0xc29353538a5c8a1c, 0x682ac2c6566ef78b, 0xfb41478f46ef06f2},
        {0x5e161e5f67332236, 0xff9195172e990542, 0xb92e95796d76a0cb, 0x259ab186088bdf3f},
        {0x6486e873cc466ff7, 0xb31912c917acb8dc, 0xc5be884fb3198d15, 0x10faeac16592014b},
        {0x1edffdde5ccfa348, 0x9e6c43c945d3f651, 0x1acd334964a7e796, 0x79d006063618b8ac},
        {0xb25ebcb415ad1268, 0xcf5d6d0b2a36dfc5, 0xcc885cb56e02fdca, 0x42680e778224005d},
        {0x0439ab45daecc534, 0xaccf5d3f77db065d, 0xcf79f87c121a00c9, 0xb2ad9c84cc093a75},
        {0x95c3c96295982aaa, 0x48c424ddaf4a3e60, 0xdd2fc0e089525844, 0xb80482ab05b509fc},
        {0xb71513b4419ba3c9, 0x9f4d589ac246357f, 0x42c230f15a8eb05f, 0x354f782daa6cda3a},
        {0xcdc443944b8506c6, 0x0a28f5915303730b, 0x165238525ca914a4, 0xd6efca5ecf613203},
        {0x69503ca95b608ef9, 0xbcfdafe461752eac, 0xb438cc093d79b98f, 0x2ab51dd584772641},
        {0xd2cab21839d5c8db, 0x07720fb70718d96f, 0x6ac541c9281456c8, 0xb3304454a654e320},
        {0x9414f479c0f59b82, 0x7c36628d5804e0d2, 0xd0a4b6765c8057ab, 0x1710e350cf1f4254},
        {0x9f343a72a0f2908f, 0x6d440c6a52841429, 0x0e4c07f4e612a871, 0x0e7042b1b68c29d0},
        {0x17ed4326a1463ce2, 0xd0973e2b98d9845a, 0xbdc3c46947750f28, 0xba29782f4260fad9},
        {0x5b3f9cbfeccd0bb3, 0x8f79c05b27116662, 0x3500418ca30cbeba, 0xbf08b73e83f62d8e},
        {0x8a18e51e3f8ec72e, 0xaae7fcc89b7d3016, 0x1703da07cb86a738, 0xcb060011117882cd},
        {0xdc325e1a5bf52be9, 0x995443feece12860, 0x8b73e2a7dda3cc80, 0x7eba59aff007139e},
        {0xe53df1767895d103, 0x54395f145b723db6, 0xcaebbb62f6de3947, 0x55495e3a8ee684b6},
        {0x277b80049a714055, 0x27d550865770f5bc, 0xe1e3964ff180b64e, 0x42a6da9928271d57},
        {0x0cc9a13d43ede548, 0x1d165617d0c644b3, 0x5917a842348eb4c8, 0x41e49ba6b115dec4},
        {0x8534cd1cf73c1b87, 0xcc854d5b47bc0c01, 0x14f31bd05cbcac1f, 0xd45451f135cba71e},
        {0x2c95f5c4d5f454c4, 0xfa3b09da8cef6493, 0x17e322a153ccaa2c, 0x3b5d836277d2f0fd},
        {0x39b2c0ad5f2ab37b, 0xa63f750d20127ba4, 0xd40755ca5df5f6ce, 0x0de5205cce51ff62},
        {0x7b24e6743ef51d12, 0xb60c28a0d8392544, 0xb89a142400da3918, 0xc68355be861a4ae1},
        {0x9ecb43f6f3c025e8, 0xf10bda6bce212c84, 0x86f1a2cdf24574c1, 0x447babf5b2348154},
        {0xa6ae904b71187573, 0x7b8f456b0c3718aa, 0xaa5d16015c324759, 0xa2dc321e25d1d5bf},
        {0x7a901d043335d4b0, 0x95a25309b5e8cf07, 0x86612f0f1a808241, 0x74903c8f3d791419},
        {0x30937f88cde76997, 0xf998163265cd77b5, 0x57fb2dc888824c9c, 0x0e196f6b590f3c73},
        {0x1a780ca7d035ceba, 0x03d1733257ad7b46, 0x652028086d2d21f5, 0x062e98e8eb8f1934},
        {0x98aa9ef969ca17e4, 0x826d185542a3e74b, 0x3ed47e36577f9f97, 0x1b0f9a80c6cab626},
        {0xed5d1ef94a623f5f, 0xdee18bb64e83b4bf, 0xc891abfe32c0a417, 0x635768006219fab6},
        {0x91a6f2650679c7b6, 0x45d5c9dad8e30d47, 0x1499d3280d173519, 0x0c7376a06c192c81},
        {0x24acc30ecf1cb882, 0xdbe8d90900ae49f2, 0xf1c9b9dd9493739d, 0xe9f2afb9deabcba7},
        {0xbd240a7dc7e3f692, 0x0cbab18eadec30e9, 0xf0a948ed80c307b7, 0xe215b1f667e89800},
        {0x890f30e544ac214c, 0xec5db1935a11a6fd, 0x6895e91d5c9d47d9, 0x8c7aaffdb075605e},
        {0x05076eab6dd624ce, 0xbe34c3d5a6228fb7, 0x8f3cbb5d00cf7b63, 0x8f98982853864c75},
        {0xbdc0df21e0ef00c7, 0x579e61532290ef23, 0xdc29eac54aa9f961, 0x59d34fbc8340a9ab},
        {0x45796e8cb39021b0, 0x25607e82382252f9, 0x3dae8c427787ed5f, 0xa3c91def53327761},
        {0x449b3ae793888c8c, 0xc3ce2f061f077568, 0xa69393ac0d837e54, 0x1a9dcf944ae47603},
        {0x97b6a2d613e4166c, 0x17433be1b75322df, 0xe0d17b2146ca96b4, 0x278675ea7aba6d4f},
        {0x2346856cd995d612, 0x80ec1c07b7a31fc7, 0xa38bfb1ef1f82414, 0xf182039dbb867eb9},
        {0x45dfc24e5d226b89, 0x0baef1992fc8c87d, 0x981cbdf7fd7a2867, 0x8d3884c0fc8fb96d},
        {0x93f3ac93c473eed3, 0xb9b19b7013eb634a, 0x6e7b6ae1f88fd2ff, 0xc12b97c7a732fd2c},
        {0xf73eeb448b43119a, 0x34d7af433b62dffb, 0x35c9effa9ea589ae, 0x3e346c084f004793},
        {0xc006720a4030aaeb, 0x7291f348b8df1f90, 0xc966b5381ec953f3, 0x6b452504a3ad33b8},
        {0x8705ef56988c6b27, 0x35d3bc862b4b3053, 0x83abcc107914654b, 0x72545ff934b55a3e},
        {0x655286e7c17baacd, 0xe6c8cbb03c545aab, 0x04c3d977f3300ff4, 0x831c5d0b67ae68c3},
        {0xbb52badf2277eadd, 0xf03f7e1fb3d9b6fb, 0x2f7f35d1f0693034, 0xf22f248988143616},
        {0x1cc27392a5acc28f, 0xc304d2cccc219857, 0xb43b89844b451884, 0x311ad80ac65a2029},
        {0xe6a120af4364c795, 0x5fc0ad21e279b011, 0x24e9fcabbe655179, 0x677b3203d5eab87c},
        {0x8c1bc19a0bc3c877, 0x7f10397ef06589c7, 0xfa572829056c020a, 0x34f25f7ea43c5240},
        {0xad330e6ef9bae352, 0x64dc2c53d1e76880, 0xd5db226da1f7f7f1, 0x723e36991306dc82},
        {0x78cf1f31921867c5, 0xf421ad4139c5f4c9, 0x0977c35c5948d9d2, 0x1858edd55b8938c8},
        {0x774c304b4c75480b, 0x46f892eb26a47c58, 0x589575b15f762c94, 0x0f4877eaeecb178a},
        {0xe13e7e7c33e928ec, 0xc88a73a1ab9300f3, 0x454c8475b6e54167, 0x1b94dd28dc37b471},
        {0x8d8500245741f37e, 0x8dffcb6a6f8928d3, 0x2ea865ae1cecdd8d, 0xb61324428227e711},
        {0x5071141533b4f76b, 0xc4439d2203366f90, 0x162215d7b1074990, 0xdb3fde8bc98dfc51},
        {0x583697d85cfb5cb4, 0x174e7cc7cd119c6b, 0x443969e7cf4d2a2c, 0x7966c92f20c4e321},
        {0xdf678087c8c9296c, 0x9a04ddf9c2a1fbbb, 0x30a5aeddc83a7e1f, 0x4fe5ce0101881fa5},
        {0xbfabaa3df06dc940, 0x183f0d94d75b8c8f, 0x68590ac7b83a1992, 0xfc549ab63635ad10},
        {0xe3ded375923be38c, 0x3eda8f2e08792d8a, 0x7dd500f990db26c9, 0x2b4944fbe7f28649},
        {0xef67f8fd6681e80c, 0xd6dd057ea59e1249, 0x308bda995aa6fda1, 0x3dc4351855bcc6ec},
        {0x22664bca6b607eed, 0x109101dfdc907f2d, 0xa4db3b83672a8e0b, 0xa89e492f80e28668},
        {0x1eabfd09d8f87f2d, 0x71115b458cc574e6, 0xa800992628874022, 0xc45d3d9429edbd84},
        {0x8b6b270d0c1d89d6, 0x3876914c710d166b, 0xe277230f7f2ec32f, 0x4101ff29c2a5fe62},
        {0x693f193b33c12a71, 0xbbbc35aed8aa3906, 0x576c90fc726582af, 0xe06db73d2a1955f6},
        {0x4cd46c606a0bfbb9, 0x8bb1bc49a739579b, 0xaa8385d9fe0299b8, 0xe975550f9efb3552},
        {0x6c22369d8c666e89, 0x6823ddb584c44cbc, 0xefb622df5ef81344, 0xd234ec92d850c0f8},
        {0xb585b69e14db7a0c, 0xe5411d6fd4478f93, 0x566cdd254e6e3c81, 0x5a4e309f9ae951c1},
        {0x5e2f638c25ea7944, 0x6ee04e21d4837af6, 0x54677b9015d89339, 0xffee20d6e563f69a},
        {0xfdf526f0dadc8101, 0x65fbe56b399b3ad0, 0x3790c946ac3c702e, 0x40d750f8940b1f46},
        {0x2a41be3920531f51, 0xc3d1d6090f3bd70b, 0xecc112f748b1e768, 0xa484160f30992e7d},
        {0x8e071f7371ba85e3, 0xe3405e38b1a7cab5, 0x95b6a39032c32d9a, 0x223a642387d9f6f9},
        {0xf297c978e0c7d197, 0x545877a162814778, 0x13d581518d6433f0, 0x6c65aa08794e8924},
        {0x441dde88fefa92f3, 0x3f21f59f33b4056a, 0x4f550a39f983f66c, 0x3d6c88932703ff06},
        {0x9112d568da7661b1, 0xf768795c33d683ce, 0x50e7b6b4345ebd9a, 0xd6a757d16963a44f},
        {0x612dd8e489027fc8, 0x4e6f94db2ace2f8d, 0x247cf4d7098debb5, 0x77090a38e361fba1},
        {0x240e0f1b79ad7295, 0xedb9ec4db0dd88ca, 0xdac7d60b923e6dd3, 0xf62add64e9b92902},
        {0xc28b538de4e1833c, 0x4dadbefced6c03b4, 0x47255ef22ccffa7a, 0x853dedabf1ca4229},
        {0xa080d8e0de8ea4db, 0x770ee0754620e672, 0xaccda2e15f68f11b, 0x63f852fe13351b09},
        {0xe9ca754ae577f5cd, 0x3cac0d67705276f3, 0x813c60726c2913a8, 0x531b7a770e433b39},
        {0x8a445c3afdd8e0e9, 0x45ddbe07a2deae65, 0xaea021277e3e76ac, 0x7e35f1be415932f3},
        {0x1368e3c049a782f2, 0x19c7242312d911ed, 0x6d72cd49ea990ab9, 0xe17e5996b40e97ff},
        {0xb33e366fc1f61505, 0xb0282759406959af, 0xbd7a65f02cfdf312, 0xa934d34046cd363f},
        {0xe6c4c0c7e7d9ce4d, 0x48d2d9af1a1b8de0, 0x85e60ffb2e4793dd, 0x4ee95579fc3655fe},
        {0xd0ec2feb00dd0698, 0xf3f5bbb162d001eb, 0x1a45cef793b456fc, 0x6e923362b21659e3},
        {0xad96463abaeaea2d, 0x6286c6a96e28fcfa, 0x94668618a1850262, 0xb3020cab4f788a32},
        {0x61df0241d372a424, 0x61fbe6cc63c7c58b, 0xd2fec7496a878bc6, 0x673993ac558ad5a0},
        {0x1a41ba31ccfaab64, 0x398b3bfcf1356349, 0xe1e2d202513b8505, 0x1f1eee5b27a61892},
        {0xc6f8b78a6f4ca2cd, 0x55b9fc9e435ec781, 0xa8c41e869ae2faea, 0x84cf77f4ba57ab1a},
        {0xf70182400bfa66f6, 0xa8a3c4b3d0942538, 0x77880deeef3f66ba, 0xa440e7ea0eea426b},
        {0x5a63d94c8d54543d, 0x691816b12383850e, 0x3fe8aefc5b62f227, 0x3abb99bcf7d4e8c4},
        {0xf0086ed524d8e696, 0x82b42d4b28d12fc4, 0x78907a3d86f124e7, 0x0f00fdb45605aa43},
        {0xe4b6578213ecfd81, 0x5243f7f0ed4442d5, 0x8bcdd039f14ae663, 0xd87c2fe379aaa68d},
        {0x718b67a16a46eeaa, 0x0dc99d0d2013c9d2, 0xa753563ee8285bcb, 0x71eb39bc3d0df708},
        {0x816908fa54541196, 0x80ca1f2905330b9c, 0x8936eeefef9e1211, 0x8c0d6921113d9753},
        {0x472df85ab8fb00cd, 0x2190425981680dd7, 0x12c2a382cf9c7941, 0xb6021b635d1fb370},
        {0x1980788e52508b37, 0xba7aa0bef39e6d99, 0x7c5dbdb2cc529042, 0xb14c1ddd3853b2fb},
        {0x65440c8997e8642c, 0x737987c7dda476d9, 0xd946bc14f1930ab4, 0x07f697d79bab2257},
        {0x6c84966cfa5f2c73, 0x13bcf2148b8ee9eb, 0xf77255ae26fba9e2, 0x892f95924b863a91},
        {0xdf2a5f22ff08d925, 0x47d7aefbf77ac475, 0xa983a79deca148d7, 0x98af2184d552b138},
        {0x1355b38d283a5f13, 0x4ed08ae8029cf5ff, 0x352df4f96b45eeed, 0xdc7c470b3c506d29},
        {0x86978e6a9f971090, 0x56283fcee33d4823, 0x53066a5e6a4c5ac2, 0x14188b2e30722ed1},
        {0x88689f99a4bf2a90, 0xa2d38d5b580ddcfa, 0x1e699dc7f8aeb3a6, 0x26fff71bef95900f},
        {0x7b721001fa0ca07b, 0xd42a3e6bca59b950, 0x3edbc316510cc42d, 0xfb3685ea0ecec614},
        {0xe1baba0acb454eaf, 0x32c035384da7c8bb, 0xd9e3d752ea59e7b9, 0xa200e35b421c1f80},
        {0xa350197d3af7af3d, 0xa3001fcbb10a18ee, 0xdc56a44daef3f6cf, 0x1d3a640066db9a1a},
        {0xd5bf331c9de04313, 0xb82f2e11fe24f5c0, 0xab63f82d1a53b045, 0x1cb854fed571b941},
        {0x222b2c8443b3a20f, 0xb772ff6348cdf683, 0xcfa83ba59ac75aef, 0xccbb8410784bc6b2},
        {0xb2229bd94bdc8eb2, 0xb722398a0b7cc7a0, 0xe969240a6f75a885, 0xc5d1a2c2d88bc29b},
        {0xfe05b3c16e5d70c0, 0xbb285cdbf4a00434, 0x4d1502d9854e272a, 0x9b35bd20f6336064},
        {0x0f63dcd1d32e3bb5, 0xb428b8199bfe649c, 0x9b1777cb7691e30f, 0x5a2422f7c76e08e2},
        {0x16c460ee2a1643f6, 0x43bd6d3bc852f3a1, 0xe8546675e38de0fe, 0x48755e67d4873f93},
        {0xbc6cc542527d9e60, 0x685f22c3870f8b45, 0xd73de50b126cf51b, 0xb52b1a461106f32e},
        {0xff37ca31036e48eb, 0x21d517b7b44c1cf6, 0xa3577107493f97c0, 0x68f53d8b2cd95ce2},
        {0xdd156e5a63303280, 0x3e777ad89b09e54d, 0xad59e2e11ddf4f71, 0x4627eb9e9a8e80e2},
        {0x5dac07915335eb93, 0x62432118fbba337a, 0x4c1262ba089e3c27, 0x286bae829ecd3d67},
        {0x6f9ba74e5090e0e9, 0xcc3b08674a72f14d, 0x527092c8c8b21ffe, 0x109e84e0374610f4},
        {0x906b94d5f7796e19, 0x99a460fc4cd5b594, 0xf7ebe41340a2b57b, 0xbe9e026358dd97fa},
        {0xff5f28960bde9f22, 0x321d3e7fbcfdfd2a, 0xb279e7bd278b6b28, 0x06a3838e59bbf93d},
        {0x239ef3d2cab6b5a2, 0x283a9d833be9a558, 0xea48e6f2a28b1145, 0x542ee7577b0db9a5},
        {0x26d0fbf2dd05fdc4, 0xfffe6b33e77b2748, 0xd11415a5a2786955, 0xfdb449a3f69e0d32},
        {0x704d502d3652ee6a, 0x0579c77ddeb403a1, 0x32bce74a9c03e296, 0xc980e38fc249e5bf},
        {0x9d9eafe072aaadb5, 0xf5ae7fec63877b70, 0x33e52ce4af1187ec, 0x01bef0627aec886d},
        {0x633630255c4c7e95, 0x58f9c498217f15fb, 0xfab710f23893c449, 0x0b0f21ecb63071a4},
        {0x28662272a6c6bf65, 0x6fe508d3438c7cb8, 0x26a82e5683a27138, 0x64ec6fef05f42bc7},
        {0x2c01134bff7304fc, 0x64cd4d04f034bae6, 0xd096e48f8a4b3986, 0xb26e305e871d862e},
        {0x3edd0153359b0a7b, 0xbb7e2e344ca8484f, 0xe6c0cd910a2d9a9d, 0x3ca5d9e4abc1de5a},
        {0x66615c7ec7ff7832, 0x5c99925ac5693fd9, 0x81cd08a44a3a58e7, 0x46de333d130ad7b7},
        {0x4eead78226f63704, 0x4021dd5df440b10e, 0xdad74d482525b835, 0xa115792d533ba4ba},
        {0x8225fc874941b90b, 0x14170ceb99621a2d, 0x7e2d57f0da4b3262, 0xed4431a833c6e25a},
        {0x1b6880e2f1d107c9, 0x87acaa07b06bbcb5, 0xbe4943d255643b4e, 0xde369d89c298c4ac},
        {0xb9429a1440882768, 0xae6be503769e6180, 0xaa5db7360a5b1986, 0xc6d1ce5dcad14424},
        {0xa5e617d6a44388bd, 0x83a88afa8450a7d6, 0xf366c4a6305c480a, 0x02c596fcb8c8b5bc},
        {0x30f5f3ae85c8eadc, 0xe234526d9f1c59aa, 0x4e65a940aab90b70, 0x2a00b5ae5a0930a1},
        {0x4756bfc73c00b23c, 0x3b4b557ec3a6a262, 0x2c011fbba7a7647c, 0x4cb0ea6bb0a3f452},
        {0x0b2aceaf0adff43c, 0x6ba8cd331b6227c9, 0x08ae91f4bb8bbaad, 0x0a4e6a33a0c9c68f},
        {0x128fafe42ce49486, 0x0382fcf348747cb3, 0xad6ba75970893a72, 0x5c6f406b5a0deb70},
        {0x8c35671ba70c0526, 0x6125e771093f3750, 0x29dd913f4bbf24bd, 0x960bdaac4b029a57},
        {0xd8a1d4ea23ed5ce0, 0x522a802f4edc5dcb, 0x0a2277917fac6095, 0x356d0051ac34340f},
        {0xee1bb49598368725, 0x1804e9f71509d840, 0x0328d79b7ff198d7, 0x632050d66c0daa39},
        {0x81c029fb8b7337e5, 0xdf70814351d81554, 0x50f447b686095a70, 0x748ccc3b6b39d670},
        {0xe35912294136f0ff, 0xcd3a33e29b6708d1, 0x126ebae8142a4ffc, 0x902c93c7e8c090bf},
        {0xacdcb5ee6e26fb3a, 0x64c90467e53df817, 0x0449da25a3014714, 0xf8f37eae6f90ec5d},
        {0xb23238712271a4d7, 0xe5940c926f4259b7, 0xdaef1c5635e6d88d, 0x01444d24c46db938},
        {0x879aa6b64a817b8e, 0x6f9217d7ac466960, 0xbad56c6952790c25, 0x027d1a4aa8a51ced},
        {0x127ab9a9e84243a6, 0x03211d89d53fecdc, 0xc772d3303c41f03f, 0xfac92b9c3b02b408},
        {0x29c99bd82aca4300, 0x3956d0c62469d48c, 0xbf613ab5b509d61c, 0x08d25ee3b1a7b2c5},
        {0xd9e836fa35dc7d84, 0x9b6c3b6db0b7f788, 0xfd59a722d2bbffb7, 0x45df4d46ead13769},
        {0xbc826216ad2f3bd7, 0x97da3edeff16a179, 0x1d5670c5eccb0e08, 0x9e16dc7440549e19},
        {0x0d47149af5a2b36a, 0x6f120681677935ab, 0xdf712feb77a4cc14, 0x9676b65e9f4abe74},
        {0xa4b82c791f81f8d4, 0x201489aa054c0ed5, 0x938b52268983e56d, 0xa1e09c61e6e808e5},
        {0x965e1e18866e9e46, 0x424b416e512d470d, 0xa628c6e07849ebba, 0xc1b6c93713580a2a},
        {0x6869417400637b20, 0x22f669f40d85acd3, 0xbd4307f256e64ace, 0xb84db6533bbe4acc},
        {0xc6c7955e48db07f5, 0x304b5de1c19a2767, 0x2ad38f0af9fb83ce, 0xe2ec2b8fe92d4acc},
        {0x19abd6b8102ef722, 0x970e915cb733d4ad, 0x8682dbfbf9de0ec4, 0x5377a801d817c758},
        {0xdcbfdcf20e19d4ad, 0xb8c4e134b2dddbd3, 0x5f3756295ef88d64, 0xa4d19c08b0b09e78},
        {0x5652670d18e5cc4f, 0xdf29357a5a23f9df, 0x3661e4619cc44a92, 0x1431a47d71b8272a},
        {0x22a490821302fa34, 0xf3af16bef4963912, 0x96955a4ffa5878aa, 0x4af26b5b5715a13d},
        {0x777716f3f4819dd0, 0xea1a4600fa978d45, 0xfdf4263a54b7bd84, 0xa8f0855ffc668a12},
        {0x9eed28e8af95cd45, 0x5540f921b3c98319, 0x10655900c73d935b, 0xa974596264a99473},
        {0x0ebe8434bfc025be, 0xe5102e35b77a6ef4, 0x598c48d67912f50f, 0x498b936e30273684},
        {0x5f84b79eb74a8482, 0xeea8f3d367ee719e, 0x2ed5e9c2bf3db73d, 0x37a768d0e8d5cc3e},
        {0x35907d5f237ab030, 0x22ff0da276d1995f, 0x8f9fc3031d490428, 0x84751e2691b0a614},
        {0x725e7fd5453fa278, 0x467664329a53f489, 0x7d55f0a4dd555375, 0x6ca927fe669a2253},
        {0x02aed9646e5b4651, 0xcda6a9dd6daa751b, 0x5b010d445edab5e4, 0x66f53fbe74037b6e}
    };

    /** Given a bit vector representation of M^i, update it to be that of M^(i+1). */
    static void NextStep(std::array<uint64_t, 4>& v) noexcept
    {
        uint64_t high = -(v[3] >> 63);
        v[3] = ((v[3] << 1) | (v[2] >> 63)) ^ (high & MUL256[1][3]);
        v[2] = ((v[2] << 1) | (v[1] >> 63)) ^ (high & MUL256[1][2]);
        v[1] = ((v[1] << 1) | (v[0] >> 63)) ^ (high & MUL256[1][1]);
        v[0] = (v[0] << 1) ^ (high & MUL256[1][0]);
    }

    /** Given a bit vector representation of M^i, update it to be that of M^(256*i). */
    static void Mul256Step(std::array<uint64_t, 4>& v) noexcept
    {
        std::array<uint64_t, 4> next_v{0, 0, 0, 0};
        for (int i = 0; i < 256; ++i) {
            if ((v[i / 64] >> (i % 64)) & 1) {
                next_v[0] ^= MUL256[i][0];
                next_v[1] ^= MUL256[i][1];
                next_v[2] ^= MUL256[i][2];
                next_v[3] ^= MUL256[i][3];
            }
        }
        v = next_v;
    }

public:
    void Seek(uint64_t steps) noexcept
    {
        // Fast path for short jumps.
        if (steps < 256) {
            while (steps--) operator()();
            return;
        }
        // Determine how many 8-bit units the steps variable is wide.
        int units = 2;
        while (units < 8 && steps >> (8 * units)) ++units;
        // Comb is a bit vector representation with basis B as explained above. It is initialized
        // to be a representation of M^((steps >> (8 * units - 8)) * 256).
        std::array<uint64_t, 4> comb = MUL256[steps >> (8 * units - 8)];
        // Process more 8-bit units in steps, updating comb to eventually represent M^steps.
        for (int i = 0; i < units - 1; ++i) {
            if (i) Mul256Step(comb);
            int iters = (steps >> (8 * (units - i - 2))) & 0xFF;
            for (int j = 0; j < iters; ++j) NextStep(comb);
        }
        // To compute (M power represented by comb)*m_s, we do not actually need to compute the
        // matrix. Instead, we go through m_s and its 255 next states, and combine them according
        // to the bits in comb into step_s, which we then switch over to.
        std::array<uint64_t, 4> step_s = {0, 0, 0, 0};
        for (int i = 0; i < 256; ++i) {
            if ((comb[i / 64] >> (i % 64)) & 1) {
                step_s[0] ^= m_s[0];
                step_s[1] ^= m_s[1];
                step_s[2] ^= m_s[2];
                step_s[3] ^= m_s[3];
            }
            if (i != 255) operator()();
        }
        m_s = step_s;
    }
};

}  // namespace

/*
int main(void) {
    uint64_t seed = GetRdRand();
    XoShiRo256PP rng1(seed);
    XoShiRo256PP rng2(seed);
    while (true) {
        uint64_t v1a = rng1();
        uint64_t v2a = rng2();
        uint64_t v1b = rng1();
        uint64_t v2b = rng2();
        assert(v1a == v2a);
        assert(v1b == v2b);
        uint64_t seek = (v1a >> (35 + (v1b % 25)));
        printf("%lu\n", (unsigned long)seek);
        rng1.Seek(seek);
        while (seek--) rng2();
    }
    return 0;
}
*/
int main(void) {
    XoShiRo256PP rng(GetRdRand());

    for (int i = 0; i < 1000000; ++i) {
        rng.Seek(rng() & 0xFFFFFFFF);
    }

    printf("%lx\n", (unsigned long)rng());
    return 0;
}