IBinaryInteger<BigInteger>.GetShortestBitLength() - int overflow is not handled

[speshuric]

Description

When bit length of BigInteger value is greater than 2^(int.MaxValue+1) - 1, then IBinaryInteger<BigInteger>.GetShortestBitLength() can not return correct result because bit length is more than int.MaxValue.
Now IBinaryInteger<BigInteger>.GetShortestBitLength() returns incorrect negative value.

Reproduction Steps

Code:

using System.Numerics;
var l1 = 42;
var l2 = int.MaxValue;
BigInteger b = (BigInteger.One<<l1)<<l2;
var ll = 1L + l1 + l2;
Console.WriteLine(ll);
var res = ((IBinaryInteger<BigInteger>)b).GetShortestBitLength();
Console.WriteLine(res);

Expected behavior

Exception on GetShortestBitLength call. Result can not be presented in int type.

Actual behavior

output

2147483690
-2147483606

Regression?

No

Known Workarounds

No

Configuration

The latest main branch

Other information

probably from PR #69391
cc @tannergooding

It seems fix is quite trivial, I can do it.

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

When bit length of BigInteger value is greater than 2^int.MaxValue, then IBinaryInteger<BigInteger>.GetShortestBitLength() can not return correct result because bit length is more than int.MaxValue.
Now IBinaryInteger<BigInteger>.GetShortestBitLength() returns incorrect negative value.

Reproduction Steps

Code:

using System.Numerics;
var l1 = 42;
var l2 = int.MaxValue;
BigInteger b = (BigInteger.One<<l1)<<l2;
var ll = 1L + l1 + l2;
Console.WriteLine(ll);
var res = ((IBinaryInteger<BigInteger>)b).GetShortestBitLength();
Console.WriteLine(res);

Expected behavior

Exception on GetShortestBitLength call. Result can not be presented in int type.

Actual behavior

output

2147483690
-2147483606

Regression?

No

Known Workarounds

No

Configuration

The latest main branch

Other information

probably from PR #69391
cc @tannergooding

It seems fix is quite trivial, I can do it.

Author:	speshuric
Assignees:	-
Labels:	area-System.Numerics
Milestone:	-

[tannergooding]

Please feel free to submit a PR, just noting the fix may not be what is expected.

With .NET 7 and the support for generic math BigInteger is not meant to allow more than int.MaxValue bits and it should be treated as a failure to produce such a value.

Such a value is a BigInteger that is roughly 256MB in size and is extremely large for a managed allocation, not only is the processing time significant for something this large, but enough short lived allocations this large can have significant negative impact on the overall application.

Additional 2.14 billion bits is considered "enough" for the purposes of what we provide as it allows values up to ~8.81 * 10^646_456_992. You need:

• 225 bits to uniquely represent every permutation of a standard pack of 52 playing cards
• 266 bits to uniquely address every atom in the observable universe
• 399 bits to represent the lower bound of the game-tree complexity for chess
• 82.5 million bits to represent the largest known prime
• 262 million bits to represent the largest Binary256 (IEEE 754) value
• Even at this boundary, you still have just shy of 2.14 billion bits left to represent other state

[speshuric]

There are some other methods where expressions with _bits.Length do not handle overflow:

• public static BigInteger Log2(BigInteger value) - the same issue (with the same input)
• private int GetGenericMathByteCount() - private, need to check call chains.
• bool IBinaryInteger<BigInteger>.TryWriteBigEndian(Span<byte> destination, out int bytesWritten) - this line looks quite dangerous: ref byte address = ref Unsafe.Add(ref startAddress, (bits.Length - 1) * sizeof(uint));
• public static BigInteger RotateRight(BigInteger value, int rotateAmount) and public static BigInteger RotateLeft(BigInteger value, int rotateAmount) - same line int byteCount = (value._bits is null) ? sizeof(int) : (value._bits.Length * 4);

I think all of them should be checked and fixed if needed.

Question to the team: how to provide tests for such fixes? As I know such tests is too expensive to include them in the main pipeline.

[tannergooding]

I think all of them should be checked and fixed if needed.

Almost all of these should be able to be handled centrally via the internal static int MaxLength property and likely shouldn't need to be handled at each callsite.

At a glance, it looks like the issue is that its doing Array.MaxLength / sizeof(uint) when it should be doing Array.MaxLength / (sizeof(uint) * 8).

The former gives us 0x7FFF_FFC7 / 4 which is 0x1FFF_FFF1 (536_870_897) uints, which is 0x3_FFFF_FE20 (17_179_868_704) bits.

The latter gives us 0x7FFF_FFC7 / 32 which is 0x3FF_FFFE (67_108_762) uints, which is 0x7FFF_FFC0 (2_147_483_584) bits

Question to the team: how to provide tests for such fixes? As I know such tests is too expensive to include them in the main pipeline.

We have a couple of 64-bit only tests, there isn't really a good way to do this outside of manual or outerloop testing due to the memory constrains, however.

[speshuric]

At a glance, it looks like the issue is that its doing Array.MaxLength / sizeof(uint) when it should be doing Array.MaxLength / (sizeof(uint) * 8)

:) Almost the same limits are in JDK BigInteger - max length is limited to 1 << 26

[speshuric]

So, did I understand correctly that it is enough to simply reduce MaxLength and check the relevance of the tests? Can it breaks something existing? I hope no one really use 2GB Bigints :)

[tannergooding]

So, did I understand correctly that it is enough to simply reduce MaxLength and check the relevance of the tests

That'd be my expectation.

Can it breaks something existing? I hope no one really use 2GB Bigints :)

Theoretically someone could "break" in that an allocation that previously would've succeeded now fails. However, in practice this was already "flaky" since it is dependent on the machine having enough memory in the first place.

This was part of the designed and intended changes we made in .NET 7 though, so it is "expected" to be failing and it not doing so is the bug at this point.

[speshuric]

Some random preliminary observations about the case:

• private BigInteger(ReadOnlySpan<uint> value, bool negative) and private BigInteger(Span<uint> value) check MaxLength before "try to conserve". Here can be some edge cases.
• public BigInteger(ReadOnlySpan<byte>, bool, bool) does not checks MaxLength
• There aren't specific tests for MaxLength, but, yes, they can be too expensive for main pipeline.
• operator << does not check MaxLength - looks suspicious.
• operator >> and operator >>> case shift == int.MinValue and some other need to be reviewed for MaxLength
• RotateLeft and RotateRight need to be reviewed for MaxLength
• Some methods (PopCount, TrailingZeroCount and others) now accumulate result internally in (u)longs. Consider to reduce it (if possible).

[speshuric]

I've sent PR with basic implementation discussed before.
Some notes:

• My private tests for large numbers (for GetShortestBitLength, Log2, etc.) are ready, but I'm in doubt where they should be.
• Methods from previous comment still needs to review (type of internal bitcounters etc.). I plan to add such commits to PR, if necessary.
• operator * does not check limits when allocate result buffer (may be it should - review needed)
• long GetBitLength() - now long result is useless but definitely change this not an option (break change in public API). Let it be longer than needed.
• Now the void LargeNegativeBigIntegerShiftTest() tests left shift but is placed in op_rightshift.cs 👎 I can move it if needed.
• Maybe some documentation needs to be updated but I am unfamiliar with this process.