2022q1 Homework3 (quiz3)

contributed by < AmyLin0210 >

2022q1 第 3 週測驗題

測驗 1

解釋程式碼運作原理

#define GENMASK(h, l) \
    (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))

首先我們看到 (~0UL) >> (63 - h) 的部份，這裡代表將左側非一的位置清零，
在後面 (~0UL) >> (l) << (l) 則是將右側非一的位置清零，
兩者再做 and 的操作，便可以只留下中間需要為 1 的數字。

下方我以 8 bit 作為示意圖

GENMASK(6, 4) 01110000
11111111 >> (7 - 6)     --> 01111111
11111111 >> (4) << (4)  --> 11110000
------------------------------------
01111111 & 11110000 --> 01110000

測驗 2

解釋程式碼運作原理

















struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){(struct foo *)(v & ~3), v & 3};
}

由題目敘述可以得知，我們想要針對 foo 這個指標以四個位元組為單位，進行向下對齊。
在一般的想法上，就是直接將該位置除以四，但由於 4 是二的倍數，所以我們可以使用 binary operation 來達成，答案是 (struct foo *)(v & ~3)

測驗 3

解釋程式碼運作原理

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
    x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
    return x;
}

以下是整個流程的示意圖：
每 4 個 bits 為一組，做 reverse

x = (x >> 4) | (x << 4)
1 2 3 4 | 5 6 7 8  ->  5 6 7 8 | 1 2 3 4

再來由於 0xCC 為 1100 1100 若有一個數字與它做 and 操作，並往右位移兩位，那便會有共 4 個位元，以兩個位元為一組，向右位移兩位。
類似的，由於 0x33 為 0011 0011 ，若有數字與它做 and 操作，並往左位移兩位，那便會有共 4 個位元，以兩個位元為一組，向左位移兩位。

x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2)

5 6 | 7 8 | 1 2 | 3 4  ->  7 8 | 5 6 | 3 4 | 1 2

最後兩個兩個位元一組左右互換

x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1)

7 | 8 | 5 | 6 | 3 | 5 | 1 | 2  ->  8 | 7 | 6 | 5 | 4 | 3 | 2 | 1

測驗 4

首先，我們先來看 __VA_ARGS__ 到底是什麼。

在 Variadic Macros 這份文件中，有解釋到他是一個可以被宣告為可變參數的 macro，以下方的程式碼為例











#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i])

int main () {
    int i;
    foreach_int(i, 0, -1, 100, 0, -99) {
        printf("i is %i\n", i);
    }
}

第 8 行的地方使用了上方定義的 foreach_int 巨集 (macro)，__VA_ARGS__ 將會是該巨集第二個之後的參數們，若是將它展開，會等同於下方的程式碼：





for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); \
     _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int);      \
     (i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]) {
     printf("i is %i\n", i);
}

一步一步的拆解上方程式碼，首先是 (int[]){0, -1, 100, 0, -99}) ，這代表了一個陣列，裡面的元素分別為 0, -1, 100, 0, -99 。
((i) = ((int[]){0, -1, 100, 0, -99})[0]) 表示將該陣列第 0 個元素的值賦值給 i
最後有運用到 comma operator，也就是假設現在有以下的程式碼：int i = (exp1, exp2) ，程式執行時會先執行 exp1 再值執行 exp2 ，並回傳出 exp2 的結果給 i。在上面的程式碼，則代表把 0 這個數字賦值給 _foreach_i。
在這個 for 迴圈的中止條件是 _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int);，所以推測 _foreach_i 儲存的資訊是已經遍歷到陣列的哪個位置
最後看到 (i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]) ，表示要把 i 更新為新的陣列內位置的值，++_foreach_i 是先加一再回傳，因此可以拿到原陣列位置加一後的資料。

在 foreach_ptr 裡面的邏輯大致與 foreach_int 類似，同樣套用範例將它展開：











#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

const char *p;
for (unsigned _foreach_i =                                              \
         (((i) = (void *) ((typeof(i)[]){"Hello", "world"})[0]), 0); \
     (i); (i) = (void *) ((typeof(i)[]){"Hello", "world",            \
                                                NULL})[++_foreach_i],   \
              _foreach_no_nullval(_foreach_i, i,                        \
                                  ((const void *[]){"Hello", "world"})))

我們可以看到在上面第 9 行的程式碼部份，在陣列的最後一個位置塞入 NULL 表示結束。

來看看 _foreach_no_nullval 這個巨集內是如何判斷該陣列正確。

