use spiral_rs::discrete_gaussian::DiscreteGaussian;
use std::sync::OnceLock;
pub const DEFAULT_SIGMA_CHI: f64 = 6.4;
const DEFAULT_MAX_VAL: i64 = 65;
pub fn default_cdf_table() -> &'static [u64] {
static TABLE: OnceLock<Vec<u64>> = OnceLock::new();
TABLE.get_or_init(|| {
include_str!("gaussian_cdf_6_4.txt")
.lines()
.map(|line| line.parse().expect("invalid frozen Gaussian CDF"))
.collect()
})
}
pub fn discrete_gaussian(sigma_chi: f64) -> DiscreteGaussian {
if sigma_chi.to_bits() != DEFAULT_SIGMA_CHI.to_bits() {
return DiscreteGaussian::init(sigma_chi * std::f64::consts::TAU.sqrt());
}
let cdf_table = default_cdf_table().to_vec();
let weights: Vec<f64> = default_counts().into_iter().map(|c| c as f64).collect();
DiscreteGaussian {
weighted_index: rand::distributions::WeightedIndex::new(weights)
.expect("frozen Gaussian CDF has positive mass"),
cdf_table,
max_val: DEFAULT_MAX_VAL,
}
}
fn default_counts() -> Vec<u128> {
let table = default_cdf_table();
let mut previous = 0u128;
let mut counts: Vec<u128> = table
.iter()
.map(|&threshold| {
let end = u128::from(threshold) + 1;
let count = end - previous;
previous = end;
count
})
.collect();
counts[DEFAULT_MAX_VAL as usize] += (1u128 << 64) - previous;
counts
}
#[cfg(test)]
mod tests {
use super::*;
use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha20Rng;
use sha2::{Digest, Sha256};
#[test]
fn frozen_table_identity_and_shape() {
let table = default_cdf_table();
assert_eq!(table.len(), 2 * DEFAULT_MAX_VAL as usize + 1);
assert!(table.windows(2).all(|w| w[0] <= w[1]));
let bytes: Vec<u8> = table.iter().flat_map(|x| x.to_le_bytes()).collect();
assert_eq!(
format!("{:x}", Sha256::digest(bytes)),
"bc68011d7224eb5dcb649a206c70697d4e6bce32af77966f4ebd60c0683cac2e"
);
}
#[test]
fn frozen_table_matches_backend_runtime_table() {
let runtime = DiscreteGaussian::init(DEFAULT_SIGMA_CHI * std::f64::consts::TAU.sqrt());
assert_eq!(runtime.max_val, DEFAULT_MAX_VAL);
assert_eq!(runtime.cdf_table, default_cdf_table());
}
#[test]
fn default_sampler_uses_frozen_table_and_matches_runtime_draws() {
let frozen = discrete_gaussian(DEFAULT_SIGMA_CHI);
assert_eq!(frozen.cdf_table, default_cdf_table());
assert_eq!(frozen.max_val, DEFAULT_MAX_VAL);
let runtime = DiscreteGaussian::init(DEFAULT_SIGMA_CHI * std::f64::consts::TAU.sqrt());
let q = 72_057_594_037_641_217;
let mut a = ChaCha20Rng::from_seed([0x47; 32]);
let mut b = ChaCha20Rng::from_seed([0x47; 32]);
for _ in 0..4096 {
assert_eq!(frozen.sample(q, &mut a), runtime.sample(q, &mut b));
}
}
#[test]
fn counts_cover_every_draw_and_are_symmetric() {
let counts = default_counts();
assert_eq!(counts.iter().sum::<u128>(), 1u128 << 64);
let zero = DEFAULT_MAX_VAL as usize;
assert!(counts[zero] > 0);
assert!(counts[zero] >= counts[zero + 1]);
for k in 1..=40 {
let diff = counts[zero - k].abs_diff(counts[zero + k]);
assert!(diff <= 1 << 13, "asymmetric at +/-{k}: {diff}");
}
}
#[test]
fn other_sigmas_use_runtime_table() {
let dg = discrete_gaussian(3.2);
let runtime = DiscreteGaussian::init(3.2 * std::f64::consts::TAU.sqrt());
assert_eq!(dg.cdf_table, runtime.cdf_table);
assert_eq!(dg.max_val, runtime.max_val);
}
}