`first_set_bit` and `last_set_bit` for integer types

[Gnurou]

Proposal

Problem statement

The standard library provides several bit-counting methods for integer types, like the leading_ones, trailing_ones, and their zeros counterparts. Two other common operations that are currently missing are the first_set_bit (ffs) and last_set_bit (fls) operations, which return the 1-based index of the least significant and most significant set bit in the value, respectively (wikipedia article).

These operations are commonly used in operating system kernels (both are used hundreds of times in the Linux kernel for instance), and the Rust for Linux project is currently implementing workarounds due to their absence.

This ACP proposes to integrate them into the standard library as they are likely to be useful in other projects as well.

Motivating examples or use cases

The ffs and fls operations are available in the BSD standard C library, the Linux kernel, and many other low-level libraries. They are hardware-supported on most popular CPUs (x86 for instance has the BSF and BSR instructions).

Looking at the Linux kernel alone, their use cases include memory allocators, schedulers, event handling, networking, audio codecs, and countless drivers.

The first user of last_set_bit in the Rust-for-Linux project will be the Nova GPU driver.

Solution sketch

These methods can be implemented on integer types similarly to e.g. leading_ones. For instance, on u32:

/// Returns the 1-based index of the first (least significant) set bit in the
/// binary representation of `self`, or `0` if no bit is set.
pub const fn first_set_bit(self) -> u32;

/// Returns the 1-based index of the last (most significant) set bit in the
/// binary representation of `self`, or `0` if no bit is set.
pub const fn last_set_bit(self) -> u32;

Implementation-wise, first_set_bit is equivalent to if self == 0 { 0 } else { self.trailing_zeros() + 1 } and last_set_bit to Self::BITS - self.leading_zeros(). Most popular CPUs have hardware support for these operations, so they can also be leveraged at the compiler level.

Alternatives

The alternative is to perform the implementation code described above in-place, which is less explicit about the intent of the code, and potentially error-prone. Also, hardware support is unlikely to be leveraged in this case, potentially leading to performance loss in critical code paths.

Links and related work

• Current work-in-progress implementation of last_set_bit() in the Rust-for-Linux project

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[ChayimFriedman2]

I think these should return Option<NonZeroU32> instead of u32.

[programmerjake]

can you elaborate on why checked_ilog2 isn't sufficient? these semantics seems like the kind of thing where POSIX decided to return 1 + the_actual_number_you_care_about since C doesn't have Option<u32> so decided to return 0 for None. From the wikipedia article, basically all hardware implements it by using count_leading_zeros or ilog2 (x86 BSR).

Also, hardware support is unlikely to be leveraged in this case, potentially leading to performance loss in critical code paths.

that seems false to me...the standard library will implement it with basically the exact same code that other crates would use so I don't see why it would produce more optimized code in the standard library.

[programmerjake]

also, the names are confusing since they use the reverse first/last (they count the LSB as first) from leading/trailing_zeros (which counts the MSB as first).

[Gnurou]

@programmerjake After checking the generated code on compiler explorer, I agree that checked_ilog2 covers the needs of last_set_bit, even using BSR as appropriate. Its zero-indexing and use of Option also make more sense with Rust. And after looking at how fls is used in the kernel, I saw many uses where - 1 was subtracted to the result, so the zero-indexing is not particularly a problem - actually it might even be better.

I haven't found an elegant existing replacement for first_set_bit though. trailing_zeros is the closest, but we still need to explicitly check for 0, where we would want None in this case. Checking whether the result of the operation is the size in bits of the type looks error-prone, and doing if 0 { None } else { Some(foo.leading_zeros()) } is a bit cumbersome for such a common operation.

[hanna-kruppe]

Since first_set_bit fails on input 0, it should also be provided on NonZero integer types so that nobody has to write x.get().first_set_bit().expect("x is non-zero") when they want to get the first set bit of x: NonZero<_>. But for NonZero, first_set_bit is just another name for trailing_zeros. So instead of adding $int::first_set_bit, you could use NonZero<$int>::trailing_zeros today. Either use NonZero::new as the zero check or adjust the surrounding code so that the input is known to be non-zero earlier.

[okaneco]

Related functions which return an integer with the most or least significant one set, instead of the index of that bit.
rust-lang/rust#136909
#467

In your use case, is the index needed or the power-of-two integer result?

[pthariensflame]

Would it be worth adding doc aliases for {integer}::checked_ilog2 and NonZero::trailing_zeros so that people looking for fls/ffs functionality will find them?

[ojeda]

Yeah, that is what I suggested in the mailing list, although I am not sure what is the policy nowadays for doc(alias). IIRC a few years ago or so there was some pushback to adding a bunch of them to the standard library.

[joshtriplett]

We discussed these in today's @rust-lang/libs-api meeting.

We'd like to see these added, but with a couple of changes:

• We'd like them to return Option<u32>, and be zero-indexed.
• We'd like to have the same methods on NonZero, but there they don't need Option.
• We'd like to use a name that doesn't use the ambiguous and confusing "first" and "last". In the meeting, we favored "highest" and "lowest" (e.g. highest_one and lowest_one), but we can re-evaluate the bikeshed at stabilization.

We recognize that these methods are potentially redundant with checked_ilog2, but we'd like to add them anyway because they're more readable for some use cases, notably those that are focused on bitwise operations rather than numeric values.

Also, we should aim for naming consistency with #467 (rust-lang/rust#136909), so if we use highest_one and lowest_one here, we should use isolate_highest_one and isolate_lowest_one for those.