libdpf/include/dpf/gf2.hpp

/// @file dpf/gf2.hpp
/// @brief Characteristic-2 field elements as DPF output types.
/// @details `dpf::gf2`, `gf22`, `gf24`, `gf28`, `gf216`, `gf232`, and `gf264`
///          are GF(2^k) for k = 1, 2, 4, 8, 16, 32, 64. Addition and
///          subtraction are XOR. Multiplication is the polynomial product
///          in the standard basis (low bit is the coefficient of 1).
///
///          The moduli match laneint on mocha2. Widths 1, 2, 4, and 16 are
///          the sparse irreducibles in `laneint/gf2_poly_basis.hpp` and the
///          epi multipliers. GF(2^8) is the AES polynomial that
///          `gf256_mul_u8` uses (`0x11B`), not the sparse `0x11D` alternative.
///          GF(2^32) and GF(2^64) use the irreducible basis polynomials.
///          The epi “default” reducers `x^32+x^7+1` and `x^64+x^4+1` factor,
///          so they are not the field. Leaf scaling of `gf28` and `gf216`
///          is the FAST'13 nibble `pshufb` (Plank, Greenan, Miller): one
///          constant builds 16-byte tables, and every lane is a shuffle.
///          `detail::shamir_field` inverts a
///          nonzero element by Fermat, `a^{2^k - 2}`. Shamir points are the
///          integers `1 .. N` as bit patterns, so `N` must be less than `2^k`
///          or two parties land on the same element.
/// @copyright Copyright (c) 2019-2026 Ryan Henry and [others](@ref authors)
/// @license Released under a GNU General Public v2.0 (GPLv2) license;
///          see [LICENSE.md](@ref license) for details.

#ifndef LIBDPF_INCLUDE_DPF_GF2_HPP__
#define LIBDPF_INCLUDE_DPF_GF2_HPP__

#include <cstddef>
#include <cstdint>
#include <cstring>
#include <ostream>
#include <stdexcept>
#include <type_traits>

#include "hedley/hedley.h"
#include "simde/simde/x86/avx2.h"

#include "dpf/leaf_arithmetic.hpp"
#include "dpf/utils.hpp"

