# 2022q1 Homework2 (quiz2)
contributed by < `Korin777` >
## 測驗一
### 延伸問題一
考慮以下對二個無號整數取平均值的程式碼:
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
```
這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
* 先將大數中的 `low` 提出後 , 在對兩數差取平均
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (a & b & 1);
}
```
* `(a >> 1) + (b >> 1)` 相當於 `2/a + 2/b` ， 當兩數皆為奇數時多出來的餘數會使得 `a/2 + b/2`比`(a+b)/2`少1
* 因此我們要判斷兩數是否皆為奇數 , 透過檢查最低位元是否為1(即`&1`)來達成
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
* `a & b`會找出2進位表示中 , 兩數皆為1的位元
* `a ^ b`會找出2進位表示中 , 只有一數為1的位元
* 而後者因為來源只有一數 , 所以要在除以2
### 延伸問題二
透過 `objdump -d` 來查看對應的組合語言輸出
1. (a + b) / 2
```c
lea (%rdi,%rsi,1),%eax
shr %eax
retq
```
* `rdi` : 儲存函式第一個 argument ,`rsi` : 儲存函式第二個 argument
* `eax` : return value ,為 `rax` 的 Low 32-bits
* `(%rdi,%rsi,1)` : `rdi` 裡的值與 1 倍的 `rsi` 裡的值的和 => a + b
* `lea (%rdi,%rsi,1),%eax` : 複製 `(%rdi,%rsi,1)` 的值到 `%eax` => %eax = a + b
* `shr %eax` : 將 `%eax` 裡的值右移一位 => %eax = (a + b) / 2
* `retq` : 結束 callee, 回到 caller 原本執行的地方
2. low + (high - low) / 2
```c
mov %esi,%eax
sub %edi,%eax
shr %eax
add %edi,%eax
retq
```
* `edi` : 儲存函式第一個 argument ,`esi` : 儲存函式第二個 argument
* `rdi` 佔 64 bits,而 `edi` 則是 `rdi` 的 Low 32-bits
* `mov %esi,%eax` : 將 `%esi` 裡的值複製到 `%eax` => %eax = low
* `sub %edi,%eax` : 將 `%eax` 裡的值與 `%edi` 裡的值差存在 `%eax` => %eax = low - high
* `shr %eax` : %eax = (low - high) / 2
* `add %edi,%eax` : 將 `%eax` 裡的值與 `%edi` 裡的值和存在 `%eax` => %eax = low + (low - high) / 2
3. (a >> 1) + (b >> 1) + (a & b & 1)
```
mov %esi,%edx
shr %esi
and $0x1,%edx
and %edi,%edx
shr %edi
add %edx,%edi
lea (%rdi,%rsi,1),%eax
retq
```
* `%edx` : 儲存函式第三個 argument,因為函式只有兩個參數,這裡應該是用來暫存計算中的值
* `mov %esi,%edx` : %edx = a
* `shr %esi` : %esi = a >> 1
* `and $0x1,%edx` : 將常數 `0x1` 與 `%edx` 裡的值做 & 運算並存在 `%edx` => %edx = a & 1
* `and %edi,%edx` : %edx = a & 1 & b
* `shr %edi` : %edi = b >> 1
* `add %edx,%edi` : %edi = (b >> 1) + (a & b & 1)
* `lea (%rdi,%rsi,1),%eax` : %eax = (a >> 1) + (b >> 1) + (a & b & 1)
4. (a & b) + ((a ^ b) >> 1)
```c
mov %edi,%eax
and %esi,%edi
xor %esi,%eax
shr %eax
lea (%rax,%rdi,1),%eax
retq
```
* `mov %edi,%eax` : %eax = a
* `and %esi,%edi` : %edi = a & b
* `xor %esi,%eax` : %eax = a ^ b
* `shr %eax` : %eax = (a ^ b) >> 1
* `lea (%rax,%rdi,1),%eax` : %eax = (a & b) + ((a ^ b) >> 1)
參考資料
* [Guide to x86-64](https://web.stanford.edu/class/archive/cs/cs107/cs107.1166/guide_x86-64.html)
* [CS107, Lecture 11
Assembly: Arithmetic and Logic](https://web.stanford.edu/class/archive/cs/cs107/cs107.1222/lectures/11/Lecture11.pdf)
## 測驗二
### 延伸問題一
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
* 當 b > a
1. a ^ ((a ^ b) & 0xffff) => x & 1 = x
2. a ^ (a ^ b) => xor associative
3. (a ^ a) ^ b => x ^ x = 0
4. 0 ^ b => 0 ^ x = x
5. b
* 當 a >= b
1. a ^ ((a ^ b) & 0) => x & 0 = 0
2. a ^ 0 => x ^ 0 = x
3. a
### 延伸問題二
參考上面 32 位元無號整數實作，撰寫針對 32 位元有號並同樣 branchless 的實作
```c
int32_t max(int32_t a, int32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
* 可以從上面的推導得知,整數有號或無號並不會影響上面的各個運算結果,因此只須將參數及回傳值型態改為 `int32_t`
## 測驗三
### 延伸問題一
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (u | v);
return u << shift;
}
```
1. 當 `u` 為 0 回傳 `v` , 反之回傳 `u` , 兩者皆為 0 回傳 0
2. 當 `u` 和 `v` 皆為偶數 , $\gcd(u,v) = 2 \ast gcd({u \over 2},{v \over 2})$ , `shift` 用來記錄之後要乘回 2 多少次
3. 如果 `u` 還是偶數 , 因為 `v` 是奇數 $\gcd(u,v) = gcd({u \over 2},v)$
4. 透過[輾轉相除法](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)來求出 `u` 和 `v` 的最大公因數 , 在這過程中因為 `u` 一直保持為奇數 , 因此 $\gcd(u,v) = gcd(u,{v \over 2})$
5. 最後要將這個最大公因數乘回 2 的 `shift` 次方
註 :`while(u | v)` 應該改成 `while(v)`,否則會陷入無窮迴圈,因為 `v` 才是過程中會減到 0 的數, 而 `u` 則是最大公因數
### 延伸問題二
透過 `__builtin_ctz` 改寫 GCD
```c
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift, shitf_u = __builtin_ctz(u), shift_v = __builtin_ctz(v);
shift = shitf_u ^ ((shitf_u ^ shift_v) & -(shitf_u > shift_v));
u >>= shitf_u, v >>= shift_v;
do {
shift_v = __builtin_ctz(v);
v >>= shift_v;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
## 測驗四
```c
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
uint64_t bitset = bitmap[k];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
* 上面函式會將 `bitmap` 資料中 , 出現 1 的位置記錄在 `out` , 並回傳 `bitmap` 出現 1 的次數 `pos`
* 假設 bitmap[i] 資料為 3 個 bit
* `bitmapsize` : 2
* `bitmap`: bitmap[0] = 3'b101 , bitmap[1] = 3'b010
* `out` : [0,2,4]
* `pos` : 3
```c
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = bitset & -bitset;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
* 一個數的2補數會將比該數 1 的最低位元還低位的位元都變成 0 => 可知上述位元皆為 0 , 1補數變成 1 , 加一變為2補數上述位元變為 0 , 而 1 的最低位元依舊為 1 ; 高位元則會跟原數相反
* 因此可以得知 `bitset & -bitset` 會保留 `bitset` 中 1 的最低位元 , 而將其他位元變成 0
* 再透過 XOR 就可以把該位消除 , 並保留其他位元
* 相比於原本需要將 `bitmap` 資料都看過一遍 , 這裡每次就只會看位元為 1 的位置
## 測驗五
```c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
struct rem_node {
int key; // 餘數
int index; // 小數循環前有幾個數
struct list_head link;
};
static int find(struct list_head *heads, int size, int key)
{
struct rem_node *node;
int hash = key % size;
list_for_each_entry (node, &heads[hash], link) {
if (key == node->key)
return node->index;
}
return -1;
}
char *fractionToDecimal(int numerator, int denominator)
{
int size = 1024;
char *result = malloc(size);
char *p = result;
if (denominator == 0) {
result[0] = '\0';
return result;
}
if (numerator == 0) {
result[0] = '0';
result[1] = '\0';
return result;
}
/* using long long type make sure there has no integer overflow */
long long n = numerator;
long long d = denominator;
/* deal with negtive cases */
if (n < 0)
n = -n;
if (d < 0)
d = -d;
bool sign = (float) numerator / denominator >= 0; // 答案正負號
if (!sign)
*p++ = '-';
// 整數部分
long long remainder = n % d; // 餘數
long long division = n / d; // 商
sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
if (remainder == 0)
return result;
p = result + strlen(result);
*p++ = '.';
/* Using a map to record all of reminders and their position.
* if the reminder appeared before, which means the repeated loop begin,
*/
char *decimal = malloc(size);
memset(decimal, 0, size);
char *q = decimal;
size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
INIT_LIST_HEAD(&heads[i]);
for (int i = 0; remainder; i++) {
int pos = find(heads, size, remainder);
if (pos >= 0) { // 有循環小數
while (pos-- > 0) // 小數沒循環的部分
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0') // 小數循環的部分
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
return result;
}
struct rem_node *node = malloc(sizeof(*node));
node->key = remainder;
node->index = i;
list_add(&node->link, &heads[remainder % size]);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal); // 沒循環小數
return result;
}
```
* `rem_node->key` 儲存已經出現過的餘數,當在一次遇到同樣的餘數,表示小數循環了
* `rem_node->index` 儲存該餘數前有幾個數,這些數為小數沒循環的部分
註:`sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);` 應可改為 `sprintf(p, "%ld", division);`,因為 `division = n / d` 又 `n`、`d` 皆為正數
## 測驗六
```c
/*
* ALIGNOF - get the alignment of a type
* @t: the type to test
*
* This returns a safe alignment for the given type.
*/
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
```
* Structure Padding : a struct instance will have the alignment of its widest scalar member
* 因為 struct 中 `type t` 最小也只會跟 `char` 一樣佔 1 byte,所以 struct 一定會跟 `type t` 對齊
* 因此先將 struct 地址變更為 0 ,再加上成員 _h 的偏移量就可以知道 `type t` 對齊幾個byte
* pointer 的運算都是遞增或遞移 1 個「單位」, `(char *) - 1` 會減少1 byte,而 `(float *) - 1` 則會減少 4 byte,這也是為什麼要強制轉型成 `(char *)`,因為我們不知道前面是什麼pointer,而當後面不是減 0 時,可能會產生上述的錯誤
* 參考資料
* [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
* [The Lost Art of Structure Packing](http://www.catb.org/esr/structure-packing/#_structure_alignment_and_padding)
* [The (char *) casting in container_of() macro in linux kernel](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel)
## 測驗七
```c
static inline bool is_divisible(uint32_t n, uint64_t M)
{
return n * M <= M - 1;
}
static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;
int main(int argc, char **argv)
{
for (size_t i = 1; i <= 100; i++) {
uint8_t div3 = is_divisible(i, M3);
uint8_t div5 = is_divisible(i, M5);
unsigned int length = (2 << div3) << div5;
char fmt[9];
strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
* 如果單獨為 3 或 5 的倍數字串長度 `length` 為 4 , 同時為 3 及 5 的倍數字串長度為 8,因此可得知 `length = 2 << div3 << div5`
* 不為 3、5、15 的倍數印出數字本身,在字串 index 為 8 的位置,此時 `KK3` 應為 0
* 5 的倍數印出 "Buzz" ,在字串 index 為 4 的位置,即 `8 >> div5`,此時 `KK3` 應為 0
* 3 及 15 的倍數分別印出 "Fizz" 和 "FizzBuzz" ,在字串 index 為 0 的位置,兩者會使 `div3` 為 1,又 3 的倍數會使 `div5` 為 0,可知 `8 >> KK3` 應為 0,因此可知 `KK3 >= 4` 即 `div3 << 2`
註:`strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length);` 中的 9 應改為 8,因 "%u" 開頭在字串 index 為 8 的位置
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz2)
Sign in with Wallet
Connect another wallet