libdpf/test/tests/carry_test.cpp

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

#include <array>
#include <cstdint>
#include <vector>

#include "dpf.hpp"
#include "grotto/carry_plan.hpp"
#include "grotto/carry.hpp"
#include "grotto/prefix_parity.hpp"

using grotto::carry_mode;
using grotto::sign_knowledge;

TEST(CarryPlan, TruncateReduceOnlyLowLt)
{
    const auto r = grotto::plan_carry_in(8, 3);
    EXPECT_TRUE(r.use_low_lt);
    EXPECT_FALSE(r.use_msb_lt);
    EXPECT_FALSE(r.use_share_msb_and);
    EXPECT_FALSE(r.use_biased_wrap);
    EXPECT_EQ(r.out_n, 5u);
}

TEST(CarryPlan, SameRingKnownSignIsAnd)
{
    const auto pos = grotto::plan_carry_out(8, 2, sign_knowledge::nonnegative);
    EXPECT_TRUE(pos.use_share_msb_and);
    EXPECT_FALSE(pos.and_is_nor);
    EXPECT_FALSE(pos.use_msb_lt);
    EXPECT_EQ(pos.and_unit, std::int64_t{1} << 6);

    const auto neg = grotto::plan_carry_out(8, 2, sign_knowledge::negative);
    EXPECT_TRUE(neg.use_share_msb_and);
    EXPECT_TRUE(neg.and_is_nor);
    EXPECT_EQ(neg.and_unit, -(std::int64_t{1} << 6));
}

TEST(CarryPlan, SameRingSecretSignNeedsBoth)
{
    const auto r = grotto::plan_carry_out(8, 2, sign_knowledge::unknown);
    EXPECT_TRUE(r.use_msb_lt);
    EXPECT_TRUE(r.use_share_msb_and);
}

TEST(CarryPlan, FusedReducedRingDropsSign)
{
    const auto r = grotto::plan_carry_fused(8, 3, 5, sign_knowledge::unknown);
    EXPECT_TRUE(r.use_low_lt);
    EXPECT_FALSE(r.use_msb_lt);
    EXPECT_FALSE(r.use_share_msb_and);
}

TEST(CarryPlan, ExtendIsBiasedWrap)
{
    const auto r = grotto::plan_carry(grotto::carry_request{
        8, 0, 16, carry_mode::extend, sign_knowledge::nonnegative});
    EXPECT_TRUE(r.use_biased_wrap);
    EXPECT_FALSE(r.use_share_msb_and);
    EXPECT_EQ(r.wrap_payload, std::int64_t{1} << 8);
}

TEST(CarryPlan, WindowPublicCarryZeroDropsEq)
{
    grotto::carry_request req{};
    req.n = 16;
    req.s = 4;
    req.out_n = 4;
    req.mode = carry_mode::window;
    req.incoming_carry_public = true;
    req.incoming_carry_value = 0;
    const auto r = grotto::plan_carry(req);
    EXPECT_TRUE(r.use_window_overflow);
    EXPECT_FALSE(r.use_window_eq);
    EXPECT_FALSE(r.use_window_product);
}

TEST(CarryPlan, WindowSecretCarryNeedsProduct)
{
    grotto::carry_request req{};
    req.n = 16;
    req.s = 4;
    req.out_n = 4;
    req.mode = carry_mode::window;
    req.incoming_carry_public = false;
    const auto r = grotto::plan_carry(req);
    EXPECT_TRUE(r.use_window_overflow);
    EXPECT_TRUE(r.use_window_eq);
    EXPECT_TRUE(r.use_window_product);
}

TEST(CarryClear, TruncateReduceMatchesHighPlusCarry)
{
    for (std::uint64_t x0 = 0; x0 < 64; ++x0)
    {
        for (std::uint64_t x1 = 0; x1 < 64; ++x1)
        {
            const auto got = grotto::carry_in_clear(x0, x1, 6, 2);
            const auto x = (x0 + x1) & 63u;
            EXPECT_EQ(got, x >> 2);
        }
    }
}

