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#[inline]
17pub fn n_of_m_eval(input: u64, n: u64, m: u64) -> u64 {
18    let window = input / m;
19    let pos = input % m;
20    // Hash this position within the window using fast register mix
21    let my_hash = crate::numeric::hash::splitmix64_u64(
22        window.wrapping_mul(0x517cc1b727220a95) ^ pos.wrapping_mul(0x9e3779b97f4a7c15),
23    );
24    // Count how many positions in the same window hash lower
25    let mut rank: u64 = 0;
26    for i in 0..m {
27        if i == pos {
28            continue;
29        }
30        let other_hash = crate::numeric::hash::splitmix64_u64(
31            window.wrapping_mul(0x517cc1b727220a95) ^ i.wrapping_mul(0x9e3779b97f4a7c15),
32        );
33        if other_hash < my_hash || (other_hash == my_hash && i < pos) {
34            rank += 1;
35        }
36    }
37    // Selected if rank < n (i.e., among the n smallest hashes)
38    if rank < n { 1 } else { 0 }
39}
polydat_core/numeric/n_of_m.rs

polydat_core/numeric/
n_of_m.rs