namespace dpf
{
namespace gf2_detail
{

template <unsigned Bits>
struct field;

template <>
struct field<1>
{
    using word = std::uint8_t;
    using wide = std::uint16_t;
    static constexpr unsigned bits = 1;
    /// `x + 1`
    static constexpr wide modulus = 0x3u;
};

template <>
struct field<2>
{
    using word = std::uint8_t;
    using wide = std::uint16_t;
    static constexpr unsigned bits = 2;
    /// `x^2 + x + 1`
    static constexpr wide modulus = 0x7u;
};

template <>
struct field<4>
{
    using word = std::uint8_t;
    using wide = std::uint16_t;
    static constexpr unsigned bits = 4;
    /// `x^4 + x + 1`
    static constexpr wide modulus = 0x13u;
};

template <>
struct field<8>
{
    using word = std::uint8_t;
    using wide = std::uint16_t;
    static constexpr unsigned bits = 8;
    /// AES: `x^8 + x^4 + x^3 + x + 1`
    static constexpr wide modulus = 0x11bu;
};

template <>
struct field<16>
{
    using word = std::uint16_t;
    using wide = std::uint32_t;
    static constexpr unsigned bits = 16;
    /// `x^16 + x^5 + x^3 + x^2 + 1`
    static constexpr wide modulus = 0x1002du;
};

template <>
struct field<32>
{
    using word = std::uint32_t;
    using wide = std::uint64_t;
    static constexpr unsigned bits = 32;
    /// `x^32 + x^31 + x^28 + x^21 + 1`
    static constexpr wide modulus = 0x190200001ull;
};

template <>
struct field<64>
{
    using word = std::uint64_t;
    using wide = unsigned __int128;
    static constexpr unsigned bits = 64;
    /// `x^64 + x^63 + x^62 + x^53 + 1`
    static constexpr wide modulus =
        (wide{1} << 64) | (wide{1} << 63) | (wide{1} << 62) | (wide{1} << 53) | wide{1};
};

template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
constexpr typename field<Bits>::word mask() noexcept
{
    using word = typename field<Bits>::word;
    if constexpr (Bits >= sizeof(word) * 8u)
        return static_cast<word>(~word{0});
    else
        return static_cast<word>((word{1} << Bits) - word{1});
}

template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
constexpr typename field<Bits>::word reduce(typename field<Bits>::wide p) noexcept
{
    using wide = typename field<Bits>::wide;
    constexpr wide mod = field<Bits>::modulus;
    for (int bit = static_cast<int>(2u * Bits) - 2; bit >= static_cast<int>(Bits); --bit)
    {
        if (((p >> bit) & wide{1}) != 0)
            p ^= mod << (bit - static_cast<int>(Bits));
    }
    return static_cast<typename field<Bits>::word>(p);
}

template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
constexpr typename field<Bits>::word mul(typename field<Bits>::word a,
    typename field<Bits>::word b) noexcept
{
    using wide = typename field<Bits>::wide;
    a = static_cast<typename field<Bits>::word>(a & mask<Bits>());
    b = static_cast<typename field<Bits>::word>(b & mask<Bits>());
    wide p = 0;
    for (unsigned i = 0; i < Bits; ++i)
    {
        if (((b >> i) & 1u) != 0u)
            p ^= static_cast<wide>(a) << i;
    }
    return reduce<Bits>(p);
}

/// @brief Multiplicative inverse, `a^{2^Bits - 2}`.
/// @param a a nonzero field element
/// @return `a^{-1}`
/// @throws std::invalid_argument if `a` is zero
template <unsigned Bits>
typename field<Bits>::word inv(typename field<Bits>::word a)
{
    using word = typename field<Bits>::word;
    a = static_cast<word>(a & mask<Bits>());
    if (a == 0)
        throw std::invalid_argument("shamir: inverse of zero");
    // Exponent 2^Bits - 2 is Bits-1 ones followed by a zero.
    word result{1};
    for (int bit = static_cast<int>(Bits) - 1; bit >= 0; --bit)
    {
        result = mul<Bits>(result, result);
        if (bit != 0)
            result = mul<Bits>(result, a);
    }
    return result;
}

/// @brief Multiply by `x` in AES GF(2^8), modulus `0x11B`.
HEDLEY_ALWAYS_INLINE
constexpr std::uint8_t gf28_mul_x(std::uint8_t a) noexcept
{
    const std::uint8_t hi = static_cast<std::uint8_t>(a & 0x80u);
    a = static_cast<std::uint8_t>(static_cast<std::uint8_t>(a << 1) ^ (hi != 0 ? 0x1bu : 0));
    return a;
}

/// @brief Multiply by `x` in GF(2^16), modulus `x^16+x^5+x^3+x^2+1`.
HEDLEY_ALWAYS_INLINE
constexpr std::uint16_t gf216_mul_x(std::uint16_t a) noexcept
{
    const std::uint16_t hi = static_cast<std::uint16_t>(a & 0x8000u);
    a = static_cast<std::uint16_t>(static_cast<std::uint16_t>(a << 1) ^ (hi != 0 ? 0x2du : 0));
    return a;
}

/// @brief 16 products of `base` with a nibble, built from four multiplies by `x`.
HEDLEY_ALWAYS_INLINE
void nibble_products_u8(std::uint8_t base, std::uint8_t out[16]) noexcept
{
    const std::uint8_t b0 = base;
    const std::uint8_t b1 = gf28_mul_x(b0);
    const std::uint8_t b2 = gf28_mul_x(b1);
    const std::uint8_t b3 = gf28_mul_x(b2);
    out[0] = 0;
    for (unsigned n = 1; n < 16u; ++n)
    {
        std::uint8_t r = 0;
        if ((n & 1u) != 0) r = static_cast<std::uint8_t>(r ^ b0);
        if ((n & 2u) != 0) r = static_cast<std::uint8_t>(r ^ b1);
        if ((n & 4u) != 0) r = static_cast<std::uint8_t>(r ^ b2);
        if ((n & 8u) != 0) r = static_cast<std::uint8_t>(r ^ b3);
        out[n] = r;
    }
}

HEDLEY_ALWAYS_INLINE
void nibble_products_u16(std::uint16_t base, std::uint8_t lo[16], std::uint8_t hi[16]) noexcept
{
    const std::uint16_t b0 = base;
    const std::uint16_t b1 = gf216_mul_x(b0);
    const std::uint16_t b2 = gf216_mul_x(b1);
    const std::uint16_t b3 = gf216_mul_x(b2);
    lo[0] = 0;
    hi[0] = 0;
    for (unsigned n = 1; n < 16u; ++n)
    {
        std::uint16_t r = 0;
        if ((n & 1u) != 0) r = static_cast<std::uint16_t>(r ^ b0);
        if ((n & 2u) != 0) r = static_cast<std::uint16_t>(r ^ b1);
        if ((n & 4u) != 0) r = static_cast<std::uint16_t>(r ^ b2);
        if ((n & 8u) != 0) r = static_cast<std::uint16_t>(r ^ b3);
        lo[n] = static_cast<std::uint8_t>(r);
        hi[n] = static_cast<std::uint8_t>(r >> 8);
    }
}

/// @brief FAST'13 nibble tables for one GF(2^8) constant.
/// @details Plank, Greenan, Miller, "Screaming Fast Galois Field Arithmetic
///          Using Intel SIMD Instructions". `y * a = (y * a_lo) XOR (y * (a_hi << 4))`,
///          each half a 16-entry `pshufb`.
struct gf28_shufb
{
    simde__m128i lo;
    simde__m128i hi;
};

inline const gf28_shufb & gf28_shufb_for(std::uint8_t y) noexcept
{
    struct tables
    {
        gf28_shufb t[256];
        tables() noexcept
        {
            for (unsigned yy = 0; yy < 256u; ++yy)
            {
                alignas(16) std::uint8_t lo[16];
                alignas(16) std::uint8_t hi[16];
                nibble_products_u8(static_cast<std::uint8_t>(yy), lo);
                const std::uint8_t x4 = gf28_mul_x(gf28_mul_x(gf28_mul_x(gf28_mul_x(
                    static_cast<std::uint8_t>(yy)))));
                nibble_products_u8(x4, hi);
                t[yy].lo = simde_mm_load_si128(reinterpret_cast<const simde__m128i *>(lo));
                t[yy].hi = simde_mm_load_si128(reinterpret_cast<const simde__m128i *>(hi));
            }
        }
    };
    static const tables all;
    return all.t[y];
}

HEDLEY_ALWAYS_INLINE
simde__m128i gf28_scale_m128(simde__m128i lut_lo, simde__m128i lut_hi, simde__m128i a) noexcept
{
    const simde__m128i m0f = simde_mm_set1_epi8(0x0f);
    const simde__m128i lo = simde_mm_and_si128(a, m0f);
    const simde__m128i hi = simde_mm_and_si128(simde_mm_srli_epi16(a, 4), m0f);
    return simde_mm_xor_si128(simde_mm_shuffle_epi8(lut_lo, lo),
        simde_mm_shuffle_epi8(lut_hi, hi));
}

/// @brief Four nibble positions of one GF(2^16) constant. Each position is a
///        low-byte table and a high-byte table.
struct gf216_shufb
{
    simde__m128i lo[4];
    simde__m128i hi[4];
};

HEDLEY_ALWAYS_INLINE
gf216_shufb gf216_shufb_prepare(std::uint16_t k) noexcept
{
    gf216_shufb L{};
    std::uint16_t base = k;
    for (unsigned nib = 0; nib < 4u; ++nib)
    {
        alignas(16) std::uint8_t lo[16];
        alignas(16) std::uint8_t hi[16];
        nibble_products_u16(base, lo, hi);
        L.lo[nib] = simde_mm_load_si128(reinterpret_cast<const simde__m128i *>(lo));
        L.hi[nib] = simde_mm_load_si128(reinterpret_cast<const simde__m128i *>(hi));
        base = gf216_mul_x(gf216_mul_x(gf216_mul_x(gf216_mul_x(base))));
    }
    return L;
}

HEDLEY_ALWAYS_INLINE
simde__m128i gf216_scale_m128(const gf216_shufb & L, simde__m128i x) noexcept
{
    const simde__m128i m4 = simde_mm_set1_epi16(0x000f);
    const simde__m128i pick_ev = simde_mm_setr_epi8(
        0, static_cast<int8_t>(0x80), 2, static_cast<int8_t>(0x80),
        4, static_cast<int8_t>(0x80), 6, static_cast<int8_t>(0x80),
        8, static_cast<int8_t>(0x80), 10, static_cast<int8_t>(0x80),
        12, static_cast<int8_t>(0x80), 14, static_cast<int8_t>(0x80));
    const simde__m128i ix0 = simde_mm_shuffle_epi8(simde_mm_and_si128(x, m4), pick_ev);
    const simde__m128i ix1 = simde_mm_shuffle_epi8(
        simde_mm_and_si128(simde_mm_srli_epi16(x, 4), m4), pick_ev);
    const simde__m128i ix2 = simde_mm_shuffle_epi8(
        simde_mm_and_si128(simde_mm_srli_epi16(x, 8), m4), pick_ev);
    const simde__m128i ix3 = simde_mm_shuffle_epi8(
        simde_mm_and_si128(simde_mm_srli_epi16(x, 12), m4), pick_ev);
    auto part = [](simde__m128i tl, simde__m128i th, simde__m128i ix) noexcept {
        const simde__m128i pl = simde_mm_shuffle_epi8(tl, ix);
        const simde__m128i ph = simde_mm_shuffle_epi8(th, ix);
        return simde_mm_or_si128(pl, simde_mm_slli_epi16(ph, 8));
    };
    return simde_mm_xor_si128(
        simde_mm_xor_si128(part(L.lo[0], L.hi[0], ix0), part(L.lo[1], L.hi[1], ix1)),
        simde_mm_xor_si128(part(L.lo[2], L.hi[2], ix2), part(L.lo[3], L.hi[3], ix3)));
}

HEDLEY_ALWAYS_INLINE
void scale_gf28(unsigned char * dst, const unsigned char * src, std::size_t n,
    std::uint8_t k) noexcept
{
    if (k == 0)
    {
        std::memset(dst, 0, n);
        return;
    }
    if (k == 1)
    {
        if (dst != src)
            std::memcpy(dst, src, n);
        return;
    }
    const gf28_shufb & lut = gf28_shufb_for(k);
    const simde__m256i lo256 = simde_mm256_broadcastsi128_si256(lut.lo);
    const simde__m256i hi256 = simde_mm256_broadcastsi128_si256(lut.hi);
    const simde__m256i m0f = simde_mm256_set1_epi8(0x0f);
    std::size_t i = 0;
    for (; i + 32 <= n; i += 32)
    {
        const simde__m256i a = simde_mm256_loadu_si256(src + i);
        const simde__m256i lo = simde_mm256_and_si256(a, m0f);
        const simde__m256i hi = simde_mm256_and_si256(simde_mm256_srli_epi16(a, 4), m0f);
        const simde__m256i r = simde_mm256_xor_si256(
            simde_mm256_shuffle_epi8(lo256, lo),
            simde_mm256_shuffle_epi8(hi256, hi));
        simde_mm256_storeu_si256(dst + i, r);
    }
    for (; i + 16 <= n; i += 16)
    {
        const simde__m128i a = simde_mm_loadu_si128(src + i);
        simde_mm_storeu_si128(dst + i, gf28_scale_m128(lut.lo, lut.hi, a));
    }
    for (; i < n; ++i)
        dst[i] = mul<8>(src[i], k);
}

HEDLEY_ALWAYS_INLINE
void scale_gf216(unsigned char * dst, const unsigned char * src, std::size_t n,
    std::uint16_t k) noexcept
{
    if (k == 0)
    {
        std::memset(dst, 0, n);
        return;
    }
    if (k == 1)
    {
        if (dst != src)
            std::memcpy(dst, src, n);
        return;
    }
    const gf216_shufb L = gf216_shufb_prepare(k);
    std::size_t i = 0;
    for (; i + 16 <= n; i += 16)
    {
        const simde__m128i a = simde_mm_loadu_si128(src + i);
        simde_mm_storeu_si128(dst + i, gf216_scale_m128(L, a));
    }
    for (; i + sizeof(std::uint16_t) <= n; i += sizeof(std::uint16_t))
    {
        std::uint16_t a{};
        std::memcpy(&a, src + i, sizeof(a));
        const std::uint16_t c = mul<16>(a, k);
        std::memcpy(dst + i, &c, sizeof(c));
    }
    for (; i < n; ++i)
        dst[i] = 0;
}

HEDLEY_ALWAYS_INLINE
void xor_bytes(unsigned char * dst, const unsigned char * a,
    const unsigned char * b, std::size_t n) noexcept
{
    for (std::size_t i = 0; i < n; ++i)
        dst[i] = static_cast<unsigned char>(a[i] ^ b[i]);
}

template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
void scale_bytes(unsigned char * dst, const unsigned char * src, std::size_t n,
    typename field<Bits>::word k) noexcept
{
    using word = typename field<Bits>::word;
    k = static_cast<word>(k & mask<Bits>());
    if constexpr (Bits == 1)
    {
        const unsigned char fill = (k & 1u) ? static_cast<unsigned char>(0xffu) : 0;
        for (std::size_t i = 0; i < n; ++i)
            dst[i] = static_cast<unsigned char>(src[i] & fill);
    }
    else if constexpr (Bits < 8)
    {
        constexpr unsigned per_byte = 8u / Bits;
        constexpr unsigned lane_mask = (1u << Bits) - 1u;
        for (std::size_t i = 0; i < n; ++i)
        {
            unsigned out = 0;
            const unsigned in = src[i];
            for (unsigned lane = 0; lane < per_byte; ++lane)
            {
                const auto a = static_cast<word>((in >> (lane * Bits)) & lane_mask);
                out |= static_cast<unsigned>(mul<Bits>(a, k)) << (lane * Bits);
            }
            dst[i] = static_cast<unsigned char>(out);
        }
    }
    else if constexpr (Bits == 8)
    {
        scale_gf28(dst, src, n, static_cast<std::uint8_t>(k));
    }
    else if constexpr (Bits == 16)
    {
        scale_gf216(dst, src, n, static_cast<std::uint16_t>(k));
    }
    else
    {
        std::size_t i = 0;
        for (; i + sizeof(word) <= n; i += sizeof(word))
        {
            word a{};
            std::memcpy(&a, src + i, sizeof(word));
            const word c = mul<Bits>(a, k);
            std::memcpy(dst + i, &c, sizeof(word));
        }
        for (; i < n; ++i)
            dst[i] = 0;
    }
}

template <typename NodeT>
HEDLEY_ALWAYS_INLINE
NodeT xor_node(const NodeT & a, const NodeT & b) noexcept
{
    unsigned char aa[sizeof(NodeT)];
    unsigned char bb[sizeof(NodeT)];
    unsigned char cc[sizeof(NodeT)];
    std::memcpy(aa, std::addressof(a), sizeof(NodeT));
    std::memcpy(bb, std::addressof(b), sizeof(NodeT));
    xor_bytes(cc, aa, bb, sizeof(NodeT));
    NodeT out;
    std::memcpy(std::addressof(out), cc, sizeof(NodeT));
    return out;
}

template <unsigned Bits, typename NodeT>
HEDLEY_ALWAYS_INLINE
NodeT scale_node(const NodeT & a, typename field<Bits>::word k) noexcept
{
    unsigned char src[sizeof(NodeT)];
    unsigned char dst[sizeof(NodeT)];
    std::memcpy(src, std::addressof(a), sizeof(NodeT));
    scale_bytes<Bits>(dst, src, sizeof(NodeT), k);
    NodeT out;
    std::memcpy(std::addressof(out), dst, sizeof(NodeT));
    return out;
}

}  // namespace gf2_detail

/// @brief Element of GF(2^Bits) in the standard polynomial basis.
/// @tparam Bits field degree. One of 1, 2, 4, 8, 16, 32, 64.
template <unsigned Bits>
class gf2n
{
  public:
    using integral_type = typename gf2_detail::field<Bits>::word;
    static constexpr unsigned bits = Bits;
    static constexpr bool dpf_gf2n = true;
    static constexpr bool dpf_point_group = true;