TEST(CarryClear, CarryOutKnownLeavesOnlySmallResidual)
{
    constexpr unsigned n = 6;
    constexpr unsigned s = 2;
    std::size_t big = 0;
    for (std::uint64_t x0 = 0; x0 < (1u << n); ++x0)
    {
        for (std::uint64_t x1 = 0; x1 < (1u << n); ++x1)
        {
            const auto x = (x0 + x1) & grotto::carry_mask(n);
            const auto true_asr = grotto::carry_asr(x, n, s);
            const auto fixed = grotto::carry_out_clear(x0, x1, n, s,
                sign_knowledge::nonnegative);
            // Known nonnegative assumes msb(x)==0; skip negatives.
            if ((x >> (n - 1)) & 1u)
                continue;
            std::int64_t d = static_cast<std::int64_t>(true_asr)
                - static_cast<std::int64_t>(fixed);
            if (d > 32)
                d -= 64;
            if (d < -32)
                d += 64;
            if (std::abs(d) > 1)
                ++big;
            EXPECT_LE(std::abs(d), 1);
        }
    }
    EXPECT_EQ(big, 0u);
}

TEST(CarryClear, AndDisagreesWithExtensionWrap)
{
    // 4-bit shares: share-MSB AND is not the extension wrap bit.
    std::size_t mismatch = 0;
    for (std::uint64_t x0 = 0; x0 < 16; ++x0)
    {
        for (std::uint64_t x1 = 0; x1 < 16; ++x1)
        {
            const auto wrap = ((x0 + x1) >= 16u) ? 1u : 0u;
            const auto s0 = (x0 >> 3) & 1u;
            const auto s1 = (x1 >> 3) & 1u;
            const auto x = (x0 + x1) & 15u;
            const auto m = (x >> 3) & 1u;
            const auto grotto = (m == 0) ? (s0 & s1) : ((1u - s0) & (1u - s1));
            if (grotto != wrap)
                ++mismatch;
        }
    }
    EXPECT_EQ(mismatch, 112u);
}

TEST(CarryClear, ExtendPreservesSignedValue)
{
    EXPECT_EQ(grotto::carry_extend_clear(0x05, 0x00, 8, 16), 0x0005u);
    EXPECT_EQ(grotto::carry_extend_clear(0x80, 0x00, 8, 16), 0xff80u);
    // 0x7f + 0x01 = 0x80 in 8 bits, which is negative and sign-extends.
    EXPECT_EQ(grotto::carry_extend_clear(0x7f, 0x01, 8, 16), 0xff80u);
    EXPECT_EQ(grotto::carry_extend_clear(0x40, 0x01, 8, 16), 0x0041u);
}

TEST(CarryClear, WindowOutgoingCarry)
{
    const auto w = grotto::carry_window_clear(0x0f, 0x01, 4, 0);
    EXPECT_EQ(w.digit, 0u);
    EXPECT_EQ(w.carry_out, 1u);
    const auto w2 = grotto::carry_window_clear(0x0e, 0x00, 4, 1);
    EXPECT_EQ(w2.digit, 0x0fu);
    EXPECT_EQ(w2.carry_out, 0u);
    const auto w3 = grotto::carry_window_clear(0x0f, 0x00, 4, 1);
    EXPECT_EQ(w3.digit, 0u);
    EXPECT_EQ(w3.carry_out, 1u);
}

TEST(CarryClear, FusedMatchesAsr)
{
    for (std::uint64_t x0 = 0; x0 < 64; ++x0)
        for (std::uint64_t x1 = 0; x1 < 64; ++x1)
            EXPECT_EQ(grotto::carry_fused_clear(x0, x1, 6, 2),
                grotto::carry_asr((x0 + x1) & 63u, 6, 2));
}

