计算装配 x86 中的 LCM
Calculating LCM in assembly x86
我有以下汇编代码
.global _start
.section .text
_start:
movq a, %rax
movq b, %rbx
imul %rbx, %rax
cmp %rbx, %rax
je gcd_calculated
ja l1
sub %rax, %rbx
jmp _start
l1:
sub %rbx, %rax
jmp _start
gcd_calculated:
div %rax
movq %rax, (c)
a,b
是四边形,我需要计算它们的 lcm,我需要将结果分配给 c
我用上面的代码得到了错误的结果,我无法找出原因。
一般来说,我在 lcm = (a*b)/gcd
上进行中继,所以我将 a*b 存储在 %rax
中,然后计算将存储在 %eax 中的 gcd,最后在它们之间进行划分。
如 1201ProgramAlarm 所说,您正在计算和比较循环的每次迭代中 a
和 b
的原始值。如果您想遵循当前的方法,则每次循环之前都必须将这些值存储在内存中。
我实际上要做的是先进行 gcd 计算,然后在最后计算 (a*b)/gcd
。
_start:
movq a(%rip), %rbx
movq b(%rip), %rcx
gcd:
cmp %rbx, %rcx
je gcd_calculated
ja l1
sub %rcx, %rbx
jmp gcd
l1:
sub %rbx, %rcx
jmp gcd
gcd_calculated:
movq a(%rip), %rax
xor %rdx, %rdx
div %rbx
imul b(%rip), %rax
movq %rax, c(%rip)
/* x86-64 gcc / clang support the __int128 type: */
/*
#include <stdint.h>
unsigned __int128 lcm (uint64_t a, uint64_t b)
{
uint64_t u = a, v = b;
for (uint64_t t = 0; (t = v) != 0; u = t)
v = u % v;
if (u != 0) /* gcd(a, b) != (0) : */
return (((unsigned __int128) a) * (b / u));
return (0);
}
*/
/* x86-64 Mach-O (OSX) / ELF calling conventions:
* first arg (a) in %rdi, second arg (b) in %rsi;
* 128-bit integer returned in %rdx:%rax [hi:lo] */
/* no caller-reserved registers or stack are used: */
.text
.globl _lcm
_lcm:
movq %rdi, %r8
movq %rsi, %rdi
movq %r8, %rcx
L_gcd:
testq %rdi, %rdi
je L_lcm # %rcx = gcd(a, b)
movq %rcx, %rax
xorl %edx, %edx
movq %rdi, %rcx
divq %rdi
movq %rdx, %rdi
jmp L_gcd
L_lcm: # lcm(0, 0) returns (0) :
xorl %eax, %eax
xorl %edx, %edx
testq %rcx, %rcx # if gcd(a, b) == 0, then:
je L_done # %rdx:%rax = 0:0; return.
movq %rsi, %rax
xorl %edx, %edx # %rdx:%rax = 0:b
divq %rcx # %rax = (b / g)
mulq %r8 # %rdx:%rax = a * (b / g)
L_done:
ret
我有以下汇编代码
.global _start
.section .text
_start:
movq a, %rax
movq b, %rbx
imul %rbx, %rax
cmp %rbx, %rax
je gcd_calculated
ja l1
sub %rax, %rbx
jmp _start
l1:
sub %rbx, %rax
jmp _start
gcd_calculated:
div %rax
movq %rax, (c)
a,b
是四边形,我需要计算它们的 lcm,我需要将结果分配给 c
我用上面的代码得到了错误的结果,我无法找出原因。
一般来说,我在 lcm = (a*b)/gcd
上进行中继,所以我将 a*b 存储在 %rax
中,然后计算将存储在 %eax 中的 gcd,最后在它们之间进行划分。
如 1201ProgramAlarm 所说,您正在计算和比较循环的每次迭代中 a
和 b
的原始值。如果您想遵循当前的方法,则每次循环之前都必须将这些值存储在内存中。
我实际上要做的是先进行 gcd 计算,然后在最后计算 (a*b)/gcd
。
_start:
movq a(%rip), %rbx
movq b(%rip), %rcx
gcd:
cmp %rbx, %rcx
je gcd_calculated
ja l1
sub %rcx, %rbx
jmp gcd
l1:
sub %rbx, %rcx
jmp gcd
gcd_calculated:
movq a(%rip), %rax
xor %rdx, %rdx
div %rbx
imul b(%rip), %rax
movq %rax, c(%rip)
/* x86-64 gcc / clang support the __int128 type: */
/*
#include <stdint.h>
unsigned __int128 lcm (uint64_t a, uint64_t b)
{
uint64_t u = a, v = b;
for (uint64_t t = 0; (t = v) != 0; u = t)
v = u % v;
if (u != 0) /* gcd(a, b) != (0) : */
return (((unsigned __int128) a) * (b / u));
return (0);
}
*/
/* x86-64 Mach-O (OSX) / ELF calling conventions:
* first arg (a) in %rdi, second arg (b) in %rsi;
* 128-bit integer returned in %rdx:%rax [hi:lo] */
/* no caller-reserved registers or stack are used: */
.text
.globl _lcm
_lcm:
movq %rdi, %r8
movq %rsi, %rdi
movq %r8, %rcx
L_gcd:
testq %rdi, %rdi
je L_lcm # %rcx = gcd(a, b)
movq %rcx, %rax
xorl %edx, %edx
movq %rdi, %rcx
divq %rdi
movq %rdx, %rdi
jmp L_gcd
L_lcm: # lcm(0, 0) returns (0) :
xorl %eax, %eax
xorl %edx, %edx
testq %rcx, %rcx # if gcd(a, b) == 0, then:
je L_done # %rdx:%rax = 0:0; return.
movq %rsi, %rax
xorl %edx, %edx # %rdx:%rax = 0:b
divq %rcx # %rax = (b / g)
mulq %r8 # %rdx:%rax = a * (b / g)
L_done:
ret