/root/bitcoin/src/minisketch/src/int_utils.h

Source
/**********************************************************************
 * Copyright (c) 2018 Pieter Wuille, Greg Maxwell, Gleb Naumenko      *
 * Distributed under the MIT software license, see the accompanying   *
 * file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
 **********************************************************************/

#ifndef _MINISKETCH_INT_UTILS_H_
#define _MINISKETCH_INT_UTILS_H_

#include <stdint.h>
#include <stdlib.h>

#include <limits>
#include <algorithm>
#include <type_traits>

#if defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L
#  include <bit>
#elif defined(_MSC_VER)
#  include <intrin.h>
#endif

template<int bits>
static constexpr inline uint64_t Rot(uint64_t x) { return (x << bits) | (x >> (64 - bits)); }

static inline void SipHashRound(uint64_t& v0, uint64_t& v1, uint64_t& v2, uint64_t& v3) {
    v0 += v1; v1 = Rot<13>(v1); v1 ^= v0;
    v0 = Rot<32>(v0);
    v2 += v3; v3 = Rot<16>(v3); v3 ^= v2;
    v0 += v3; v3 = Rot<21>(v3); v3 ^= v0;
    v2 += v1; v1 = Rot<17>(v1); v1 ^= v2;
    v2 = Rot<32>(v2);
}

inline uint64_t SipHash(uint64_t k0, uint64_t k1, uint64_t data) {
    uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
    uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
    uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
    uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ data;
    SipHashRound(v0, v1, v2, v3);
    SipHashRound(v0, v1, v2, v3);
    v0 ^= data;
    v3 ^= 0x800000000000000ULL;
    SipHashRound(v0, v1, v2, v3);
    SipHashRound(v0, v1, v2, v3);
    v0 ^= 0x800000000000000ULL;
    v2 ^= 0xFF;
    SipHashRound(v0, v1, v2, v3);
    SipHashRound(v0, v1, v2, v3);
    SipHashRound(v0, v1, v2, v3);
    SipHashRound(v0, v1, v2, v3);
    return v0 ^ v1 ^ v2 ^ v3;
}

class BitWriter {
    unsigned char state = 0;
    int offset = 0;
    unsigned char* out;

    template<int BITS, typename I>
    inline void WriteInner(I val) {
        // We right shift by up to 8 bits below. Verify that's well defined for the type I.
        static_assert(std::numeric_limits<I>::digits > 8, "BitWriter::WriteInner needs I > 8 bits");
        int bits = BITS;
        if (bits + offset >= 8) {
            state |= ((val & ((I(1) << (8 - offset)) - 1)) << offset);
            *(out++) = state;
            val >>= (8 - offset);
            bits -= 8 - offset;
            offset = 0;
            state = 0;
        }
        while (bits >= 8) {
            *(out++) = val & 255;
            val >>= 8;
            bits -= 8;
        }
        state |= ((val & ((I(1) << bits) - 1)) << offset);
        offset += bits;
    }


public:
    BitWriter(unsigned char* output) : out(output) {}

    template<int BITS, typename I>
    inline void Write(I val) {
        // If I is smaller than an unsigned int, invoke WriteInner with argument converted to unsigned.
        using compute_type = typename std::conditional<
            (std::numeric_limits<I>::digits < std::numeric_limits<unsigned>::digits),
            unsigned, I>::type;
        return WriteInner<BITS, compute_type>(val);
    }

    inline void Flush() {
        if (offset) {
            *(out++) = state;
            state = 0;
            offset = 0;
        }
    }
};

class BitReader {
    unsigned char state = 0;
    int offset = 0;
    const unsigned char* in;

public:
    BitReader(const unsigned char* input) : in(input) {}

    template<int BITS, typename I>
    inline I Read() {
        int bits = BITS;
        if (offset >= bits) {
            I ret = state & ((1 << bits) - 1);
            state >>= bits;
            offset -= bits;
            return ret;
        }
        I val = state;
        int out = offset;
        while (out + 8 <= bits) {
            val |= ((I(*(in++))) << out);
            out += 8;
        }
        if (out < bits) {
            unsigned char c = *(in++);
            val |= (c & ((I(1) << (bits - out)) - 1)) << out;
            state = c >> (bits - out);
            offset = 8 - (bits - out);
        } else {
            state = 0;
            offset = 0;
        }
        return val;
    }
};