TEST(CarryKeys, TruncateReduceOnline)
{
    auto keys = grotto::make_carry_in_keys(8, 3);
    for (int trial = 0; trial < 32; ++trial)
    {
        const std::uint64_t x0 = dpf::uniform_sample<std::uint8_t>();
        const std::uint64_t x1 = dpf::uniform_sample<std::uint8_t>();
        const std::uint64_t x = (x0 + x1) & 0xffu;
        const std::uint64_t opened = (x + keys.rin) & 0xffu;
        dpf::proof_token pi0{}, pi1{};
        const auto y0 = grotto::eval_carry_in(keys, 0, opened);
        const auto y1 = grotto::eval_carry_in(keys, 1, opened);
        const auto got = (y0.value + y1.value) & 0x1fu;
        EXPECT_EQ(got, grotto::carry_in_clear(x0, x1, 8, 3));
        (void)pi0;
        (void)pi1;
    }
}

TEST(CarryKeys, TruncateReduceVerifiableProof)
{
    grotto::carry_auth auth{};
    auth.verifiable = true;
    auto keys = grotto::make_carry_in_keys(8, 3, auth);
    const std::uint64_t x0 = 0x11;
    const std::uint64_t x1 = 0x22;
    const std::uint64_t opened = ((x0 + x1) + keys.rin) & 0xffu;
    dpf::proof_token pi0{}, pi1{};
    const auto y0 = grotto::eval_carry_in(keys, 0, opened, &pi0);
    const auto y1 = grotto::eval_carry_in(keys, 1, opened, &pi1);
    EXPECT_EQ((y0.value + y1.value) & 0x1fu, grotto::carry_in_clear(x0, x1, 8, 3));
    EXPECT_TRUE(dpf::verify(pi0, pi1));

    // Flip every correction seed so some on-path level mixes the tamper.
    for (auto & cs : const_cast<typename std::decay_t<decltype(keys.low_lt_v->first)>::correction_seeds_array &>(
             keys.low_lt_v->first.correction_seeds()))
    {
        cs[0] = simde_mm_xor_si128(cs[0], simde_mm_set1_epi8(1));
    }
    dpf::proof_token q0{}, q1{};
    auto ignore0 = grotto::eval_carry_in(keys, 0, opened, &q0);
    auto ignore1 = grotto::eval_carry_in(keys, 1, opened, &q1);
    (void)ignore0;
    (void)ignore1;
    EXPECT_FALSE(dpf::verify(q0, q1));
}

TEST(CarryKeys, ProveCarryKeysBatch)
{
    grotto::carry_auth auth{};
    auth.verifiable = true;
    auto keys = grotto::make_carry_in_keys(8, 3, auth);
    const std::uint64_t opened = 0x3cu;
    dpf::proof_token t0[4]{}, t1[4]{};
    const auto n0 = grotto::prove_carry_keys(keys, 0, opened, t0, 4);
    const auto n1 = grotto::prove_carry_keys(keys, 1, opened, t1, 4);
    EXPECT_EQ(n0, n1);
    EXPECT_GE(n0, 1u);
    EXPECT_TRUE(dpf::verify_batch(
        std::vector<dpf::proof_token>(t0, t0 + n0),
        std::vector<dpf::proof_token>(t1, t1 + n1)));
}

TEST(CarryKeys, OutputMacDetectsFlip)
{
    grotto::carry_auth auth{};
    auth.verifiable = true;
    auth.output_mac = true;
    auto keys = grotto::make_carry_in_keys(8, 3, auth);
    ASSERT_TRUE(keys.has_mac);
    const std::uint64_t opened = 0x3cu;
    dpf::proof_token t0[4]{}, t1[4]{};
    const auto n0 = grotto::prove_carry_keys(keys, 0, opened, t0, 4);
    const auto n1 = grotto::prove_carry_keys(keys, 1, opened, t1, 4);
    ASSERT_EQ(n0, n1);
    ASSERT_GE(n0, 1u);
    const std::uint64_t y0 = 3;
    const std::uint64_t y1 = 4;
    auto [m0, m1] = grotto::mac_carry_result(keys, y0, y1);
    EXPECT_TRUE(dpf::mac_verify(m0, m1, keys.mac, t0[0], t1[0]));
    EXPECT_FALSE(dpf::mac_verify(m0, m1, keys.mac, dpf::detail::vdpf::zero_proof(),
        t1[0]));
    m0.value ^= 1u;
    EXPECT_FALSE(dpf::mac_verify(m0, m1, keys.mac, t0[0], t1[0]));
}

