¿Cómo funciona el entero de 128 bits `i128` de Rust en un sistema de 64 bits?

x86-64 bigint

Question

Rust tiene enteros de 128 bits, estos se denotan con el tipo de datos i128 (y u128 para u128 sin signo):

let a: i128 = 170141183460469231731687303715884105727;

¿Cómo hace Rust para que estos valores de i128 funcionen en un sistema de 64 bits? Por ejemplo, ¿cómo hace aritmética en estos?

Dado que, hasta donde yo sé, el valor no puede caber en un registro de una CPU x86-64, ¿el compilador de alguna manera usa 2 registros para un valor i128 ? ¿O en su lugar están utilizando algún tipo de estructura entera grande para representarlos?

Answer 1

El compilador los almacenará en múltiples registros y usará múltiples instrucciones para hacer aritmética en esos valores si es necesario. La mayoría de los ISA tienen una instrucción add-with-carry como adc de x86 que hace que sea bastante eficiente hacer add / sub de enteros de precisión extendida.

Por ejemplo, dado

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

el compilador genera lo siguiente al compilar para x86-64 sin optimización:
(comentarios añadidos por @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

donde puede ver que el valor 42 se almacena en rax y rcx .

(Nota del editor: las convenciones de llamadas x86-64 C devuelven enteros de 128 bits en RDX: RAX. Pero este main no devuelve ningún valor. Toda la copia redundante es puramente por la desactivación de la optimización, y ese Rust realmente comprueba el desbordamiento en modo de depuración.)

A modo de comparación, aquí está el asm para números enteros Rust de 64 bits en x86-64 donde no se necesita agregar con acarreo, solo un registro único o ranura de pila para cada valor.

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

El setb / test sigue siendo totalmente redundante: jc (salto si CF = 1) funcionaría bien.

Con la optimización habilitada, el compilador Rust no comprueba el desbordamiento, por lo que + funciona como .wrapping_add() .

Answer 2

Para proporcionar quizás un ejemplo más claro, en x86_64, compilado con el indicador -O , la función

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

compila a

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

(Mi publicación original tenía u128 lugar del i128 que preguntaste. La función compila el mismo código de cualquier manera, una buena demostración de que la adición firmada y sin firmar es la misma en una CPU moderna).

El otro listado produjo código no optimizado. Es seguro avanzar en un depurador, porque se asegura de que pueda poner un punto de interrupción en cualquier lugar e inspeccionar el estado de cualquier variable en cualquier línea del programa. Es más lento y más difícil de leer. La versión optimizada está mucho más cerca del código que realmente se ejecutará en producción.

El parámetro a de esta función se pasa en un par de registros de 64 bits, rsi: rdi. El resultado se devuelve en otro par de registros, rdx: rax. Las dos primeras líneas de código inicializan la suma a a .

La tercera línea agrega 1337 a la palabra baja de la entrada. Si esto se desborda, lleva el 1 en el indicador de acarreo de la CPU. La cuarta línea agrega cero a la palabra alta de la entrada, más el 1 si se transfirió.

Puede pensar en esto como una simple adición de un número de un dígito a un número de dos dígitos

  a  b
+ 0  7
______
 

pero en la base 18,446,744,073,709,551,616. Todavía está agregando el "dígito" más bajo primero, posiblemente llevando un 1 a la siguiente columna, luego agregando el siguiente dígito más el acarreo. La resta es muy similar.

La multiplicación debe usar la identidad (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, donde cada una de estas multiplicaciones devuelve la mitad superior del producto en un registro y la mitad inferior del producto en otro. Algunos de esos términos se eliminarán, porque los bits por encima del 128 no caben en un u128 y se descartan. Aun así, esto requiere una serie de instrucciones de la máquina. La división también toma varios pasos. Para un valor con signo, la multiplicación y la división necesitarían además convertir los signos de los operandos y el resultado. Esas operaciones no son muy eficientes en absoluto.

En otras arquitecturas, se vuelve más fácil o más difícil. RISC-V define una extensión de conjunto de instrucciones de 128 bits, aunque que yo sepa nadie lo ha implementado en silicio. Sin esta extensión, el manual de arquitectura RISC-V recomienda una rama condicional: addi t0, t1, +imm; blt t0, t1, overflow addi t0, t1, +imm; blt t0, t1, overflow

SPARC tiene códigos de control como los indicadores de control de x86, pero debe usar una instrucción especial, add,cc , para configurarlos. MIPS, por otro lado, requiere que verifique si la suma de dos enteros sin signo es estrictamente menor que uno de los operandos. Si es así, la adición se desbordó. Al menos puede establecer otro registro al valor del bit de acarreo sin una rama condicional.

Answer 3

Sí, de la misma manera que se manejaron enteros de 64 bits en máquinas de 32 bits, o enteros de 32 bits en máquinas de 16 bits, o incluso enteros de 16 y 32 bits en máquinas de 8 bits (¡todavía aplicable a microcontroladores! ) Sí, almacena el número en dos registros, o ubicaciones de memoria, o lo que sea (realmente no importa). La suma y la resta son triviales, toman dos instrucciones y usan la bandera de acarreo. La multiplicación requiere tres multiplicaciones y algunas adiciones (es común que los chips de 64 bits ya tengan una operación de multiplicación de 64x64-> 128 que genera dos registros). La división ... requiere una subrutina y es bastante lenta (excepto en algunos casos donde la división por una constante puede transformarse en un turno o una multiplicación), pero aún funciona. Bitwise y / o / xor simplemente tienen que hacerse en las mitades superior e inferior por separado. Los cambios se pueden lograr con rotación y enmascaramiento. Y eso prácticamente cubre las cosas.

Answer 4

Todos los tipos enteros de Rust se compilan en enteros LLVM . La máquina abstracta LLVM permite enteros de cualquier ancho de bit de 1 a 2 ^ 23 - 1. * Las instructions LLVM generalmente funcionan en enteros de cualquier tamaño.

Obviamente, no hay muchas arquitecturas de 8388607 bits, así que cuando el código se compila en código de máquina nativo, LLVM tiene que decidir cómo implementarlo. La semántica de una instrucción abstracta como add está definida por el propio LLVM. Por lo general, las instrucciones abstractas que tienen un equivalente de instrucción única en código nativo se compilarán a esa instrucción nativa, mientras que las que no se emularán, posiblemente con múltiples instrucciones nativas. La respuesta de mcarton demuestra cómo LLVM compila tanto las instrucciones nativas como las emuladas.

(Esto no solo se aplica a los enteros que son más grandes de lo que la máquina nativa puede admitir, sino también a los que son más pequeños. Por ejemplo, las arquitecturas modernas pueden no admitir la aritmética nativa de 8 bits, por lo que una instrucción add en dos i8 s puede ser emulado con una instrucción más amplia, los bits adicionales descartados).

¿El compilador de alguna manera usa 2 registros para un valor de i128 ? ¿O están usando algún tipo de estructura entera grande para representarlos?

En el nivel de LLVM IR, la respuesta es ninguna: i128 cabe en un único registro, al igual que cualquier otro tipo de valor único . Por otro lado, una vez traducido al código de máquina, no hay realmente una diferencia entre los dos, porque las estructuras pueden descomponerse en registros al igual que los enteros. Sin embargo, cuando se hace aritmética, es una apuesta bastante segura que LLVM simplemente cargará todo en dos registros.

* Sin embargo, no todos los backends LLVM se crean de la misma manera. Esta respuesta se relaciona con x86-64. Entiendo que el soporte de back-end para tamaños mayores de 128 y no potencias de dos es irregular (lo que puede explicar en parte por qué Rust solo expone enteros de 8, 16, 32, 64 y 128 bits). Según est31 en Reddit , rustc implementa números enteros de 128 bits en el software cuando apunta a un backend que no los admite de forma nativa.