Tracking Issue for bigint helper methods

[clarfonthey]

Feature gate: #![feature(bigint_helper_methods)]

This is a tracking issue for the following methods on integers:

• carrying_add
• borrowing_sub
• carrying_mul
• widening_mul

These methods are intended to help centralise the effort required for creating efficient big integer implementations, by offering a few methods which would otherwise require special compiler intrinsics or custom assembly code in order to do efficiently. They do not alone constitute big integer implementations themselves, but are necessary building blocks for a larger implementation.

Public API

// On unsigned integers:

/// `self + rhs + carry` (full adder)
const fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);

/// `self - rhs - carry` (full "subtractor")
const fn borrowing_sub(self, rhs: Self, carry: bool) -> (Self, bool);

/// `self * rhs + carry` (multiply-accumulate)
const fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);

/// `self * rhs` (wide multiplication, same as `self.carrying_mul(rhs, 0)`)
const fn widening_mul(self, rhs: Self) -> (Self, Self);


// On signed integers:

/// `self + rhs + carry` (full adder)
const fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);

/// `self - rhs - carry` (full "subtractor")
const fn borrowing_sub(self, rhs: Self, carry: bool) -> (Self, bool);

Steps / History

• widening_mul RFC: widening_mul rfcs#2417
• Initial implementation of carrying_add, borrowing_sub, carrying_mul, and widening_mul Add carrying_add, borrowing_sub, widening_mul, carrying_mul methods to integers #85017
• Remove implementations on signed types Remove bigint_helper_methods for *signed* types #90848 per discussion in Signed carry carrying_add in bigint_helper_methods #90541
• Add new carrying_add and borrowing_sub on signed types: Reimplement carrying_add and borrowing_sub for signed integers. #93873
• Add a compiler intrinsic to back bigint_helper_methods #133663
• Add assembly tests to ensure this keeps doing the right thing
• Clarify documentation
  ("without the ability to overflow" can be confusing.)
• Final commenting period (FCP)
• Stabilization PR

Unresolved Questions

• Should these be implemented using compiler intrinsics? LLVM currently has no equivalents, so, we'd have to custom-build some.
• Should an alternative API be provided for widening_mul that simply returns the next-larger type? What would we do for u128/i128?
• What should the behaviour be for signed integers? Should there be implementations for signed integers at all?
• Is the "borrowing" terminology worth it for subtraction, or should we simply call that "carrying" as well for consistency?
• Are there other methods that should be added in addition to the existing ones?

[leonardo-m]

Are there other methods that should be added in addition to the existing ones?

I'd like a mul_mod, as shown in #85017, because I think you can't implement it efficiently without asm and it's a basic block for power_mod and other things.

[clarfonthey]

Another set of methods that could be useful that I'll probably offer implementations for at some point:

/// `(self << rhs) | carry`
fn carrying_shl(self, rhs: u32, carry: Self) -> (Self, Self); 

/// `(self >> rhs) | carry`
fn borrowing_shr(self, rhs: u32, carry: Self) -> (Self, Self);

/// `self << rhs`
fn widening_shl(self, rhs: u32) -> (Self, Self);

/// `self >> rhs`
fn widening_shr(self, rhs: u32) -> (Self, Self);

Essentially, return the two halves of a rotation, i.e. x.widening_shl(y) is the same as (x << y, x >> (BITS - y)) and similarly for widening_shr. Not sure whether they should allow rhs == BITS or not, but presumably they wouldn't for consistency with existing shift methods.

[clarfonthey]

From @scottmcm in the original PR:

Some prior art I happened upon: https://docs.rs/cranelift-codegen/0.74.0/cranelift_codegen/ir/trait.InstBuilder.html#method.isub_bin

Same as isub with an additional borrow flag input. Computes:

   a = x - (y + b_{in}) \pmod 2^B

[photino]

Why don't we add carrying_mul and widening_mul for i128/u128 as well?

[clarfonthey]

Mostly effort implementing them efficiently. In the meantime, you can do it with four calls to the u64 version. Or three if you want to be fancy.

[RalfJung]

fn borrowing_sub(self, rhs: Self, carry: bool) -> (Self, bool);

I was very confused by this function name at first, since borrowing in Rust usually refers to references. I am not a native speaker, but I do formal mathematical work in English professionally, and yet I never before heard the term "borrowing" in the context of subtraction. So I think this, at least, needs some explanation in the docs. (I would have expected something like carrying_sub, but maybe that is nonsense for a native speaker.)

The current docs for some of the other methods could probably also be improved: they talk about not having the "ability to overflow", which makes it sound like not overflowing is a bad thing.

