tasm_lib/arithmetic/u64/
log_2_floor.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::prelude::*;
6use crate::traits::basic_snippet::Reviewer;
7use crate::traits::basic_snippet::SignOffFingerprint;
8
9/// The base 2 logarithm of the input, rounded down. See also: [u64::ilog2].
10///
11/// ### Behavior
12///
13/// ```text
14/// BEFORE: _ [x: u64]
15/// AFTER:  _ [y: u32]
16/// ```
17///
18/// ### Preconditions
19///
20/// - the input `x` is properly [`BFieldCodec`] encoded
21/// - the input `x` is not 0
22///
23/// ### Postconditions
24///
25/// - `y` is the [base-2 integer logarithm](u64::ilog2) of `x`
26/// - `y` is properly [`BFieldCodec`] encoded
27#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
28pub struct Log2Floor;
29
30impl BasicSnippet for Log2Floor {
31    fn parameters(&self) -> Vec<(DataType, String)> {
32        vec![(DataType::U64, "x".to_string())]
33    }
34
35    fn return_values(&self) -> Vec<(DataType, String)> {
36        vec![(DataType::U32, "log_2_floor(x)".to_string())]
37    }
38
39    fn entrypoint(&self) -> String {
40        "tasmlib_arithmetic_u64_log_2_floor".to_string()
41    }
42
43    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
44        let entrypoint = self.entrypoint();
45
46        let hi_neq_zero = format!("{entrypoint}_hi_neq_zero");
47        let hi_eq_zero = format!("{entrypoint}_hi_eq_zero");
48        triton_asm!(
49            // BEFORE: _ x_hi x_lo
50            // AFTER:  _ log2_floor(x)
51            {entrypoint}:
52                push 1
53                dup 2
54                // _ x_hi x_lo 1 x_hi
55
56                skiz call {hi_neq_zero}
57                skiz call {hi_eq_zero}
58                // _ log2_floor(x)
59
60                return
61
62            {hi_neq_zero}:
63                // x_hi != 0
64                // _ x_hi x_lo 1
65
66                pop 1
67                // _ x_hi x_lo
68
69                /* assert valid encoding */
70                pop_count
71                pop 1
72                // _ x_hi
73
74                log_2_floor
75                addi 32
76                // _ (log2_floor(x_hi) + 32)
77
78                push 0
79                // _ (log2_floor(x_hi) + 32) 0
80
81                return
82
83            {hi_eq_zero}:
84                // x_hi == 0
85                // _ 0 x_lo
86                pick 1
87                pop 1
88                log_2_floor
89                // _ log_2_floor(x_lo)
90
91                return
92        )
93    }
94
95    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
96        let mut sign_offs = HashMap::new();
97        sign_offs.insert(Reviewer("ferdinand"), 0xc89c4b19e24a3ba1.into());
98        sign_offs
99    }
100}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105    use crate::test_helpers::negative_test;
106    use crate::test_prelude::*;
107
108    impl Closure for Log2Floor {
109        type Args = u64;
110
111        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) -> Result<(), RustShadowError> {
112            let x = pop_encodable::<Self::Args>(stack)?;
113            let log = x.checked_ilog2().ok_or(RustShadowError::Other)?;
114            push_encodable(stack, &log);
115            Ok(())
116        }
117
118        fn pseudorandom_args(
119            &self,
120            seed: [u8; 32],
121            bench_case: Option<BenchmarkCase>,
122        ) -> Self::Args {
123            match bench_case {
124                Some(BenchmarkCase::CommonCase) => u64::from(u32::MAX),
125                Some(BenchmarkCase::WorstCase) => u64::MAX,
126                None => StdRng::from_seed(seed).random(),
127            }
128        }
129
130        fn corner_case_args(&self) -> Vec<Self::Args> {
131            (0..63)
132                .map(|pow| 1_u64 << pow)
133                .flat_map(|x| [x.checked_sub(1), Some(x), x.checked_add(1)])
134                .flatten()
135                .filter(|&x| x != 0)
136                .collect()
137        }
138    }
139
140    #[macro_rules_attr::apply(test)]
141    fn rust_shadow_test() {
142        ShadowedClosure::new(Log2Floor).test();
143    }
144
145    #[macro_rules_attr::apply(proptest)]
146    fn hi_is_u32_but_lo_is_not(
147        #[strategy(0_u32..)]
148        #[map(BFieldElement::from)]
149        x_hi: BFieldElement,
150        #[strategy(1_u64 << 32..)]
151        #[map(BFieldElement::new)]
152        x_lo: BFieldElement,
153    ) {
154        let mut init_stack = Log2Floor.init_stack_for_isolated_run();
155        init_stack.push(x_hi);
156        init_stack.push(x_lo);
157
158        let expected_err = InstructionError::OpStackError(OpStackError::FailedU32Conversion(x_lo));
159        negative_test(
160            &ShadowedClosure::new(Log2Floor),
161            InitVmState::with_stack(init_stack),
162            &[expected_err],
163        );
164    }
165
166    #[macro_rules_attr::apply(proptest)]
167    fn hi_is_not_u32_but_lo_is(
168        #[strategy(1_u64 << 32..)]
169        #[map(BFieldElement::new)]
170        x_hi: BFieldElement,
171        #[strategy(0_u32..)]
172        #[map(BFieldElement::from)]
173        x_lo: BFieldElement,
174    ) {
175        let mut init_stack = Log2Floor.init_stack_for_isolated_run();
176        init_stack.push(x_hi);
177        init_stack.push(x_lo);
178
179        let expected_err = InstructionError::OpStackError(OpStackError::FailedU32Conversion(x_hi));
180        negative_test(
181            &ShadowedClosure::new(Log2Floor),
182            InitVmState::with_stack(init_stack),
183            &[expected_err],
184        );
185    }
186
187    #[macro_rules_attr::apply(test)]
188    fn crash_on_zero() {
189        negative_test(
190            &ShadowedClosure::new(Log2Floor),
191            InitVmState::with_stack(Log2Floor.set_up_test_stack(0)),
192            &[InstructionError::LogarithmOfZero],
193        );
194    }
195
196    #[macro_rules_attr::apply(test)]
197    fn unit_test() {
198        fn assert_terminal_stack_is_as_expected(x: u64, expected: u32) {
199            let mut expected_stack = Log2Floor.init_stack_for_isolated_run();
200            push_encodable(&mut expected_stack, &expected);
201
202            test_rust_equivalence_given_complete_state(
203                &ShadowedClosure::new(Log2Floor),
204                &Log2Floor.set_up_test_stack(x),
205                &[],
206                &NonDeterminism::default(),
207                &None,
208                Some(&expected_stack),
209            );
210        }
211
212        // many of the following are already covered by the edge cases declared in
213        // “corner_case_initial_states” but repeated here as a sanity check
214        assert_terminal_stack_is_as_expected(1, 0);
215        assert_terminal_stack_is_as_expected(2, 1);
216        assert_terminal_stack_is_as_expected(3, 1);
217        assert_terminal_stack_is_as_expected(4, 2);
218        assert_terminal_stack_is_as_expected(5, 2);
219        assert_terminal_stack_is_as_expected(6, 2);
220        assert_terminal_stack_is_as_expected(7, 2);
221        assert_terminal_stack_is_as_expected(8, 3);
222        assert_terminal_stack_is_as_expected((1 << 32) - 20_000, 31);
223        assert_terminal_stack_is_as_expected((1 << 32) + 800, 32);
224    }
225}
226
227#[cfg(test)]
228mod benches {
229    use super::*;
230    use crate::test_prelude::*;
231
232    #[macro_rules_attr::apply(test)]
233    fn benchmark() {
234        ShadowedClosure::new(Log2Floor).bench();
235    }
236}
tasm_lib/arithmetic/u64/log_2_floor.rs

tasm_lib/arithmetic/u64/
log_2_floor.rs
