libdpf/test/tests/geneval_test.cpp

#include <gtest/gtest.h>
#include <tuple>

#include "dpf.hpp"

#include <algorithm>
#include <cstdint>
#include <limits>
#include <cstring>
#include <vector>

namespace
{

simde__m128i g_roots[8];
int g_ri = 0;
simde__m128i take_root() { return g_roots[g_ri++]; }

struct Pad
{
    uint64_t n = 1;
    simde__m128i block()
    {
        auto v = simde_mm_set_epi64x(static_cast<long long>(n),
            static_cast<long long>(n * 9 + 3));
        n += 2;
        return v;
    }
    uint8_t bit() { return static_cast<uint8_t>(n++ & 1u); }
};

void reset_roots()
{
    g_ri = 0;
    for (int i = 0; i < 8; ++i)
        g_roots[i] = simde_mm_set_epi64x(0x1111 * (i + 1), 0xA5A50000u + i * 17);
}

template <typename T>
T bare(const T & v)
{
    return v;
}

template <typename T, std::size_t Party, dpf::sharing Scheme>
T bare(const dpf::secret_share<T, Party, Scheme> & s)
{
    return s.raw();
}

template <typename A, typename B>
auto recon(const A & a, const B & b)
{
    using T = decltype(bare(a));
    // Subtractive reconstruction: party 0 minus party 1.
    return static_cast<T>(bare(a) - bare(b));
}

template <typename Key, typename In>
auto ev(const Key & key, In x)
{
    return bare(*dpf::eval_point(key, x));
}

template <typename Key>
uint64_t leaf_of(typename Key::input_type x)
{
    dpf::utils::flip_msb_if_signed_integral(x);
    return static_cast<uint64_t>(dpf::utils::get_from_node<Key>(x));
}

std::size_t lcp_bits(uint64_t a, uint64_t b, std::size_t depth)
{
    std::size_t n = 0;
    for (std::size_t i = 0; i < depth; ++i)
    {
        const std::size_t sh = depth - 1 - i;
        if (((a >> sh) & 1ull) != ((b >> sh) & 1ull))
            break;
        ++n;
    }
    return n;
}

std::size_t live_through_lcp(std::size_t lcp, std::size_t depth)
{
    return std::min(depth, lcp + 1);
}

HEDLEY_PRAGMA(GCC diagnostic push)
HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
template <typename Key>
void expect_prefix_words(const Key & key, const std::vector<simde__m128i,
        dpf::aligned_allocator<simde__m128i>> & cws,
    const std::vector<uint8_t> & advice, std::size_t live, bool leaf_live,
    const void * leaf, std::size_t leaf_bytes)
{
    ASSERT_LE(live, cws.size());
    ASSERT_EQ(advice.size(), cws.size());
    for (std::size_t i = 0; i < live; ++i)
    {
        EXPECT_EQ(std::memcmp(&cws[i], &key.correction_word(i), sizeof(simde__m128i)), 0)
            << "cw " << i;
        EXPECT_EQ(advice[i], key.correction_advice(i)) << "advice " << i;
    }
    if (leaf_live)
    {
        EXPECT_EQ(live, Key::depth);
        EXPECT_EQ(std::memcmp(leaf, &key.template leaf<0>(), leaf_bytes), 0);
    }
}

template <typename T>
dpf::ds_randomness<simde__m128i (*)(), Pad> rng()
{
    return {take_root, Pad{}};
}
HEDLEY_PRAGMA(GCC diagnostic pop)

}  // namespace

TEST(Geneval, PointOnTargetMatchesKeyAndEval)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x0abc;
    in_t x0 = 0x1111;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 0x4242;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_point(x0, x1, alpha, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    const auto id = leaf_of<key_t>(alpha);
    const std::size_t live = live_through_lcp(lcp_bits(id, id, key_t::depth), key_t::depth);
    EXPECT_EQ(g.live_levels, live);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, g.leaf_live, &g.leaf, sizeof(g.leaf));

    auto e0 = ev(keys.first, alpha);
    auto e1 = ev(keys.second, alpha);
    ASSERT_EQ(g.party0.size(), 1u);
    EXPECT_EQ(g.party0[0], e0);
    EXPECT_EQ(g.party1[0], e1);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), y);
}

TEST(Geneval, PointDivergesAfterSharedPrefix)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x0abc;
    in_t query = 0x0a7e;
    in_t x0 = 0x00ff;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 7;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_point(x0, x1, query, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(query), key_t::depth),
        key_t::depth);
    EXPECT_LT(live, key_t::depth);
    EXPECT_EQ(g.live_levels, live);
    EXPECT_FALSE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, false, nullptr, 0);

    auto e0 = ev(keys.first, query);
    auto e1 = ev(keys.second, query);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), recon(e0, e1));
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), out_t{0});
}

TEST(Geneval, SameLeafDifferentLane)
{
    using in_t = uint16_t;
    using out_t = uint8_t;
    in_t alpha = 0x1234;
    in_t query = static_cast<in_t>(alpha ^ 1u);
    in_t x0 = 0x0101;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 9;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    using key_t = std::decay_t<decltype(keys.first)>;
    ASSERT_GT(key_t::lg_outputs_per_leaf, 0u);
    ASSERT_EQ(leaf_of<key_t>(alpha), leaf_of<key_t>(query));

    reset_roots();
    auto g = dpf::geneval_point(x0, x1, query, rng<in_t>(), y);
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));

    auto e0 = ev(keys.first, query);
    auto e1 = ev(keys.second, query);
    EXPECT_EQ(g.party0[0], e0);
    EXPECT_EQ(g.party1[0], e1);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), out_t{0});
}

TEST(Geneval, IntervalContainsTarget)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 1000;
    in_t from = 990;
    in_t to = 1010;
    in_t x0 = 0x0f0f;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 33;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_interval(x0, x1, from, to, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));

    ASSERT_EQ(g.party0.size(), static_cast<std::size_t>(to - from) + 1);
    for (in_t q = from; ; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q - from);
        auto e0 = ev(keys.first, q);
        auto e1 = ev(keys.second, q);
        EXPECT_EQ(g.party0[i], e0) << q;
        EXPECT_EQ(g.party1[i], e1) << q;
        const out_t want = (q == alpha) ? y : out_t{0};
        EXPECT_EQ(recon(g.party0[i], g.party1[i]), want) << q;
        if (q == to)
            break;
    }
}

TEST(Geneval, IntervalMissesAfterSharedPrefix)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x8000;
    in_t from = 0x8100;
    in_t to = 0x8108;
    in_t x0 = 1;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 5;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_interval(x0, x1, from, to, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    const auto a = leaf_of<key_t>(alpha);
    const auto q = leaf_of<key_t>(from);
    const auto live = live_through_lcp(lcp_bits(a, q, key_t::depth), key_t::depth);
    EXPECT_LT(g.live_levels, key_t::depth);
    EXPECT_EQ(g.live_levels, live);
    EXPECT_FALSE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, false, nullptr, 0);

    for (std::size_t i = 0; i < g.party0.size(); ++i)
        EXPECT_EQ(recon(g.party0[i], g.party1[i]), out_t{0}) << i;
}

