# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 15 週測驗題 ###### tags: `sysprog2020` :::info 目的: 引導學員挑戰 LeetCode 和複習記憶體管理機制 ::: ==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSdIhhVeIOLInSPt_1TFjc92TamE4ZuqP4vbQyG6YCBWHzBjQw/viewform)== --- ### 測驗 `1` LeetCode [835. Image Overlap](https://leetcode.com/problems/image-overlap/) 給定二個影像 A 和 B，二者皆為大小相同的二維正方形矩陣，內部以二進位表示。我們轉換其中一個影像，向左、右、上，或下滑動任意數量的單位，並將其置於另一個影像之上，隨後，該轉換的重疊 (overlap) 指二個影像都有 1 的位置數量，注意：轉換不包含向任一方向旋轉。於是，最大可能的重疊為何？ 範例 1: ![](https://i.imgur.com/OnF5wBs.png) * 輸入 $$ A = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) $$ $$ B = \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array} \right) $$ * 輸出: * `3` * 解釋 * 將 A 向右移動 1 個單位，然後向下移動 1 個單位 ![](https://i.imgur.com/ONuIxjj.png) * 二張影像中都存在 `1` 的位置總數為 `3`，見下圖紅色標記 ![](https://i.imgur.com/N00Zxg7.png) 思路：找出所有 1 的位置，對兩個矩陣的所有這些位置進行求差，再統計這些差出現最多的次數。兩個坐標的差表示什麼？即是將其中一個坐標移動到另一個坐標需要移動的向量。於是，在走訪個別單元的過程中，我們找出 `A` 中所有值為 `1` 的坐標，移動到 `B` 中所有值為 `1` 的坐標需要移動的向量。於是乎，在這些向量中出現次數最多的向量，就是我們要求的整個矩陣應該移動的向量。 以下程式碼針對 LeetCode [835. Image Overlap](https://leetcode.com/problems/image-overlap/)，提出可能的解法： ```cpp #include <string.h> #define max(a, b) (((a) > (b)) ? (a) : (b)) static inline int overlap_count(unsigned int *AA, unsigned int *BB, int size) { int res = 0; for (int i = 0; i < size; ++i) res += __builtin_popcount(AA[i] & BB[i]); return res; } static void translate(unsigned int *v, int vsize, int i, int j, unsigned int *res) { memcpy(res, v, sizeof(unsigned int) * vsize); int mask[32]; for (int k = 0; k < 32; k++) mask[k] = (1U << k) - 1; int n = vsize; if (i >= 0) { for (int k = 0; k < n; k++) res[k] >>= i; } else { i = -i; for (int k = 0; k < n; k++) res[k] = ((res[k] << i) & mask[n]); } if (j >= 0) { ITER1; for (int k = 0; k < j; k++) res[k] = 0; } else { j = -j; ITER2; for (int k = n - j; k < n; k++) res[k] = 0; } } int largestOverlap(int **img1, int img1Size, int *img1ColSize, int **img2, int img2Size, int *img2ColSize) { int n = img1Size; unsigned int A[n], B[n]; memset(A, 0, sizeof(unsigned int) * n); memset(B, 0, sizeof(unsigned int) * n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (img1[i][j] == 1) A[i] |= 1 << j; if (img2[i][j] == 1) B[i] |= 1 << j; } } int res = 0; for (int i = -(n - 1); i <= (n - 1); ++i) { for (int j = -(n - 1); j <= (n - 1); ++j) { unsigned int AA[n]; translate(A, n, i, j, AA); res = max(res, overlap_count(AA, B, n)); } } return res; } ``` 請補完程式碼，使其符合 LeetCode 題目要求。 參考資料: * [LeetCode 835. Image Overlap](https://www.cnblogs.com/grandyang/p/10355589.html) ==作答區== ITER1 = ? * `(a)` `for (int k = 0; k < n - j; k++) res[k + j] = res[k]` * `(b)` `for (int k = 0; k <= n - j; k++) res[k + j] = res[k]` * `(c)` `for (int k = n - j - 1; k >= 0; k--) res[k + j] = res[k]` * `(d)` `for (int k = n - j; k >= 0; k--) res[k + j] = res[k]` ITER2 = ? * `(a)` `for (int k = j; k < n; k++) res[k + j] = res[k]` * `(b)` `for (int k = j; k < n; k++) res[k - j] = res[k]` * `(c)` `for (int k = j - 1; k < n; k++) res[k + j] = res[k]` * `(d)` `for (int k = j - 1; k < n; k++) res[k - j] = res[k]` :::success 延伸題目: 1. 解釋上述程式碼運作原理 2. 提出效率更高，且空間佔用更少的 C 程式碼實作 ::: --- ### 測驗 `2` LeetCode [1569. Number of Ways to Reorder Array to Get Same BST](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/) 給定一個陣列 `nums` 表示 $1$ 到 $n$ 的排列，依據元素在 `nums` 中的順序，依次插入一個初始為空的二元搜尋樹 (BST)。請你統計將 `nums` 重新排序後，滿足以下條件的個數： * 重排後得到的 BST 與 `nums` 原本數值順序得到的 BST 相同。 例如，給定 $nums = [2,1,3]$，我們得到一棵 `2` 為 root、`1` 為 left 及 `3` 為 right 的樹。 ![](https://i.imgur.com/zp2bTKD.png) 陣列 $[2,3,1]$ 也能得到相同的 BST，但 $[3,2,1]$ 會得到一棵不同的 BST 。 由於答案可能會很大，請將結果對 $10^9 + 7$ 取餘數。 * 為何是 $10^9 + 7$ 呢？請見 [Modulo 10^9+7 (1000000007)](https://www.geeksforgeeks.org/modulo-1097-1000000007/) 範例 1 ![](https://i.imgur.com/zp2bTKD.png) * 輸入 * $nums = [2,1,3]$ * 輸出 * `1` * 解釋 * 我們將 `nums` 重排，$[2,3,1]$ 可得到相同的 BST * 沒有其他得到相同 BST 的方法 範例 2 ![](https://i.imgur.com/EQRaUTp.png) * 輸入 * $nums = [3,4,5,1,2]$ * 輸出 * `5` * 解釋 * 下面 5 個陣列可得到相同的 BST * $[3,1,2,4,5]$ * $[3,1,4,2,5]$ * $[3,1,4,5,2]$ * $[3,4,1,2,5]$ * $[3,4,1,5,2]$ 範例 3 ![](https://i.imgur.com/pHEpvcY.png) * 輸入 * $nums = [1,2,3]$ * 輸出 * `0` * 解釋 * 沒有其他排列順序能得到相同的 BST 範例 4 ![](https://i.imgur.com/KnFWUNa.png) * 輸入 * $nums = [3,1,2,5,4,6]$ * 輸出 * `19` 範例 5 * 輸入 * $nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]$ * 輸出 * `216212978` * 解釋 * 得到相同 BST 的個數是 `3216212999` * 將其對 $10^9 + 7$ 取餘後得到 `216212978` 根節點是陣列第一個數，分為左右兩個子樹，左右子樹之間的順序若不變即可 假設左子樹 $L$ 長度 $nL$，右子樹 $R$ 長度 $nR$，則有效組合數為 $C_{nL+nR}^{nL} \times f(L) \times f(R)$ ```cpp #include <string.h> static const int MOD = 1e9 + 7; /* prime */ static int recursive(int *nums, int nums_size, int N, DECL) { if (nums_size <= 2) return 1; int left[N + 1], left_size = 0, right[N + 1], right_size = 0; for (int i = 1; i < nums_size; i++) nums[i] > nums[0] ? (right[right_size++] = nums[i]) : (left[left_size++] = nums[i]); int l = recursive(left, left_size, N, cache), r = recursive(right, right_size, N, cache); return (((long) cache[nums_size - 1][left_size] * l % MOD) * r) % MOD; } int numOfWays(int *nums, int N) { int comb[N + 1][N + 1]; /* combination table */ memset(comb, 0, sizeof(comb)); comb[0][0] = 1; for (int i = 1; i <= N; i++) { comb[i][0] = 1; for (int j = 1; j <= N; j++) INIT; } return recursive(nums, N, N, comb) - 1; } ``` 參考資訊: * [花花醬 LeetCode 1569](https://zxi.mytechroad.com/blog/recursion/leetcode-1569-number-of-ways-to-reorder-array-to-get-same-bst/) 注意：`DECL` 若是 `int **cache`，會在 [undefined behavior sanitizer](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html) (UBsan) 的執行階段遇到 [Load of misaligned address](https://stackoverflow.com/questions/47619944/load-of-misaligned-address-and-ubsan-finding) 請補完程式碼，使其符合 LeetCode 題目要求。 ==作答區== DECL = ? * `(a)` `int cache[N][N]` * `(b)` `int cache[N - 1][N - 1]` * `(c)` `int cache[N + 1][N]` * `(d)` `int (*cache)[N + 1]` * `(e)` `int (*cache)[N]` INT = ? * `(a)` `comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD` * `(b)` `comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1])` * `(c)` `comb[i][j] = (comb[i][j] + comb[i - 1][j - 1]) % MOD` * `(d)` `comb[i][j] = (comb[i][j] + comb[i - 1][j - 1])` * `(e)` `comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1]) % MOD` * `(f)` `comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1])` :::success 延伸題目: 1. 解釋上述程式碼運作原理 2. 提出效率更高，且空間佔用更少的 C 程式碼實作 ::: --- ### 測驗 `3` 在 Ubuntu/Debian Linux 中，可執行 `sudo apt install dictionaries-common` 以安裝辭典套件，於是可得到 `/usr/share/dict/words` 檔案，後者包含超過 10 萬個單字/詞: ```shell $ wc -l /usr/share/dict/words ``` 考慮以下 C 程式 (`strsearch.c`) 可從給定的詞典中檢索: ```cpp /* * Hash table is represented as `htable` array of size N (N = number of lines in * dict), where each element either points to the end of a singly-linked list or * is equal to zero. Lists are stored in pre-allocated array `clist` of size N. * * This implementation is memory-efficient and cache-friendly, requiring only * 12N + O(1) bytes of "real" memory which can be smaller than the size of * dict, sacrificing however for request processing speed, which is * O(req_size) in most cases, but may be up to O(dict_size) due to hash collision. */ #include <fcntl.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/mman.h> #include <sys/stat.h> #include <unistd.h> /* 2 additional bytes for '\n' and '\0' */ #define MAX_REQUEST_SIZE (128 * 1024 * 1024 + 2) struct htable_entry { uint32_t ptr; }; struct collision_list { uint32_t fpos; uint32_t len; uint32_t prev; }; struct compr_collision_list { uint32_t fpos; uint32_t len; }; typedef struct htable_entry htable_entry_t; typedef struct collision_list collision_list_t; typedef struct compr_collision_list compr_collision_list_t; static char *dict; static htable_entry_t *htable; static collision_list_t *clist; static compr_collision_list_t *cclist; static size_t num_of_bytes, num_of_lines; static size_t num_of_buckets; static int clist_size = 1; static uint32_t hash(char *s, size_t len) { uint32_t hash = 5381; for (size_t i = 0; i < len; i++) hash = ((hash << 5) + hash) + (s[i] - 32); return hash % num_of_buckets; } static void htable_insert(size_t fpos, size_t len) { uint32_t h = hash(dict + fpos, len); clist[clist_size].fpos = fpos; clist[clist_size].len = len; clist[clist_size].prev = htable[h].ptr; htable[h].ptr = clist_size; ++clist_size; } static bool htable_lookup(char *s, size_t len) { uint32_t h = hash(s, len); uint32_t ptr = htable[h].ptr; uint32_t nextptr = htable[h + 1].ptr; for (; ptr < nextptr; ptr++) { if ((len == cclist[ptr].len) && !memcmp(s, dict + cclist[ptr].fpos, len)) return true; } return false; } int main(int argc, char **argv) { if (argc != 2) { printf("usage: %s dictionary_file\n", argv[0]); return 2; } /* Map dictionary file directly to memory for easier access from program */ int dictfd; if ((dictfd = open(argv[1], O_RDONLY)) < 0) return 1; struct stat st; fstat(dictfd, &st); num_of_bytes = st.st_size; if ((dict = mmap(0, num_of_bytes, PROT_READ, MAP_PRIVATE, dictfd, 0)) == MAP_FAILED) return 1; /* Count number of lines in file */ for (size_t i = 0; i < num_of_bytes; i++) { if (dict[i] == '\n') num_of_lines++; } num_of_lines++; num_of_buckets = num_of_lines; htable = calloc(num_of_buckets + 1, sizeof(htable_entry_t)); clist = malloc((num_of_lines + 1) * sizeof(collision_list_t)); size_t prev_start = 0; for (size_t i = 0; i < num_of_bytes; i++) { if (dict[i] == '\n') { htable_insert(prev_start, P1); prev_start = P2; } } /* Compress collision list and update ptrs in htable accordingly */ htable[num_of_buckets].ptr = num_of_lines; cclist = malloc((num_of_lines + 1) * sizeof(compr_collision_list_t)); size_t clines = 0; for (size_t i = 0; i < num_of_buckets; i++) { uint32_t ptr = htable[i].ptr; htable[i].ptr = clines; while (ptr) { cclist[clines].fpos = clist[ptr].fpos; cclist[clines].len = clist[ptr].len; ptr = clist[ptr].prev; clines++; } } free(clist); /* Ready to accept requests */ char *req_buf = malloc(MAX_REQUEST_SIZE); while (!feof(stdin)) { fgets(req_buf, MAX_REQUEST_SIZE, stdin); size_t len = strlen(req_buf); /* Exit on "exit" command */ if (!strncmp(req_buf, "exit\n", len)) break; printf("%s: %s\n", req_buf, htable_lookup(req_buf, len) ? "YES" : "NO"); } free(req_buf); free(htable); free(cclist); munmap(dict, num_of_bytes); close(dictfd); return 0; } ``` 給定測試輸入 (檔名: `inputs`) 如下: ``` gnu linux kernel X XX exit ``` 測試方式: ```shell $ ./strsearch /usr/share/dict/words < inputs ``` 預期執行結果: ``` gnu : YES linux : NO kernel : YES X : YES XX : NO ``` 請補完程式碼。 ==作答區== P1 = ? * `(a)` `prev_start + i` * `(b)` `prev_start + i + 1` * `(c)` `i - prev_start` * `(d)` `i - prev_start + 1` P2 = ? * `(a)` `i` * `(b)` `i + 1` * `(c)` `i - 1` :::success 延伸題目: 1. 解釋上述程式碼運作原理 2. 提出效率更高，且空間佔用更少的 C 程式碼實作 ::: ---
Last changed by  
 
sysprog
System Software Programming
1063

Read more

並行程式設計: Atomics 操作

本文回顧微處理器的 atomic 指令及軟硬體設計考量、memory ordering 及 memory barrier、C11 標準的 <stdatomic.h> 及 Linux 核心介面，和探討經典 lock-free 資料結構和演算法案例。

4/20/2024
2020q1 第 15 週測驗題

目的: 檢驗學員對 timerfd 系統呼叫的認知

4/20/2024
2020q1 第 16 週測驗題

目的: 檢驗學員對 Linux 系統呼叫和 ring buffer 的認知

4/20/2024
Linux 核心原始程式碼巨集: __randomize_layout

Linux 核心不僅是個作業系統的核心，其涉及的領域之廣，可說是整個資訊科技領域的縮影。Linux 核心原始程式碼的 `__randomize_layout` 巨集反映出資訊安全和編譯器設計的議題，本文嘗試探討該巨集的緣由及 Linux 核心的 GCC plugin 的整合機制。

4/20/2024
Read more from sysprog
Published on HackMD