rustev_core/ranking/
permute.rs

1//! `rustev.permute/1` (spec 039, 3.8.4), using spec 002's identity builder.
2use rustev_contract::canonical::{CanonicalError, canonical_bytes, tagged_digest};
3use serde::Serialize;
4
5#[derive(Debug, Clone, PartialEq, Eq)]
6pub enum PermuteError {
7    Canonical(CanonicalError),
8    DigestEncoding,
9    Overflow,
10}
11
12/// Distinguishes integer permutation indices from string comparison keys.
13#[derive(Debug, Clone, Copy, Serialize)]
14#[serde(untagged)]
15pub enum DrawKey<'a> {
16    Permutation(u64),
17    Comparison(&'a str),
18}
19
20/// An unbiased draw in 0..=i, also exposing rejected attempts for vectors.
21pub fn draw(
22    seed: &str,
23    step: &str,
24    instance: &[String],
25    j: DrawKey<'_>,
26    i: u64,
27) -> Result<(u64, u64), PermuteError> {
28    let range = u128::from(i) + 1;
29    let space = 1u128 << 64;
30    let limit = (space / range) * range;
31    let mut attempt = 0u64;
32    loop {
33        // Spec 039, 3.8.4: instance is the contract's array of strings
34        // (Vec<String>, empty at the step root); j is an integer for a
35        // permutation index and a string for a pairwise comparison key.
36        let bytes = canonical_bytes(&(seed, step, instance, j, i, attempt))
37            .map_err(PermuteError::Canonical)?;
38        let digest = tagged_digest("rustev.permute/1", &bytes);
39        let prefix = digest.get(7..23).ok_or(PermuteError::DigestEncoding)?;
40        // The first sixteen hex digits encode the first eight digest bytes
41        // in big-endian order, without a second hashing implementation.
42        let v = u64::from_str_radix(prefix, 16).map_err(|_| PermuteError::DigestEncoding)?;
43        if u128::from(v) < limit {
44            return Ok(((u128::from(v) % range) as u64, attempt));
45        }
46        attempt = attempt.checked_add(1).ok_or(PermuteError::Overflow)?;
47    }
48}
49
50/// Pool-position permutation; callers retain candidate ids in pool order.
51pub fn permutation(
52    size: usize,
53    seed: &str,
54    step: &str,
55    instance: &[String],
56    j: u64,
57) -> Result<Vec<usize>, PermuteError> {
58    let mut positions: Vec<_> = (0..size).collect();
59    for i in (1..size).rev() {
60        let index = u64::try_from(i).map_err(|_| PermuteError::Overflow)?;
61        let (r, _) = draw(seed, step, instance, DrawKey::Permutation(j), index)?;
62        let r = usize::try_from(r).map_err(|_| PermuteError::Overflow)?;
63        // draw guarantees r <= i, and i < size, so swap cannot panic.
64        positions.swap(i, r);
65    }
66    Ok(positions)
67}
68
69/// The pairwise presentation bit (i = 1, string comparison key).
70pub fn presentation_bit(
71    seed: &str,
72    step: &str,
73    instance: &[String],
74    comparison: &str,
75) -> Result<bool, PermuteError> {
76    draw(seed, step, instance, DrawKey::Comparison(comparison), 1).map(|(v, _)| v == 1)
77}
rustev_core/ranking/permute.rs

rustev_core/ranking/
permute.rs