TEST(Geneval, SequenceOrderAndSharedTrie)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x2222;
    in_t x0 = 0x00aa;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 11;
    const in_t xs[] = {0x2200, alpha, 0x00ff, alpha, 0x2223};

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_sequence(x0, x1, std::begin(xs), std::end(xs), rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_TRUE(g.leaf_live);
    EXPECT_EQ(g.live_levels, key_t::depth);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));

    ASSERT_EQ(g.party0.size(), 5u);
    for (std::size_t i = 0; i < 5; ++i)
    {
        auto e0 = ev(keys.first, xs[i]);
        auto e1 = ev(keys.second, xs[i]);
        EXPECT_EQ(g.party0[i], e0);
        EXPECT_EQ(g.party1[i], e1);
        EXPECT_EQ(recon(g.party0[i], g.party1[i]), xs[i] == alpha ? y : out_t{0});
    }

    reset_roots();
    auto miss = dpf::geneval_sequence(x0, x1, xs, xs + 1, rng<in_t>(), y);
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(xs[0]), key_t::depth),
        key_t::depth);
    EXPECT_EQ(miss.live_levels, live);
    EXPECT_LT(miss.live_levels, key_t::depth);
    expect_prefix_words(keys.first, miss.correction_words, miss.correction_advice,
        miss.live_levels, false, nullptr, 0);
    EXPECT_EQ(recon(miss.party0[0], miss.party1[0]), out_t{0});
}

TEST(Geneval, FullDomainUint8)
{
    using in_t = uint8_t;
    using out_t = uint8_t;
    in_t alpha = 0x3c;
    in_t x0 = 0x10;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 0x7e;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_full(x0, x1, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.party0.size(), 256u);
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));

    for (int q = 0; q < 256; ++q)
    {
        auto e0 = ev(keys.first, static_cast<in_t>(q));
        auto e1 = ev(keys.second, static_cast<in_t>(q));
        EXPECT_EQ(g.party0[q], e0);
        EXPECT_EQ(g.party1[q], e1);
    }
    EXPECT_EQ(recon(g.party0[alpha], g.party1[alpha]), y);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), out_t{0});
    EXPECT_TRUE(dpf::verify(g.proof0, g.proof1));
    EXPECT_NE(recon(g.party1[alpha], g.party0[alpha]), y);
    g.proof0[0] = simde_mm_xor_si128(g.proof0[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(g.proof0, g.proof1));
}

TEST(Geneval, EmptySequence)
{
    using in_t = uint16_t;
    in_t alpha = 1;
    in_t x0 = 2;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    const in_t * p = nullptr;
    reset_roots();
    auto g = dpf::geneval_sequence(x0, x1, p, p, rng<in_t>(), uint16_t{1});
    EXPECT_TRUE(g.party0.empty());
    EXPECT_EQ(g.live_levels, 0u);
    EXPECT_TRUE(g.correction_words.empty());
}

TEST(Geneval, ArithPointMatchesDealerAtQuery)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t x = 0x1357;
    in_t x0 = 0x0100;
    in_t x1 = static_cast<in_t>(x - x0);
    in_t query = 0x2000;
    out_t y = 99;

    reset_roots();
    auto keys = dpf::make_dpf(x, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_point(dpf::arith_input, x0, x1, query, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(x), leaf_of<key_t>(query), key_t::depth),
        key_t::depth);
    EXPECT_EQ(g.live_levels, live);
    EXPECT_LT(live, key_t::depth);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, g.leaf_live, &g.leaf, sizeof(g.leaf));

    auto e0 = ev(keys.first, query);
    auto e1 = ev(keys.second, query);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), recon(e0, e1));
}

TEST(Geneval, ArithPointOnSecretIsFullKey)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t x = 0x42;
    in_t x0 = 0x10;
    in_t x1 = static_cast<in_t>(x - x0);
    out_t y = 8;

    reset_roots();
    auto keys = dpf::make_dpf(x, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_point(dpf::arith_input, x0, x1, x, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));
    auto e0 = ev(keys.first, x);
    auto e1 = ev(keys.second, x);
    EXPECT_EQ(g.party0[0], e0);
    EXPECT_EQ(g.party1[0], e1);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), y);
}

TEST(Geneval, ArithIntervalAndSequence)
{
    using in_t = uint8_t;
    using out_t = uint8_t;
    in_t x = 40;
    in_t x0 = 7;
    in_t x1 = static_cast<in_t>(x - x0);
    out_t y = 3;

    reset_roots();
    auto keys = dpf::make_dpf(x, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto iv = dpf::geneval_interval(dpf::arith_input, x0, x1, in_t{10}, in_t{20},
        rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    ASSERT_EQ(iv.party0.size(), 11u);
    for (in_t q = 10; q <= 20; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q - 10);
        auto e0 = ev(keys.first, q);
        auto e1 = ev(keys.second, q);
        EXPECT_EQ(recon(iv.party0[i], iv.party1[i]), recon(e0, e1)) << int(q);
    }
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(x), leaf_of<key_t>(in_t{10}), key_t::depth),
        key_t::depth);
    EXPECT_EQ(iv.live_levels, live);
    expect_prefix_words(keys.first, iv.correction_words, iv.correction_advice,
        iv.live_levels, iv.leaf_live, &iv.leaf, sizeof(iv.leaf));

    const in_t seq[] = {1, x, 255, 2};
    reset_roots();
    auto sq = dpf::geneval_sequence(dpf::arith_input, x0, x1,
        std::begin(seq), std::end(seq), rng<in_t>(), y);
    ASSERT_EQ(sq.party0.size(), 4u);
    EXPECT_TRUE(sq.leaf_live);
    EXPECT_EQ(sq.live_levels, key_t::depth);
    expect_prefix_words(keys.first, sq.correction_words, sq.correction_advice,
        sq.live_levels, true, &sq.leaf, sizeof(sq.leaf));
    for (std::size_t i = 0; i < 4; ++i)
    {
        auto e0 = ev(keys.first, seq[i]);
        auto e1 = ev(keys.second, seq[i]);
        EXPECT_EQ(sq.party0[i], e0);
        EXPECT_EQ(sq.party1[i], e1);
        EXPECT_EQ(recon(sq.party0[i], sq.party1[i]), seq[i] == x ? y : out_t{0});
    }
}

