ciphercore_base/applications/
minimum.rs

1//! Minimum of an integer array
2use crate::custom_ops::CustomOperation;
3use crate::data_types::{array_type, ScalarType, BIT};
4use crate::errors::Result;
5use crate::graphs::{Context, Graph, SliceElement};
6use crate::ops::min_max::Min;
7
8/// Creates a graph that finds the minimum of an array.
9///
10/// # Arguments
11///
12/// * `context` - context where a minimum graph should be created
13/// * `n` - number of elements of an array (i.e., 2<sup>n</sup>)
14/// * `st` - scalar type of array elements
15///
16/// # Returns
17///
18/// Graph that finds the minimum of an array
19pub fn create_minimum_graph(context: Context, n: u64, st: ScalarType) -> Result<Graph> {
20    // Get sign of the input scalar type that indicates whether signed comparisons should be computed
21    let signed_comparison = st.is_signed();
22
23    // Create a graph in a given context that will be used for finding the minimum
24    let g = context.create_graph()?;
25
26    // Create the type of the input array with `2^n` elements.
27    let input_type = array_type(vec![1 << n], st);
28
29    // Add an input node to the empty graph g created above.
30    // This input node requires the input array type generated previously.
31    let input_array = g.input(input_type)?;
32
33    // To find the minimum of an array, we resort to the custom operation Min (see ops.rs) that accepts only binary input.
34    // Thus, we need to convert the input in the binary form (if necessary).
35    let mut binary_array = if st != BIT {
36        input_array.a2b()?
37    } else {
38        input_array
39    };
40
41    // We find the minimum using the tournament method. This allows to reduce the graph size to O(n) from O(2<sup>n</sup>) nodes.
42    // Namely, we split the input array into pairs, find a minimum within each pair and create a new array from these minima.
43    // Then, we repeat this procedure for the new array.
44    // For example, let [2,7,0,3,11,5,0,4] be an input array.
45    // The 1st iteration yields [min(2,11), min(7,5), min(0,0), min(3,4)] = [2,5,0,3]
46    // The 2nd iteration results in [min(2,0), min(5,3)] = [0,3]
47    // The 3rd iteration returns [min(0,3)] = [0]
48    for level in (0..n).rev() {
49        // Extract the first half of the array using the [Graph::get_slice] operation.
50        // Our slicing conventions follow [the NumPy rules](https://numpy.org/doc/stable/user/basics.indexing.html).
51        let half1 =
52            binary_array.get_slice(vec![SliceElement::SubArray(None, Some(1 << level), None)])?;
53        // Extract the first half of the array using the [Graph::get_slice] operation.
54        let half2 =
55            binary_array.get_slice(vec![SliceElement::SubArray(Some(1 << level), None, None)])?;
56        // Compare the first half with the second half elementwise to find minimums.
57        // This is done via the custom operation Min (see ops.rs).
58        binary_array = g.custom_op(
59            CustomOperation::new(Min { signed_comparison }),
60            vec![half1, half2],
61        )?;
62    }
63    // Convert output from the binary form to the arithmetic form
64    let output = if st != BIT {
65        binary_array.b2a(st)?
66    } else {
67        binary_array
68    };
69    // Before computation every graph should be finalized, which means that it should have a designated output node.
70    // This can be done by calling `g.set_output_node(output)?` or as below.
71    output.set_as_output()?;
72    // Finalization checks that the output node of the graph g is set. After finalization the graph can't be changed.
73    g.finalize()?;
74
75    Ok(g)
76}
77
78#[cfg(test)]
79mod tests {
80    use crate::custom_ops::run_instantiation_pass;
81    use crate::data_types::{INT32, UINT32};
82    use crate::data_values::Value;
83    use crate::evaluators::random_evaluate;
84    use crate::graphs::create_context;
85    use std::ops::Not;
86
87    use super::*;
88
89    fn test_minimum_helper<T: TryInto<u128> + Not<Output = T> + TryInto<u8> + Copy>(
90        input_value: &[T],
91        n: u64,
92        st: ScalarType,
93    ) -> Value {
94        || -> Result<Value> {
95            let c = create_context()?;
96            let g = create_minimum_graph(c.clone(), n, st)?;
97            g.set_as_main()?;
98            c.finalize()?;
99            let mapped_c = run_instantiation_pass(c)?.get_context();
100            let mapped_g = mapped_c.get_main_graph()?;
101
102            let input_type = array_type(vec![n], st);
103            let val = Value::from_flattened_array(input_value, input_type.get_scalar_type())?;
104            random_evaluate(mapped_g, vec![val])
105        }()
106        .unwrap()
107    }
108
109    #[test]
110    fn test_minimum() {
111        || -> Result<()> {
112            assert!(
113                test_minimum_helper(
114                    &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],
115                    4,
116                    UINT32
117                ) == Value::from_flattened_array(&[1], UINT32)?
118            );
119            Ok(())
120        }()
121        .unwrap();
122        || -> Result<()> {
123            assert!(
124                test_minimum_helper(
125                    &[-1, 2, -3, 4, -5, 6, -7, 8, -9, 10, -11, 12, -13, 14, -15, 16],
126                    4,
127                    INT32
128                ) == Value::from_flattened_array(&[-15], INT32)?
129            );
130            Ok(())
131        }()
132        .unwrap();
133        || -> Result<()> {
134            assert!(
135                test_minimum_helper(&[0, 1, 1, 0, 1, 1, 0, 0], 3, BIT)
136                    == Value::from_flattened_array(&[0], BIT)?
137            );
138            Ok(())
139        }()
140        .unwrap();
141    }
142}
ciphercore_base/applications/minimum.rs

ciphercore_base/applications/
minimum.rs
