# 2019-MPSL Lab2
> 2019 Fall Microprocessor System Lab
> Lab2 ARM Assembly II
> [name=0516009 吳宗達、0616015 劉姿利]
## What to Do
- Learning how to use stack pointer `SP`
- Learning how to implement recursion with stack in assembly language
- Finishing 2 tasks
- Postfix arithmetic
- GCD and the Stack Size
## How to Do
### Postfix Arithmetic
```cpp=
.syntax unified
.cpu cortex-m4
.thumb
.data
user_stack_bottom: .zero 128
expr_result: .word 0
.text
.global main
postfix_expr: .asciz "-100 10 20 + - 10 +"
// R0: address
// R1: ptr
// R2: value
// R3: pop, push
// R4: pop
// R5: ten
main:
ldr SP, =user_stack_bottom
add SP, #128
ldr R0, =postfix_expr
mov R1, #0
LOOP:
ldrb R2, [R0, R1]
// \0
cmp R2, #0
it eq
bleq END
// space
cmp R2, #32
itt eq
addeq R1, #1
beq LOOP
// add
cmp R2, #43
it eq
beq ADD
// sub
cmp R2, #45
it eq
beq SUB
b NUM
ADD:
pop {R3, R4}
add R3, R4
push {R3}
add R1, #1
b LOOP
SUB:
add R1, #1
ldrb R2, [R0, R1]
cmp R2, #32
it eq
beq SUB_OP
cmp R2, #0
it eq
beq SUB_OP
it ne
bne SUB_NUM
SUB_NUM:
bl atoi
sub R12, #1
mvn R12, R12
push {R12}
b LOOP
SUB_OP:
pop {R3, R4}
sub R4, R3
push {R4}
b LOOP
NUM:
bl atoi
push {R12}
b LOOP
END:
pop {R2}
ldr R0, =expr_result
str R2, [R0]
L:
nop
b L
// R12: return value
// R5: ten
atoi:
mov R12, #0
mov R5, #10
ATOI_LOOP:
ldrb R2, [R0, R1]
add R1, #1
// break
cmp R2, #32
it eq
bxeq LR
cmp R2, #0
it eq
bxeq LR
mul R12, R5
sub R2, #48
add R12, R2
b ATOI_LOOP
bx LR
```
#### Sample Testcase
```
45 49 48 48 32 49 48 32 50 48 32 43 32 45 32 49 48 32 43 00
- 1 0 0 1 0 2 0 + - 1 0 + \0
```
#### `.zero` 意義
```cpp
user_stack_bottom: .zero 128
```
宣告 128 個 bytes 的空間並把他們初始化為 0。
#### `SP` Configuration
```cpp
ldr SP, =user_stack_bottom
add SP, #128
```
將 `SP` 移到 `user_stack_bottom` 的位址並往後移 128 個 byte，因為 `stack` `push` 和 `pop` 的操作是以 `SP` 為 base，從高位開始使用，所以要先加到高位的 address 上去。
#### `atoi` Implementation
- `R0`: Begin address of `postfix_expr`
- `R1`: Index of `postfix_expr` （`postfix_expr` 中第幾個 byte）
- `R2`: 位於 `R0` + `R1` 位址的 value
- `R5`: Const integer 10
- `R12`: Return value
```cpp
atoi:
mov R12, #0 // 初始化 return value 為 0
mov R5, #10 // 設 R5 為 10
ATOI_LOOP:
ldrb R2, [R0, R1] // 取出位於 R0 + R1 位址的 value
add R1, #1 // index++
// break: 遇到 space 或 \0 則返回
cmp R2, #32 // space
it eq
bxeq LR
cmp R2, #0 // \0
it eq
bxeq LR
mul R12, R5 // R12 *= 10
sub R2, #48 // R2 -= '0'
add R12, R2 // R12 += R2
b ATOI_LOOP
bx LR
```
#### Get 2's Complement
```cpp
sub R12, #1
mvn R12, R12
```
如果要將 `R12` 中的字轉成 2's complement，要先將 `R12` 減 1 然後取 1's complement。
#### Postfix Arithmetic Using Stack
`push` 和 `pop` 在 memory 位址中與目標 register index 的大小關係為：
- `push`: 由高位到低位，優先將 register index 大的 push 到 memory 中
- `pop`: 由低位到高位，優先 pop 到 index 小的 register 上
##### `push` Number
```cpp
push {R12}
```
##### `pop`: 加法
```cpp
pop {R3, R4}
add R3, R4
push {R3}
```
##### `push`: 減法
```cpp
pop {R3, R4}
sub R4, R3
push {R4}
```
因為 `pop` 會將後丟進 stack 的值優先放入 register index 小的 `R3` 中，但是我們要用「先放入 stack 的值」減去「後放入 stack 的值」，所以要拿 `R4` 減去 `R3`，至於加法有交換律則沒有這個問題。
### GCD and the Stack Size
```cpp=
.syntax unified
.cpu cortex-m4
.data
result: .word 0
max_size: .word 0
.text
m: .word 0x5E // 94
n: .word 0x60 // 96
.global main
// R0: address
// R1: a
// R2: b
// R3: modified a
// R4: modified b
// R5: a % 2
// R6: b % 2
// R7: return value
// R8: SP
/* start GCD */
GCD:
// push
push {LR}
mov R8, SP
// return cases
cmp R1, #0
itt eq
moveq R7, R2
popeq {PC}
cmp R2, #0
itt eq
moveq R7, R1
popeq {PC}
// compare
and R5, R1, #1
and R6, R2, #1
orr R3, R5, R6
cmp R3, #0
asr R3, R1, #1
asr R4, R2, #1
// recursion cases
case1:
it ne
bne case2
mov R1, R3
mov R2, R4
bl GCD
lsl R7, #1
pop {PC}
case2:
cmp R5, #0
it ne
bne case3
mov R1, R3
bl GCD
pop {PC}
case3:
cmp R6, #0
it ne
bne case4
mov R2, R4
bl GCD
pop {PC}
case4:
cmp R1, R2
ittee ge
subge R3, R1, R2
movge R4, R2
sublt R3, R2, R1
movlt R4, R1
mov R1, R3
mov R2, R4
bl GCD
pop {PC}
/* end GCD */
main:
ldr R0, =m
ldr R1, [R0]
ldr R0, =n
ldr R2, [R0]
bl GCD
ldr R0, =result
str R7, [R0]
sub R8, SP, R8
ldr R0, =max_size
str R8, [R0]
nop
nop
L:
b L
```
#### GCD Code in C
```cpp
int GCD(int a, int b) {
// return cases
if (a == 0) return b;
if (b == 0) return a;
// recursion cases
if (a % 2 == 0 && b % 2 == 0) // case1
return 2 * GCD (a >> 1, b >> 1);
else if (a % 2 == 0) // case2
return GCD(a >> 1, b);
else if (b % 2 == 0) // case3
return GCD(a, b >> 1);
else // case4
return GCD(abs(a - b), min(a, b));
}
```
#### GCD 的 parameters 使用
我們將 `R1` 和 `R2` 分別代表 GCD 的 parameters `a` 和 `b`，在進入 recursion `bl GCD` 之前，要先將需要的 parameters 移進 `R1` 和 `R2` 中。
以下以 case4 為例。
```cpp
// e.g. case4
mov R1, R3 // R3 = (a >> 1)
mov R2, R4 // R4 = (b >> 1)
bl GCD
```
#### push 和 pop 的使用
##### push
```cpp
GCD:
push {LR}
...
```
每次一進入 GCD 就馬上把 return link `LR` 存起來，因為 recursion 時再次呼叫 `bl GCD` 會把原本在 `LR` 上的值覆蓋掉。
##### pop
```cpp
pop {PC}
```
當要 return 的時候直接使用上面這行讓 `PC` 直接跳回 return link `LR`。
#### max_size 的計算
```cpp
push {LR}
mov R8, SP
```
每次 push 完將新的 `SP` 值存到 `R8` 裡面。
因為每一層 `GCD` 的 recursion 只會往下長出一個下一層的 `GCD`，所以 `R8` 的值只會越來越小。
```cpp
sub R8, SP, R8
ldr R0, =max_size
str R8, [R0]
```
計算 `max_size` 要將 `SP` 和 `R8` （遞迴途中 `SP` 的最小值）相減，再存到記憶體中。
## Feedback
這次 Lab 完成之後有更了解 `push` 跟 `pop` 的運作，尤其是他們在 recursion 中扮演的角色。
原先以為 push 到 stack 上的值是要傳遞到下一層的 parameters，後來才發現真正的目的是要保存目前的狀態，return 之後才可以繼續用。
另外一個比較有收穫的就是 ascii 在 memory 中的配置還有字串的處理，對於在 assembly language 中沒有型態只有記憶體與數值的架構感覺有點新奇。
## Reference
- [Assembler Directives](https://docs.oracle.com/cd/E26502_01/html/E28388/eoiyg.html)
Sign in with Wallet
Connect another wallet