fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In > Class Template Reference

2-party DPF scheme with packed sub-128-bit outputs, using the Half-Tree construction. More...

Classes
struct	Cw
	Correction word for a tree level or the final packed-output correction word. More...

Public Types
using	Input = In
	The caller-facing input-domain type.

Public Member Functions
	PackedHalfTreeDpf (Hash hash, int4 instance_seed)
	Configure the CCR hash and public instance seed S.
void	Gen (cuda::std::span< int4 > cws, cuda::std::span< const int4, 2 > s0s, In a, uint64_t beta, size_t stride=1)
	Generate split Cws for the packed point function.
int4	Eval (bool b, int4 s0, cuda::std::span< const int4 > cws, In x, size_t stride=1)
	Evaluate the packed output block containing x from split Cws.
void	EvalAll (bool b, int4 s0, cuda::std::span< const int4 > cws, int4 ys[], int par_depth=0, size_t stride=1)
	Evaluate all packed output blocks from split Cws on the host.
void	EvalRange (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< int4 > ys, int par_depth=0, size_t stride=1)
	Evaluate the closed input interval [first, last] from split Cws.
template<int frontier_depth = 16, int threads_per_block = 256> requires (kDepth < sizeof(size_t) * 8)
cudaError_t	EvalAllGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=1) const
	Launch full-domain CUDA evaluation from split device Cws.
template<int frontier_depth = 16, int threads_per_block = 256> requires (kDepth < sizeof(size_t) * 8)
cudaError_t	EvalAllGpuBatch (bool b, cuda::std::span< const int4 > s0s, cuda::std::span< const int4 > cws, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=0) const
	Launch full-domain CUDA evaluation for s0s.size() keys from split device Cws.

Static Public Member Functions
static uint64_t	Extract (int4 block, In x)
	Extracts the out_bits-bit output share for input x from a packed block.

Static Public Attributes
static constexpr int	kLanes = 128 / out_bits
	Number of consecutive inputs covered by one output block.
static constexpr int	kDepth
	Tree depth that is actually expanded.
static constexpr int	kCwCount = kDepth + 1
	Seed-component count Gen() writes at stride 1: kDepth levels plus the packed-output terminal.

Detailed Description

template<int in_bits, int out_bits, typename Hash, typename In = uint>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)
class fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >

2-party DPF scheme with packed sub-128-bit outputs, using the Half-Tree construction.

Template Parameters

in_bits	Input domain bit size.
out_bits	Output width in bits. A power of two within [1, 64]: 128 % out_bits == 0 then holds, so kLanes = 128 / out_bits lanes exactly fill a block. Widths above 64 give a single lane per block and no packing gain; use HalfTreeDpf with its 127-bit group instead.
Hash	Unary CCR hash backend. See CcrHashable.
In	Type for the input domain. From uint8_t to __uint128_t.

Gen() and scalar Eval() are callable from host and device when the backend supports the execution space and all accessed storage is accessible there. EvalAll() and EvalRange() are host operations. EvalAllGpu() and EvalAllGpuBatch() are host launch methods compiled with a CUDA compiler; they do not run on the device.

Constructor & Destructor Documentation

PackedHalfTreeDpf()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)

fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::PackedHalfTreeDpf ( Hash hash, int4 instance_seed )

inlineexplicit

Configure the CCR hash and public instance seed S.

Parameters

hash	Unary CCR hash backend used throughout generation and evaluation.
instance_seed	Uniformly sampled public seed S, fixed for this instance.

Member Function Documentation

Eval()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)

int4 fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::Eval ( bool b, int4 s0, cuda::std::span< const int4 > cws, In x, size_t stride = 1 )

inline

Evaluate the packed output block containing x from split Cws.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter. The result contains kLanes consecutive shares; Extract(result, x) reads x's share using the original input x.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's initial seed.
cws	Correction words, layer l at index l*stride and the packed-output correction word at index kDepth*stride.
x	Input in [0, 2^in_bits).
stride	Positive stride between Cw entries.

Returns

This party's block of kLanes output shares. Extract() reads x's lane.