[AaronKutch]

The word borrow here comes from the terminology for a full subtractor. I am thinking that maybe the borrowing_sub function could be removed altogether. The same effect that borrowing_sub has can be obtained from carrying_add by making the first carrying_add in the chain have a set carry bit, and then bitnot every rhs. This fact could be put in the documentation of carrying_add.

[clarfonthey]

The word borrow here comes from the terminology for a full subtractor. I am thinking that maybe the borrowing_sub function could be removed altogether. The same effect that borrowing_sub has can be obtained from carrying_add by making the first carrying_add in the chain have a set carry bit, and then bitnot every rhs. This fact could be put in the documentation of carrying_add.

Considering how the primary goal of these methods is to be as efficient as possible, usually optimising down to a single instruction, I don't think it'd be reasonable to just get rid of subtraction in favour of telling everyone to use addition instead. Definitely open to changing the name, though.

[AaronKutch]

These helper methods will not be very useful to me unless they are implemented for every kind of integer. Here is an implementation for a widening multiplication-addition for u128:

/// Extended multiply-addition of `(lhs * rhs) + add`. The result is returned as a tuple of the wrapping part and the
/// overflow part. No numerical overflow is possible even if all three arguments are set to their max values.
pub const fn widen_mul_add(lhs: u128, rhs: u128, add: u128) -> (u128, u128) {
    //                       [rhs_hi]  [rhs_lo]
    //                       [lhs_hi]  [lhs_lo]
    //                     X___________________
    //                       [------tmp0------]
    //             [------tmp1------]
    //             [------tmp2------]
    //     [------tmp3------]
    //                       [-------add------]
    // +_______________________________________
    //                       [------sum0------]
    //     [------sum1------]

    let lhs_lo = lhs as u64;
    let rhs_lo = rhs as u64;
    let lhs_hi = (lhs.wrapping_shr(64)) as u64;
    let rhs_hi = (rhs.wrapping_shr(64)) as u64;
    let tmp0 = (lhs_lo as u128).wrapping_mul(rhs_lo as u128);
    let tmp1 = (lhs_lo as u128).wrapping_mul(rhs_hi as u128);
    let tmp2 = (lhs_hi as u128).wrapping_mul(rhs_lo as u128);
    let tmp3 = (lhs_hi as u128).wrapping_mul(rhs_hi as u128);
    // tmp1 and tmp2 straddle the boundary. We have to handle three carries
    let (sum0, carry0) = tmp0.overflowing_add(tmp1.wrapping_shl(64));
    let (sum0, carry1) = sum0.overflowing_add(tmp2.wrapping_shl(64));
    let (sum0, carry2) = sum0.overflowing_add(add as u128);
    let sum1 = tmp3
        .wrapping_add(tmp1.wrapping_shr(64))
        .wrapping_add(tmp2.wrapping_shr(64))
        .wrapping_add(carry0 as u128)
        .wrapping_add(carry1 as u128)
        .wrapping_add(carry2 as u128);
    (sum0, sum1)
}

I have tested this with my crate awint.

edit: There is a version of this that uses the Karatsuba trick to use 3 multiplications instead of 4, but it incurs extra summations, branches, and is not as parallel. For typical desktop processors the above should be the fastest.

[clarfonthey]

I would make a PR for that.

[AaronKutch]

Some alternative signatures include u128::widen_mul_add(lhs, rhs, add), lhs.widen_mul_add(rhs, add), or add.widen_mul_add(lhs, rhs). In awint my general purpose mul-add function is mul_add_triop which uses the third signature but takes self mutably and add-assigns lhs * rhs. I'm not sure which is best.

[AaronKutch]

I would also change up the documentation headers for the carrying_add function to say

Extended addition of `self + rhs + carry`. The booleans are interpreted as a single bit
integer of value 0 or 1. If unsigned overflow occurs, then the boolean in the tuple
returns 1. The output carry can be chained into the input carry of another carrying add,
which allows for arbitrarily large additions to be calculated.

I specifically note unsigned overflow, because that happens for both signed and unsigned
integers because of how two's complement works.

[AaronKutch]

borrowing_sub should be left in with its naming, but its documentation could be

Extended subtraction of `self - rhs - borrow`. The "borrowing" here refers to borrowing in the full subtractor sense.
The booleans are interpreted as a single bit integer of value 0 or 1. If unsigned overflow occurs, then the boolean
in the tuple returns 1. The output carry can be chained into the input carry of another borrowing subtract,
which allows for arbitrarily large subtraction to be calculated.

[tspiteri]

