C语言 是否存在256位整数类型?

mrzz3bfm  于 2023-04-19  发布在  其他
关注(0)|答案(3)|浏览(268)

操作系统:Linux(Debian 10)
CC:GCC 8.3
CPU:i7-5775C
在GCC中有一个unsigned __int128/__int128,但是有没有办法在GCC中有一个uint256_t/int256_t
我读到一个__m256i,似乎是从英特尔。有什么标题,我可以包括得到它?
它是否像一个假设的unsigned __int256一样可用?我的意思是,如果你可以从/到它赋值,比较它们,按位操作等。
它的有符号等价物是什么(如果有的话)?

编辑1:

我做到了:

#include <immintrin.h>
typedef __m256i uint256_t;

如果我可以用它做一些操作,我会在这里更新它。

编辑2:

发现的问题:

uint256_t   m;
int         l = 5;

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

输出:

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

hujrc8aj1#

Clang有_ExtInt扩展整数,支持除除法以外的操作,但SIMD对它没有用,因为元素之间有进位。你需要一个库或其他东西来定义一个自定义类型,并使用clang将使用的相同的加进位指令(或者纯C2中效率较低的仿真)。

现在已重命名为_BitInt(n),并将成为ISO C23.(clang -std=gnu2x)的一部分

作为一个扩展,clang在C++中也接受_BitInt,无论版本如何,即使是-std=c++11而不是-std=gnu++11。在早期的C版本中,如-std=gnu11-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;
}

Godboltwith clang -std=gnu2x-甚至可以与-m32一起工作,其中它是8x 32位肢体,而不仅仅是4x 64位。乘法和除法扩展内联到大量代码,而不是调用辅助函数,因此请谨慎使用。

  • Clang 11和12支持_ExtInt(256),除了比128更宽的划分。不支持_BitInt

a<0需要像a < (i256)0这样的显式强制转换。

  • Clang 13添加了从int_ExtInt类型的隐式转换。仍然不支持对大于128位的整数的除法。
    *Clang 14和15支持_BitInt(n),但仅支持_BitInt(128)以下的大小,因此所有支持的大小都支持除法。
    *Clang 16及更高版本接受unsigned _BitInt(256) bar;,包括穆尔和div(但它是内联扩展的,不是辅助函数,因此这些操作的代码大小很大。)
    *GCC 12和13之前版本的中继根本不支持_BitInt

SIMD 256位向量不是256位标量整数

__m256i是AVX2 SIMD 4x uint64_t(或更窄的元素大小,如8x uint32_t)。它不是256位标量整数类型,您不能将其用于标量操作,__m256i var = 1甚至无法编译。对于宽度超过64位的整数,没有x86 SIMD 支持,而Intel的内部类型,如__m128i__m256i,则是纯SIMD类型,你可以用它们进行位布尔运算。
GCC的__int128/unsigned __int128通常使用标量add/adc和/或标量mul/imul,因为AVX 2通常对扩展精度没有帮助,除非您使用a partial-word storage format so you can defer carry。(SIMD对元素边界无关的按位AND/OR/XOR等内容很有帮助。)

脚注1:实际上,对于BigInteger类型使用SIMD是有一定范围的,但只能使用专门的格式。更重要的是,您必须手动选择何时重新规范化(传播进位),因此您的计算必须围绕它设计;它不是一个简单的替代品。请参阅Mysticial的回答:长整数例程能从SSE中受益吗?
脚注2:不幸的是,C不提供加法/减法的进位输出,所以在C中编写甚至不方便。当没有进位输入时,sum = a+b/carry = sum<a用于进位输出,但是用C语言写全加器要困难得多。编译器通常会做一些垃圾asm,这些垃圾asm不只是在机器上使用本地的加进位指令。扩展-用于非常大的整数(如GMP)的精度库通常用asm编写。

polkgigr

polkgigr2#

我只在Pollard Rho算法中计算“f(x)=(x^2+a)mod n”时需要“uint256_t”。函数“f”之外的所有变量都是内置类型__uint128_t。
为此,我实现了uint256_t,简单地说:

typedef __uint128_t uint256_t[2];

然后我实现了计算“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);

在以下要点中找到实现:
https://gist.github.com/Hermann-SW/a20af17ee6666467fe0b5c573dae701d
我确实针对gmplib函数对我的代码进行了基准测试,并实现了对所有gmplib的加速(经过大量工作),详情如下:
https://www.raspberrypi.org/forums/viewtopic.php?f=33&t=311893&p=1873552#p1873552
一个函数执行100万次的运行时间(以纳秒为单位):

dxxyhpgq

dxxyhpgq3#

你可以看到一点关于BITCOIN的源代码,他们使用C语言库。如果 Delphi /Pascal,你可以使用Fundamentals 5(https://github.com/fundamentalslib/fundamentals5)。寻找,有可能找到更多的第三个付费库的选项。有一些解决方案超过256位。

相关问题