---
# System prepended metadata

title: 2019-MPSL Lab1

---

# 2019-MPSL Lab1

> 2019 Fall Microprocessor System Lab
> Lab1 ARM Assembly I
> [name=0516009 吳宗達、0616015 劉姿利]

## What to Do

- Hamming Distance：計算兩個數長度為 2-bytes 的 hamming distance，並將結果存放至 result 變數中
- Fibonacci Serial：宣告一數值N (1≤N≤100)，計算 Fib(N) 並將回傳值存放至 R4 暫存器
- Bubble Sort：每個 byte 為一個數字，利用組合語言完成長度為 8-byte bubble sort

## How to Do

### Hamming Distance

```asm=
.data
	result: .byte 0
	X: .word 0x55AA
	Y: .word 0xAA55
	One: .word 0x0001

.text
	.global main

hamm:
	movs R2, R1
	and R2, R3
	add R4, R2
	asr R1, R1, #1
	cmp R1, #0
 	bne hamm
	bx lr

main:
	ldr R0, =X
	ldr R1, [R0] // R1 = X
	ldr R0, =Y
	ldr R2, [R0] // R2 = Y
	ldr R0, =One
	ldr R3, [R0]
	eor R1, R1, R2

	ldr R0, =result
	ldrb R4, [R0]

	bl hamm

	strb R4, [R0]

L:
	b L
```

#### Assemble Error in Original Code
```
movs R0, #X
```
- **The Error**
  mov 用法 (manual 3.5.6 on page 89)
  ```
  MOV{S}{cond} Rd, Operand2
  ```
  其中 `Operand2` 參考 manual (3.3.3 on page 60) 裡面寫到將 constant 作為 `Operand2` 的四種形式：
  - 能夠從 8-bit 數字向左 shift 成的 word
  - Form `0x00XY00XY`
  - Form `0xXY00XY00`
  - Form `0xXYXYXYXY`
  
  然而 `X` 為 `0x55AA` 並不在上面任何一個裡面，才會出現 error
- **Solution**
  在 `movs` 的方式行不通後，我們決定採用 `ldr`
  ```asm
  ldr R0, =X        // 將 X 的位址存到 R0
  ldr R1, [R0]      // 將 X 的值存入 R1
  ```
  就可以順利把數字存進 register 了
  
#### `cmp`, `bne` and Label out of Range

原本 15 至 16 行採用的是
```
bnez R1, hamm
```
但是 tag `hamm` 數值太大了會噴 label out of range
所以改成兩行的寫法

#### Load Byte

variable `result` 的資料類型為 `byte`，直接 `ldr` 的話會讀到不相關的位置（多讀到 3 個 byte）,所以在讀值跟存值（不包含讀址）的時候我們需要使用 `ldrb` 以及 `strb`

#### 計算 Word 內 1 的數量

以下是 function `hamm`
- 需要被計算 1 的數量的 word 資料被存在 `R1`
- `R3` 內的數值為 1
- 最後 1 的數量會被累加到答案 `R4` 上

```cpp
hamm:
    movs R2, R1        // 先複製一份 R1 到 R2
    and R2, R3         // R2 和 1 做 and 取得最低位的 bit 數值
    add R4, R2         // 將最低位加到答案上
    asr R1, R1, #1     // 將 R1 向右 shift 一位
    /* 以下三行表示如果 R1 等於 0 就從回圈出去 */
    cmp R1, #0
    bne hamm
    bx lr
```

### Fib
```asm=
.text
    .global main
    .equ N, 50

fib:
    movs R1, #0  // fib_0
    movs R2, #1  // fib_1

    movs R0, #0
    loopI :
        add R2, R1
        sub R1, R2, R1
        cmp R2, #0
        blt overflow_error
        add R0, #1
        cmp R0, #N
        blt loopI
    movs R4, R2
    bx lr

bound_check:
    cmp R0, #1      // N < 1
    blo range_error
    cmp R0, #100    // N > 100
    bgt range_error
    bx lr

range_error:
    movs R3, #0
    mvn R4, R3
    b end

overflow_error:
    movs R3, #1
    mvn R4, R3
    b end

main:
    movs R0, #N
    bl bound_check
    bl fib

end: b end
```
- 如何使用條件判斷
    - manual 3.3.7 Conditional execution
        ```asm
        // in C language
        if (a<b) { /* do something */ }
        
        // in asm
        cmp a, b
        blt do_something
        ```
    - line 14, 17, 22, 24 有用到條件判斷
    - 先做一次 compare, 下一行的指令就可以加上條件, 例如 line 21 先做了一次比較, line 22 裡本來的 `b` 指令就可以加上小於的判斷 `lo` 變成 `blo` 也就是先判斷上一個比較的結果是否滿足小於, 如果是才執行 `b`
- 實作迴圈
    ```asm
    // in C++
    for (int i=0; i<n; i++){
        // do something
    }
    
    // in asm
    movs R0, #0
	loopI :
        // do something
        add R0, #1
        cmp R0, #N
        blt loopI
	bx lr
    ```
