Is there a 256-bit integer type?

Question

OS: Linux (Debian 10)

CC: GCC 8.3

CPU: i7-5775C

There is a unsigned __int128/__int128 in GCC, but is there any way to have a uint256_t/int256_t in GCC?

I have read of a __m256i which seems to be from Intel. Is there any header that I can include to get it?

Is it as usable as a hypothetic unsigned __int256? I mean if you can assign from/to it, compare them, bitwise operations, etc.

What is its signed equivalent (if any)?

---

EDIT 1:

I achieved this:

#include <immintrin.h>
typedef __m256i uint256_t;

and compiled. If I can do some operations with it, I'll update it here.

---

EDIT 2:

Issues found:

uint256_t   m;
int         l = 5;

m = ~((uint256_t)1 << l);

ouput:

error: can’t convert a value of type ‘int’ to vector type ‘__vector(4) long long int’ which has different size
  m = ~((uint256_t)1 << l);

Answer 1

Clang had _ExtInt extended integers that supports operations other than division, but SIMD isn't useful for that because of carry between elements¹. Other mainstream x86-64 compilers don't even have that; you need a library or something to define a custom type and use the same add-with-carry instructions clang will use. (Or a less efficient emulation in pure C²).

This has now been renamed _BitInt(n), and will be part of ISO C23. (clang -std=gnu2x).
As an extension, clang also accepts _BitInt in C++, regardless of revision, even with -std=c++11 rather than -std=gnu++11. Also in earlier C revisions, like -std=gnu11 or -std=c11.

---

typedef unsigned _BitInt(256) u256;
typedef /*signed*/ _BitInt(256) i256;

// works with clang 16
// but not GCC yet (as of April 2023)

int lt0(i256 a){
    return a < 0;  // just the sign bit in the top limb
}

// -march=broadwell allows mulx which clang uses, and adox/adcx which it doesn't
u256 mul256(u256 a, u256 b){
    return a*b;
}

Godbolt with clang -std=gnu2x - works even with -m32, where it's 8x 32-bit limbs instead of just 4x 64-bit. Multiply and divide expand inline to a large amount of code, not calling helper functions, so use carefully.

• Clang 11 and 12 supported _ExtInt(256), except for divide wider than 128. Not _BitInt.
  a<0 required explicit casts like a < (i256)0.
• Clang 13 added implicit conversion from int to _ExtInt types. Still no divide support for integers wider than 128-bit.
• Clang 14 and 15 support _BitInt(n), but only for sizes up to _BitInt(128), so all supported sizes support division.
• Clang 16 and later accept unsigned _BitInt(256) bar;, including mul and div (but it's expanded inline, not a helper function, so code-size is large for those ops.)
• GCC 12 and pre-13 trunk don't yet support _BitInt at all.

---

SIMD 256-bit vectors aren't 256-bit scalar integers

__m256i is AVX2 SIMD 4x uint64_t (or a narrower element size like 8x uint32_t). It's not a 256-bit scalar integer type, you can't use it for scalar operations, __m256i var = 1 won't even compile. There is no x86 SIMD support for integers wider than 64-bit, and the Intel intrinsic types like __m128i and __m256i are purely for SIMD. You can do bitwise boolean ops with them.

GCC's __int128 / unsigned __int128 typically uses scalar add/adc, and/or scalar mul / imul, because AVX2 is generally not helpful for extended precision, unless you use a partial-word storage format so you can defer carry. (SIMD is helpful for stuff like bitwise AND/OR/XOR where element boundaries are irrelevant.)

---

Footnote 1: There actually is some scope for using SIMD for BigInteger types, but only with a specialized format. And more importantly, you have to manually choose when to re-normalize (propagate carry) so your calculations have to be designed around it; it's not a drop-in replacement. See Mysticial's answer on Can long integer routines benefit from SSE?

Footnote 2: Unfortunately C does not provide carry-out from addition / subtraction, so it's not even convenient to write in C. sum = a+b / carry = sum<a works for carry out when there's no carry in, but it's much harder to write a full adder in C. And compiler typically make crap asm that doesn't just use native add-with-carry instructions on machines where they're available. Extended-precision libraries for very big integers, like GMP, are typically written in asm.

Answer 2

I did need "uint256_t" only while computing "f(x) = (x^2+a) mod n" in Pollard Rho algorithm. All variables outside function "f" are of builtin type __uint128_t.

I implemented uint256_t for that purpose simply as:

typedef __uint128_t uint256_t[2];

And then I implemented the functions needed for computing "f()":

__uint128_t set_128(unsigned long h, unsigned long l);
void set_256(uint256_t d, __uint128_t l, __uint128_t h);
void add_128(uint256_t d, uint256_t x, __uint128_t a);
void add_256(uint256_t d, uint256_t x, uint256_t a);
void shl_256(uint256_t d, long s);
void sqr_128(uint256_t d, __uint128_t x);
several print functions and macros for printing 128bit and 256bit numbers
__uint128_t mod_256(uint256_t x, __uint128_t n);
__uint128_t f(__uint128_t x);

Find the implementation in this gist:
https://gist.github.com/Hermann-SW/a20af17ee6666467fe0b5c573dae701d

I did benchmark my code against gmplib functions and achieved speedup over gmplib for all (after a lot of work), for details:
https://www.raspberrypi.org/forums/viewtopic.php?f=33&t=311893&p=1873552#p1873552

Runtimes in nanoseconds for 1 million executions of a function:

Answer 3

You can see a litle about on source code of BITCOIN, they use a library to C Language. If Delphi/Pascal you can use the Fundamentals5 (https://github.com/fundamentalslib/fundamentals5). Looking for, is possible to find more options of third paid libraries. There are some solutions to more than 256 bits.