# 2022q1 Homework3 (quiz3) contributed by < `happyjack91630` > > [作業需求](https://hackmd.io/@sysprog/BJJMuNRlq) > [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3) ## 測驗 `1` ：GENMASK :::success EXP1 = 63 - h EXP2 = l ::: 產生連續的 bitmask。 ```c #define GENMASK(h, l) \ (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT))) //(~0UL = 1111...111) ``` 例如: * `GENMASK(6, 4)` 產生 01110000 * `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元) `GENMASK(h, l)` 可以看出就是在h ~ l + 1 位元以外的地方都是0。 `((~0UL) >> (LEFT)`的作用是將63 ~ h位元設成0，所以`LEFT = 63 - h`。 `(~0UL) >> (l) << (RIGHT))`的作用是將 l - 1 ~ 0位元設成0，所以`RIGHT = l`。 `((~0UL) >> (63 - h)` 跟 `(~0UL) >> (l) << (l))`做 and 運算，就能將h ~ l + 1，l - 1 ~ 0 位元清除成0，保留其他位元為1。 ## 測驗 `2` ：align down >參考 `kevinshieh0225` :::success EXP1 = (struct foo *)(v & -3) ::: ```c= struct foo; struct fd { struct foo *foo; unsigned int flags; }; static inline struct fd to_fd(unsigned long v) { return (struct fd){EXP1, v & 3}; //foo = exp1, flags = v & 3; } ``` >函式 `to_fd` 接受指定的地址 `v`，填入一個 `fd` 結構體，並確保第一個成員的地址得以依據〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 `struct foo`; 運用〈你所不知道的 C 語言：指標篇〉提及的 forward declaration 技巧，可在實作階段才提供具體 `struct foo` 的定義。 我們希望將`to_fd`指派在地址`v`且向下對齊的位置上。舉例來說，v = 7，向下對齊要變成4，v = 15，向下對齊要變成12，所以比v小的最大4的倍數。(v & ~3)就能取到比v小且為4的倍數。但是`struct fd`裡第一個存的是`struct foo *foo`，所以要將`v`轉型成`struct foo`的型態。 ## 測驗 `3` ：Reverse Bits :::success EXP2 = (x & 0x33) << 2 EXP3 = (x & 0x55) << 1 ::: ```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; } ``` 這裡我用 `x = 12345678`當作以下解釋程式碼的範例。 ```c #include <stdint.h> //每次都取一半來做反轉 uint8_t rev8(uint8_t x) { x = (x >> 4) | (x << 4); // (12345678 >> 4) | (12345678 << 4) = 56781234 x = ((x & 0xCC) >> 2) | (EXP2); // ((56781234) & 11001100) >> 2) | ((56781234) & 00110011)) << 2 = 78563412 x = ((x & 0xAA) >> 1) | (EXP3); // ((78563412) & 10101010) >> 1 | ((78563412) & 01010101) << 1 = 87564321 return x; } ``` :::warning 避免說「一半」這種詞彙，請將自己設想在「科技公司面試場合」，用字要精準，無論你如何位移，資料寬度仍是一致，因此跟「一半」的概念不同。 :notes: jserv ::: ## 測驗 `4` ： foreach 巨集 >參考`hsuedw` :::success EXP4 = ++_foreach_i EXP5 = ++_foreach_i ::: > 延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法: ```c= int i; foreach_int(i, 0, -1, 100, 0, -99) { printf("i is %i\n", i); } const char *p; foreach_ptr(p, "Hello", "world") { printf("p is %s\n", p); } ``` 對應的巨集定義: ```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__}))) ``` ```c= int i; foreach_int(i, 0, -1, 100, 0, -99) { printf("i is %i\n", i); } ``` 先針對上述的`foreach_int(i, 0, -1, 100, 0, -99)`做解析，利用相關巨集定義做展開，對展開一項一項做解析。 ```c= int i; for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); (i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]) { printf("i is %i\n", i); } ``` * `(int[]){0, -1, 100, 0, -99})` 表示宣告一個int array，裡面包了這5個元素。 * `((int[]){0, -1, 100, 0, -99})[0]` 表示取這個array的第0個index的值，也就是0。 * `((i) = ((int[]){0, -1, 100, 0, -99})[0])` 表示將這個array的第0個index的值，assign給i。 * `unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0)` ，這段程式碼可以看做成`unsigned _foreach_i = (0, 0)`，第一個0的由來是取第0個index的值，第二個0可以看成是將`_foreach_i`的初始值設為0。 * `_foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int);` 這個為for loop的中止條件，_foreach_i(index)要小於array的長度。 * `(i) = ((int[]){0, -1, 100, 0, -99,0})[EXP4]` for迴圈有了初始條件，有了終止條件，剩下的就是要做`_foreach_i(index)`的狀態變化。那這題是要將`_foreach_i`做遞增，讓array跑完。`EXP4 = ++_foreach_i`。 那第二個巨集`foreach_ptr`就跟上述想法一致，所以`EXP5 = ++_foreach_i` ## 測驗 `5` ：LeetCode 29. Divide Two Integers :::success EXP6 = dvs << shift EXP7 = dvd -= dvs << shift ::: 針對 LeetCode 29. Divide Two Integers，以下是可能的實作: ```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; } ``` * 第4行到第15行的程式碼要先辨識出最後的答案是正數還是負數。 * 第17行到第27行的程式碼就是在做除法運算，res會是商，那EXP7則是算餘數是多少。 * 第29行到第32行則是再把結果，變成正數or負數。 ![](https://i.imgur.com/pQ3RLvd.png) ## 測驗 `7` ：ilog32 考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作: ```c= int ilog32(uint32_t v) { int ret = v > 0; int m = (v > 0xFFFFU) << 4; //0xFFFFU = 0x0000FFFF 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; } ``` 這題換句話說，就是要取2進位，最高位元的1在甚麼地方?這邊用的方法，類似於binary search的方法，每次都找**一半**。 ![](https://i.imgur.com/4JydSZr.png) ## 測驗 `9` ：ROUND_UP_TO_ALIGNMENT_SIZE :::success MMM = 1 NNN = MAX_ALIGNMENT - 1 ::: 考慮以下進行記憶體地址對齊 (alignment) 的巨集: ```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)) ``` 這題是要考記憶體對齊，對齊的單位為16，也就是要補滿到最近的16倍數，例如 7 => 16，15 => 16，29 => 32，換句話說，就是要無條件進位到16的倍數。要將 x 進位到 16 倍數的想法就是，先 x + 15 再將後面3個bit(bit 0 ~ 3)清成0。 ![](https://i.imgur.com/JsIAep7.png) >上述方法可以應用在各種 2 的冪進位系統上。 ## 測驗 `10` ：DIVIDE_ROUND_CLOSEST :::success RRR = __x + (__d >> 1) SSS = __x - (__d >> 1) ::: 此題實作整數除法取近似整數。 ```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)); \ }) ``` 原本C的整數除法是**無條件捨去法**，這題的函示要做的除法是**四捨五入**。 ```c= typeof(x) __x = x typeof(divisor) __d = divisor; ``` 上述宣告方式是要避免巨集展開時，導致多次的evalution，所以才先將x跟divisor的值放入另一個參數中，防止變數被更改到(之所以要檢查是否為 unsigned ，是因為跟 unsigned 運算的 signed 數值也會變 unsigned ，因此恆大於等於 0)。 ```c= (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \ (((__x) > 0) == ((__d) > 0))) ``` >參考`jim12312321` 這條件式主要是先判斷結果有沒有可能是負數，是結果採用**正數除法**還是**負數除法**。x 如果為int，代表typeof((x) - 1 > 0)不成立，那如果 x 為unsigned int ，代表typeof((x) - 1 > 0)成立。 ```c= ((RRR) / (__d)) ((SSS) / (__d)); ``` 先撇開三元條件式，上述程式碼是要去計算除法且**四捨五入後**的結果。 ![](https://i.imgur.com/U181hTf.png) :::danger 改用 Graphviz 或 HackMD 支援的標記語法來製圖 :notes: jserv ::: 根據上述的範例得知，可以先讓被**除數(x)先加除數(divisor)的一半**，再去做C的整數除法，就能做到四捨五入了。但是上述想法只用於正數除法，**負數除法則是要先減再除**，答案才會對。
Last changed by  
 
于乃喆
357

Read more

Linux 核心實作 hankmd 筆記

GitHub 2022q1 Homework1 (lab0) 2022q1 Homework1 (quiz1) 2022q1 Homework2 (quiz2) 2022q1 Homework3 (fibdrv)

7/4/2022
2022q1 Project (cpumemory)

contributed by ??? 目標 [ ] 閱讀 Ulrich Drepper 於 2007 年撰寫的論文《 [What Every Programmer Should Know About Memory] [ ] SRAM DRAM 讀取差異 [ ] Virtual Memory [ ] TLB 作用 [ ] Cache Line Sharing 成本 [ ] MESI

6/29/2022
2022-04-04

contributed by < happyjack91630 > happyjack91630 GitHub 測驗 1 利用上述 SIMD within a register (SWAR) 的技巧，我們可改寫為以下 memchr_opt 函式: #include <stddef.h> #include <stdint.h> #include <limits.h> #include <string.h>

4/5/2022
2022q1 Homework4 (quiz4)

contributed by < happyjack91630 > 作業需求 :::danger 注意書寫規範和使用通順的漢語。 :notes: jserv ::: 測驗 1 : $\lceil log_2(x) \rceil$

4/5/2022
Read more from 于乃喆
Published on HackMD