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

Rust 有128位整数，它们用数据类型 i128(和 u128表示无符号整数)表示:

let a: i128 = 170141183460469231731687303715884105727;

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

因为，据我所知，这个值不能放入 x86-64 CPU 的一个寄存器中，编译器是否以某种方式为一个 i128值使用了两个寄存器？还是用某种大整数结构来表示它们？

26604 次浏览
小开

编译器将把这些值存储在多个寄存器中，并在需要时使用多个指令对这些值进行算术运算。大多数 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-64C 调用约定在 RDX: RAX 中返回128位整数。但是这个 main根本不返回值。所有冗余的复制都纯粹来自禁用优化，而 Rust 实际上在调试模式下检查溢出。)

相比之下，x86-64上的 Rust 64位整数不需要进位加法，只需要为每个值设置一个寄存器或堆栈槽即可。

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()类似。

小开
最佳答案

所有 Rust 的整数类型都被编译为 LLVM 整数。LLVM 抽象机允许从1到2 ^ 23-1的任意位宽度的整数。LLVM 指示通常处理任何大小的整数。

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

(这不仅适用于大于本机支持范围的整数，也适用于小于本机支持范围的整数。例如，现代体系结构可能不支持本地8位算术，因此在两个 i8上的一个 add指令可以用更广泛的指令进行仿真，多余的位被丢弃。)

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

在 LLVM IR 级别上，答案是两者都不适合: i128只适合一个寄存器，就像其他 单值类型单值类型一样。另一方面，一旦转换成机器代码，两者之间实际上没有什么区别，因为结构可以像整数一样被分解成寄存器。当做算术，但是，它是一个相当安全的打赌，LLVM 将只是加载到两个寄存器的整个东西。

* 然而，并非所有 LLVM 后端都创建相同的。这个答案与 x86-64有关。我理解后端对大于128和非2的幂的支持是不稳定的(这可能部分解释了为什么 Rust 只公开8-、16-、32-、64-和128-位整数)。当针对本身不支持它们的后端时，rustc 在软件中实现了128位整数。

小开

是的，就像处理32位机器上的64位整数，或16位机器上的32位整数，甚至8位机器上的16位和32位整数一样(仍然适用于微控制器.是的，您将数字存储在两个寄存器中，或者存储在内存位置中，或者其他任何地方(这并不重要)。加法和减法是微不足道的，需要两个指令，并使用进位标志。乘法需要三次乘法和一些加法(64位芯片通常已经有一个64x64-> 128次乘法运算，输出到两个寄存器)。除法... 需要一个子程序，并且相当慢(除了在某些情况下，常量的除法可以转换为移位或乘法) ，但它仍然可以工作。按位和/或/xor 只需分别在顶部和底部执行。转移可以通过旋转和掩蔽来完成。差不多就这些了。

小开

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

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到下一列，然后再加上下一个数字加上进位。减法非常相似。

乘法必须使用恒等式(264a + b)(264c + d) = 2128ac + 264(ad + bc) + bd，其中每个乘法返回一个寄存器中的乘积的上半部分和另一个寄存器中的乘积的下半部分。其中一些术语将被丢弃，因为位以上的128不适合进入 u128和被丢弃。即便如此，这也需要大量的机器指令。组织也采取了一些措施。对于有符号值，乘法和除法还需要转换操作数的符号和结果。这些操作一点也不高效。

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

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


提交答案