- 如何設定負數 (overflow 將 R4 設成 -2, 輸入範圍錯誤將 R4 設成 -1)
    - `MVN` - manual 3.5.6 MOV and MVN
        > MOV{S}{cond} Rd, Operand2
        > MOV{cond} Rd, #imm16 // imm16’ is any value in the range 0—65535.
        > MVN{S}{cond} Rd, Operand2 
    - `MOV` 放常數只能放 0 - 65535, 不能設定 -1. 所以要利用 `MVN`, 而 `MVN` 不能直接放常數, 要接一個變數在後面, 像 line 28-29 先將 -1 的補數存到 R3, 再利用 `MVN` 將 R3 的 complement 存入 R4
- 執行
    - 按 F8 可以一次跑很多行 (跑到下一次遇到中斷點), 在結尾設定中斷點就可以直接看執行結果
- 測試資料
    - [x] n=0 (range error)
    - [x] n=1 1
    - [x] n=2 1
    - [x] n=3 2
    - [x] n=20 10946
    - [x] n=50 (overflow)
    - [x] n=101 (range error)

### Bubble Sort

```asm=
.data
	// arr1: .byte 8, 7, 6, 5, 4, 3, 2, 1
	arr1: .byte 0x19, 0x34, 0x14, 0x32, 0x52, 0x23, 0x61, 0x29
	arr2: .byte 0x18, 0x17, 0x33, 0x16, 0xFA, 0x20, 0x55, 0xAC

.text
	.global main

check_swap:
	ldrb R5, [R2]
	ldrb R6, [R3]
	cmp R5, R6
	ble end_check_swap
	strb R5, [R3]
	strb R6, [R2]
	end_check_swap:
	b ret_check_swap

do_sort:
	movs R1, #0
	movs R4, R0
	add R4, #8
	loopI:
		movs R2, R0
		add R3, R2, #1
		loopJ:
			b check_swap
			ret_check_swap:
			add R2, #1
			add R3, #1
			cmp R3, R4
			blt loopJ

		add R1, #1
		cmp R1, #8
		blt loopI
	bx lr

print:
	mov R1, #0
	ldrb r4, [R0, R1]
	add R1, #1
	ldrb r5, [R0, R1]
	add R1, #1
	ldrb r6, [R0, R1]
	add R1, #1
	ldrb r7, [R0, R1]
	add R1, #1
	ldrb r4, [R0, R1]
	add R1, #1
	ldrb r5, [R0, R1]
	add R1, #1
	ldrb r6, [R0, R1]
	add R1, #1
	ldrb r7, [R0, R1]
	bx lr

main:
	ldr r0, =arr1
	bl do_sort
	bl print
	ldr r0, =arr2
	bl do_sort
	bl print

end: b end
```

#### Load Byte with Offset
`ldr` 與 `str` 在 manual 3.4.3 on page 73 中的 syntax 為
```
op{type}{cond} Rt, [Rn, Rm {, LSL #n}]
```

當我們要取出一個 register 中特定位置的 byte
需要寫成

```
ldrb Rt, [Rn, Rm]
strb Rt, [Rn, Rm]
```

代表將以 `Rn` 為起點第 `Rm`(0 base) 個 byte load/store 值出來/進去


#### `lr` 覆蓋問題

##### Problem

bubble sort 的 functions 們設計如下
由 `main` function 呼叫 `do_sort` 再在 `do_sort` 中進行 `swap`

```graphviz
digraph{
    node [shape=circle]
    check_swap,do_sort,main
    main -> do_sort [color=blue]
    do_sort -> main [color=red]
    do_sort -> check_swap [color=blue]
    check_swap -> do_sort
}
```
但由於 `lr` register 只有一個，上圖兩個藍色箭頭都用 `bl` branch with link 過去的話，第二次 `bl` 會把 `do_sort` 返回 `main` 存放在 `lr` 內的 `pc` 位址洗掉，造成紅色箭頭沒辦法順利完成

##### Solution
```asm
check_swap:
	ldrb R5, [R2]
	ldrb R6, [R3]
	cmp R5, R6
	ble end_check_swap
	strb R5, [R3]
	strb R6, [R2]
	end_check_swap:
	b ret_check_swap

...

b check_swap
ret_check_swap:

...
```
最後我們 swap 的寫法如上，在 `b check_swap` 後馬上接上 `ret_check_swap` 的 label
而 `check_swap` label 後的 `bx lr` 就用 `ble end_check_swap` 和 `b ret_check_swap` 代替，就不會用到 `lr` 了

但更好的方法是善用 stack 與 `sp`，將之後才要用到的第一層 `lr` store 到 stack 上面，要用的時候再取出來，等之後有時間再來改成這樣的方式

## Feedback

覺得寫組語需要的思考方式和平常寫高階語言的方式非常不同，因為 register 是以 `R0`, `R1`, ... 編號下去，沒辦法以意義命名，寫的時候要很清楚每個 register 現在代表什麼以及還有哪些沒用過等等有點不習慣