Re: [PATCH 1/2] rust: add BitInt integer wrapping type

Alexandre Courbot
2025-11-04T03:13:39Z

On Tue Nov 4, 2025 at 4:36 AM JST, Yury Norov wrote:
> On Mon, Nov 03, 2025 at 10:42:13PM +0900, Alexandre Courbot wrote:
>> Hi Yury,
>>
>> On Mon Nov 3, 2025 at 11:17 AM JST, Yury Norov wrote:
>> > On Fri, Oct 31, 2025 at 10:39:57PM +0900, Alexandre Courbot wrote:
>> >> Add the `BitInt` type, which is an integer on which the number of bits
>> >> allowed to be used is restricted, capping its maximal value below that
>> >> of primitive type is wraps.
>> >>
>> >> This is useful to e.g. enforce guarantees when working with bit fields.
>> >>
>> >> Alongside this type, provide many `From` and `TryFrom` implementations
>> >> are to reduce friction when using with regular integer types. Proxy
>> >> implementations of common integer traits are also provided.
>> >>
>> >> Signed-off-by: Alexandre Courbot <acourbot@nvidia.com>
>> >> ---
>> >> rust/kernel/lib.rs | 1 +
>> >> rust/kernel/num.rs | 75 ++++
>> >> rust/kernel/num/bitint.rs | 896 ++++++++++++++++++++++++++++++++++++++++++++++
>> >> 3 files changed, 972 insertions(+)
>> >
>> > ...
>> >
>> >> +/// Evaluates to `true` if `$value` can be represented using at most `$num_bits` on `$type`.
>> >> +///
>> >> +/// Can be used in const context.
>> >> +macro_rules! fits_within {
>> >> + ($value:expr, $type:ty, $num_bits:expr) => {{
>> >> + // Any attempt to create a `BitInt` with more bits used for representation than its backing
>> >> + // type (i.e. create an invalid `BitInt`) must be aborted at build time.
>> >> + build_assert!(
>> >> + <$type>::BITS >= $num_bits,
>> >> + "Number of bits requested for representation is larger than backing type."
>> >> + );
>> >> +
>> >> + let shift: u32 = <$type>::BITS - $num_bits;
>> >> + let v = $value;
>> >> +
>> >> + // The value fits within `NUM_BITS` if shifting it left by the number of unused bits, then
>> >> + // right by the same number, doesn't change the value.
>> >> + //
>> >> + // This method has the benefit of working with both unsigned and signed integers.
>> >> + (v << shift) >> shift == v
>> >
>> > In C it doesn't work:
>> >
>> > int c = 0x7fffffff;
>> > printf("%x\t%x\n", c, (c << 1) >> 1); // 7fffffff ffffffff
>> >
>> > Neither in rust:
>> >
>> > let c: i32 = 0x7fffffff;
>> > println!("{} {}", c, (c << 1) >> 1); // 2147483647 -1
>> >
>> > Or I misunderstand something?
>>
>> For a short while I though this was indeed not working, to my despair as
>> this looked like an elegant solution.
>
> No it does not. One suggested by Alice is better because it's more
> straightforward.

The benefit of the shift approach is that it makes it very clear to the
compiler that the MSBs will be unused, opening the way to related
optimizations. I'm worried this would not be carried as clearly if we
rely on value comparisons.

>
>> But then I considered why we are doing that shift by 1 in the first
>> place: that would be because we are intent on using only 31 of the 32
>> bits of the `0x7fffffff` value, in order to encode a signed number.
>>
>> And the positive `0x7fffffff` value cannot be encoded as a signed
>> integer of 31 bits, as after ignoring the MSB the next bit (which would
>> be the sign bit) is `1`. So the post-shift value differs from the
>> original one, and the creation of a `BitInt<i32, 31>` for that value
>> fails, which is working as intended.
>>
>> If OTOH we did the same operation for a `BitInt<u32, 31>`, the
>> non-signed nature of the value would make the shift-and-back operation
>> produce the same value as the initial one - allowing the creation of the
>> `BitInt`, which again is correct because `0x7fffffff` can be
>> represented as an unsigned value using 31 bits.
>>
>> I have tested both cases successfully - so this way of validating still
>> looks correct to me.
>
> I read this carefully more than once, but still can't understand. So
> I gave your macro a try:
>
> macro_rules! fits_within {
> ($value:expr, $BITS:expr, $num_bits:expr) => {{
> let shift: u32 = $BITS - $num_bits;
> let v = $value;
>
> (v << shift) >> shift == v
> }};
> }
>
> fn main() {
> let a: i32 = -1;
> let b: i32 = 0x7fffffff;
>
> println!("{}", fits_within!(a, 32, 31)); // true
> println!("{}", fits_within!(b, 32, 31)); // false
> }
>
> This is exactly opposite to what I naively expect: 32-bit '-1'
> shouldn't fit into 31-bit storage, but 31-bit 0x7fffffff should.

That still looks correct to me, but from your later example I understand
why you think it isn't. Let me explain my reasoning.

For `a`, you want to represent the signed value `-1` using 31 bits.
That's possible (just like you can represent it using 16 or 8 bits), so
`fits_within` succeeds.

For `b`, you want to represent the signed, positive value `0x7fffffff`
using 31 bits. To do that, the MSB or sign bit must be zero, but bit 30
is set to 1 in that value. Thus you need at 32 bits to represent it
properly, and `fits_within` fails.

But from your example below I think your expectation is that we should
consider bit 30 as the sign bit in this case? There could be a case for
doing that, but I think it is also essential that we are able to express
things like "create a 4-bits BitInt with the value -1" simply.

>
> And said aloud, my naive expectation is: fits_withing() must
> return true iff typecasting from one type to another followed
> by typecasting back to the original type would not change the
> value.
>
> Nevermind. Let's consider a more practical example: I read some
> 12-bit ADC with a C function:
>
> int read_my_adc();
>
> It gives me either some 12-bit value, or errno, like -EAGAIN. Let's
> assume my ADC is differential, and bit 11 encodes sign of the output.
> Now, I want to put it into a 12-bit variable. So:
>
> let val = read_my_adc(); // -EAGAIN
> fits_within!(val, i32, 12);
>
> returns true. This is surely not what one would expect.

In Rust `read_my_adc` would return a `Result`, so you cannot pass the
error value to `fits_within` to begin with.

Now if the problem is that `val`'s MSBs are zero and we still want to
interpret it as signed with bit 11 as the signed bit, that's a different
thing (and I better understand the different expectations we have about
`fits_within`). We could either normalize the value before turning it
into a bounded int, or have a dedicated constructor that only considers
the first 12 bits and extends the bit sign as appropriate. Normalizing
is simple ("if bit 11 is set then apply this mask on val"), so I'd
suggest that `read_my_adc` does that (and better, returns a
`Result<BitInt>`).

>
> This is one more example:
>
> let a: i64 = -1i64;
> println!("{}", fits_within!(a, 32, 31));
>
> Here you exceed even the 'backing storage', but still return OK.
>
>> >> + }};
>> >> +}
>> >> +
>> >> +/// Trait for primitive integer types that can be used to back a [`BitInt`].
>> >> +///
>> >> +/// This is mostly used to lock all the operations we need for [`BitInt`] in a single trait.
>> >> +pub trait Boundable
>> >> +where
>> >> + Self: Integer
>> >> + + Sized
>> >> + + Copy
>> >> + + core::ops::Shl<u32, Output = Self>
>> >> + + core::ops::Shr<u32, Output = Self>
>> >> + + core::cmp::PartialEq,
>> >> + Self: TryInto<u8> + TryInto<u16> + TryInto<u32> + TryInto<u64>,
>> >> + Self: TryInto<i8> + TryInto<i16> + TryInto<i32> + TryInto<i64>,
>> >> +{
>> >> + /// Returns `true` if `value` can be represented with at most `NUM_BITS` on `T`.
>> >> + fn fits_within(value: Self, num_bits: u32) -> bool {
>> >> + fits_within!(value, Self, num_bits)
>> >> + }
>> >> +}
>> >> +
>> >> +/// Inplement `Boundable` for all integers types.
>> >> +impl<T> Boundable for T
>> >> +where
>> >> + T: Integer
>> >> + + Sized
>> >> + + Copy
>> >> + + core::ops::Shl<u32, Output = Self>
>> >> + + core::ops::Shr<u32, Output = Self>
>> >> + + core::cmp::PartialEq,
>> >> + Self: TryInto<u8> + TryInto<u16> + TryInto<u32> + TryInto<u64>,
>> >> + Self: TryInto<i8> + TryInto<i16> + TryInto<i32> + TryInto<i64>,
>> >> +{
>> >> +}
>> >> +
>> >> +/// Integer type for which only the bits `0..NUM_BITS` are valid.
>> >> +///
>> >> +/// # Invariants
>> >> +///
>> >> +/// Stored values are represented with at most `NUM_BITS` bits.
>> >> +///
>> >> +/// # Examples
>> >> +///
>> >> +/// ```
>> >> +/// use kernel::num::BitInt;
>> >> +///
>> >> +/// // An unsigned 8-bit integer, of which only the 4 LSBs can ever be set.
>> >> +/// // The value `15` is statically validated to fit within the specified number of bits.
>> >> +/// let v = BitInt::<u8, 4>::new::<15>();
>> >
>> > What for do you make user to declare the storage explicitly? From
>> > end-user perspective, declaring 4-bit variable must imply the most
>> > suitable storage... C version of the same doesn't allow user to select
>> > the storage as well:
>> >
>> > _BitInt(4) x = 8;
>> >
>> > I can't think out any useful usecase for this... I believe that the
>> > optimal storage must be chosen by implementation. And it may even be
>> > different for different arches.
>>
>> Alice provided a good justification in her reply, but let me elaborate a
>> bit more.
>
> This is what Alice said:
>
> It's more complex to not specify the backing storage explicitly, but I
> also think it would be nice to be able to avoid it.
>
> I agree with her. But I don't see any justification here for the
> proposed approach.
>
> TBH, I think it's not too complicated to realize that the best
> backing storage for an N-bit value is 2^(ceil(log(N)))-bit type,
> unless arch specifics comes in play.
>
> I also think that you can bake first version based on 64-bit backing
> storage, regardless of number of bits, so tailoring BitInt() would
> be a future improvement.

