# 2022q1 Homework2 (quiz2)
contributed by < [`Pepitaw`](https://github.com/Pepitaw) >
###### tags: `linux2022`
:::danger
注意書寫規範！
:notes: jserv
已修正
:::

## 測驗 1
### 解釋上述程式碼運作的原理

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

- a + b 可能會有 overflow ，超出 uint32_t 可表示的範圍

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

- 取平均可以視為將較小的加上兩數差取平均

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (a & b & 1);
}

- a 除以 2 ， b 除以 2 相加，再加上補償
- 此補償為判斷 a 與 b 的 lsb 是否皆為 1 ，若是就要加 1 ，反之則加 0
- 解答為 a & b & 1

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

- a & b 為 a 跟 b 相加完會進位的，再加上進位後再右移（除以二）bit 不需要再改變位置
- a ^ b 要將不會進位的 bit 做補償，因此還要再右移（除以二）
### 組合語言輸出與解讀

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (a & b & 1);
}

:::spoiler 用 godbolt 觀察的非編譯器最佳化

push    rbp
mov     rbp, rsp
mov     DWORD PTR [rbp-4], edi  
mov     DWORD PTR [rbp-8], esi
mov     eax, DWORD PTR [rbp-4]
shr     eax
mov     edx, eax
mov     eax, DWORD PTR [rbp-8]
shr     eax
add     edx, eax
mov     eax, DWORD PTR [rbp-4]
and     eax, DWORD PTR [rbp-8]
and     eax, 1
add     eax, edx
pop     rbp
ret

逐行翻
- 將 register rbp 放到 stack
- 將 rsp assign 給 rbp
- 將 edi 放入 rbp pointer 裡，記憶體位置是 rbp - 4
- 將 esi 放入 rbp pointer 裡，記憶體位置是 rbp - 8
- 將 rbp - 4 的記憶體位置 assign 給 eax
- 將 eax 右移一個 bit
- 將 eax assign 給 edx
- 將 rbp - 8 的記憶體位置 assign 給 eax
- 將 eax 右移一個 bit
- eax 與 edx 相加存入 edx
- 將記憶體位置是 rbp - 4 、記憶體位置是 rbp - 8 與 1 做 and 存入 eax
- 將右移好的 edx 與 做完 and 的 eax 相加
- 將 register rbp 移出 stack
- 返回

- 將記憶體位置 rbp - 4 的 register 做右移
- 再將記憶體位置 rbp - 8 的 register 做右移，並相加存入 edx
- 將 rbp - 4 、 rbp - 8 的 register 與 1 做 and 存入 eax
- 最後 eax 與 edx 相加
:::
用 `gcc -S -O3 *.c` 達到編譯器最佳化

movl    %edi, %eax
movl    %esi, %edx
andl    %esi, %edi
shrl    %eax
shrl    %edx
andl    $1, %edi
addl    %edx, %eax
addl    %edi, %eax
ret

- 將 edi 與 esi 做 and 存入 edi
- 再將 edx 與 esx 分別做右移
- edi 與 1 做 and
- 最後將 edx, eax, edi 相加

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

movl    %edi, %eax
andl    %esi, %edi
xorl    %esi, %eax
shrl    %eax
addl    %edi, %eax
ret

- 將 edi 與 esi 做 and 存入 edi
- 將 esi 與 eax 做 xor 再做右移
- 再全部加起來
#### 差異
- 此兩種寫法，後者用到的 operator 較少，所需的動作較少
- 另外後者用 mov 的次數也較少，不會像前者需要足夠的 register 做運算而需要將值 mov 到其他 register 暫放

---

## 測驗 2
### 解釋上述程式碼運作的原理

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

- 若 a 小於 b 就是 a ^ a ^ b ，即為 0 ^ b ， b 為最大值
- 反之則 a ^ 0 ， a 即為最大值
### 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
#### a, b皆為有號數

#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

#### 其一為有號，另一為無號

int32_t max(int32_t a, uint32_t b)
{
    return a ^ ((a ^ b) & (-(a < b) | (a >> 31)));
}

- 因為有號數與無號數做比較運算子，會將有號數轉成無號數
- 多加 a >> 31 當判斷，若 a 為負則 a >> 31 為 0xFFFF ，結果是 a ^ a ^ b ，輸出 b
- 反之則 a >> 31 為 0x0000 ，用 -(a < b) 來決定輸出 a 或 b

---

## 測驗 3
### 解釋上述程式運作原理

#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 (v);
    return u << shift;
}

- 此為輾轉相除法的延伸，利用不斷互減仍是最大公因數之倍數的方式，一次次貼近最大公因數
- 看 u 和 v 是否為 0
- 連續除以二，直到其中一數不是二的倍數為止，並用 shift 做公因數中有幾個 2 的紀錄
- 為了減少兩數的大小，分別對兩數做連續除以二
- 接著就是一直用兩數之差與較小的數連續相減，一路比兩數相等，也就是 u - v = 0 (兩數之差會放在 v )
- 最後回傳公因數 u 乘上 shift 所記錄的幾個公因數 2
### 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升