TEST(Geneval, ArithFullMatchesDealer)
{
    using in_t = uint8_t;
    using out_t = uint8_t;
    in_t x = 40;
    in_t x0 = 7;
    in_t x1 = static_cast<in_t>(x - x0);
    out_t y = 3;

    reset_roots();
    auto keys = dpf::make_dpf(x, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_full(dpf::arith_input, x0, x1, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.party0.size(), 256u);
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));
    EXPECT_EQ(recon(g.party0[x], g.party1[x]), y);
    for (int q = 0; q < 256; ++q)
    {
        auto e0 = ev(keys.first, static_cast<in_t>(q));
        auto e1 = ev(keys.second, static_cast<in_t>(q));
        EXPECT_EQ(g.party0[q], e0);
        EXPECT_EQ(g.party1[q], e1);
    }
}

TEST(Geneval, DoernerShelatKeyAgreesOnLivePrefix)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x55aa;
    in_t query = 0x5500;
    in_t x0 = 0x1234;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 1;

    reset_roots();
    HEDLEY_PRAGMA(GCC diagnostic push)
    HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
    dpf::ds_randomness<simde__m128i (*)(), Pad> ds_rng{take_root, Pad{}};
    HEDLEY_PRAGMA(GCC diagnostic pop)
    auto ds = dpf::make_dpf_doerner_shelat(x0, x1, ds_rng, y);
    reset_roots();
    auto g = dpf::geneval_point(x0, x1, query, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(ds.first)>;
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(query), key_t::depth),
        key_t::depth);
    EXPECT_EQ(g.live_levels, live);
    EXPECT_GT(live, 0u);
    EXPECT_LT(live, key_t::depth);
    expect_prefix_words(ds.first, g.correction_words, g.correction_advice,
        g.live_levels, false, nullptr, 0);
}

struct PadB
{
    uint64_t n = 99;
    simde__m128i block()
    {
        auto v = simde_mm_set_epi64x(static_cast<long long>(n * 7),
            static_cast<long long>(n ^ 0x5a5a));
        n += 3;
        return v;
    }
    uint8_t bit() { return static_cast<uint8_t>((n++ >> 2) & 1u); }
};

template <typename Key, typename In>
std::size_t best_live(const Key &, In alpha, const std::vector<In> & qs)
{
    using key_t = Key;
    const auto a = leaf_of<key_t>(alpha);
    std::size_t best = 0;
    for (In q : qs)
        best = std::max(best, lcp_bits(a, leaf_of<key_t>(q), key_t::depth));
    return live_through_lcp(best, key_t::depth);
}

template <typename T>
std::vector<T> span_inclusive(T from, T to)
{
    std::vector<T> qs;
    for (T q = from; ; ++q)
    {
        qs.push_back(q);
        if (q == to)
            break;
    }
    return qs;
}

TEST(Geneval, EdgesZeroMaxAndSinglePointShapesAgree)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0;
    in_t x0 = 0xffff;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 0x1111;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    using key_t = std::decay_t<decltype(keys.first)>;

    for (in_t q : {in_t{0}, in_t{1}, in_t{0x8000}, in_t{0xffff}})
    {
        reset_roots();
        auto pt = dpf::geneval_point(x0, x1, q, rng<in_t>(), y);
        reset_roots();
        auto iv = dpf::geneval_interval(x0, x1, q, q, rng<in_t>(), y);
        const in_t seq[] = {q};
        reset_roots();
        auto sq = dpf::geneval_sequence(x0, x1, std::begin(seq), std::end(seq),
            rng<in_t>(), y);

        const auto live = live_through_lcp(
            lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(q), key_t::depth),
            key_t::depth);
        EXPECT_EQ(pt.live_levels, live) << q;
        EXPECT_EQ(iv.live_levels, live) << q;
        EXPECT_EQ(sq.live_levels, live) << q;
        EXPECT_EQ(pt.correction_words.size(), key_t::depth);
        EXPECT_EQ(std::memcmp(pt.correction_words.data(), iv.correction_words.data(),
            key_t::depth * sizeof(simde__m128i)), 0) << q;
        EXPECT_EQ(std::memcmp(pt.correction_words.data(), sq.correction_words.data(),
            key_t::depth * sizeof(simde__m128i)), 0) << q;
        EXPECT_EQ(pt.correction_advice, iv.correction_advice);
        EXPECT_EQ(pt.correction_advice, sq.correction_advice);
        EXPECT_EQ(recon(pt.party0[0], pt.party1[0]), q == alpha ? y : out_t{0});
        EXPECT_EQ(recon(iv.party0[0], iv.party1[0]), recon(pt.party0[0], pt.party1[0]));
        EXPECT_EQ(recon(sq.party0[0], sq.party1[0]), recon(pt.party0[0], pt.party1[0]));
        if (live < key_t::depth)
        {
            EXPECT_NE(std::memcmp(&pt.correction_words[live],
                &keys.first.correction_word(live), sizeof(simde__m128i)), 0) << q;
            auto e0 = ev(keys.first, q);
            EXPECT_NE(pt.party0[0], e0) << q;
        }
    }
}

TEST(Geneval, XorSplitAndPadStreamDoNotChangeLiveWords)
{
    using in_t = uint16_t;
    using out_t = uint32_t;
    in_t alpha = 0x0f0f;
    in_t query = 0x0e00;
    out_t y = 0xabcdef01u;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    using key_t = std::decay_t<decltype(keys.first)>;
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(query), key_t::depth),
        key_t::depth);
    ASSERT_GT(live, 0u);
    ASSERT_LT(live, key_t::depth);

    auto check = [&](in_t x0, auto pad, const char * name) {
        in_t x1 = static_cast<in_t>(alpha ^ x0);
        reset_roots();
        HEDLEY_PRAGMA(GCC diagnostic push)
        HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
        dpf::ds_randomness<simde__m128i (*)(), decltype(pad)> r{take_root, pad};
        HEDLEY_PRAGMA(GCC diagnostic pop)
        auto g = dpf::geneval_point(x0, x1, query, r, y);
        EXPECT_EQ(g.live_levels, live) << name;
        expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
            live, false, nullptr, 0);
        EXPECT_NE(std::memcmp(&g.correction_words[live],
            &keys.first.correction_word(live), sizeof(simde__m128i)), 0) << name;
    };
    check(0, Pad{}, "share 0");
    check(alpha, Pad{}, "share alpha");
    check(0x1234, Pad{}, "mixed share");
    check(0x1234, PadB{}, "other pads");
}