在裡面的 (i) >= sizeof(arr) / sizeof(arr[0]) ，由於 || 的特性，當 (exp1 || exp2) 時，只有在 exp1 為 false 的狀況下，才會去執行 exp2
在這裡的話，sizeof(arr) / sizeof(arr[0]) 算出的數字為該陣列內有幾個元素，當 i 還小於等於那個元素，我就去檢查 p 是否為 NULL ，若 p 為 NULL ，assert 內的判斷式為 false ，表示我會在 stderr 內輸出錯誤訊息並結束程式。

測驗 5
































#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        dvd -= dvs << shift;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

同樣一行行的來看程式碼，

第 4 到第 15 行，做的事情都是去判斷 dividend 和 divisor 是否為負數，若是負數，則利用二補數的特性，將它轉為正數，並且在 signal 這個參數儲存他是正數或者負數的資訊。
在第 17 到 20 行，由於在二進制的 shift 等同於乘以二的冪次，所以就是找到 dvd 大於 dvs 的多少二的冪次。
第 22 到第 27 行，在 dvd 仍大於 dvs 的狀況下，相減他們，並使用 res 來記住已經減了多少，一次就是減 dvs 乘以二的冪次，使用 shift 來紀錄是要 shift 多少位。

測驗 6











































































































#include <stdbool.h>
#include "list.h"

struct Point {
    int x, y;
};

struct point_node {
    int p1, p2;
    struct list_head link;
};

static bool can_insert(struct list_head *head, int p1, int p2)
{
    struct point_node *pn;
    list_for_each_entry (pn, head, link)
        return p1 == pn->p1;
    return true;
}

static int gcd(int x, int y)
{
    while (y) {
        int tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

static int maxPoints(struct Point *points, int pointsSize)
{
    if (pointsSize <= 2)
        return pointsSize;

    int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
    int *dup_cnts = malloc(pointsSize * sizeof(int));
    int *hori_cnts = malloc(pointsSize * sizeof(int));
    int *vert_cnts = malloc(pointsSize * sizeof(int));
    int *slope_cnts = malloc(slope_size * sizeof(int));
    memset(hori_cnts, 0, pointsSize * sizeof(int));
    memset(vert_cnts, 0, pointsSize * sizeof(int));
    memset(slope_cnts, 0, slope_size * sizeof(int));

    for (i = 0; i < pointsSize; i++)
        dup_cnts[i] = 1;

    struct list_head *heads = malloc(slope_size * sizeof(*heads));
    for (i = 0; i < slope_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (i = 0; i < pointsSize; i++) {
        for (j = i + 1; j < pointsSize; j++) {
            if (points[i].x == points[j].x)
                hori_cnts[i]++, hori_cnts[j]++;

            if (points[i].y == points[j].y)
                vert_cnts[i]++, vert_cnts[j]++;

            if (points[i].x == points[j].x && points[i].y == points[j].y)
                dup_cnts[i]++, dup_cnts[j]++;

            if (points[i].x != points[j].x && points[i].y != points[j].y) {
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int tmp = gcd(dx, dy);
                dx /= tmp;
                dy /= tmp;
                int hash = dx * dy - 1333 * (dx + dy);
                if (hash < 0)
                    hash = -hash;
                hash %= slope_size;
                if (can_insert(&heads[hash], i, j)) {
                    struct point_node *pn = malloc(sizeof(*pn));
                    pn->p1 = i;
                    pn->p2 = j;
                    list_add(&pn->link, &heads[hash]);
                }
            }
        }
    }

    for (i = 0; i < slope_size; i++) {
        int index = -1;
        struct point_node *pn;
        list_for_each_entry (pn, &heads[i], link) {
            index = pn->p1;
            slope_cnts[i]++;
        }
        if (index >= 0)
            slope_cnts[i] += dup_cnts[index];
    }

    int max_num = 0;
    for (i = 0; i < pointsSize; i++) {
        if (hori_cnts[i] + 1 > max_num)
            max_num = hori_cnts[i] + 1;
        if (vert_cnts[i] + 1 > max_num)
            max_num = vert_cnts[i] + 1;
    }
    for (i = 0; i < slope_size; i++) {
        if (slope_cnts[i] > max_num)
            max_num = slope_cnts[i];
    }

    return max_num;
}

在這份程式碼裡的想法是去分別計算對於一個點來說，與他處在相同 x 軸、y 軸、擁有相同斜率的點有哪些。

在第 63 到 79 行的地方，做的事情就是去找到相同斜率的點。
由於在電腦中，儲存浮點數很容易會有精度上的的問題，所以選擇算出兩點之間 x 軸與 y 軸之間的距離，再去找到他們的最大公因數，除以最大公因數後，以此紀錄他們的斜率。
在第 73 行呼叫了 can_insert，這個函式的內容定義在第 13 行，可以看到當中的做的事情是，只去記錄相同斜率狀況下，從同一個點出發的次數以避免重複呼叫。這個想法很類似於數學上的點斜式，也就是給定一個點，給定一個向量，就可以求出一個直線。
但是在目前的程式碼中，我發現可能會出現一個狀況，就是有機會非共線但相同斜率的狀態下，有些點會被捨棄掉。因此應該要重新設計演算法，將從哪些位置出發也列入考量。

測驗 7


















int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = (v > 0x3U) << 1;
    v >>= m;
    ret |= m;
    ret |= v > 0x1U;
    return ret;
}

在這裡，基本上是去找到最高位元是哪一個，以上的實作方式的優點是當中沒有 branch，若直觀的使用 for 迴圈去找出最高的位元在哪裡的話，就無可避免地會有 branch 的發生。

第 4 行的地方，去看有沒有超過
$2^{2^{4}}$ ，如果有就把結果儲存到 ret 裡，並向右 shift 相對應的位元。
第 10 行的地方，同上面的步驟，看看有沒有超過
$2^{2^{3}}$ 。
第 13 與第 16 行皆是相同的邏輯。

測驗 8

在本測驗裡，主要是要將程式碼使用指標的指標來簡化。



























void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            p = &(*p)->left;
        else
            p = &(*p)->right;
    }
    tnode *q = *p;
    if (!q)
        return;

    if (!q->left)
        *p = q->right;
    else if (!q->right)
        *p = q->left;
    else {
        tnode **r = &q->right;
        while ((*r)->left)
            r = &(*r)->left;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

程式碼的第 4 到第 8 行的部分，是找到想要移除的結點在哪裡，若想移除的節點值較目前節點的小往左走，反之往右走。

在第 14 行，若找到的節點左邊已經沒有節點了，那直接將右邊的整個結構往上挪

假設我現在想要移除的 data 是 10 ，那我只需要把該節點替換為該節點的 right 即可

      13                 13
    /    \              /  \
 10      15           11    15
   \           -->     \
   11                   12
     \
      12

在 16 行做的事情與上述的相似，差別只在於若現在是右邊沒有節點了，那我直接把左邊的結構網上挪。

第 18 到第 25 行處理的狀況為，若左右都有節點，那我先找到該節點右邊子樹中最小的 (也就是子樹中最左邊的 leaf)，將他的值替換至想要被取代的節點。
第 24 行做的事情就是將該子樹最左邊的 leaf 的右子樹往上挪，以下圖範例來看，就是將 16 挪至原本 15 的位置

假設我們現在想要取代的的數字是 13

      13                 15
    /    \              /  \
 10      18           10    18
        /      -->         /
       15                 16 
         \                  \
          16                 17
            \
             17

測驗 9

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - MMM) & ~(NNN))