I don't think I can explain it better than I already did. If we don't
let users control the size of their values, it will make it very
cumbersome to perform actual work with them.

>
>> C allows itself to implicitly cast values when performing operations.
>> For instance:
>>
>> signed char a = -128;
>> unsigned int b = 120;
>> unsigned short c = b + a;
>>
>> printf("%d\n", c);
>>
>> This absolutely not confusing program is perfectly valid and prints
>> `65528`.
>>
>> For the equivalent code in Rust:
>>
>> let a = -128i8;
>> let b = 120u32;
>> let c: u16 = b + a;
>>
>> I don't even bother printing the result because these 3 lines alone
>> produce 3 build errors. Rust doesn't let you perform operations on
>> primitive integers that are not exactly the same type.
>>
>> So that's the first reason for explicitly passing a type: so you can
>> perform the operations you want with your `BitInt` without jumping
>> through cast hoops. This is particularly important to use it with
>> bitfields, which is the primary goal.
>
> OK, that's really a Rust innovation. So, if we follow the rule, I have
> two and a half considerations:
>
> 1. It also means that BitInt(u8, 4) and BitInt(u8, 5) should be the
> different types, and you shouldn't be able to do arithmetics with them
> even if the backing types match. Can you confirm that?

That's true as of v2. But we could probably make it work, and make the
return type be the backing type. Actually I got the following to work:

