libdpf/include/dpf/prg_aes_ccr.hpp

/// @file dpf/prg_aes_ccr.hpp
/// @brief Circular correlation-robust (CCR) hash from fixed-key AES.
/// @details Implements the GKWY / Half-Tree CCR construction
///          `H(x) = π(σ(x)) ⊕ σ(x)` where `π` is the library's fixed-key AES
///          (same schedule as `prg::aes128`) and `σ` is the bitstring linear
///          orthomorphism `σ(xL∥xR) = (xL⊕xR)∥xL`.
///
///          `eval01(s)` returns the Half-Tree children `{H(s), H(s)⊕s}`. That
///          expand is **not** a drop-in for BGI `make_dpf`; use it only with
///          Half-Tree `tree_traits` (see `dpf/tree_traits.hpp`).
/// @note Following Guo, Yang, Wang, Zhang, Xie, Zhang, and Liu, ePrint 2022/1431: mid-level children are `{H(s), H(s)⊕s}`.
/// @see dpf/tree_traits.hpp
/// @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_PRG_AES_CCR_HPP__
#define LIBDPF_INCLUDE_DPF_PRG_AES_CCR_HPP__

#include <array>
#include <cstddef>
#include <cstdint>
#include <cstring>

#include "hedley/hedley.h"
#include "simde/simde/x86/avx2.h"
#include "portable-snippets/exact-int/exact-int.h"

#include "dpf/prg_aes.hpp"
#include "dpf/twiddle.hpp"
#include "dpf/utils.hpp"

namespace dpf
{
namespace prg
{

namespace ccr_detail
{

/// @brief Linear orthomorphism on 128-bit strings: `σ(xL∥xR) = (xL⊕xR)∥xL`.
/// @param x the `x`
/// @return Linear orthomorphism on 128-bit strings: `σ(xL∥xR) = (xL⊕xR)∥xL`
HEDLEY_NO_THROW
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
simde__m128i sigma(simde__m128i x) noexcept
{
    const std::uint64_t lo = static_cast<std::uint64_t>(
        simde_mm_cvtsi128_si64(x));
    const std::uint64_t hi = static_cast<std::uint64_t>(
        simde_mm_extract_epi64(x, 1));
    return simde_mm_set_epi64x(static_cast<long long>(lo),
        static_cast<long long>(lo ^ hi));
}

/// @brief Inverse: if `σ(x)=(a,b)=(xL⊕xR, xL)` then `xL=b`, `xR=a⊕b`.
/// @param y the `y`
/// @return Inverse: if `σ(x)=(a,b)=(xL⊕xR, xL)` then `xL=b`, `xR=a⊕b`
HEDLEY_NO_THROW
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
simde__m128i sigma_inv(simde__m128i y) noexcept
{
    const std::uint64_t a = static_cast<std::uint64_t>(
        simde_mm_cvtsi128_si64(y));
    const std::uint64_t b = static_cast<std::uint64_t>(
        simde_mm_extract_epi64(y, 1));
    return simde_mm_set_epi64x(static_cast<long long>(a ^ b),
        static_cast<long long>(b));
}

/// @brief `σ'(x) = σ(x) ⊕ x`.
/// @param x the `x`
/// @return `σ'(x) = σ(x) ⊕ x`
HEDLEY_NO_THROW
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
simde__m128i sigma_prime(simde__m128i x) noexcept
{
    return simde_mm_xor_si128(sigma(x), x);
}

}  // namespace ccr_detail

/// @brief CCR hash + Half-Tree expand over fixed-key AES-128.
/// @details Selecting this as an *interior* PRG opts into Half-Tree via `half_tree_tag`.
struct aes128_ccr final
{
    using block_type = simde__m128i;
    using half_tree_tag = void;
    using underlying_aes = aes128;

    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    static void require_block_aligned(const void * p) noexcept
    {
        underlying_aes::require_block_aligned(p);
    }

    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_CONST
    static block_type sigma(block_type x) noexcept
    {
        return ccr_detail::sigma(x);
    }

    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_CONST
    static block_type sigma_inv(block_type y) noexcept
    {
        return ccr_detail::sigma_inv(y);
    }

    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_CONST
    static block_type sigma_prime(block_type x) noexcept
    {
        return ccr_detail::sigma_prime(x);
    }

    /// @brief `H(x) = π(σ(x)) ⊕ σ(x)` with `π` the fixed-key AES permutation
    /// (implemented as the library MMO at position 0).
    /// @param x the `x`
    /// @return `H(x) = π(σ(x)) ⊕ σ(x)` with `π` the fixed-key AES permutation (implemented as the
    /// library MMO at position 0)
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    static block_type hash(block_type x) noexcept
    {
        return underlying_aes::eval(sigma(x), 0);
    }

