chfast/intx

Extended precision integer C++ library

intx's Issues

Implement is_constant_evaluated

The std::is_constant_evaluated has been introduced in C++20. It is useful for having simple API with different paths for constexpr and fast runtime (using intrinsics or inline asm).

It can be easily implemented with __builtin_is_constant_evaluated (also MSVC). In case the builtin is not available, true should be returned (otherwise constexpr function will break).

Prototype preview with minimal compiler versions: https://godbolt.org/z/5b9E8E.
Previous work: #180.

Allow building with -fno-exceptions

The main issue are throws in the string to int procedures.

Implement int128 type

Implement the signed variant of 128-bit integer as an adapter/wrapper of uint128 from int128.hpp.

to_string only prints lo

Hi @chfast thank you for the great library

From my use of the library, it appears that to_string and hex only seem to be printing the lo bytes, I am using uint<256>

Implement montgomery modular multiplication

Merge int128.hpp and intx.hpp headers

Single-header library is easier to use, e.g. in https://godbolt.org.

Support conan package manager

Add the conan recipe and add intx to conan center.

How to convert uint256 to evmc_uint256be?

Could I use intx::uint256 as balance type in evmc?

If so, how to convert intx::uint256 to evmc_uint256be?

If not, how could I do math in evmc_uint256be, such as add(), sub()?

Support little endian load-store

Currently only big endian is supported: https://github.com/chfast/intx/blob/master/include/intx/intx.hpp#L921

question about operator<<

Any reason why we would not do this:

Build with -Wshadow

Upgrade Cable to 0.4.0 which enables -Wshadow. Then fix compilation issues.

Add all @= operator overloadings

Implement expmod

This can be usable in EVM's exp (mod for 256-bit) and Ethereum's modexp precompile.

The algorithm ethereumjs-vm used is this: https://stackoverflow.com/questions/1503007/sum-of-series-11-22-33-nn-mod-m/1503019#1503019

Of course for large exponents it is worth using #80 if it supported.

Currently only a naive exponentiation is implemented here

Improve to/from bytes conversions

• Mark the functions taking uint8_t* as unsafe. E.g. uint_unsafe() or from_unsafe().
• Add templates for uint8_t[N].
• Add extending and truncating variants in both directions.
• Add variants for types having .bytes field.

Draft in #104.

Optimize division

• Low level division procedure: https://github.com/piggypiggy/fp256/blob/master/src/ll/x64/ll_div-x64.pl.

Apply "Small Quotient Division" optimization

If you consider 256x256 bit division (i.e. 4-by-4 words division) where division by 1 and 2 words is already fast, the Small Quotient Division should nicely apply to remaining 4-by-4 and 4-by-3 cases.

https://gmplib.org/manual/Small-Quotient-Division

Code comment in GMP: https://gmplib.org/repo/gmp/file/tip/mpn/generic/tdiv_qr.c#l171

Add support for `operator <=>`

It seems current intx implementation is not compatible with C++20 operator <=>.

The test case is something like:

struct S
{
    intx::uint256 x;

    operator<=>() = default;
}

Move different div implementations to benchmarks

Optimize uint256 multiplication

1. We want to use the "loop" procedure as in mul_loop_opt().
2. There, it may be good to separate first iteration which does not need to load p[] values as they are zeros. Compilers are not always able to figure it out.
3. The best score was 60 instructions.
4. Some experimentation: https://godbolt.org/z/915aeG.

Redesign: change internal structure of intx types

The current intx 0.5 has "recursive" design, i.e. uint<N> types is composed of two (high and low) parts of uint<N/2> types. This was inspired by LLVM type legalization, but it turned out to have number of limitations and issues:

• the performance depends heavily on compiler inlining and is unpredictable which procedures are going to stay not inlined,
• it seems it would be better to have a loop over words instead of procedure calling some other big procedures,
• only power-of-two bit lengths are supported (no uint384),
• arbitrary length procedures cannot be reused (needed for division).

We propose to change the internal structure of intx types to simple array of 64-bit words uint64_t[K]. This makes this types being very close to std::array<uint64_t, K> although we will not use std::array directly — we want freedom to define other constructors and conversion operators.

An alternative was also considered:

1. Union of uint64_t[K} and two parts uint<N/2> hi, lo. This would allow two different style of access to the data, but it is quite complex and requires very obscure hackery to have constexpr support. In lo/hi access is needed it is probably much easier and cleaner to provide hi() and lo() helpers (methods or free functions).

Optimize comparison (less-than) with AVX2

https://godbolt.org/z/xEcGzqKo9

unsigned bsr(unsigned m)
{
    return  31 - __builtin_clz(m);  
}

auto lt_avx(const u256& x, const u256& y)
{
    auto xv = std::bit_cast<__m256i>(x);
    auto yv = std::bit_cast<__m256i>(y);
    auto e = _mm256_cmpeq_epi64(xv, yv);
    auto ed = std::bit_cast<__m256d>(e);
    unsigned m = _mm256_movemask_pd(ed);
    auto f = m ^ 0xf;  // flip mask (4 bits)
    auto g = f | 1;  // fixup eq
    auto i = bsr(g);
    return x.w[i] < y.w[i];
}

Division is broken

Division does not work when build with GCC6 / Release.

Unit tests fail with Xcode 14.3 on Apple silicon

Environement

Apple M1, Apple clang version 14.0.3 (clang-1403.0.22.14.1), macOS 13.4 (22F66)

Steps to reproduce

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
build/test/intx-unittests

Output

