---
# System prepended metadata

title: 2019-MPSL Lab2

---

# 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)