Precondition

x is in [0, 2^in_bits).

stride > 0.

With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/kDepth and cws has at least kDepth*stride+1 elements.

All accessed storage is accessible from the calling execution space.

A stride or capacity violation aborts with a diagnostic in Debug builds on both the host and the device, and is undefined behavior in Release builds.

EvalAll()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)

void fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::EvalAll ( bool b, int4 s0, cuda::std::span< const int4 > cws, int4 ys[], int par_depth = 0, size_t stride = 1 )

inline

Evaluate all packed output blocks from split Cws on the host.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter. The output has exactly B = 2^kDepth blocks and matches the Cw form block for block.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's initial seed.
cws	Correction words, layer l at index l*stride and the packed-output correction word at index kDepth*stride.
ys	Pre-allocated output array of at least 2^kDepth blocks, in input order.
par_depth	Nonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive stride between Cw entries.

Precondition

stride > 0.

With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/kDepth and cws has at least kDepth*stride+1 elements.

The packed output element count and byte size fit size_t, and ys is allocated.

Exceptions

std::invalid_argument

if stride is zero or too large or cws is shorter than kDepth*stride+1.

Postcondition

Block j covers inputs j * kLanes through (j + 1) * kLanes - 1.

EvalAllGpu()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (kDepth < sizeof(size_t) * 8)

template<int frontier_depth, int threads_per_block>
requires (kDepth < sizeof(size_t) * 8)

cudaError_t fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::EvalAllGpu ( bool b, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< int4 > ys, cudaStream_t stream = 0, size_t stride = 1 ) const

inline

Launch full-domain CUDA evaluation from split device Cws.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter. Hash values, resource rules and tuning rules match EvalAllGpu().

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's seed, passed by value as a kernel argument.
cws	Device correction words, layer l at index l*stride.
ys	Device storage containing at least 2^kDepth packed output blocks.
stream	Stream on the device owning the referenced resources.
stride	Positive stride between Cw entries.

Returns

Immediate CUDA launch status. Invalid buffer dimensions, strides, null used buffers, or unaddressable byte sizes return cudaErrorInvalidValue. Execution remains asynchronous; the caller observes completion errors through stream.

Precondition

stride > 0 and cws holds at least kDepth*stride+1 elements.

All referenced storage remains alive until the stream work completes.

EvalAllGpuBatch()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (kDepth < sizeof(size_t) * 8)

template<int frontier_depth, int threads_per_block>
requires (kDepth < sizeof(size_t) * 8)

cudaError_t fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::EvalAllGpuBatch ( bool b, cuda::std::span< const int4 > s0s, cuda::std::span< const int4 > cws, cuda::std::span< int4 > ys, cudaStream_t stream = 0, size_t stride = 0 ) const

inline

Launch full-domain CUDA evaluation for s0s.size() keys from split device Cws.

The batch uses the level-major layout: key k layer l is read from cws[l*stride + k] and key k's packed-output correction word from cws[kDepth*stride + k]. The construction carries no control bits, so there is no packed-control parameter. stride selects the layout. 0 selects the dense level-major layout, in which the stride is the key count of this call. Any other value is a positive stride of at least s0s.size(). Resource and tuning rules match EvalAllGpu(). The batch shares one party index and hash configuration. Every key produces the complete packed domain.

Parameters

b	Party index shared by the batch.
s0s	Device storage containing one seed per key.
cws	Device level-major correction words.
ys	Device key-major rows of 2^kDepth packed output blocks per key.
stream	Stream on the device owning the referenced resources.
stride	0 for the dense level-major layout, where the stride is the key count of this call, or a positive element stride >= s0s.size().

Returns

Immediate CUDA status. Empty batches succeed without reading buffers. Invalid dimensions, null used buffers, strides, or unaddressable counts and bytes return cudaErrorInvalidValue. Oversized grids return cudaErrorInvalidConfiguration.

Precondition

stride is 0 or at least s0s.size().

cws holds at least kDepth*stride + s0s.size() elements, where a stride of 0 counts as s0s.size().