TEST(Geneval, IntervalLiveFollowsLongestPrefixNotTheFirstPoint)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x0f08;
    in_t from = 0x0000;
    in_t to = 0x0f00;
    in_t x0 = 0x00ff;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 4;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_interval(x0, x1, from, to, rng<in_t>(), y);
    using key_t = std::decay_t<decltype(keys.first)>;

    const auto only_from = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(from), key_t::depth),
        key_t::depth);
    const auto want = best_live(keys.first, alpha, span_inclusive(from, to));
    EXPECT_GT(want, only_from);
    EXPECT_FALSE(g.leaf_live);
    EXPECT_EQ(g.live_levels, want);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, false, nullptr, 0);
    if (g.live_levels < key_t::depth)
    {
        EXPECT_NE(std::memcmp(&g.correction_words[g.live_levels],
            &keys.first.correction_word(g.live_levels), sizeof(simde__m128i)), 0);
    }
    else
    {
        EXPECT_NE(std::memcmp(&g.leaf, &keys.first.template leaf<0>(), sizeof(g.leaf)), 0);
    }

    ASSERT_EQ(g.party0.size(), static_cast<std::size_t>(to - from) + 1);
    for (std::size_t i = 0; i < g.party0.size(); ++i)
        EXPECT_EQ(recon(g.party0[i], g.party1[i]), out_t{0}) << i;
}

TEST(Geneval, PartialLeafExcludesTargetButKeepsItsWord)
{
    using in_t = uint16_t;
    using out_t = uint8_t;
    in_t alpha = 0x1000;
    in_t from = 0x1001;
    in_t to = 0x1005;
    in_t x0 = 7;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 0x5a;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    using key_t = std::decay_t<decltype(keys.first)>;
    ASSERT_GT(key_t::lg_outputs_per_leaf, 0u);
    ASSERT_EQ(leaf_of<key_t>(alpha), leaf_of<key_t>(from));
    ASSERT_NE(alpha, from);

    reset_roots();
    auto g = dpf::geneval_interval(x0, x1, from, to, rng<in_t>(), y);
    EXPECT_TRUE(g.leaf_live);
    EXPECT_EQ(g.live_levels, key_t::depth);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));
    for (in_t q = from; q <= to; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q - from);
        EXPECT_EQ(g.party0[i], ev(keys.first, q));
        EXPECT_EQ(g.party1[i], ev(keys.second, q));
        EXPECT_EQ(recon(g.party0[i], g.party1[i]), out_t{0});
    }
}

TEST(Geneval, DepthOneBitOutput)
{
    using in_t = uint8_t;
    using out_t = dpf::bit;
    in_t alpha = 0x80;
    in_t other = 0x7f;
    in_t same_leaf = 0x81;
    in_t x0 = 0x3c;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = dpf::bit::one;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    using key_t = std::decay_t<decltype(keys.first)>;
    ASSERT_EQ(key_t::depth, 1u);

    reset_roots();
    auto on = dpf::geneval_point(x0, x1, alpha, rng<in_t>(), y);
    EXPECT_EQ(on.live_levels, 1u);
    EXPECT_TRUE(on.leaf_live);
    expect_prefix_words(keys.first, on.correction_words, on.correction_advice,
        1, true, &on.leaf, sizeof(on.leaf));
    EXPECT_EQ(recon(on.party0[0], on.party1[0]), y);
    EXPECT_EQ(on.party0[0], ev(keys.first, alpha));

    reset_roots();
    auto lane = dpf::geneval_point(x0, x1, same_leaf, rng<in_t>(), y);
    EXPECT_TRUE(lane.leaf_live);
    EXPECT_EQ(recon(lane.party0[0], lane.party1[0]), out_t{false});
    EXPECT_EQ(lane.party0[0], ev(keys.first, same_leaf));

    reset_roots();
    auto off = dpf::geneval_point(x0, x1, other, rng<in_t>(), y);
    EXPECT_EQ(off.live_levels, 1u);
    EXPECT_FALSE(off.leaf_live);
    expect_prefix_words(keys.first, off.correction_words, off.correction_advice,
        1, false, nullptr, 0);
    EXPECT_EQ(recon(off.party0[0], off.party1[0]), out_t{false});
    EXPECT_NE(std::memcmp(&off.leaf, &keys.first.template leaf<0>(), sizeof(off.leaf)), 0);
}

TEST(Geneval, FullMatchesWholeIntervalAndRejectsHugeDomain)
{
    using in_t = uint8_t;
    using out_t = uint8_t;
    in_t alpha = 255;
    in_t x0 = 0;
    in_t x1 = alpha;
    out_t y = 9;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto full = dpf::geneval_full(x0, x1, rng<in_t>(), y);
    reset_roots();
    auto iv = dpf::geneval_interval(x0, x1, in_t{0}, in_t{255}, rng<in_t>(), y);
    ASSERT_EQ(full.party0.size(), iv.party0.size());
    EXPECT_EQ(full.correction_advice, iv.correction_advice);
    EXPECT_EQ(std::memcmp(full.correction_words.data(), iv.correction_words.data(),
        full.correction_words.size() * sizeof(simde__m128i)), 0);
    for (std::size_t i = 0; i < full.party0.size(); ++i)
    {
        EXPECT_EQ(full.party0[i], iv.party0[i]);
        EXPECT_EQ(full.party1[i], iv.party1[i]);
    }
    EXPECT_EQ(recon(full.party0[255], full.party1[255]), y);
    EXPECT_EQ(recon(full.party0[0], full.party1[0]), out_t{0});

    EXPECT_THROW(dpf::geneval_full(uint32_t{1}, uint32_t{2}, rng<uint32_t>(),
        uint32_t{1}), std::length_error);
    EXPECT_THROW(dpf::geneval_interval(in_t{5}, in_t{1}, in_t{4}, in_t{3},
        rng<in_t>(), y), std::invalid_argument);
}

TEST(Geneval, SequencePermutationKeepsWordsAndDuplicates)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    in_t alpha = 0x4444;
    in_t x0 = 0x0001;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = 6;
    const in_t fwd[] = {0x1000, 0x0100, alpha, 0x1000};
    const in_t rev[] = {0x1000, alpha, 0x0100, 0x1000};

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto a = dpf::geneval_sequence(x0, x1, std::begin(fwd), std::end(fwd), rng<in_t>(), y);
    reset_roots();
    auto b = dpf::geneval_sequence(x0, x1, std::begin(rev), std::end(rev), rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(a.live_levels, key_t::depth);
    EXPECT_EQ(b.live_levels, key_t::depth);
    EXPECT_EQ(std::memcmp(a.correction_words.data(), b.correction_words.data(),
        key_t::depth * sizeof(simde__m128i)), 0);
    EXPECT_EQ(a.correction_advice, b.correction_advice);
    EXPECT_EQ(recon(a.party0[2], a.party1[2]), y);
    EXPECT_EQ(recon(a.party0[0], a.party1[0]), recon(a.party0[3], a.party1[3]));
    EXPECT_EQ(recon(b.party0[1], b.party1[1]), y);
    EXPECT_EQ(a.party0[0], ev(keys.first, fwd[0]));
    EXPECT_EQ(b.party0[2], ev(keys.first, rev[2]));
}

