在Clang中进行256位算术运算（扩展整数）。

Question

在Clang中进行256位算术运算（扩展整数）。

cclangx86-64bigintextint

16

我正在设计一个项目，在其中需要大量进行简单的256位整数运算（仅包括加、减、乘、除），并且需要一些在这四个操作方面相对较优化的东西。

我已经熟悉了GMP、NTL和其他大型bignum实现。然而，这些实现的开销让我倾向于编写自己的低级实现 - 这是我真的不想做的事情；这种东西出了问题很难调试。

在我的研究中，我注意到了Clang中的新扩展整数类型-我是gcc的用户-我想知道是否有人在实际中使用过扩展的整数类型？它们是否针对“显而易见”的位大小（256、512等）进行了优化？

我在Linux下的x-64上使用C语言开发（目前是Ubuntu，但如有必要可选择其他发行版）。我主要使用gcc进行生产工作。

此外： @phuclv找到了之前的答案C++ 128/256-bit fixed size integer types。（感谢@phuclv。）这个问答集重点关注C++支持；我希望确定是否有人有使用新Clang类型的具体经验。

- Owen2020

3

欢迎来到 StackOverflow！恭喜您以一个有趣的问题作为您的第一篇帖子！不幸的是，我只能给您这个博客链接。 - Serge Ballesta

请使用一些库，如boost、https://github.com/calccrypto/uint256_t或https://www.ttmath.org/来代替。[C++ 128/256位固定大小整数类型](https://dev59.com/1G435IYBdhLWcg3wvys5)。 - phuclv

这个回答解决了你的问题吗？C++ 128/256位固定大小整数类型 - phuclv

