# 2022q1 Homework3 (quiz3) contributed by < [2020leon](https://github.com/2020leon) > ## [作業要求](https://hackmd.io/@sysprog/BJJMuNRlq) - [ ] 重新回答[第 3 周測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)^從測驗一到測驗十一^，附帶的「==延伸問題==」也需要完成 - 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz) - [ ] 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb), [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 和 [參考題解](https://hackmd.io/@RinHizakura/BysgszHNw) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。 - [x] 將你的共筆加到 [2022q1 Homework3 (作業區)](https://hackmd.io/@sysprog/linux2022-homework3) ## [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3) ### 測驗 `1` #### 測驗 `1` 填空 ```c #define GENMASK(h, l) \ (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT))) ``` 首先 `~0UL` 為在二進位中全是 `1` 的數，在 64 位元中即 `0xffffffffffffffff` 。若要達到題目要求，須對該數位移。其中 `(~0UL) >> (LEFT)` 的目的為製造在較高位元的 `0` ，故填入 `63 -h` ；而 `(~0UL) >> (l) << (RIGHT)` 則是空出較低位元的 `0` ，故填入 `l` 。 | 陳述式 | 答案 | | ------- | -------- | | `LEFT` | `63 - h` | | `RIGHT` | `l` | :::info 注：事實上如下便可達到要求。 ```c #define GENMASK(h, l) \ (((~0UL) >> (63 - h)) & ((~0UL) << (l))) ``` ::: ### 測驗 `2` #### 測驗 `2` 填空 ```c struct foo; struct fd { struct foo *foo; unsigned int flags; }; enum { FOO_DEFAULT = 0, FOO_ACTION, FOO_UNLOCK, } FOO_FLAGS; static inline struct fd to_fd(unsigned long v) { return (struct fd){EXP1, v & 3}; } ``` 觀察結構成員型態，因此賦值時須轉換型態為 `struct foo *` 以避免編譯器警告。再依據題目要求「對 4 個位元組進行向下對齊」，須清空所傳進之 `v` 參數之最低二位元，即將 `v` 和一特定遮罩進行 AND 運算。而最容易製作遮罩的方式即對 3 進行一補數運算。因此空格需填入 `(struct foo *) (v & ~3)` 。 | 陳述式 | 答案 | | ------ | ------------------------- | | `EXP1` | `(struct foo *) (v & ~3)` | ### 測驗 `3` #### 測驗 `3` 填空 ```c #include <stdint.h> uint8_t rev8(uint8_t x) { x = (x >> 4) | (x << 4); x = ((x & 0xCC) >> 2) | (EXP2); x = ((x & 0xAA) >> 1) | (EXP3); return x; } ``` 逐一位元反轉可見於[課程說明](https://docs.google.com/presentation/d/1B80k91_3_XuZ0zMzfdgS-D1I29VaHxZTg3XD3bok0io/edit#slide=id.g4f2b7eb495_0_12)，其原理便是從「大單位」逐漸反轉至「小單位」，直至全部反轉完畢。 | 陳述式 | 答案 | | ------ | ----------------- | | `EXP2` | `(x & 0x33) << 2` | | `EXP3` | `(x & 0x55) << 1` | ### 測驗 `4` #### 測驗 `4` 填空 ```c #include <assert.h> #define _foreach_no_nullval(i, p, arr) \ assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p)) #define foreach_int(i, ...) \ for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \ _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \ (i) = ((int[]){__VA_ARGS__, 0})[EXP4]) #define foreach_ptr(i, ...) \ for (unsigned _foreach_i = \ (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \ (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \ NULL})[EXP5], \ _foreach_no_nullval(_foreach_i, i, \ ((const void *[]){__VA_ARGS__}))) ``` 觀察題目範例後可知兩個 `foreach` 巨集均是對 `__VA_ARGS__` 進行遍歷，而 `i` 為遍歷時儲存遍歷值的變數，真正的索引變數為 `_foreach_i` 。在進行遍歷時，須對 `_foreach_i` 做累加，並取其值作為索引。在此為 `++_foreach_i` 而非 `_foreach_i++` 的原因為 `i` 所要儲存的應為下一個元素，因此先加一後再取其值。 | 陳述式 | 答案 | | ------ | -------------- | | `EXP4` | `++_foreach_i` | | `EXP5` | `++_foreach_i` | ### 測驗 `5` #### 測驗 `5` 填空 ```c #include <limits.h> int divide(int dividend, int divisor) { int signal = 1; unsigned int dvd = dividend; if (dividend < 0) { signal *= -1; dvd = ~dvd + 1; } unsigned int dvs = divisor; if (divisor < 0) { signal *= -1; dvs = ~dvs + 1; } int shift = 0; while (dvd > (EXP6)) shift++; unsigned int res = 0; while (dvd >= dvs) { while (dvd < (dvs << shift)) shift--; res |= (unsigned int) 1 << shift; EXP7; } if (signal == 1 && res >= INT_MAX) return INT_MAX; return res * signal; } ``` | 陳述式 | 答案 | | ------ | --------------------- | | `EXP6` | `dvs << shift` | | `EXP7` | `dvd -= dvs << shift` | ### 測驗 `6` #### 測驗 `6` 填空 ```c #include <stdbool.h> #include "list.h" struct Point { int x, y; }; struct point_node { int p1, p2; struct list_head link; }; static bool can_insert(struct list_head *head, int p1, int p2) { struct point_node *pn; list_for_each_entry (pn, head, link) return EXP8; return true; } static int gcd(int x, int y) { while (y) { int tmp = y; y = x % y; x = tmp; } return x; } static int maxPoints(struct Point *points, int pointsSize) { if (pointsSize <= 2) return pointsSize; int i, j, slope_size = pointsSize * pointsSize / 2 + 133; int *dup_cnts = malloc(pointsSize * sizeof(int)); int *hori_cnts = malloc(pointsSize * sizeof(int)); int *vert_cnts = malloc(pointsSize * sizeof(int)); int *slope_cnts = malloc(slope_size * sizeof(int)); memset(hori_cnts, 0, pointsSize * sizeof(int)); memset(vert_cnts, 0, pointsSize * sizeof(int)); memset(slope_cnts, 0, slope_size * sizeof(int)); for (i = 0; i < pointsSize; i++) dup_cnts[i] = 1; struct list_head *heads = malloc(slope_size * sizeof(*heads)); for (i = 0; i < slope_size; i++) INIT_LIST_HEAD(&heads[i]); for (i = 0; i < pointsSize; i++) { for (j = i + 1; j < pointsSize; j++) { if (points[i].x == points[j].x) hori_cnts[i]++, hori_cnts[j]++; if (points[i].y == points[j].y) vert_cnts[i]++, vert_cnts[j]++; if (points[i].x == points[j].x && points[i].y == points[j].y) dup_cnts[i]++, dup_cnts[j]++; if (points[i].x != points[j].x && points[i].y != points[j].y) { int dx = points[j].x - points[i].x; int dy = points[j].y - points[i].y; int tmp = gcd(dx, dy); dx /= tmp; dy /= tmp; int hash = dx * dy - 1333 * (dx + dy); if (hash < 0) hash = -hash; hash %= slope_size; if (can_insert(&heads[hash], i, j)) { struct point_node *pn = malloc(sizeof(*pn)); pn->p1 = i; pn->p2 = j; EXP9; } } } } for (i = 0; i < slope_size; i++) { int index = -1; struct point_node *pn; list_for_each_entry (pn, &heads[i], link) { index = pn->p1; slope_cnts[i]++; } if (index >= 0) slope_cnts[i] += dup_cnts[index]; } int max_num = 0; for (i = 0; i < pointsSize; i++) { if (hori_cnts[i] + 1 > max_num) max_num = hori_cnts[i] + 1; if (vert_cnts[i] + 1 > max_num) max_num = vert_cnts[i] + 1; } for (i = 0; i < slope_size; i++) { if (slope_cnts[i] > max_num) max_num = slope_cnts[i]; } return max_num; } ``` | 陳述式 | 答案 | | ------ | ----------------------------------- | | `EXP8` | `p1 == pn->p1` 或 `pn->p1 == p1` | | `EXP9` | `list_add(&pn->link, &heads[hash])` | ### 測驗 `7` #### 測驗 `7` 填空 ```c int ilog32(uint32_t v) { int ret = v > 0; int m = (v > 0xFFFFU) << 4; v >>= m; ret |= m; m = (v > 0xFFU) << 3; v >>= m; ret |= m; m = (v > 0xFU) << 2; v >>= m; ret |= m; m = EXP10; v >>= m; ret |= m; EXP11; return ret; } ``` | 陳述式 | 答案 | | ------- | ------------------ | | `EXP10` | `m = (v > 3) << 1` | | `EXP11` | `ret += v > 1` | ### 測驗 `8` #### 測驗 `8` 填空 ```cpp void remove_data(tree &t, int d) { tnode **p = &t; while (*p != 0 && (*p)->data != d) { if (d < (*p)->data) EXP12; else EXP13; } tnode *q = *p; if (!q) return; if (!q->left) *p = q->right; else if (!q->right) *p = q->left; else { tnode **r = &q->right; while ((*r)->left) r = EXP14; q->data = (*r)->data; q = *r; *r = q->right; } delete q; } ``` | 陳述式 | 答案 | | ------- | ------------------ | | `EXP12` | `p = &(*p)->left` | | `EXP13` | `p = &(*p)->right` | | `EXP14` | `&(*r)->left` | ### 測驗 `9` #### 測驗 `9` 填空 ```c /* maximum alignment needed for any type on this platform, rounded up to a power of two */ #define MAX_ALIGNMENT 16 /* Given a size, round up to the next multiple of sizeof(void *) */ #define ROUND_UP_TO_ALIGNMENT_SIZE(x) \ (((x) + MAX_ALIGNMENT - MMM) & ~(NNN)) ``` | 陳述式 | 答案 | | ------ | ------------------- | | `MMM` | `1` | | `NNN` | `MAX_ALIGNMENT - 1` | ### 測驗 `10` #### 測驗 `10` 填空 ```c #define DIVIDE_ROUND_CLOSEST(x, divisor) \ ({ \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \ (((__x) > 0) == ((__d) > 0))) \ ? ((RRR) / (__d)) \ : ((SSS) / (__d)); \ }) ``` | 陳述式 | 答案 | | ------ | ---------------------- | | `RRR` | `(__x) + ((__d) >> 1)` | | `SSS` | `(__x) - ((__d) >> 1)` | <!-- (__x) + (__d) --> ### 測驗 `11` #### 測驗 `11` 填空 ```c static inline unsigned long fls(unsigned long word) { int num = 64 - 1; if (!(word & (~0ul << 32))) { num -= 32; word <<= 32; } if (!(word & (~0ul << (64 - 16)))) { num -= 16; word <<= 16; } if (!(word & (~0ul << (64 - 8)))) { num -= 8; word <<= 8; } if (!(word & (~0ul << (64 - 4)))) { num -= 4; word <<= 4; } if (!(word & (~0ul << (64 - 2)))) { num -= 2; word <<= 2; } if (!(word & (~0ul << (64 - 1)))) num -= 1; return num; } unsigned long i_sqrt(unsigned long x) { unsigned long b, m, y = 0; if (x <= 1) return x; m = 1UL << (fls(x) & ~1UL); while (m) { b = y + m; XXX; if (x >= b) { YYY; y += m; } ZZZ; } return y; } ``` | 陳述式 | 答案 | | ------ | --------- | | `XXX` | `y >>= 1` | | `YYY` | `x -= b` | | `ZZZ` | `m >>= 2` |
Last changed by  
 
