Rust的128位整数“ i128”如何在64位系统上工作？

Question

Rust具有128位整数，这些整数用数据类型表示i128（u128对于无符号整数）：

let a: i128 = 170141183460469231731687303715884105727;

Rust如何使这些i128值在64位系统上工作？例如，如何对这些进行算术运算？

据我所知，既然该值不能容纳在x86-64 CPU的一个寄存器中，那么编译器是否会以某种方式使用2个寄存器i128？还是他们改用某种大整数结构来表示它们？

Answer 1

所有Rust的整数类型都被编译为LLVM integers。LLVM抽象机允许从1到2 ^ 23-1的任何位宽的整数。* LLVM 指令通常在任何大小的整数上工作。

显然，那里并没有太多的8388607位架构，因此，在将代码编译为本机代码时，LLVM必须决定如何实现它。像这样的抽象指令的语义add是由LLVM自己定义的。通常，在本机代码中具有单指令等效项的抽象指令将被编译为该本机指令，而在没有本机代码的情况下将被模拟，可能使用多个本机指令。mcarton的答案演示了LLVM如何编译本机指令和仿真指令。

（这不仅适用于大于本机机器可以支持的整数，而且还适用于较小的整数。例如，现代体系结构可能不支持本机8位算术，因此可以模拟add两个i8s 上的指令使用更宽的指令，多余的位将被丢弃。）

编译器是否以某种方式将2个寄存器用于一个i128值？还是他们使用某种大整数结构来表示它们？

在LLVM IR级别上，答案都不是：i128像所有其他单值类型一样适合单个寄存器。另一方面，一旦翻译成机器代码，两者之间实际上并没有什么区别，因为结构可能像整数一样分解为寄存器。但是，在进行算术运算时，可以肯定地认为LLVM会将整个内容加载到两个寄存器中。

*但是，并非所有的LLVM后端都是相同的。此答案与x86-64有关。我知道后端对大于128的大小和非2的幂的支持是参差不齐的（这可能部分解释了Rust为何只公开8位，16位，32位，64位和128位整数）。根据Reddit上的 est31，当目标不是本机支持整数的后端时，rustc在软件中实现128位整数。

Answer 2

编译器会将它们存储在多个寄存器中，并在需要时使用多个指令对这些值进行算术运算。大多数ISA都有x86这样的“adc随身携带”指令，这使得执行扩展精度整数加/减相当有效。

例如，给定

fn main() {
    let a = 42u128;
    let b = a + 1337;
}

在不进行优化的情况下为x86-64进行编译时，编译器会生成以下内容：（
注释由@PeterCordes添加）

playground::main:
    sub rsp, 56
    mov qword ptr [rsp + 32], 0
    mov qword ptr [rsp + 24], 42         # store 128-bit 0:42 on the stack
                                         # little-endian = low half at lower address

    mov rax, qword ptr [rsp + 24]
    mov rcx, qword ptr [rsp + 32]        # reload it to registers

    add rax, 1337                        # add 1337 to the low half
    adc rcx, 0                           # propagate carry to the high half. 1337u128 >> 64 = 0

    setb    dl                           # save carry-out (setb is an alias for setc)
    mov rsi, rax
    test    dl, 1                        # check carry-out (to detect overflow)
    mov qword ptr [rsp + 16], rax        # store the low half result
    mov qword ptr [rsp + 8], rsi         # store another copy of the low half
    mov qword ptr [rsp], rcx             # store the high half
                             # These are temporary copies of the halves; probably the high half at lower address isn't intentional
    jne .LBB8_2                       # jump if 128-bit add overflowed (to another not-shown block of code after the ret, I think)

    mov rax, qword ptr [rsp + 16]
    mov qword ptr [rsp + 40], rax     # copy low half to RSP+40
    mov rcx, qword ptr [rsp]
    mov qword ptr [rsp + 48], rcx     # copy high half to RSP+48
                  # This is the actual b, in normal little-endian order, forming a u128 at RSP+40
    add rsp, 56
    ret                               # with retval in EAX/RAX = low half result

您可以在其中看到该值42存储在rax和中rcx。