I specifically note unsigned overflow, because that happens for both signed and unsigned
integers because of how two's complement works.

But unsigned overflow and signed overflow are different. For example, on x86_64, while unsigned and signed integers share addition and subtraction instructions, unsigned overflow is detected using the carry flag while signed overflow is detected using the overflow flag.

As a concrete example: 127i8 + 1 causes signed overflow but not unsigned overflow. So the carry flag should be false/0.

Edit: I think I had misread your comment and thought the middle part of your comment was the current doc, not your suggestion, so it looks like I completely misinterpreted your final comment.

[AaronKutch]

Yes signed and unsigned overflow are different, but the carrying_add as implemented for unsigned and signed integers both use unsigned overflow because of how two's complement carrying works. Someone using i64::carrying_add might think that the carry out bit follows the bit of i64::overflowing_add when in actuality it is following u64::overflowing_add. So in the documentation I would put emphasis on _unsigned_ overflow.

[clarfonthey]

I think all of these are good suggestions, and like mentioned earlier, these changes definitely should go in a PR if you have the time. I think one important thing to note is that so far the APIs here seem good, but the documentation definitely could use some work. Although if there's a bigger case for changing the subtraction behaviour to be more in line with what's expected (the existing behaviour is mostly modelled after the x86 instructions adc and sbb), then I'm for that.

That said, the main goal is to make it relatively painless to write correct code that compiles down to the right instructions in release mode, so, I would say we should make sure that happens regardless of what's done. I would have added an explicit test for that but I honestly don't know how.

[scottmcm]

@typetetris @nickkuk Your messages made me realize something: the way to justify carrying2_mul is not to talk about it as two carries, but that it's mul_add_carry. Basically, it's what you need for the wide version of z += a * b;. And, conveniently, LLVM already knows that both adds in the wider type can't overflow https://llvm.godbolt.org/z/6r7bxc39E.

If you want to send a PR adding it to nightly, I'm willing to approve it, though it'll need naming feedback from libs-api at some before before it would have a chance at stabilizing. (I could see carrying_mul_add, mul_add_carry, mul_add_with_carry, or more, so pick whatever you think is best justified.)

