UInt128 division broken on big-endian platforms

[uweigand]

Description

The software 128-bit division algorithm added in #69204 (@tannergooding @bartonjs) does not work correctly on big-endian platforms, leading to failed assertions when running the test suite on s390x.

Reproduction Steps

Run the System.Tests.Int128Tests_GenericMath.op_DivisionTest test on linux-s390x.

Expected behavior

Test passes.

Actual behavior

Unhandled Exception:
System.Diagnostics.DebugProvider+DebugAssertException:    at System.Diagnostics.DebugProvider.Fail(String message, String detailMessage) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/DebugProvider.cs:line 22
   at System.Diagnostics.Debug.Fail(String message, String detailMessage) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Debug.cs:line 133
   at System.Diagnostics.Debug.Assert(Boolean condition, String message, String detailMessage) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Debug.cs:line 97
   at System.Diagnostics.Debug.Assert(Boolean condition) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Debug.cs:line 82
   at System.Number.UInt128ToDecStr(UInt128 value) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs:line 2236
   at System.Number.UInt128ToDecStr(UInt128 value, Int32 digits) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs:line 2244
   at System.Number.FormatInt128(Int128 value, String format, IFormatProvider provider) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs:line 1179
   at System.Int128.ToString(String format, IFormatProvider provider) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Int128.cs:line 111
   at System.Convert.ToString(Object value, IFormatProvider provider) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Convert.cs:line 1941
   at Xunit.Sdk.ArgumentFormatter.Format(Object value, Int32 depth, Nullable`1& pointerPostion, Nullable`1 errorIndex, Boolean isDictionaryEntry) in /_/src/xunit.assert/Asserts/Sdk/ArgumentFormatter.cs:line 187
   at Xunit.Sdk.ArgumentFormatter.Format(Object value, Nullable`1 errorIndex) in /_/src/xunit.assert/Asserts/Sdk/ArgumentFormatter.cs:line 79
   at Xunit.Sdk.AssertActualExpectedException.ConvertToString(Object value) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/AssertActualExpectedException.cs:line 176
   at Xunit.Sdk.AssertActualExpectedException..ctor(Object expected, Object actual, String userMessage, String expectedTitle, String actualTitle, Exception innerException) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/AssertActualExpectedException.cs:line 79
   at Xunit.Sdk.AssertActualExpectedException..ctor(Object expected, Object actual, String userMessage, String expectedTitle, String actualTitle) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/AssertActualExpectedException.cs:line 48
   at Xunit.Sdk.EqualException..ctor(Object expected, Object actual) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/EqualException.cs:line 47
   at Xunit.Assert.Equal[Int128](Int128 expected, Int128 actual, IEqualityComparer`1 comparer) in /_/src/xunit.assert/Asserts/EqualityAsserts.cs:line 101
   at Xunit.Assert.Equal[Int128](Int128 expected, Int128 actual) in /_/src/xunit.assert/Asserts/EqualityAsserts.cs:line 63
   at System.Tests.Int128Tests_GenericMath.op_DivisionTest() in /home/uweigand/runtime/src/libraries/System.Runtime/tests/System/Int128Tests.GenericMath.cs:line 389

Regression?

Newly added test case now causes the test suite to fail.

Known Workarounds

n/a

Configuration

Current runtime sources, on linux-s390x.

Other information

