Provide a way to perform Add with carry and Subtract with borrow

[Scooletz]

Background and Motivation

The motivation behind this proposal is to provide API that can be useful for adding/subtracting big integers without the need of calculating carry manually. Currently, the only way that I'm aware of .NET uses ADC assembly instruction is an overflow check, followed by a conditional jump to the exception throw. With a proper intrinsics/Math method it could be leveraged to provide a fast add with carry operation. This would be beneficial for BitInteger but also for any other code using this API.

Proposed API

namespace System
{
    public static partial class Math
    {
+         ulong AddWithCarry(ulong a, ulong b, ref ulong carry);
    }
 }

Usage Examples

The immediate beneficent would be BigInteger with methods like

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.AddSub.cs

Lines 75 to 79 in 21a03c3

	for (; i < rightLength; i++)
	{
	long digit = (left[i] + carry) + right[i];
	bits[i] = unchecked((uint)digit);
	carry = digit >> 32;

Risks

The implementation overhead. This would require to go to JIT/intrinsics area and provide a proper fallback, something similar to what was done in Math.BigMul.

Tagging subscribers to this area: @tannergooding, @pgovind
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and Motivation

The motivation behind this proposal is to provide API that can be useful for adding/subtracting big integers without the need of calculating carry manually. Currently, the only way that I'm aware of .NET usesADC assembly instruction is an overflow check. With a proper intrinsics/Math method it could be leveraged to provide a fast add with carry operation. This would be beneficial forBitInteger` but also for any other code using this API.

Proposed API

[tannergooding]

This likely needs more design work and usage samples.

[Scooletz]

@tannergooding Could you clarify whether it's an issue author responsibility, meaning: me, or is it a request for various people to chime in? If the first, I'm not sure if I can provide more. The finding is based on my work in https://github.com/NethermindEth/int256 and my search in the BigInteger area to find how it's done in there. In both cases ADC looked like a good match for carrying over.

[tannergooding]

Its ultimately the area owners (my own and Prashanth's) responsibility to drive this if we feel its worth getting in.

However, interested community members are also free to help out here and to drive much of the design work/addressing feedback/etc. This can sometimes be faster based on what workload we otherwise have.

In the case of this API, I do believe its worth adding and there are corresponding proposals such as #54439 or #46259 that are in a similar vein.

As far as this proposal goes, I think the "design" work that is needed includes:

• Showing what other languages are doing (C/C++, Rust, Java, Go, Swift, etc)
  • e.g. C/C++ expose what is effectively bool addcarry(bool carry, uint a, uint b, out uint result)
  • This will help ensure we are exposing the right shape
• Showing what logic this replaces today
  • e.g. Today you manually track the carry by doing a twice as large addition or comparing the result to the inputs
  • This is displayed, should be broadened a bit to include the carry declaration and ideally to show the replacement code using this API instead
• Sharing how this would impact performance in given workloads
  • IIRC, the simple single case is typically the same, but multiple unrolled adds can be much better

[pentp]

C/C++ exposes it as unsigned char _addcarry_u64(unsigned char, unsigned __int64, unsigned __int64, unsigned __int64 *), but compilers recognize some of the comparison based code patterns also.
Rust exposes it as pub unsafe fn _addcarry_u64(c_in: u8, a: u64, b: u64, out: &mut u64) -> u8
Go exposes it as func Add64(x, y, carry uint64) (sum, carryOut uint64)

Proposed API

namespace System
{
    partial class Math
    {
        public static (uint Sum, bool Carry) AddWithCarry(uint a, uint b, bool carry);
        public static (nuint Sum, bool Carry) AddWithCarry(nuint a, nuint b, bool carry);
        public static (ulong Sum, bool Carry) AddWithCarry(ulong a, ulong b, bool carry);
    }
}

Usage Examples

In decimal.DecCalc.VarDecMul this would be used quite a lot:

// Highest 32 bits is non-zero. Calculate 5 more partial products.
-tmp2 = UInt32x32To64(d1.Low, d2.High);
-tmp += tmp2; // this could generate carry
+(tmp, bool carry) = Math.AddWithCarry(tmp, UInt32x32To64(d1.Low, d2.High), false);
-uint tmp3 = 0;
-if (tmp < tmp2) // detect carry
-    tmp3 = 1;
+uint tmp3 = Convert.ToUInt32(carry);

-tmp2 = UInt32x32To64(d1.High, d2.Low);
-tmp += tmp2; // this could generate carry
+(tmp, carry) = Math.AddWithCarry(tmp, UInt32x32To64(d1.High, d2.Low), false);
bufProd.U2 = (uint)tmp;
-if (tmp < tmp2) // detect carry
-    tmp3++;
+(tmp3, _) = Math.AddWithCarry(tmp3, 0, carry);
-tmp2 = ((ulong)tmp3 << 32) | (tmp >> 32);

-tmp = UInt32x32To64(d1.Mid, d2.High);
-tmp += tmp2; // this could generate carry
+(tmp, carry) = Math.AddWithCarry(((ulong)tmp3 << 32) | (tmp >> 32), UInt32x32To64(d1.Mid, d2.High), false);
-tmp3 = 0;
-if (tmp < tmp2) // detect carry
-    tmp3 = 1;
+tmp3 = Convert.ToUInt32(carry);

-tmp2 = UInt32x32To64(d1.High, d2.Mid);
-tmp += tmp2; // this could generate carry
+(tmp, carry) = Math.AddWithCarry(tmp, UInt32x32To64(d1.High, d2.Mid), false);
bufProd.U3 = (uint)tmp;
-if (tmp < tmp2) // detect carry
-    tmp3++;
+(tmp3, _) = Math.AddWithCarry(tmp3, 0, carry);
tmp = ((ulong)tmp3 << 32) | (tmp >> 32);

bufProd.High64 = UInt32x32To64(d1.High, d2.High) + tmp;
hiProd = 5;

In BigIntegerCalculator.Add(uint[] left, uint right):

uint[] bits = new uint[left.Length + 1];

-long digit = (long)left[0] + right;
-bits[0] = unchecked((uint)digit);
-long carry = digit >> 32;
+(bits[0], bool carry) = Math.AddWithCarry(left[0], right, false);

for (int i = 1; i < left.Length; i++)
{
-    digit = left[i] + carry;
-    bits[i] = unchecked((uint)digit);
-    carry = digit >> 32;
+    (bits[i], carry) = Math.AddWithCarry(left[i], 0, carry);
}
-bits[left.Length] = (uint)carry;
+bits[left.Length] = Convert.ToUInt32(carry);

return bits;

[scottmcm]

Rust exposes it as pub unsafe fn _addcarry_u64(c_in: u8, a: u64, b: u64, out: &mut u64) -> u8

Rust now exposes this in a platform-independent way (not just via arch intrinsics) through u64::carrying_mul_add and friends.