---
tags: linux, kernel
---

# 2022q1 Homework3 (quiz3)
contributed by < `Destiny0504` >

## 測驗一
因為 ```~0UL``` 在 2's complement 的編碼會呈現全部為一的結果，所以我們利用這種特性並利用 ```shift right``` 和 ```shift left``` 兩種方式來製作 mask 保留我們想要的 bits
- ```shift right``` 是用於製作 ```MASK(h, 0)```
- ```shift left``` 是用於製作 ```MASK(0, l)```
- 將兩者合併之後就可以得出我們要的 ```MASK``` 了

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

## 測驗二

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

## 測驗三
利用 ```shift bit``` 與 ```mask``` 並用的方式來達成 reverse 的效果

- 首先，我們先將整個 x 的前四個 bits 與後四個 bits 進行交換。
- 接著將交換好的 x 的前半部份的 bits 分成兩半並進行交換，直到交換的 bits 長度為 1 就結束。
- 為了完成前面想要的交換，我們需要利用 ```mask``` 來去除掉我們不需要的 bits
- e.g. ```0xCC``` 用二進位表示為 ```11001100```，這樣就可以只保留我們要的四個 bits，達成 mask 的作用。

uint8_t rev8(uint8_t x)
{
    // switch the first 4 bits and the last 4 bits in x
    x = (x >> 4) | (x << 4);
    x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
    x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
    return x;
}

- [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/submissions/)
- 因為 leetcode 的題目與我們的實作原理相同，所以就順便作答了一下。

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 16);
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
    return n;
}

## 測驗四

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

#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])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[++_foreach_i],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

## 測驗五

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 > (dvs << shift))
        shift++;

    printf("%d\n", 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;
}

## 測驗六

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

## 測驗七
因為我們需要找出最高位的 bit，所以利用比大小之後的結果來決定 ```shift``` 與否，在將我們所有 ```shift``` 的位數全部加起來就可以得出最後的結果。
- 在我們實作的演算法中，我們先比較 v 是否大於 $2^{16} - 1$ 來判斷我們需不需要 ```shift``` 16位之後在繼續比大小，接著重複以樣的動作，只是要比的數依序從 $2^{8} - 1$、$2^{4} - 1$、$2^{2} - 1$、$1$，再把我們得到的值全部相加就可以知道我們最少需要多少 bit 來儲存這個數了
- 因為我們的電腦屬於二進位的系統，所以這邊全部以 2 的次方減 1 作為比較的基準，這樣可以加快之後相加的運算速度。

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;
    // exp 10
    m = (v > 0x3U) << 1;
    v >>= m;
    ret |= m;
    // exp 11
    ret |= (v > 0x1U);
    return ret;
}

- ```EXP10``` 的答案為 ```m = (v > 0x3) << 1```，而 ```0x3``` 與 ```0x3U``` 的值相同，所以我認為我的實作方式也沒問題。
- ```EXP11``` 的答案為 ```ret += v > 1```，```|= 1 or 0``` 與 ```+= 1 or 0``` 的結果是一樣的，所以我覺得我的實作方式會與答案得出相同的結果。
## 測驗八

typedef struct tnode *tree;                   
struct tnode {
    int data;   
    tnode *left;
    tnode *right;
    tnode(int d)
    {       
        data = d;
        left = right = 0;
    }           
};

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

## 測驗九
將輸入的 x 對齊到```MAX_ALIGNMENT``` * $\lceil \frac{x}{16}\rceil$

- 先將 x 加上 ```MAX_ALIGNMENT - 1``` 來達成無條件進位到 ```MAX_ALIGNMENT``` 的那一位數，再利用 ```MAX_ALIGNMENT - 1u``` 這個 mask 來去除 x 除以 ```MAX_ALIGNMENT``` 的餘數。

/* 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 - 1u) & ~(MAX_ALIGNMENT - 1u))

- 另外一種 alignment 方式
- 對齊到 ```ALIGNMENT``` * $\lfloor \frac{x}{16}\rfloor$

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

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x)) & ~(ALIGNMENT - 1u))

## 測驗十
- 按照題目說明的，```DIVIDE_ROUND_CLOSEST``` 這個 macro 只有在 divisor > 0 時，才是有意義的，所以我們可以分成兩個情況來討論這個問題。
- 第一種情況 x > 0
- 在這個情況下會執行的是 ```(((__x) + ((__d) >> 1)) / (__d))``` 。c 語言的環境中，整數的除法採用的是無條件捨去，所以我們只要將 x 加上 $\frac{divisor}{2}$ ，就可以對原本餘數會大於等於 $\frac{divisor}{2}$ 的情況進位。
- 第二種情況 x <= 0
- 在這個情況下會執行的是 ```(((__x) - ((__d) >> 1)) / (__d))``` ，c 語言的環境中，整數的除法採用的是無條件捨去，所以我們只要將 x 減去 $\frac{divisor}{2}$ ，就會讓計算完的結果為最接近的整數了。

#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)))                         \
            ? (((__x) + ((__d) >> 1)) / (__d))                  \
            : (((__x) - ((__d) >> 1)) / (__d));                 \
    })

## 測驗十一

static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) {
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) {
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))
        num -= 1;
    return num;
} 

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        y >>= 1;

        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }

    return y;
}