首先我們可以看到以上的程式碼，和測驗 2 有些相似之處。
首先看到 NNN 的部分，因為我們會希望可以對齊 16，所以會想要把最後面的 4 個位元做 mask 處理掉，因此在這邊會是 MAX_ALIGNMENT - 1 ，也就等同於 0xFU。
再來是 MMM 的部分。在題目裡，會希望可以做到向上對齊，但是如果直接將最後的四個位元給歸零，做的事情是向下對齊。因此我們可以將他們加上一個數字，向上位移至上一個位元組，再向下對齊。
在這裡的 MMM 是 1 ，我們討論一下邊界的狀況，當原先的位置最後 4 個位元就是 0 時，對齊結果應該要是和原先相同的。在這裡要將 x 加上 MAX_ALIGNMENT 後再扣掉一就是考量這個原因。

測驗 10

#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

在這裡我參考了 NOVBobLee 同學的筆記，當中有對於在不同型態下，進行除法運算時的不同結果。

除了在不同型態下的除法運算邏輯外，主要應用到的邏輯與測驗 9 的向上位移相似，所以 RRR 是 __x + ((__d) >> 1)
而 SSS 處理的為 x 是負數的狀況，因此是加減正好顛倒， __x - ((__d) >> 1)

2022q1 Homework3 (quiz3)

測驗 1

解釋程式碼運作原理

測驗 2

解釋程式碼運作原理

測驗 3

解釋程式碼運作原理

測驗 4

測驗 5

測驗 6

測驗 7

測驗 8

測驗 9

測驗 10

測驗 11

Read more

Lockless Multithreaded Logger 實作

2022q1 Homework2 (quiz2)

2022q1 Homework1 (lab0)

2022q1 Homework1 (quiz1)