1use crate::Choice;
12use core::hint::black_box;
13
14macro_rules! bitle {
18 ($x:expr, $y:expr, $bits:expr) => {
19 (((!$x) | $y) & (($x ^ $y) | !($y.wrapping_sub($x)))) >> ($bits - 1)
20 };
21}
22
23macro_rules! bitborrow {
27 ($x:expr, $y:expr, $result:expr, $bits:expr) => {
28 (((!$x) & $y) | (((!$x) | $y) & $result)) >> ($bits - 1)
29 };
30}
31
32macro_rules! bitlt {
36 ($x:expr, $y:expr, $bits:expr) => {
37 $crate::primitives::bitborrow!($x, $y, ($x).wrapping_sub($y), $bits)
38 };
39}
40
41macro_rules! bitnz {
43 ($value:expr, $bits:expr) => {
44 ($value | $value.wrapping_neg()) >> ($bits - 1)
45 };
46}
47
48pub(crate) use {bitborrow, bitle, bitlt};
49
50macro_rules! nonzero_primitive {
54 ($ty:ty, $nz:ident, $from_lsb:ident) => {
55 #[inline(always)]
56 pub(crate) const fn $nz(value: $ty) -> Choice {
57 #[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
77macro_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 #[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 #[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 #[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 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#[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#[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 leading_zeros_u32_soft(value.reverse_bits())
219 }
220}
221
222#[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#[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#[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#[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#[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#[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 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 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 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 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}