Skip to main content

ctutils/
primitives.rs

1//! Constant-time integer primitives for cryptographic arithmetic.
2//!
3//! Core integer methods can lower to branches or table lookups on targets without the corresponding
4//! instructions. These helpers provide alternatives if `value` is zero-bit counting  and carry propagation.
5//!
6//! Like [`Choice`], they use optimization barriers where needed. Their generated code should still
7//! be checked for the target and compiler in use.
8//!
9//! Native zero counts are used when supported and advertised by the target configuration.
10
11use crate::Choice;
12use core::hint::black_box;
13
14/// Bitwise less-than-or equal: returns `1` if `x <= y`, and otherwise returns `0`.
15///
16/// See "Hacker's Delight" 2nd edition, section 2-12 (Comparison predicates)
17macro_rules! bitle {
18    ($x:expr, $y:expr, $bits:expr) => {
19        (((!$x) | $y) & (($x ^ $y) | !($y.wrapping_sub($x)))) >> ($bits - 1)
20    };
21}
22
23/// Outgoing borrow bit for a wrapping `x - y - borrow_in` result.
24///
25/// See "Hacker's Delight", 2nd edition, section 2-13 (Overflow detection)
26macro_rules! bitborrow {
27    ($x:expr, $y:expr, $result:expr, $bits:expr) => {
28        (((!$x) & $y) | (((!$x) | $y) & $result)) >> ($bits - 1)
29    };
30}
31
32/// Bitwise less-than: returns `1` if `x < y`, and otherwise returns `0`.
33///
34/// See "Hacker's Delight" 2nd edition, section 2-12 (Comparison predicates)
35macro_rules! bitlt {
36    ($x:expr, $y:expr, $bits:expr) => {
37        $crate::primitives::bitborrow!($x, $y, ($x).wrapping_sub($y), $bits)
38    };
39}
40
41/// Bitwise non-zero: returns `1` if `x != 0`, and otherwise returns `0`.
42macro_rules! bitnz {
43    ($value:expr, $bits:expr) => {
44        ($value | $value.wrapping_neg()) >> ($bits - 1)
45    };
46}
47
48pub(crate) use {bitborrow, bitle, bitlt};
49
50// Shared by every nonzero constructor, including the widths which do not use
51// comparison_primitives. A result barrier alone does not prevent specialization
52// of the arithmetic which computes the predicate.
53macro_rules! nonzero_primitive {
54    ($ty:ty, $nz:ident, $from_lsb:ident) => {
55        #[inline(always)]
56        pub(crate) const fn $nz(value: $ty) -> Choice {
57            // Hide caller range information before computing the predicate.
58            // For example, a shifted value or signed mask can otherwise turn
59            // the nonzero test into a secret-dependent comparison branch.
60            #[cfg(any(
61                target_arch = "riscv32",
62                all(target_arch = "arm", not(target_has_atomic = "ptr"))
63            ))]
64            let value = black_box(value);
65            let bit = bitnz!(value, <$ty>::BITS);
66            #[cfg(all(target_arch = "arm", not(target_has_atomic = "ptr")))]
67            let bit = black_box(bit);
68            Choice::$from_lsb(bit)
69        }
70    };
71}
72
73nonzero_primitive!(u8, nz_u8, from_u8_lsb);
74nonzero_primitive!(u16, nz_u16, from_u16_lsb);
75nonzero_primitive!(u128, nz_u128, from_u128_lsb);
76
77// Keep the comparison bit opaque before narrowing it to Choice's byte representation.
78// ARM targets without pointer-width atomics cover Thumb-1 on Rust 1.87, which does not
79// advertise `thumb2` as a target feature. The other targets retain the original lowering.
80macro_rules! comparison_primitives {
81    ($ty:ty, $le:ident, $lt:ident, $nz:ident, $from_lsb:ident) => {
82        #[inline(always)]
83        pub(crate) const fn $le(lhs: $ty, rhs: $ty) -> Choice {
84            let bit = bitle!(lhs, rhs, <$ty>::BITS);
85            #[cfg(all(target_arch = "arm", not(target_has_atomic = "ptr")))]
86            let bit = black_box(bit);
87            Choice::$from_lsb(bit)
88        }
89
90        #[cfg_attr(
91            all(target_arch = "arm", not(target_has_atomic = "ptr")),
92            inline(never)
93        )]
94        #[cfg_attr(
95            not(all(target_arch = "arm", not(target_has_atomic = "ptr"))),
96            inline(always)
97        )]
98        pub(crate) const fn $lt(lhs: $ty, rhs: $ty) -> Choice {
99            let bit = $crate::primitives::bitlt!(lhs, rhs, <$ty>::BITS);
100            #[cfg(all(target_arch = "arm", not(target_has_atomic = "ptr")))]
101            let bit = black_box(bit);
102            Choice::$from_lsb(bit)
103        }
104
105        nonzero_primitive!($ty, $nz, $from_lsb);
106    };
107}
108
109comparison_primitives!(u32, le_u32, lt_u32, nz_u32, from_u32_lsb);
110comparison_primitives!(u64, le_u64, lt_u64, nz_u64, from_u64_lsb);
111
112macro_rules! borrowing_sub_primitives {
113    ($ty:ty, $sub:ident, $sub_mask:ident, $sub_inner:ident, $from_lsb:ident) => {
114        /// Subtract `rhs` and an incoming borrow from `lhs`.
115        ///
116        /// Returns the wrapping difference and [`Choice::TRUE`] if the subtraction underflows.
117        /// The incoming `borrow` subtracts one when true and zero when false.
118        #[inline]
119        #[must_use]
120        pub const fn $sub(lhs: $ty, rhs: $ty, borrow: Choice) -> ($ty, Choice) {
121            let (difference, borrow) = $sub_inner(lhs, rhs, borrow.to_u8() as $ty);
122            (difference, Choice::$from_lsb(borrow))
123        }
124
125        /// Subtract `rhs` and an incoming borrow from `lhs`, using word-sized borrow masks.
126        ///
127        /// The incoming borrow is the most significant bit of `borrow`; all other bits are ignored.
128        /// Returns the wrapping difference and an all-ones mask if the subtraction underflows,
129        /// or zero otherwise.
130        ///
131        /// The outgoing mask can be passed directly to the next limb's subtraction, avoiding
132        /// conversions to and from [`Choice`] at each step of a multi-limb subtraction.
133        #[inline]
134        #[must_use]
135        pub const fn $sub_mask(lhs: $ty, rhs: $ty, borrow: $ty) -> ($ty, $ty) {
136            let (difference, borrow) = $sub_inner(lhs, rhs, borrow >> (<$ty>::BITS - 1));
137            (difference, borrow.wrapping_neg())
138        }
139
140        // The incoming borrow must be zero or one; the outgoing borrow is also zero or one.
141        #[inline(always)]
142        const fn $sub_inner(lhs: $ty, rhs: $ty, borrow: $ty) -> ($ty, $ty) {
143            let difference = lhs.wrapping_sub(rhs).wrapping_sub(borrow);
144            // Keep all arithmetic in the operand type: widening can trigger incorrect
145            // optimization on older compilers: https://github.com/rust-lang/rust/issues/149522
146            // Keep the full-width bit opaque before forming a mask or narrowing it to Choice,
147            // so a caller's masked add-back cannot be folded into a secret-dependent branch.
148            let borrow = black_box(bitborrow!(lhs, rhs, difference, <$ty>::BITS));
149            (difference, borrow)
150        }
151    };
152}
153
154borrowing_sub_primitives!(
155    u32,
156    borrowing_sub_u32,
157    borrowing_sub_mask_u32,
158    borrowing_sub_inner_u32,
159    from_u32_lsb
160);
161borrowing_sub_primitives!(
162    u64,
163    borrowing_sub_u64,
164    borrowing_sub_mask_u64,
165    borrowing_sub_inner_u64,
166    from_u64_lsb
167);
168
169/// Count leading zero bits, returning 32 if `value` is zero.
170#[inline]
171#[must_use]
172pub const fn leading_zeros_u32(value: u32) -> u32 {
173    #[cfg(any(
174        target_arch = "aarch64",
175        target_arch = "x86",
176        target_arch = "x86_64",
177        target_feature = "thumb2",
178        target_feature = "zbb"
179    ))]
180    {
181        value.leading_zeros()
182    }
183    #[cfg(not(any(
184        target_arch = "aarch64",
185        target_arch = "x86",
186        target_arch = "x86_64",
187        target_feature = "thumb2",
188        target_feature = "zbb"
189    )))]
190    {
191        leading_zeros_u32_soft(value)
192    }
193}
194
195/// Count trailing zero bits, returning 32 if `value` is zero.
196#[inline]
197#[must_use]
198pub const fn trailing_zeros_u32(value: u32) -> u32 {
199    #[cfg(any(
200        target_arch = "aarch64",
201        target_arch = "x86",
202        target_arch = "x86_64",
203        target_feature = "thumb2",
204        target_feature = "zbb"
205    ))]
206    {
207        value.trailing_zeros()
208    }
209    #[cfg(not(any(
210        target_arch = "aarch64",
211        target_arch = "x86",
212        target_arch = "x86_64",
213        target_feature = "thumb2",
214        target_feature = "zbb"
215    )))]
216    {
217        // Reversing bits uses fixed shifts and masks when RBIT is unavailable.
218        leading_zeros_u32_soft(value.reverse_bits())
219    }
220}
221
222/// Count leading zero bits, returning 64 if `value` is zero.
223#[inline]
224#[must_use]
225#[allow(clippy::cast_possible_truncation)]
226pub const fn leading_zeros_u64(value: u64) -> u32 {
227    #[cfg(any(target_arch = "aarch64", target_arch = "x86_64"))]
228    {
229        value.leading_zeros()
230    }
231    #[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
232    {
233        let hi = (value >> 32) as u32;
234        let lo = value as u32;
235        let mask = Choice::from_u32_nz(hi).not().to_u32_mask();
236        leading_zeros_u32(hi).wrapping_add(mask & leading_zeros_u32(lo))
237    }
238}
239
240/// Count trailing zero bits, returning 64 if `value` is zero.
241#[inline]
242#[must_use]
243#[allow(clippy::cast_possible_truncation)]
244pub const fn trailing_zeros_u64(value: u64) -> u32 {
245    #[cfg(any(target_arch = "aarch64", target_arch = "x86_64"))]
246    {
247        value.trailing_zeros()
248    }
249    #[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
250    {
251        let hi = (value >> 32) as u32;
252        let lo = value as u32;
253        let mask = Choice::from_u32_nz(lo).not().to_u32_mask();
254        trailing_zeros_u32(lo).wrapping_add(mask & trailing_zeros_u32(hi))
255    }
256}
257
258/// Fixed-stage binary search for the highest set bit, including the zero case.
259#[cfg(any(
260    test,
261    not(any(
262        target_arch = "aarch64",
263        target_arch = "x86",
264        target_arch = "x86_64",
265        target_feature = "thumb2",
266        target_feature = "zbb"
267    ))
268))]
269#[inline]
270#[allow(clippy::arithmetic_side_effects, reason = "shift is between 1 and 16")]
271const fn leading_zeros_u32_soft(mut value: u32) -> u32 {
272    let mut count = 0u32;
273    let mut shift = 16;
274    while shift != 0 {
275        let mask = Choice::from_u32_nz(value >> (u32::BITS - shift))
276            .not()
277            .to_u32_mask();
278        value ^= mask & (value ^ (value << shift));
279        count = count.wrapping_add(mask & shift);
280        shift >>= 1;
281    }
282    count.wrapping_add(Choice::from_u32_nz(value).not().to_u32_mask() & 1)
283}
284
285/// Add two integers, returning the wrapping sum and [`Choice::TRUE`] on overflow.
286#[inline]
287#[must_use]
288pub const fn overflowing_add_u64(lhs: u64, rhs: u64) -> (u64, Choice) {
289    let sum = lhs.wrapping_add(rhs);
290    let carry = ((lhs & rhs) | ((lhs | rhs) & !sum)) >> (u64::BITS - 1);
291    (sum, Choice::from_u64_lsb(carry))
292}
293
294/// Add two integers, returning the wrapping sum and [`Choice::TRUE`] on overflow.
295#[inline]
296#[must_use]
297pub const fn overflowing_add_u128(lhs: u128, rhs: u128) -> (u128, Choice) {
298    #[cfg(target_arch = "riscv32")]
299    {
300        overflowing_add_u128_halves(lhs, rhs)
301    }
302    #[cfg(not(target_arch = "riscv32"))]
303    {
304        let sum = lhs.wrapping_add(rhs);
305        let carry = ((lhs & rhs) | ((lhs | rhs) & !sum)) >> (u128::BITS - 1);
306        (sum, Choice::from_u128_lsb(carry))
307    }
308}
309
310// RV32 can branch even in `u128::wrapping_add`, before computing the final carry.
311// Keep this workaround local to that target, preserving native addition elsewhere.
312#[cfg(any(target_arch = "riscv32", test))]
313#[inline]
314#[allow(clippy::cast_possible_truncation)]
315const fn overflowing_add_u128_halves(lhs: u128, rhs: u128) -> (u128, Choice) {
316    let (lo, lo_carry) = overflowing_add_u64(lhs as u64, rhs as u64);
317    let (hi, hi_carry) = overflowing_add_u64((lhs >> 64) as u64, (rhs >> 64) as u64);
318    let (hi, carry) = overflowing_add_u64(hi, lo_carry.to_u8() as u64);
319    (((hi as u128) << 64) | lo as u128, hi_carry.or(carry))
320}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325
326    // Keep all public entrypoints usable by const callers such as crypto-bigint.
327    const _: () = {
328        assert!(borrowing_sub_u32(0, 0, Choice::TRUE).0 == u32::MAX);
329        assert!(borrowing_sub_u32(0, 0, Choice::TRUE).1.to_bool());
330        assert!(borrowing_sub_u64(0, 0, Choice::TRUE).0 == u64::MAX);
331        assert!(borrowing_sub_u64(0, 0, Choice::TRUE).1.to_bool());
332        assert!(!borrowing_sub_u32(1, 0, Choice::TRUE).1.to_bool());
333        assert!(!borrowing_sub_u64(1, 0, Choice::TRUE).1.to_bool());
334        assert!(borrowing_sub_mask_u32(0, 0, u32::MAX).0 == u32::MAX);
335        assert!(borrowing_sub_mask_u32(0, 0, u32::MAX).1 == u32::MAX);
336        assert!(borrowing_sub_mask_u64(0, 0, u64::MAX).0 == u64::MAX);
337        assert!(borrowing_sub_mask_u64(0, 0, u64::MAX).1 == u64::MAX);
338        assert!(borrowing_sub_mask_u32(1, 0, u32::MAX).1 == 0);
339        assert!(borrowing_sub_mask_u64(1, 0, u64::MAX).1 == 0);
340        assert!(leading_zeros_u32(0) == 32);
341        assert!(trailing_zeros_u32(0) == 32);
342        assert!(leading_zeros_u64(0) == 64);
343        assert!(trailing_zeros_u64(0) == 64);
344        assert!(overflowing_add_u64(u64::MAX, 1).1.to_bool());
345        assert!(overflowing_add_u128(u128::MAX, 1).1.to_bool());
346    };
347
348    #[test]
349    fn zero_counts_u32() {
350        for bit in 0..u32::BITS {
351            for value in [0, 1 << bit, !(1 << bit), u32::MAX >> bit] {
352                assert_eq!(leading_zeros_u32(value), value.leading_zeros());
353                assert_eq!(trailing_zeros_u32(value), value.trailing_zeros());
354                // Exercise the software fallback even on hosts with native instructions.
355                assert_eq!(leading_zeros_u32_soft(value), value.leading_zeros());
356                assert_eq!(
357                    leading_zeros_u32_soft(value.reverse_bits()),
358                    value.trailing_zeros()
359                );
360            }
361        }
362    }
363
364    #[test]
365    fn zero_counts_u64() {
366        for bit in 0..u64::BITS {
367            for value in [0, 1 << bit, !(1 << bit), u64::MAX >> bit] {
368                assert_eq!(leading_zeros_u64(value), value.leading_zeros());
369                assert_eq!(trailing_zeros_u64(value), value.trailing_zeros());
370            }
371        }
372    }
373
374    macro_rules! subtraction_tests {
375        ($test:ident, $ty:ty, $sub:ident, $sub_mask:ident) => {
376            #[test]
377            fn $test() {
378                let half = 1 << (<$ty>::BITS >> 1);
379                let high = 1 << (<$ty>::BITS - 1);
380                let values = [0, 1, half - 1, half, half + 1, high - 1, high, <$ty>::MAX];
381                for lhs in values {
382                    for rhs in values {
383                        // Include noncanonical masks: only the most significant bit matters.
384                        for mask in [0, 1, high - 1, high, <$ty>::MAX - 1, <$ty>::MAX] {
385                            let incoming = mask >> (<$ty>::BITS - 1) != 0;
386                            let (expected, first_borrow) = lhs.overflowing_sub(rhs);
387                            let (expected, second_borrow) =
388                                expected.overflowing_sub(<$ty>::from(incoming));
389                            let (difference, borrow) =
390                                $sub(lhs, rhs, Choice::from_u8_lsb(u8::from(incoming)));
391                            assert_eq!(
392                                (difference, borrow.to_bool()),
393                                (expected, first_borrow | second_borrow)
394                            );
395                            assert_eq!(
396                                $sub_mask(lhs, rhs, mask),
397                                (
398                                    expected,
399                                    <$ty>::from(first_borrow | second_borrow).wrapping_neg()
400                                )
401                            );
402                        }
403                    }
404                }
405            }
406        };
407    }
408
409    subtraction_tests!(sub_u32, u32, borrowing_sub_u32, borrowing_sub_mask_u32);
410    subtraction_tests!(sub_u64, u64, borrowing_sub_u64, borrowing_sub_mask_u64);
411
412    #[test]
413    fn sub_mask_propagates_borrow() {
414        let (lo, borrow) = borrowing_sub_mask_u32(0, 1, 0);
415        let (mid, borrow) = borrowing_sub_mask_u32(0, 0, borrow);
416        assert_eq!((lo, mid, borrow), (u32::MAX, u32::MAX, u32::MAX));
417        assert_eq!(borrowing_sub_mask_u32(1, 0, borrow), (0, 0));
418
419        let (lo, borrow) = borrowing_sub_mask_u64(0, 1, 0);
420        let (mid, borrow) = borrowing_sub_mask_u64(0, 0, borrow);
421        assert_eq!((lo, mid, borrow), (u64::MAX, u64::MAX, u64::MAX));
422        assert_eq!(borrowing_sub_mask_u64(1, 0, borrow), (0, 0));
423    }
424
425    macro_rules! addition_tests {
426        ($test:ident, $ty:ty, $add:ident) => {
427            #[test]
428            fn $test() {
429                // Include both full-width and half-width carry boundaries.
430                let half = 1 << (<$ty>::BITS >> 1);
431                let high = 1 << (<$ty>::BITS - 1);
432                let values = [0, 1, half - 1, half, half + 1, high - 1, high, <$ty>::MAX];
433                for lhs in values {
434                    for rhs in values {
435                        let (sum, carry) = $add(lhs, rhs);
436                        assert_eq!((sum, carry.to_bool()), lhs.overflowing_add(rhs));
437                    }
438                }
439            }
440        };
441    }
442
443    addition_tests!(add_u64, u64, overflowing_add_u64);
444    addition_tests!(add_u128, u128, overflowing_add_u128);
445    addition_tests!(add_u128_halves, u128, overflowing_add_u128_halves);
446}