ARM assembly 12: GCD（最大公约数）计算

首先，我们看看GCD(Greatest Common Divisor)的CPP实现

int gcd(int a, int b)
{if(b == 0) return a;return gcd(b, a%b);	
}

 基于下面的gcd.s文件，我们尝试实现gcd函数

//gcd.s
.global main
.extern fopen, fprintf, fclose, printf, atoi.section .data
filename: .asciz "nums.txt"
write_mode: .asciz "w"
format_str: .asciz "%d\n".section .textprint_num_to_file:push {lr}push {r0-r5}mov r5, r0// Open the file for writingldr r0, =filenameldr r1, =write_modebl fopenmov r4, r0               // Store the file pointer in r4// Check if fopen succeededcmp r4, #0beq close_file// Write the number to the filemov r0, r4ldr r1, =format_strmov r2, r5bl fprintf// Close the file
close_file:mov r0, r4bl fclosepop {r0-r5}pop {pc}gcd:push {lr} // Replace this with your code! Return value goes in r0mov r0, #-1end_gcd:pop {pc}main:push {r4-r7, lr}// Check if argument count (argc) is correctcmp r0, #3             // Expecting 3 arguments (program name and two operands)blt exit// Convert argument strings to integerspush {r1}ldr r0, [r1, #4]       // Load address of second argument (first operand)bl atoi                // Convert string to integermov r4, r0pop {r1}push {r4}ldr r0, [r1, #8]       // Load address of third argument (second operand)bl atoi                // Convert string to integermov r5, r0pop {r4}// Calculate the gcd of both operandsmov r0, r4mov r1, r5bl gcd// Print gcd result to our filebl print_num_to_fileexit:// Exitmov r0, #0pop {r4-r7, pc}

接下来，我们尝试实现gcd函数

gcd:push {lr} // Base case// if (b == 0) return acmp r1, #0beq end_gcd// Recursive case// return gcd(b, a % b)// Compute a % bsdiv r2, r0, r1mul r3, r2, r1sub r4, r0, r3          // r4 now contains the modulus// Now compute gcd(b, a % b)mov r0, r1mov r1, r4bl gcd

基于gcd.s,我们可以看到，gcd函数的两个参数可以分别被传入到r0,r1寄存器中，然后，我们可以基于此实现base case，也就是上述代码中 b == 0的情况。

gcd:push {lr}// Base case// if (b ==0) {returan a;} cmp r1, #0beq end_gcd// Recursice case

值得注意的是，ARM汇编中，不直接支持modulus operation。所以，我们要进行相对复杂的等价转换。

a % b = a - (a / b) * bint division = a/b;
int product = division * b;
int remainder = a - product;

我们尝试在汇编中实现上述逻辑，没有什么难点，需要注意SDIV用于实现 signed integer division

//Recursice case
//return gcd(b, a%b)//a%b
// int division = a/b;
// int product = division *b;
// int remainder = a - product;sdiv r2, r0, r1
mul r3, r2, r1
sub r4, r0, r3

 在完成了recursive中参数的计算后，我们需要把它们分别传入r0,r1(现在它们在r1和r4).接下来，利用bl操作执行迭代操作。

mov r0, r1
mov r1, r4
bl gcd

执行

as gcd.s -o gcd.ogcc --static gcd.o  gcd./gcd

在nums.txt中，我们可以看到