    /// @brief The zero element.
    HEDLEY_ALWAYS_INLINE
    constexpr gf2n() noexcept = default;

    /// @brief Bit embedding of an integer. A negative value is the field
    ///        negation of its magnitude, which is the same element: every
    ///        element is its own additive inverse.
    /// @tparam T integral type
    /// @param v the integer to embed
    template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
    HEDLEY_ALWAYS_INLINE
    constexpr gf2n(T v) noexcept
    {
        if constexpr (std::is_signed_v<T>)
        {
            if (v < 0)
            {
                using unsigned_type = std::make_unsigned_t<T>;
                const auto mag = static_cast<unsigned_type>(0)
                    - static_cast<unsigned_type>(v);
                val = static_cast<integral_type>(mag) & gf2_detail::mask<Bits>();
            }
            else
            {
                val = static_cast<integral_type>(v) & gf2_detail::mask<Bits>();
            }
        }
        else
        {
            val = static_cast<integral_type>(v) & gf2_detail::mask<Bits>();
        }
    }

    /// @brief Low `Bits` of a PRG block. Every bit string is a field element.
    /// @param bytes the PRG output
    /// @param n the number of bytes available
    /// @return the field element
    HEDLEY_ALWAYS_INLINE
    static gf2n from_seed(const void * bytes, std::size_t n) noexcept
    {
        integral_type w{};
        if (bytes != nullptr && n != 0)
        {
            const std::size_t take = n < sizeof(w) ? n : sizeof(w);
            std::memcpy(&w, bytes, take);
        }
        return gf2n{w};
    }