/** Return a value of type I with its `bits` lowest bits set (bits must be > 0). */
template<int BITS, typename I>
constexpr inline I Mask() { return ((I((I(-1)) << (std::numeric_limits<I>::digits - BITS))) >> (std::numeric_limits<I>::digits - BITS)); }

/** Compute the smallest power of two that is larger than val. */
template<typename I>
static inline int CountBits(I val, int max) {
#if defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L
    // c++20 impl
    (void)max;
    return std::bit_width(val);
#elif defined(_MSC_VER)
    (void)max;
    unsigned long index;
    unsigned char ret;
    if (std::numeric_limits<I>::digits <= 32) {
        ret = _BitScanReverse(&index, val);
    } else {
        ret = _BitScanReverse64(&index, val);
    }
    if (!ret) return 0;
    return index + 1;
#elif defined(HAVE_CLZ)
    (void)max;
    if (val == 0) return 0;
    if (std::numeric_limits<unsigned>::digits >= std::numeric_limits<I>::digits) {
        return std::numeric_limits<unsigned>::digits - __builtin_clz(val);
    } else if (std::numeric_limits<unsigned long>::digits >= std::numeric_limits<I>::digits) {
        return std::numeric_limits<unsigned long>::digits - __builtin_clzl(val);
    } else {
        return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(val);
    }
#else
    while (max && (val >> (max - 1) == 0)) --max;
    return max;
#endif
}

template<typename I, int BITS>
class BitsInt {
private:
    static_assert(std::is_integral<I>::value && std::is_unsigned<I>::value, "BitsInt requires an unsigned integer type");
    static_assert(BITS > 0 && BITS <= std::numeric_limits<I>::digits, "BitsInt requires 1 <= Bits <= representation type size");

    static constexpr I MASK = Mask<BITS, I>();

public:

    typedef I Repr;

    static constexpr int SIZE = BITS;

    static void inline Swap(I& a, I& b) {
        std::swap(a, b);
    }

    static constexpr inline bool IsZero(I a) { return a == 0; }
    static constexpr inline bool IsOne(I a) { return a == 1; }
    static constexpr inline I Mask(I val) { return val & MASK; }
    static constexpr inline I Shift(I val, int bits) { return ((val << bits) & MASK); }
    static constexpr inline I UnsafeShift(I val, int bits) { return (val << bits); }

    template<int Offset, int Count>
    static constexpr inline int MidBits(I val) {
        static_assert(Count > 0, "BITSInt::MidBits needs Count > 0");
        static_assert(Count + Offset <= BITS, "BitsInt::MidBits overflow of Count+Offset");
        return (val >> Offset) & ((I(1) << Count) - 1);
    }

    template<int Count>
    static constexpr inline int TopBits(I val) {
        static_assert(Count > 0, "BitsInt::TopBits needs Count > 0");
        static_assert(Count <= BITS, "BitsInt::TopBits needs Offset <= BITS");
        return static_cast<int>(val >> (BITS - Count));
    }

    static inline constexpr I CondXorWith(I val, bool cond, I v) {
        return val ^ (-I(cond) & v);
    }

    template<I MOD>
    static inline constexpr I CondXorWith(I val, bool cond) {
        return val ^ (-I(cond) & MOD);
    }

    static inline int Bits(I val, int max) { return CountBits<I>(val, max); }
};

/** Class which implements a stateless LFSR for generic moduli. */
template<typename F, uint32_t MOD>
struct LFSR {
    typedef typename F::Repr I;
    /** Shift a value `a` up once, treating it as an `N`-bit LFSR, with pattern `MOD`. */
    static inline constexpr I Call(const I& a) {
        return F::template CondXorWith<MOD>(F::Shift(a, 1), F::template TopBits<1>(a));
    }
};