TEST(CarryCmp, VerifiableComparisonPathProof)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{10}, dpf::lt(std::uint64_t{1}),
        dpf::verifiable{});
    dpf::proof_token pi0{}, pi1{};
    const auto y0 = dpf::eval_point(dpf::cmp, k0, Input{3}, dpf::prove(pi0));
    const auto y1 = dpf::eval_point(dpf::cmp, k1, Input{3}, dpf::prove(pi1));
    EXPECT_EQ(dpf::reconstruct(y0, y1) & 1u, 1u);
    EXPECT_TRUE(dpf::verify(pi0, pi1));

    for (auto & cs : const_cast<typename std::decay_t<decltype(k0)>::correction_seeds_array &>(
             k0.correction_seeds()))
    {
        cs[0] = simde_mm_xor_si128(cs[0], simde_mm_set1_epi8(0x5a));
    }
    dpf::proof_token q0{}, q1{};
    dpf::eval_point(dpf::cmp, k0, Input{3}, dpf::prove(q0));
    dpf::eval_point(dpf::cmp, k1, Input{3}, dpf::prove(q1));
    EXPECT_FALSE(dpf::verify(q0, q1));
}

TEST(OutputMac, BatchVerify)
{
    auto key = dpf::sample_mac_key<std::uint64_t>();
    std::vector<dpf::mac_share<std::uint64_t>> left, right;
    std::vector<std::uint64_t> coeffs;
    for (std::uint64_t i = 0; i < 4; ++i)
    {
        auto [a, b] = dpf::mac_share_value(i * 3u + 1u, key);
        left.push_back(a);
        right.push_back(b);
        coeffs.push_back(i + 1u);
    }
    EXPECT_TRUE(dpf::mac_verify_batch(left, right, coeffs, key));
    left[1].tag ^= 1u;
    EXPECT_FALSE(dpf::mac_verify_batch(left, right, coeffs, key));
}

TEST(CarryKeys, KnownSignCarryOutOnlineMatchesClear)
{
    constexpr unsigned n = 8;
    constexpr unsigned s = 3;
    auto keys = grotto::make_carry_out_keys(n, s, sign_knowledge::nonnegative);
    ASSERT_TRUE(keys.has_and_beaver);
    ASSERT_TRUE(keys.recipe.use_share_msb_and);

    std::size_t checked = 0;
    for (std::uint64_t x0 = 0; x0 < 256; x0 += 17)
    {
        for (std::uint64_t x1 = 0; x1 < 256; x1 += 19)
        {
            const std::uint64_t x = (x0 + x1) & 0xffu;
            if ((x >> (n - 1)) & 1u)
                continue;  // nonnegative assumption
            const std::uint64_t s0 = (x0 >> (n - 1)) & 1u;
            const std::uint64_t s1 = (x1 >> (n - 1)) & 1u;
            const auto y0 = grotto::eval_carry_out_known(keys, 0, x0, s0, s1);
            const auto y1 = grotto::eval_carry_out_known(keys, 1, x1, s1, s0);
            const auto got = (y0.value + y1.value) & 0xffu;
            const auto expect = grotto::carry_out_clear(x0, x1, n, s,
                sign_knowledge::nonnegative);
            EXPECT_EQ(got, expect) << "x0=" << x0 << " x1=" << x1;
            ++checked;
        }
    }
    EXPECT_GT(checked, 50u);
}

TEST(CarryKeys, NegativeSignCarryOutOnlineMatchesClear)
{
    constexpr unsigned n = 8;
    constexpr unsigned s = 3;
    auto keys = grotto::make_carry_out_keys(n, s, sign_knowledge::negative);
    ASSERT_TRUE(keys.recipe.and_is_nor);

    std::size_t checked = 0;
    for (std::uint64_t x0 = 0; x0 < 256; x0 += 17)
    {
        for (std::uint64_t x1 = 0; x1 < 256; x1 += 19)
        {
            const std::uint64_t x = (x0 + x1) & 0xffu;
            if (((x >> (n - 1)) & 1u) == 0u)
                continue;  // negative assumption
            const std::uint64_t s0 = (x0 >> (n - 1)) & 1u;
            const std::uint64_t s1 = (x1 >> (n - 1)) & 1u;
            const auto y0 = grotto::eval_carry_out_known(keys, 0, x0, s0, s1);
            const auto y1 = grotto::eval_carry_out_known(keys, 1, x1, s1, s0);
            const auto got = (y0.value + y1.value) & 0xffu;
            const auto expect = grotto::carry_out_clear(x0, x1, n, s,
                sign_knowledge::negative);
            EXPECT_EQ(got, expect) << "x0=" << x0 << " x1=" << x1;
            ++checked;
        }
    }
    EXPECT_GT(checked, 50u);
}

