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 Key Switching Shader
//
// **Purpose**: Decompose ciphertext for key switching
//
// **Algorithm**: Base-B digit decomposition
// ```
// For coefficient c and base B:
//   d₀ = c mod B
//   d₁ = (c / B) mod B
//   d₂ = (c / B²) mod B
//   ...
//   dₗ = (c / B^L) mod B
// ```
//
// **Performance**: O(L·n) where L is decomposition levels

@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,
    decomp_base: u32,
    decomp_levels: u32,
    modulus_lo: u32,
    modulus_hi: u32,
    _padding: vec3<u32>,
}

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

// ============================================================================
// U64 Helpers
// ============================================================================

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);
}

// Divide u64 by u32
fn u64_div_u32(a: U64, b: u32) -> U64 {
    let a_val = (u64(a.hi) << 32u) | u64(a.lo);
    let quotient = a_val / u64(b);
    return U64(u32(quotient & 0xFFFFFFFFu), u32(quotient >> 32u));
}

// Modulo u64 by u32
fn u64_mod_u32(a: U64, b: u32) -> u32 {
    let a_val = (u64(a.hi) << 32u) | u64(a.lo);
    return u32(a_val % u64(b));
}

// ============================================================================
// Base-B Decomposition
// ============================================================================

/// Decompose coefficient into base-B digits
///
/// Returns the k-th digit: (coeff / B^k) mod B
fn decompose_digit(coeff: U64, base: u32, level: u32) -> u32 {
    var current = coeff;
    
    // Divide by B^level
    for (var i = 0u; i < level; i = i + 1u) {
        current = u64_div_u32(current, base);
    }
    
    // Take modulo B
    return u64_mod_u32(current, base);
}

// ============================================================================
// Main Compute Kernels
// ============================================================================

/// Decompose ciphertext component into base-B representation
@compute @workgroup_size(256)
fn decompose_base_b(
    @builtin(global_invocation_id) global_id: vec3<u32>,
) {
    let coeff_idx = global_id.x;
    
    if (coeff_idx >= params.degree) {
        return;
    }
    
    // Load coefficient to decompose
    let coeff = load_u64(coeff_idx);
    
    // For simplified version, just copy input to output
    // Full implementation would store L digits per coefficient
    // in a (degree * L) output buffer
    
    // Decompose into base-B digits (demonstration)
    // In production: store all digits for multiplication with switching keys
    let digit_0 = decompose_digit(coeff, params.decomp_base, 0u);
    
    // For now, store first digit (full version stores all L digits)
    // This demonstrates the decomposition algorithm
    store_u64(coeff_idx, U64(digit_0, 0u));
}

/// Accumulate switched ciphertext components
///
/// Phase 3 requirement: Full key switching accumulation needs:
///   1. Switching key storage buffers (L × degree × 2 polynomials)
///   2. NTT-domain multiplication (via fhe_ntt.wgsl)
///   3. Multi-level accumulation across all L decomposition digits
///
/// Current: Identity pass-through (decompose kernel outputs digit[0]).
/// The decomposition + pass-through structure is correct and tested.
/// Full accumulation will be wired when the FHE key infrastructure
/// (key generation, serialization, NTT-domain key storage) is implemented.
@compute @workgroup_size(256)
fn accumulate_switched(
    @builtin(global_invocation_id) global_id: vec3<u32>,
) {
    let coeff_idx = global_id.x;
    
    if (coeff_idx >= params.degree) {
        return;
    }
    
    // Load decomposed digit
    let digit = load_u64(coeff_idx);
    
    // Identity pass-through: preserves the decomposed coefficient.
    // When switching keys are available, this becomes:
    //   var acc = u64_from_u32(0u);
    //   for level 0..L:
    //     acc = u64_add(acc, u64_mul_mod(digit[level], switch_key[level][coeff_idx], m, mu));
    //   store_u64(coeff_idx, acc);
    store_u64(coeff_idx, digit);
}