Tracking Issue for signed bigint helper methods

Feature gate: #![feature(signed_bigint_helpers)]

This issue continues discussion #85532 with the following methods on integers:

uN::carrying_mul_add_signed
iN::overflowing_add_carry
iN::overflowing_sub_borrow
iN::carrying_mul
iN::carrying_mul_add
iN::carrying_mul_add_unsigned

impl uN {
    /// `add += self * rhs + carry`, covers full `i2N` range exactly
    fn carrying_mul_add_signed(self, rhs: iN, carry: Self, add: iN) -> (Self, iN);
}

impl iN {
    /// Returns `self + rhs + carry` and (signed) overflow flag;
    /// should be used for most significant limb only; shouldn't be chained
    fn overflowing_add_carry(self, rhs: Self, carry: bool) -> (Self, bool);
    
    /// Returns `self - rhs - borrow` and (signed) overflow flag;
    /// should be used for most significant limb only; shouldn't be chained
    fn overflowing_sub_borrow(self, rhs: Self, borrow: bool) -> (Self, bool);
    
    /// `self * rhs + carry`
    fn carrying_mul(self, rhs: Self, carry: Self) -> (uN, Self);
    
    /// `add += self * rhs + carry`, fits `i2N` range, but doesn't cover it fully
    fn carrying_mul_add(self, rhs: Self, carry: Self, add: Self) -> (uN, Self);
    
    /// `add += self * rhs + carry`, covers full `i2N` range exactly
    fn carrying_mul_add_unsigned(self, rhs: uN, carry: Self, add: uN) -> (uN, Self);
}

@tspiteri

I found that addition of carrying_mul_unsigned_add with carry: uN looks natural.

We want it to be optimized correctly, because as mentioned by @tspiteri and @programmerjake simple

pub fn widemul_u64_i64(a: u64, b: i64) -> i128 {
    (a as i128) * (b as i128)
}

is better for RISC-V: godbolt, but is not enough for good x86_64 assembly and this should be used instead: godbolt.

@tspiteri noted this LLVM mis-optimization some time ago: llvm/llvm-project#57549, but its fix was abandoned.

Its result range is natural: e.g., for base b = 2^64 we have

lower bound -b/2 * (b - 1) - b/2 = -b²/2;
and upper bound (b/2 - 1) * (b - 1) + b/2 - 1 + b - 1 = b²/2 - 1,

which are exactly the bounds of i128 type.

Here is recursive implementation without any other methods: gist.

@scottmcm

I believe that implementing analog of @scottmcm's generic quadratic loop is also possible, but need to compute multiplications in a bit different order and take into account different result types u64 vs i64.

/// Multiply two signed integers, first is `x` has two limbs, second is `y` with three limbs.
pub fn mul_2x3(x: ([u64; 1], i64), y: ([u64; 2], i64)) -> ([u64; 4], i64) {
    let (r0, r1) = u64_carrying_mul_add(x.0[0], y.0[0], 0, 0);
    let (r1, r2) = u64_carrying_mul_add(x.0[0], y.0[1], r1, 0);
    let (r2a, r3a) = u64_carrying_mul_signed_add(x.0[0], y.1, r2, 0);
    let (r1, r2b) = i64_carrying_mul_unsigned_add(x.1, y.0[0], r1, 0);
    let (r2, r3b) = i64_carrying_mul_unsigned_add(x.1, y.0[1], r2a, r2b);
    let (r3, r4) = i64_carrying_mul_add(x.1, y.1, r3a, r3b);
    ([r0, r1, r2, r3], r4)
}

functions

pub fn u64_carrying_mul_add(x: u64, y: u64, z: u64, w: u64) -> (u64, u64) {
    x.carrying_mul_add(y, z, w)
}

pub fn i64_carrying_mul_add(x: i64, y: i64, z: i64, w: i64) -> (u64, i64) {
    let r = i128::from(x)
        .wrapping_mul(i128::from(y))
        .wrapping_add(i128::from(z))
        .wrapping_add(i128::from(w));
    (r as u64, (r >> 64) as i64)
}

pub fn i64_carrying_mul_unsigned_add(x: i64, y: u64, z: u64, w: i64) -> (u64, i64) {
    let y = y.cast_signed();
    // if y has become negative, we need to add 2^64 * x to the answer
    let correction = if y.is_negative() {
        i128::from(x) << 64
    } else {
        0
    };
    let r = i128::from(x)
        .wrapping_mul(i128::from(y))
        .wrapping_add(correction)
        .wrapping_add(i128::from(z))
        .wrapping_add(i128::from(w));
    (r as u64, (r >> 64) as i64)
}

