Перейти к основному содержимому

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

ОБЯЗАТЕЛЬНО
Разработчику

Контекст: 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                                    ; результат

Разбор:

  • dq объявляет 64-битные слова, поэтому каждое число хранится как массив лимбов шириной 8 байт.

  • В little-endian массиве первый dq у каждой переменной содержит младшую часть большого числа.

  • big_a и big_b задают два 128-битных операнда как по два 64-битных элемента.

  • big_sum dq 0, 0 резервирует буфер под результат той же разрядности.

  • Такая раскладка удобна для циклов adc/sbb, где каждая итерация обрабатывает одно слово.

  • 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 показывает перенос за пределы старшего слова (переполнение беззнакового числа).

Код ITЗагрузка примера кода…

Разбор:

  • Функция add_words получает три указателя и длину массива, что делает её универсальной для N-словных чисел.
  • xor rax, rax стартует цепочку с CF=0, чтобы младший лимб складывался без входного переноса.
  • В каждой итерации adc r8, [rsi] суммирует A[i] + B[i] + CF, а новый CF передаёт перенос в следующий лимб.
  • Указатели rdi/rsi/rdx сдвигаются на 8 байт, переходя к следующему 64-битному слову.
  • loop .loop использует RCX как счётчик оставшихся слов.
  • После цикла setc al превращает финальный перенос в явный флаг 0/1, который расширяется в RAX.
  • Возвращаемое значение удобно для контроля переполнения за старший разряд.

Важно: между итерациями нельзя вставлять инструкции, которые портят 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

Разбор:

  • sub_words повторяет ту же структуру цикла, но вместо adc использует sbb для цепочки заёма.
  • sbb r8, [rsi] вычитает текущее слово и дополнительную единицу, если предыдущий лимб потребовал borrow (CF=1).
  • Такой перенос заёма делает многоразрядное вычитание корректным на всей длине массива.
  • Финальный setc al сообщает, был ли заём из старшего слова, то есть ушли ли "ниже нуля" в беззнаковой арифметике.
  • Вся логика остаётся O(N) и масштабируется на произвольную разрядность.

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

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

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

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

Разбор:

  • add qword [rdi], 1 инкрементирует младший лимб большого числа.
  • Если младший лимб переполнился (стал 0), CF поднимется и передаст перенос вверх.
  • Каждая следующая adc ..., 0 добавляет только перенос к более старшему лимбу.
  • Цепочка останавливается естественно, когда CF перестаёт быть установленным.
  • Это эффективный шаблон для счётчиков большой разрядности и криптографических nonce.

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

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

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

Код ITЗагрузка примера кода…

Разбор:

  • r10 хранит межсловный перенос бита, который нужно "втянуть" в младший бит следующего лимба.
  • mov rax, [rdi + r11*8] читает текущее 64-битное слово, shl rax, 1 сдвигает его влево.
  • or rax, r10 добавляет перенос, пришедший из предыдущего менее значимого слова.
  • Через mov rbx, rax (до изменения) и shr rbx, 63 выделяется исходный старший бит текущего слова.
  • Полученный бит сохраняется в r10 как перенос для следующей итерации.
  • В конце r10 содержит "выпавший" за пределы старшего слова бит, то есть признак переполнения при сдвиге.
  • Паттерн показывает, как вручную реализуется единый сдвиг на всём большом числе.

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

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

Умножение и деление "в лоб"​

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

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

Сравнение двух 128-битных чисел (от старшего слова к младшему):

Код ITЗагрузка примера кода…

Разбор:

  • Сравнение начинают со старшего лимба: он задаёт порядок величины числа.
  • JA/JB используют беззнаковую семантику — для "длинных" целых это обычный выбор.
  • Если старшие слова равны, сравнивают младшие (как в десятичном сравнении разрядов).
  • Функция возвращает 0/1 в RAX как простой булев результат.
  • Умножение/деление строят на тех же идеях, но циклы заметно длиннее.

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

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

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

Содержание