1#[cfg(feature = "unstable-public-internals")]
2pub use implementation::trailing_zeros;
3#[cfg(not(feature = "unstable-public-internals"))]
4pub(crate) use implementation::trailing_zeros;
5
6mod implementation {
7 use crate::int::{CastFrom, Int};
8
9 /// Returns number of trailing binary zeros in `x`.
10 #[allow(dead_code)]
11 pub fn trailing_zeros<I: Int>(x: I) -> usize
12 where
13 u32: CastFrom<I>,
14 u16: CastFrom<I>,
15 u8: CastFrom<I>,
16 {
17 let mut x = x;
18 let mut r: u32 = 0;
19 let mut t: u32;
20
21 const { assert!(I::BITS <= 64) };
22 if I::BITS >= 64 {
23 r += ((u32::cast_from_lossy(x) == 0) as u32) << 5; // if (x has no 32 small bits) t = 32 else 0
24 x >>= r; // remove 32 zero bits
25 }
26
27 if I::BITS >= 32 {
28 t = ((u16::cast_from_lossy(x) == 0) as u32) << 4; // if (x has no 16 small bits) t = 16 else 0
29 r += t;
30 x >>= t; // x = [0 - 0xFFFF] + higher garbage bits
31 }
32
33 const { assert!(I::BITS >= 16) };
34 t = ((u8::cast_from_lossy(x) == 0) as u32) << 3;
35 x >>= t; // x = [0 - 0xFF] + higher garbage bits
36 r += t;
37
38 let mut x: u8 = x.cast_lossy();
39
40 t = (((x & 0x0F) == 0) as u32) << 2;
41 x >>= t; // x = [0 - 0xF] + higher garbage bits
42 r += t;
43
44 t = (((x & 0x3) == 0) as u32) << 1;
45 x >>= t; // x = [0 - 0x3] + higher garbage bits
46 r += t;
47
48 x &= 3;
49
50 r as usize + ((2 - (x >> 1) as usize) & (((x & 1) == 0) as usize).wrapping_neg())
51 }
52}
53
54intrinsics! {
55 /// Returns the number of trailing binary zeros in `x` (32 bit version).
56 pub extern "C" fn __ctzsi2(x: u32) -> usize {
57 trailing_zeros(x)
58 }
59
60 /// Returns the number of trailing binary zeros in `x` (64 bit version).
61 pub extern "C" fn __ctzdi2(x: u64) -> usize {
62 trailing_zeros(x)
63 }
64
65 /// Returns the number of trailing binary zeros in `x` (128 bit version).
66 pub extern "C" fn __ctzti2(x: u128) -> usize {
67 let lo = x as u64;
68 if lo == 0 {
69 64 + __ctzdi2((x >> 64) as u64)
70 } else {
71 __ctzdi2(lo)
72 }
73 }
74}
75