# 2021q1 Homework2 (quiz2)
contributed by < `mingyen066` >
:::danger
注意共筆書寫規範：中英文間用一個半形空白區隔！
:notes: jserv
:::
# 測驗一
# 測驗二
## 程式說明
```c=
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
return (N + 1) >> 1;
}
```
:::danger
「把最高位元 `1` 右邊的數字也通通填上 `1`」用語不精確，你需要定義左邊和右邊何者是高位元 (MSB)
:notes: jserv
:::
根據註解我們可知，剛開始四行程式碼的目的是為了把最高位元 `1` 右邊的數字也通通填上 `1`，一開始執行`N |= N >> 1;`，我們可以知道 N 的最高位元1以及右邊 1 位都會變成 1，也就是從最高位元往右數會有兩個連續1，接下再利用這兩個連續1把右邊兩位也變成 1，變成連續 4 個 1，也就是
`N |= N >> 2;` 的操作，以此類推，就算 1 在 MSB，我們也可以把寬度16位元的 unsigned int 都變成 1。
## 考慮LSB為1的情形
假設當我們使用輸入65535 = 0xFFFF 的輸入時，以第一直覺的想法是在程式最後一行`return (N + 1) >> 1;` 中的 `(N + 1)`，N 是 unsigned，1 是 integer constant，
unsinged integer 遇到 signed integer 會把signed integer promote 成 unsigned integer 做運算，如此一來結果會變成 [1]0000 0000 0000 0000，因為 overflow 會捨棄進位的 1，所以（N + 1）的結果會是 0，0做算數右移的結果還是0，結果出錯。
但是實際輸入65535，程式結果卻是32768，是正確答案。
所以這時產生的想法是有可能是 unsigned 是16 bit 所以 conversion 的規則不一樣。
根據C11規格書:
> 6.3.1.8 Usual arithmetic conversions
> ...
>> Otherwise, the integer promotions are performed on both operands. Then the
following rules are applied to the promoted operands:
...
>>>Otherwise, if the type of the operand with signed integer type can represent
all of the values of the type of the operand with unsigned integer type, then
the operand with unsigned integer type is converted to the type of the
operand with signed integer type.
意思是說：如果 signed integer type 可以表達 unsigned integer type 的所有數值，那麼 unsigned integer 會被轉換成 signed integer type
:::warning
在實驗過程中遇到一個疑問，當我想測試 conversion 的結果時，運用下列程式，把兩個 operand 都 cast 成 uint16_t：
```c
int main(void)
{
uint16_t x = (uint16_t)0xFFFF + (uint16_t)1;
printf("%u\n", x);
}
```
這時編譯器會產生警告
```shell
warning: unsigned conversion from ‘int’ to ‘uint16_t’ {aka ‘short unsigned int’} changes value from ‘65536’ to ‘0’ [-Woverflow]
3 | uint16_t x = (uint16_t)0xFFFF + (uint16_t)1;
```
但是採用下列表示時，卻又不會產生警告
```c
int main(void)
{
uint16_t x = (uint16_t)(0xFFFF + 1);
printf("%u\n", x);
}
```
> 注意 C 語言規格書描述!
> :notes: jserv
:::
# 測驗 3
```c=
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);
```
```
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
```
因為資料型態是 uint8 ，所以先把資料分成8位元一個區塊的方式可以方便指標做加減的操作
其中 `_read & 7` 題目中有提到相當於 `_read % 8` ，目的是為了計算每8位元一組之後，還會多出幾個 bit ，lhs 代表 left hand side ，rhs 則代表 right hand side
```
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
```
接著我們把 source 指向要讀取的區塊開頭(8位元一組)，因為把 _src 轉型成指向 uint8_t 的指標，所以一次加1就會位移8位元，同理，也對 write 做一樣的操作
```c=
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 */
};
```
上述 mask 程式碼用來方便對位元做操作，對 mask 做 & 操作代表我們要保留左邊或右邊幾位位元，
舉例來說：`x = x & read_mask[4]` 代表我們保留左邊4位元，右邊其餘位元設成0，
我們也可以做出保留左右位元的 mask ，舉例來說：`mask = read_mask[3] | write_mask[2]` 代表最左邊三位元為1，最右邊兩位元為1的 mask，也就是`11100011b`
```c=
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
```
我們每次對 source 一位元組做處理，從 source 讀取一位元組資料，並傳給 data，如果剩餘要寫入的資料大於一位元組，則把 bitsize 設成8，即只考慮一位元組的意思，但是我們要的資料有可能橫跨兩個區塊，前幾位元我們不要讀取，而且剩下的資料在 source 的下一個區塊開頭，如下圖所示：
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
bit [label = "{<bad> x|x|x|<good>0|1|0|1|0}"];
bit2 [label = "{1|1|0|x|x|x|x|x}"];
source [shape=circle]
source ->bit:in
bit->bit2[taillabel="next byte"]
// labelloc="t";
// label="data";
databit [xlabel="data" label = "{<bad> x|x|x|<good>0|1|0|1|0}"];
}
```
因為我們有紀錄 `read_lhs` ，假設是上述例子 `read_lhs` 就是 3，透過 `data <<= read_lhs`把 data 往左位移3 bit變成
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="data<<read_lhs";
databit [label = "{0|1|0|1|0|x|x|x}"];
}
```
如果要處理的 bitsize 超過 `read_rhs` ，這例子中是5，則要讀入下個區塊的前 `read_lhs` 位元， 例子中就是3位元，透過` (*source >> read_rhs);` 可以得到下個區塊的前3位元，但是位移到最右邊。
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="(*source >> read_rhs)";
data [label = "{x|x|x|x|x|1|1|0}"];
}
```
因為左移跟右移過後填上的 x 都是0，所以我們可以與 data 做 OR 即可合併橫跨兩個區塊的資料
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="data";
databit [label = "{0|1|0|1|0|1|1|1}"];
}
```
接下來如果 `bitsize` 小於8，我們再用 `data &= read_mask[bitsize];` 保留左邊個數 `bitsize` 的位元
```c=
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);
}
```
`read_mask[write_lhs]` 得到的 mask 用來保留目的地資料前 write_lhs 個位元，因為我們從 write_lhs 個位元之後才開始寫入，如果 `bitsize > write_rhs` 代表我們會寫入兩個區塊，把 original 與 mask 做 AND 來先保留不需寫入的位元，把要待寫入的位元清成0，這裡的 x 代表原始資料。
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="(original & mask)";
databit [label = "{x|x|x|x|x|0|0|0}"];
}
```
接著先寫入 data 的前 `write_rhs` 位元，我們可以利用 data 右移 `write_lhs` 位元，再進行 OR 即可寫入 dest 的尾端，這裡的 x 代表右移產生的0。
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="(data>>write_lhs)";
databit [label = "{x|x|x|x|x|0|1|0}"];
}
```
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="(original & mask) | (data>>write_lhs)";
databit [label = "{x|x|x|x|x|0|1|0}"];
}
```
接著寫入下一個區塊，使用 `write_mask` 來保留右邊 `bitsize - write_rhs` 個原始資料，也就是 `*dest & write_mask[bitsize - write_rhs]` 做的事，
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="*dest & write_mask[bitsize - write_rhs]";
databit [label = "{0|0|0|0|0|x|x|x}"];
}
```
接著把後 write_rhs 個位元位移到最左邊，並寫入資料，這裡的 x 是位移產生的0
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="(data << write_rhs);";
databit [label = "{1|0|1|1|1|x|x|x}"];
}
```
下面的 x 的是目的地的原始資料
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t";
label="original | (data << write_rhs)";
databit [label = "{1|0|1|1|1|x|x|x}"];
}
```
如果 `bitsize <= write_rhs` 代表我們只需要寫入一個區塊，我們使用 write_mask 來結合原本的 mask ，來保留左端及右端的資料，假設 `write_lfs=3，bitsize=3`
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t"
label="mask"
databit [label = "{1|1|1|0|0|0|0|0}"]
}
```
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t"
label="write_mask[write_lfs + bitsize]"
databit [label = "{0|0|0|0|0|0|1|1}"]
}
```
```graphviz
digraph display_1 {
graph [ rankdir = LR]
node [ shape = record ]
labelloc="t"
label="mask | write_mask"
databit [label = "{1|1|1|0|0|0|1|1}"]
}
```
Sign in with Wallet
Connect another wallet