160

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

let a: i128 = 170141183460469231731687303715884105727;

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

因为，据我所知，该值无法放入 x86-64 CPU 的一个寄存器中，编译器是否以某种方式将两个寄存器用于一个i128值？或者他们是否使用某种大整数结构来表示它们？

4

4 回答 4

179

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

显然，8388607 位的架构并不多，所以当代码编译为本机代码时，LLVM 必须决定如何实现它。抽象指令的语义add是由 LLVM 本身定义的。通常，在本机代码中具有单指令等效的抽象指令将被编译为该本机指令，而那些没有的将被模拟，可能具有多个本机指令。mcarton 的回答演示了 LLVM 如何编译本机和模拟指令。

（这不仅适用于大于本机机器支持的整数，也适用于那些更小的整数。例如，现代架构可能不支持本机 8 位算术，因此可以模拟add两个 s 上的指令i8使用更宽的指令，多余的位被丢弃。）

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

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

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

于 2019-08-03T17:34:56.263 回答
64

编译器会将这些值存储在多个寄存器中，并在需要时使用多条指令对这些值进行算术运算。大多数 ISA 都有一个与x86adc类似的带进位指令，这使得执行扩展精度整数加/减相当有效。

例如，给定

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存储在raxand中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().

于 2019-08-03T17:22:31.980 回答
33

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

于 2019-08-04T05:00:27.987 回答
30

为了提供一个更清晰的示例，在 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¹²⁸ac + 2⁶⁴(ad+bc) + bd，其中每一个乘法都在一个寄存器中返回乘积的上半部分，在一个寄存器中返回乘积的下半部分其他。其中一些术语将被删除，因为第 128 位以上的位不适合 au128并被丢弃。即便如此，这也需要一些机器指令。除法也采取了几个步骤。对于有符号值，乘法和除法还需要转换操作数和结果的符号。这些操作根本不是很有效。

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

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

于 2019-08-04T13:39:49.967 回答