#include <stdint.h>
#define min(a,b) ((a) < (b) ? (a) : (b))
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v)
        return u | v;
    int a = __builtin_ctz(u);
    int shift = min(a, __builtin_ctz(v));
    u >>= a;
    do {
        v >>= __builtin_ctz(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

---
## 測驗 4
### 解釋上述程式運作原理與舉出運用的案例

#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;
}

- 把 bitmap 中的每一個位元存到 out 裡面，最後回傳 bitmap 中所存的 bit 總數
---
## 測驗 5
### 解釋上述程式運作原理，指出其中不足，並予以改進

#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;
}

從 find 看起，
- 用 key % size 對應要儲存 hash 的位置
- 若從 hash 中找到一樣的值就代表小數循環，回傳儲存在 hash 的位置
- 反之則回傳 -1

從 fractionToDecimal 看起，
- 若 denominator 或 numerator 為 0 ，就分別回傳空字串與 0
- 將 denominator 與 numerator 轉成正整數，存取 sign 到 result
- 利用 sprint 將 long 轉 char ，若商為正，將除數放入 result
- 若整除就回傳 result
- 將 p 指向 result 的字尾，加入小數點
- 宣告與配置記憶體給 decimal ，並初始化值為 0
- 宣告並初始化 1333 個 linked list
- 利用 find 確認是否有循環小數
- 若 pos 是正數或 0 就找到答案
- 反之，利用 list_add 加入新的 node 在 remainder % size ，其值為餘數
- 利用餘數乘十除以除數，將商儲存在 decimal ，並找下一輪餘數

指出其中不足
- 當值要放入的記憶體位置大於 1024 所 malloc 的記憶體時，要重新 realloc p ，要不然就會有隨機 assign 的記憶體位置給 p 形成 memory leak
- 配置記憶體時是用 size 配置，可能會有 buffer overflow 與沒使用到的記憶體浪費。可以紀錄當前能使用的空間，若需要更大空間再 realloc 就好
- 由於前面的判斷，商部會出現 0 或負值，可直接改為下行

sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
sprintf(p, "%ld", (long) division);

- 若輸入為無限小數時，此程式會陷入無限迴圈

for (int i = 0; remainder; i++) //遇到無限小數時， remainder 部會為 0

---
## 測驗 6
### 解釋上述程式運作原理

#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)

((struct { char c; t _h; } *)0)
//定義一個指向記憶體位置 0 的 struct ， size 是 8
(&((struct { char c; t _h; } *)0)->_h)
//指向 _h 所在的記憶體位置，代表也就是 t 資料型別所在的記憶體位置

- 指向 t 所代表的記憶體位置，再扣掉一開始 alignment 的位置 0 ，即為 t 資料型別所 align 的記憶體位置

#include <stdio.h>
#define ALIGNOF(t) \
        (&((struct { char c[5];} *)0)->c[t])
int main()
{    //註解為 output
        printf("%d\n", ALIGNOF(0));    // 0
        printf("%d\n", ALIGNOF(1));    // 1
        printf("%d\n", ALIGNOF(2));    // 2
        printf("%d\n", ALIGNOF(3));    // 3
        printf("%d\n", ALIGNOF(4));    // 4
        printf("%d\n", sizeof(ALIGNOF(0)));    // 8
}

- 看到每個 char[i] 所 alignment 的記憶體位置

#include <stdio.h>
#define ALIGNOF(t) \
    ((int *)(&((struct { char c; t _h; } *)5)->_h))
int main()
{
        printf("%d\n", ALIGNOF(int));    // 9
        printf("%d\n", (char *)5);    // 5
}

- 可知 5 就是 struct 所對齊的記憶體位置
---
## 測驗 7
### 解釋上述程式運作原理

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;
}

從 is_divisible 看
$n/d = n * (2^N/d) / (2^N)$ ... $n - (n/d) * d$
從餘數推導
$n - (n/d) * d = n - n * (2^N/d) / (2^N) * d$
$= n - n * 2^N / 2^N$
- 當 $n * 2^N$ 比 $2^N$ 大時，可知有餘數

n * M <= M - 1

:::warning
問題：
為什麼不像下行這樣寫就好？

n * M < M

:::
從 main 來看
- M3 與 M5 分別為在 64 位元下能被 3 與被 5 整除的最大無號整數數量
- div3 與 div5 表示 i 是否能被 3 或被 5 整除
- 藉由 FizzBuzz 為 8 個 char 的特性，若可被任一整除，就左移 length ，使 strncpy 拿的字串長度為 2 (%u) 、 4 (Fizz or Buzz) 或 8 (FizzBuzz)

以這行來討論 [(9 >> div5) >> (div3 << 2)]

- 只要 div3 = 1 ，運算完要是 0
- 只有 div5 = 1 ，運算完要是 4
- 都為 0 ，運算完要是 8
:::danger
該題目有誤：

strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length);

9 應改成 8

strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)], length);

:::