    /// @brief Reduced representative in `0 .. 2^Bits - 1`.
    /// @return the stored field element
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    constexpr integral_type raw() const noexcept
    {
        return static_cast<integral_type>(val & gf2_detail::mask<Bits>());
    }

    /// @brief Same value as `raw()`.
    /// @return the stored field element
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    explicit constexpr operator integral_type() const noexcept { return raw(); }

  private:
    integral_type val{};
};

/// @brief GF(2).
using gf2 = gf2n<1>;
/// @brief GF(4) = GF(2^2), modulus `x^2 + x + 1`.
using gf22 = gf2n<2>;
/// @brief GF(16) = GF(2^4), modulus `x^4 + x + 1`.
using gf24 = gf2n<4>;
/// @brief GF(256) = GF(2^8), AES modulus `x^8 + x^4 + x^3 + x + 1`.
using gf28 = gf2n<8>;
/// @brief GF(2^16), modulus `x^16 + x^5 + x^3 + x^2 + 1`.
using gf216 = gf2n<16>;
/// @brief GF(2^32), modulus `x^32 + x^31 + x^28 + x^21 + 1`.
using gf232 = gf2n<32>;
/// @brief GF(2^64), modulus `x^64 + x^63 + x^62 + x^53 + 1`.
using gf264 = gf2n<64>;

/// @brief Field addition. XOR of the reduced representatives.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr gf2n<Bits> operator+(gf2n<Bits> a, gf2n<Bits> b) noexcept
{
    using word = typename gf2n<Bits>::integral_type;
    return gf2n<Bits>{static_cast<word>(a.raw() ^ b.raw())};
}

/// @brief Field subtraction. Identical to addition.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr gf2n<Bits> operator-(gf2n<Bits> a, gf2n<Bits> b) noexcept
{
    return a + b;
}

/// @brief Additive inverse. Identical to `a` in characteristic 2.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr gf2n<Bits> operator-(gf2n<Bits> a) noexcept
{
    return a;
}

/// @brief Field XOR. Identical to addition.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr gf2n<Bits> operator^(gf2n<Bits> a, gf2n<Bits> b) noexcept
{
    return a + b;
}

/// @brief Field multiplication.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr gf2n<Bits> operator*(gf2n<Bits> a, gf2n<Bits> b) noexcept
{
    return gf2n<Bits>{gf2_detail::mul<Bits>(a.raw(), b.raw())};
}

/// @brief Equality of the reduced representatives.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr bool operator==(gf2n<Bits> a, gf2n<Bits> b) noexcept
{
    return a.raw() == b.raw();
}

/// @brief Inequality of the reduced representatives.
template <unsigned Bits>
HEDLEY_ALWAYS_INLINE
constexpr bool operator!=(gf2n<Bits> a, gf2n<Bits> b) noexcept
{
    return a.raw() != b.raw();
}

/// @brief Write the reduced representative in decimal.
template <unsigned Bits>
std::ostream & operator<<(std::ostream & os, gf2n<Bits> a)
{
    return os << static_cast<unsigned long long>(a.raw());
}

/// @brief Non-template operators so a packed-lane proxy converts to the field
///        and finds `+` / `-` the same way `nyble` and `twobit` do.
#define DPF_GF_LANE_OPS(Type)                                                     \
HEDLEY_ALWAYS_INLINE constexpr Type operator+(Type a, Type b) noexcept          \
{                                                                                \
    using word = typename Type::integral_type;                                  \
    return Type{static_cast<word>(a.raw() ^ b.raw())};                          \
}                                                                                \
HEDLEY_ALWAYS_INLINE constexpr Type operator-(Type a, Type b) noexcept          \
{                                                                                \
    return a + b;                                                                \
}                                                                                \
HEDLEY_ALWAYS_INLINE constexpr Type operator-(Type a) noexcept { return a; }   \
HEDLEY_ALWAYS_INLINE constexpr Type operator^(Type a, Type b) noexcept          \
{                                                                                \
    return a + b;                                                                \
}                                                                                \
HEDLEY_ALWAYS_INLINE constexpr Type operator*(Type a, Type b) noexcept          \
{                                                                                \
    return Type{gf2_detail::mul<Type::bits>(a.raw(), b.raw())};                 \
}                                                                                \
HEDLEY_ALWAYS_INLINE constexpr bool operator==(Type a, Type b) noexcept         \
{                                                                                \
    return a.raw() == b.raw();                                                   \
}                                                                                \
HEDLEY_ALWAYS_INLINE constexpr bool operator!=(Type a, Type b) noexcept         \
{                                                                                \
    return !(a == b);                                                            \
}                                                                                \
inline std::ostream & operator<<(std::ostream & os, Type a)                     \
{                                                                                \
    return os << static_cast<unsigned long long>(a.raw());                      \
}

DPF_GF_LANE_OPS(gf2)
DPF_GF_LANE_OPS(gf22)
DPF_GF_LANE_OPS(gf24)
DPF_GF_LANE_OPS(gf28)
DPF_GF_LANE_OPS(gf216)
DPF_GF_LANE_OPS(gf232)
DPF_GF_LANE_OPS(gf264)
#undef DPF_GF_LANE_OPS

namespace utils
{

template <unsigned Bits>
struct bitlength_of<gf2n<Bits>>
    : std::integral_constant<std::size_t, Bits>
{ };

template <unsigned Bits, typename NodeT>
struct bitlength_of_output<gf2n<Bits>, NodeT>
    : std::integral_constant<std::size_t, Bits>
{ };

template <unsigned Bits>
struct is_packed_subbyte<gf2n<Bits>> : std::bool_constant<(Bits < 8)> {};

template <unsigned Bits>
struct packed_lane_bits<gf2n<Bits>>
    : std::integral_constant<std::size_t, (Bits < 8 ? Bits : 0)> {};

template <unsigned Bits>
struct has_characteristic_two<gf2n<Bits>> : std::true_type {};

}  // namespace utils

namespace leaf_arithmetic
{

template <unsigned Bits, typename NodeT>
struct add_t<gf2n<Bits>, NodeT, std::enable_if_t<!std::is_void_v<NodeT>>>
{
    HEDLEY_ALWAYS_INLINE
    auto operator()(const NodeT & a, const NodeT & b) const noexcept
    {
        return gf2_detail::xor_node(a, b);
    }
};

template <unsigned Bits, typename NodeT>
struct subtract_t<gf2n<Bits>, NodeT, std::enable_if_t<!std::is_void_v<NodeT>>>
{
    HEDLEY_ALWAYS_INLINE
    auto operator()(const NodeT & a, const NodeT & b) const noexcept
    {
        return gf2_detail::xor_node(a, b);
    }
};

template <unsigned Bits, typename NodeT>
struct multiply_t<gf2n<Bits>, NodeT, std::enable_if_t<!std::is_void_v<NodeT>>>
{
    HEDLEY_ALWAYS_INLINE
    auto operator()(const NodeT & a, gf2n<Bits> b) const noexcept
    {
        return gf2_detail::scale_node<Bits>(a, b.raw());
    }
};

}  // namespace leaf_arithmetic

}  // namespace dpf

