polydat_core/numeric/
n_of_m.rs

1// Copyright 2024-2026 Jonathan Shook
2// SPDX-License-Identifier: Apache-2.0
3
4//! The n-of-m selection: within each window of `m` inputs, the `n`
5//! whose position hashes lowest are selected; the body of `n_of` and
6//! of its native lowering.
7
8/// Core n-of-m evaluation: hash the input's position within its window
9/// and check whether its rank falls within the selected n.
10///
11/// Algorithm: within each window of m consecutive inputs, hash each
12/// position (0..m) and sort by hash. The n positions with the smallest
13/// hashes are selected. To avoid sorting at runtime, we count how many
14/// of the m positions hash lower than the current one — if fewer than
15/// n do, this position is selected.
16///
17/// Preconditions: `1 <= m <= 65536` and `n <= m`. `n_of` states both
18/// to the factory — `m` through a range constraint and the relation
19/// through a node validator — so a program that names bad values is
20/// refused before this runs, on every engine. They are not re-checked
21/// here, because this is the inner loop of the native lowering as well
22/// as of the body. The cost is `m` hashes a call, which is why `m` is
23/// bounded.
24#[inline]
25pub fn n_of_m_eval(input: u64, n: u64, m: u64) -> u64 {
26    let window = input / m;
27    let pos = input % m;
28    // Hash this position within the window using fast register mix
29    let my_hash = crate::numeric::hash::splitmix64_u64(
30        window.wrapping_mul(0x517cc1b727220a95) ^ pos.wrapping_mul(0x9e3779b97f4a7c15),
31    );
32    // Count how many positions in the same window hash lower
33    let mut rank: u64 = 0;
34    for i in 0..m {
35        if i == pos {
36            continue;
37        }
38        let other_hash = crate::numeric::hash::splitmix64_u64(
39            window.wrapping_mul(0x517cc1b727220a95) ^ i.wrapping_mul(0x9e3779b97f4a7c15),
40        );
41        if other_hash < my_hash || (other_hash == my_hash && i < pos) {
42            rank += 1;
43        }
44    }
45    // Selected if rank < n (i.e., among the n smallest hashes)
46    if rank < n { 1 } else { 0 }
47}
polydat_core/numeric/n_of_m.rs

polydat_core/numeric/
n_of_m.rs