6649
249

Read more

2022q1 Homework1 (lab0)

contributed by < 2020leon > 作業要求 [x] 在 GitHub 上 fork lab0-c參閱 Git 教學和 GitHub 設定指引 ^附教學影片^ [x] 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差

2/23/2024
2022q1 Project (cpumemory)

contributed by < 2020leon > 目標 [ ] 閱讀 Ulrich Drepper 於 2007 年撰寫的論文《 What Every Programmer Should Know About Memory 》(版次: 1.0) [ ] 嘗試執行第六章提及的程式碼 [ ] 翻譯和校訂《每位程式開發者都該有的記憶體知識》 環境 $ uname -a

6/30/2022
2022q1 Homework3 (fibdrv)

contributed by < 2020leon > 作業要求 自我檢查清單 [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗; [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說 [ ] 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本; [ ] 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？ [ ] lsmod 的輸出結果有一欄名為 Used by，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？

3/19/2022
2022q1 Homework2 (quiz2)

contributed by < 2020leon > 作業要求 [ ] 重新回答第 2 周測驗題^從測驗一到測驗七^，附帶的「==延伸問題==」也需要完成 解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析 [ ] 比照 課前測驗參考解答: Q1, Linked list 題目分析 和 參考題解 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。 [x] 將你的共筆加到 2022q1 Homework2 (作業區)

3/13/2022
Read more from 6649
Published on HackMD