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