Длинная целочисленная арифметика

ОБЯЗАТЕЛЬНО

Разработчику

Контекст: NASM, x86-64, Linux, беззнаковая арифметика. Предполагается знакомство с флагами и ADD/SUB и типами данных.

Длинная арифметика - числа шире регистра

Регистр RAX вмещает 64 бита. Криптография, хеши, большие счётчики и промежуточные результаты компилятора оперируют сотнями и тысячами бит. На уровне ассемблера такое число — не «тип», а массив машинных слов фиксированной ширины (обычно 32 или 64 бита на элемент), упакованный в память в порядке little-endian: младшее слово лежит по младшему адресу.

Обычные ADD и SUB обновляют флаг переноса CF (Carry). Инструкции ADC (add with carry) и SBB (subtract with borrow) включают CF в следующий разряд — это основа поразрядной арифметики «в столбик» на железе.

---

Представление числа

Пусть число из N слов по 64 бита:

section .data
    big_a   dq 0x89ABCDEF01234567, 0xFEDCBA9876543210   ; 128 бит, 2 слова
    big_b   dq 0x1111111111111111, 0x2222222222222222
    big_sum dq 0, 0                                    ; результат

• big_a[0] — младшие 64 бита (младший адрес).
• big_a[8] — следующее слово (в NASM dq + смещение 8).

Размер в байтах: N * 8. Длина в битах: N * 64.

---

Сложение — ADC по словам

Алгоритм:

1. Обнулить CF (xor rax, rax / sub rax, rax — оба дают CF=0).
2. Для i от 0 до N−1: загрузить слова операндов, выполнить adc в слово результата.
3. После цикла CF показывает перенос за пределы старшего слова (переполнение беззнакового числа).

; rdi = адрес A, rsi = адрес B, rdx = адрес результата, rcx = число слов (N)
add_words:
    xor rax, rax              ; CF := 0
.loop:
    mov r8, [rdi]
    adc r8, [rsi]             ; r8 = A[i] + B[i] + CF
    mov [rdx], r8
    add rdi, 8
    add rsi, 8
    add rdx, 8
    loop .loop                  ; dec rcx; jnz — классический счётчик
    setc al                     ; al = 1, если был перенос за старший разряд
    movzx rax, al
    ret

Важно: между итерациями нельзя вставлять инструкции, которые портят CF (лишние add/sub/cmp без сохранения флагов). Если нужна арифметика внутри цикла — сохраняйте CF через pushfq / popfq или перестройте цикл.

Для знакового переполнения смотрите также OF; для беззнакового «не влезло» достаточно финального CF.

---

Вычитание — SBB

Зеркальная схема: перед циклом CF=0, в теле — sbb:

sub_words:
    xor rax, rax
.loop:
    mov r8, [rdi]
    sbb r8, [rsi]
    mov [rdx], r8
    add rdi, 8
    add rsi, 8
    add rdx, 8
    loop .loop
    setc al
    movzx rax, al
    ret

SBB вычитает операнд и дополнительно 1, если CF был установлен (заём из старшего разряда).

---

Сложение константы к младшему слову

Инкремент «длинного» числа на малый шаг:

    xor rax, rax
    add qword [rdi], 1          ; младшее слово; CF = перенос
    adc qword [rdi + 8], 0      ; распространить перенос по старшим словам
    adc qword [rdi + 16], 0
    ; ...

Так же работает вычитание единицы: sub + цепочка sbb со второго слова.

---

Сдвиг всего числа на один бит влево

Обход от младшего слова к старшему: в r10 храним перенос из предыдущего (0 или 1), после сдвига слова старший бит уходит в перенос для следующего.

; rdi = база массива слов, rcx = N (>= 1)
; по завершении r10 = бит, «выпавший» из старшего слова (переполнение)
shl_words_left_1:
    xor r10, r10              ; перенос в младшее слово = 0
    xor r11, r11              ; индекс слова
.loop:
    mov rax, [rdi + r11*8]
    mov rbx, rax
    shl rax, 1
    or rax, r10               ; втянуть перенос с предыдущего слова
    mov [rdi + r11*8], rax
    shr rbx, 63               ; исходный старший бит -> перенос для следующего
    mov r10, rbx
    inc r11
    loop .loop
    ret

Сдвиг вправо — зеркально: shr, перенос из младшего бита в r10, or в старший бит следующего слова. Для больших k повторяют однобитовый сдвиг или комбинируют сдвиг внутри слова с отдельным переносом между словами.

Сдвиг вправо (деление на 2) — симметрично, от младшего к старшему, с заимом через CF.

---

Умножение и деление «в лоб»

Полное умножение двух N-словных чисел — алгоритм «в столбик» по словам с накоплением через ADC, либо использование MUL/IMUL для произведения одного слова на всё число (как в школьном умножении длинных чисел). Деление — обратная идея со DIV/IDIV по частям. В прикладном коде эти циклы длинные; библиотеки (GMP, OpenSSL) комбинируют их с SIMD и специальными инструкциями (MULX, ADCX, ADOX на современных x86).

Для обучения достаточно уверенно владеть сложением и вычитанием — остальное строится поверх них.

---

Типичные ошибки

Ошибка	Последствие
Потеря CF между итерациями	Неверная сумма/разность начиная со второго слова
Перепутан порядок слов (big-endian в памяти)	Число «переворачивается» при сравнении с ожиданием
Смешение 32- и 64-битных слов в одном массиве	Смещения +8 не совпадают с реальным размером элемента
Знаковое сравнение длинных чисел через JG без учёта старшего слова	Нужно сравнивать от старшего слова к младшему как беззнаковые (JA/JB) или реализовать знаковую семантику отдельно

---

Связь с другими темами

• Условные переходы без ветвления — SETcc и CMOV.
• Вызов подпрограммы, которая обрабатывает буфер в памяти — Команды и подпрограммы.
• Криптографические ускорители в истории раздела используют те же идеи на сотнях слов.

---