TEST(CarryKeys, WindowSecretBuildsEqAndOverflow)
{
    grotto::carry_request req{};
    req.n = 16;
    req.s = 4;
    req.out_n = 4;
    req.mode = carry_mode::window;
    req.incoming_carry_public = false;
    auto keys = grotto::make_carry_keys(req);
    EXPECT_TRUE(keys.window_overflow.has_value() || keys.window_overflow_v.has_value());
    EXPECT_TRUE(keys.window_eq.has_value() || keys.window_eq_v.has_value());
    EXPECT_TRUE(keys.has_and_beaver);
}

TEST(CarryKeys, WindowPublicZeroOmitsEq)
{
    grotto::carry_request req{};
    req.n = 16;
    req.s = 4;
    req.out_n = 4;
    req.mode = carry_mode::window;
    req.incoming_carry_public = true;
    req.incoming_carry_value = 0;
    auto keys = grotto::make_carry_keys(req);
    EXPECT_TRUE(keys.window_overflow.has_value() || keys.window_overflow_v.has_value());
    EXPECT_FALSE(keys.window_eq.has_value());
    EXPECT_FALSE(keys.window_eq_v.has_value());
    EXPECT_FALSE(keys.has_and_beaver);
}

TEST(CarryKeys, FusedSameRingPlansBothThenOnlineLowOnlyWhenReduced)
{
    auto reduced = grotto::make_carry_fused_keys(8, 3, 5);
    EXPECT_TRUE(reduced.recipe.use_low_lt);
    EXPECT_FALSE(reduced.recipe.use_share_msb_and);
    EXPECT_TRUE(reduced.low_lt.has_value() || reduced.low_lt_v.has_value());

    auto same = grotto::make_carry_fused_keys(8, 3, 8, sign_knowledge::nonnegative);
    EXPECT_TRUE(same.recipe.use_low_lt);
    EXPECT_TRUE(same.recipe.use_share_msb_and);
    EXPECT_TRUE(same.has_and_beaver);
}

TEST(PrefixParity, VerifiableTokensMatchAndTamperRejects)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x2a}, dpf::bit{1}, dpf::verifiable{});
    // Exclusive of alpha; include alpha itself (must reconstruct to 0).
    const std::array<Input, 3> ends{Input{0x10}, Input{0x2a}, Input{0x40}};

    dpf::proof_token pi0{}, pi1{};
    auto [p0, n0] = grotto::prefix_parities(k0, ends, dpf::prove(pi0));
    auto [p1, n1] = grotto::prefix_parities(k1, ends, dpf::prove(pi1));
    (void)n0;
    (void)n1;
    for (std::size_t i = 0; i < ends.size(); ++i)
        EXPECT_EQ(p0[i] ^ p1[i], ends[i] > Input{0x2a});
    EXPECT_TRUE(dpf::verify(pi0, pi1));

    pi0[0] = simde_mm_xor_si128(pi0[0], simde_mm_set1_epi8(0x3c));
    EXPECT_FALSE(dpf::verify(pi0, pi1));
}