TEST(Geneval, SignedPointIntervalAndCrossZero)
{
    using in_t = int16_t;
    using out_t = int16_t;
    in_t alpha = -100;
    in_t x0 = 1;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = -25;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    using key_t = std::decay_t<decltype(keys.first)>;

    reset_roots();
    auto on = dpf::geneval_point(x0, x1, alpha, rng<in_t>(), y);
    EXPECT_EQ(on.live_levels, key_t::depth);
    EXPECT_TRUE(on.leaf_live);
    expect_prefix_words(keys.first, on.correction_words, on.correction_advice,
        on.live_levels, true, &on.leaf, sizeof(on.leaf));
    EXPECT_EQ(on.party0[0], ev(keys.first, alpha));
    EXPECT_EQ(on.party1[0], ev(keys.second, alpha));
    EXPECT_EQ(recon(on.party0[0], on.party1[0]), y);

    in_t far = 100;
    reset_roots();
    auto off = dpf::geneval_point(x0, x1, far, rng<in_t>(), y);
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(far), key_t::depth),
        key_t::depth);
    EXPECT_EQ(off.live_levels, live);
    EXPECT_LT(live, key_t::depth);
    expect_prefix_words(keys.first, off.correction_words, off.correction_advice,
        live, false, nullptr, 0);
    EXPECT_EQ(recon(off.party0[0], off.party1[0]), out_t{0});

    in_t from = -3;
    in_t to = 3;
    reset_roots();
    auto iv = dpf::geneval_interval(x0, x1, from, to, rng<in_t>(), y);
    ASSERT_EQ(iv.party0.size(), 7u);
    EXPECT_FALSE(iv.leaf_live);
    for (in_t q = from; ; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q - from);
        EXPECT_EQ(recon(iv.party0[i], iv.party1[i]), out_t{0}) << q;
        EXPECT_EQ(recon(iv.party0[i], iv.party1[i]),
            recon(ev(keys.first, q), ev(keys.second, q))) << q;
        if (q == to)
            break;
    }

    in_t near = -101;
    reset_roots();
    auto around = dpf::geneval_interval(x0, x1, in_t{-102}, in_t{-98}, rng<in_t>(), y);
    EXPECT_TRUE(around.leaf_live);
    EXPECT_EQ(around.live_levels, key_t::depth);
    expect_prefix_words(keys.first, around.correction_words, around.correction_advice,
        around.live_levels, true, &around.leaf, sizeof(around.leaf));
    for (in_t q = -102; q <= -98; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q - in_t{-102});
        EXPECT_EQ(around.party0[i], ev(keys.first, q)) << q;
        EXPECT_EQ(recon(around.party0[i], around.party1[i]), q == alpha ? y : out_t{0});
    }
    (void)near;
}

TEST(Geneval, SignedFullAndArithFull)
{
    using in_t = int8_t;
    using out_t = int8_t;
    in_t alpha = -5;
    in_t x_xor0 = 3;
    in_t x_xor1 = static_cast<in_t>(alpha ^ x_xor0);
    out_t y = -9;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_full(x_xor0, x_xor1, rng<in_t>(), y);
    ASSERT_EQ(g.party0.size(), 256u);
    constexpr auto to_int = dpf::utils::to_integral_type<in_t>{};
    for (int q = -128; q <= 127; ++q)
    {
        in_t v = static_cast<in_t>(q);
        const std::size_t i = static_cast<std::size_t>(to_int(v));
        EXPECT_EQ(g.party0[i], ev(keys.first, v)) << q;
        EXPECT_EQ(g.party1[i], ev(keys.second, v)) << q;
    }

    in_t secret = -20;
    in_t a0 = 100;
    in_t a1 = static_cast<in_t>(secret - a0);
    ASSERT_EQ(static_cast<in_t>(a0 + a1), secret);
    reset_roots();
    auto wkeys = dpf::make_dpf(secret, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto w = dpf::geneval_full(dpf::arith_input, a0, a1, rng<in_t>(), y);
    ASSERT_EQ(w.party0.size(), 256u);
    EXPECT_EQ(w.live_levels, std::decay_t<decltype(wkeys.first)>::depth);
    expect_prefix_words(wkeys.first, w.correction_words, w.correction_advice,
        w.live_levels, true, &w.leaf, sizeof(w.leaf));
    for (int q = -128; q <= 127; ++q)
    {
        in_t v = static_cast<in_t>(q);
        const std::size_t i = static_cast<std::size_t>(to_int(v));
        EXPECT_EQ(w.party0[i], ev(wkeys.first, v)) << q;
        EXPECT_EQ(w.party1[i], ev(wkeys.second, v)) << q;
    }
    EXPECT_EQ(recon(w.party0[static_cast<std::size_t>(to_int(secret))],
                  w.party1[static_cast<std::size_t>(to_int(secret))]), y);
}

TEST(Geneval, ArithShareOverflowAndWrappingInterval)
{
    using in_t = uint8_t;
    using out_t = uint8_t;
    in_t secret = 10;
    in_t x0 = 200;
    in_t x1 = 66;
    ASSERT_EQ(static_cast<in_t>(x0 + x1), secret);
    out_t y = 17;

    reset_roots();
    auto keys = dpf::make_dpf(secret, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto on = dpf::geneval_point(dpf::arith_input, x0, x1, secret, rng<in_t>(), y);
    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(on.live_levels, key_t::depth);
    EXPECT_TRUE(on.leaf_live);
    expect_prefix_words(keys.first, on.correction_words, on.correction_advice,
        on.live_levels, true, &on.leaf, sizeof(on.leaf));
    EXPECT_EQ(recon(on.party0[0], on.party1[0]), y);

    in_t query = 250;
    reset_roots();
    auto off = dpf::geneval_point(dpf::arith_input, x0, x1, query, rng<in_t>(), y);
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(secret), leaf_of<key_t>(query), key_t::depth),
        key_t::depth);
    EXPECT_EQ(off.live_levels, live);
    expect_prefix_words(keys.first, off.correction_words, off.correction_advice,
        off.live_levels, off.leaf_live, &off.leaf, sizeof(off.leaf));
    EXPECT_EQ(recon(off.party0[0], off.party1[0]),
        recon(ev(keys.first, query), ev(keys.second, query)));

    in_t from = 250;
    in_t to = 10;
    EXPECT_THROW(dpf::geneval_interval(dpf::arith_input, x0, x1, from, to,
        rng<in_t>(), y), std::invalid_argument);

    from = 250;
    to = 255;
    reset_roots();
    auto iv = dpf::geneval_interval(dpf::arith_input, x0, x1, from, to,
        rng<in_t>(), y);
    ASSERT_EQ(iv.party0.size(), 6u);
    for (in_t q = from; ; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(static_cast<in_t>(q - from));
        EXPECT_EQ(recon(iv.party0[i], iv.party1[i]),
            recon(ev(keys.first, q), ev(keys.second, q))) << int(q);
        if (q == to)
            break;
    }
}

