# 2024q1 Homework5 (assessment)
contributed by < `aa860630` >

## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)〉的啟發與心得
>在失敗過這麼多次後，我們得到了一個結論：「我們要解決更為具體的問題。」

在文章的第一篇就有這麼一段話 :「我們要解決更為具體的問題」，這直截了當地反映出我與大多數學生當前需要改善的問題。在現有教育體制下，所有的解決辦法都過於理想，結局往往都會被狠狠打臉，這也是為何在課堂 code review 時明明作業都是獨立完成，卻連個小問題都答不上來，因為我們在解決問題時都忘記探究問題根本的重要性，先了解問題本身方能解決更具體的問題

>「你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已。」

這大概是我每天都要面對的問題。大學雖然念的是資工系，但我就是典型的資工系不會寫程式，只要在作業上遇到問題就習慣性問已經寫完的同學，從來不會自己理解問題並尋求解決辦法，我知道我只是在逃避問題，就算再遇到同樣的問題，我想我還是不會。「面對它、接受它、處理它、放下它」才是遇到問題時該保持的態度

在閱讀這篇文章的過程中，我多次反省自己，換作是我會在製作自動販賣機的第幾個步驟放棄，反觀作者在遇到問題時能善用工具仔細分析，在一次次的試錯中不斷成長，聰明的人不斷探究真理，而天生不夠聰穎的我卻還總想藉口說服自己已經盡力，是時候改變一下自己了

## 課堂心得
課程的第一個禮拜出了第一項作業 -- 指定的佇列操作，每天寫程式的時間超過10個小時，心想第一個作業就已經讓我疲憊不堪，退選的心一直存在，看到一起修課的同學半夜持續在更新自己的 github 與 HackMD 就覺得自己不能輸

在比較 list sort、merge sort 跟 Timsort 的過程我發現影響排序的因素很多，包括資料、穩定度等，過去的我會因為求出 $O(n)$ 或 $O(n\log{n})$ 這類大方向的時間複雜度而去判斷一個演算法的好壞，我學習到工程師追求更精準、更有效率的精神，在判別時間複雜度時讓我理解做研究的態度應當是專注於更細緻的分析與比較，而非只停留於表面

經過三分之一個學期我感覺收穫良多，尤其是在學習 C 語言的基礎方面。最令我印象深刻的是 Bitwise Operation 這一章節。我發現許多表達式例如乘法、除法、轉換大小寫......，都可以用簡單的邏輯運算子像 or,xor 等這類運算子進行運算，這不僅改進運算效率，也讓我對計算機如何在底層處理資料有了更深入的理解。

在上過了計算機結構與 Linux 核心實作，發現老師對我們要求不僅僅是程式上的，誠實面對自己、如何清楚的表達自己、如何探究問題本身等，都是我在這兩堂課程中學到的，現在做其他作業的筆記都會使用老師要求我們的方法，在中英切換時也會下意識地按下空白鍵，我清楚的看見自己成長了，也希望可以把課堂所學在未來的各個地方發揮上

