# 2021q1 Homework2 (quiz2)
contributed by < `cyrong` >
## Q1: Linux 核心 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 與 mergesort
### 解釋上述程式碼運作原理，指出改進空間並著手實作
#### `container_of`
```cpp
/**
* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
#ifndef container_of
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#endif
```
`__extension__` 代表程式要使用 GNU extension ，加上 `__extension__` 後可以去除 compile warning
[參考資料](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#index-_005f_005fextension_005f_005f)
`__typeof__()` 會回傳傳入值的型態，並使用此型態宣告 `__pmember`
最後一步
```c
(type *) ((char *) __pmember - offsetof(type, member));
```
先是使用 `(char *)` 取得 `__pmember` 的絕對位址
之後再減去 `offsetof(type, member)` 就可以得到這個 type 的開頭位址
最後用 `(type *)` 把開頭位址轉型成 pointer to `type`
在這裡有幾個點可以探討
1. `((type *) 0)->member` 被傳進了 `__typeof__`
先看一下 `__typeof__` 的 argument 要輸入什麼
參考 gcc onlinedoc 中的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof)
`typeof` 要輸入的 argument 是 expression or type
看起來 `((type *) 0)->member` 是一個 expression
再進一步分析
`(type *) 0` = 0 is cast to a pointer to struct type，也就是說這段是一個指標
`((type *) 0)->member` 把 0 做 member offset 的位移後取值
此時的型態就會是 member 的型態，因為已經將 0 轉型為 type
再放入 `typeof` 中就可以得到 struct 中 member 的型態
2. `({})` 的使用，其實就是在括號中作運算，
詳情可見 [gcc statement and declaration in expression](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)
#### `INIT_LIST_HEAD`
```cpp
/**
* INIT_LIST_HEAD() - Initialize empty list head
* @head: pointer to list head
*/
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
```
對 list head 作初始化，一開始的 head 中 next 和 prev 都是自己
#### `list_add_tail()`
```cpp
/**
* list_add_tail() - Add a list node to the end of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
先做一個 `*prev` 為 `head->prev` 也就是 tail
接下來對這個 tail 跟 head 作配合操作就可以 add tail 了
#### `list_del()`
```cpp
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
```
用傳入的 `*node` 得到這個 node 的前後兩個 node 並接在一起，便成功作到 del node 的效果
#### `list_empty()`
```cpp
/**
* list_empty() - Check if list head has no nodes attached
* @head: pointer to the head of the list
*/
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
回傳 `head->next` 是否為 `head`
代表如果只有 `head` 此 list 就是 empty
#### `list_is_singular()`
```cpp
/**
* list_is_singular() - Check if list head has exactly one node attached
* @head: pointer to the head of the list
*/
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
回傳 list 是否只有一個 node
若 `head->next` 和 `head->prev` 相同代表只有一個 node
#### `list_splice_tail`
```cpp
/**
* list_splice_tail() - Add list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next, *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
```
把 `list` 中所有的 node 接到 `head` 的尾端
不需要重新鏈接，只需要有 node 們的 first 和 last
把 first 接到 `head` 尾，再將 last 接到 `head->prev` 就完成了
#### `list_cut_position()`
```cpp
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
將 `head_from` 中的 `node` 以前的所有 nodes 都搬到 `head_to` 後
#### `list_entry()`
```cpp
/**
* list_entry() - Calculate address of entry that contains list node
* @node: pointer to list node
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_entry(node, type, member) container_of(node, type, member)
```
利用 `container_of` 找到輸入 node 之初始位址
#### `list_first_entry()`
```cpp
/**
* list_first_entry() - get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
使用 `list_entry()` 但是輸入的 node 為 `(head)->next` 因此得到的會是 list 中的第一個 node
#### `list_for_each()`
```cpp
/**
* list_for_each - iterate over list nodes
* @node: list_head pointer used as iterator
* @head: pointer to the head of the list
*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
利用 for 迴圈走訪 list 所有節點
#### 搭配使用的 merge sort
```c=
#include <string.h>
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
struct list_head list;
} queue_t;
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (COND1 || COND2)
break;
fast = fast->next->next;
}
return list_entry(TTT, list_ele_t, list);
}
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
if (list_empty(lhs)) {
list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
list_splice_tail(rhs, head);
return;
}
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = list_entry(lhs->next, list_ele_t, list)->value;
char *rv = list_entry(rhs->next, list_ele_t, list)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
void list_merge_sort(queue_t *q)
{
if (list_is_singular(&q->list))
return;
queue_t left;
struct list_head sorted;
INIT_LIST_HEAD(&left.list);
list_cut_position(&left.list, &q->list, MMM);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
}
```
#### `get_middle()`
這段程式碼用的手法是 `slow` 每動一格 `fast` 就會動兩格
而等到 `fast` 到達 list 尾端時 走過的 node 數是 list 的大小 `n`
這時 `slow` 正好走過 `n/2` 也就是 list 的中間了
#### `list_merge()`
這裡是在作 mergesort 的合併 `lhs` 代表 left hand side，
`rhs` 代表 right hand side
從兩邊 list 的頭開始走完兩個 list 的所有 node
合併進 `head`
#### quiz 題目
20 行的 `COND1` 和 `COND2` 是為了判斷 `slow` 是否已經到達了 list 的中間
而分成 `COND1` 和 `COND2` 的原因是 `n` 可能是奇數或偶數
`COND1` 對應的是偶數的情況 `fast->next == list`
`COND2` 對應的是奇數的情況 `fast->next->next == list`
24 行是已經找到 middle 了 並且要得到其位址
middle 也就是 `slow` 因此 `TTT` 傳入 `slow`
59 行的目的是把 `list` 切成兩半，分別再作 mergesort
`MMM` 是要找的 middle node ，所以應該要用 `get_middle()`
要注意的是 `get_middle()` 回傳的 type 是 `list_ele_t`
但是 `list_cut_position()` 要輸入的參數是 `list_head *`
因此要對找到的 `list_ele_t` 的 `list` 作取值，並且傳入他的位址，參數型態才會對
參數型態的問題在 `get_middle()` 也要注意，要傳入的是 `list_head *`
所以 `MMM` 答案應是 `&(get_middle(&q->list)->list)`
---
## Q2: power-of-2
### 解釋程式碼
```c=
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> X;
N |= N >> Y;
N |= N >> Z;
return (N + 1) >> 1;
}
```
假定 N = 10101~2~ = 21~10~，那麼 func(21) 要得到 16，請補完程式碼，使其運作符合預期。
16~10~ = 10000~2~
而 `return (N + 1) >> 1` = 10000~2~
可以回推 `N` 是 11111~2~
再從程式碼第3行看
```c=3
N |= N >> 1;
```
`N` = `10101 | (10101 >> 1)` = `10101 | 1010` = `11111`
雖然這樣看起來就是答案了
不過程式需要的功能是 change all right side bits to 1
在這個 `uint16_t` 的 type 下，最大的值就是 16 個 bits 都是 1
會是 1 的最高位也就是 16
要做到可以把最高位 1 的 right side 都變成 1
假設現在要操作的值是 `1000 0000 0000 0000`
作第三行的操作後是 `1100 0000 0000 0000`
用 4 步去把 1 個 1 用 `>>` 複製成 16 個
最好的方法就是每次都可以把 1 的數量加倍
`1100 0000 0000 0000`
=> `1111 0000 0000 0000`
=> `1111 1111 0000 0000`
=> `1111 1111 1111 1111`
之後要位移的量就分別是 2, 4, 8
因此 `X = 2` `Y = 4` `Z = 8`
## Q3: bitcpy
考慮到一個 `bitcpy` 實作，允許開發者對指定的記憶體區域，逐 bit 進行資料複製。
### 解釋程式碼
```c=
#include <stdint.h>
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
RRR;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
DDD;
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
}
```
輸入的參數有 dest, src, write offset, read offset, count
一開始會有一些變數設定
有 `read_lhs / rhs`, `write_lhs / rhs` 以及作過處理的 `source` 跟 `dest`
```c=9
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
```
`read_lhs` = `_read` & `7` = `_read` % `8`
`read_rhs` = `8` - `read_lhs`
`read_lhs` 目的是留下 read offset 的 0 ~ 2 bit 的值
因為程式是以一個 byte 作處理
所以配合 `read_rhs`
left 處理開頭，right 處理收尾
而 `source` 的處理
```c
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
```
讓 `source` 是 `_src` 移動 `(_read / 8)` 個單位，也就是 `(_read / 8)` bytes
`source` 就是開始讀取的地方
`write_lhs` 和 `write_rhs` 的作法和 read 一樣
`dest` 則是和 `source` 一樣
接著是兩個 mask 是為了方便等一下的 `bitcpy` 方便使用
```c=16
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
```
最下面的 while 迴圈就是在作 bit copy
```c=40
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
RRR;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
DDD;
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
```
41~42
創一個 `uint8_t` data 是當前的 `source`，之後 `source`++， `source` 進到下個 byte
`bitsize` 最大到 8 為了方便使用 mask
43~47
`if (read_lhs > 0)` 這裡判斷有沒有需要對 `data` 作調整
要讓 `data` 是要讀的第一個 byte 的第 `read_lhs` 到 第 7 個 bit ( bit 是 0~7 )
然後再接上下一個 byte 從 0 開始的 `read_rhs` 個 bits
`RRR` 要作的是把 `data` 往左 shift `read_lhs` 次
`RRR` = `data <<= read_lhs`
下一個判斷是 要複製的 `bitsize` 有沒有超過 `read_rhs` 也就是有沒有要跨 byte
如果有就把下個 byte 從 0 開始的 `read_rhs` 個 bits
複製到 data 前 `read_rhs` 個 bits
49~50
如果 `bitsize` 不到 8 就把用不到的 bits 清掉
手法是利用 `read_mask`
54~58
要複製的 `bitsize` 會超出當前 byte 因此要作兩次複製
目前的 byte 利用 `mask` 操作，最後留下的資料是:
前 `write_lhs` bits 保持原狀，後面的 bits 換成 `data >> write_lhs`
下一個 byte 操作前，先置換 `original`
把 `original` 換成下一個 byte 的 original
而`write_mask` 把不會操作到的 bits 保持原狀
進到下一個 byte 操作
把剛剛做好的 `original` & `data << write_rhs`
59~63
`else` 指 `bitsize` 個 bit 操作不會超出 byte bound
因此只需要改 `bitsize` 個 bit ，其他 bits 都要保持原狀
因此 `mask` 要改成除了前 `write_lhs` 個 bit 保持外
還要保持 `write_lhs` + `bitsize` 後的 bits
因此 `DDD` |= `write_mask[write_lhs + bitsize]`
`write_mask[write_lhs + bitsize]` 就是剛才提到 `write_lhs` + `bitsize` 後的 bits
`mask` 做好後用 `original` 與 `mask` 調整好再複製 `data >> write_lhs`
Sign in with Wallet
Connect another wallet