From an initial investigation, it appears the problem is located in DivideSlow (in src/libraries/System.Private.CoreLib/src/System/UInt128.cs:1038:

                // This is the same algorithm currently used by BigInteger so
                // we need to get a Span<uint> containing the value represented
                // in the least number of elements possible.

                uint* pLeft = stackalloc uint[Size / sizeof(uint)];
                quotient.WriteLittleEndianUnsafe(new Span<byte>(pLeft, Size));
                Span<uint> left = new Span<uint>(pLeft, (Size / sizeof(uint)) - (BitOperations.LeadingZeroCount(quotient) / 32));

                uint* pRight = stackalloc uint[Size / sizeof(uint)];
                divisor.WriteLittleEndianUnsafe(new Span<byte>(pRight, Size));
                Span<uint> right = new Span<uint>(pRight, (Size / sizeof(uint)) - (BitOperations.LeadingZeroCount(divisor) / 32));

WriteLittleEndianUnsafe writes out the 128-bit integer as a little-endian byte sequence. That sequence of bytes is then re-interpreted as an array of uint. This is only correct on systems where uint is little-endian.

[dotnet-issue-labeler]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[ghost]

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

Issue Details

---

Description

The software 128-bit division algorithm added in #69204 (@tannergooding @bartonjs) does not work correctly on big-endian platforms, leading to failed assertions when running the test suite on s390x.

Reproduction Steps

Run the System.Tests.Int128Tests_GenericMath.op_DivisionTest test on linux-s390x.

Expected behavior

Test passes.

Actual behavior

Unhandled Exception:
System.Diagnostics.DebugProvider+DebugAssertException:    at System.Diagnostics.DebugProvider.Fail(String message, String detailMessage) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/DebugProvider.cs:line 22
   at System.Diagnostics.Debug.Fail(String message, String detailMessage) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Debug.cs:line 133
   at System.Diagnostics.Debug.Assert(Boolean condition, String message, String detailMessage) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Debug.cs:line 97
   at System.Diagnostics.Debug.Assert(Boolean condition) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Debug.cs:line 82
   at System.Number.UInt128ToDecStr(UInt128 value) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs:line 2236
   at System.Number.UInt128ToDecStr(UInt128 value, Int32 digits) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs:line 2244
   at System.Number.FormatInt128(Int128 value, String format, IFormatProvider provider) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Number.Formatting.cs:line 1179
   at System.Int128.ToString(String format, IFormatProvider provider) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Int128.cs:line 111
   at System.Convert.ToString(Object value, IFormatProvider provider) in /home/uweigand/runtime/src/libraries/System.Private.CoreLib/src/System/Convert.cs:line 1941
   at Xunit.Sdk.ArgumentFormatter.Format(Object value, Int32 depth, Nullable`1& pointerPostion, Nullable`1 errorIndex, Boolean isDictionaryEntry) in /_/src/xunit.assert/Asserts/Sdk/ArgumentFormatter.cs:line 187
   at Xunit.Sdk.ArgumentFormatter.Format(Object value, Nullable`1 errorIndex) in /_/src/xunit.assert/Asserts/Sdk/ArgumentFormatter.cs:line 79
   at Xunit.Sdk.AssertActualExpectedException.ConvertToString(Object value) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/AssertActualExpectedException.cs:line 176
   at Xunit.Sdk.AssertActualExpectedException..ctor(Object expected, Object actual, String userMessage, String expectedTitle, String actualTitle, Exception innerException) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/AssertActualExpectedException.cs:line 79
   at Xunit.Sdk.AssertActualExpectedException..ctor(Object expected, Object actual, String userMessage, String expectedTitle, String actualTitle) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/AssertActualExpectedException.cs:line 48
   at Xunit.Sdk.EqualException..ctor(Object expected, Object actual) in /_/src/xunit.assert/Asserts/Sdk/Exceptions/EqualException.cs:line 47
   at Xunit.Assert.Equal[Int128](Int128 expected, Int128 actual, IEqualityComparer`1 comparer) in /_/src/xunit.assert/Asserts/EqualityAsserts.cs:line 101
   at Xunit.Assert.Equal[Int128](Int128 expected, Int128 actual) in /_/src/xunit.assert/Asserts/EqualityAsserts.cs:line 63
   at System.Tests.Int128Tests_GenericMath.op_DivisionTest() in /home/uweigand/runtime/src/libraries/System.Runtime/tests/System/Int128Tests.GenericMath.cs:line 389

Regression?

Newly added test case now causes the test suite to fail.

Known Workarounds

n/a

Configuration

Current runtime sources, on linux-s390x.

Other information

From an initial investigation, it appears the problem is located in DivideSlow (in src/libraries/System.Private.CoreLib/src/System/UInt128.cs:1038:

                // This is the same algorithm currently used by BigInteger so
                // we need to get a Span<uint> containing the value represented
                // in the least number of elements possible.

                uint* pLeft = stackalloc uint[Size / sizeof(uint)];
                quotient.WriteLittleEndianUnsafe(new Span<byte>(pLeft, Size));
                Span<uint> left = new Span<uint>(pLeft, (Size / sizeof(uint)) - (BitOperations.LeadingZeroCount(quotient) / 32));

                uint* pRight = stackalloc uint[Size / sizeof(uint)];
                divisor.WriteLittleEndianUnsafe(new Span<byte>(pRight, Size));
                Span<uint> right = new Span<uint>(pRight, (Size / sizeof(uint)) - (BitOperations.LeadingZeroCount(divisor) / 32));

WriteLittleEndianUnsafe writes out the 128-bit integer as a little-endian byte sequence. That sequence of bytes is then re-interpreted as an array of uint. This is only correct on systems where uint is little-endian.

Author:	uweigand
Assignees:	-
Labels:	area-System.Numerics, untriaged
Milestone:	-

[tannergooding]

Have a PR up (#71162). Sorry for the breakage.

[uweigand]

Thanks for the quick fix, @tannergooding ! The test now passes again (unfortunately another regression came in at the same time so CI still isn't green, but that's unrelated ...)

While there seem to be no more int128-related test suite failures, I noticed this comment in the source that is confusing to me:

        // Unix System V ABI actually requires this to be little endian
        // order and not `upper, lower` on big endian systems.

        private readonly ulong _lower;
        private readonly ulong _upper;

Not sure why the System V ABI is called out here, but I do not believe this statement to be correct. Is the intent that this data structure is compatible with a native __int128 type, as far as the calling convention (or at least in-memory layout) is concerned? If so, then this isn't true for the 64-bit big-endian platforms I'm aware of, certainly not for s390x (or big-endian ppc64).

On s390x, the native __int128 type is fully big-endian, i.e. the first byte in memory is the most significant of all the 16 bytes. This would not be compatible with the memory layout of the C# Int128 struct as defined above.

[tannergooding]

Not sure why the System V ABI is called out here, but I do not believe this statement to be correct.

System V is the default Unix ABI for most platforms. All of the System V ABI docs I've checked explicitly state:

The __int128 type is stored in little-endian order in memory, i.e., the 64 low-order bits are stored at a a lower address than the 64 high-order bits.

and

For classification purposes __int128 is treated as if it were implemented
as: typedef struct { long low, high; } __int128;

Notably I don't see that in the s390x-abi doc I found here: https://github.com/IBM/s390x-abi/blob/main/lzsabi.tex. It unfortunately makes no comment on the layout of the data...

Is the intent that this data structure is compatible with a native __int128 type, as far as the calling convention (or at least in-memory layout) is concerned?

Yes and we have interop tests that are meant to validate this. I wonder if they are not running on s390x.

[tannergooding]

Ah right, they are all disabled on Mono: #69531

If you can open another issue tracking this, I can work on changing it. The following godbolt link shows the ordering difference for s390x: https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIApACYAQuYukl9ZATwDKjdAGFUtAK4sGIM9KuADJ4DJgAcj4ARpjEEhqkAA6oCoRODB7evv7SyamOAiFhkSwxcVwJdpgO6UIETMQEmT5%2BAbaY9gUMdQ0ERRHRsfG29Y3N2W0Ko32hA6VDFQCUtqhexMjsHOYAzKHI3lgA1CbbblP4ggB0CCfYJhoAgvcPXqEEAGySAPoEhwCyXAgXgYqWAYXQhy%2BXzeXDMAA4AFSHVSLZ4mADsVkehxxh2ImAIawYhyBb0%2BP0WEARKJOWKe6IAImjHq9BOTfn8zECQXgwZgIVCYfCkTTHhi6bi8QSiSTWR9vgRKdTjts7qrDp9Uds6RiGRxlrROABWXh%2BDhaUioThuazWQ4KVbrTDHMzbHikAiafXLADWIG220uAeDIdD730nEkpq9ls4vAUIASnvN%2BtIcFgSDQLESdFi5EoWZz9DiwGQyAU2wAnBpVFxYQkaLQCLEExAojGoqEGgBPTjurNsQQAeQYtF7KdIWBYhmA4gn%2BHxNQAbpgExPMKpql5m33eG8OjHaHgosQex4sDGCMQ8Cxd8sqAZgAoAGp4TAAdyHiUYu5kghEYjsFIf7yEoagxroXD6DOKC2pY%2BjHgmkDLKgiRdGuAC0Q7bPGHTVF0LgMO4ngtHowSzCUZR6HkaQCOMfhQTRXT9JRCztJ0tTTPRehVDUAg9I0LGDOUIy9NxUFTL0QnzOUywOmsGx6FemCbDwBrGtGE5WhwFbVqohylsghx1pcZiXBoJI2pY1ikIcuCECQLpurZHjZrmxBOVwiy8MmWiLL6/qBqGwXBuGhocFGpBmha2nxomHpess6aICgqBucW%2BYQIW7kgMAdZmHwdDNsQrbthOnbMMQ479mlg4ECOY4xlOM5zhaC74XgK5rhaG5bju3B7oIB4TkeJ5nhgmwWleN53nwj4vm%2Bn7fma7r8P%2BojiMBa2gSo6gTroBUGEYsHWfBo1IRAKFoekmHYbhHHOBArjiaQ5HFMJ1EpLRGQkdkjFfcxFEfRJeF8d0XG/Qx7Edfx0zSVREkQ1kUOSYJQMyRIcmOopUHKapqbhSaUUxtpqhwu8GGfAZZbGVwpmWXBNh2fgRAeTsUGHK5RaxE5ZjeQlKb%2BaQfoBkGIXBRGEWaTFca2PFvnepLZjS7wsUC35ywriV6QgJIQA%3D%3D

[tannergooding]

PR here: #71211

[uweigand]

Not sure why the System V ABI is called out here, but I do not believe this statement to be correct.

System V is the default Unix ABI for most platforms. All of the System V ABI docs I've checked explicitly state:

The __int128 type is stored in little-endian order in memory, i.e., the 64 low-order bits are stored at a a lower address than the 64 high-order bits.

and

For classification purposes __int128 is treated as if it were implemented
as: typedef struct { long low, high; } __int128;

Well, those would presumably be ABI documents for little-endian platforms, where this would be correct.

Notably I don't see that in the s390x-abi doc I found here: https://github.com/IBM/s390x-abi/blob/main/lzsabi.tex. It unfortunately makes no comment on the layout of the data...

That's the correct document. The pdf version may be easier to read: https://github.com/IBM/s390x-abi/releases/download/v1.6/lzsabi_s390x.pdf

Figure 1.4 (on page 10) of that document shows the layout of the 128-bit (quadword) type.

For PowerPC64, both little- and big-endian versions of the ABI are defined by the same document, which can be downloaded from here: https://openpowerfoundation.org/specifications/64bitelfabi/

The layout of the big-endian version of __int128 on PowerPC64 is defined in Table 2.10 there, and it is likewise fully big-endian (MSB is byte 0).

I'll open another issue shortly.

[tannergooding]

The layout of the big-endian version of __int128 on PowerPC64 is defined in Table 2.10 there, and it is likewise fully big-endian (MSB is byte 0).

I see its inverse in 2.5 (little-endian bit and byte numbering in quadwords) and so expectations look to be "little-endian in little-endian" and "big-endian in big-endian" so that keeps this simple.

👍

I'll open another issue shortly.

Thanks!