@clarfonthey We have intrinsics with fallback bodies now, so we can add a poor version in rust in a way that it can be overridden by LLVM (to emit i256 operations like https://llvm.godbolt.org/z/qjfEajb7Y) to let LLVM see it as well as possible but without forcing all the other backends to implement it too.

[clarfonthey]

So, I was looking into this again and wanted to summarise some of the stuff folks have discussed so far, to see what common ground has been established.

Addition methods

So far, we're totally okay with the signatures of the two methods, where T is any integer type:

• addition: (T + T + bool) -> (T, bool)
• subtraction: (T - T - bool) -> (T, bool)

The main issue is naming these methods, and there doesn't seem to be a consensus so far. A few of the options for addition:

• carrying_add (current)
• extending_add
• overflowing_add_carry
• carrying_add_carry
• add_with_carry

And for subtraction:

• borrowing_add (current)
• extending_sub
• overflowing_sub_borrow
• sub_with_carry

One option I particularly like is using the carry terminology for unsigned integers only, and using overflowing instead for signed integers, to indicate that they have different usages. So:

• uN::carrying_add_carry
• uN::carrying_sub_carry
• iN::overflowing_add_carry
• iN::overflowing_sub_carry

Although we definitely need to come up with a name consensus before stabilisation. The shed awaits…

Multiplication methods

These ones have undergone a lot of different discussion. A few notes that folks have added:

1. Less-significant words should always be unsigned. This also helps a bit with return value order since regardless of order, you'll know based upon the type.
2. In addition to unsigned-unsigned and signed-signed multiplication, there should be signed-unsigned as well.
3. There can be up to two carries for multiplication, and people have expressed desire for all combinations (zero carries, one carry, and two carries).
4. There are also requests for mul_mod, which would only have one return value. No one mentioned signed versions, but presumably these would exist.

So, just to fully cover the signatures of these, using not-Rust syntax. Going to use a period for concatenation, and give a temporary name to them to hopefully make sense.

Shorthand	Input Signature	Input Meaning	Output Signature	Output Meaning
unsigned	(x: uN, y: uN)	x * y	(z: uN, w: uN)	(z . w)
unsigned-carry	(x: uN, y: uN, a: uN)	x * y + a	(z: uN, w: uN)	(z . w)
unsigned-carry2	(x: uN, y: uN, a: uN, b: uN)	x * y + a + b	(z: uN, w: uN)	(z . w)
mixed	(x: iN, y: uN)	x * y	(z: iN, w: uN)	(z . w)
mixed-carry	(x: iN, y: uN, a: iN)	x * y + a	(z: iN, w: uN)	(z . w)
mixed-carry2	(x: iN, y: uN, a: iN, b: iN)	x * y + a + b	(z: iN, w: uN)	(z . w)
signed	(x: iN, y: iN)	x * y	(z: iN, w: uN)	(z . w)
signed-carry	(x: iN, y: iN, a: iN)	x * y + a	(z: iN, w: uN)	(z . w)
signed-carry2	(x: iN, y: iN, a: iN, b: iN)	x * y + a + b	(z: iN, w: uN)	(z . w)
unsigned-mod	(x: uN, y: uN, n: uN)	(x * y) % n	z: uN	z
mixed-mod	(x: iN, y: uN, n: iN)	(x * y) % n	z: iN	z
signed-mod	(x: iN, y: iN, n: iN)	(x * y) % n	z: iN	z

Not a whole lot has been done for names. Generally, people think of the two-word versions of multiplication as a "wide mul" or "widening mul" and that's okay. Probably the names carry and carry2 will be what we use for the carrying + double-carrying versions.

Right now, it's unclear whether signed-mod and mixed-mod should have an unsigned or signed modulo, which would affect the final result. It feels reasonable to potentially offer this for greater precision.

Finally, there's the subject of the return value. It seems reasonable to create a struct for this, since otherwise it won't be clear what word is which in most cases.

Right now, only the unsigned is implemented as widening_mul (excluding u128) and unsigned-carry is implemented as carrying_mul (excluding u128 again).

Bit-shift methods

People seemed pretty amenable to adding these, although again, the carry/borrow name is a bit weird. Particularly, (T shift u32) | T -> (T . T) (carrying) and (T shift u32) -> (T . T) (not carrying), where they represent shifts potentially with an or-ed carry.

These aren't on nightly yet.

Conclusions

It seems definitely reasonable to add intrinsics for some of these methods as a good next step, since it's unlikely we'll get the right result without help.

[kennytm]

It seems definitely reasonable to add intrinsics for some of these methods as a good next step, since it's unlikely we'll get the right result without help.

I don't think it's unlikely to get the right result for all of these without intrinsics. The intrinsics are needed to get them right and fast (easy to optimizable).

[clarfonthey]

So, I attempted to start writing some intrinsics for these, but I have not done this before and may have run into the most cursed compiler bug I've ever encountered, and I've also never done this before.

But uh, we'll see what this ends up as later. Figured I'd mention in case anyone else was thinking of trying.

---

In case you're wondering, it's me finding out that LLVM doesn't document any of its methods and secretly makes them all have unknown preconditions that can trigger UB if not properly met. I was getting illegal instructions just randomly in the middle of building my code.

[Rudxain]

Is there a link pointing to some Internals-Forum or Zulip thread for bike-shedding the names?

I'm aware that tracking-issues aren't meant for discussion, that's why I'm asking 😅

[clarfonthey]

No, but you're more than welcome to make one and link it here!

[Rudxain]

Done!

[leb-kuchen]

After looking at the assembly, I say that carrying_add and borrowing_sub are desperately needed. the optimal assembly has an add instruction with a constant of -1, an addc instruction, one of which is a constant, and a set instruction, while the current assembly has two add instructions, two set instructions, and an or instruction.
Then for example, dashu could also use optimal assembly for targets other than x86-64 without much effort.

example::add_with_carry_arch::h46794524507ae557:
        mov     rax, rdi
        add     dl, -1
        adc     rax, rsi
        setb    dl
        ret

example::add_with_carry_helper::h2bc1fa2da7e86911:
        add     rdi, rsi
        setb    cl
        mov     eax, edx
        add     rax, rdi
        setb    dl
        or      dl, cl
        ret

https://godbolt.org/z/roejrjjzz

[TDecking]

It turns out that rustc was able to optimize the current implementation of carrying_add/borrowing_sub perfectly in previous versions,
but it has regressed since. Rust 1.82 added another regression in which the use of these functions inside a standard bignum addition loop
is now worse when compared to a version using architecture instrinsics.

https://godbolt.org/z/hK7M37Y85

[scottmcm]

Opened #133663 to add an intrinsic for wide_mul and carrying_mul, including adding u128 support for both.

[scottmcm]

is now worse when compared to a version using architecture instrinsics.

Replace || with | and it'll work great again: https://godbolt.org/z/sv5xxGTMr

(Classic problem that || is worse because it's control flow.)

Fixed in #133674