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