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 Rotation Shader (Galois Automorphism)
//
// **Purpose**: Apply X → X^(2k+1) automorphism for slot rotation
//
// **Algorithm**: Coefficient permutation based on Galois automorphism
// ```
// For rotation by k:
//   galois = 2k + 1
//   new_index[i] = (i * galois) mod N
//   output[new_index[i]] = input[i] * sign
//   where sign = -1 if (i * galois) >= N, else 1
// ```
//
// **Performance**: O(n) parallel, 1 thread per coefficient

@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,
    rotation: u32, // Normalized [0, degree)
    modulus_lo: u32,
    modulus_hi: u32,
}

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

// ============================================================================
// U64 Helpers (minimal subset)
// ============================================================================

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

// Negate u64 mod modulus
fn u64_negate_mod(a: U64, m: U64) -> U64 {
    // result = (modulus - a) mod modulus
    let a_val = (u64(a.hi) << 32u) | u64(a.lo);
    let m_val = (u64(m.hi) << 32u) | u64(m.lo);
    
    if (a_val == 0u) {
        return U64(0u, 0u);
    }
    
    let result = m_val - a_val;
    return U64(u32(result & 0xFFFFFFFFu), u32(result >> 32u));
}

// ============================================================================
// Galois Automorphism
// ============================================================================

/// Compute Galois element: 2*rotation + 1
fn compute_galois_element(rotation: u32) -> u32 {
    return 2u * rotation + 1u;
}

/// Apply Galois automorphism: X^i → X^(i*galois) mod (X^N + 1)
fn apply_automorphism(coeff_idx: u32, galois: u32, degree: u32) -> u32 {
    // new_power = (coeff_idx * galois) mod (2 * degree)
    let new_power = (coeff_idx * galois) % (2u * degree);
    
    // If new_power >= degree, wrap around with negation
    // X^N = -1 in ring R = Z[X]/(X^N + 1)
    if (new_power >= degree) {
        return new_power - degree; // Index for negated coefficient
    } else {
        return new_power;
    }
}

/// Check if coefficient should be negated after automorphism
fn should_negate(coeff_idx: u32, galois: u32, degree: u32) -> bool {
    let new_power = (coeff_idx * galois) % (2u * degree);
    return new_power >= degree;
}

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

@compute @workgroup_size(256)
fn rotate_automorphism(
    @builtin(global_invocation_id) global_id: vec3<u32>,
) {
    let coeff_idx = global_id.x;
    
    // Bounds check
    if (coeff_idx >= params.degree) {
        return;
    }
    
    // Compute Galois element for this rotation
    let galois = compute_galois_element(params.rotation);
    
    // Load input coefficient
    let coeff = load_u64(coeff_idx);
    
    // Apply automorphism: determine new position
    let new_idx = apply_automorphism(coeff_idx, galois, params.degree);
    let negate = should_negate(coeff_idx, galois, params.degree);
    
    // Apply negation if needed (for X^N wraparound)
    let modulus = u64_from_parts(params.modulus_lo, params.modulus_hi);
    let output_coeff = select(coeff, u64_negate_mod(coeff, modulus), negate);
    
    // Store at new position
    // NOTE: This is a simplified version. Full implementation would need
    // atomic operations or separate buffers to avoid race conditions.
    // For sequential GPU execution with proper barriers, this is safe.
    store_u64(new_idx, output_coeff);
}