openvm_sdk/keygen/
perm.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
use std::cmp::Reverse;

use openvm_circuit::arch::{CONNECTOR_AIR_ID, PROGRAM_AIR_ID, PUBLIC_VALUES_AIR_ID};

use crate::verifier::common::types::SpecialAirIds;

// FIXME: is there a good crate to replace this?
pub struct AirIdPermutation {
    pub perm: Vec<usize>,
}

impl AirIdPermutation {
    pub fn compute(heights: &[usize]) -> AirIdPermutation {
        let mut height_with_air_id: Vec<_> = heights.iter().copied().enumerate().collect();
        height_with_air_id.sort_by_key(|(_, h)| Reverse(*h));
        AirIdPermutation {
            perm: height_with_air_id
                .into_iter()
                .map(|(a_id, _)| a_id)
                .collect(),
        }
    }
    pub fn get_special_air_ids(&self) -> SpecialAirIds {
        let perm_len = self.perm.len();
        let mut ret = SpecialAirIds {
            program_air_id: perm_len,
            connector_air_id: perm_len,
            public_values_air_id: perm_len,
        };
        for (i, &air_id) in self.perm.iter().enumerate() {
            if air_id == PROGRAM_AIR_ID {
                ret.program_air_id = i;
            } else if air_id == CONNECTOR_AIR_ID {
                ret.connector_air_id = i;
            } else if air_id == PUBLIC_VALUES_AIR_ID {
                ret.public_values_air_id = i;
            }
        }
        debug_assert_ne!(ret.program_air_id, perm_len, "Program AIR not found");
        debug_assert_ne!(ret.connector_air_id, perm_len, "Connector AIR not found");
        debug_assert_ne!(
            ret.public_values_air_id, perm_len,
            "Public Values AIR not found"
        );
        ret
    }
    /// arr[i] <- arr[perm[i]]
    pub(crate) fn permute<T>(&self, arr: &mut [T]) {
        debug_assert_eq!(arr.len(), self.perm.len());
        let mut perm = self.perm.clone();
        for i in 0..perm.len() {
            if perm[i] != i {
                let mut curr = i;
                loop {
                    let target = perm[curr];
                    perm[curr] = curr;
                    if perm[target] == target {
                        break;
                    }
                    arr.swap(curr, target);
                    curr = target;
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::keygen::perm::AirIdPermutation;

    #[test]
    fn test_air_id_permutation() {
        {
            let perm = AirIdPermutation {
                perm: vec![2, 0, 1, 3],
            };
            let mut arr = vec![0, 100, 200, 300];
            perm.permute(&mut arr);
            assert_eq!(arr, vec![200, 0, 100, 300]);
        }
        {
            let perm = AirIdPermutation {
                perm: vec![0, 1, 2, 3],
            };
            let mut arr = vec![0, 100, 200, 300];
            perm.permute(&mut arr);
            assert_eq!(arr, vec![0, 100, 200, 300]);
        }
    }
}