Try   HackMD

2022q1 Homework3 (quiz3)

contributed by < StevenChou499 >

測驗 1

在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:

  • GENMASK(6, 4) 產生 01110000
  • GENMASK(39, 21) 產生0x000000FFFFE00000 (64位元)
    已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:
#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

思考與想法

因為是要產一個 bitmask ，所以其中的 & 運算應該是要利用分別只有單邊的 1 做 & 運算後只剩下中間同時為 1 部份。

                0000001111111111
             &  0000001111000000
           -------------------------
                0000001111000000
                      ^  ^
                      同時都擁有1的部份

而 & 的左側為 (~0UL) >> (LEFT) ，若變數為 64 位元，則需要往右側 shift (63 - h) 次，因為變數的最右側位元為第 0 個位元，因此 LEFT 為 63 - h ，而 & 的右側為 (~0UL) >> (l) << (RIGHT) ，便是將 64 個 1 向右 shift 再向左 shift ，以便創造出只有中間有 1 ，兩側皆為 0 的情形。因此 RIGHT 為 l 。

LEFT : 63 - h
RIGHT : l

測驗 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){EXP1, v & 3};
}

函式 fo_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據〈所不知道的 C 語言：記憶體管理、對齊及硬體特性〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 struct foo; 運用〈你所不知道的 C 語言：指標篇〉提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。

思考與想法

由題目可以知道，輸入一地址之後，回傳之 struct foo * 指標必須為 4 的倍數，因此必須將 4 以下之位數都清除，所以 EXP1 之值為 (struct foo *)(v & ~3)。

EXP1 : (struct foo *)(v & ~3)

測驗 3

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. Reverse Bits 的描述。

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

思考與想法

由未完成的程式碼可以知道其實該程式碼是想要透過三次的四四互換、兩兩互換和一一互換達成反轉的結果。

  • 函式中的第一行：
    x = (x >> 4) | (x << 4);

為左邊四位與右邊四位做互換

  • 函式中的第二行：
    x = ((x & 0xCC) >> 2) | (EXP2);

由 0xCC 轉成 binary 為 11001100 可以知道其作用是將為 0 的部份透過 & 的方式轉為 0 ，做 >> 2 則代表原本與 11 & 的位置移動到與 00 & 的位置。所以其實式為了將 11 與 00 的位置互換。因此 EXP2 為剛好反過來，需要 x 與 00110011 做 & 再 << 2 ，這樣剛好可以達成兩兩互換的結果。所以 EXP2 的值為 (x & 0x33) << 2 。

  • 函式中的第三行：
    x = ((x & 0xAA) >> 1) | (EXP3);

由 0xAA 轉成 binary 為 10101010 可以知道其作用是將為 0 的部份透過 & 的方式轉為 0 ，做 >> 1 則代表原本與 1 & 的位置移動到與 0 & 的位置。所以其實式為了將 1 與 0 的位置互換。因此 EXP3 為剛好反過來，需要 x 與 01010101 做 & 再 << 1 ，這樣剛好可以達成兩兩互換的結果。所以 EXP3 的值為 (x & 0x55) << 1 。

以 1~8 舉例：

以下為 1~8 的牌子







INIT



poker_1to8

1

2

3

4

5

6

7

8

先將左右各四份交換

    x = (x >> 4) | (x << 4);







INIT



poker_56781234

5

6

7

8

1

2

3

4



equal
||



poker_5678

5

6

7

8

 

 

 

 



omit
+



poker_1234

 

 

 

 

1

2

3

4

再兩兩交換

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







INIT



poker_56781234

7

8

5

6

3

4

1

2



equal
||



poker_5678

7

8

 

 

3

4

 

 



omit
+



poker_1234

 

 

5

6

 

 

1

2

最後再各自交換

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







INIT



poker_56781234

8

7

6

5

4

3

2

1



equal
||



poker_5678

8

 

6

 

4

 

2

 



omit
+



poker_1234

 

7

 

5

 

3

 

1

完成！

EXP2 : (x & 0x33) << 2
EXP3 : (x & 0x55) << 1

測驗 4

延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:

    int i;
    foreach_int(i, 0, -1, 100, 0, -99) {
        printf("i is %i\n", i);
    }
    const char *p;
    foreach_ptr(p, "Hello", "world") {
        printf("p is %s\n", p);
    }

預期輸出如下:

i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world

對應的巨集定義:

#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})[EXP4])

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

思考與想法

由上述的程式碼可以看出該巨集是循序訪問陣列中的元素，其中 _foreach_i 為 0 ，而在宣告 _foreach_i 的同時也宣告 i 為一代表 int 或是 const char 的陣列。在聚集中可以看到其實內容為一 for 迴圈，而 for 迴圈的最後一個敘述式為若第二個敘述式為真才要執行的結果，又因為 _foreach_i 為代表 i 陣列的元素位置，因此 EXP4 與 EXP5 的值皆為 ++_foreach_i 。

EXP4 : ++_foreach_i
EXP5 : ++_foreach_i

測驗 5

