Как я могу умножить два 64-битных числа, используя язык ассемблера x86?
https://stackoverflow.com/questions/87771
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как бы я поступил...
умножение двух 64-битных чисел
умножение двух 16-значных шестнадцатеричных чисел
... используя язык ассемблера.
Мне разрешено использовать только регистры %eax, %ebx, %ecx, %edx и стек.
РЕДАКТИРОВАТЬ:О, я использую синтаксис ATT на x86.
РЕДАКТИРОВАТЬ2:Не разрешено декомпилировать в сборку...
Решение
Используйте то, что, вероятно, должно быть вашим учебником, «Искусство языка ассемблера» Рэндалла Хайда.
Видеть 4.2.4 – Умножение повышенной точности
Хотя умножения 8x8, 16x16 или 32x32 обычно достаточно, бывают случаи, когда вам может потребоваться перемножить большие значения.Вы будете использовать инструкции MUL и IMUL с одним операндом x86 для умножения повышенной точности.
Наверное, самое важное, что нужно помнить при выполнении умножения с повышенной точностью необходимо одновременно выполнить сложение с множественной точностью..Сложение всех частичных продуктов требует нескольких дополнений, которые дадут результат.Следующий листинг демонстрирует правильный способ умножения двух 64-битных значений на 32-битном процессоре.
(См. ссылку на полный список сборок и иллюстрации.)
Другие советы
Если бы это было 64x86,
function(x, y, *lower, *higher)
movq %rx,%rax #Store x into %rax
mulq %y #multiplies %y to %rax
#mulq stores high and low values into rax and rdx.
movq %rax,(%r8) #Move low into &lower
movq %rdx,(%r9) #Move high answer into &higher
Поскольку вы используете x86, вам нужны 4 инструкции mull.Разделите 64-битные величины на два 32-битных слова и умножьте младшие слова на младшее и 2-е младшее слова результата, затем обе пары младшего и старшего слова из разных чисел (они идут ко 2-му и 3-му младшему слову результата) и наконец, оба старших слова превращаются в 2 старших слова результата.Сложите их все вместе, не забывая заниматься переносом.Вы не указали расположение памяти для входов и выходов, поэтому невозможно написать пример кода.
В этом коде предполагается, что вам нужен x86 (а не код x64), что вам, вероятно, нужен только 64-битный продукт и что вас не волнуют переполнение или числа со знаком.(Подписанная версия аналогична).
MUL64_MEMORY:
mov edi, val1high
mov esi, val1low
mov ecx, val2high
mov ebx, val2low
MUL64_EDIESI_ECXEBX:
mov eax, edi
mul ebx
xch eax, ebx ; partial product top 32 bits
mul esi
xch esi, eax ; partial product lower 32 bits
add ebx, edx
mul ecx
add ebx, eax ; final upper 32 bits
; answer here in EBX:ESI
Это не учитывает точные ограничения регистров OP, но результат полностью соответствует регистрам, предлагаемым x86.(Этот код не проверен, но я думаю, что он правильный).
[Примечание:Я перенес (свой) этот ответ из другого вопроса, который был закрыт, потому что НИ ОДИН из других «ответов» здесь не ответил на вопрос напрямую].
Это зависит от того, какой язык вы используете.Насколько я помню из изучения сборки MIPS, есть команды Move From High и Move From Lo, или mflo и mfhi.mfhi хранит верхние 64 бита, а mflo — младшие 64 бита общего числа.
ах, сборка, давно я ею не пользовался.Итак, я предполагаю, что настоящая проблема заключается в том, что микроконтроллер (который я все равно использовал для написания кода на ассемблере), над которым вы работаете, не имеет 64-битных регистров?в этом случае вам придется разбить числа, с которыми вы работаете, на части и выполнить несколько умножений с их частями.
Судя по тому, как вы это сформулировали, это похоже на домашнее задание, поэтому я не буду подробно это объяснять :P
Просто выполните обычное длинное умножение, как если бы вы умножали пару двузначных чисел, за исключением того, что каждая «цифра» на самом деле является 32-битным целым числом.Если вы умножаете два числа по адресам X и Y и сохраняете результат в Z, то вам нужно сделать (в псевдокоде):
Z[0..3] = X[0..3] * Y[0..3] Z[4..7] = X[0..3] * Y[4..7] + X[4..7] * Y[0..3]
Обратите внимание, что мы отбрасываем старшие 64 бита результата (поскольку 64-битное число, умноженное на 64-битное число, составляет 128-битное число).Также обратите внимание, что это предполагает прямой порядок байтов.Кроме того, будьте осторожны с знаковым и беззнаковым умножением.
Найдите компилятор C, поддерживающий 64-битную версию (GCC поддерживает IIRC), скомпилируйте программу, которая делает именно это, а затем выполните дизассемблирование.GCC может выдать его самостоятельно, и вы можете извлечь его из объектного файла с помощью подходящих инструментов.
OTOH, это операция 32bX32b = 64b на x86.
a:b * c:d = e:f
// goes to
e:f = b*d;
x:y = a*d; e += x;
x:y = b*c; e += x;
все остальное переполняется
(непроверено)
Редактировать Только без подписи
Держу пари, что вы студент, так что посмотрите, сможете ли вы справиться с этой задачей:Делайте это слово за словом и используйте битовые сдвиги.Придумайте наиболее эффективное решение.Остерегайтесь знакового бита.
Если вам нужен режим 128, попробуйте это...
__uint128_t AES::XMULTX(__uint128_t TA,__uint128_t TB)
{
union
{
__uint128_t WHOLE;
struct
{
unsigned long long int LWORDS[2];
} SPLIT;
} KEY;
register unsigned long long int __XRBX,__XRCX,__XRSI,__XRDI;
__uint128_t RESULT;
KEY.WHOLE=TA;
__XRSI=KEY.SPLIT.LWORDS[0];
__XRDI=KEY.SPLIT.LWORDS[1];
KEY.WHOLE=TB;
__XRBX=KEY.SPLIT.LWORDS[0];
__XRCX=KEY.SPLIT.LWORDS[1];
__asm__ __volatile__(
"movq %0, %%rsi \n\t"
"movq %1, %%rdi \n\t"
"movq %2, %%rbx \n\t"
"movq %3, %%rcx \n\t"
"movq %%rdi, %%rax \n\t"
"mulq %%rbx \n\t"
"xchgq %%rbx, %%rax \n\t"
"mulq %%rsi \n\t"
"xchgq %%rax, %%rsi \n\t"
"addq %%rdx, %%rbx \n\t"
"mulq %%rcx \n\t"
"addq %%rax, %%rbx \n\t"
"movq %%rsi, %0 \n\t"
"movq %%rbx, %1 \n\t"
: "=m" (__XRSI), "=m" (__XRBX)
: "m" (__XRSI), "m" (__XRDI), "m" (__XRBX), "m" (__XRCX)
: "rax","rbx","rcx","rdx","rsi","rdi"
);
KEY.SPLIT.LWORDS[0]=__XRSI;
KEY.SPLIT.LWORDS[1]=__XRBX;
RESULT=KEY.WHOLE;
return RESULT;
}
Если вам нужно 128-битное умножение, это должно работать, это формат AT&T.
__uint128_t FASTMUL128(const __uint128_t TA,const __uint128_t TB)
{
union
{
__uint128_t WHOLE;
struct
{
unsigned long long int LWORDS[2];
} SPLIT;
} KEY;
register unsigned long long int __RAX,__RDX,__RSI,__RDI;
__uint128_t RESULT;
KEY.WHOLE=TA;
__RAX=KEY.SPLIT.LWORDS[0];
__RDX=KEY.SPLIT.LWORDS[1];
KEY.WHOLE=TB;
__RSI=KEY.SPLIT.LWORDS[0];
__RDI=KEY.SPLIT.LWORDS[1];
__asm__ __volatile__(
"movq %0, %%rax \n\t"
"movq %1, %%rdx \n\t"
"movq %2, %%rsi \n\t"
"movq %3, %%rdi \n\t"
"movq %%rsi, %%rbx \n\t"
"movq %%rdi, %%rcx \n\t"
"movq %%rax, %%rsi \n\t"
"movq %%rdx, %%rdi \n\t"
"xorq %%rax, %%rax \n\t"
"xorq %%rdx, %%rdx \n\t"
"movq %%rdi, %%rax \n\t"
"mulq %%rbx \n\t"
"xchgq %%rbx, %%rax \n\t"
"mulq %%rsi \n\t"
"xchgq %%rax, %%rsi \n\t"
"addq %%rdx, %%rbx \n\t"
"mulq %%rcx \n\t"
"addq %%rax, %%rbx \n\t"
"movq %%rsi, %%rax \n\t"
"movq %%rbx, %%rdx \n\t"
"movq %%rax, %0 \n\t"
"movq %%rdx, %1 \n\t"
"movq %%rsi, %2 \n\t"
"movq %%rdi, %3 \n\t"
: "=m"(__RAX),"=m"(__RDX),"=m"(__RSI),"=m"(__RDI)
: "m"(__RAX), "m"(__RDX), "m"(__RSI), "m"(__RDI)
: "rax","rbx","ecx","rdx","rsi","rdi"
);
KEY.SPLIT.LWORDS[0]=__RAX;
KEY.SPLIT.LWORDS[1]=__RDX;
RESULT=KEY.WHOLE;
return RESULT;
}
