bench_poly_eval/
lib.rs

1//! Polynomial evaluation via Horner's method — mirrors
2//! `p3_uni_stark::verify`'s AIR constraint polynomial evaluation at
3//! FRI challenge points.
4//!
5//! For each of `NUM_POINTS` challenge points `x`, evaluate a degree-
6//! `(DEGREE - 1)` polynomial
7//! `p(x) = c_0 + c_1·x + c_2·x² + … + c_{DEGREE-1}·x^(DEGREE-1)` via
8//! Horner's method. Memory access is a sequential streaming read of
9//! `coeffs[]` (4096 × u64 = 32 KiB, fits in L1). Compute: `DEGREE-1`
10//! chained `mul + add` per point — totally dependent (each step
11//! needs the previous result).
12//!
13//! Complements:
14//!   - `goldilocks-mul`: chained mul, no add, no memory
15//!   - `mini-verifier`: closed-form constraint eval (no memory access)
16//!   - `fri-fold-tree`: scattered memory access
17
18#![cfg_attr(target_os = "none", no_std)]
19
20use subsoil as _;
21
22#[cfg(target_os = "none")]
23extern crate alloc;
24
25#[cfg(target_os = "none")]
26mod bump_alloc {
27    use core::alloc::{GlobalAlloc, Layout};
28    use core::cell::UnsafeCell;
29
30    const HEAP_SIZE: usize = 64 * 1024;
31
32    pub struct BumpAlloc {
33        heap: UnsafeCell<[u8; HEAP_SIZE]>,
34        pos: UnsafeCell<usize>,
35    }
36
37    unsafe impl Sync for BumpAlloc {}
38
39    unsafe impl GlobalAlloc for BumpAlloc {
40        unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
41            let pos = unsafe { &mut *self.pos.get() };
42            let aligned = (*pos + layout.align() - 1) & !(layout.align() - 1);
43            let next = aligned + layout.size();
44            if next > HEAP_SIZE {
45                return core::ptr::null_mut();
46            }
47            *pos = next;
48            unsafe { (*self.heap.get()).as_mut_ptr().add(aligned) }
49        }
50        unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {}
51    }
52
53    #[global_allocator]
54    static ALLOC: BumpAlloc = BumpAlloc {
55        heap: UnsafeCell::new([0; HEAP_SIZE]),
56        pos: UnsafeCell::new(0),
57    };
58}
59
60#[cfg(target_os = "none")]
61use alloc::vec::Vec;
62
63use gp::{add, canonical, mul, ZERO};
64
65const DEGREE: usize = 4096;
66const NUM_POINTS: usize = 64;
67const SEED_COEFFS: u64 = 0x123456789abcdef0;
68const SEED_POINTS: u64 = 0xfedcba9876543210;
69const MULTIPLIER: u64 = 0x9E3779B97F4A7C15;
70
71pub fn poly_eval_bench() -> u32 {
72    let mut coeffs: Vec<u64> = Vec::with_capacity(DEGREE);
73    let mut x = SEED_COEFFS;
74    let mut i = 0;
75    while i < DEGREE {
76        x = mul(x, MULTIPLIER);
77        coeffs.push(x);
78        i += 1;
79    }
80
81    let mut points: [u64; NUM_POINTS] = [0; NUM_POINTS];
82    let mut y = SEED_POINTS;
83    let mut j = 0;
84    while j < NUM_POINTS {
85        y = mul(y, MULTIPLIER);
86        points[j] = y;
87        j += 1;
88    }
89
90    let mut accum = ZERO;
91    let mut k = 0;
92    while k < NUM_POINTS {
93        let z = points[k];
94        let mut result = coeffs[DEGREE - 1];
95        let mut idx = DEGREE - 1;
96        while idx > 0 {
97            idx -= 1;
98            result = add(mul(result, z), coeffs[idx]);
99        }
100        accum = add(accum, result);
101        k += 1;
102    }
103
104    (canonical(accum) & 0xFFFF_FFFF) as u32
105}
bench_poly_eval/lib.rs

bench_poly_eval/
lib.rs
