chfast / intx

Extended precision integer C++ library

intx

Extended precision integer C++ library

The intx header-only C++20 library provides allocation-free extended precision integer types. They are implemented as arrays of std::uint64_t words and closely match the behavior of built-in types.

Usage

To build, test or benchmark.

git clone https://github.com/chfast/intx
cd intx

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel

build/test/intx-unittests
build/test/intx-bench

Maintainer

Paweł Bylica @chfast

License

Licensed under the Apache License, Version 2.0.

intx's Issues

Division is broken

Division does not work when build with GCC6 / Release.

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.

Implement montgomery modular multiplication

Add constexpr clz

Support conan package manager

Add the conan recipe and add intx to conan center.

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 Cable to a subtree

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

Allow building with -fno-exceptions

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

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().

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()?

Implement int128 type

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

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.

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>

Fix integrating as CMake subproject

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

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

Move different div implementations to benchmarks

Merge int128.hpp and intx.hpp headers

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

Add all @= operator overloadings

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.

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.

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

question about operator<<

Any reason why we would not do this:

Support little endian load-store

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

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

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];
}

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).

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

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

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<>.

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.

Build with -Wshadow

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

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

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'