libdpf/examples/applications/prac.cpp

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

#include "dpf.hpp"
#include "dpf/app_flow.hpp"
#include "dpf/app_plans.hpp"

// PRAC, the DPF steps that are not Duoram (Sasy, Vadapalli, and Goldberg,
// ePrint 2023/1897). Binary search builds the path with `make_dpf` /
// `extend`, one prefix at a time. Heapify uses a wide `vec` leaf.
//
//   c++ -std=c++17 -march=native -I include -I thirdparty \
//       examples/applications/prac.cpp

namespace
{

constexpr std::size_t n = 256;
constexpr std::size_t bitlen = 8;
using beta_t = std::uint64_t;
using input_t = std::uint8_t;
using wide3 = dpf::vec<beta_t, 3>;

template <typename Key0, typename Key1>
beta_t open_prefix(const Key0 & k0, const Key1 & k1, std::size_t level,
    input_t x)
{
    auto one = [&](auto lvl) {
        return dpf::reconstruct(
            *dpf::eval_point(dpf::out<lvl.value>, k0, x),
            *dpf::eval_point(dpf::out<lvl.value>, k1, x));
    };
    switch (level)
    {
    case 0: return one(std::integral_constant<std::size_t, 0>{});
    case 1: return one(std::integral_constant<std::size_t, 1>{});
    default: throw std::logic_error("prac: level");
    }
}

}  // namespace

int main()
{
    constexpr std::array<std::uint64_t, 8> memory{
        1, 3, 5, 7, 9, 11, 13, 15};
    constexpr std::uint64_t needle = 10;

    // Search path bits (MSB first): 1, then 0 → prefix 0b10......
    constexpr input_t path = 0x80;
    auto [p0, p1] = dpf::make_dpf(path, dpf::at<1>(beta_t{1}));
    auto [q0, q1] = dpf::extend(p0, p1, path, dpf::at<2>(beta_t{1}));

    constexpr std::uint64_t stride2[] = {memory[1], memory[5]};
    constexpr std::uint64_t stride4[] = {memory[0], memory[2], memory[4], memory[6]};

    const auto sel1 = open_prefix(q0, q1, 0, path);
    const auto sel2 = open_prefix(q0, q1, 1, path);
    const auto at_5 = sel1 * stride2[1];
    const auto at_4 = sel2 * stride4[2];
    if (memory[3] != 7 || at_5 != 11 || at_4 != 9
        || sel1 != 1 || sel2 != 1)
    {
        std::cerr << "prac search " << at_5 << " " << at_4 << "\n";
        return 1;
    }
    constexpr unsigned answer = 0b101;
    if (answer != 5 || memory[answer] < needle)
    {
        std::cerr << "prac index\n";
        return 1;
    }

    // Heapify: one wide leaf of three lanes at the answer index.
    wide3 payload{};
    payload.lanes = {1, 2, 3};
    auto [h0, h1] = dpf::make_dpf(static_cast<input_t>(answer), payload);
    const auto w0 = *dpf::eval_point(h0, static_cast<input_t>(answer));
    const auto w1 = *dpf::eval_point(h1, static_cast<input_t>(answer));
    const auto opened = dpf::reconstruct(w0, w1);
    if (opened.lanes[0] != 1 || opened.lanes[1] != 2 || opened.lanes[2] != 3)
    {
        std::cerr << "prac heapify\n";
        return 1;
    }

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

    std::cout << "prac ok\n";
    return 0;
}