let v = BitInt::<u8, 4>::new::<15>();
let u = BitInt::<u8, 5>::new::<30>();

assert_eq!(v + 5, 20);
assert_eq!(v + u, 45);

And I'd say it probably does make sense to support this, since `BitInt`
is really just a transparent shell around a primitive type that
restricts its allowed values. That's all the more reason to specify the
type being wrapped, otherwise you wouldn't be able to e.g. add a
`BitInt<4>` to a `BitInt<17>` as their automatically-infered backing
types would differ.

>
> 2. Later in your patch you allow this:
>
> let v = BitInt::<u32, 4>::new::<15>();
> assert_eq!(v * 10, 150);
>
> This one is really misleading. You allow me to multiply 4-bit number
> by 10, which looks really C-like, and produce an extended result, just
> like C does. But from what you say here, and Miguel in another email,
> it breaks the spirit of Rust types safety.

We don't produce an extended result here. We multiply a u32 with another
u32, and get a u32 as a result. It does make sense when (repeating
myself, but this is the fundamental point) you consider `BitInt` as a
transparent shell around a primitive type that restricts its possible
values.

>
> 2a. Here you allow to do:
>
> let v = BitInt::<i32, 4>::new::<15>();
> let n = -EINVAL;
> assert_eq!(v + n, -7);
>
> And this is not OK. To follow Rust way, you need to convert n to
> BitInt(4), and then it would work as expected - making sure it's
> impossible and throwing an overflow.