pub fn u64_carrying_mul_signed_add(x: u64, y: i64, z: u64, w: i64) -> (u64, i64) {
    i64_carrying_mul_unsigned_add(y, x, z, w)
}

but is not enough for good x86_64 assembly and this should be used instead: godbolt.

did you actually benchmark them? the "fixed" version looks like it probably has higher latency so could perform worse than the code generated by using i128 multiply.

@programmerjake

@programmerjake yeah, sorry, maybe you are right. Right now I can't get anything useful from my x86_64 with such small test.

Initially I was surprised by 2x amount of mul's when we discussed this for @tspiteri's library here.

Do you think your prediction still correct for i128 widemul for my variant vs current nightly Rust std (i.e. 4 muls vs 8)? https://godbolt.org/z/YfsxcddcW

Do you think your prediction still correct for i128 widemul for my variant vs current nightly Rust std (i.e. 4 muls vs 8)? https://godbolt.org/z/YfsxcddcW

that's enough code that I'm not going to manually calculate instruction dependency chains, sorry. you can try using llvm-mca (in the tools menu) and look at the predicted cycle count, though you do have to make sure the output only has one function (so #[cfg(...)] disable the other) without any branches since llvm-mca will assume all provided assembly is one loop and ignore returns and branches.

If I'm using llvm-mca correctly (directly right in godbolt), then both i64-u64 mul variants for my version returns almost the same

Iterations:        100
Instructions:      6600
Total Cycles:      2217
Total uOps:        8500

Variant with

i128::from(self).wrapping_mul(i128::from(rhs)).wrapping_add(i128::from(carry)).wrapping_add(i128::from(add))

even a bit better by 100 total uOps.

In this case something else is wrong for current nightly Rust i128::carrying_mul_add:

Iterations:        100
Instructions:      8000
Total Cycles:      3019
Total uOps:        10600

In this case something else is wrong for current nightly Rust i128::carrying_mul_add:

Note that that one we emit as just i256 operations to LLVM, see https://rust.godbolt.org/z/4EaYqE4xG

  %0 = sext i128 %a to i256
  %1 = sext i128 %b to i256
  %2 = sext i128 %c1 to i256
  %3 = sext i128 %c2 to i256
  %4 = mul nsw i256 %0, %1
  %5 = add nsw i256 %4, %2
  %6 = add nsw i256 %5, %3
  %7 = trunc i256 %6 to i128
  %8 = lshr i256 %6, 128
  %9 = trunc i256 %8 to i128

So if it's suboptimal, consider filing a bug on LLVM, as the same thing would probably happen with _BitInt(256) in C.

@scottmcm

Also worth pointing out that pretty much all of these methods are done via intrinsics to ensure we can control codegen as much as possible. So, there is always the option of doing that for any new methods that don't perform optimally.

Personally, I think trying to replicate the examples in the docs (which I think were all written by @scottmcm?) for any new methods would be the best way of ensuring that they feel natural to use. Ultimately, the types of operands matters less to the codegen and more toward how people use and understand them, and AFAIK that latter part is what's the biggest struggle at the moment.

Also, if you find any suboptimal codegen and find a way to fix it, be sure to add codegen tests!

Ultimately, the types of operands matters less to the codegen and more toward how people use and understand them, and AFAIK that latter part is what's the biggest struggle at the moment.

Absolutely this. uN::carrying_mul_add turned out really nicely (despite me not liking it at first) in part because it fits the range perfectly. iN::carrying_mul_add doesn't work like that at all, so might be best working materially differently. Similarly I understand what the carry means in uN::carrying_add, but for iN::carrying_add seeing a bool is very non-obvious (to me at least) since adding signed numbers could carry both positively or negatively.

So it needs a holistic story about what these are for and how they should work. We can always tune the implementation details later.

Rollup merge of rust-lang#152018 - clarfonthey:bigint-tracking-issues…

having some kind of 3-valued enum as carry is imo a bad choice since LLVM has no idea what to do with it and generates terrible code

This seems to not be the case, as shown in the code I shared. Since it sees the code as either (unsigned | (signed << 1)) & 1 or (unsigned | (signed << 1)) >> 1, it can simplify to either unsigned or signed in those cases. Definitely would generate atrocious unoptimized code, but at least after optimization it works.

Compare the inner loops, new_add is atrocious by comparison:

new_add:
        ...
.LBB0_3: ; processes 1 byte per loop
        movzx   r10d, byte ptr [rsi + rax]
        movzx   r11d, byte ptr [rcx + rax]
        cmp     r8b, 1
        setne   bl
        mov     r8d, r10d
        add     r8b, r11b
        seto    bpl
        add     r8b, bl
        mov     byte ptr [rsi + rax], r8b
        lea     rax, [rax + 1]
        seto    r9b
        xor     r9b, bpl
        lea     r8d, [r9 + r9]
        add     bl, -1
        adc     r10b, r11b
        adc     r8b, 0
        cmp     rdx, rax
        jne     .LBB0_3
        ...

old_add:
        ...
.LBB1_7: ; processes 2 bytes per loop
        movzx   r11d, byte ptr [rcx + r9 + 1]
        movzx   eax, al
        bt      eax, 0
        adc     byte ptr [rsi + r9 + 1], r11b
        movzx   eax, byte ptr [rcx + r9 + 2]
        adc     byte ptr [rsi + r9 + 2], al
        lea     r9, [r9 + 2]
        setb    al
        cmp     r10, r9
        jne     .LBB1_7
        ...

Okay, that makes sense; I was specifically looking for vectorization in the code but it wasn't vectorization, it's just using bigger adds. That's why it looked like just the same code in the IR with extra branches.

The ternary enum is definitely a no, then, but I'm still wondering the best way to make this work without extra typecasting or special casing inside the loop itself. Maybe it's just not possible.

I'm still wondering the best way to make this work without extra typecasting or special casing inside the loop itself.

I think here is quite funny implementation of twos complement big int addition without mentioning of iN at all. Just using potentially infinite sign extension.

type Limb = u8;

#[derive(Clone, Debug)]
pub struct BigInt {
    limbs: Vec<Limb>,
}

impl BigInt {
    fn limb(&self, index: usize) -> Limb {
        if index < self.limbs.len() {
            self.limbs[index]
        } else if self
            .limbs
            .last()
            .is_some_and(|msl| msl.cast_signed().is_negative())
        {
            Limb::MAX
        } else {
            0
        }
    }
}

impl core::ops::Add<&BigInt> for &BigInt {
    type Output = BigInt;
    fn add(self, rhs: &BigInt) -> BigInt {
        let result_size = self.limbs.len().max(rhs.limbs.len()) + 1;
        let mut result = BigInt {
            limbs: Vec::with_capacity(result_size),
        };
        let mut carry = false;
        for i in 0..result_size {
            let r;
            (r, carry) = self.limb(i).carrying_add(rhs.limb(i), carry);
            result.limbs.push(r);
        }
        result
    }
}

@programmerjake

Here is an implementation with methods @programmerjake suggested. It is almost the same as previous, but its result is a bit more normalized, i.e. creates new limb only when overflow occurs. Also uses #152179 to determine which limb to add.

type Limb = i8;

#[derive(Clone, Debug)]
pub struct BigInt {
    limbs: Vec<Limb>,
}

impl BigInt {
    fn limb(&self, index: usize) -> Limb {
        if index < self.limbs.len() {
            self.limbs[index]
        } else if self.limbs.last().is_some_and(|msl| msl.is_negative()) {
            -1
        } else {
            0
        }
    }
}

/// Addition x + y + carry with possible unsinged carry as output.
fn carrying_add(x: Limb, y: Limb, carry: bool) -> (Limb, bool) {
    let (z, c) = x.cast_unsigned().carrying_add(y.cast_unsigned(), carry);
    (z.cast_signed(), c)
}

/// Addition x + y + carry with possible signed overflow output.
fn overflowing_add_carry(x: Limb, y: Limb, carry: bool) -> (Limb, bool) {
    let (a, b) = x.overflowing_add(y);
    let (c, d) = a.overflowing_add(carry as Limb);
    (c, b != d)
}

impl core::ops::Add<&BigInt> for &BigInt {
    type Output = BigInt;
    fn add(self, rhs: &BigInt) -> BigInt {
        let result_size = self.limbs.len().max(rhs.limbs.len()) + 1;
        let last_limb_index = result_size.saturating_sub(2);
        let mut result = BigInt {
            limbs: Vec::with_capacity(result_size),
        };
        let mut carry = false;
        for i in 0..last_limb_index {
            let r;
            (r, carry) = carrying_add(self.limb(i), rhs.limb(i), carry);
            result.limbs.push(r);
        }
        let (r, overflow) =
            overflowing_add_carry(self.limb(last_limb_index), rhs.limb(last_limb_index), carry);
        result.limbs.push(r);
        if overflow {
            if r < 0 {
                result.limbs.push(0);
            } else {
                result.limbs.push(-1);
            }
        }
        result
    }
}

I guess it might be worth asking whether slice-based versions of these primitives should be offered if the API is weird and sensitive to how exactly you order the operations. We'd still need to have separate ternary and binary versions (x = y + z vs. x += y) but this would be similar to how we already need two versions of methods for mutable/immutable slices in most cases anyway.

and reverse binary x = y - x

TBH I'd use overflowing_add_carry when you want to know if a fixed-size big integer add overflowed, if you want to auto-resize I think carrying_add is still better:

/// twos complement little-endian big integer
struct BigInt(Vec<u64>); // why was everyone using u8/i8, it's so inefficient...

impl BigInt {
    fn sign_extend_word(&self) -> u64 {
        (self.0.last().unwrap_or(0).cast_signed() >> 63).cast_unsigned()
    }
}

impl<'a> Add<&'a BigInt> for &'_ BigInt {
    type Output = BigInt;
    fn add(self, other: &'a BigInt) -> Self::Output {
        let mut short = self;
        let mut long = other;
        if short.len() > long.len() {
            (short, long) = (long, short);
        }
        let mut carry = false;
        let mut retval = Self(Vec::with_capacity(long.len() + 1));
        for i in 0..short.len() {
            let sum;
            (sum, carry) = short[i].carrying_add(long[i], carry);
            retval.0.push(sum);
        }
        let short_sign = short.sign_extend_word();
        for i in short.len()..long.len() {
            let sum;
            (sum, carry) = short_sign.carrying_add(long[i], carry);
            retval.0.push(sum);
        }
        let long_sign = long.sign_extend_word();
        let sum;
        (sum, carry) = short_sign.carrying_add(long_sign, carry);
        retval.0.push(sum);
        while let [.., second_to_last, last] = *retval.0 {
            if (second_to_last.cast_signed() >> 63).cast_unsigned() == last {
                retval.0.pop();
            } else {
                break;
            }
        }
        retval
    }
}