嗨@phuclv。感谢您提供之前问题/答案的链接。我熟悉boost和其他在答案中提到的C++东西，最终可能不得不去那里:(！但是感谢您提供calccrypto链接-我以前没有看过。然而，我希望利用一些本地的东西，因此更有可能在空间和速度上更有效率，因此我想知道是否有人对Clang中的新类型有任何经验。 - Owen2020

谢谢@SergeBallesta。正是那篇博客让我开始了这条路!!! - Owen2020

3

你需要在GCC中使用可移植性吗？你的问题仅被标记为clang和clang-llvm，其中clang的新扩展将为您提供非常好的内联汇编。完全展开，因此不要将其用于巨大的整数，但256位= 4x64对于加法/减法是可以的。512位的话对乘除法来说有点臃肿，我假设除法会寻找除数只有一个limb的特殊情况，可以在https://godbolt.org/上尝试，或者逐步通过汇编来查看。 - Peter Cordes

2个回答

2

我使用_ExtInt(256)编写了一个简单的二进制除法算法：

我假设你正在编写与以太坊相关的内容，因此我也会在下面附上exp mod函数：

; typedef _ExtInt(256) I;
; void udiv256(I n, I d, I* q) {
;     *q = 0;
;     while (n >= d) {
;         I i = 0, d_t = d;
;         while (n >= (d_t << 1) && ++i)
;             d_t <<= 1;
;         *q |= (I)1 << i;
;         n -= d_t;
;     }
; }
define dso_local void @udiv256(i256*, i256*, i256*) {
  store i256 0, i256* %2, align 8
  %4 = load i256, i256* %0, align 8
  %5 = load i256, i256* %1, align 8
  %6 = icmp slt i256 %4, %5
  br i1 %6, label %24, label %7

  %8 = phi i256 [ %22, %16 ], [ %5, %3 ]
  %9 = phi i256 [ %21, %16 ], [ %4, %3 ]
  br label %10

  %11 = phi i256 [ %15, %10 ], [ 0, %7 ]
  %12 = phi i256 [ %13, %10 ], [ %8, %7 ]
  %13 = shl i256 %12, 1
  %14 = icmp slt i256 %9, %13
  %15 = add nuw nsw i256 %11, 1
  br i1 %14, label %16, label %10

  %17 = shl nuw i256 1, %11
  %18 = load i256, i256* %2, align 8
  %19 = or i256 %18, %17
  store i256 %19, i256* %2, align 8
  %20 = load i256, i256* %0, align 8
  %21 = sub nsw i256 %20, %12
  store i256 %21, i256* %0, align 8
  %22 = load i256, i256* %1, align 8
  %23 = icmp slt i256 %21, %22
  br i1 %23, label %24, label %7

  ret void
}


; void sdiv256(I* n, I* d, I* q) {
;     I ret = (I)1;
;     if (*n < (I)0) { ret *= (I)-1; *n = -*n; }
;     if (*d < (I)0) { ret *= (I)-1; *d = -*d; }
;     udiv256(n, d, q);
;     *q *= ret;
; }
define dso_local void @sdiv256(i256*,i256*, i256*) {
  %4 = load i256, i256* %0, align 8
  %5 = icmp slt i256 %4, 0
  br i1 %5, label %6, label %8

  %7 = sub nsw i256 0, %4
  store i256 %7, i256* %0, align 8
  br label %8

  %9 = phi i256 [ -1, %6 ], [ 1, %3 ]
  %10 = load i256, i256* %1, align 8
  %11 = icmp slt i256 %10, 0
  br i1 %11, label %12, label %15

  %13 = sub nsw i256 0, %9
  %14 = sub nsw i256 0, %10
  store i256 %14, i256* %1, align 8
  br label %15

  %16 = phi i256 [ %13, %12 ], [ %9, %8 ]
  store i256 0, i256* %2, align 8
  %17 = load i256, i256* %0, align 8
  %18 = load i256, i256* %1, align 8
  %19 = icmp slt i256 %17, %18
  br i1 %19, label %39, label %20

  %21 = phi i256 [ %35, %29 ], [ %18, %15 ]
  %22 = phi i256 [ %34, %29 ], [ %17, %15 ]
  br label %23

  %24 = phi i256 [ %28, %23 ], [ 0, %20 ]
  %25 = phi i256 [ %26, %23 ], [ %21, %20 ]
  %26 = shl i256 %25, 1
  %27 = icmp slt i256 %22, %26
  %28 = add nuw nsw i256 %24, 1
  br i1 %27, label %29, label %23

  %30 = shl nuw i256 1, %24
  %31 = load i256, i256* %2, align 8
  %32 = or i256 %31, %30
  store i256 %32, i256* %2, align 8
  %33 = load i256, i256* %0, align 8
  %34 = sub nsw i256 %33, %25
  store i256 %34, i256* %0, align 8
  %35 = load i256, i256* %1, align 8
  %36 = icmp slt i256 %34, %35
  br i1 %36, label %37, label %20

  %38 = load i256, i256* %2, align 8
  br label %39

  %40 = phi i256 [ %38, %37 ], [ 0, %15 ]
  %41 = mul nsw i256 %40, %16
  store i256 %41, i256* %2, align 8
  ret void
}


; void neg(I* n) {
;     *n = -*n;
; }
define dso_local void @neg(i256*) {
  %2 = load i256, i256* %0, align 8
  %3 = sub nsw i256 0, %2
  store i256 %3, i256* %0, align 8
  ret void
}

; void modPow(I* b, I* e, I* ret) {
;     *ret = (I)1;
;     I p = *b;
;     for (I n = *e; n > (I)0; n >>= 1) {
;         if ((n & (I)1) != (I)0)
;             *ret *= p;
;         p *= p;
;     }
; }
define dso_local void @powmod(i256*, i256* ,i256*) {
  store i256 1, i256* %2, align 8
  %4 = load i256, i256* %1, align 8
  %5 = icmp sgt i256 %4, 0
  br i1 %5, label %6, label %8

  %7 = load i256, i256* %0, align 8
  br label %9

  ret void

  %10 = phi i256 [ %18, %17 ], [ 1, %6 ]
  %11 = phi i256 [ %20, %17 ], [ %4, %6 ]
  %12 = phi i256 [ %19, %17 ], [ %7, %6 ]
  %13 = and i256 %11, 1
  %14 = icmp eq i256 %13, 0
  br i1 %14, label %17, label %15

  %16 = mul nsw i256 %10, %12
  store i256 %16, i256* %2, align 8
  br label %17

  %18 = phi i256 [ %10, %9 ], [ %16, %15 ]
  %19 = mul nsw i256 %12, %12
  %20 = lshr i256 %11, 1
  %21 = icmp eq i256 %20, 0
  br i1 %21, label %8, label %9
}

- Ricky Han

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nate Eldredge · Accepted Answer

看起来这些类型的除法目前仅支持不超过128位。

截至2020年8月2日，在godbolt上使用clang trunk编译以下x86-64代码时：

typedef unsigned _ExtInt(256) uint256;

uint256 div(uint256 a, uint256 b) {
    return a/b;
}

失败并显示错误信息

fatal error: error in backend: Unsupported library call operation!

试一试

_ExtInt(129) 和我尝试的所有更大的东西都会出现相同的问题。然而，_ExtInt(128) 和更小的似乎可以工作，但它们调用内部库函数__udivti3而不是内联。

这已经被报告为LLVM bug 45649。页面上有一些讨论，但总之他们似乎并不想编写完整的任意精度除法指令。

在此版本中，加法、减法和乘法与_ExtInt(256)一起使用是可行的。