Have you tried building this code before telling me it is allowed? How
do you get `EINVAL` as an integer in Rust?

Error codes are their own type, `kernel::error::Error`, so you cannot
even contemplate adding them to an integer.

>
>> Another reason is that even if you don't care about the size of the
>> storage, you should care about its signedness, which is part of the
>> type.
>
> Just invent BitUint or unsigned BitInt, or teach the macro to
> understand BitInt(i12) notation.
>
>> I played a bit with C's `_Bitint`, and managed to produce this
>> wonder:
>>
>> _BitInt(8) v = -1;
>> printf("%d\n", v);
>>
>> This programs prints `255`, even though I used the signed "%d"
>> formatter? Maybe that's because I should make my `_BitInt` explicitly
>> signed?
>>
>> signed _BitInt(8) v = -1;
>> printf("%d\n", v);
>>
>> Nope. Still `255`. Go figure. ¯\_(ツ)_/¯
>
> Clang throws Wformat on this; and it is printf() issue, not the
> _BitInt()s math bug.
>
>> You cannot do that with our implementation. You either specify
>>
>> let v = BitInt::<i8, 8>::new::<-1>();
>>
>> and get a proper, signed `-1` value that prints properly, or do
>>
>> let v = BitInt::<u8, 8>::new::<-1>();
>>
>> and get the build error you should get. No ambiguity, no surprises.
>>
>> >
>> >> +/// assert_eq!(v.get(), 15);
>> >> +///
>> >> +/// let v = BitInt::<i8, 4>::new::<-8>();
>> >> +/// assert_eq!(v.get(), -8);
>> >> +///
>> >> +/// // This doesn't build: a `u8` is smaller than the requested 9 bits.
>> >> +/// // let _ = BitInt::<u8, 9>::new::<10>();
>> >> +///
>> >> +/// // This also doesn't build: the requested value doesn't fit within the requested bits.
>> >> +/// // let _ = BitInt::<i8, 4>::new::<8>();
>> >> +///
>> >> +/// // Values can also be validated at runtime. This succeeds because `15` can be represented
>> >> +/// // with 4 bits.
>> >> +/// assert!(BitInt::<u8, 4>::try_new(15).is_some());
>> >> +/// // This fails because `16` cannot be represented with 4 bits.
>> >> +/// assert!(BitInt::<u8, 4>::try_new(16).is_none());
>> >
>> > Nice! Maybe .is_overflow() instead of .is_none(), so that user will
>> > know that the variable contains truncated value. Just like C does.
>> >
>> > Can you please print the exact error that user will get on compile-
>> > and runtime? How big is the cost of runtime test for overflow? If it
>> > is indeed nonzero, can you consider making the runtime part
>> > configurable?
>>
>> `is_none()` comes from the `Option` type, so we cannot change its name
>> and it's the idiomatic way to do anyway.
>
> I understand. I suggested to implement this .is_overflow(), and have
> .is_none() reserved for cases like assigning floating values to
> unsigned type.

We cannot add a method to `Option`, we would have to implement our own
return type and we are not doing that. Returning an `Option` is the
idiomatic way to do in that case, that's how it is done in the standard
library [1], and everyone a bit familiar with Rust expects this pattern.

[1] https://doc.rust-lang.org/std/num/struct.NonZero.html#method.new

We also don't need to reserve anything for assigning floating values to
unsigned types, since you already get a build error if you try to assign
floating values to unsigned types.