TEST(Geneval, XorWrapperOutput)
{
    using in_t = uint16_t;
    using out_t = dpf::xor_wrapper<uint32_t>;
    in_t alpha = 0x0102;
    in_t query = 0x0180;
    in_t x0 = 0x00f0;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y{0x01020304u};

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto on = dpf::geneval_point(x0, x1, alpha, rng<in_t>(), y);
    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_TRUE(on.leaf_live);
    expect_prefix_words(keys.first, on.correction_words, on.correction_advice,
        on.live_levels, true, &on.leaf, sizeof(on.leaf));
    EXPECT_EQ(recon(on.party0[0], on.party1[0]), y);
    EXPECT_EQ(on.party0[0], ev(keys.first, alpha));

    reset_roots();
    auto off = dpf::geneval_point(x0, x1, query, rng<in_t>(), y);
    const auto live = live_through_lcp(
        lcp_bits(leaf_of<key_t>(alpha), leaf_of<key_t>(query), key_t::depth),
        key_t::depth);
    EXPECT_EQ(off.live_levels, live);
    EXPECT_LT(live, key_t::depth);
    expect_prefix_words(keys.first, off.correction_words, off.correction_advice,
        live, false, nullptr, 0);
    EXPECT_EQ(recon(off.party0[0], off.party1[0]), out_t{0});
}

TEST(Geneval, SignedRegressionsFromTheCornerPass)
{
    using in_t = int8_t;
    using out_t = int8_t;
    in_t alpha = -40;
    in_t x0 = 3;
    in_t x1 = static_cast<in_t>(alpha ^ x0);
    out_t y = -7;

    // An inverted signed range must not wrap the long way around.
    EXPECT_THROW(dpf::geneval_interval(in_t{2}, in_t{1}, in_t{4}, in_t{-3},
        rng<in_t>(), y), std::invalid_argument);

    // [INT_MIN, INT_MAX] is numeric order; full is bit-pattern order.
    // The words are the same trie. Each input's share matches either way.
    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto full = dpf::geneval_full(x0, x1, rng<in_t>(), y);
    reset_roots();
    auto iv = dpf::geneval_interval(x0, x1, std::numeric_limits<in_t>::min(),
        std::numeric_limits<in_t>::max(), rng<in_t>(), y);
    ASSERT_EQ(full.party0.size(), 256u);
    ASSERT_EQ(iv.party0.size(), 256u);
    EXPECT_EQ(std::memcmp(full.correction_words.data(), iv.correction_words.data(),
        full.correction_words.size() * sizeof(simde__m128i)), 0);
    EXPECT_EQ(full.correction_advice, iv.correction_advice);
    constexpr auto to_int = dpf::utils::to_integral_type<in_t>{};
    for (int q = -128; q <= 127; ++q)
    {
        in_t v = static_cast<in_t>(q);
        const std::size_t bit = static_cast<std::size_t>(to_int(v));
        const std::size_t num = static_cast<std::size_t>(q - (-128));
        EXPECT_EQ(full.party0[bit], iv.party0[num]) << q;
        EXPECT_EQ(full.party1[bit], iv.party1[num]) << q;
        EXPECT_EQ(full.party0[bit], ev(keys.first, v)) << q;
    }

    // Negative secret, additive shares that wrap through the signed MSB.
    in_t secret = -20;
    in_t a0 = 100;
    in_t a1 = static_cast<in_t>(secret - a0);
    ASSERT_EQ(static_cast<in_t>(a0 + a1), secret);
    in_t query = 60;
    reset_roots();
    auto akeys = dpf::make_dpf(secret, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_point(dpf::arith_input, a0, a1, query, rng<in_t>(), y);
    EXPECT_EQ(recon(g.party0[0], g.party1[0]),
        recon(ev(akeys.first, query), ev(akeys.second, query)));
    expect_prefix_words(akeys.first, g.correction_words, g.correction_advice,
        g.live_levels, g.leaf_live, &g.leaf, sizeof(g.leaf));
}

TEST(Geneval, CmpEmptyRangeOpensNothing)
{
    reset_roots();
    const uint8_t ends[] = {0};
    auto g = dpf::geneval_cmp(uint8_t{1}, uint8_t{2}, ends, ends, rng<uint8_t>(),
        uint64_t{1});
    EXPECT_TRUE(g.party0.empty());
    EXPECT_TRUE(g.party1.empty());
    EXPECT_EQ(g.live_levels, 0u);
    EXPECT_TRUE(g.value_cw.empty());
}

TEST(Geneval, CmpMatchesDoernerShelatKeyAndGtPredicate)
{
    using in_t = uint8_t;
    const in_t alpha = 40;
    const in_t x0 = 0x11;
    const in_t x1 = static_cast<in_t>(alpha ^ x0);
    const uint64_t beta = 7;
    const std::vector<in_t> ends{0, 1, 10, 40, 200, 255, 40};

    reset_roots();
    auto keys = dpf::make_dpf_doerner_shelat(x0, x1, rng<in_t>(), dpf::gt(beta));
    reset_roots();
    auto g = dpf::geneval_cmp(x0, x1, ends.begin(), ends.end(), rng<in_t>(), beta);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.live_levels, key_t::depth);
    ASSERT_EQ(g.correction_words.size(), key_t::depth);
    ASSERT_EQ(g.value_cw.size(), key_t::depth);
    for (std::size_t level = 0; level < key_t::depth; ++level)
    {
        EXPECT_EQ(std::memcmp(&g.correction_words[level],
            &keys.first.correction_word(level), sizeof(simde__m128i)), 0) << level;
        EXPECT_EQ(g.correction_advice[level], keys.first.correction_advice(level)) << level;
        EXPECT_EQ(g.value_cw[level], keys.first.value_cw(level)) << level;
    }
    EXPECT_EQ(g.cw_last, keys.first.cw_last());
    EXPECT_EQ(g.addend0, keys.first.cmp_addend().raw());
    EXPECT_EQ(g.addend1, keys.second.cmp_addend().raw());
    EXPECT_EQ((g.addend0 + g.addend1) & g.mask, beta);
    ASSERT_EQ(g.party0.size(), ends.size());

    for (std::size_t i = 0; i < ends.size(); ++i)
    {
        const auto e0 = dpf::eval_point(dpf::cmp, keys.first, ends[i]);
        const auto e1 = dpf::eval_point(dpf::cmp, keys.second, ends[i]);
        EXPECT_EQ(g.party0[i], e0.raw()) << int(ends[i]);
        EXPECT_EQ(g.party1[i], e1.raw()) << int(ends[i]);
        const uint64_t opened = (g.party0[i] + g.party1[i]) & g.mask;
        EXPECT_EQ(opened, ends[i] > alpha ? beta : 0u) << int(ends[i]);
    }
}