/** Helper class for carryless multiplications. */
template<typename I, int N, typename L, typename F, int K> struct GFMulHelper;
template<typename I, int N, typename L, typename F> struct GFMulHelper<I, N, L, F, 0>
{
    static inline constexpr I Run(const I& a, const I& b) { return I(0); }
};
template<typename I, int N, typename L, typename F, int K> struct GFMulHelper
{
    static inline constexpr I Run(const I& a, const I& b) { return F::CondXorWith(GFMulHelper<I, N, L, F, K - 1>::Run(L::Call(a), b), F::template MidBits<N - K, 1>(b), a); }
};

/** Compute the carry-less multiplication of a and b, with N bits, using L as LFSR type. */
template<typename I, int N, typename L, typename F> inline constexpr I GFMul(const I& a, const I& b) { return GFMulHelper<I, N, L, F, N>::Run(a, b); }

/** Compute the inverse of x using an extgcd algorithm. */
template<typename I, typename F, int BITS, uint32_t MOD>
inline I InvExtGCD(I x)
{
    if (F::IsZero(x) || F::IsOne(x)) return x;
    I t(0), newt(1);
    I r(MOD), newr = x;
    int rlen = BITS + 1, newrlen = F::Bits(newr, BITS);
    while (newr) {
        int q = rlen - newrlen;
        r ^= F::Shift(newr, q);
        t ^= F::UnsafeShift(newt, q);
        rlen = F::Bits(r, rlen - 1);
        if (r < newr) {
            F::Swap(t, newt);
            F::Swap(r, newr);
            std::swap(rlen, newrlen);
        }
    }
    return t;
}

/** Compute the inverse of x1 using an exponentiation ladder.
 *
 * The `MUL` argument is a multiplication function, `SQR` is a squaring function, and the `SQRi` arguments
 * compute x**(2**i).
 */
template<typename I, typename F, int BITS, I (*MUL)(I, I), I (*SQR)(I), I (*SQR2)(I), I(*SQR4)(I), I(*SQR8)(I), I(*SQR16)(I)>
inline I InvLadder(I x1)
{
    static constexpr int INV_EXP = BITS - 1;
    I x2 = (INV_EXP >= 2) ? MUL(SQR(x1), x1) : I();
    I x4 = (INV_EXP >= 4) ? MUL(SQR2(x2), x2) : I();
    I x8 = (INV_EXP >= 8) ? MUL(SQR4(x4), x4) : I();
    I x16 = (INV_EXP >= 16) ? MUL(SQR8(x8), x8) : I();
    I x32 = (INV_EXP >= 32) ? MUL(SQR16(x16), x16) : I();
    I r;
    if (INV_EXP >= 32) {
        r = x32;
    } else if (INV_EXP >= 16) {
        r = x16;
    } else if (INV_EXP >= 8) {
        r = x8;
    } else if (INV_EXP >= 4) {
        r = x4;
    } else if (INV_EXP >= 2) {
        r = x2;
    } else {
        r = x1;
    }
    if (INV_EXP >= 32 && (INV_EXP & 16)) r = MUL(SQR16(r), x16);
    if (INV_EXP >= 16 && (INV_EXP & 8)) r = MUL(SQR8(r), x8);
    if (INV_EXP >= 8 && (INV_EXP & 4)) r = MUL(SQR4(r), x4);
    if (INV_EXP >= 4 && (INV_EXP & 2)) r = MUL(SQR2(r), x2);
    if (INV_EXP >= 2 && (INV_EXP & 1)) r = MUL(SQR(r), x1);
    return SQR(r);
}

#endif

Coverage Report

Created: 2025-09-19 18:31

