---
tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---
# 2020q3 Homework10 (quiz10)
contributed by < `RusselCK` >
###### tags: `RusselCK`
> [ Arm 處理器 & dynamic programming 練習題](https://hackmd.io/@sysprog/2020-quiz10)
## Q1. 彩色圖片轉灰階
- [ ] [ARM NEON 範例](https://hackmd.io/FnDnLZcDQJOMqTHaPlsfVw?both#ARM-NEON-%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90)
- [ ] [Neon Intrinsics](https://developer.arm.com/architectures/instruction-sets/simd-isas/neon/intrinsics)
### 使用 float 來保存像素
```c=
#include <stdint.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
uint8_t *to_rgb(const float *m, int w, int h, uint8_t *rgb)
{
int size = w * h;
const float *ptr0 = m + (0 * size);
const float *ptr1 = m + (1 * size);
const float *ptr2 = m + (2 * size);
uint8_t *ret = rgb;
#define SATURATE_CAST_UCHAR(X) (uint8_t) MIN(MAX((int) (X), 0), 255);
for (int remain = size; remain > 0; remain--) {
rgb[0] = SATURATE_CAST_UCHAR(*ptr0);
rgb[1] = SATURATE_CAST_UCHAR(*ptr1);
rgb[2] = SATURATE_CAST_UCHAR(*ptr2);
rgb += 3;
ptr0++, ptr1++, ptr2++;
}
#undef SATURATE_CAST_UCHAR
return ret;
}
```
### 針對 Aarch64 (Arm 64-bit) 架構 (假設為 little-endian) 的程式碼
```c=
#include <arm_neon.h>
float *rgb_to_gray(const uint8_t *rgb, int w, int h, float *m)
{
const uint8_t Y_shift = 8;
const uint8_t R2Y = 77, G2Y = 151, B2Y = 28;
float *ptr = m;
int size = w * h;
int nn = size >> 3;
int remain = size - (nn << 3);
uint8x8_t _R2Y = vdup_n_u8(R2Y);
uint8x8_t _G2Y = vdup_n_u8(G2Y);
uint8x8_t _B2Y = vdup_n_u8(B2Y);
for (; nn > 0; nn--) {
uint8x8x3_t _rgb = vld3_u8(rgb);
uint16x8_t y16 = vmull_u8(_rgb.val[0], _R2Y);
y16 = vmlal_u8(y16, _rgb.val[1], _G2Y);
y16 = vmlal_u8(y16, _rgb.val[2], _B2Y);
y16 = vshrq_n_u16(y16, Y_shift);
float32x4_t _ylow = vcvtq_f32_u32(vmovl_u16(vget_low_u16(y16)));
float32x4_t _yhigh = vcvtq_f32_u32(vmovl_u16(vget_high_u16(y16)));
vst1q_f32(ptr + OFFSET1, _ylow); // OFFSET1 = 0
vst1q_f32(ptr + OFFSET2, _yhigh); // OFFSET2 = 4
rgb += 3 * 8, ptr += 8;
}
for (; remain > 0; remain--) {
*ptr = (rgb[0] * R2Y + rgb[1] * G2Y + rgb[2] * B2Y) >> Y_shift;
rgb += 3, ptr++;
}
return m;
}
```
## Q1. 整合 [libattopng](https://github.com/misc0110/libattopng)，輸出 RGBA 和灰階的 PNG 圖片
### Set up ARM playground
> - [ ] [How to set up an ARM64 playground on Ubuntu 18.04](https://dev.to/offlinemark/how-to-set-up-an-arm64-playground-on-ubuntu-18-04-27i6)
- [x] [How to launch ARM aarch64 VM with QEMU from scratch.](https://futurewei-cloud.github.io/ARM-Datacenter/qemu/how-to-launch-aarch64-vm/)
* 確認是否準備成功
```shell
$ uname -m
aarch64
```
- [x] [lab0 - 開發環境設定](https://hackmd.io/@sysprog/2020-lab0#-%E9%96%8B%E7%99%BC%E7%92%B0%E5%A2%83%E8%A8%AD%E5%AE%9A)
> - [ ] [Linux Command 命令列指令與基本操作入門教學](https://blog.techbridge.cc/2017/12/23/linux-commnd-line-tutorial/)
> - [ ] [GNU Debugger Tutorial](https://www.tutorialspoint.com/gnu_debugger/index.htm)
* git 上傳
- [ ] [Git 使用教學](https://zlargon.gitbooks.io/git-tutorial/content/?q=)
- [ ] [GitHub 設定指引](http://wiki.csie.ncku.edu.tw/github)
```shell
$ git add .
$ git status
$ git commit -m "..."
$ git push
```
### ImageMagick
- [ ] [Install ImageMagick from Source](https://imagemagick.org/script/install-source.php)
```shell
$ sudo apt-get install imagemagick
```
- [ ] [Getting started with ImageMagick](https://opensource.com/article/17/8/imagemagick)
### [libattopng](https://github.com/misc0110/libattopng)
**Usage**
Using libattopng is as simple as adding both `libattopng.h` and `libattopng.c` to your project.
### 開始作業
* [/quiz10/rgb_to_gray.c](https://github.com/RusselCK/sysprog2020/blob/master/quiz10/rgb_to_gray.c)
編譯
```shell
$ gcc -o rgb_to_gray rgb_to_gray.c -mfpu=neon
```
出現錯誤
```
In file included from rgb_to_gray.c:3:
In function ‘vshrq_n_u16’,
inlined from ‘rgb_to_gray’ at rgb_to_gray.c:30:9:
/usr/lib/gcc/arm-linux-gnueabihf/8/include/arm_neon.h:4394:22: error: argument 2 must be a constant immediate
return (uint16x8_t)__builtin_neon_vshru_nv8hi ((int16x8_t) __a, __b);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
```
## Q1. 引入 loop unrolling 和 prefetch 指令，嘗試改進 NEON 程式碼效率
### [Raspberry Pi 4 B](https://www.raspberrypi.org/products/raspberry-pi-4-model-b/)
- [x] [Installing operating system images](https://www.raspberrypi.org/documentation/installation/installing-images/?fbclid=IwAR26V11lRLR4Tq1PjdqAQoZhWmVPjua0weA_eHl74FI-BwR22slIezS8beg)
- [ ] [[基礎] 從序列埠登入到 Raspberry Pi](https://www.raspberrypi.com.tw/1999/connect-to-raspberry-pi-via-serial/)
> 透過 USB 轉 TTL 序列傳輸線，就可以在不需要螢幕和鍵盤滑鼠的情況下登入 Raspberry Pi
> * [PL2303 Windows Driver Download](http://www.prolific.com.tw/US/ShowProduct.aspx?p_id=225&pcid=41)
- [x] [如何在沒有螢幕或鍵盤的情況下設置Raspberry Pi](https://hackmd.io/@ShenTengTu/r1baxV4pQ)
- [ ] [[基礎] 以 VNC 和 Raspberry Pi 連線](https://www.raspberrypi.com.tw/586/setting-up-vnc/)
- [ ] [如何设置树莓派 VNC 的分辨率](https://shumeipai.nxez.com/2019/07/08/set-the-resolution-of-the-raspberry-pi-vnc.html)
### Prefetch
- [ ] [数据预取 __builtin_prefetch()](https://www.cnblogs.com/dongzhiquan/p/3694858.html)
- [ ] [How to use pld instruction in ARM](https://stackoverflow.com/questions/16032202/how-to-use-pld-instruction-in-arm)
## Q2. LeetCode [1617. Count Subtrees With Max Distance Between Cities](https://leetcode.com/problems/count-subtrees-with-max-distance-between-cities/)
給定 `n` 個城市，編號為從 `1` 到 `n`，再給予一大小為 `n−1` 的陣列 `edges`，其中 **`edges[i]=[ui,vi]`** 表示城市 `ui` 和 `vi` 之間存在雙向邊。
題目保證任意城市之間有唯一的路徑，也就是說所城市構成一棵**樹 (tree)**。
一棵**子樹 (subtree)** 是上述所有城市的子集，在子集中，任意城市間可透過子集的其他城市和邊到達。
兩個子樹被認為不一樣的條件是，至少有個城市在其中一棵子樹中存在，卻又不存在於另一棵子樹中。
給定 `d` 範圍介於從 `1` 到 `n−1`，請你找出城市間 **最大距離** 恰好為 `d` 的所有子樹數目。
請你回傳一個小為 `n−1` 的陣列，其中第 d 個元素 **（下標從 1 始）** 是城市間 **最大距離** 恰好等於 `d` 的子樹數目。
> 兩個城市間 **距離** 定義是，它們之間需要經過的邊的數目。
```c=
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define ITERATE(i, begin, end) \
for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
//for (int i = (begin); i < (end); i++)
int *countSubgraphsForEachDiameter(int n,
int **edges,
int edgesSz,
int *edges0sz,
int *rsz)
{
uint8_t d[n][n]; /* distance */
memset(d, 0xFF, sizeof(d));
```
`d[n][n]` : 任兩個城市的距離
* `#18` : 距離初始為 $\infty$
> 實際上只要大於 `n-1` 即可
:::warning
* `d[i][j]` = `d[j][i]`，應該可以有更節省空間的方式
:::
```c=19
uint16_t conn[n];
ITERATE (i, 0, n)
conn[i] = 1 << i;
```
`conn[n]` : 與城市`n` 相連的 bitmask
* `#20、21` : (初始) 城市`n` 必定和自己相連
```c=22
for (int z = 0; z < edgesSz; z++) {
int *e = edges[z];
int u = e[0] - 1, v = e[1] - 1;
d[u][v] = d[v][u] = 1;
conn[u] |= 1 << v, conn[v] |= 1 << u;
}
```
從 `edges[]` 中得到相連狀況並更新 `d[][]` 和 `conn[]`
* `edges[z]` 的內容是 1-indexed，因此需要 `-1` 改成 0-indexed
```c=29
ITERATE (k, 0, n)
ITERATE (i, 0, n)
ITERATE (j, 0, n)
d[i][j] = MIN(d[i][j], d[i][k] + d[k][j]);
```
更新 `d[][]`，將 兩步 以上可達的兩個城市的距離記錄下來
* 更新後，若 `d[i][j]` 仍為 `0xFF`，代表 城市`i` 無法到達 城市`j`，反之亦然
:::warning
- [ ] 這部分還有更省時的作法嗎?
:::
```c=34
int *rv = calloc(n - 1, sizeof(int));
```
`rv` : 要回傳的陣列
> `calloc(n - 1, sizeof(int))` : 配置 `n - 1` 個 `int` 的陣列，並初始為 `0`
:::warning
- [x] `int *rv = calloc(n - 1, sizeof(int));` 可以改寫成下列形式嗎?
```c
int rv[n - 1];
memeset(rv, 0, sizeof(rv));
```
* 不行，會出現 runtime error: load of null pointer of type 'int' 的錯誤
參考資料:
* [runtime error: load of null pointer of type 'const int' 错误提示](https://blog.csdn.net/qq_34824576/article/details/86496130)
:::
### 窮舉法 + DFS/BFS
```c=35
ITERATE (S, 1, (1 << n)) {
```
窮舉所有的子樹 (bitmask 為 `S`)
```c=36
int ctmp = 1 << __builtin_ctz(S);
while (1) {
int conn_nxt = ctmp;
ITERATE (d, 0, n)
if ((ctmp >> d) & 1)
conn_nxt |= conn[d];
conn_nxt &= S;
if (COND1) // COND1 = conn_nxt == ctmp
break;
ctmp = conn_nxt;
}
if (COND2) // COND2 = ~ctmp & S
continue;
```
判斷 `S` 是否為合法的子樹 ( 即 是否為無環連通圖 )
> BFS 非遞迴版本
* `ctmp` : 目前這層 ( k 步內 ) 可以走訪到的城市
* `conn_nxt` : 下一層 ( (k + 1) 步內 ) 可以走訪到的城市
`#36` : 將 `S` 中編號最小的城市當作 root，並納入 `ctmp`
`#39 ~ 41` : 走訪目前這一層可到的城市 (`ctmp`)，並將下一層可以走訪的城市納入 `conn_nxt`
`#42` : `conn_nxt &= S` : 將下一層可走訪的城市先縮在 `S` 有涵蓋的城市
`#43、44` : 若 `conn_nxt == ctmp`， 代表已經走訪完所有可走訪的城市，可以跳出 BFS
`#45` : 若否，則 `conn_nxt` 設置成下一層的 `ctmp`
:::info
`#47、48` : 若 `~ctmp & S` ，代表 `S` 並非無環連通圖，即不為合法子樹
:::
```c=49
uint8_t ret = 0;
ITERATE (i, 0, n)
if ((S >> i) & 1)
ITERATE (j, 0, i)
if (((S >> j) & 1) && (ret < d[i][j]))
ret = d[i][j];
if (!ret)
continue;
rv[ITER]++; //ITER = --ret
}
```
找出 `S` 中的最長距離 (`ret`)，並更新 `rv[--ret]`
> `--ret` 用意 : 改成 0-indexed
```c=59
*rsz = n - 1;
return rv;
}
```
## Q2. 進階題 (更有效率的實作)
### Dynamic programming on tree
```c=
```
Sign in with Wallet
Connect another wallet