Длинная арифметика: Сложение

В криптографии часто возникает случаи когда необходимо работать с длинными числами, например необходимо вычислить 256 в 512 степени. А также сделать с этими числами некие арифметические операции. В текущий момент регистры в современных компьютерах, на 64 битных операционных системах, позволяют хранить знаковое число +-9223372036854775807 ну или беззнаковое - умножить это число на 2. С такими числами размеров 64бита можно проводить стандартные операции вычитания, деления и с некоторыми условями - умножение и сложение. Но как быть если число как я написал например 256 в 512 степени, это приблизительно - 1.04 * 10 в 1233 степени. Тоесть такое число будет занимать больше килобайта, если на каждый символ отдавать по 1 байту. Понятно, что килобайт это ничто в текущих реалиях, а если там будет 100 тысячная степень или еще больше? Тут к нам приходят на помощь алгоритмы длинной арифметики.



Для начала рассмотрим простое сложение, вспомним 3ий класс или когда там начинают складывать? :)
Самый простой вариант - это сложить 2 числа столбиком, пример:
 1289
+
 4322
=
 5611 - результат
Идем с права на лево, от младшего знака к старшему, работам в десятеричной системе.
1. Складываем 9 + 2 = 11, но так как у нас 10ричная система, больше 9и мы записать не можем, так, что 1 пишем в младший регистр ответа и 1 уходит в перенос.
2. Складываем 8 + 2 = 10, опять получается, что мы превысили нашу десятеричную систему, по этому пишем 0 и тут мы вспоминаем, что у нас в переносе уже лежит 1, по этому прибавляем еденицу к нулю, итоговый результат уже 11, а в переносе снова лежит единица.
3. Складываем 2 + 3 = 5 - десятичную систему не переполнили и в перенос уже ничего не пишем, прибавляем к этому ответу еденицу из предыдущего переноса и получаем на этот этап итоговый результат 611
4. Последний этап, складываем 4 + 1 = 5 - десятичную систему не переполнили, в переносе у нас пусто, записываем в ответ в старший знак 5 и финальный ответ получается -  5611

 Вообщем пока все просто, а теперь можно попробовать это перенести в код ассемблера:

plus proc uses ecx edx ebx esi edi cif1:DWORD, cif2:DWORD, out_place:DWORD, lenght1:DWORD, lenght2:DWORD
    
    mov        ebx, cif1 ; в ebx заносим адрес цифры1
    mov        edx, cif2 ; в edx заносим адрес цифры2
    mov        edi, out_place ; в edi заносим адрес куда будем писать ответ
    xor        esi, esi ; обнуляем esi
    mov        al, BYTE PTR [edx] ; в al заносим младший байт цифры2
    add        al, BYTE PTR [ebx] ; прибавляем к al младший байт цифры 1
    mov        BYTE PTR [edi], al ; копируем цифру в младший регистр ответа
    jae        next_plus ; проверяем, а не превысили ли мы 8бит, 0FFh или 255 в десятеричной
    inc        BYTE PTR [edi+1] ; превысили - прибавляем в следующий младший байт еденицу
next_plus:
    dec        lenght1 ; уменьшаем счетчик длины первого числа
    dec        lenght2    ; уменьшаем счетчик длины второго числа
    inc        esi ; свдигаем esi - это у нас позиция в числах
    mov        al, BYTE PTR [edx + esi] ; копируем в al следующий младший байт числа1
    add        al, BYTE PTR [ebx + esi] ; складываем al с младшим байтом числа 2
    jae        plus_one_2 ; проверяем, а не превысили ли мы 8бит, 0FFh или 255 в десятеричной
    inc        BYTE PTR [edi+esi+1] ; превысили - прибавляем в следующий младший байт единицу
plus_one_2:
    add        BYTE PTR [edi + esi], al ; прибавляем результат к ответу
    jae        plus_one_3 ; а вдруг у нас там уже 1h а мы прибавляем 0FFh, проверим
    inc        BYTE PTR [edi+esi+2] ; и правда, прибавляем еденицу к следующему байту ответа
plus_one_3: ; начинаем колдунства если числа разной длинны
    mov        eax, lenght1 ; в eax копируем счетчик длины первого числа
    or        eax,eax ; проверим оно равно нулю?
    mov        eax, edx ; на всякий случай, скопируем адрес числа2 в eax
    jz        finish_plus ; число 1 всетаки равно нулю, прыгаем на finish_plus
    mov        eax, lenght2 ; в eax копируем счетчик длины второго числа
    or        eax,eax ; проверим оно равно нулю?
    mov        eax, ebx ; на всякий случай, скопируем адрес числа1 в eax
    jz        finish_plus ; число 2 всетаки равно нулю, прыгаем на finish_plus
    jmp        next_plus ; ни то ни другое чсило еще не кончилось, прыгаем на next_plus
finish_plus:
    mov        ebx, eax ; копируем адрес числа которое еще не закончилось в ebx
    mov        eax, lenght1 ; копируем длинну числа 1
    or        eax, eax ; проверяем, это оно закончилось?
    jz        check_plus_zero ; да? прыгаем на check_plus_zero
    mov        ecx, lenght1 ; скопируем в ecx на всякий случай длинну числа 1
    jmp        add_other_plus ; прыгаем на вычисление оставшегося большего числа
check_plus_zero:
    mov        eax, lenght2 ; копируем длинну числа 2
    or        eax, eax ; проверяем, это оно закончилось?
    jz        end_plus ; оба числа закончились - завершаем расчеты
    mov        ecx, lenght2 ; скопируем в ecx на всякий случай длинну числа 2
add_other_plus:
    inc        esi ; увеличиваем счетчик позиции в числе
    mov        al, BYTE PTR [ebx+esi] ; копируем в al байт числа в котором еще есть позиции
    add        BYTE PTR[edi+esi], al ; прибавляем к текущему байту в ответе
    jae        plus_one4 ; проверяем, а не превысили ли мы 8бит, 0FFh или 255 в десятеричной
    inc        BYTE PTR[edi+1+esi] ; превысили, прибавляем к след позиции 1
plus_one4:
    loop    add_other_plus ; повторить, пока счетчик ecx не обнулиться
end_plus:
    mov        eax, edi ; скопировать в eax адрес ответа

    Ret ; возвращаемся
plus EndP

Прототип функции будет следующий:
 plus PROTO:DWORD, :DWORD, :DWORD, :DWORD, :DWORD 
А вызывается следующим образом:
 invoke plus, ADDR num1, ADDR num2, ADDR int128, 3, 3 
Когда функция закончит работу, в eax будет адрес младшего байта суммы.
Из багов, алгоритм работает от 2х байт, если будет меньше, то возможно неправильные вычисления, так что надо учитывать или переписать его нафиг.
Ну вот на сегодня все, в следующей части будет, описание с кодом как вычитать числа.