>
>> The runtime cost for overflow is the double-shift and comparison with
>> the initial value.
>
> Are you sure that everyone is OK to pay this runtime cost, especially
> after passing debug phase?

`BitInt` guarantees the following invariant: stored values can be
represented within `N` bits, and the compiler and user can make
optimization decisions based on this invariant.

If you want to create a `BitInt`, you must guarantee that this invariant
is withheld for the value you want to wrap. If you can prove this
statically, you can use `new` or `from_expr` constructors, and there
will be no runtime check and thus no runtime cost.

If you cannot, then you must check the value at runtime - otherwise you
get undefined behavior.

Now we can also add a `new_unchecked` constructor that is marked
`unsafe` and bypass that check altogether if the need arises, but for
now the current family of constructors looks reasonable to me.

>
>> >> +/// // Non-constant expressions can also be validated at build-time thanks to compiler
>> >> +/// // optimizations. This should be used as a last resort though.
>> >> +/// let v = BitInt::<u8, 4>::from_expr(15);
>> >
>> > Not sure I understand that. Can you confirm my understanding?
>> >
>> > 1. For compile-time initialization I use BitInt::<i8, 4>::new::<8>();
>> > 2. For compile- or runtime initialization: BitInt::<i8, 4>::from_expr(val);
>> > 3. For runtime-only initialization: BitInt::<i8, 4>::try_new(val);
>> >
>> > In this scheme #3 looks excessive...
>>
>> This example was not very good. The v2 features a better one:
>>
>> let v = BitInt::<u32, 4>::from_expr(some_number() & 0xf);
>>
>> Here assume that `some_number()` returns a random value. You cannot use
>> the static `new` constructor, as the exact value is not statically
>> known, so the alternative would be to use `try_new` and check for an
>> overflow error you know cannot happen because the value is masked with
>> `0xf` and thus will fit the 4 bits.
>>
>> `from_expr` allows you to create this `BitInt` infallibly, by relying on
>> the compiler being smart enough to infer from the mask operation that
>> the value will indeed satify the constraints of the `BitInt`, and throws
>> a linker error if it couldn't. If the program builds, there is no need
>> for error checking and no runtime validation.
>
> So from_expr() only allows statically true expressions, like this one
>
> some_number() & 0xf < 16.
>
> And try_new() allows true runtime fallible ones.
>
> Looks like OK... But this ::new<8>() syntax really looks overloaded.

That's how Rust deals with constant parameters. FWIW, using
`from_expr(8)` should be strictly equivalent, but the `::<8>` syntax has
the benefit of being usable in `const` context.

>
>> >> +/// // Common operations are supported against the backing type.
>> >> +/// assert_eq!(v + 5, 20);
>> >> +/// assert_eq!(v / 3, 5);
>> >
>> > No, v + 5 == 20 for a different reason. There's nothing about 'backing
>> > storage' here.
>> >
>> > v + 5 should be 20 because addition implies typecasting to the wider
>> > type. In this case, 20 is numeral, or int, and BitInt(4) + int == int.
>> >
>> > I tried C23, and it works exactly like that:
>> >
>> > unsigned _BitInt(4) x = 15;
>> >
>> > printf("%d\n", x + 5); // 20
>> > printf("%d\n", x / 3); // 5
>> > printf("%d\n", x + (unsigned _BitInt(4))5); // 4
>> > x += 5;
>> > printf("%d\n", x); // 4
>> >
>> > Rust _must_ do the same thing to at least be arithmetically
>> > compatible to the big brother.
>>
>> Rust doesn't do implicit casts. I do agree that "backing storage" is not
>> the best choice of words though.
>
> In fact, in "assert_eq!(v + 5, 20)" the '5' is implicitly typecasted
> to the backing storage type.
>
> In other words, Rust doesn't prohibit typecasting. It just typecasts
> to the most restricted type, instead than most relaxed one.
>
>> > It makes me more confident that this 'backing storage' concept
>> > brings nothing but confusion.

`5` is never cast. It is created as the backing storage type of `v` from
the beginning.

