Арифметика больших чисел

Сложение и вычитание больших чисел

Поскольку регистры общего назначения в архитектуре x86-64 64-разрядные, то загрузить в один регистр число большей разрядности у нас не получится. Тем не менее мы не ограничены только 64-разрядными числами и можем работать с числами большей разрядности, например, 128-, 192-, 256-битными и т.д.

Например, возьмем 128-разрядные числа. Определенно такое число не помещается в один 64-разрядный регистр. Но мы можем разбить число и поместить его младшие 64 бита в один регистр, а старшие 64 бита в другой. Аналогично 192-разрядные числа разносятся по трем 64-разрядным регистрам.

При работе с большими числами, которые не укладываются в рамки одного регистра, основная идея состоит в том, чтобы разбить большую операцию на последовательность более мелких. Поскольку семейство процессоров x86 способно одновременно складывать не более 64 бит (используя регистры общего назначения), операция должна выполняться блоками по 64 бита или меньше.

Сложение больших чисел

Например, возьмем сложение 128-разрядных чисел. Сначала складываем младшие 64 разряда чисел. Если при сложении новое число выходит за пределы 64 бит, то процессор устанавливает флаг переноса CF. Затем складываем старшие 64 бита чисел и бит переноса.

Для сложения двух операндов с битом переноса применяется инструкция adc

adc dest, source    ; dest = dest + source + CF

Она, как и инструкция add, складывает два числа, но также к результату добавляет бит из флага переноса CF. Рассмотрим пример:

.data
    x oword 01ffffffffffffffffh
    y oword 010000000000000002h
    z oword ?
.code
main proc
    mov rax, qword ptr x    ; В RAX загружаем младшие 64 бита числа x
    add rax, qword ptr y    ; складываем их с младшими 64 битами числа y
    mov qword ptr z, rax    ; результат сложения помещаем в младшие 64 бита числа z

    mov rax, qword ptr x[8] ; В RAX загружаем старшие 64 бита числа x
    adc rax, qword ptr y[8] ; складываем их со старшими 64 битами числа y и с битом переноса

    mov qword ptr z[8], rax ; результат сложения помещаем в младшие 64 бита числа z
    ret
main endp
end

Для хранения данных здесь определяем три переменных типа oword (восьмеричное слово - 128-разрядное число). Сначала помещаем в регистр RAX младшие 64 бита переменной x и складываем их с младшими 64 битами переменной y. Чтобы получить младшие 64 бита, оператор qword ptr приводит переменные x, y и z к 64 битам (по сути берет младшие 64 бита).

После сложения младших 64 бит складываем старшие 64 бита. Для этого помещаем в RAX старшие 64 бита переменной x, складываем их со старшими 64 битами переменной y и помещаем результат в старшие 64 разряда переменной z. Чтобы получить старшие 64 бита, применяется выражение в форме x[8] вместе с оператором qword ptr (число 8 указывает на 8 байт).

В итоге мы получаем вычисления

01ffffffffffffffffh
+
010000000000000002h
=
030000000000000001h

В младших 64 бита будет число 1, а в старших 64 битах - число 3.

Подобным механизм можно распространить на числа и большей разрядности. Например, возьмем сложение 192-разрядных чисел:

.data
BigInt1 qword 0ffffffffffffffffh,   ; младшие 64 бит
              0ffffffffffffffffh,   ; средние 64 бит
              00000000000000001h    ; старшие 64 бит
BigInt2 qword 00000000000000002h,
              00000000000000000h,
              00000000000000001h
BigInt3 qword 3 dup (?) 
.code
main proc

    mov rax, BigInt1[0]
    add rax, BigInt2[0]
    mov BigInt3[0], rax
    
    mov rax, BigInt1[8]     ; 64 бита начиная с 8 байт
    adc rax, BigInt2[8]
    mov BigInt3[8], rax
 
    mov rax, BigInt1[16]     ; 64 бита начиная с 16 байт
    adc rax, BigInt2[16]
    mov BigInt3[16], rax
    ret
main endp
end

Здесь каждое число представлено переменной BigInt1/BigInt2/BigInt3, которое по сути представляет набор из 3 значений qword - младших, средних и старших 64 бит числа. И мы также по отдельности складываем эти части. А для учета при сложении флага переноса применяем инструкцию adc. То есть получаем вычисления

0000000000000001 ffffffffffffffff ffffffffffffffffh
+
0000000000000001 0000000000000000 00000000000000002h
=
0000000000000003 0000000000000000 00000000000000001h

Вычитание больших чисел

Аналогично можно применять вычитание больших чисел, разрядность которых больше 64 бит. В этом случае для вычитания младших 64 бит применяется стандартная инструкция sub, а для вычитания последующих 64 бит применяется инструкция sbb ("subtract with borrow" или вычитание с заимствованием), которая имеет аналогичный синтаксис:

sbb dest, source    ; dest=dest-source-CF

Из dest вычитается source и бит флага переноса, который устанавливается при заимствовании. И результат помещается в dest

Рассмотрим пример:

.data
    x oword 030000000000000001h
    y oword 01ffffffffffffffffh
    z oword ?
.code
main proc

    mov rax, qword ptr x        ; помещаем в RAX младшие 64 бит числа x
    sub rax, qword ptr y        ; вычитаем из RAX младшие 64 бит числа y
    mov qword ptr z, rax        ; результат помещаем в младшие 64 бит числа z
 
    mov rax, qword ptr x[8]     ; помещаем в RAX старшие 64 бит числа x
    sbb rax, qword ptr y[8]     ; вычитаем из RAX старшие 64 бит числа y
    mov qword ptr z[8], rax     ; результат помещаем в старшие 64 бит числа z

    ret
main endp
end

Здесь из 128-разрядного числа x вычитаем другое 128-разрядное число y. Сначала вычитаем из младшие 64 бита, а затем старшие. Таким образом получим:

30000000000000001h
-
1ffffffffffffffffh
=
10000000000000002h

Если смотреть поэтапно, то сначала вычитаем младшие 64 бита

0000000000000001h
-
ffffffffffffffffh
=
0000000000000002h

Значение первого числа меньше значения второго числа, поэтому необходимо заимствование в первом числе из старших 64 бит.

Подобным механизм можно вычитать числа большей разрядности. Например, возьмем вычитание 192-разрядных чисел:

.data
BigInt1 qword 00000000000000001h,   ; младшие 64 бит
              00000000000000000h,   ; средние 64 бит
              00000000000000003h    ; старшие 64 бит

BigInt2 qword 0ffffffffffffffffh,   ; младшие 64 бит
              0ffffffffffffffffh,   ; средние 64 бит
              00000000000000001h    ; старшие 64 бит
BigInt3 qword 3 dup (?) 
.code
main proc

    mov rax, BigInt1[0]
    sub rax, BigInt2[0]
    mov BigInt3[0], rax
    
    mov rax, BigInt1[8]     ; средние 64 бита - начиная с 8 байт
    sbb rax, BigInt2[8]     ; вычитание с заимствованием
    mov BigInt3[8], rax
 
    mov rax, BigInt1[16]     ; старшие 64 бита - начиная с 16 байт
    sbb rax, BigInt2[16]     ; вычитание с заимствованием
    mov BigInt3[16], rax

    ret
main endp
end

Здесь будет идет следующее вычисление:

0000000000000003 0000000000000000 0000000000000001h
-
0000000000000001 ffffffffffffffff ffffffffffffffffh
=
0000000000000001 0000000000000000 0000000000000002h