# 2021q1 Homework2 (quiz2)
contributed by < `tigger12613` >
> [2021q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz2)
## 測驗 `1`
### 解釋程式碼運作原理
#### List add tail
新增一個節點在鏈的尾端
```cpp
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;
}
```
before add node
```graphviz
digraph a {
rankdir=LR;
edge [dir = both]
node[shape=box]
head [label = "head"]
tail [label = "tail"]
middle[label = "..."]
first [label = "first"]
head->first
first->middle
middle ->tail
tail-> head
}
```
after add node ，紅色是新增的，灰色是移除的
``` graphviz
digraph b {
rankdir=LR;
edge [dir = both]
node[shape=box]
new_node [ label = "new node" fontcolor = red color = red]
head [label = "head"]
tail [label = "tail"]
middle[label = "..."]
first [label = "first"]
head->first
first->middle
middle ->tail
head->tail [ color = gray]
tail->new_node [color = red]
new_node->head [color = red]
}
```
#### List delete
移除一個指定的節點
```cpp
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
```
```graphviz
digraph a {
rankdir=LR;
edge [dir = both]
node[shape=box]
none1 [label = "..." shape=none]
prev [label = "prev node"]
next [label = "next node"]
removed [label = "removed node" fontcolor = gray color=gray ]
none2 [label = "..." shape=none]
prev->removed [color=gray]
none1->prev
removed->next [color=gray]
prev->next [color=red]
next->none2
}
```
#### Get middle
找到鏈的中點
用一個快指標跟慢指標，快指標一次走兩個節點，慢指標一次走一個節點，最後慢指標會停在鏈的中點。
```cpp
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);
}
```
COND1 = `fast->next == list`
COND2 = `fast->next->next == list`
TTT = `slow`
#### Merge sort
```cpp
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);
}
```
MMM = `&get_middle(&q->list)->list`
`q` is `queue_t`
`q->list` is `struct list_head`
`&q->list` is `struct list_head*` is type is `get_middle`needed.
So, chose `&q->list` be the varable of `get_middle`
MMM need `struct list_head *node`
`get_middle` return `list_ele_t`
`list_ele_t->list` is `struct list_head`
`&list_ele_t->list` is we want.
By checking the type we will know MMM = `&get_middle(&q->list)->list`
```c
static list_ele_t get_middle(struct list_head *list)
```
---
## 測驗 `2`
### 解釋程式碼運作原理
考慮函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2 (漢字可寫作為 2 的冪)
```cpp
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;
}
```
X = 2
Y = 4
Z = 8
#### 解法
小於或等於 N 的 power-of-2 就是 N 保留二進位第一個 1 剩下的都變成 0 就是答案。
舉例來說
```c
if N = 01??????????????
after N |= N >> 1, N = 011?????????????b
after N |= N >> 2, N = 01111???????????b
after N |= N >> 4, N = 011111111???????b
after N |= N >> 8, N = 0111111111111111b
after (N + 1) >> 1,N = 0100000000000000b
```
:::warning
你可用漢語或英語書寫共筆，但全頁面應該用單一語文
:notes: jserv
:::
for every `0 < N < 2^16` the function will return the correct answer.
if `N = 0`, we will get 1. Actually, there is no any power-of-2 that is smaller or equal to `0`.
if `2^15 <= N < (2^16)-1`, the return value should be `0`, because after line `N |= N >> 8` N = `1111111111111111b`, N+1 = `0000000000000000b`, `(N + 1) >> 1` = `0000000000000000b`, because it will overflow the result should be 0.
But on my computer `Ubuntu 20.04` running on `Parallels VM` on `macOS Catalina` on a `intel 64bit` processer, it return right answer `100000000000000b`.
```cpp=
uint16_t func(uint16_t N)
{
N = N | N >> 1;
N = N | N >> 2;
N = N | N >> 4;
N = N | N >> 8;
return (N+1) >> 1;
}
int main(){
unsigned int u32 = 0xffffffff;
printf("sizeof uint: %ld\n",sizeof(unsigned int));
printf("u32=0x%x u32+1=0x%x\n",u32,u32+1);
uint16_t u16 = 0xffff;
printf("sizeof u_int16: %ld\n",sizeof(u_int16_t));
printf("u16=0x%x u16+1=0x%x\n",u16,u16+1);
printf("intput:0x%x\n",(uint16_t) pow(2,15)+1);
printf("pow-of-2 = 0x%x\n",func((uint16_t) pow(2,15)+1));
return 0;
}
```
```shell
sizeof uint: 4
u32=0xffffffff u32+1=0x0
sizeof u_int16: 2
u16=0xffff u16+1=0x10000
intput:0x8001
pow-of-2 = 0x8000
```
考慮到可能是因為 N+1 的時候 1 被視為 int 讓 N+1 轉型成 int ，因此設計以下實驗，可以發現如果印出暫時數值的時候超出 16bit ，相加後給予實際變數之後卻會溢出。
```cpp=
uint16_t u16 = 0xffff;
uint16_t tmp = 0x0001;
uint16_t result = u16 + tmp;
printf("sizeof u_int16: %ld\n",sizeof(u_int16_t));
printf("u16=0x%x u16+1=0x%x result=0x%x\n",u16,u16+tmp, result);
```
```shell
sizeof u_int16: 2
u16=0xffff u16+1=0x10000 result=0x0
```
---
## 測驗 `3`
### 解釋程式碼運作原理
```cpp=
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) /* Numbers of bit to copy */
{
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.
mask |= write_mask[write_lhs + bitsize];
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
}
```
`read_lhs` 在一個 byte 中有幾個左邊的 bit 不要被複製
`read_rhs` 在一個 byte 中有幾個右邊的 bit 要被複製
`source` 指向第一個需要被複製的 byte
`write_lhs` 在一個 byte 中有幾個左邊的 bit 不要被覆蓋
`write_rhs` 在一個 byte 中有幾個右邊的 bit 要被覆蓋
`dest` 指向第一個需要被覆蓋的 byte
```cpp=7
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);
```
`data` 要複製的 bits
`bitsize` 本次要複製的 bits count ，如果大於 8 則複製 8 個
```cpp=39
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
/*讓 data 的最左邊是要複製的 bits*/
data <<= read_lhs;
/* 如果成立，代表要被複製的數量大於現在在 data 裡的數量
* 因此要把下一個位置的 bits 也放到 data 中*/
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
/*不需要的位置設為0*/
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 */
/* (original & mask)把要被覆蓋的位子設為0
* (data >> write_lhs)對齊位置 */
*dest++ = (original & mask) | (data >> write_lhs);
/* original 左邊要被覆蓋的位置設為0*/
original = *dest & write_mask[bitsize - write_rhs];
/* 把 data 右邊還沒複製的 bits 複製上去*/
*dest = original | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
/* 因為bitsize <= write_rhs
* 且 write_lhs + write_rhs = 8
* 因此 write_lhs + bitsize <= 8
* mask 把左邊與右邊不需要覆蓋的範圍設為1*/
mask |= write_mask[write_lhs + bitsize];
/* (original & mask)把需要被覆蓋的位置設為0
* (data >> write_lhs)對齊位置*/
*dest++ = (original & mask) | (data >> write_lhs);
}
```
---
## 測驗 `4`
### 解釋程式碼運作原理
Sign in with Wallet
Connect another wallet