libdpf/examples/applications/llama.cpp

#include <cstdint>
#include <iostream>

#include "dpf.hpp"
#include "dpf/app_flow.hpp"
#include "dpf/app_plans.hpp"
#include "grotto/carry.hpp"
#include "grotto/carry_plan.hpp"

// LLAMA, the FSS gates that touch a DPF (Gupta, Kumaraswamy, Chandran,
// and Gupta, ePrint 2022/793). Width gates call `grotto::sign_extend` and
// `grotto::truncate_reduce`. A degree-0 spline is one interval key per piece.
//
//   c++ -std=c++17 -march=native -I include -I thirdparty \
//       examples/applications/llama.cpp

int main()
{
    constexpr std::uint8_t r = 20;
    constexpr std::uint8_t knot = 16;
    const std::uint8_t threshold = static_cast<std::uint8_t>(knot + r);

    auto [c0, c1] = dpf::make_dpf(threshold, dpf::gt(std::uint64_t{1}));
    const auto above = dpf::reconstruct(
        dpf::eval_point(dpf::cmp, c0, static_cast<std::uint8_t>(30 + r)),
        dpf::eval_point(dpf::cmp, c1, static_cast<std::uint8_t>(30 + r)));
    const auto below = dpf::reconstruct(
        dpf::eval_point(dpf::cmp, c0, static_cast<std::uint8_t>(4 + r)),
        dpf::eval_point(dpf::cmp, c1, static_cast<std::uint8_t>(4 + r)));
    if (above != 1 || below != 0)
    {
        std::cerr << "llama comparison\n";
        return 1;
    }

    auto [lo0, lo1] = dpf::make_dpf(r, dpf::ic(std::uint8_t{0}, std::uint8_t{15},
        std::uint64_t{2}));
    auto [hi0, hi1] = dpf::make_dpf(r, dpf::ic(std::uint8_t{16}, std::uint8_t{31},
        std::uint64_t{5}));

    auto piece = [&](std::uint8_t x) {
        const std::uint8_t x_hat = static_cast<std::uint8_t>(x + r);
        const auto lo = dpf::reconstruct(
            dpf::eval_point(dpf::ic, lo0, x_hat),
            dpf::eval_point(dpf::ic, lo1, x_hat));
        const auto hi = dpf::reconstruct(
            dpf::eval_point(dpf::ic, hi0, x_hat),
            dpf::eval_point(dpf::ic, hi1, x_hat));
        return lo + hi;
    };
    if (piece(4) != 2 || piece(20) != 5 || piece(40) != 0)
    {
        std::cerr << "llama spline\n";
        return 1;
    }

    // Truncate-reduce: drop 3 low bits of an 8-bit opening.
    {
        auto keys = grotto::make_truncate_reduce_keys(8, 3);
        const std::uint64_t x0 = 0x05, x1 = 0x03;
        const std::uint64_t opened = (x0 + x1 + keys.rin) & 0xffu;
        const auto y0 = grotto::truncate_reduce(keys, 0, opened);
        const auto y1 = grotto::truncate_reduce(keys, 1, opened);
        const auto got = (y0.value + y1.value) & 0x1fu;
        const auto want = grotto::eval_carry_clear(keys.recipe, x0, x1);
        if (got != want)
        {
            std::cerr << "llama truncate_reduce\n";
            return 1;
        }
    }

    // Sign-extend: 8 → 16 bits.
    {
        auto keys = grotto::make_sign_extend_keys(8, 16);
        const std::uint64_t x0 = 0x80, x1 = 0;
        const std::uint64_t opened = (x0 + x1 + keys.rin) & 0xffu;
        const std::uint64_t msb_high = 1;  // 0x80 is negative
        const auto y0 = grotto::sign_extend(keys, 0, opened, msb_high);
        const auto y1 = grotto::sign_extend(keys, 1, opened, msb_high);
        const auto got = (y0.value + y1.value) & 0xffffu;
        const auto want = grotto::carry_extend_clear(x0, x1, 8, 16);
        if (got != want)
        {
            std::cerr << "llama sign_extend\n";
            return 1;
        }
    }

    {
        if (int rc = dpf::app::run_measured("llama",
                dpf::protocol::range_count_plan(0), 8))
            return rc;
    }

    std::cout << above << " " << piece(20) << "\n";
    return 0;
}