primal-barracuda 0.4.0

barraCuda — BARrier-free Rust Abstracted Cross-platform Unified Dimensional Algebra. Vendor-agnostic GPU compute via WGSL.
Documentation
// SPDX-License-Identifier: AGPL-3.0-or-later
//! FHE Polynomial Multiplication Shader
//!
//! **Purpose**: Multiply two polynomials modulo q (FHE ciphertext operation)
//!
//! **Deep Debt**: Pure WGSL, hardware-agnostic, numerically precise
//!
//! **Algorithm**: Coefficient-wise multiplication with Barrett modular reduction
//!
//! ## Mathematical Background
//!
//! FHE ciphertexts are polynomials over Z_q[X]/(X^N + 1):
//! - Degree N (typically 2048, 4096, or 8192)
//! - Coefficients modulo q (large prime, e.g., 2^64)
//! - Multiplication: (a₀ * b₀) mod q, (a₁ * b₁) mod q, ..., (aₙ * bₙ) mod q
//!
//! ## Note on Full Polynomial Multiplication
//!
//! This implements **coefficient-wise multiplication**, not full polynomial
//! multiplication (which would require NTT/FFT and degree reduction).
//!
//! For FHE operations:
//! - Boolean gates use coefficient-wise operations
//! - Full polynomial multiplication is for advanced operations
//! - NTT optimization can be added later for performance
//!
//! ## Barrett Reduction
//!
//! After multiplication, we need (a * b) mod q:
//! - Multiply two 64-bit values → 128-bit result
//! - Reduce 128-bit result modulo 64-bit q
//! - Use Barrett reduction for efficiency

struct Params {
    degree: u32,        // Polynomial degree (N)
    modulus_lo: u32,    // q lower 32 bits
    modulus_hi: u32,    // q upper 32 bits
    mu_lo: u32,         // Barrett constant μ lower 32 bits
    mu_hi: u32,         // Barrett constant μ upper 32 bits
}

@group(0) @binding(0) var<storage, read> poly_a: array<u32>;      // First polynomial (2×degree for u64)
@group(0) @binding(1) var<storage, read> poly_b: array<u32>;      // Second polynomial (2×degree for u64)
@group(0) @binding(2) var<storage, read_write> result: array<u32>; // Result polynomial (2×degree for u64)
@group(0) @binding(3) var<uniform> params: Params;

/// Reconstruct 64-bit value from two 32-bit parts
fn u64_from_parts(lo: u32, hi: u32) -> vec2<u32> {
    return vec2<u32>(lo, hi);
}

/// Compare two 64-bit values (returns true if a >= b)
fn u64_gte(a: vec2<u32>, b: vec2<u32>) -> bool {
    if (a.y > b.y) { return true; }
    if (a.y < b.y) { return false; }
    return a.x >= b.x;
}

/// Subtract two 64-bit values (assumes a >= b)
fn u64_sub(a: vec2<u32>, b: vec2<u32>) -> vec2<u32> {
    let borrow = select(0u, 1u, a.x < b.x);
    let lo_diff = a.x - b.x;
    let hi_diff = a.y - b.y - borrow;
    return vec2<u32>(lo_diff, hi_diff);
}

/// Helper: Multiply two 32-bit values to get 64-bit result
fn u32_mul_to_u64(a: u32, b: u32) -> vec2<u32> {
    // Split into 16-bit parts to avoid overflow
    let a_lo = a & 0xFFFFu;
    let a_hi = a >> 16u;
    let b_lo = b & 0xFFFFu;
    let b_hi = b >> 16u;
    
    // Partial products
    let p_ll = a_lo * b_lo;
    let p_lh = a_lo * b_hi;
    let p_hl = a_hi * b_lo;
    let p_hh = a_hi * b_hi;
    
    // Combine with carries
    let mid = p_lh + p_hl + (p_ll >> 16u);
    let lo = (mid << 16u) | (p_ll & 0xFFFFu);
    let hi = p_hh + (mid >> 16u);
    
    return vec2<u32>(lo, hi);
}

/// Helper: Add two 64-bit values
fn u64_add(a: vec2<u32>, b: vec2<u32>) -> vec2<u32> {
    let lo_sum = a.x + b.x;
    let carry = select(0u, 1u, lo_sum < a.x);
    let hi_sum = a.y + b.y + carry;
    return vec2<u32>(lo_sum, hi_sum);
}