All referenced storage remains alive until the stream work completes.

EvalRange()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)

void fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::EvalRange ( bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< int4 > ys, int par_depth = 0, size_t stride = 1 )

inline

Evaluate the closed input interval [first, last] from split Cws.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter. The block layout matches the Cw form exactly.

Parameters

b	Party index, false for party 0 and true for party 1.
first	First input in the interval, inclusive.
last	Last input in the interval, inclusive.
s0	This party's initial seed.
cws	Correction words, layer l at index l*stride and the packed-output correction word at index kDepth*stride.
ys	Output storage for ceil((last - first + 1) / kLanes) blocks.
par_depth	Nonnegative OpenMP split depth. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive stride between Cw entries.

Precondition

first <= last and both endpoints belong to the input domain.

stride > 0.

With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/kDepth and cws has at least kDepth*stride+1 elements.

The output block count and byte size fit size_t, and used pointers are nonnull.

Exceptions

std::invalid_argument

if stride is zero or too large, cws is shorter than kDepth*stride+1, ys is null, first > last, an endpoint is outside the input domain, the interval does not fit size_t, or ys is too short.

Postcondition

Extract(ys[j / kLanes], j) is this party's share at first + j. Unused lanes in the last output block are zero. Extra capacity is untouched.

Extract()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)

uint64_t fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::Extract ( int4 block, In x )

inlinestatic

Extracts the out_bits-bit output share for input x from a packed block.

For full-domain output ys, use Extract(ys[x / kLanes], x). The lane is x % kLanes. Pass the original input x, not the block index. For in_bits = 8 and out_bits = 8, kLanes = 16 and x = 42 selects block 2 and lane 10: Extract(ys[2], 42). For EvalRange() output, x is the relative input index j = input - first. Use Extract(ys[j / kLanes], j).

Parameters

block	A packed output block, or the XOR of the two parties' blocks.
x	The original input for Eval()/EvalAll(), or relative input index for EvalRange().

Returns

The out_bits-bit lane value.

Gen()

template<int in_bits, int out_bits, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && CcrHashable<Hash> && out_bits >= 1 && out_bits <= 64 && (out_bits & (out_bits - 1)) == 0)

void fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::Gen ( cuda::std::span< int4 > cws, cuda::std::span< const int4, 2 > s0s, In a, uint64_t beta, size_t stride = 1 )

inline

Generate split Cws for the packed point function.

Layer l is stored at cws[l*stride] and the packed-output correction word at cws[kDepth*stride]. Tree levels hold the seed correction words and the terminal holds the packed-output correction word exactly as the final Cw entry does. The construction carries no control bits, so there is no packed-control parameter.

Parameters

cws	Output storage; its capacity includes kDepth*stride+1 elements.
s0s	Two initial seeds, retained by the caller.
a	The secret point. Its low log2(kLanes) bits select the packed lane.
beta	Output value, which must fit in out_bits bits.
stride	Positive element stride between layer entries. The default stride of 1 stores the components contiguously.

Precondition

a is in [0, 2^in_bits).

beta <= the out_bits-bit maximum.

stride > 0.

With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/kDepth and cws has at least kDepth*stride+1 elements.

Inputs and outputs do not overlap.

All accessed storage is accessible from the calling execution space.

A beta, stride, or capacity violation aborts with a diagnostic in Debug builds on both the host and the device, and is undefined behavior in Release builds.

Postcondition

cws and s0s[party] form the corresponding party's key.

Only the described prefix is written, and storage beyond it is untouched.

Member Data Documentation

kDepth

template<int in_bits, int out_bits, typename Hash, typename In = uint>

int fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::kDepth

staticconstexpr

Initial value:

= in_bits - [] {
    int r = 0;
    int v = kLanes;
    while (v > 1) {
      v >>= 1;
      ++r;
    }
    return r;
  }()

Tree depth that is actually expanded.

The remaining log2(kLanes) levels never run.

---

The documentation for this class was generated from the following file:

• include/fss/packed_half_tree_dpf.cuh