algorithmbit-manipulationriscvmicro-optimizationriscv32# Branchless count-leading-zeros on 32-bit RISC-V without Zbb extension

The context of this question is the creation of a side-channel resistant implementation of a IEEE-754 compliant single-precision square root for a 32-bit RISC-V platform without hardware support for floating-point arithmetic and without the Zbb extension for advanced bit manipulation. Integer multiplies, in particular the `MUL`

and `MULHU`

instructions, *are* supported by the hardware and can be assumed to have fixed latency. Counting the leading zero bits is required for normalization of subnormal operands, and the `CLZ`

emulation should be branchless because of the side-channel resistant design.

I started with C99 code for a 32-bit leading-zero count that I used twenty years ago on ARMv4t processors. This is a *full-range* implementation, i.e. it returns 32 for an input of zero.

```
uint32_t cntlz (uint32_t a)
{
uint32_t n = 0;
#if 0
n = __builtin_clz (a);
#else
n = !a + 1;
if (a < 0x00010000u) { n |= 16; a <<= 16; }
if (a < 0x01000000u) { n |= 8; a <<= 8; }
if (a < 0x10000000u) { n |= 4; a <<= 4; }
if (a < 0x40000000u) { n += 2; a <<= 2; }
n = n - (a >> 31);
#endif
return n;
}
```

As a *sanity check*, I compiled the above source with clang 18.1 `-marm -march=armv4t`

, resulting in the following code that, at 16 instruction without function return, uses one instruction more than the best ARMv4t implementation I am aware of (which uses 15 instructions without the function return):

```
cntlz:
mov r1, #1
cmp r0, #0
moveq r1, #2
cmp r0, #65536
lsllo r0, r0, #16
orrlo r1, r1, #16
cmp r0, #16777216
lsllo r0, r0, #8
orrlo r1, r1, #8
cmp r0, #268435456
lsllo r0, r0, #4
orrlo r1, r1, #4
cmp r0, #1073741824
addlo r1, r1, #2
lsllo r0, r0, #2
add r0, r1, r0, asr #31
bx lr
```

I am currently working without access to a RISC-V development platform and used Compiler Explorer to compile for a 32-bit RISC-V target. I could not figure out how to specify extensions properly to turn off floating-point support, so I used clang 18.1 with `-march=rv32gc`

, which resulted in the following assembly code being generated:

```
cntlz: # @cntlz
seqz a1, a0
srli a2, a0, 16
seqz a2, a2
slli a2, a2, 4
or a1, a1, a2
sll a0, a0, a2
srli a2, a0, 24
seqz a2, a2
slli a2, a2, 3
or a1, a1, a2
sll a0, a0, a2
srli a2, a0, 28
seqz a2, a2
slli a2, a2, 2
or a1, a1, a2
sll a0, a0, a2
srli a2, a0, 30
seqz a2, a2
slli a2, a2, 1
or a1, a1, a2
sll a0, a0, a2
srai a0, a0, 31
add a0, a0, a1
addi a0, a0, 1
ret
```

I am unable to identify any improvements to the code generated by Clang, that is, it appears to be as tight as possible. I am aware that RISC-V implementations could implement macro-op fusion. See: Christopher Celio, et al., "The Renewed Case for the Reduced Instruction Set Computer:
Avoiding ISA Bloat with Macro-Op Fusion for RISC-V", UC Berkeley technical report EECS-2016-130. But none of the fusion idioms discussed in the report appear to apply to this code, leading me to assume an execution time of 24 cycles for this 24 instruction sequence (without the function return). I was curious what `__builtin_clz()`

resolves to. Compiling with that code path enabled results in a 31-instruction sequence that converts the leading zeros into a left-justified mask of 1-bits and then applies a population count computation to the mask:

```
srli a1, a0, 1
or a0, a0, a1
srli a1, a0, 2
or a0, a0, a1
srli a1, a0, 4
or a0, a0, a1
srli a1, a0, 8
or a0, a0, a1
srli a1, a0, 16
or a0, a0, a1
not a0, a0 // a0 now left-aligned mask of 1-bits
srli a1, a0, 1
lui a2, 349525
addi a2, a2, 1365
and a1, a1, a2
sub a0, a0, a1
lui a1, 209715
addi a1, a1, 819
and a2, a0, a1
srli a0, a0, 2
and a0, a0, a1
add a0, a0, a2
srli a1, a0, 4
add a0, a0, a1
lui a1, 61681
addi a1, a1, -241
and a0, a0, a1
lui a1, 4112
addi a1, a1, 257
mul a0, a0, a1
srli a0, a0, 24
ret
```