（编者注：x86-64 C调用约定在RDX：RAX中返回128位整数。但这main根本不返回值。所有冗余复制纯粹是出于禁用优化的考虑，Rust实际上在调试中检查溢出模式。）

为了进行比较，这是x86-64上Rust 64位整数的asm，其中不需要加载，每个值仅需一个寄存器或堆栈槽。

playground::main:
    sub rsp, 24
    mov qword ptr [rsp + 8], 42           # store
    mov rax, qword ptr [rsp + 8]          # reload
    add rax, 1337                         # add
    setb    cl
    test    cl, 1                         # check for carry-out (overflow)
    mov qword ptr [rsp], rax              # store the result
    jne .LBB8_2                           # branch on non-zero carry-out

    mov rax, qword ptr [rsp]              # reload the result
    mov qword ptr [rsp + 16], rax         # and copy it (to b)
    add rsp, 24
    ret

.LBB8_2:
    call panic function because of integer overflow

setb / test仍然是完全多余的：（jc如果CF = 1，则跳转）就可以了。

启用优化功能后，Rust编译器不会检查溢出，因此其+工作方式类似于.wrapping_add()。

Answer 3

是的，就像处理32位计算机上的64位整数，或处理16位计算机上的32位整数，甚至处理8位计算机上的16位和32位整数一样（仍然适用于微控制器！）。 ）。是的，您可以将数字存储在两个寄存器中，或者存储在内存中，或者其他任何东西上（这并不重要）。加法和减法都很简单，需要两条指令并使用进位标志。乘法需要三个乘法和一些加法（对于64位芯片，已经有一个64x64-> 128乘法运算输出到两个寄存器是很常见的）。除法...需要一个子例程，并且速度很慢（在某些情况下，除以常数可以转换为移位或乘法），但它仍然有效。逐位和/或/或仅需分别在上半部分和下半部分进行。移位可以通过旋转和遮罩来完成。这几乎涵盖了一切。

Answer 4

为了提供一个更清晰的示例，在x86_64上，用-O标志编译该函数

pub fn leet(a : i128) -> i128 {
    a + 1337
}

编译为

example::leet:
  mov rdx, rsi
  mov rax, rdi
  add rax, 1337
  adc rdx, 0
  ret

（我的原始帖子u128不是i128您所问的。函数以两种方式编译相同的代码，很好地演示了现代CPU上带符号和无符号加法是相同的。）

另一个清单产生未优化的代码。进入调试器是安全的，因为它确保您可以在任何地方放置断点并检查程序任何行中任何变量的状态。它更慢，更难阅读。优化的版本更接近实际在生产中运行的代码。

a此函数的参数在一对64位寄存器rsi：rdi中传递。结果在另一对寄存器rdx：rax中返回。代码的前两行将总和初始化为a。

第三行将1337添加到输入的低位字。如果溢出，它将在CPU的进位标志中带有1。第四行在输入的高位字上加上零，如果进位则加1。

您可以认为这是将一位数字简单地加到两位数字上

  a  b
+ 0  7
______
 

但以18,446,744,073,709,551,616为基数。您仍然要先添加最低的“数字”，可能在下一列中加1，然后再添加下一个数字加进位。减法非常相似。

乘法必须使用恒等式（2 ?? a + b）（2 ?? c + d）= 2 12？ac + 2 ??（ad + bc）+ bd，其中每个乘法都返回乘积的上半部分。一个寄存器，产品的下半部分另一个。其中一些术语将被丢弃，因为第128位以上的位不适合u128并被丢弃。即使这样，这仍然需要许多机器指令。除法也采取了几个步骤。对于带符号的值，乘法和除法还需要转换操作数的符号和结果。这些操作根本不是很有效。

在其他体系结构上，它变得更容易或更难。RISC-V定义了一种128位指令集扩展，尽管据我所知没有人在硅片上实现它。如果没有此扩展，则RISC-V体系结构手册建议使用条件分支：addi t0, t1, +imm; blt t0, t1, overflow

SPARC具有类似于x86的控制标志的控制代码，但是您必须使用特殊的指令add,cc来进行设置。另一方面，MIPS 要求您检查两个无符号整数的和是否严格小于一个操作数。 如果是这样，则添加内容溢出。至少您可以在没有条件分支的情况下将另一个寄存器设置为进位位的值。