AVR Assembly 中的递归是如何实现的？
How is recursion possible in AVR Assembly?
我似乎无法完全理解汇编语言中的递归。我了解它在高级语言中的工作原理，但我不明白当 return 值无法直接传递给函数时如何在汇编中实现。
我正在尝试在 AVR 中创建递归阶乘函数，但我不明白当阶乘需要 n * (n-1) 时堆栈如何传递值，同时需要 n 和 n-1
用加法代替乘法
unsigned int accumulate(unsigned int n)
{
if(n) return(n+accumulate(n-1));
return(1);
}
和不同的指令集，可能更容易理解
00000000 <accumulate>:
0: e3500000 cmp r0, #0
4: 0a000005 beq 20 <accumulate+0x20>
8: e3a03000 mov r3, #0
c: e0833000 add r3, r3, r0
10: e2500001 subs r0, r0, #1
14: 1afffffc bne c <accumulate+0xc>
18: e2830001 add r0, r3, #1
1c: e12fff1e bx lr
20: e3a00001 mov r0, #1
24: e12fff1e bx lr
在这种情况下，编译器实际上并没有调用函数，它检测到发生了什么，只是做了一个循环。
由于递归并没有什么神奇之处，因此无论您调用相同的函数还是调用其他函数都没有区别。
unsigned int otherfun ( unsigned int );
unsigned int accumulate(unsigned int n)
{
if(n) return(n+otherfun(n-1));
return(1);
}
00000000 <accumulate>:
0: e92d4010 push {r4, lr}
4: e2504000 subs r4, r0, #0
8: 03a00001 moveq r0, #1
c: 0a000002 beq 1c <accumulate+0x1c>
10: e2440001 sub r0, r4, #1
14: ebfffffe bl 0 <otherfun>
18: e0800004 add r0, r0, r4
1c: e8bd4010 pop {r4, lr}
20: e12fff1e bx lr
所以这说明了它是如何工作的。如果你有寄存器，而不是使用堆栈来存储总和，更便宜的解决方案是使用非易失性寄存器将该寄存器保存到堆栈然后在函数期间使用该寄存器，这取决于你有多少寄存器以及有多少您需要跟踪的本地中间值。所以 r4 得到一个 n 的副本，然后将其添加到 return 调用下一个函数的值（使用递归，编译器没有弄清楚我们在做什么，这本来是对我们自己的调用，我们可以编写这个 asm 并让它成为对我们自己的调用，看看它是如何实现的作品）
然后函数 return求和。
如果我们假设 otherfun 确实是 accumulate，我们输入这个函数时输入 4 让我们说
00000000 <accumulate>:
0: e92d4010 push {r4, lr}
4: e2504000 subs r4, r0, #0
8: 03a00001 moveq r0, #1
c: 0a000002 beq 1c <accumulate+0x1c>
10: e2440001 sub r0, r4, #1
14: ebxxxxxx bl accumulate
18: e0800004 add r0, r0, r4
1c: e8bd4010 pop {r4, lr}
20: e12fff1e bx lr
r4 and lr are saved on the stack (call this r4-4 and lr-4)
r4 = n (4)
r0 = n-1 (3)
call accumulate with n-1 (3)
r4 (4) and lr are saved on the stack (r4-3, lr-3) lr now points back into
r4 = n (3)
r0 = n-1 (2)
call accumulate with n-1 (2)
r4 (3) and lr are saved on the stack (r4-2, lr-2)
r4 = n (2)
r0 = n-1 (1)
call accumulate with n-1 (1)
r4 (2) and lr are saved on the stack (r4-1, lr-1)
r0 = n-1 (0)
call accumulate with n-1 (0)
now things change...
r0 = 1
return to lr-1 which is into accumulate after the call to accumulate
r4 gets 2 from the stack
r0 (1) = r0 (1) + r4 (2) = 3
return to lr-2 which is into accumulate r4 gets 3 from the stack
r0 (3) = r0 (3) + r4 (3) = 6
return to lr-3 which is into accumulate r4 gets 4 from the stack
r0 (6) = r0 (6) + r4 (4) = 10
return to lr-4 which is the function that called accumulate r4 is restored
to what it was before accumulate was first called, r4 is non-volatile you have to for this instruction set return r4 the way you found it (as well
as others, but we didnt modify those)
所以在你想要的情况下，这种情况下的加法是
结果 = 1 + 2 + 3 + 4
这是怎么发生的，我们基本上是将 n 压入堆栈，然后用 n-1 调用函数。在这种情况下，我们推 4、3、2、1 然后我们开始展开它，每个 return 处理 1 然后 2 然后 3 然后 4 因为它 returns
本质上是从堆栈中取出那些。
底线是你不必关心递归支持递归只需使用支持递归的abi，这并不难
做，然后像编译器一样在汇编中手动编写指令
也许这样更容易看清。 n coming in 既是一个参数进来，也是函数运行期间它是一个局部变量，local
变量进入堆栈。
unsigned int accumulate(unsigned int n)
{
unsigned int m;
m = n;
if(n) return(m+accumulate(n-1));
return(1);
}
回到这里
unsigned int accumulate(unsigned int n)
{
if(n) return(n+accumulate(n-1));
return(1);
}
如此独立于指令集
accumulate:
if(n!=0) jump over
return_reg = 1
return
over:
push n on the stack
first parameter (stack or register) = n - 1
call accumulate
pop or load n from the stack
return_reg = return_reg + n
clean stack
return
如果需要，还可以处理指令集的 return 地址。
ABI 可以使用堆栈来传递参数或寄存器。
如果我不遵循 arm abi 我可以实现
accumulate:
cmp r0,#0
bne over
mov r0,#1
bx lr
over:
push {lr}
push {r0}
sub r0,#1
bl accumulate
pop {r1}
add r0,r0,r1
pop {lr}
bx lr
for grins 指令集使用堆栈来处理大多数事情，而不是
寄存器
00000000 <_accumulate>:
0: 1166 mov r5, -(sp)
2: 1185 mov sp, r5
4: 10a6 mov r2, -(sp)
6: 1d42 0004 mov 4(r5), r2
a: 0206 bne 18 <_accumulate+0x18>
c: 15c0 0001 mov , r0
10: 1d42 fffc mov -4(r5), r2
14: 1585 mov (sp)+, r5
16: 0087 rts pc
18: 1080 mov r2, r0
1a: 0ac0 dec r0
1c: 1026 mov r0, -(sp)
1e: 09f7 ffde jsr pc, 0 <_accumulate>
22: 6080 add r2, r0
24: 65c6 0002 add , sp
28: 1d42 fffc mov -4(r5), r2
2c: 1585 mov (sp)+, r5
2e: 0087 rts pc
it does a stack frame thing
gets the n parameter from the stack
saves that n parameter to the stack
compares and branches if not zero
in the if zero case we set the return value to 1
clean up the stack and return
now in the if not zero case
make the first parameter n-1
call a function (ourself)
do the addition and return
我刚刚用下面的小代码帮助另一个人计算 AVR AtMega 程序集中的阶乘。
它产生 1~10 的阶乘，结果为十进制 3628800（十六进制 0x375F00）。
如果选择 8，它使用的正是 OP 想要的！作为数字！在R2中，它会将8移动到结果字节，然后乘以数字！-1等等，直到达到1，然后结束。乘法 24x8 是我能写的最棘手的，它节省了寄存器和时钟周期。不使用栈和RAM，直接使用AVR寄存器。
; Input at R2, value 1~10, from 1! to 10!
; Result 1~3628800 (0x375F00) at: R20:R21:R22 (LSB)
; Temporary Multiplication Middle Byte: R17
ldi r16, low(RAMEND)
out SPL, r16
ldi r16, high(RAMEND)
out SPH, r16
Mov R16, R2 ; Get Value to factor
Rcall A0 ; Call Factorial
...
A0: Clr R20 ; Results = Number!
Clr R21 ;
Ldi R22, R16 ;
A1: Dec R16 ; Number! - 1
Cpi R16,1 ; If 1 then ended
Brne A2 ;
Ret
; This multiplication 24x8 is tricky, fast and save bytes
A2: Mul R22, R16 ; Mul Result LSB x Number!-1
Mov R22, R0 ; LSB Mul to Result LSB Byte
Mov R17, R1 ; MSB Mul to Temporary Middle Byte
Mul R20, R16 ; Mul Result MSB x Number!-1
Mov R20, R0 ; LSB Mul to MSB Result Byte, ignore MSB Mul, will be zero
Mul R21, R16 ; Mul Result Middle x Number!-1
Mov R21, R0 ; LSB Mul to Result Middle Byte
Add R21, R17 ; Add Temporary Middle to Result Middle Byte
Adc R20, R1 ; Add MSB Mul with Carry to Result MSB Byte
Rjmp A1
我似乎无法完全理解汇编语言中的递归。我了解它在高级语言中的工作原理，但我不明白当 return 值无法直接传递给函数时如何在汇编中实现。
我正在尝试在 AVR 中创建递归阶乘函数，但我不明白当阶乘需要 n * (n-1) 时堆栈如何传递值，同时需要 n 和 n-1
用加法代替乘法
unsigned int accumulate(unsigned int n)
{
if(n) return(n+accumulate(n-1));
return(1);
}
和不同的指令集，可能更容易理解
00000000 <accumulate>:
0: e3500000 cmp r0, #0
4: 0a000005 beq 20 <accumulate+0x20>
8: e3a03000 mov r3, #0
c: e0833000 add r3, r3, r0
10: e2500001 subs r0, r0, #1
14: 1afffffc bne c <accumulate+0xc>
18: e2830001 add r0, r3, #1
1c: e12fff1e bx lr
20: e3a00001 mov r0, #1
24: e12fff1e bx lr
在这种情况下，编译器实际上并没有调用函数，它检测到发生了什么，只是做了一个循环。
由于递归并没有什么神奇之处，因此无论您调用相同的函数还是调用其他函数都没有区别。
unsigned int otherfun ( unsigned int );
unsigned int accumulate(unsigned int n)
{
if(n) return(n+otherfun(n-1));
return(1);
}
00000000 <accumulate>:
0: e92d4010 push {r4, lr}
4: e2504000 subs r4, r0, #0
8: 03a00001 moveq r0, #1
c: 0a000002 beq 1c <accumulate+0x1c>
10: e2440001 sub r0, r4, #1
14: ebfffffe bl 0 <otherfun>
18: e0800004 add r0, r0, r4
1c: e8bd4010 pop {r4, lr}
20: e12fff1e bx lr
所以这说明了它是如何工作的。如果你有寄存器，而不是使用堆栈来存储总和，更便宜的解决方案是使用非易失性寄存器将该寄存器保存到堆栈然后在函数期间使用该寄存器，这取决于你有多少寄存器以及有多少您需要跟踪的本地中间值。所以 r4 得到一个 n 的副本，然后将其添加到 return 调用下一个函数的值（使用递归，编译器没有弄清楚我们在做什么，这本来是对我们自己的调用，我们可以编写这个 asm 并让它成为对我们自己的调用，看看它是如何实现的作品）
然后函数 return求和。
如果我们假设 otherfun 确实是 accumulate，我们输入这个函数时输入 4 让我们说
00000000 <accumulate>:
0: e92d4010 push {r4, lr}
4: e2504000 subs r4, r0, #0
8: 03a00001 moveq r0, #1
c: 0a000002 beq 1c <accumulate+0x1c>
10: e2440001 sub r0, r4, #1
14: ebxxxxxx bl accumulate
18: e0800004 add r0, r0, r4
1c: e8bd4010 pop {r4, lr}
20: e12fff1e bx lr
r4 and lr are saved on the stack (call this r4-4 and lr-4)
r4 = n (4)
r0 = n-1 (3)
call accumulate with n-1 (3)
r4 (4) and lr are saved on the stack (r4-3, lr-3) lr now points back into
r4 = n (3)
r0 = n-1 (2)
call accumulate with n-1 (2)
r4 (3) and lr are saved on the stack (r4-2, lr-2)
r4 = n (2)
r0 = n-1 (1)
call accumulate with n-1 (1)
r4 (2) and lr are saved on the stack (r4-1, lr-1)
r0 = n-1 (0)
call accumulate with n-1 (0)
now things change...
r0 = 1
return to lr-1 which is into accumulate after the call to accumulate
r4 gets 2 from the stack
r0 (1) = r0 (1) + r4 (2) = 3
return to lr-2 which is into accumulate r4 gets 3 from the stack
r0 (3) = r0 (3) + r4 (3) = 6
return to lr-3 which is into accumulate r4 gets 4 from the stack
r0 (6) = r0 (6) + r4 (4) = 10
return to lr-4 which is the function that called accumulate r4 is restored
to what it was before accumulate was first called, r4 is non-volatile you have to for this instruction set return r4 the way you found it (as well
as others, but we didnt modify those)
所以在你想要的情况下，这种情况下的加法是
结果 = 1 + 2 + 3 + 4
这是怎么发生的，我们基本上是将 n 压入堆栈，然后用 n-1 调用函数。在这种情况下，我们推 4、3、2、1 然后我们开始展开它，每个 return 处理 1 然后 2 然后 3 然后 4 因为它 returns 本质上是从堆栈中取出那些。
底线是你不必关心递归支持递归只需使用支持递归的abi，这并不难 做，然后像编译器一样在汇编中手动编写指令
也许这样更容易看清。 n coming in 既是一个参数进来，也是函数运行期间它是一个局部变量，local 变量进入堆栈。
unsigned int accumulate(unsigned int n)
{
unsigned int m;
m = n;
if(n) return(m+accumulate(n-1));
return(1);
}
回到这里
unsigned int accumulate(unsigned int n)
{
if(n) return(n+accumulate(n-1));
return(1);
}
如此独立于指令集
accumulate:
if(n!=0) jump over
return_reg = 1
return
over:
push n on the stack
first parameter (stack or register) = n - 1
call accumulate
pop or load n from the stack
return_reg = return_reg + n
clean stack
return
如果需要，还可以处理指令集的 return 地址。 ABI 可以使用堆栈来传递参数或寄存器。
如果我不遵循 arm abi 我可以实现
accumulate:
cmp r0,#0
bne over
mov r0,#1
bx lr
over:
push {lr}
push {r0}
sub r0,#1
bl accumulate
pop {r1}
add r0,r0,r1
pop {lr}
bx lr
for grins 指令集使用堆栈来处理大多数事情，而不是 寄存器
00000000 <_accumulate>:
0: 1166 mov r5, -(sp)
2: 1185 mov sp, r5
4: 10a6 mov r2, -(sp)
6: 1d42 0004 mov 4(r5), r2
a: 0206 bne 18 <_accumulate+0x18>
c: 15c0 0001 mov , r0
10: 1d42 fffc mov -4(r5), r2
14: 1585 mov (sp)+, r5
16: 0087 rts pc
18: 1080 mov r2, r0
1a: 0ac0 dec r0
1c: 1026 mov r0, -(sp)
1e: 09f7 ffde jsr pc, 0 <_accumulate>
22: 6080 add r2, r0
24: 65c6 0002 add , sp
28: 1d42 fffc mov -4(r5), r2
2c: 1585 mov (sp)+, r5
2e: 0087 rts pc
it does a stack frame thing
gets the n parameter from the stack
saves that n parameter to the stack
compares and branches if not zero
in the if zero case we set the return value to 1
clean up the stack and return
now in the if not zero case
make the first parameter n-1
call a function (ourself)
do the addition and return
我刚刚用下面的小代码帮助另一个人计算 AVR AtMega 程序集中的阶乘。 它产生 1~10 的阶乘，结果为十进制 3628800（十六进制 0x375F00）。 如果选择 8，它使用的正是 OP 想要的！作为数字！在R2中，它会将8移动到结果字节，然后乘以数字！-1等等，直到达到1，然后结束。乘法 24x8 是我能写的最棘手的，它节省了寄存器和时钟周期。不使用栈和RAM，直接使用AVR寄存器。
; Input at R2, value 1~10, from 1! to 10!
; Result 1~3628800 (0x375F00) at: R20:R21:R22 (LSB)
; Temporary Multiplication Middle Byte: R17
ldi r16, low(RAMEND)
out SPL, r16
ldi r16, high(RAMEND)
out SPH, r16
Mov R16, R2 ; Get Value to factor
Rcall A0 ; Call Factorial
...
A0: Clr R20 ; Results = Number!
Clr R21 ;
Ldi R22, R16 ;
A1: Dec R16 ; Number! - 1
Cpi R16,1 ; If 1 then ended
Brne A2 ;
Ret
; This multiplication 24x8 is tricky, fast and save bytes
A2: Mul R22, R16 ; Mul Result LSB x Number!-1
Mov R22, R0 ; LSB Mul to Result LSB Byte
Mov R17, R1 ; MSB Mul to Temporary Middle Byte
Mul R20, R16 ; Mul Result MSB x Number!-1
Mov R20, R0 ; LSB Mul to MSB Result Byte, ignore MSB Mul, will be zero
Mul R21, R16 ; Mul Result Middle x Number!-1
Mov R21, R0 ; LSB Mul to Result Middle Byte
Add R21, R17 ; Add Temporary Middle to Result Middle Byte
Adc R20, R1 ; Add MSB Mul with Carry to Result MSB Byte
Rjmp A1