## 前期作業改進
1. [第三週測驗五](https://hackmd.io/72_-cupDS1Wz1qMeDLv8Sg?view#%E6%B8%AC%E9%A9%97%E4%BA%94)
## 研讀 [CS:APP 3/e 第一章](https://bottomupcs.com/ch02.html)

#### Ch1-2
* 為了在系統上運行 hello.c，個別的 C 敘述必須由其他程式轉換為一系列低階機器語言指令，過程如下:(圖片來自 Computer Systems - A Programmer's Persp. 3nd ed.)
過程分為 preprocessor, compiler, assembler, and linker 四個階段 :
* Preprocessing 階段 : preprocessor（cpp）根據以 `#` 字元開頭的敘述修改原始的 C 程式。例如，在 hello.c 的第 1 行中的`#include <stdio.h>` 敘述告訴前置處理器讀取系統標頭檔 `stdio.h` 的內容並直接插入到程式中。結果是另一個 C 程式，通常具有 `.i` 副檔名
* Compilation 階段 : 編譯器（cc1）將過前置處理的 C 原始程式碼轉換為組合語言，組合語言是一種更接近機械碼的低階語言，通常具有 `.s` 副檔名
* Assembly 階段 : 組譯器（as）將 `hello.s` 組譯成機器語言，通常為一個二進位檔案，具有 `.o` 副檔名
* Linking 階段 : hello 程式呼叫了 `printf` 函式，後者位於名為 `printf.o` 的單獨預先編譯目標檔 (object file) 中，必須以某種方式與我們的 `hello.o` 程式合併。連結器（ld）負責處理這個合併過程

:::danger
使用台灣慣用科技術語:
* character 是字元
* file 是檔案
* statement 是敘述
* machine code 是機械碼
* source code/file 是原始程式碼
* preprocessor 是前置處理器
* program 是程式
* assemble 是組譯，而非編譯 (compile)

參見[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)和[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)，並留意指定的格式及風格，以通順的漢語書寫。

段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
:::

#### Ch1-3
* 編譯系統固然會產生有效的機械碼，但為了避免安全漏洞、瞭解連結時的錯誤與優化程式性能方面，瞭解編譯系統運作的原理是必要的。

#### Ch1-4
* [shell](https://en.wikipedia.org/wiki/Shell_(computing)) 是指[作業系統](https://en.wikipedia.org/wiki/Operating_system)中提供存取[核心](https://zh.wikipedia.org/wiki/%E5%86%85%E6%A0%B8)所提供之服務的程式，為使用者提供操作介面的程式，如果命令行的第一個單詞不對應於內置的 shell 命令，則 shell 假設它是一個可執行文件的名稱，加載並運行它
* 系統的硬體組成，包含以下 4 個元件 :
* [匯流排](https://zh.wikipedia.org/zh-tw/%E6%80%BB%E7%BA%BF) : 以一種通用的方式為各組件提供資料傳送和控制邏輯，匯流排可同時傳輸的資料數就稱為寬度（width），以位元為單位，匯流排寬度愈大，傳輸效能就愈佳。
* [主記憶體](https://en.wikipedia.org/wiki/Computer_data_storage#Primary_storage): 主記憶體（也被稱為內部記憶體或主記憶體）簡稱為內存。這是 CPU 直接存取的唯一記憶體，CPU 會不斷地讀取儲存在內存中的指令並根據需要執行它們。所有主動操作的資料也以統一的方式儲存在內存中。
* [處理器](https://en.wikipedia.org/wiki/Processor_(computing)) :
* [I/O 裝置](https://en.wikipedia.org/wiki/Input/output) : 輸入/輸出（通常簡寫為 I/O），是指資訊處理系統（例如電腦）與外部世界（可能是人類或另一個資訊處理系統）之間的通訊。輸入是系統接收的訊號或數據，而輸出則是系統發送的訊號或數據。

#### Ch2-1

- gcc 可以指定要用哪一個 c 標準來編譯程式碼，比如說 `-std=c99` 或是 `-std=c11` 之類的，但是也可以使用 `-std=gnu11` 這種標準來做編譯，這邊的 gnu11 ，以他[文件](https://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html#index-std-1)的說法，其實是 C11 的 GNU dialect ，兩者差異如下：
- 如果是標準的話， compiler 會把一些跟 C 標準相衝的 gcc feature 關掉 (但其他 feature 還是打開的)
- 如果是 GNU dialect 的話， compiler 會把所有 gcc feature 打開，就算有些 feature 會蓋掉原來 C 標準所定義的東西。

- C data type 所佔的 byte 長度跟程式是根據硬體為 32bits 或 64bits，細節如下表格

| 有號數 | 無號數 | 32bits | 64bits |
|:-------------------------:|:-----:|:---------------:|:------------:|
| [signed] char | unsigned char | 1 | 1
| short | unsigned short | 2 | 2
| int | unsigned | 4 | 4
| long | unsigned long | 4 | 8
| int32_t | uint32_t | 4 | 4
| int64_t | uint64_t | 8 | 8
| char * | | 4 | 8
| float | | 4 | 4
| double | | 8 | 8

- endianness
- Little endian: 最低有效字節放最前面(低的記憶體位置)
- Big endian: 最高有效字節放最前面(低的記憶體位置)

:::info

在二的補數乘法應用中，討論到乘法溢位造成的安全漏洞，乘法溢位可能造成資料結構被破壞或者程式崩潰，還有哪些問題嚴重到可以被稱之為安全漏洞，抑或是上述問題可以如何被拿來惡意操作?
:::

## 教材延伸問題
:::info
在[你所不知道的 C 語言：bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)中，可以透過建立 LUT 來加速 RGB 轉為灰階的運算，以下兩種操作除了表格儲存方式可能不一樣還有哪些差別?

方法1:

方法2:

原始程式碼: [RGBAtoBW](https://github.com/charles620016/embedded-summer2015/tree/master/RGBAtoBW)
:::

:::info
在 RGBA 轉為灰階的操作中，為何透明度 $alpha$ 不與 RGB 一樣建立表格

原始程式碼: [RGBAtoBW](https://github.com/charles620016/embedded-summer2015/tree/master/RGBAtoBW)
:::

## 期末專題

1. 打造 Linux 虛擬攝影機裝置驅動程式 :
透過這個專題，開發者能夠深入研究 Linux 核心的設計和多媒體架構，了解如何開發和實現一個虛擬攝影機裝置的驅動程式。在現代偷拍事件頻傳下，開發者可以透過某些手段有效防止個資洩漏，對資訊安全也有一定程度的幫助。

2. 透過 Netfilter 自動過濾廣告 :
儘管現有網頁瀏覽器擴展如 AdBlock 能夠過濾廣告，但它們需要額外的設定且消耗系統資源。透過 netfilter 在核心層級實現廣告過濾，可以為所有應用程式提供廣告過濾功能，而不需要額外的擴展或設定。
> TLS; https; layer 4 firewall; OSI 七層
> TCP 3-way handshake? SYN, sliding window

3. [第 5 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz5)、[第 6 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz6)、[第 11 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz11)提及逐步建構記憶體配置器 (memory allocator)，本任務針對 Linux 核心的機制，設計現代的高效記憶體配置器
* 相關資訊
* [rpmalloc](https://github.com/mjansson/rpmalloc)
* [Deterministic Memory Allocation for Mission-Critical Linux](https://ossna2017.sched.com/event/BCsR)

TODO: 重現去年 Netfilter 實驗，記錄下來

期末專題: [透過 Netfilter 自動過濾廣告](https://hackmd.io/SppwxGnoR5SOD7q1L89j0w)