1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

// Note: these functions happen to produce the correct `usize::leading_zeros(0)` value
// without a explicit zero check. Zero is probably common enough that it could warrant
// adding a zero check at the beginning, but `__clzsi2` has a precondition that `x != 0`.
// Compilers will insert the check for zero in cases where it is needed.

public_test_dep! {
/// Returns the number of leading binary zeros in `x`.
#[allow(dead_code)]
pub(crate) fn usize_leading_zeros_default(x: usize) -> usize {
    // The basic idea is to test if the higher bits of `x` are zero and bisect the number
    // of leading zeros. It is possible for all branches of the bisection to use the same
    // code path by conditionally shifting the higher parts down to let the next bisection
    // step work on the higher or lower parts of `x`. Instead of starting with `z == 0`
    // and adding to the number of zeros, it is slightly faster to start with
    // `z == usize::MAX.count_ones()` and subtract from the potential number of zeros,
    // because it simplifies the final bisection step.
    let mut x = x;
    // the number of potential leading zeros
    let mut z = usize::MAX.count_ones() as usize;
    // a temporary
    let mut t: usize;
    #[cfg(target_pointer_width = "64")]
    {
        t = x >> 32;
        if t != 0 {
            z -= 32;
            x = t;
        }
    }
    #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
    {
        t = x >> 16;
        if t != 0 {
            z -= 16;
            x = t;
        }
    }
    t = x >> 8;
    if t != 0 {
        z -= 8;
        x = t;
    }
    t = x >> 4;
    if t != 0 {
        z -= 4;
        x = t;
    }
    t = x >> 2;
    if t != 0 {
        z -= 2;
        x = t;
    }
    // the last two bisections are combined into one conditional
    t = x >> 1;
    if t != 0 {
        z - 2
    } else {
        z - x
    }

    // We could potentially save a few cycles by using the LUT trick from
    // "https://embeddedgurus.com/state-space/2014/09/
    // fast-deterministic-and-portable-counting-leading-zeros/".
    // However, 256 bytes for a LUT is too large for embedded use cases. We could remove
    // the last 3 bisections  and use this 16 byte LUT for the rest of the work:
    //const LUT: [u8; 16] = [0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4];
    //z -= LUT[x] as usize;
    //z
    // However, it ends up generating about the same number of instructions. When benchmarked
    // on x86_64, it is slightly faster to use the LUT, but this is probably because of OOO
    // execution effects. Changing to using a LUT and branching is risky for smaller cores.
}
}

// The above method does not compile well on RISC-V (because of the lack of predicated
// instructions), producing code with many branches or using an excessively long
// branchless solution. This method takes advantage of the set-if-less-than instruction on
// RISC-V that allows `(x >= power-of-two) as usize` to be branchless.

public_test_dep! {
/// Returns the number of leading binary zeros in `x`.
#[allow(dead_code)]
pub(crate) fn usize_leading_zeros_riscv(x: usize) -> usize {
    let mut x = x;
    // the number of potential leading zeros
    let mut z = usize::MAX.count_ones() as usize;
    // a temporary
    let mut t: usize;

    // RISC-V does not have a set-if-greater-than-or-equal instruction and
    // `(x >= power-of-two) as usize` will get compiled into two instructions, but this is
    // still the most optimal method. A conditional set can only be turned into a single
    // immediate instruction if `x` is compared with an immediate `imm` (that can fit into
    // 12 bits) like `x < imm` but not `imm < x` (because the immediate is always on the
    // right). If we try to save an instruction by using `x < imm` for each bisection, we
    // have to shift `x` left and compare with powers of two approaching `usize::MAX + 1`,
    // but the immediate will never fit into 12 bits and never save an instruction.
    #[cfg(target_pointer_width = "64")]
    {
        // If the upper 32 bits of `x` are not all 0, `t` is set to `1 << 5`, otherwise
        // `t` is set to 0.
        t = ((x >= (1 << 32)) as usize) << 5;
        // If `t` was set to `1 << 5`, then the upper 32 bits are shifted down for the
        // next step to process.
        x >>= t;
        // If `t` was set to `1 << 5`, then we subtract 32 from the number of potential
        // leading zeros
        z -= t;
    }
    #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
    {
        t = ((x >= (1 << 16)) as usize) << 4;
        x >>= t;
        z -= t;
    }
    t = ((x >= (1 << 8)) as usize) << 3;
    x >>= t;
    z -= t;
    t = ((x >= (1 << 4)) as usize) << 2;
    x >>= t;
    z -= t;
    t = ((x >= (1 << 2)) as usize) << 1;
    x >>= t;
    z -= t;
    t = (x >= (1 << 1)) as usize;
    x >>= t;
    z -= t;
    // All bits except the LSB are guaranteed to be zero for this final bisection step.
    // If `x != 0` then `x == 1` and subtracts one potential zero from `z`.
    z - x
}
}

intrinsics! {
    #[maybe_use_optimized_c_shim]
    #[cfg(any(
        target_pointer_width = "16",
        target_pointer_width = "32",
        target_pointer_width = "64"
    ))]
    /// Returns the number of leading binary zeros in `x`.
    pub extern "C" fn __clzsi2(x: usize) -> usize {
        if cfg!(any(target_arch = "riscv32", target_arch = "riscv64")) {
            usize_leading_zeros_riscv(x)
        } else {
            usize_leading_zeros_default(x)
        }
    }
}