針對 LeetCode 29. Divide Two Integers，以下是可能的實作:

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

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

思考與想法

看到程式碼時可以想到這個程式是想要利用 shift 一一從二進位的高位數進行比較，若大於 dvd 則 shift 減 1 ，直到 dvs << shift 小於 dvd 的第一次則代表 res 在這位式可以紀錄 1 的，因此使用 res |= 1 << shift 的方式將 1 的位置記錄下來，而此時應該要將 dvd 減去 dvs * (1 << shift) ，這樣才可以計算剩下的值對於 dvs 的倍數為何，一直進行下去直到 shift 的值為 1 為止。一開始我將 EXP6 的值輸入 dvs << shift ，而 EXP7的值輸入 dvd -=res * dvs ，發現一直會有錯誤，結果發現我的想法是對的，但是直接將 dvd 的值減去 res * dvs 會導致多次減去高位數的 1 ，導致做 while 判斷式時會發生錯誤，從而進入一無限迴圈。因此 EXP6 的值為 dvs << shift ，而 EXP7的值應為 dvd -= (1 << shift) * dvs 。

簡單來說，程式碼可以算做是二進制的長除法（以 133 除以 7 為例）：

                 res = 16 +  2 +  1 = 19
                     /-------------------
                   7/ 133
                      112
                      -------------------
                       21 ->21
                            14
                      -------------------
                             7 ->7
                                 7
                      -------------------
                                 0

EXP6 : dvs << shift
EXP7 : dvd -= (1 << shift) * dvs

測驗 6

針對 LeetCode 149. Max Points on a Line，以下是可能的實作:

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

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

測驗 7

考慮 ilog32 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:

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 = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}

思考與想法

由原本的程式瑪可以看出，函式的第一行為判斷數字 v 是否為不小於零。皆著判斷 v 是否大於 0xFFFFU ，若大於 0xFFFFU 則為 1 ，並且向右位移 4 次變成 16 ，而 v >>= m 則是向右位移 16 次，最後 ret |= m 便是加上 m 的過程，以此類推，最後便可以算出需要的位數。

由於傳入的數值 v 剛好為 uint32_t ，因此在計算之後透過 | 的動作若為 32 位皆為 1 則剛好可以，因此我們可以知道 EXP10 為 (v > 0x3U) << 1 ，且 EXP11 因為已經剩下最後一位，不需要經過位移，因此其值為 ret |= v > 0x1U 。

EXP10 : (v > 0x3U) << 1
EXP11 : ret |= v > 0x1U

測驗 8

考慮以下 C++ 二元搜尋樹的程式:

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;
    tnode *q;
    while (p != 0 && p->data != d) {
        if (d < p->data) {
            q = p;
            p = p->left;
        } else {
            q = p;
            p = p->right;
        }
    }
    if (p != 0) {
        if (p->left == 0)
            if (p == t)
                t = p->right;
            else if (p == q->left)
                q->left = p->right;
            else
                q->right = p->right;
        else if (p->right == 0)
            if (p == t)
                t = p->left;
            else if (p == q->left)
                q->left = p->left;
            else
                q->right = p->left;
        else {
            tnode *r = p->right;
            while (r->left) {
                q = r;
                r = r->left;
            }
            p->data = r->data;
            if (r == p->right)
                p->right = r->right;
            else
                q->left = r->right;
            p = r;
        }
        delete p;
    }
}

函式 remove_data 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 remove_data 過於冗長，於是我們可善用 indirect pointer 改寫為以下:

void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            EXP12;
        else
            EXP13;
    }
    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 = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

測驗 9

考慮以下進行記憶體地址對齊 (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 - MMM) & ~(NNN))

思考與想法

根據題意，該巨集需要返回一經過記憶體對齊後的大小，也就是說若傳入介於 1~16 之值，需要回傳 16 ，若傳入 0 ，則需要回傳 0 。我們先不考慮傳入值為 0 的情形，若假設傳入數值為 3 ：

                        x 00000011
        x + MAX_ALIGNMENT 00010011

因為需要回傳 16 也就是 00010000 ，且 bitwise 的運算為 & ，因此我們可以知道 ~(NNN) 的值為 11111100 ，但是因為最後面的 0 是根據 x + MAX_ALIGNMENT 才知道需要什麼樣的 ~(NNN) ，因此 ~(NNN) 應該是依靠前方的 - (MMM) 來完成 & 的。由於 ~ 的關係，大部分的位元應該都是 1 ，若要前方皆為 1 ，後方不為 1 ，只能令 NNN 為 MAX_ALIGNMENT - 1 ，此時 ~(NNN) 為 11110000 ，這樣變可以讓 MAX_ALIGNMENT 位元中的 1 可以被 & 到，並且 x + MAX_ALIGMENT 的剩下位元也不會計算出來。

但是當傳入值為 0 時， x + MAX_ALIGNMENT 為 00010000 ， ~(NNN) 為 11110000 ，此時卻會回傳 16 ，但是其實必須回傳 0 ，因此 MMM 應該為 1 ，因為 x + MAX_ALIGnMENT - 1 為 00001111 ，而 ~(NNN) 為 11110000 ，此時剛好會回傳 0 ，並且輸入 1~16 時也不會影響原本的輸出。

