2023q1 Homework3 (quiz3)

--- tags: linux kernel, jserv --- # 2023q1 Homework3 (quiz3) contributed by < [`WangHanChi`](https://github.com/WangHanChi) > > [作業要求](https://hackmd.io/@sysprog/linux2023-quiz3) :::info - 測驗 1 - [ ] 指出 treesort.c 程式碼的缺失並改進 - [ ] 利用 Linux 核心的 list.h 標頭檔改寫並整合進第一次作業的實驗程式碼中，探討 Tree sort 的效率 - [ ] 研讀 Linux 核心的 Red–black tree 程式碼，比較給定的 treesort.c 實作手法，指出後者的改進空間並予以實作 - 測驗 2 - [ ] 解釋上述程式碼運作原理，並比較用紅黑樹實作的 priority queue，應提供完整的測試程式和效能分析 - [ ] Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素，並搭配 git log 來解讀 - [ ] 研讀 Linux 核心原始程式碼，指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 rbtree.h，探究是否可用後者替換，從而爭取到貢獻程式碼到 Linux 核心的機會 - 測驗 3 - [ ] 解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例 - [x] 解釋上述程式碼運作的原理 - [ ] 在 Linux 核心原始程式碼中找到 $log_2(x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $log_2(x)$ 的應用案例並解說。 - [ ] lab0-c 提供類似的實作 log2_lshift16.h，解釋其原理並嘗試改進其效能 - 測驗 4 - [ ] 解釋上述程式碼運作原理 - [ ] 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless - [ ] 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有 ::: ## 測驗 `1` ### 研讀 treesort.c 在 treesort.c 中有幾個重要的結構體 1. camp_iter_t 2. node_t 3. cmap_internel :::spoiler 常用結構體 ```c typedef struct { struct __node *prev, *node; } cmap_iter_t; typedef struct __node { uintptr_t color; struct __node *left, *right; struct __node *next; long value; } node_t __attribute__((aligned(sizeof(long)))); struct cmap_internal { node_t *head; /* Properties */ size_t key_size, element_size, size; cmap_iter_t it_end, it_most, it_least; int (*comparator)(void *, void *); }; ``` ::: 其中最常用的結構體就是 node_t ，定義了每個節點以及[親代節點的顏色與指標](https://hackmd.io/@sysprog/linux-rbtree#%E7%B4%85%E9%BB%91%E6%A8%B9%E7%AF%80%E9%BB%9E) cmap_internel 定義的是 map 內部的資訊，像是 `key`, `element` 還有 `size`的大小，並且紀錄了最尾巴, 最大值跟最小值。 ```c typedef struct __node { uintptr_t color; struct __node *left, *right; struct __node *next; long value; } node_t __attribute__((aligned(sizeof(long)))); ``` 再來可以使用 bitwise 來取得該節點的顏色或是親代節點的顏色，如下面巨集所定義，至於為何是 `~3`，理應要是 `~7`，但是我認為這邊應該是要可以讓程式碼通用於 64 bit 以及 32 bit 的機器，所以選擇 `~3` ，而[老師的筆記中](https://hackmd.io/@sysprog/linux-rbtree#%E8%A6%AA%E4%BB%A3%E7%AF%80%E9%BB%9E) 寫的也是 `~3`。 ```c #define rb_parent(r) ((node_t *) (((r)->color & ~3))) #define rb_color(r) ((color_t) (r)->color & 1) ``` `cmap_rotate_left` 與 `cmap_rotate_right` 這兩個函式主要負責紅黑數的左旋與右旋，詳細的旋轉流程可以參考 [rb-tree 學習筆記](https://hackmd.io/fyJrxz9sQ-SXfdKpImPtOw) ```c static void cmap_l_l(cmap_t obj, node_t *node UNUSED, node_t *parent UNUSED, node_t *grandparent, node_t *uncle UNUSED) { /* Rotate to the right according to grandparent */ grandparent = cmap_rotate_right(obj, grandparent); /* Swap grandparent and uncle's colors */ color_t c1 = rb_color(grandparent), c2 = rb_color(grandparent->right); if (c1 == CMAP_RED) rb_set_red(grandparent->right); else rb_set_black(grandparent->right); if (c2 == CMAP_RED) rb_set_red(grandparent); else rb_set_black(grandparent); } ``` 再來看到有四個非常相似的函式，分別是 `cmap_l_l`, `cmap_l_r`, `cmap_r_r` 以及 `cmap_r_l`，主要處理红黑樹中插入操作中需要處理的四種情况，即`左-左`、`左-右`、`右-右`和`右-左` 左-左和右-右是最基本的情況，即插入節點和其親代節點以及祖父節點都在一條直線上，並且父節點和祖父節點都是紅色。為了保持紅黑樹的性質，需要進行一次右旋轉 `cmap_rotate_right`（左-左情況）或左旋轉 `cmap_rotate_left`（右-右情況），並將父節點和祖父節點的顏色進行調換。左-右和右-左則是稍微複雜一些的情況，即插入節點和其父節點不在同一條直線上。為了處理這種情況，需要進行兩次旋轉操作：首先對插入節點的父節點進行一次旋轉，使其變成左-左或右-右情況，然後再調用左-左或右-右情況的處理函數即可。 :::info TODO 用 graphviz 畫出以上四種情況 ::: 再來看到 `cmap_fix_colors` 這個函式 :::spoiler cmap_fix_colors 原始碼 ```c static void cmap_fix_colors(cmap_t obj, node_t *node) { /* If root, set the color to black */ if (node == obj->head) { rb_set_black(node); return; } /* If node's parent is black or node is root, back out. */ if (rb_is_black(rb_parent(node)) && rb_parent(node) != obj->head) return; /* Find out the identity */ node_t *parent = rb_parent(node), *grandparent = rb_parent(parent), *uncle; if (!rb_parent(parent)) return; /* Find out the uncle */ if (grandparent->left == parent) uncle = grandparent->right; else uncle = grandparent->left; if (uncle && rb_is_red(uncle)) { /* If the uncle is red, change color of parent and uncle to black */ rb_set_black(uncle); rb_set_black(parent); /* Change color of grandparent to red. */ rb_set_red(grandparent); /* Call this on the grandparent */ cmap_fix_colors(obj, grandparent); } else if (!uncle || rb_is_black(uncle)) { /* If the uncle is black. */ if (parent == grandparent->left && node == parent->left) cmap_l_l(obj, node, parent, grandparent, uncle); else if (parent == grandparent->left && node == parent->right) cmap_l_r(obj, node, parent, grandparent, uncle); else if (parent == grandparent->right && node == parent->left) cmap_r_l(obj, node, parent, grandparent, uncle); else if (parent == grandparent->right && node == parent->right) cmap_r_r(obj, node, parent, grandparent, uncle); } } ``` ::: 當插完一個節點後需要進行修復紅黑樹的平衡時所使用的一個函數。該函式主要功能是透過判斷節點的父節點和叔父節點的顏色來決定是進行左旋轉還是右旋轉以及是否需要重新上色等操作，進而維持紅黑樹的平衡性質 :::spoiler cmap_insert 原始碼 ```c /* Insert a key/value pair into the cmap. The value can be blank. If so, * it is filled with 0's, as defined in "cmap_create_node". */ static bool cmap_insert(cmap_t obj, node_t *node, void *value) { cmap_create_node(node); obj->size++; if (!obj->head) { /* Just insert the node in as the new head. */ obj->head = node; rb_set_black(obj->head); /* Calibrate the tree to properly assign pointers. */ cmap_calibrate(obj); return true; } /* Traverse the tree until we hit the end or find a side that is NULL */ for (node_t *cur = obj->head;;) { int res = obj->comparator(&node->value, &cur->value); if (!res) /* If the key matches something else, don't insert */ assert(0 && "not support repetitive value"); if (res < 0) { if (!cur->left) { cur->left = node; rb_set_parent(node, cur); cmap_fix_colors(obj, node); break; } cur->left = cur; } else { if (!cur->right) { cur->right = node; rb_set_parent(node, cur); cmap_fix_colors(obj, node); break; } cur->right = cur; } } cmap_calibrate(obj); return true; } ``` ::: 再來是插入節點的函式，可以看到 `cmap_insert` 這個函式會走訪所有的節點，並且根據其 key 值進行比對，若是比 cur 大的話，就往 right 找，若是比 cur 小的話，就往 left 找。根據這樣的步驟來找到相對應的插入點。最後是 treesort() ```c void tree_sort(node_t **list) { node_t **record = list; cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int); while (*list) { cmap_insert(map, *list, NULL); list = &(*list)->next; } node_t *node = cmap_first(map), *first = node; for (; node; node = cmap_next(node)) { *list = node; list = &(*list)->next; } *list = NULL; *record = first; free(map); } ``` 在第一個 while-loop 中，它會將 list 轉變成紅黑樹的節點，所以這邊應該會進行 list 的迭代，因此，套用 <[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)> 中的**間接指標**，所以會需要使用 `list = &(*list)->next;` ，同理，下面的 for-loop 中也是填入 `list = &(*list)->next;`。最後需要將 list 設定成 NULL，因此最後會是 `*list = NULL;` 至於為何要將原本 sorted node 轉換回 list 是因為我們將原始的 linked list 轉換為紅黑樹，然後按順序遍歷紅黑樹以得到排序後的節點序列。最後，我們需要將排序後的節點重新插入回原始的 linked list 中。這樣才是一個完整的 treesort 演算法。 ## 測驗 `2` AVL tree 其實跟 rb tree 很相似，只是 avl tree 相對來說會更為平衡，也因此，在平衡上， avl tree 可能會花比較多次在進行旋轉上。因此可以得出一個結論為 ==實際應用中，若搜索的次數遠遠大於插入和刪除，那麼選擇 avl tree，如果搜索，插入刪除次數幾乎差不多，應該選擇 rb tree。== ### 解釋上述程式碼 ```c static inline void avl_prio_queue_insert_unbalanced( struct avl_prio_queue *queue, struct avlitem *new_entry) { struct avl_node *parent = NULL; struct avl_node **cur_nodep = &queue->root.node; struct avlitem *cur_entry; int isminimal = 1; while (*cur_nodep) { cur_entry = avl_entry(*cur_nodep, struct avlitem, avl); parent = *cur_nodep; if (cmpint(&new_entry->i, &cur_entry->i) <= 0) { cur_nodep = &((*cur_nodep)->left); } else { cur_nodep = &((*cur_nodep)->right); isminimal = 0; } } if (isminimal) queue->min_node = &new_entry->avl; avl_link_node(&new_entry->avl, parent, cur_nodep); } ``` 上面這個函式主要是在插入節點，透過走訪整個 avl tree 來找到插入的點，其中使用了 `cmpint()` 來比較值來確定是否該插入進去，特別注意，這邊插入節點完之後會是不平衡的狀態，之後要再 call 調整函式來將它變得平衡。 ```c static inline void avl_prio_queue_insert_balanced( struct avl_prio_queue *queue, struct avlitem *new_entry) { struct avl_node *parent = NULL; struct avl_node **cur_nodep = &queue->root.node; struct avlitem *cur_entry; int isminimal = 1; while (*cur_nodep) { cur_entry = avl_entry(*cur_nodep, struct avlitem, avl); parent = *cur_nodep; if (cmpint(&new_entry->i, &cur_entry->i) <= 0) { cur_nodep = &((*cur_nodep)->left); } else { cur_nodep = &((*cur_nodep)->right); isminimal = 0; } } if (isminimal) queue->min_node = &new_entry->avl; avl_insert(&new_entry->avl, parent, cur_nodep, &queue->root); } ``` 這段程式碼與上面的幾乎相同，差在最後是用 `avl_link_node` 或是 `avl_insert` 來進行插入節點。 `avl_link_node` 僅會進行點的插入，可以從這邊看到 [avl_link_node](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2#file-incomplete-avltree-h-L147) 而 `avl_insert` 多了一個 `avl_insert_balance` 的步驟，這個就是調整到平衡的函式，可以從這邊看到 [avl_insert](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2#file-incomplete-avltree-h-L172)。 ```c static inline struct avlitem *avl_prio_queue_pop_unbalanced( struct avl_prio_queue *queue) { struct avlitem *item; bool removed_right; if (!queue->min_node) return NULL; item = avl_entry(queue->min_node, struct avlitem, avl); queue->min_node = avl_next(queue->min_node); avl_erase_node(&item->avl, &queue->root, &removed_right); return item; } ``` 這個函式是用來移除這條 priority queue 裡面最小的點的，可以從 ```c if (!queue->min_node) return NULL; ``` 這裡確定他是要移除最小的點，並且他在移除之後，會是不平衡的，一樣要 call 調整的函式來進行處理。 ```c static inline struct avlitem *avl_prio_queue_pop_balanced( struct avl_prio_queue *queue) { struct avlitem *item; if (!queue->min_node) return NULL; item = avl_entry(queue->min_node, struct avlitem, avl); queue->min_node = avl_next(queue->min_node); avl_erase(&item->avl, &queue->root); return item; } ``` 這邊也與上面相似，也是分成有沒有調整函式的差別而已。 ### Linux 核心也有 AVL tree 的身影，但陸續被紅黑樹替代，請揣摩 Linux 核心開發者的考慮因素在 [linux/Documentation/core-api/rbtree.rst](https://github.com/torvalds/linux/blob/master/Documentation/core-api/rbtree.rst) 當中有提到相關的說明 >Red-black trees are similar to AVL trees, but provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time. 在簡體中文的文件中可以找到翻譯的版本 >红黑树和AVL树类似，但在插入和删除时提供了更快的实时有界的最坏情况性能（分别最多两次旋转和三次旋转，来平衡树），查询时间轻微变慢（但时间复杂度仍然是O(log n)）。也可以從這篇文件中找到蠻酷的東西像是 >Cached rbtrees >Computing the leftmost (smallest) node is quite a common task for binary search trees, such as for traversals or users relying on a the particular order for their own logic. To this end, users can use 'struct rb_root_cached' to optimize O(logN) rb_first() calls to a simple pointer fetch avoiding potentially expensive tree iterations. This is done at negligible runtime overhead for maintenance; albeit larger memory footprint. **帶有 cache 的紅黑樹**，會有這樣子的 API ```c struct rb_node *rb_first_cached(struct rb_root_cached *tree); void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool); void rb_erase_cached(struct rb_node *node, struct rb_root_cached *); ``` ### 研讀 Linux 核心原始程式碼指出曾經/現在使用 AVL tree 的部分，對照 Linux 核心的 rbtree.h，探究是否可用後者替換。使用 ```shell $ ag avl ``` 來查看在 kernel 中還有使用多少 avl tree 可以看到有蠻多的篇幅是在講 driver 相關的，像是 `drivers/fpga/dfl.h`, 或是 `drivers/iio/gyro/st_gyro_core.c` 等等的檔案。目前認為可以替換的條件就是假如今天需要頻繁的插入或移除節點，那使用紅黑樹的效率會更高的多。 ## 測驗 `3` ### 解釋 Linear feedback shift register (LFSR) 的運作原理 >In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. 由 [LFSR](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) 中的敘述可以知道主要會有一條 x 的冪為互質 [Coprimality in sets](https://en.wikipedia.org/wiki/Coprime_integers#Coprimality_in_sets) 線性多項式 (例如 $x^{16}+x^{14}+x^{13}+x^{11}+1$ )，接著在對其用 `XOR(^)` 來做運算，並且會將新生成的 bit 放進 [m-sequence](https://en.wikipedia.org/wiki/Maximum_length_sequence) 由此來產生一條二進制的序列。 ![](https://i.imgur.com/yV2uOct.png) 例如使用以下程式碼 ```c #include <stdint.h> unsigned lfsr_fib(void) { uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */ uint16_t lfsr = start_state; uint16_t bit; /* Must be 16-bit to allow bit<<15 later in the code */ unsigned period = 0; do { /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u; lfsr = (lfsr >> 1) | (bit << 15); ++period; } while (lfsr != start_state); return period; } ``` 原本的狀態是 `0xACE1` ，下一個就會是 `0x5670` ，由此可以建立出 M-sequence 而這樣的概念的應用可說是相當廣泛 1. 用來當作 [clock divider or as a counter ](https://en.wikipedia.org/wiki/Clock_divider) 2. 在密碼學中作為 [PRNG](https://en.wikipedia.org/wiki/Pseudo-random_number_generator) 3. 數位廣播及通訊中作為 [Scrambling](https://en.wikipedia.org/wiki/Scrambler) ### 在 Linux 核心原始程式碼中找到 `LFSR` 首先在 linux 的目錄夾下使用 `$ ag "lfsr"`，會找到所有內文包括 lfsr 的檔案，接著進行一一過濾，其中一個為 [linux/drivers/net/ethernet/sfc/siena/farch.c](https://github.com/torvalds/linux/blob/master/drivers/net/ethernet/sfc/siena/farch.c) ```c=1892 /* The filter hash function is LFSR polynomial x^16 + x^3 + 1 of a 32-bit * key derived from the n-tuple. The initial LFSR state is 0xffff. */ static u16 efx_farch_filter_hash(u32 key) { u16 tmp; /* First 16 rounds */ tmp = 0x1fff ^ key >> 16; tmp = tmp ^ tmp >> 3 ^ tmp >> 6; tmp = tmp ^ tmp >> 9; /* Last 16 rounds */ tmp = tmp ^ tmp << 13 ^ key; tmp = tmp ^ tmp >> 3 ^ tmp >> 6; return tmp ^ tmp >> 9; } ``` 這段程式碼實作了一個雜湊函數，它使用了一個32位的 key ，並且基於 n-tuple 推導出來。此函式使用了線性反饋移位寄存器（LFSR）的多項式 $x^{16} + x^3 +1$。初始化的 LFSR 為 `0xffff`。它的操作流程如下：首先，將32位的 key 右移16位，並且對 `0x1fff` 進行 `XOR (^)` 操作。然後，對這個結果進行三次右移 3 位的操作，然後三次右移 6 位的操作，最後三次右移 9 位的操作。接下來，進行 16 次操作，將上一輪結果進行左移 13 位，然後對 key 進行`XOR (^)`操作，再對這個結果進行三次右移 3 位的操作，然後三次右移 6 位的操作，最後三次右移 9 位的操作。簡單來說，這個雜湊函數是將32位的 key 轉換成 16 bit的 hash 值，使用了 LFSR 多項式和一些 bitwise 操作。 ### 解釋上述程式碼運作的原理 [完整的程式碼](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d) 可以看到下面的程式碼目的是實作 LFSR ，在上方有解釋過 LSFR 的原理了，這邊就不再贅述，他的線性函數分成 32 bit 與 64 bit 的版本，並且都是不可再約分的冪之函數 - 32-bit - $x^{64}+x^{61}+x^{34}+x^{9}+1$ - 64-bit - $x^{32}+x^{22}+x^{2}+x^{1}+1$ 而在程式碼實作部分就將 `*up` 按照公式來進行平移，並且將其做 `XOR (^)` 的處理。再和 1 進行 `AND (&)` 運算，獲取最右側的 bit。這個 bit 會成為新的隨機數 new_bit。接著，將原資料 `*up` 向右 shift 1，然後將 new_bit 插入最左側。完成後，`up` 指向的數據就是更新後的 LFSR 序列，符合下面的這張**示意圖**的步驟。 ![](https://i.imgur.com/yV2uOct.png) ```c /* Implementation of LFSR (linear feedback shift register) * on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1 * (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1) */ static void lfsr(uint64_t *up) { uint64_t new_bit = ((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u; /* don't have to map '+1' in polynomial */ *up = ((*up) >> 1) | (new_bit << 63); /* shift *up by 1 to RIGHT and insert new_bit at "empty" position */ } ``` 接著可以看到下面是一個 char 的陣列 ```c static const char log_table_256[256] = { #define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, _(4), _(5), _(5), _(6), _(6), _(6), _(6), _(7), _(7), _(7), _(7), _(7), _(7), _(7), _(7), #undef _ }; #undef _ ``` 這個巨集使用了前置處理器，詳情可以參考[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)。主要的內容是填充一個 256 個內容的查找表，首先會先有 ``` -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, ``` 這些數字出現的次數都是一個，接下來的 `_(4)` ，會透過 `#define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n` 這個巨集展開成 16 次的 4 ，也就是 `4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4` 這樣，透過這個方式既可以簡潔的表達也更容易了解規律。可以整理成下面這樣 | log_table_256[n] | 對應的值 | | ---------------- | ---------- | | 0-15 | 直接參即可 | | 16-31 | 4 | | 32-47 | 5 | | 48-63 | 5 | | 64-79 | 6 | | 80-95 | 6 | | 96-111 | 6 | | 112-127 | 6 | | 128-143 | 7 | | 144-159 | 7 | | 160-175 | 7 | | 176-191 | 7 | | 192-207 | 7 | | 208-223 | 7 | | 224-239 | 7 | | 240-255 | 7 | ```c uint64_t log2_64(uint64_t v) { unsigned r; uint64_t t, tt, ttt; ttt = v >> 32; if (ttt) { tt = ttt >> 16; if (tt) { t = tt >> 8; if (t) { r = AAAA + log_table_256[t]; } else { r = BBBB + log_table_256[tt]; } } else { t = ttt >> 8; if (t) { r = CCCC + log_table_256[t]; } else { r = DDDD + log_table_256[ttt]; } } } else { tt = v >> 16; if (tt) { t = tt >> 8; if (t) { r = EEEE + log_table_256[t]; } else { r = FFFF + log_table_256[tt]; } } else { t = v >> 8; if (t) { r = GGGG + log_table_256[t]; } else { r = HHHH + log_table_256[v]; } } } return r; } ``` 由題目的要求可以知道 >- log2_64 : 計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor) 這個函式主要計算以 2 為底的 x 的對數，並且根據向右 shift 的結果分成了 8 個部分，再透過老師所屏蔽的部分加上剛剛的查找表，就可以知道回傳的 `r` 是多少。主要的實作邏輯以下圖表示 ```graphviz digraph Algorithm { rankdir=L; node[shape="record"]; v [label="v"]; ttt[label="{<f0> ttt |{ttt = 0|<here> ttt != 0}}", style=bold]; tt_0 [label="{ <f0> tt |{<here0>tt = 0|<here1> tt != 0}}", style=bold]; tt_1 [label="{ <f0> tt |{<here0>tt = 0|<here1> tt != 0}}", style=bold]; t_0 [label="{ <f0> t |{<here0>t = 0|<here1> t != 0}}", style=bold]; t_1 [label="{ <f0> t |{<here0>t = 0|<here1> t != 0}}", style=bold]; t_2 [label="{ <f0> t |{<here0>t = 0|<here1> t != 0}}", style=bold]; t_3 [label="{ <f0> t |{<here0>t = 0|<here1> t != 0}}", style=bold]; r [label="return r;"] l0[label="log_table_256"] l1[label="log_table_256"] l2[label="log_table_256"] l3[label="log_table_256"] l4[label="log_table_256"] l5[label="log_table_256"] l6[label="log_table_256"] l7[label="log_table_256"] v -> ttt[shape=plaintext;label=" v >> 32"] ttt -> tt_0[shape=plaintext;label=" v >> 16"] ttt -> tt_1[shape=plaintext;label=" ttt >> 16"] tt_0:here0 -> t_0[shape=plaintext;label=" v >> 8"] tt_0:here1 -> t_1[shape=plaintext;label=" tt >> 8"] tt_1:here0 -> t_2[shape=plaintext;label=" ttt >> 8"] tt_1:here1 -> t_3[shape=plaintext;label=" tt >> 8"] t_0:here0 -> l0[shape=plaintext;label="add"] l0 -> r t_0:here1 -> l1[shape=plaintext;label="add"] l1 -> r t_1:here0 -> l2[shape=plaintext;label="add"] l2 -> r t_1:here1 -> l3[shape=plaintext;label="add"] l3 -> r t_2:here0 -> l4[shape=plaintext;label="add"] l4 -> r t_2:here1 -> l5[shape=plaintext;label="add"] l5 -> r t_3:here0 -> l6[shape=plaintext;label="add"] l6 -> r t_3:here1 -> l7[shape=plaintext;label="add"] l7 -> r } ``` 因此只要跟隨著這個邏輯的話，就可以依序得出 `AAAA` 到 `HHHH`，是從 `56` 到 `0` 的等差數列。 :::info 這題可以搭配電腦內的計算機來解題 ![](https://i.imgur.com/OHVNmMq.jpg) 利用中間紅色框框的部份，一共八個區域，分別對應到 `uint64_t log2_64(uint64_t v)` 的八個 if-else 敘述句，只要按照函式的流程暗計算機就可以得到相對應的答案了。 ::: ```c void set_N_BUCKETS(unsigned int n) { N_BUCKETS = n; } void set_N_BITS() { N_BITS = log2_64(N_BUCKETS); } ``` 接著會設定 `N_BUCKETS` 以及 `N_BITS` ```c /* n == number of totally available buckets, so buckets = \{0, ...,, n-1\} * ASSUME n < (1 << 32) */ unsigned int bucket_number(uint64_t x) { uint64_t mask111 = (1 << (N_BITS + 1)) - 1; uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */ unsigned char leq = ((x & mask111) < N_BUCKETS); /* leq (less or equal) is 0 or 1. */ return (leq * (x & mask111)) + ((1 - leq) * ((x >> (N_BITS + 1)) & mask011)); /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity. * '... & mask011' guarantees that the result is less or equal N_BUCKETS. */ } ``` 再來會根據剛剛所設定的 `N_BITS` ，接著就設定 `mask111`, 以及 `mask011` ，從命名就可以發現前者會以 `111` 開頭，後者會以 `011` 開頭。例如 `N_BITS` 是 6 的話，則 `mask111` = 127 ，`mask011` = 63 ``` mask111 = 63 -> 111 1111 ------------- mask011 = 31 -> 011 1111 ``` 接著藉由下方程式碼可以知道，`leq` 為 0 或 1，所以在 return 的部份，就只會有 `(leq * (x & IIII))` 或是 `((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ))`，並且根據註解得知， `JJJJ` 會是 `mask011` ，`IIII` 會是 `mask111` 來避免超過 `num_of_buckets` 。 ```c unsigned char leq = ((x & mask111) < N_BUCKETS); /* leq (less or equal) is 0 or 1. */ return (leq * (x & IIII)) + ((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ)); /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity. * '... & mask011' guarantees that the result is less or equal N_BUCKETS. */ ``` 接著會去執行 `fill_buckets` 這個函式，主要內容就是取得透過 lfsr 來取得偽隨機數 ## 測驗 `4` - 輸入必為大於 0 的數值 - 用以計算 $log_2(x)$ - ceil : smallest integral value not less than argument - log2 : return the base 2 logarithm of x. ```c int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r; shift = (x > 0xFF) << 3; x >>= shift; r |= shift; shift = (x > 0xF) << 2; x >>= shift; r |= shift; shift = (x > 0x3) << 1; x >>= shift; return (r | shift | x >> 1) + 1; } ``` 這段程式碼可以將輸入轉換以 2 為底的 log 對數，並且會輸出 $\lceil log_2(x)\rceil$ 以一個簡單的例子來了解程式碼 ``` 10 進制的數值 11877 為輸入 x 先將其轉換為 2 進制 00101110 01100101 ---------------------------------- 首先, 先減 1 變成 11876 (00101110 01100100) 再來 r = 0, x = x >> r => 等於把 x 的最低 16 個 bit 去除可以得到原來的 x 再來, 設定 shift = 1 << 3 x = x >> shift => 等於把 x 的最低 8 個 bit 去除 r = r | shift , r = 1100 再來, 設定 shift = 1 << 2 x = x >> shift => 等於把 x 的最低 4 個 bit 去除 r = r | shift , r = 1110 再來, 設定 shift = 1 << 1 x = x >> shift => 等於把 x 的最低 2 個 bit 去除最後要進行 return 回傳值會是 ( 1110 | 10 | 0) + 1 = 14 以計算機求得的數字也是如此 ``` ### 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless 原本的程式碼並沒有辦法處理 x = 0 的情況，如果遇到 x = 0，就會輸出錯誤的結果，於是需要將程式碼修改，讓其變成 branchless 的版本並且一樣的精簡。 ```c int ceil_log2_v2(uint32_t x) { uint8_t r = ((x & (x - 1)) != 0); return (32 - __builtin_clz(x) - 1 + r); } ``` 可以從幾個簡單的例子來觀察 ``` 0b 11010 = 26 , 而 log2(26) 會是 5 0b 100000100000101010111100111101 = 545435453, 而 log2(545435453) 會是 30 ``` 由上述的例子可以發現，我們需要先進行判斷這個數字究竟是否為 2 的冪，如果 `(x & (x-1)) == 0` 就代表 x 是 2 的冪，然後再決定 r 是否為 1。再來就是找出這個數字的最大為 1 的位數，也就是使用 `32 - __builtin_clz(x-1)`，接著他有可能會是 `0b 1000 = 8` ，這種 2 的冪，但是有進位的數值，所以會需要 -1 再根據 r 來決定是否將其加回。 ### 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 ## 參考資料 - [torvalds/linux](https://github.com/torvalds/linux)