#include "dpf/output_buffer.hpp"

namespace dpf
{

template <>
class output_buffer<gf2> : public dynamic_packed_array<gf2>
{
    using base = dynamic_packed_array<gf2>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<gf22> : public dynamic_packed_array<gf22>
{
    using base = dynamic_packed_array<gf22>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<gf24> : public dynamic_packed_array<gf24>
{
    using base = dynamic_packed_array<gf24>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<subtractive_share<gf2, 0>> : public packed_share_output<gf2, 0>
{
    using base = packed_share_output<gf2, 0>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<subtractive_share<gf2, 1>> : public packed_share_output<gf2, 1>
{
    using base = packed_share_output<gf2, 1>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<subtractive_share<gf22, 0>> : public packed_share_output<gf22, 0>
{
    using base = packed_share_output<gf22, 0>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<subtractive_share<gf22, 1>> : public packed_share_output<gf22, 1>
{
    using base = packed_share_output<gf22, 1>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<subtractive_share<gf24, 0>> : public packed_share_output<gf24, 0>
{
    using base = packed_share_output<gf24, 0>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

template <>
class output_buffer<subtractive_share<gf24, 1>> : public packed_share_output<gf24, 1>
{
    using base = packed_share_output<gf24, 1>;
  public:
    using size_type = typename base::size_type;
    explicit output_buffer(size_type size) : base(size) { }
    output_buffer(output_buffer &&) noexcept = default;
    output_buffer(const output_buffer &) = delete;
    output_buffer & operator=(output_buffer &&) noexcept = default;
    output_buffer & operator=(const output_buffer &) = delete;
    ~output_buffer() noexcept = default;
};

}  // namespace dpf

#include "dpf/shamir.hpp"

namespace dpf
{
namespace detail
{

/// @brief Shamir inverse for `gf2n`. Points `1 .. N` must stay distinct, so
///        `N < 2^Bits`.
template <unsigned Bits>
struct shamir_field<gf2n<Bits>> : std::true_type
{
    /// @brief `a^{-1}` by Fermat, `a^{2^Bits - 2}`.
    /// @param a a nonzero field element
    /// @return `a^{-1}`
    /// @throws std::invalid_argument if `a` is zero
    static gf2n<Bits> inv(gf2n<Bits> a)
    {
        return gf2n<Bits>{gf2_detail::inv<Bits>(a.raw())};
    }
};

}  // namespace detail
}  // namespace dpf

#endif  // LIBDPF_INCLUDE_DPF_GF2_HPP__