TEST(Geneval, CmpSignedPayloadAndDomainMax)
{
    using in_t = int16_t;
    const in_t alpha = -3;
    const in_t x0 = 9;
    const in_t x1 = static_cast<in_t>(alpha ^ x0);
    const uint64_t beta = 5;
    const std::vector<in_t> ends{-100, -3, -2, 0, 4, 32767};

    reset_roots();
    auto g = dpf::geneval_cmp(x0, x1, ends.begin(), ends.end(), rng<in_t>(),
        dpf::gt(beta));
    EXPECT_EQ(g.live_levels, 16u);
    EXPECT_EQ(g.value_cw.size(), g.live_levels);
    for (std::size_t i = 0; i < ends.size(); ++i)
    {
        const uint64_t opened = (g.party0[i] + g.party1[i]) & g.mask;
        EXPECT_EQ(opened, ends[i] > alpha ? beta : 0u) << ends[i];
    }

    const in_t top0 = 1;
    const in_t top = std::numeric_limits<in_t>::max();
    const in_t top1 = static_cast<in_t>(top ^ top0);
    const std::vector<in_t> all{std::numeric_limits<in_t>::min(), in_t{0}, top};
    reset_roots();
    auto trivial = dpf::geneval_cmp(top0, top1, all.begin(), all.end(), rng<in_t>(),
        uint64_t{1});
    for (std::size_t i = 0; i < all.size(); ++i)
        EXPECT_EQ((trivial.party0[i] + trivial.party1[i]) & trivial.mask, 0u) << all[i];
}

TEST(Geneval, CmpLtIsTheComplementOfTheStrictUpperSet)
{
    using in_t = uint8_t;
    const in_t alpha = 10;
    const in_t x0 = 3;
    const in_t x1 = static_cast<in_t>(alpha ^ x0);
    const std::vector<in_t> ends{0, 10, 11, 255};
    reset_roots();
    auto g = dpf::geneval_cmp(x0, x1, ends.begin(), ends.end(), rng<in_t>(),
        dpf::lt(uint64_t{4}));
    for (std::size_t i = 0; i < ends.size(); ++i)
    {
        const uint64_t opened = (g.party0[i] + g.party1[i]) & g.mask;
        EXPECT_EQ(opened, ends[i] < alpha ? 4u : 0u) << int(ends[i]);
    }
}

TEST(Geneval, DoernerShelatOnTargetSharesMatch)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    const in_t alpha = 0x55aa;
    const in_t x0 = 0x1234;
    const in_t x1 = static_cast<in_t>(alpha ^ x0);
    const out_t y = 0x9f3c;

    reset_roots();
    HEDLEY_PRAGMA(GCC diagnostic push)
    HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
    dpf::ds_randomness<simde__m128i (*)(), Pad> ds_rng{take_root, Pad{}};
    HEDLEY_PRAGMA(GCC diagnostic pop)
    auto ds = dpf::make_dpf_doerner_shelat(x0, x1, ds_rng, y);
    reset_roots();
    auto g = dpf::geneval_point(x0, x1, alpha, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(ds.first)>;
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(ds.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));
    EXPECT_EQ(g.party0[0], ev(ds.first, alpha));
    EXPECT_EQ(g.party1[0], ev(ds.second, alpha));
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), y);
}

TEST(Geneval, WideLiveFrontierMatchesDealer)
{
    using in_t = uint16_t;
    using out_t = uint16_t;
    const in_t alpha = 0x00ff;
    const in_t x0 = 0x0f0f;
    const in_t x1 = static_cast<in_t>(alpha ^ x0);
    const out_t y = 0xabcd;
    const in_t from = 0;
    const in_t to = 0x00ff;

    reset_roots();
    auto keys = dpf::make_dpf(alpha, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_interval(x0, x1, from, to, rng<in_t>(), y);

    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));
    ASSERT_EQ(g.party0.size(), static_cast<std::size_t>(to - from) + 1);
    for (in_t q = from; ; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q - from);
        EXPECT_EQ(g.party0[i], ev(keys.first, q)) << q;
        EXPECT_EQ(g.party1[i], ev(keys.second, q)) << q;
        const out_t opened = recon(g.party0[i], g.party1[i]);
        EXPECT_EQ(opened, q == alpha ? y : out_t{0}) << q;
        if (q == to)
            break;
    }
}

TEST(Geneval, CmpLeqGeqNonzeroElseAndDomainMin)
{
    using in_t = uint8_t;
    const in_t alpha = 10;
    const in_t x0 = 3;
    const in_t x1 = static_cast<in_t>(alpha ^ x0);
    const std::vector<in_t> ends{0, 9, 10, 11, 255};

    auto check = [&](auto spec, auto pred) {
        auto spec_ds = spec;
        auto spec_g = spec;
        reset_roots();
        HEDLEY_PRAGMA(GCC diagnostic push)
        HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
        dpf::ds_randomness<simde__m128i (*)(), Pad> ds_rng{take_root, Pad{}};
        HEDLEY_PRAGMA(GCC diagnostic pop)
        auto ds = dpf::make_dpf_doerner_shelat(x0, x1, ds_rng, spec_ds);
        reset_roots();
        auto g = dpf::geneval_cmp(x0, x1, ends.begin(), ends.end(), rng<in_t>(), spec_g);
        using key_t = std::decay_t<decltype(ds.first)>;
        EXPECT_EQ(g.live_levels, key_t::depth);
        EXPECT_EQ(g.correction_words.size(), key_t::depth);
        for (std::size_t level = 0; level < key_t::depth; ++level)
        {
            EXPECT_EQ(std::memcmp(&g.correction_words[level],
                &ds.first.correction_word(level), sizeof(simde__m128i)), 0) << level;
            EXPECT_EQ(g.correction_advice[level], ds.first.correction_advice(level));
        }
        for (std::size_t i = 0; i < ends.size(); ++i)
        {
            const uint64_t opened = (g.party0[i] + g.party1[i]) & g.mask;
            const uint64_t from_key =
                (dpf::eval_point(dpf::cmp, ds.first, ends[i]).raw()
                    + dpf::eval_point(dpf::cmp, ds.second, ends[i]).raw())
                & ds.first.cmp().mask;
            EXPECT_EQ(opened, from_key) << int(ends[i]);
            EXPECT_EQ(opened, pred(ends[i])) << int(ends[i]);
        }
    };

    check(dpf::leq(uint64_t{5}, uint64_t{2}), [&](in_t e) {
        return e <= alpha ? uint64_t{5} : uint64_t{2};
    });
    check(dpf::geq(uint64_t{5}, uint64_t{2}), [&](in_t e) {
        return e >= alpha ? uint64_t{5} : uint64_t{2};
    });

    using wide = int16_t;
    const wide amin = std::numeric_limits<wide>::min();
    const wide w0 = 1;
    const wide w1 = static_cast<wide>(amin ^ w0);
    const std::vector<wide> wends{amin, static_cast<wide>(amin + 1), wide{-1}, wide{0},
        std::numeric_limits<wide>::max()};
    reset_roots();
    auto g = dpf::geneval_cmp(w0, w1, wends.begin(), wends.end(), rng<wide>(),
        dpf::gt(uint64_t{3}));
    for (std::size_t i = 0; i < wends.size(); ++i)
    {
        const uint64_t opened = (g.party0[i] + g.party1[i]) & g.mask;
        EXPECT_EQ(opened, wends[i] > amin ? 3u : 0u) << wends[i];
    }
}