TEST(CarryClear, EvalCarryClearDispatchMatchesHelpers)
{
    const auto tr = grotto::plan_carry_in(8, 3);
    EXPECT_EQ(grotto::eval_carry_clear(tr, 0xab, 0x11),
        grotto::carry_in_clear(0xab, 0x11, 8, 3));

    const auto ext = grotto::plan_carry(grotto::carry_request{
        8, 0, 16, carry_mode::extend});
    EXPECT_EQ(grotto::eval_carry_clear(ext, 0x80, 0),
        grotto::carry_extend_clear(0x80, 0, 8, 16));

    const auto fuse = grotto::plan_carry_fused(8, 2, 8);
    EXPECT_EQ(grotto::eval_carry_clear(fuse, 0x11, 0x22),
        grotto::carry_fused_clear(0x11, 0x22, 8, 2));
}

TEST(CarryKeys, BeaverAndOfPrivateBitsIsOneWhenBothSet)
{
    // Direct check of the AND helper via known-sign path with unit=1, s=0
    // is awkward; instead use n=2,s=1 so unit=2 and check the product bit.
    auto keys = grotto::make_carry_out_keys(4, 1, sign_knowledge::nonnegative);
    // Both MSBs set: x0=0b1xxx, x1=0b1xxx with nonnegative sum.
    // 0b1000 + 0b1000 = 0b0000 mod 16, msb of sum is 0 — OK for nonnegative.
    const std::uint64_t x0 = 0b1000;
    const std::uint64_t x1 = 0b1000;
    const auto y0 = grotto::eval_carry_out_known(keys, 0, x0, 1, 1);
    const auto y1 = grotto::eval_carry_out_known(keys, 1, x1, 1, 1);
    const auto got = (y0.value + y1.value) & 0xfu;
    const auto expect = grotto::carry_out_clear(x0, x1, 4, 1,
        sign_knowledge::nonnegative);
    EXPECT_EQ(got, expect);
    // AND must be 1, so correction is +2^{3}=+8 on top of local ASRs.
    const auto base = (grotto::carry_asr(x0, 4, 1) + grotto::carry_asr(x1, 4, 1)) & 0xfu;
    EXPECT_EQ(got, (base + 8u) & 0xfu);
}

TEST(CarryKeys, UnknownSignMatchesClear)
{
    constexpr unsigned n = 8;
    constexpr unsigned s = 3;
    auto keys = grotto::make_carry_out_keys(n, s, sign_knowledge::unknown);
    ASSERT_TRUE(keys.recipe.use_msb_lt);
    ASSERT_TRUE(keys.recipe.use_share_msb_and);

    std::size_t checked = 0;
    for (std::uint64_t x0 = 0; x0 < 256; x0 += 17)
    {
        for (std::uint64_t x1 = 0; x1 < 256; x1 += 19)
        {
            const std::uint64_t x = (x0 + x1) & 0xffu;
            const std::uint64_t msb_high = (x >> (n - 1)) & 1u;
            const std::uint64_t s0 = (x0 >> (n - 1)) & 1u;
            const std::uint64_t s1 = (x1 >> (n - 1)) & 1u;
            const auto y0 = grotto::eval_carry_out_unknown(keys, 0, x0, s0, s1, msb_high);
            const auto y1 = grotto::eval_carry_out_unknown(keys, 1, x1, s1, s0, msb_high);
            const auto got = (y0.value + y1.value) & 0xffu;
            const auto expect = grotto::carry_out_clear(x0, x1, n, s,
                sign_knowledge::unknown);
            EXPECT_EQ(got, expect) << "x0=" << x0 << " x1=" << x1;
            ++checked;
        }
    }
    EXPECT_GT(checked, 50u);
}

TEST(CarryKeys, ExtendMatchesClear)
{
    auto keys = grotto::make_carry_keys(grotto::carry_request{
        8, 0, 16, carry_mode::extend});
    ASSERT_TRUE(keys.recipe.use_biased_wrap);
    for (std::uint64_t x0 = 0; x0 < 256; x0 += 13)
    {
        for (std::uint64_t x1 = 0; x1 < 256; x1 += 17)
        {
            const std::uint64_t x = (x0 + x1) & 0xffu;
            const std::uint64_t msb_high = (x >> 7) & 1u;
            const std::uint64_t opened = (x + keys.rin) & 0xffu;
            const auto y0 = grotto::eval_carry_extend(keys, 0, opened, msb_high);
            const auto y1 = grotto::eval_carry_extend(keys, 1, opened, msb_high);
            const auto got = (y0.value + y1.value) & 0xffffu;
            EXPECT_EQ(got, grotto::carry_extend_clear(x0, x1, 8, 16))
                << "x0=" << x0 << " x1=" << x1;
        }
    }
}

