[SOLVED] Is there a 256-bit integer type?

Issue

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

Solution

Clang has _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²).

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

GCC's __int128 / unsigned __int128 typically uses scalar add/adc, and/or scalar mul / imul, because AVX2 is generally not helpful for extended precision. (Only 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.

Answered By - Peter Cordes