Again, I am not sure what instructions could be subject to macro-op fusion here, but the most likely candidate seems to be the `LUI`

/`ADDI`

idiom used to load 32-bit immediate data, similar to the way modern ARM processors fuse `MOVW`

/`MOVT`

pairs. With that assumption, the code would still appear to be slower than what I currently have. I tried half a dozen additional integer-based variants of 32-bit `CLZ`

emulation and did not find any that resulted in fewer than 24 instructions. I also searched the internet and was unable to find anything superior to my current code.

Are there any *branchless* full-range implementations of leading-zero count for 32-bit RISC-V platforms that require fewer than 24 cycles? Conservatively, I want to assume the absence of macro-op fusion as this seems like an expensive feature in a low-end microcontroller, but answers relying on macro-op fusion as present in existing RISC-V implementations are also welcome.

**Note:** Table-based methods are not suitable in this context as table access could trigger cache misses which can be exploited for side-channel attacks.

**Update 6/9/2024**: After working on this issue for another 1.5 days, I found a variant that should reduce the number of instructions required from 24 to 22, however, not all compilers can actually deliver the desired code.

The basic observation is that the RISC-V ISA is not orthogonal with regard to `SET`

-type instructions, in that it only supports a "less than" flavor. Other comparisons may require inversion of the comparison followed by *inversion of the result*, for example by XOR-ing 1, or applying `SEQZ`

, adding one instruction per instance. My idea now is to avoid this per-instance inversion by transposing a positive operand into a negative one *once*, allowing the direct use of "less than" comparisons. Expressed in portable C++11 code, and annotated with the RISC-V instructions I expect to be generated:

```
// https://stackoverflow.com/a/74563384/780717
// Only applies right shift to non-negative values to avoid implementation-defined behavior
int32_t sra (int32_t x, int32_t y)
{
return (x < 0) ? (~(~x >> y)) : (x >> y);
}
uint32_t cntlz_rv32 (uint32_t a)
{
uint32_t n, t;
int32_t as;
n = !a; // 1: seqz
t = ((a >> 16)!=0)*16; n = n - t; a = a >> t; // 5: srli, snez, slli, sub, srl
as = (int32_t)(~a); // 1: not
t = (as < -256) * 8; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
t = (as < -16) * 4; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
t = (as < -4) * 2; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
t = (as < -2) * 1; n = n - t; // 2: slti, sub
n += 31; // 1: addi
return n; // 22 instructions total w/o ret
}
```

With gcc 13.3 (**not** 14.1), the following branchless 22-instruction sequence (not counting the `ret`

) is generated:

```
cntlz_rv32(unsigned int):
srli a3,a0,16
snez a3,a3
slli a3,a3,4
srl a4,a0,a3
not a4,a4
slti a1,a4,-256
slli a1,a1,3
sra a4,a4,a1
slti a2,a4,-16
slli a2,a2,2
seqz a5,a0
addi a5,a5,31
sra a0,a4,a2
slti a4,a0,-4
sub a5,a5,a3
slli a4,a4,1
sub a5,a5,a1
sub a5,a5,a2
sra a0,a0,a4
sub a5,a5,a4
slti a0,a0,-2
sub a0,a5,a0
ret
```

For reasons I do not understand, gcc 14.1 refuses to generate the expected `SLTI`

with `-256`

. By moving the comparison prior to the application of the 1's complement it then requires the addition of an `SEQZ`

to invert the result of the comparison. clang 18.1 generates an inefficient 33-instruction sequence for the above source code for no reason that I can discern.

Solution

After some more thinking, I invented hybrid approach, when long shifts by 16/8/4 performed as in the 1st version (binary searches), and instead of last two ones, performed "table lookup", when table - just 32-bit word. I not sure, is this better than two previous approaches, but try to check it, also:

```
uint32_t myclz2(uint32_t x) {
int r = !x, c;
c = (x < 0x00010000) << 4;
r += c; x <<= c; // off 16
c = (x < 0x01000000) << 3;
r += c; x <<= c; // off 8
c = (x < 0x10000000) << 2;
r += c; x <<= c; // off 4
c = (x >> (32 - 4 - 1)) & 0x1e;
r += (0x55af >> c) & 3;
return r;
}
```

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?