I guess it might be worth asking whether slice-based versions of these primitives should be offered

I believe strongly that at minimum they should be a separate ACP and a separate tracking issue. To me the point of these is just to be building-blocks that ecosystem crates can combine into slice versions or Vec<Limb> versions or whatever.

Maybe this is more an LLVM question than a rustc question, but I see rather poor codegen with the current implementation of i64::carrying_add on x86: https://godbolt.org/z/4P5eMT4PE

I was expecting to see a chain of add, adc, ... adc, and then a single seto at the end. Instead, the last adc is manually unwrapped into a series of flag manipulation and adds equivalent to the naive implementation.
Also, if you switch the target-cpu in the example from zen3 to zen4, notice how it baloons to over double the instructions.

Rollup merge of #152179 - nickkuk:overflow-direction-note, r=jhpratt

I was asked to post this example here to contribute to the bikeshedding. In this implementation of "i16" in terms of (i8, u8), I believe as intended by the bignum helpers, the namings of the functions produce unfortunately counterintuitive source code:

#![feature(signed_bigint_helpers)]

#[derive(PartialEq, Eq, Clone, Copy)]
struct I16 {
    hi: i8,
    lo: u8,
}

impl I16 {
    fn overflowing_add(self, other: Self) -> (Self, bool) {
        let (lo, carry_out) = u8::overflowing_add(self.lo, other.lo);
        let (hi, overflow_out) = i8::carrying_add(self.hi, other.hi, carry_out);
        (I16 { hi, lo }, overflow_out)
    }
}