    /// @brief Alias for `hash`.
    /// @param x the `x`
    /// @return Alias for `hash`
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    static block_type H(block_type x) noexcept
    {
        return hash(x);
    }

    /// @brief Position-tweaked CCR hash: `H(x; pos) = AES_MMO(σ(x), pos)`.
    /// @param seed the PRG seed
    /// @param pos the 0-based index
    /// @return Position-tweaked CCR hash: `H(x; pos) = AES_MMO(σ(x), pos)`
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    static block_type eval(block_type seed, psnip_uint32_t pos) noexcept
    {
        return underlying_aes::eval(sigma(seed), pos);
    }

    /// @brief Half-Tree children: left = `H(s)`, right = `H(s) ⊕ s`.
    /// @param seed the PRG seed
    /// @return Half-Tree children: left = `H(s)`, right = `H(s) ⊕ s`
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    static auto eval01(block_type seed) noexcept
    {
        const block_type h = hash(seed);
HEDLEY_PRAGMA(GCC diagnostic push)
HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
        return std::array<block_type, 2>{h, simde_mm_xor_si128(h, seed)};
HEDLEY_PRAGMA(GCC diagnostic pop)
    }

    /// @brief Last-level two-tweak stretch: `{H(s|0), H(s|1)}` (LSB forced).
    /// @param seed the PRG seed
    /// @return Last-level two-tweak stretch: `{H(s|0), H(s|1)}` (LSB forced)
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_PURE
    static auto eval01_twotweak(block_type seed) noexcept
    {
        const block_type base = dpf::unset_lo_bit(seed);
HEDLEY_PRAGMA(GCC diagnostic push)
HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
        return std::array<block_type, 2>{
            hash(base),
            hash(dpf::set_lo_bit(base))
        };
HEDLEY_PRAGMA(GCC diagnostic pop)
    }

    /// @brief `count` CCR blocks starting at lane `pos`.
    /// @details `output` is unused when `count` is 0. Each block is
    ///          `AES_MMO(σ(seed), pos + i)`.
    /// @param seed the PRG seed
    /// @param output the destination. Unused when `count` is 0
    /// @param count the number of blocks
    /// @param pos the first lane index
    /// @throws std::invalid_argument if `pos + count` wraps `uint32_t`
    HEDLEY_ALWAYS_INLINE
    static void eval(block_type seed, block_type * HEDLEY_RESTRICT output,
        psnip_uint32_t count, psnip_uint32_t pos = 0)
    {
        underlying_aes::eval(sigma(seed), output, count, pos);
    }

    /// @brief CCR hash of four seeds.
    /// @param inputs four seeds
    /// @param output four hashes, `H(inputs[i])`
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_NON_NULL(1, 2)
    static void hash_x4(const block_type * HEDLEY_RESTRICT inputs,
        block_type * HEDLEY_RESTRICT output) noexcept
    {
        require_block_aligned(inputs);
        require_block_aligned(output);
        alignas(block_type) block_type sx[4];
        DPF_UNROLL_LOOP
        for (std::size_t i = 0; i < 4; ++i)
            sx[i] = sigma(inputs[i]);
        underlying_aes::eval_x4(sx, output, 0);
    }

    /// @brief Half-Tree children of four seeds.
    /// @param seeds four seeds
    /// @param left `H(seeds[i])`
    /// @param right `H(seeds[i]) ⊕ seeds[i]`
    HEDLEY_NO_THROW
    HEDLEY_ALWAYS_INLINE
    HEDLEY_NON_NULL(1, 2, 3)
    static void eval01_x4(const block_type * HEDLEY_RESTRICT seeds,
        block_type * HEDLEY_RESTRICT left,
        block_type * HEDLEY_RESTRICT right) noexcept
    {
        require_block_aligned(seeds);
        require_block_aligned(left);
        require_block_aligned(right);
        hash_x4(seeds, left);
        DPF_UNROLL_LOOP
        for (std::size_t i = 0; i < 4; ++i)
            right[i] = simde_mm_xor_si128(left[i], seeds[i]);
    }

    template <typename T, std::size_t Party>
    HEDLEY_NO_THROW
    static auto expand(block_type seed, psnip_uint32_t pos = 0) noexcept;
};

}  // namespace prg
}  // namespace dpf

#endif  // LIBDPF_INCLUDE_DPF_PRG_AES_CCR_HPP__