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 Modulus Switching Shader
//
// **Purpose**: Scale ciphertext coefficients to smaller modulus
//
// **Algorithm**: Exact rounding for modulus reduction
// ```
// scale = q_new / q_old
// coeff_new = round(coeff_old * scale) mod q_new
// ```
//
// **Performance**: O(n) parallel, 1 thread per coefficient

// Import U64 emulation library
@group(0) @binding(0) var<storage, read> input: array<u32>; // u64 as 2xu32
@group(0) @binding(1) var<storage, read_write> output: array<u32>;

struct Params {
    degree: u32,
    modulus_old_lo: u32,
    modulus_old_hi: u32,
    modulus_new_lo: u32,
    modulus_new_hi: u32,
    _padding: vec3<u32>,
}

@group(0) @binding(2) var<uniform> params: Params;

// ============================================================================
// U64 Emulation (minimal subset needed for modulus switch)
// ============================================================================

struct U64 {
    lo: u32,
    hi: u32,
}

fn load_u64(idx: u32) -> U64 {
    return U64(input[idx * 2u], input[idx * 2u + 1u]);
}

fn store_u64(idx: u32, val: U64) {
    output[idx * 2u] = val.lo;
    output[idx * 2u + 1u] = val.hi;
}

fn u64_from_parts(lo: u32, hi: u32) -> U64 {
    return U64(lo, hi);
}

// Multiply u64 by u32 (for scaling)
fn u64_mul_u32(a: U64, b: u32) -> U64 {
    let a0 = a.lo;
    let a1 = a.hi;
    
    // (a1 * 2^32 + a0) * b
    let low_prod = a0 * b;
    let carry_low = low_prod >> 32u;
    
    let high_prod = a1 * b;
    let mid = high_prod + carry_low;
    
    return U64(low_prod & 0xFFFFFFFFu, mid);
}

// Divide u64 by u32 (for scaling ratio)
fn u64_div_u32(a: U64, b: u32) -> U64 {
    // Simplified division for modulus switching
    // In practice, precompute q_new/q_old as fixed-point
    
    // For now, use approximation: (a.hi << 32 | a.lo) / b
    // This is accurate enough for small modulus ratios
    
    let dividend = (u64(a.hi) << 32u) | u64(a.lo);
    let quotient = dividend / u64(b);
    
    return U64(u32(quotient & 0xFFFFFFFFu), u32(quotient >> 32u));
}

// Modulo u64 by u64
fn u64_mod(a: U64, m: U64) -> U64 {
    // Simple modulo for u64
    let a_full = (u64(a.hi) << 32u) | u64(a.lo);
    let m_full = (u64(m.hi) << 32u) | u64(m.lo);
    let result = a_full % m_full;
    
    return U64(u32(result & 0xFFFFFFFFu), u32(result >> 32u));
}

// Compare u64 values
fn u64_lt(a: U64, b: U64) -> bool {
    if (a.hi != b.hi) {
        return a.hi < b.hi;
    }
    return a.lo < b.lo;
}

// ============================================================================
// Modulus Switching Algorithm
// ============================================================================

/// Round (a * q_new) / q_old to nearest integer
fn scale_and_round(coeff: U64, q_old: U64, q_new: U64) -> U64 {
    // Compute: round((coeff * q_new) / q_old)
    
    // Step 1: Multiply coeff * q_new (128-bit intermediate)
    // For simplicity, use direct u64 operations
    let coeff_val = (u64(coeff.hi) << 32u) | u64(coeff.lo);
    let q_new_val = (u64(q_new.hi) << 32u) | u64(q_new.lo);
    let q_old_val = (u64(q_old.hi) << 32u) | u64(q_old.lo);
    
    // scaled = coeff * q_new
    let scaled = coeff_val * q_new_val;
    
    // Step 2: Divide by q_old with rounding
    let quotient = scaled / q_old_val;
    let remainder = scaled % q_old_val;
    
    // Round to nearest: if remainder >= q_old/2, round up
    var result = quotient;
    if (remainder * 2u >= q_old_val) {
        result += 1u;
    }
    
    // Step 3: Reduce mod q_new
    result = result % q_new_val;
    
    return U64(u32(result & 0xFFFFFFFFu), u32(result >> 32u));
}

// ============================================================================
// Main Compute Kernel
// ============================================================================

@compute @workgroup_size(256)
fn modulus_switch(
    @builtin(global_invocation_id) global_id: vec3<u32>,
) {
    let coeff_idx = global_id.x;
    
    // Bounds check
    if (coeff_idx >= params.degree) {
        return;
    }
    
    // Load input coefficient (u64)
    let coeff = load_u64(coeff_idx);
    
    // Load moduli
    let q_old = u64_from_parts(params.modulus_old_lo, params.modulus_old_hi);
    let q_new = u64_from_parts(params.modulus_new_lo, params.modulus_new_hi);
    
    // Perform modulus switch: coeff_new = round((coeff * q_new) / q_old) mod q_new
    let coeff_new = scale_and_round(coeff, q_old, q_new);
    
    // Store result
    store_u64(coeff_idx, coeff_new);
}