1// Note: these functions happen to produce the correct `usize::leading_zeros(0)` value
2// without a explicit zero check. Zero is probably common enough that it could warrant
3// adding a zero check at the beginning, but `__clzsi2` has a precondition that `x != 0`.
4// Compilers will insert the check for zero in cases where it is needed.
5
6#[cfg(feature = "unstable-public-internals")]
7pub use implementation::{leading_zeros_default, leading_zeros_riscv};
8#[cfg(not(feature = "unstable-public-internals"))]
9pub(crate) use implementation::{leading_zeros_default, leading_zeros_riscv};
10
11mod implementation {
12 use crate::int::{CastFrom, Int};
13
14 /// Returns the number of leading binary zeros in `x`.
15 #[allow(dead_code)]
16 pub fn leading_zeros_default<I: Int>(x: I) -> usize
17 where
18 usize: CastFrom<I>,
19 {
20 // The basic idea is to test if the higher bits of `x` are zero and bisect the number
21 // of leading zeros. It is possible for all branches of the bisection to use the same
22 // code path by conditionally shifting the higher parts down to let the next bisection
23 // step work on the higher or lower parts of `x`. Instead of starting with `z == 0`
24 // and adding to the number of zeros, it is slightly faster to start with
25 // `z == usize::MAX.count_ones()` and subtract from the potential number of zeros,
26 // because it simplifies the final bisection step.
27 let mut x = x;
28 // the number of potential leading zeros
29 let mut z = I::BITS as usize;
30 // a temporary
31 let mut t: I;
32
33 const { assert!(I::BITS <= 64) };
34 if I::BITS >= 64 {
35 t = x >> 32;
36 if t != I::ZERO {
37 z -= 32;
38 x = t;
39 }
40 }
41 if I::BITS >= 32 {
42 t = x >> 16;
43 if t != I::ZERO {
44 z -= 16;
45 x = t;
46 }
47 }
48 const { assert!(I::BITS >= 16) };
49 t = x >> 8;
50 if t != I::ZERO {
51 z -= 8;
52 x = t;
53 }
54 t = x >> 4;
55 if t != I::ZERO {
56 z -= 4;
57 x = t;
58 }
59 t = x >> 2;
60 if t != I::ZERO {
61 z -= 2;
62 x = t;
63 }
64 // the last two bisections are combined into one conditional
65 t = x >> 1;
66 if t != I::ZERO {
67 z - 2
68 } else {
69 z - usize::cast_from(x)
70 }
71
72 // We could potentially save a few cycles by using the LUT trick from
73 // "https://embeddedgurus.com/state-space/2014/09/
74 // fast-deterministic-and-portable-counting-leading-zeros/".
75 // However, 256 bytes for a LUT is too large for embedded use cases. We could remove
76 // the last 3 bisections and use this 16 byte LUT for the rest of the work:
77 //const LUT: [u8; 16] = [0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4];
78 //z -= LUT[x] as usize;
79 //z
80 // However, it ends up generating about the same number of instructions. When benchmarked
81 // on x86_64, it is slightly faster to use the LUT, but this is probably because of OOO
82 // execution effects. Changing to using a LUT and branching is risky for smaller cores.
83 }
84
85 // The above method does not compile well on RISC-V (because of the lack of predicated
86 // instructions), producing code with many branches or using an excessively long
87 // branchless solution. This method takes advantage of the set-if-less-than instruction on
88 // RISC-V that allows `(x >= power-of-two) as usize` to be branchless.
89
90 /// Returns the number of leading binary zeros in `x`.
91 #[allow(dead_code)]
92 pub fn leading_zeros_riscv<I: Int>(x: I) -> usize
93 where
94 usize: CastFrom<I>,
95 {
96 let mut x = x;
97 // the number of potential leading zeros
98 let mut z = I::BITS;
99 // a temporary
100 let mut t: u32;
101
102 // RISC-V does not have a set-if-greater-than-or-equal instruction and
103 // `(x >= power-of-two) as usize` will get compiled into two instructions, but this is
104 // still the most optimal method. A conditional set can only be turned into a single
105 // immediate instruction if `x` is compared with an immediate `imm` (that can fit into
106 // 12 bits) like `x < imm` but not `imm < x` (because the immediate is always on the
107 // right). If we try to save an instruction by using `x < imm` for each bisection, we
108 // have to shift `x` left and compare with powers of two approaching `usize::MAX + 1`,
109 // but the immediate will never fit into 12 bits and never save an instruction.
110 const { assert!(I::BITS <= 64) };
111 if I::BITS >= 64 {
112 // If the upper 32 bits of `x` are not all 0, `t` is set to `1 << 5`, otherwise
113 // `t` is set to 0.
114 t = ((x >= (I::ONE << 32)) as u32) << 5;
115 // If `t` was set to `1 << 5`, then the upper 32 bits are shifted down for the
116 // next step to process.
117 x >>= t;
118 // If `t` was set to `1 << 5`, then we subtract 32 from the number of potential
119 // leading zeros
120 z -= t;
121 }
122 if I::BITS >= 32 {
123 t = ((x >= (I::ONE << 16)) as u32) << 4;
124 x >>= t;
125 z -= t;
126 }
127 const { assert!(I::BITS >= 16) };
128 t = ((x >= (I::ONE << 8)) as u32) << 3;
129 x >>= t;
130 z -= t;
131 t = ((x >= (I::ONE << 4)) as u32) << 2;
132 x >>= t;
133 z -= t;
134 t = ((x >= (I::ONE << 2)) as u32) << 1;
135 x >>= t;
136 z -= t;
137 t = (x >= (I::ONE << 1)) as u32;
138 x >>= t;
139 z -= t;
140 // All bits except the LSB are guaranteed to be zero for this final bisection step.
141 // If `x != 0` then `x == 1` and subtracts one potential zero from `z`.
142 z as usize - usize::cast_from(x)
143 }
144}
145
146intrinsics! {
147 /// Returns the number of leading binary zeros in `x`
148 pub extern "C" fn __clzsi2(x: u32) -> usize {
149 if cfg!(any(target_arch = "riscv32", target_arch = "riscv64")) {
150 leading_zeros_riscv(x)
151 } else {
152 leading_zeros_default(x)
153 }
154 }
155
156 /// Returns the number of leading binary zeros in `x`
157 pub extern "C" fn __clzdi2(x: u64) -> usize {
158 if cfg!(any(target_arch = "riscv32", target_arch = "riscv64")) {
159 leading_zeros_riscv(x)
160 } else {
161 leading_zeros_default(x)
162 }
163 }
164
165 /// Returns the number of leading binary zeros in `x`
166 pub extern "C" fn __clzti2(x: u128) -> usize {
167 let hi = (x >> 64) as u64;
168 if hi == 0 {
169 64 + __clzdi2(x as u64)
170 } else {
171 __clzdi2(hi)
172 }
173 }
174}
175