test

impl I16 {
    fn pack(self) -> i16 {
        (i16::from(self.hi) << 8) | i16::from(self.lo)
    }
}

#[test]
fn test() {
    for ah in i8::MIN..=i8::MAX {
        for al in u8::MIN..=u8::MAX {
            for bh in i8::MIN..=i8::MAX {
                for bl in u8::MIN..=u8::MAX {
                    let a = I16 { hi: ah, lo: al };
                    let b = I16 { hi: bh, lo: bl };
                    let (aplusb, overflow) = a.overflowing_add(b);
                    assert_eq!(
                        a.pack().overflowing_add(b.pack()),
                        (aplusb.pack(), overflow)
                    )
                }
            }
        }
    }
}

Notably, you get the carry from u8::overflowing_add, and get the overflow from i8::carrying_add.

If i8::carrying_add was actually named i8::overflowing_add_carry there would be less confusion, but at least I don't think these are confusable with each other.

The main thing to me is that it is very unintuitive if you already have an expectation of what "carry" and "overflow" mean, but it feels like an intentional break from convention for me. I was nevertheless asked to post this here so here you go.

The main thing to me is that it is very unintuitive if you already have an expectation of what "carry" and "overflow" mean

I wanted to second this and add a couple of references from ISA manuals.

Reference 1: Armv6-M