TEST(Geneval, ArithSignedMsbAndCarryAcrossPowerOfTwo)
{
    using in_t = int8_t;
    using out_t = int8_t;
    const in_t secret = -20;
    const in_t a0 = 100;
    const in_t a1 = static_cast<in_t>(secret - a0);
    ASSERT_EQ(static_cast<in_t>(a0 + a1), secret);
    const out_t y = -7;

    reset_roots();
    auto keys = dpf::make_dpf(secret, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, y);
    reset_roots();
    auto g = dpf::geneval_point(dpf::arith_input, a0, a1, secret, rng<in_t>(), y);
    using key_t = std::decay_t<decltype(keys.first)>;
    EXPECT_EQ(g.live_levels, key_t::depth);
    EXPECT_TRUE(g.leaf_live);
    expect_prefix_words(keys.first, g.correction_words, g.correction_advice,
        g.live_levels, true, &g.leaf, sizeof(g.leaf));
    EXPECT_EQ(g.party0[0], ev(keys.first, secret));
    EXPECT_EQ(g.party1[0], ev(keys.second, secret));
    EXPECT_EQ(recon(g.party0[0], g.party1[0]), y);

    // Carry across 2^k: shares that wrap the unsigned modulus.
    using u8 = uint8_t;
    const u8 usecret = 7;
    const u8 x0 = 200;
    const u8 x1 = static_cast<u8>(usecret - x0);
    ASSERT_EQ(static_cast<u8>(x0 + x1), usecret);
    const u8 uy = 9;

    reset_roots();
    auto ukeys = dpf::make_dpf(usecret, dpf::root_sampler_t<dpf::prg::aes128>{take_root}, uy);
    reset_roots();
    auto iv = dpf::geneval_interval(dpf::arith_input, x0, x1, u8{0}, u8{3},
        rng<u8>(), uy);
    ASSERT_EQ(iv.party0.size(), 4u);
    for (u8 q = 0; q <= 3; ++q)
    {
        const std::size_t i = static_cast<std::size_t>(q);
        EXPECT_EQ(iv.party0[i], ev(ukeys.first, q)) << int(q);
        EXPECT_EQ(iv.party1[i], ev(ukeys.second, q)) << int(q);
        EXPECT_EQ(recon(iv.party0[i], iv.party1[i]),
            recon(ev(ukeys.first, q), ev(ukeys.second, q))) << int(q);
    }
    using ukey_t = std::decay_t<decltype(ukeys.first)>;
    EXPECT_EQ(iv.live_levels,
        live_through_lcp(
            lcp_bits(leaf_of<ukey_t>(usecret), leaf_of<ukey_t>(u8{0}), ukey_t::depth),
            ukey_t::depth));
}

TEST(Geneval, ArithDoernerShelatAndCmpMatchDealer)
{
    using in_t = uint8_t;
    const in_t secret = 40;
    const in_t a0 = 250;
    const in_t a1 = static_cast<in_t>(secret - a0);
    ASSERT_EQ(static_cast<in_t>(a0 + a1), secret);
    const uint64_t beta = 7;
    const std::vector<in_t> ends{0, 1, 10, 40, 200, 255};

    reset_roots();
    auto dealer = dpf::make_dpf(secret, dpf::root_sampler_t<dpf::prg::aes128>{take_root},
        dpf::gt(beta));
    reset_roots();
    auto ds = dpf::make_dpf_doerner_shelat(dpf::arith_input, a0, a1, rng<in_t>(),
        dpf::gt(beta));
    using key_t = std::decay_t<decltype(dealer.first)>;
    for (std::size_t level = 0; level < key_t::depth; ++level)
    {
        EXPECT_EQ(std::memcmp(&ds.first.correction_word(level),
            &dealer.first.correction_word(level), sizeof(simde__m128i)), 0) << level;
        EXPECT_EQ(ds.first.correction_advice(level),
            dealer.first.correction_advice(level)) << level;
        EXPECT_EQ(ds.first.value_cw(level), dealer.first.value_cw(level)) << level;
    }

    reset_roots();
    auto g = dpf::geneval_cmp(dpf::arith_input, a0, a1, ends.begin(), ends.end(),
        rng<in_t>(), beta);
    EXPECT_EQ(g.live_levels, key_t::depth);
    for (std::size_t i = 0; i < ends.size(); ++i)
    {
        const uint64_t opened = (g.party0[i] + g.party1[i]) & g.mask;
        EXPECT_EQ(opened, ends[i] > secret ? beta : 0u) << int(ends[i]);
    }
}

TEST(Geneval, ArithCarryLeavesXorShares)
{
    // 250 + 13 = 7 (mod 256). The carry must not collapse the sharing to (7, 0).
    auto split_u8 = [](std::uint64_t seed) {
        Pad pad;
        pad.n = seed;
        dpf::detail::local_cw_protocol<Pad> proto{pad};
        std::uint8_t x0 = 250;
        std::uint8_t x1 = 13;
        proto.encode_walk_shares(x0, x1, true);
        // Seven carries. Each is one bit-Beaver from `sample_beaver2` on
        // `xor_wrapper<uint8_t>`: `sample_fresh<2>` draws 7 ring elements
        // and each element is 8 pad bits.
        EXPECT_EQ(pad.n, seed + 7u * 7u * 8u);
        EXPECT_EQ(static_cast<std::uint8_t>(x0 ^ x1), 7);
        EXPECT_NE(x1, 0);
        EXPECT_NE(x0, 7);
    };
    split_u8(1);
    split_u8(50);

    Pad pad;
    dpf::detail::local_cw_protocol<Pad> proto{pad};
    const std::int8_t secret = -20;
    std::int8_t a0 = 100;
    std::int8_t a1 = static_cast<std::int8_t>(secret - a0);
    std::int8_t encoded = secret;
    dpf::utils::flip_msb_if_signed_integral(encoded);
    proto.encode_walk_shares(a0, a1, true);
    EXPECT_EQ(static_cast<std::uint8_t>(a0) ^ static_cast<std::uint8_t>(a1),
        static_cast<std::uint8_t>(encoded));
    EXPECT_NE(a1, 0);
}