out.txt
[ FAILED ] 8 tests, listed below:
[ FAILED ] uint_test/uint192.comparison, where TypeParam = intx::uint<192u>
[ FAILED ] uint_test/uint384.comparison, where TypeParam = intx::uint<384u>
[ FAILED ] uint_test/uint512.comparison, where TypeParam = intx::uint<512u>
[ FAILED ] uint256.arithmetic
[ FAILED ] uint256.addmod
[ FAILED ] uint256.addmod_ec1
[ FAILED ] uint256.addmod_ec2
[ FAILED ] Uint256Test.add_against_sub

Add constexpr clz

Invalid noexcept attribute on the string operators (ie ""_u256)

They use from_string which is not marked noexcept and in fact throws exceptions.

Questions!

Hi Pawel, instead of having #if INTX_HAS_BUILTIN_INT128 in multiple APIs, why not just do:

#if INTX_HAS_BUILTIN_INT128
    using uint128 = builtin_uint128;
#else
    using uint128 = uint<128>;
#endif

Fix integrating as CMake subproject

Utility functions for small types

Extend support of intx utility functions to types smaller than uint64_t: uint8_t, uint16_t and uint32_t.

• Add bswap() for smaller types.
• Fix/test intx::be::unsafe<>.

Simplify literal API

Currently there is from_string<> and the literal operator, one supports hexadecimal, the other doesn't.

I think this should be made consistent.

Should also introduce to_hex_string() next to to_string().

Introduce iterator-based load/store

Currently it is based on arrays/vectors and byteswapping is performed afterwards. In many cases the inputs are iterators and could avoid byteswapping with reverse-iterating.

Library fails to build with MSVC because of unrecognized attributes

I have a project which requires building for most major platforms, including Windows using MSVC.
Currently, intx fails to build with MSBuild due to this warning (-Werror):

warning C5030: attribute 'gnu::always_inline' is not recognized

Specifically, my CI is on MSBuild version 17.4.1+9a89d02ff for .NET Framework

This issue is fixed by #284

clang static analyzer reports warnings

scan-build-8 cmake ../..
scan-build-8 make

/home/chfast/Projects/ethereum/intx/lib/intx/intx.cpp:174:27: warning: Division by zero
            qp = dividend / v[n-1];
                 ~~~~~~~~~^~~~~~~~
/home/chfast/Projects/ethereum/intx/lib/intx/intx.cpp:338:30: warning: The right operand of '*' is a garbage value
            uint64_t p = qhat*vn[i];
                             ^~~~~~
/home/chfast/Projects/ethereum/intx/lib/intx/intx.cpp:426:34: warning: The right operand of '/' is a garbage value
        uint64_t qhat = dividend / vn[n-1];         // Estimated quotient digit.
                                 ^ ~~~~~~~
/home/chfast/Projects/ethereum/intx/lib/intx/intx.cpp:443:30: warning: The right operand of '*' is a garbage value
            uint64_t p = qhat*vn[i];
                             ^~~~~~
/home/chfast/Projects/ethereum/intx/lib/intx/intx.cpp:592:31: warning: The right operand of '*' is a garbage value
            uint64_t p = qhat * vn[i];
                              ^ ~~~~~
/home/chfast/Projects/ethereum/intx/lib/intx/intx.cpp:659:9: warning: Assigned value is garbage or undefined
        uint64_t divisor = vn[n - 1];
        ^~~~~~~~~~~~~~~~   ~~~~~~~~~
6 warnings generated.

Move Cable to a subtree

Makes it easier to use intx as a submodule, such as in evmone.

Possible undefined behavior in normalize function

XCode's analyzer (through clang) is reporting possible undefined behavior in the normalize function, reached through a call to to_string. The issue occurs at

intx/include/intx/intx.hpp

Line 712 in 732522a

vn[i] = (v[i] << na.shift) | (v[i - 1] >> (64 - na.shift));

where v[i] is left shifted by na.shift bits. When na.shift == 64 this is undefined behavior. It looks like one possible solution to this would be to just set v[i] = v[i - 1] when na.shift == 64.

I've attached the execution trace that xcode produced, but the issue seems easy to produce na.shift == 64 when v[n - 1] == 0 due to the clz function.

intx/int128.hpp:858:1: Entered call from 'operator<<'
intx/int128.hpp:863:9: Assuming the condition is false
intx/int128.hpp:867:12: Entering loop body
intx/int128.hpp:870:26: Calling 'udivrem<256>'
intx/intx.hpp:858:1: Entered call from 'to_string<256>'
intx/intx.hpp:860:15: Calling 'normalize<intx::uint<256>>'
intx/intx.hpp:687:24: Entered call from 'udivrem<256>'
intx/intx.hpp:701:34: Assuming the condition is false
intx/intx.hpp:701:25: Loop body executed 0 times
intx/intx.hpp:705:25: Loop body executed 0 times
intx/intx.hpp:708:16: Calling 'clz'
intx/int128.hpp:476:1: Entered call from 'normalize<intx::uint<256>>'
intx/int128.hpp:481:12: Assuming 'x' is equal to 0
intx/int128.hpp:481:5: Returning the value 64, which participates in a condition later
intx/int128.hpp:481:5: Returning the value 64
intx/intx.hpp:708:16: Returning from 'clz'
intx/intx.hpp:708:5: The value 64 is assigned to 'na.shift'
intx/intx.hpp:711:37: Entering loop body
intx/intx.hpp:711:9: Looping back to the head of the loop
intx/intx.hpp:711:37: Entering loop body
intx/intx.hpp:711:9: Looping back to the head of the loop
intx/intx.hpp:711:37: Entering loop body
intx/intx.hpp:712:27: The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'