Source: DDI0491E page A2-33

Convention: C flag, "carry", is a carry-out from the MSB (aka unsigned wrapping). V flag, "overflow", is a sign change caused by an unrepresentable result (signed overflow).

Reference 2: x86_64

Source: SDM volume 1 page 3-16

Convention: same as Arm, except C flag is inverted for subtraction. This definition makes it so that e.g. -(0u32) is not considered to wrap, which many people find more intuitive even though the two's-complement negation of zero is adding one to all-ones.

The main sources of confusion for me were:

overflow usually being something signed integers (and, entirely separately, IEEE 754 floats) do,
carry-out usually being something all integers do, with a signedness-invariant definition,
wrapping usually being the thing unsigned integers do when they generate a carry-out (possibly inverted for subtraction and negation).

Here are some of the distinct meanings of overflow I inferred from the examples in the docs. These are places the word "overflow" is used in the doc description, not necessarily the function name:

Function	Overflow on...	Common term(s)
`i32::carrying_add`	Unbounded-precision result isn't representable in target type	Overflow
`i32::overflowing_add`	Unbounded-precision result isn't representable in target type	Overflow
`u32::overflowing_add`	Unbounded-precision result isn't representable in target type	Carry-out
`i32::overflowing_neg`	Unbounded-precision result isn't representable in target type (only `::MIN`)	Overflow
`u32::overflowing_neg`	Unbounded-precision result is representable in target type (expressed in two's complement identity: only `0u32` has carry-out)	Borrow, !Carry
`i32::overflowing_shl`	Unsigned wrapping of `rhs`, independent of whether shift result is representable.	None
`i32::overflowing_mul`	Unbounded-precision result isn't representable in target type	Overflow
`u32::overflowing_mul`	Unbounded-precision result isn't representable in target type	Carry-out
`i32::carrying_mul_add`	Result is always representable; uses the term "overflow" for the high half of the result	-

The main sources of confusion for me were:

overflow usually being something signed integers (and, entirely separately, IEEE 754 floats) do,

unsigned integers can overflow too.

carry-out usually being something all integers do, with a signedness-invariant definition,

I think of carry out as specifically limited to an additional output of some arithmetic operation that allows propagating to the next higher word when doing multi-word arithmetic. so generally carry out only happens from addition/subtraction as a 1-bit value, and from multiplication as a full word value. for multiplication I don't consider a did-overflow flag as a carry out since that isn't enough information to distinguish 0x10u8 * 0x10 vs. 0x80u8 * 0x10 -- those have different carry outputs.

wrapping usually being the thing unsigned integers do when they generate a carry-out (possibly inverted for subtraction and negation).

to me wrapping is something all integers do, signed integers wrap too (e.g. 1000i32 as i8 wraps to -24i8 because 1000i32.rem_euclid(0x100) == (-24i32).rem_euclid(0x100)).

Navigation Menu

Repository navigation

Tracking Issue for signed bigint helper methods #151989

19 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Tracking Issue for signed bigint helper methods #151989

Description

Activity

nickkuk commented on Feb 2, 2026

nickkuk commented on Feb 2, 2026

Krishna-js45 commented on Feb 2, 2026

programmerjake commented on Feb 2, 2026

nickkuk commented on Feb 2, 2026

programmerjake commented on Feb 2, 2026

nickkuk commented on Feb 2, 2026

scottmcm commented on Feb 2, 2026

clarfonthey commented on Feb 2, 2026

scottmcm commented on Feb 2, 2026

19 remaining items

programmerjake commented on Mar 2, 2026

clarfonthey commented on Mar 2, 2026

nickkuk commented on Mar 2, 2026

nickkuk commented on Mar 3, 2026

clarfonthey commented on Mar 4, 2026

programmerjake commented on Mar 4, 2026

programmerjake commented on Mar 4, 2026

scottmcm commented on Mar 5, 2026

andrepd commented on Mar 10, 2026

dramforever commented on Jul 23, 2026

Wren6991 commented on Jul 23, 2026

programmerjake commented on Jul 23, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions