Skip to main content

polycore/
sample.rs

1//! Deterministic sampling and black boxes: every point is named by a key, so reruns and snapshots
2//! reproduce and callers that share a key share evaluations.
3
4use rand_xoshiro::rand_core::{Rng as _, SeedableRng};
5use rand_xoshiro::{SplitMix64, Xoshiro256PlusPlus};
6#[cfg(feature = "parallel")]
7use rayon::prelude::*;
8
9/// A hash of `key`, for deriving independent seeds from one.
10pub fn hash(key: &[u64]) -> u64 {
11    key.iter()
12        .fold(0, |h, &k| SplitMix64::seed_from_u64(h ^ k).next_u64())
13}
14
15/// The nonzero residue modulo `p` named by `key`.
16pub fn point(key: &[u64], p: u64) -> u64 {
17    1 + hash(key) % (p - 1)
18}
19
20/// `xoshiro256++`, seeded through `SplitMix64`.
21#[derive(Clone, Debug)]
22pub struct Rng(Xoshiro256PlusPlus);
23
24impl Rng {
25    pub fn new(seed: u64) -> Self {
26        Self(Xoshiro256PlusPlus::seed_from_u64(seed))
27    }
28
29    pub fn next_u64(&mut self) -> u64 {
30        self.0.next_u64()
31    }
32
33    /// Uniform in `[1, p)`, up to a bias of `p / 2^64`.
34    pub fn nonzero(&mut self, p: u64) -> u64 {
35        1 + self.next_u64() % (p - 1)
36    }
37}
38
39/// A polynomial or rational function known only through its values modulo `p`. `None` marks a
40/// point where evaluation broke down and which should be avoided.
41pub trait BlackBox {
42    fn eval(&self, x: &[u64], p: u64) -> Option<u64>;
43
44    /// Independent points at once, which an implementation may spread over threads.
45    fn eval_many(&self, xs: &[Vec<u64>], p: u64) -> Vec<Option<u64>> {
46        xs.iter().map(|x| self.eval(x, p)).collect()
47    }
48}
49
50/// Closures are black boxes, evaluated in parallel with the `parallel` feature.
51impl<F: Fn(&[u64], u64) -> Option<u64> + Sync> BlackBox for F {
52    fn eval(&self, x: &[u64], p: u64) -> Option<u64> {
53        self(x, p)
54    }
55
56    #[cfg(feature = "parallel")]
57    fn eval_many(&self, xs: &[Vec<u64>], p: u64) -> Vec<Option<u64>> {
58        xs.par_iter().map(|x| self(x, p)).collect()
59    }
60}