TEST(CarryKeys, WindowPublicMatchesClear)
{
    grotto::carry_request req{};
    req.n = 16;
    req.s = 4;
    req.out_n = 4;
    req.mode = carry_mode::window;
    req.incoming_carry_public = true;
    req.incoming_carry_value = 1;
    auto keys = grotto::make_carry_keys(req);
    for (std::uint64_t p0 = 0; p0 < 16; ++p0)
    {
        for (std::uint64_t p1 = 0; p1 < 16; ++p1)
        {
            const std::uint64_t sum = p0 + p1 + 1u;
            const auto y0 = grotto::eval_carry_window(keys, 0, sum);
            const auto y1 = grotto::eval_carry_window(keys, 1, sum);
            const auto got = y0.value + y1.value;
            const auto w = grotto::carry_window_clear(p0, p1, 4, 1);
            EXPECT_EQ(got, (w.carry_out << 4) | w.digit);
        }
    }
}

TEST(CarryKeys, FusedReducedMatchesTruncate)
{
    auto keys = grotto::make_carry_fused_keys(8, 3, 5);
    ASSERT_TRUE(keys.recipe.use_low_lt);
    ASSERT_FALSE(keys.recipe.use_share_msb_and);
    for (int trial = 0; trial < 32; ++trial)
    {
        const std::uint64_t x0 = dpf::uniform_sample<std::uint8_t>();
        const std::uint64_t x1 = dpf::uniform_sample<std::uint8_t>();
        const std::uint64_t opened = ((x0 + x1) + keys.rin) & 0xffu;
        const auto y0 = grotto::eval_carry_fused(keys, 0, opened, x0);
        const auto y1 = grotto::eval_carry_fused(keys, 1, opened, x1);
        const auto got = (y0.value + y1.value) & 0x1fu;
        EXPECT_EQ(got, grotto::carry_in_clear(x0, x1, 8, 3));
    }
}

TEST(CarryKeys, FusedSameRingKnownSignMatchesClear)
{
    constexpr unsigned n = 8;
    constexpr unsigned s = 2;
    auto keys = grotto::make_carry_fused_keys(n, s, n, sign_knowledge::nonnegative);
    ASSERT_TRUE(keys.recipe.use_share_msb_and);
    std::size_t checked = 0;
    for (std::uint64_t x0 = 0; x0 < 256; x0 += 21)
    {
        for (std::uint64_t x1 = 0; x1 < 256; x1 += 23)
        {
            const std::uint64_t x = (x0 + x1) & 0xffu;
            if ((x >> (n - 1)) & 1u)
                continue;
            const std::uint64_t s0 = (x0 >> (n - 1)) & 1u;
            const std::uint64_t s1 = (x1 >> (n - 1)) & 1u;
            const std::uint64_t opened = (x + keys.rin) & 0xffu;
            const auto y0 = grotto::eval_carry_fused(keys, 0, opened, x0, s0, s1);
            const auto y1 = grotto::eval_carry_fused(keys, 1, opened, x1, s1, s0);
            const auto got = (y0.value + y1.value) & 0xffu;
            EXPECT_EQ(got, grotto::carry_out_clear(x0, x1, n, s,
                sign_knowledge::nonnegative))
                << "x0=" << x0 << " x1=" << x1;
            ++checked;
        }
    }
    EXPECT_GT(checked, 20u);
}

TEST(CarryKeys, RecipeMakeCarryKeysFinalizesBlinds)
{
    const auto recipe = grotto::plan_carry_in(8, 3);
    auto keys = grotto::make_carry_keys(recipe);
    const std::uint64_t high = grotto::carry_mask(5);
    const std::uint64_t y_hi = ((std::uint64_t{0} - keys.rin) >> 3) & high;
    EXPECT_EQ((keys.rout0 + keys.rout1) & high, y_hi);
}