Line	Count	Source
1		/**********************************************************************
2		* Copyright (c) 2018 Pieter Wuille, Greg Maxwell, Gleb Naumenko *
3		* Distributed under the MIT software license, see the accompanying *
4		* file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
5		**********************************************************************/
6
7		#ifndef _MINISKETCH_INT_UTILS_H_
8		#define _MINISKETCH_INT_UTILS_H_
9
10		#include <stdint.h>
11		#include <stdlib.h>
12
13		#include <limits>
14		#include <algorithm>
15		#include <type_traits>
16
17		#if defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L
18		# include <bit>
19		#elif defined(_MSC_VER)
20		# include <intrin.h>
21		#endif
22
23		template<int bits>
24	0	static constexpr inline uint64_t Rot(uint64_t x) { return (x << bits) \| (x >> (64 - bits)); } Unexecuted instantiation: minisketch.cpp:_ZL3RotILi13EEmm Unexecuted instantiation: minisketch.cpp:_ZL3RotILi32EEmm Unexecuted instantiation: minisketch.cpp:_ZL3RotILi16EEmm Unexecuted instantiation: minisketch.cpp:_ZL3RotILi21EEmm Unexecuted instantiation: minisketch.cpp:_ZL3RotILi17EEmm Unexecuted instantiation: generic_4bytes.cpp:_ZL3RotILi13EEmm Unexecuted instantiation: generic_4bytes.cpp:_ZL3RotILi32EEmm Unexecuted instantiation: generic_4bytes.cpp:_ZL3RotILi16EEmm Unexecuted instantiation: generic_4bytes.cpp:_ZL3RotILi21EEmm Unexecuted instantiation: generic_4bytes.cpp:_ZL3RotILi17EEmm Unexecuted instantiation: clmul_4bytes.cpp:_ZL3RotILi13EEmm Unexecuted instantiation: clmul_4bytes.cpp:_ZL3RotILi32EEmm Unexecuted instantiation: clmul_4bytes.cpp:_ZL3RotILi16EEmm Unexecuted instantiation: clmul_4bytes.cpp:_ZL3RotILi21EEmm Unexecuted instantiation: clmul_4bytes.cpp:_ZL3RotILi17EEmm
25
26	0	static inline void SipHashRound(uint64_t& v0, uint64_t& v1, uint64_t& v2, uint64_t& v3) {
27	0	v0 += v1; v1 = Rot<13>(v1); v1 ^= v0;
28	0	v0 = Rot<32>(v0);
29	0	v2 += v3; v3 = Rot<16>(v3); v3 ^= v2;
30	0	v0 += v3; v3 = Rot<21>(v3); v3 ^= v0;
31	0	v2 += v1; v1 = Rot<17>(v1); v1 ^= v2;
32	0	v2 = Rot<32>(v2);
33	0	} Unexecuted instantiation: minisketch.cpp:_ZL12SipHashRoundRmS_S_S_ Unexecuted instantiation: generic_4bytes.cpp:_ZL12SipHashRoundRmS_S_S_ Unexecuted instantiation: clmul_4bytes.cpp:_ZL12SipHashRoundRmS_S_S_
34
35	0	inline uint64_t SipHash(uint64_t k0, uint64_t k1, uint64_t data) {
36	0	uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
37	0	uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
38	0	uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
39	0	uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ data;
40	0	SipHashRound(v0, v1, v2, v3);
41	0	SipHashRound(v0, v1, v2, v3);
42	0	v0 ^= data;
43	0	v3 ^= 0x800000000000000ULL;
44	0	SipHashRound(v0, v1, v2, v3);
45	0	SipHashRound(v0, v1, v2, v3);
46	0	v0 ^= 0x800000000000000ULL;
47	0	v2 ^= 0xFF;
48	0	SipHashRound(v0, v1, v2, v3);
49	0	SipHashRound(v0, v1, v2, v3);
50	0	SipHashRound(v0, v1, v2, v3);
51	0	SipHashRound(v0, v1, v2, v3);
52	0	return v0 ^ v1 ^ v2 ^ v3;
53	0	}
54
55		class BitWriter {
56		unsigned char state = 0;
57		int offset = 0;
58		unsigned char* out;
59
60		template<int BITS, typename I>
61	0	inline void WriteInner(I val) {
62		// We right shift by up to 8 bits below. Verify that's well defined for the type I.
63	0	static_assert(std::numeric_limits<I>::digits > 8, "BitWriter::WriteInner needs I > 8 bits");
64	0	int bits = BITS;
65	0	if (bits + offset >= 8) {
66	0	state \|= ((val & ((I(1) << (8 - offset)) - 1)) << offset);
67	0	*(out++) = state;
68	0	val >>= (8 - offset);
69	0	bits -= 8 - offset;
70	0	offset = 0;
71	0	state = 0;
72	0	}
73	0	while (bits >= 8) {
74	0	*(out++) = val & 255;
75	0	val >>= 8;
76	0	bits -= 8;
77	0	}
78	0	state \|= ((val & ((I(1) << bits) - 1)) << offset);
79	0	offset += bits;
80	0	}
81
82
83		public:
84	0	BitWriter(unsigned char* output) : out(output) {}
85
86		template<int BITS, typename I>
87	0	inline void Write(I val) {
88		// If I is smaller than an unsigned int, invoke WriteInner with argument converted to unsigned.
89	0	using compute_type = typename std::conditional<
90	0	(std::numeric_limits<I>::digits < std::numeric_limits<unsigned>::digits),
91	0	unsigned, I>::type;
92	0	return WriteInner<BITS, compute_type>(val);
93	0	}
94
95	0	inline void Flush() {
96	0	if (offset) {
97	0	*(out++) = state;
98	0	state = 0;
99	0	offset = 0;
100	0	}
101	0	}
102		};
103
104		class BitReader {
105		unsigned char state = 0;
106		int offset = 0;
107		const unsigned char* in;
108
109		public:
110	0	BitReader(const unsigned char* input) : in(input) {}
111
112		template<int BITS, typename I>
113	0	inline I Read() {
114	0	int bits = BITS;
115	0	if (offset >= bits) {
116	0	I ret = state & ((1 << bits) - 1);
117	0	state >>= bits;
118	0	offset -= bits;
119	0	return ret;
120	0	}
121	0	I val = state;
122	0	int out = offset;
123	0	while (out + 8 <= bits) {
124	0	val \|= ((I(*(in++))) << out);
125	0	out += 8;
126	0	}
127	0	if (out < bits) {
128	0	unsigned char c = *(in++);
129	0	val \|= (c & ((I(1) << (bits - out)) - 1)) << out;
130	0	state = c >> (bits - out);
131	0	offset = 8 - (bits - out);
132	0	} else {
133	0	state = 0;
134	0	offset = 0;
135	0	}
136	0	return val;
137	0	}
138		};
139
140		/** Return a value of type I with its `bits` lowest bits set (bits must be > 0). */
141		template<int BITS, typename I>
142	0	constexpr inline I Mask() { return ((I((I(-1)) << (std::numeric_limits<I>::digits - BITS))) >> (std::numeric_limits<I>::digits - BITS)); }
143
144		/** Compute the smallest power of two that is larger than val. */
145		template<typename I>
146	0	static inline int CountBits(I val, int max) {
147		#if defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L
148		// c++20 impl
149		(void)max;
150		return std::bit_width(val);
151		#elif defined(_MSC_VER)
152		(void)max;
153		unsigned long index;
154		unsigned char ret;
155		if (std::numeric_limits<I>::digits <= 32) {
156		ret = _BitScanReverse(&index, val);
157		} else {
158		ret = _BitScanReverse64(&index, val);
159		}
160		if (!ret) return 0;
161		return index + 1;
162		#elif defined(HAVE_CLZ)
163		(void)max;
164		if (val == 0) return 0;
165		if (std::numeric_limits<unsigned>::digits >= std::numeric_limits<I>::digits) {
166		return std::numeric_limits<unsigned>::digits - __builtin_clz(val);
167		} else if (std::numeric_limits<unsigned long>::digits >= std::numeric_limits<I>::digits) {
168		return std::numeric_limits<unsigned long>::digits - __builtin_clzl(val);
169		} else {
170		return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(val);
171		}
172		#else
173	0	while (max && (val >> (max - 1) == 0)) --max;
174		return max;
175		#endif
176	0	} Unexecuted instantiation: minisketch.cpp:_ZL9CountBitsIjEiT_i Unexecuted instantiation: generic_4bytes.cpp:_ZL9CountBitsIjEiT_i
177
178		template<typename I, int BITS>
179		class BitsInt {
180		private:
181		static_assert(std::is_integral<I>::value && std::is_unsigned<I>::value, "BitsInt requires an unsigned integer type");
182		static_assert(BITS > 0 && BITS <= std::numeric_limits<I>::digits, "BitsInt requires 1 <= Bits <= representation type size");
183
184		static constexpr I MASK = Mask<BITS, I>();
185
186		public:
187
188		typedef I Repr;
189
190		static constexpr int SIZE = BITS;
191
192	0	static void inline Swap(I& a, I& b) {
193	0	std::swap(a, b);
194	0	}
195
196	0	static constexpr inline bool IsZero(I a) { return a == 0; }
197	0	static constexpr inline bool IsOne(I a) { return a == 1; }
198	0	static constexpr inline I Mask(I val) { return val & MASK; }
199	0	static constexpr inline I Shift(I val, int bits) { return ((val << bits) & MASK); }
200	0	static constexpr inline I UnsafeShift(I val, int bits) { return (val << bits); }
201
202		template<int Offset, int Count>
203	0	static constexpr inline int MidBits(I val) {
204	0	static_assert(Count > 0, "BITSInt::MidBits needs Count > 0");
205	0	static_assert(Count + Offset <= BITS, "BitsInt::MidBits overflow of Count+Offset");
206	0	return (val >> Offset) & ((I(1) << Count) - 1);
207	0	} Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi0ELi6EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi6ELi6EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi12ELi5EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi17ELi5EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi22ELi5EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi0ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi4ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi8ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi12ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi16ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi20ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi24ELi4EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi31ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi30ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi29ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi28ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi27ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi26ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi25ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi24ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi23ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi22ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi21ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi20ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi19ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi18ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi17ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi16ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi15ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi14ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi13ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi12ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi11ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi10ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi9ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi8ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi7ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi6ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi5ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi4ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi3ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi2ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi1ELi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7MidBitsILi0ELi1EEEij
208
209		template<int Count>
210	0	static constexpr inline int TopBits(I val) {
211	0	static_assert(Count > 0, "BitsInt::TopBits needs Count > 0");
212	0	static_assert(Count <= BITS, "BitsInt::TopBits needs Offset <= BITS");
213	0	return static_cast<int>(val >> (BITS - Count));
214	0	} Unexecuted instantiation: _ZN7BitsIntIjLi32EE7TopBitsILi5EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7TopBitsILi1EEEij Unexecuted instantiation: _ZN7BitsIntIjLi32EE7TopBitsILi4EEEij
215
216	0	static inline constexpr I CondXorWith(I val, bool cond, I v) {
217	0	return val ^ (-I(cond) & v);
218	0	}
219
220		template<I MOD>
221	0	static inline constexpr I CondXorWith(I val, bool cond) {
222	0	return val ^ (-I(cond) & MOD);
223	0	}
224
225	0	static inline int Bits(I val, int max) { return CountBits<I>(val, max); }
226		};
227
228		/** Class which implements a stateless LFSR for generic moduli. */
229		template<typename F, uint32_t MOD>
230		struct LFSR {
231		typedef typename F::Repr I;
232		/** Shift a value `a` up once, treating it as an `N`-bit LFSR, with pattern `MOD`. */
233	0	static inline constexpr I Call(const I& a) {
234	0	return F::template CondXorWith<MOD>(F::Shift(a, 1), F::template TopBits<1>(a));
235	0	}
236		};
237
238		/** Helper class for carryless multiplications. */
239		template<typename I, int N, typename L, typename F, int K> struct GFMulHelper;
240		template<typename I, int N, typename L, typename F> struct GFMulHelper<I, N, L, F, 0>
241		{
242	0	static inline constexpr I Run(const I& a, const I& b) { return I(0); }
243		};
244		template<typename I, int N, typename L, typename F, int K> struct GFMulHelper
245		{
246	0	static inline constexpr I Run(const I& a, const I& b) { return F::CondXorWith(GFMulHelper<I, N, L, F, K - 1>::Run(L::Call(a), b), F::template MidBits<N - K, 1>(b), a); } Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li32EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li31EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li30EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li29EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li28EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li27EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li26EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li25EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li24EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li23EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li22EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li21EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li20EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li19EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li18EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li17EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li16EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li15EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li14EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li13EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li12EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li11EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li10EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li9EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li8EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li7EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li6EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li5EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li4EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li3EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li2EE3RunERKjS6_ Unexecuted instantiation: _ZN11GFMulHelperIjLi32E4LFSRI7BitsIntIjLi32EELj141EES2_Li1EE3RunERKjS6_
247		};
248
249		/** Compute the carry-less multiplication of a and b, with N bits, using L as LFSR type. */
250	0	template<typename I, int N, typename L, typename F> inline constexpr I GFMul(const I& a, const I& b) { return GFMulHelper<I, N, L, F, N>::Run(a, b); }
251
252		/** Compute the inverse of x using an extgcd algorithm. */
253		template<typename I, typename F, int BITS, uint32_t MOD>
254		inline I InvExtGCD(I x)
255	0	{
256	0	if (F::IsZero(x) \|\| F::IsOne(x)) return x;
257	0	I t(0), newt(1);
258	0	I r(MOD), newr = x;
259	0	int rlen = BITS + 1, newrlen = F::Bits(newr, BITS);
260	0	while (newr) {
261	0	int q = rlen - newrlen;
262	0	r ^= F::Shift(newr, q);
263	0	t ^= F::UnsafeShift(newt, q);
264	0	rlen = F::Bits(r, rlen - 1);
265	0	if (r < newr) {
266	0	F::Swap(t, newt);
267	0	F::Swap(r, newr);
268	0	std::swap(rlen, newrlen);
269	0	}
270	0	}
271	0	return t;
272	0	}
273
274		/** Compute the inverse of x1 using an exponentiation ladder.
275		*
276		* The `MUL` argument is a multiplication function, `SQR` is a squaring function, and the `SQRi` arguments
277		* compute x(2i).
278		*/
279		template<typename I, typename F, int BITS, I (MUL)(I, I), I (SQR)(I), I (SQR2)(I), I(SQR4)(I), I(SQR8)(I), I(SQR16)(I)>
280		inline I InvLadder(I x1)
281	0	{
282	0	static constexpr int INV_EXP = BITS - 1;
283	0	I x2 = (INV_EXP >= 2) ? MUL(SQR(x1), x1) : I();
284	0	I x4 = (INV_EXP >= 4) ? MUL(SQR2(x2), x2) : I();
285	0	I x8 = (INV_EXP >= 8) ? MUL(SQR4(x4), x4) : I();
286	0	I x16 = (INV_EXP >= 16) ? MUL(SQR8(x8), x8) : I();
287	0	I x32 = (INV_EXP >= 32) ? MUL(SQR16(x16), x16) : I();
288	0	I r;
289	0	if (INV_EXP >= 32) {
290	0	r = x32;
291	0	} else if (INV_EXP >= 16) {
292	0	r = x16;
293	0	} else if (INV_EXP >= 8) {
294	0	r = x8;
295	0	} else if (INV_EXP >= 4) {
296	0	r = x4;
297	0	} else if (INV_EXP >= 2) {
298	0	r = x2;
299	0	} else {
300	0	r = x1;
301	0	}
302	0	if (INV_EXP >= 32 && (INV_EXP & 16)) r = MUL(SQR16(r), x16);
303	0	if (INV_EXP >= 16 && (INV_EXP & 8)) r = MUL(SQR8(r), x8);
304	0	if (INV_EXP >= 8 && (INV_EXP & 4)) r = MUL(SQR4(r), x4);
305	0	if (INV_EXP >= 4 && (INV_EXP & 2)) r = MUL(SQR2(r), x2);
306	0	if (INV_EXP >= 2 && (INV_EXP & 1)) r = MUL(SQR(r), x1);
307	0	return SQR(r);
308	0	}
309
310		#endif