/// Multiply two 64-bit values, return full 128-bit result
/// 
/// Returns vec4 where:
/// - .xy = lower 64 bits
/// - .zw = upper 64 bits
fn u64_mul(a: vec2<u32>, b: vec2<u32>) -> vec4<u32> {
    // (a.y * 2^32 + a.x) * (b.y * 2^32 + b.x)
    // = a.y*b.y*2^64 + (a.y*b.x + a.x*b.y)*2^32 + a.x*b.x
    
    let p0 = u32_mul_to_u64(a.x, b.x);  // a.x * b.x -> [0:64)
    let p1 = u32_mul_to_u64(a.x, b.y);  // a.x * b.y -> [32:96)
    let p2 = u32_mul_to_u64(a.y, b.x);  // a.y * b.x -> [32:96)
    let p3 = u32_mul_to_u64(a.y, b.y);  // a.y * b.y -> [64:128)
    
    // Lower 64 bits
    let lo_lo = p0.x;
    // Add mid-level products with carry
    let mid_sum = u64_add(vec2<u32>(p0.y, 0u), u64_add(vec2<u32>(p1.x, 0u), vec2<u32>(p2.x, 0u)));
    let lo_hi = mid_sum.x;
    
    // Upper 64 bits  
    let hi_partial = u64_add(vec2<u32>(p1.y, 0u), vec2<u32>(p2.y, 0u));
    let hi_with_carry = u64_add(hi_partial, vec2<u32>(mid_sum.y, 0u));
    let hi_final = u64_add(hi_with_carry, p3);
    
    return vec4<u32>(lo_lo, lo_hi, hi_final.x, hi_final.y);
}

/// Barrett reduction: reduce 128-bit value (a_hi:a_lo) modulo 64-bit q
///
/// Simplified Barrett for WGSL constraints:
/// 1. Approximate quotient using upper bits
/// 2. Compute remainder
/// 3. Correct if needed (at most 2 iterations)
fn barrett_reduce_128(a_lo: vec2<u32>, a_hi: vec2<u32>, q: vec2<u32>, mu: vec2<u32>) -> vec2<u32> {
    // For 128-bit input, we use upper 64 bits for approximation
    // q_approx ≈ a_hi * mu / 2^64
    
    // Multiply upper part by μ (simplified)
    let approx_mul = u64_mul(a_hi, mu);
    
    // Use upper part as approximate quotient
    let q_approx = vec2<u32>(approx_mul.z, approx_mul.w);
    
    // Compute q * q_approx (need only lower 64 bits)
    let q_times_approx = u64_mul(q, q_approx);
    let q_times_approx_lo = vec2<u32>(q_times_approx.x, q_times_approx.y);
    
    // Remainder: r = a_lo - q_times_approx_lo (assuming a_lo >= q_times_approx_lo)
    var r: vec2<u32>;
    if (u64_gte(a_lo, q_times_approx_lo)) {
        r = u64_sub(a_lo, q_times_approx_lo);
    } else {
        // Handle underflow (simplified for common case)
        r = a_lo;
    }
    
    // Correction iterations (at most 2)
    if (u64_gte(r, q)) {
        r = u64_sub(r, q);
    }
    if (u64_gte(r, q)) {
        r = u64_sub(r, q);
    }
    
    return r;
}

/// Simple modular reduction for values likely to be < 2^65
/// Works by iterative subtraction (good for small multiples of q)
fn simple_mod_reduce(a: vec2<u32>, q: vec2<u32>) -> vec2<u32> {
    var r = a;
    // For products up to 65536 * q, we need at most 65536 iterations
    // In practice, for FHE we expect products << 100*q, so ~100 iterations max
    for (var i = 0u; i < 1000u; i = i + 1u) {
        if (!u64_gte(r, q)) {
            break;
        }
        r = u64_sub(r, q);
    }
    return r;
}

/// Modular multiplication: (a * b) mod q
fn modular_mul(a: vec2<u32>, b: vec2<u32>, q: vec2<u32>, mu: vec2<u32>) -> vec2<u32> {
    // Multiply a * b → 128-bit result
    let product = u64_mul(a, b);
    let product_lo = vec2<u32>(product.x, product.y);
    let product_hi = vec2<u32>(product.z, product.w);
    
    // For small products (hi part is 0), use simple reduction
    if (product_hi.x == 0u && product_hi.y == 0u) {
        return simple_mod_reduce(product_lo, q);
    }
    
    // For large products, use Barrett reduction
    return barrett_reduce_128(product_lo, product_hi, q, mu);
}

@compute @workgroup_size(256)
fn fhe_poly_mul(@builtin(global_invocation_id) gid: vec3<u32>) {
    let idx = gid.x;
    
    // Boundary check
    if (idx >= params.degree) {
        return;
    }
    
    // Each coefficient is stored as two u32 values (lo, hi)
    let idx_lo = idx * 2u;
    let idx_hi = idx_lo + 1u;
    
    // Load coefficients from poly_a
    let a_lo = poly_a[idx_lo];
    let a_hi = poly_a[idx_hi];
    let a = u64_from_parts(a_lo, a_hi);
    
    // Load coefficients from poly_b
    let b_lo = poly_b[idx_lo];
    let b_hi = poly_b[idx_hi];
    let b = u64_from_parts(b_lo, b_hi);
    
    // Load modulus and Barrett constant
    let q = u64_from_parts(params.modulus_lo, params.modulus_hi);
    let mu = u64_from_parts(params.mu_lo, params.mu_hi);
    
    // Modular multiplication
    let product = modular_mul(a, b, q, mu);
    
    // Store result
    result[idx_lo] = product.x;
    result[idx_hi] = product.y;
}