MMM : 1
NNN : 15

測驗 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));                 \
    })

思考與想法

由程式碼中可以總共分出四種情況，分別為 x 是 int 或是 uint ，和 divisor 分別是 int 和 uint 。

  • x 為 int 且 divisor 為 int

由於 __x 會與 x 的變數型態相同，且 __d 會與 divisor 的變數型態相同。因此在進入 ? : 判斷式時，因為型態皆為 int ，因此前兩個條件 -1 > 0 為否，第三個條件 (__x > 0) == (__d > 0) 因為 __d 必定大於零，因此要依 __x 是否大於零或小於零，若大於零則為真，會回傳第一個結果： (RRR) / (__d) 若不大於零則為否，會回傳第二個結果： (SSS) / (__d) 。

  • x 為 int 且 divisor 為 uint

此時 ((typeof(x)) -1) > 0 為否，而 ((typeof(divisor)) -1) > 0 為真，所以也會回傳第一個結果 (RRR) / (__d) 。

  • x 為 uint 且 divisor 為 int
    此時 ((typeof(x)) -1) > 0 為真，而 ((typeof(divisor)) -1) > 0 為否，所以也會回傳第一個結果 (RRR) / (__d) 。

  • x 為 uint 且 divisor 為 uint
    此時 ((typeof(x)) -1) > 0 為真，而 ((typeof(divisor)) -1) > 0 為真，所以也會回傳第一個結果 (RRR) / (__d) 。

以下為 x 與 divisor 的各種情況：

divisor 為 int divisor 為 uint
x 為 int 且 > 0 (RRR) / (__d) (RRR) / (__d)
x 為 int 且 < 0 (SSS) / (__d) (RRR) / (__d)
x 為 uint (RRR) / (__d) (RRR) / (__d)

由上表可以知道，只有在 x 為 int 且 < 0 並且 divisor 為 int 的情況下才會回傳 (SSS) / (__d) ，其餘皆會回傳 (RRR) / (__d) 。

由題目之例子，需要輸出離答案最接近的整數，因此若在做除法時，若數值為 (7, 3) ，算出來為 2.333… ，則必須要四捨五入至 2 ，反之若數值為 (5, 3) ，算出來為 1.666… ，則會四捨五入至 2 ，因此我們可以知道其輸出為 2 的範圍為 5 ~ 7 ，若是需要大於 6 的數字除以 3 輸出為 2 ，我們只要將 RRR 定義為 __x ，如此便可以直接計算出需要的數值。而若需要小於 6 的數字除以 3 輸出為 2 ，我們可以將 RRR 定義為 __x + __d ，這樣可以讓數字足以進位一次，但是這會讓四捨五入變成無條件進位，因此我們需要更改增加的數值，將原本的 __d 更改成 __d >> 1 。如此一來，便可以避免加過多導致進位，又可以讓小數字可以成功進位。因此 RRR 的值為 __x + (__d >> 1) ，而 SSS 便是處理負數的問題，因此處理方式為剛好相反， SSS 的數值為 __x - (__d >> 1) 。

RRR : __x + (__d >> 1)
SSS : __x - (__d >> 1)

測驗 11

考慮以下計算整數開平方根的實作:

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

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }

    return y;
}

思考與想法

上述的 fls() 函式的主要功能為

Last changed by 
 
StevenChou43
0
434

Read more

Ring buffer 期末報告

contributed by < StevenChou499 > 進行 第 12 週測驗題第二題的延伸問題。過程中參照第 13 週測驗題第一/二題，嘗試開發出高效的 ring buffer。 相關資訊：[ ] ringbuffer 報告 [ ] Super Fast Circular Ring Buffer Using Virtual Memory trick [ ] Using black magic to make a fast circular buffer [ ] linear_ringbuffer/include/bev/linear_ringbuffer.hpp [ ] wuffs/script/mmap-ring-buffer.c

Feb 2, 2024
數位 IC 設計

ModelSim 在終端機使用方法 vlib <name> : 建立名為 name 的設計函式庫。 vlog <files> : 使用 ModelSim 編譯所有 files 的檔案。 vsim <top_level_module> : 使用 ModelSim 開啟編譯完成的檔案。 在 ModelSim 中輸入 run -all : 使用 vsim 開啟檔案後，輸入 run -all 可以執行模擬。 以下為範例 : PS C:\Users\StevenChou\Desktop\Verilog_practice\Chp5\Q3> vlib work ** Warning: (vlib-34) Library already exists at "work".

May 2, 2023
HW4 ATCONV

第一個成功版本 程式碼 : `timescale 1ns/10ps module ATCONV( input clk, input reset, output reg busy, input ready,

May 1, 2023
HDLBits 習題

HDLBits 連結 : https://hdlbits.01xz.net/wiki/Main_Page

Apr 19, 2023
Read more from StevenChou43
Published on HackMD