Repository: rust
Issue: Tracking Issue for bigint helper methods
Labels: T-libs-api,C-tracking-issue

<!--
Thank you for creating a tracking issue!

Tracking issues are for tracking a feature from implementation to stabilization.

Make sure to include the relevant RFC for the feature if it has one.

If the new feature is small, it may be fine to skip the RFC process. In that
case, you can use use `issue = "none"` in your initial implementation PR. The
reviewer will ask you to open a tracking issue if they agree your feature can be
added without an RFC.
-->

Feature gate: `#![feature(bigint_helper_methods)]`

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

* `carrying_add`
* `borrowing_sub`
* `carrying_mul`
* `carrying_mul_add`
* `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


```rust
// 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 + carry` (multiply-accumulate-carry)
const fn carrying_mul_add(self, rhs: Self, addend: 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

<!--
For larger features, more steps might be involved.
If the feature is changed later, please add those PRs here as well.
-->

- [x] `widening_mul` RFC: rust-lang/rfcs#2417
- [x] Initial implementation of `carrying_add`, `borrowing_sub`, `carrying_mul`, and `widening_mul` #85017
- [x] Remove implementations on signed types #90848 per discussion in #90541 
- [x] Add new `carrying_add` and `borrowing_sub` on signed types: https://github.com/rust-lang/rust/pull/93873
- [x] #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

<!--
Once the feature has gone through a few release cycles and there are no
unresolved questions left, the feature might be ready for stabilization.

If this feature didn't go through the RFC process, a final commenting period
(FCP) is always needed before stabilization. This works as follows:

A library team member can kick off the stabilization process, at which point
the rfcbot will ask all the team members to verify they agree with
stabilization. Once enough members agree and there are no concerns, the final
commenting period begins: this issue will be marked as such and will be listed
in the next This Week in Rust newsletter. If no blocking concerns are raised in
that period of 10 days, a stabilzation PR can be opened by anyone.
-->

### Unresolved Questions

- [x] Should these be implemented using compiler intrinsics? LLVM currently has no equivalents, so, we'd have to custom-build some.
  - Done in #133663
- 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?