>> >
>> >> +/// // The backing type can be changed while preserving the number of bits used for representation.
>> >> +/// assert_eq!(v.cast::<u32>(), BitInt::<u32, 4>::new::<15>());
>> >> +///
>> >> +/// // We can safely extend the number of bits...
>> >> +/// assert_eq!(v.extend::<5>(), BitInt::<u8, 5>::new::<15>());
>> >> +/// // ... but reducing the number of bits fails here as the value doesn't fit anymore.
>> >> +/// assert_eq!(v.try_shrink::<3>(), None);
>> >
>> > Not sure what for you need this. If I need to 'extend', I just assign
>> > the value to a variable:
>> >
>> > BitInt(3) a = 3;
>> > BitInt(10) b;
>> > int c;
>> >
>> > b = a + 123; // extend
>> > c = b; // another extend
>> >
>> > How would this 'extend' and 'shrink' work with arrays of BitInts?
>>
>> I think this discussion would be more productive if we don't rely on
>> examples in a language that is irrelevant for the current patch. :)
>
> The language I rely on is called 'pseudo language', and it is perfectly
> OK as soon as it helps me to describe my intention. If you want me to
> start thinking in Rust, please make it more friendly.

I am doing my best to make my explanations accessible.

To answer your question, your code above would translate to
something like:

let a = BitInt::<i8, 3>::new::<3>();
let b = BitInt::<i16, 10>::from_expr(a.cast::<i16>() + 123i16);

let c: i32 = b.into();

(let `let b` line works because `from_expr` can infer that the BitInt
invariant won't be broken - another way would be to use `try_new` if the
value in `a` was not known at build time).

Regarding arrays of BitInts, I guess you mean BitInts that are larger
than any primitive type? This is out of scope for this implementation.

>
> The following is really a nightmare:
>
> let a = BitInt::<u8, 3>::new::<3>();
> let b = BitInt::<u16, 10>::new::<123>() + BitInt::<u16, 10>::try_from(a);
>
> let c = BitInt::<u32, 32>::try_from(a) + BitInt::<u32, 32>::try_from(b);

It also wouldn't build. Here is the correct version (assuming the `+`
operator improvement discussed above is available):

let a = BitInt::<u8, 3>::new::<3>();
let b = BitInt::<u16, 10>::new::<123>() + a.cast::<u16>();

let c = a.cast::<u32>() + u32::from(b);

Note that `b` and `c` are regular `u16` and `u32`. Arithmetic operations
cannot guarantee that the BitInt invariant will be maintained, so the
result needs to be converted back if that's what one wants.

>
>> Rust does not allow overloading the `=` operator, so these implicit
>> conversions from one type to another cannot be performed. Having
>> dedicated methods is an idiomatic way to do this according to my
>> experience - an alternative would be to have `From` implementations, but
>> doing this elegantly would require one language feature (generic const
>> expressions) that is still not stable.
>>
>> >
>> >> +/// // Conversion into primitive types is dependent on the number of useful bits, not the backing
>> >> +/// // type.
>> >> +/// //
>> >> +/// // Event though its backing type is `u32`, this `BitInt` only uses 8 bits and thus can safely
>> >> +/// // be converted to a `u8`.
>> >> +/// assert_eq!(u8::from(BitInt::<u32, 8>::new::<128>()), 128u8);
>> >
>> > 'Backing type' is useless here too.
>> >
>> >> +/// // The same applies to signed values.
>> >> +/// asserkkt_eq!(i8::from(BitInt::<i32, 8>::new::<127>()), 127i8);
>> >> +///
>> >> +/// // This however is not allowed, as 10 bits won't fit into a `u8` (regardless of the actually
>> >> +/// // contained value).
>> >> +/// // let _ = u8::from(BitInt::<u32, 10>::new::<10>());
>> >
>> > If I explicitly typecast from a wider type, please just let me do
>> > that. In the above examples you show that .is_some() and .is_none()
>> > can help user to check for overflow if needed.
>> >
>> > Otherwise, user will hack your protection by just converting
>> > BitInt(8) to u32, and then to BitInt(10).
>>
>> Doing so would require validating that the value in the `u32` can fit
>> within the 10-bit `BitInt` one way or the other, so the protection
>> cannot be bypassed that way.
>
> That's what I meant. You allow one way to initialize data, but
> disallow another equivalent and more straightforward way.

I cannot make sense of what you want here. Can you write down what you
expect to be possible to do?