# 2025q1 Homework5 (assessment)
contributed by < [`h0w726`](https://github.com/h0w726) >

## 從前 6 週的測驗題選出 3 題改進

### [Week 3 測驗2](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-2)

#### Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
在 [linux/arch/arm64/lib/memchr.S](https://github.com/torvalds/linux/blob/master/arch/arm64/lib/memchr.S) 找到在 Linux 核心原始程式碼找出 arm64 對應的最佳化實作如下

/* SPDX-License-Identifier: GPL-2.0-only */
/*
 * Copyright (C) 2021 Arm Ltd.
 */

#include <linux/linkage.h>
#include <asm/assembler.h>

/*
 * Find a character in an area of memory.
 *
 * Parameters:
 *	x0 - buf
 *	x1 - c
 *	x2 - n
 * Returns:
 *	x0 - address of first occurrence of 'c' or 0
 */

#define L(label) .L ## label

#define REP8_01 0x0101010101010101
#define REP8_7f 0x7f7f7f7f7f7f7f7f

#define srcin		x0
#define chrin		w1
#define cntin		x2

#define result		x0

#define wordcnt		x3
#define rep01		x4
#define repchr		x5
#define cur_word	x6
#define cur_byte	w6
#define tmp		x7
#define tmp2		x8

	.p2align 4
	nop
SYM_FUNC_START(__pi_memchr)
	and	chrin, chrin, #0xff
	lsr	wordcnt, cntin, #3
	cbz	wordcnt, L(byte_loop)
	mov	rep01, #REP8_01
	mul	repchr, x1, rep01
	and	cntin, cntin, #7
L(word_loop):
	ldr	cur_word, [srcin], #8
	sub	wordcnt, wordcnt, #1
	eor	cur_word, cur_word, repchr
	sub	tmp, cur_word, rep01
	orr	tmp2, cur_word, #REP8_7f
	bics	tmp, tmp, tmp2
	b.ne	L(found_word)
	cbnz	wordcnt, L(word_loop)
L(byte_loop):
	cbz	cntin, L(not_found)
	ldrb	cur_byte, [srcin], #1
	sub	cntin, cntin, #1
	cmp	cur_byte, chrin
	b.ne	L(byte_loop)
	sub	srcin, srcin, #1
	ret
L(found_word):
CPU_LE(	rev	tmp, tmp)
	clz	tmp, tmp
	sub	tmp, tmp, #64
	add	result, srcin, tmp, asr #3
	ret
L(not_found):
	mov	result, #0
	ret
SYM_FUNC_END(__pi_memchr)
SYM_FUNC_ALIAS_WEAK(memchr, __pi_memchr)
EXPORT_SYMBOL_NOKASAN(memchr)

其中 `chrin` 為所要找的目標字元，`wordcnt` 是將整塊搜尋的記憶體切成幾個 word，`repchr` 與測驗中的 `mask` 用途一樣，產生一段 word 大小的目標字元，`cntin` 表示不足一個 word 長度 (8 bytes) 的部分。

`word loop` 一次搜尋一個 word 裡有沒有目標字元，一樣透過與 `repchr` XOR，若為目標字元，byte 會變為 `0x00`。
其中

sub	tmp, cur_word, rep01
orr	tmp2, cur_word, #REP8_7f
bics	tmp, tmp, tmp2

其實就是測驗中的 `DETECT_NULL`，`orr tmp2, cur_word, #REP8_7f` 對應到
` x | 0x7f7f7f7f7f7f7f7f`， `bics tmp, tmp, tmp2` 為 `((X) - (0x0101010101010101)) & ~((X)|(0x7f7f7f7f7f7f7f7f))`，因為 `~(A|B) == (~A) & (~B)`，所以這式子和測驗中是等價的，[bics](https://www.scs.stanford.edu/~zyedidia/arm64/bics.html) 會根據 `tmp` 的值更新 flags，如果 zero flags 不等於 0 代表有找到目標字元。

## 紀錄閱讀〈[因為自動飲料機而延畢的那一年](https://www.opasschang.com/docs/the-story-of-auto-beverage-machine-1)〉的啟發
閱讀這篇文章時，會讓人不自覺地想讀下去，就像許多故事一樣，主角與一群志同道合的朋友想要做一些大事，與很多人不一樣的是，他們是真的投入其中且真的達成了。當然其中也會遇到很多挫折，也會有想放棄的時候，例如主角曾經一度就想說是不是選錯專案，覺得自己是不是在浪費時間，但正如老師所說的
> 你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望。你可以計算要花多少錢，然後評估自己可以接受多少損失，畢業後慢慢還都好，要錢我也可以借你。但青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。

已經決定要做一件事，那就把它做到最好，老師也提到
> 但我相信這個問題絕對不會沒有人碰過，一定有人解決過，所以你不該卡在這裡，因為這件事卡在這裡是相當不值得的。

既然已經有人解決過的問題，那為什麼我沒有能力解決呢，老師上課最常說的「缺什麼補什麼」，遇到問題不懂的，不是去選擇逃避，而是去補充知識，去解決它。工程師不是只需要會打 code ，就像主角一樣，機械領域不熟那就嘗試去學。失敗不可恥，沒辦法承受失敗並進步才可恥。

## 簡述想投入的專案
1. 在寫 [第一份作業](https://hackmd.io/8LcvFQ-gToaGZAXKYQcZ9g#%E4%BA%82%E6%95%B8) 時，有一個部分是要實作 Xorshift 產生亂數並轉換成字串，當時有參閱 [Linux 核心專題: 亂數產生器研究](https://hackmd.io/@sysprog/BkhlALt8A)，了解 Linux 核心中如何產生亂數，亂數在安全上是非常重要的部分，若產生的亂數不夠亂，就有可能被攻擊者利用，想探討 Linux 核心中產生亂數的策略，以及是否有能改進的部分。
2. 完成第三次作業。