Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < hsuedw >


測驗 1

題目

  • 以 bitwise 操作對兩個無號整數取平均值。
    • 也就是撰寫程式碼 2 中的 EXP1 使其功能等價於程式碼 1。
    • 也就是撰寫程式碼 3 中的 EXP2EXP3 使其功能等價於程式碼 1。
    • 程式碼 1
      ​​​​​​#include <stdint.h>
      ​​​​​​uint32_t average(uint32_t a, uint32_t b)
      ​​​​​​{
      ​​​​​​    return (a + b) / 2;
      ​​​​​​}
      
    • 程式碼 2
      ​​​​​​#include <stdint.h>
      ​​​​​​uint32_t average(uint32_t a, uint32_t b)
      ​​​​​​{
      ​​​​​​    return (a >> 1) + (b >> 1) + (EXP1);
      ​​​​​​}
      
    • 程式碼 3
      ​​​​​​uint32_t average(uint32_t a, uint32_t b)
      ​​​​​​{
      ​​​​​​    return (EXP2) + ((EXP3) >> 1);
      ​​​​​​}
      

作答

  • EXP1 = a & b & 1
  • 假設
    ba
    • EXP2 = a & b
    • EXP3 = a ^ b

延伸問題 1. 解釋上述程式碼運作的原理

  • 程式碼 2 運作的原理

    • 在 bitwise 運算中,向左位移一個 bit 就相當於
      x
      ,其中
      x=a2
    • 雖然在數學上
      a+b2
      =
      a2
      +
      b2
      ,但是在 C 語言中,當 a 與 b 皆為奇數時,因為 a 與 b 皆個別先除以 2 再相加,所以平均值會少 1。假設 a = 3,b = 5。
      • (a + b) / 2 = 4
      • a / 2 + b / 2 = 3
    • 若 a 與 b 為一奇一偶或皆為偶數,則沒有這個現象。
    • 一個奇數的二進為編碼中,LSB 必為 1。若 a & b 的 LSB 為 1,表示 a 與 b 皆為奇數。所以將 EXP1 實作為 a & b & 1 可補上當 a 與 b 皆為奇數時,各別先除二再相加所少掉的那個 1。
  • 程式碼 3 運作的原理

    • AND 與 XOR 的真值表如下所示。
      AND XOR
      0 0 0 0
      0 1 0 1
      1 0 0 1
      1 1 1 0
    • 一個位元的加法運算如下所示。觀察後可發現進位 (carry) 那一欄就是 AND 運算。 bit sum 那一欄就是 XOR 運算。所以可以用 AND 與 XOR 進行加法運算。
      carry bit sum
      0 + 0 0 0
      0 + 1 0 1
      1 + 0 0 1
      1 + 1 1 0
    • 對兩個整數 a 與 b 做加法。 a ^ b 就是每個位元的各別位元和。 (a & b) << 1 就是兩數相加後,各別位元的進位狀況。所以,C 語言程式碼中, a + b 可改寫為 (a ^ b) + ((a & b) << 1)
    • (a + b) / 2 就是 (a + b) >> 1
    • 所以, (a + b) >> 1 就是 ((a ^ b) + ((a & b) << 1)) >> 1。展開後就可以得到 (a & b) + (a ^ b) >> 1
    • 所以,EXP2 可實作為 a & bEXP3 可實作為 a ^ b
  • 參考資料:

延伸問題 2. 比較上述實作在編譯器最佳化開啟的狀況,對應的組合語言輸出,並嘗試解讀 (可研讀 CS:APP 第 3 章)

  • working

延伸問題 3. 研讀 Linux 核心原始程式碼 include/linux/average.h,探討其 Exponentially weighted moving average (EWMA) 實作,以及在 Linux 核心的應用

移動平均(Moving average),又稱滾動平均值、滑動平均,在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數,來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用,以消除短期波動,突出長期趨勢或周期。短期和長期之間的閾值取決於應用,移動平均的參數將相應地設置。例如,它通常用於對財務數據進行技術分析,如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。

  • working

測驗 2

題目

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

作答

  • EXP4: a ^ b
  • EXP5: a < b

延伸問題 1. 解釋上述程式碼運作的原理

  • 列舉部分 AND 與 XOR 運算的特性。
    • a ^ a = 0
    • a ^ 0 = a
    • a ^ 0xffffffff = 0 (假設 a 為 32 位元整數)
    • a & a = a
    • a & 0 = 0
    • a & 0xffffffff = a
  • 為了說明方便,把程式碼補齊,如下所示。
    ​​#include <stdint.h>
    ​​uint32_t max(uint32_t a, uint32_t b)
    ​​{
    ​​    return a ^ ((a ^ b) & -(a < b));
    ​​}
    
    • 假設 a > b
      • a ^ ((a ^ b) & -(a < b))
      • a ^ ((a ^ b) & -(0))
        C99 Standard

        6.5.8 Relational operators
        Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.) The result has type int.

      • a ^ ((a ^ b) & 0)
      • a ^ (0)
      • a
    • 假設 a < b
      • a ^ ((a ^ b) & -(a < b))
      • a ^ ((a ^ b) & -(1))
      • a ^ ((a ^ b) & 0xffffffff)
      • a ^ (a ^ b)
      • (a ^ a) ^ b
      • (0) ^ b
      • b
    • 假設 a = b
      • a ^ ((a ^ b) & -(a < b))
      • a ^ ((a ^ a) & -(a < a))
      • a ^ ((0) & -(1))
      • a ^ (0x00000000 & 0xffffffff)
      • a ^ (0)
      • a
  • 參考資料:

延伸問題 2. 針對 32 位元無號/有號整數,撰寫同樣 branchless 的實作

  • working

延伸問題 3. Linux 核心也有若干 branchless / branch-free 的實作,例如 lib/sort.c。

/*
 * Logically, we're doing "if (i & lsbit) i -= size;", but since the
 * branch is unpredictable, it's done with a bit of clever branch-free
 * code instead.
 */
__attribute_const__ __always_inline
static size_t parent(size_t i, unsigned int lsbit, size_t size)
{
    i -= size;
    i -= size & -(i & lsbit);
    return i / 2;
}

請在 Linux 核心原始程式碼中,找出更多類似的實作手法。請善用 git log 檢索。


測驗 3

題目

考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

註: GCD 演算法

  1. If both x and y are 0, gcd is zero
    gcd(0,0)=0
    .
  2. gcd(x,0)=x
    and
    gcd(0,y)=y
    because everything divides 0.
  3. If x and y are both even,
    gcd(x,y)=2gcd(x2,y2)
    because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
  4. If x is even and y is odd,
    gcd(x,y)=gcd(x2,y)
    .
  5. On similar lines, if x is odd and y is even, then
    gcd(x,y)=gcd(x,y2)
    . It is because 2 is not a common divisor.

改寫為以下等價實作:

#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 (COND);
    return RET;
}

作答

  • COND = v
  • RET = u << shift

延伸問題 1. 解釋上述程式運作原理

  • 就是題目附註裡寫的 GCD 演算法。

延伸問題 2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD,分析對效能的提升

  • working

延伸問題 3. Linux 核心中也內建 GCD (而且還不只一種實作),例如 lib/math/gcd.c,請解釋其實作手法和探討在核心內的應用場景。

  • working

測驗 4

題目

在影像處理中,bit array (也稱 bitset) 廣泛使用,考慮以下程式碼:

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

考慮 GNU extenstion 的 __builtin_ctzll的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。

範例: 當 a = 16
16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
從低位元 (即右側) 往高位元,我們可發現 0 → 0 → 0 → 0 → 1 ,於是 ctz 就為 4,表示最低位元往高位元有 4 個 0

用以改寫的程式碼如下:

#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 = EXP6; int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } } return pos; }

其中第 9 行的作用是找出目前最低位元的 1,並紀錄到 t 變數。舉例來說,若目前 bitset 為 000101b,那 t 就會變成 000001b,接著就可以透過 XOR 把該位的 1 清掉,其他保留 (此為 XOR 的特性)。

若 bitmap 越鬆散 (即 1 越少),於是 improved 的效益就更高。

請補完程式碼。書寫規範:

  • bitwise 運算子和運算元之間用一個半形空白區隔,如: bitset | 0x1
  • 考慮到 -bitwise 的特性
  • 不要包含任何小括號,即 ( 和 )
  • 以最精簡的形式撰寫程式碼

作答

  • EXP6 = -bitset & bitset

延伸問題 1. 解釋上述程式運作原理,並舉出這樣的程式碼用在哪些真實案例中

  • 運作原理

    • 假設 bitset 的二進位表示法中,由 LSB 往 MSB 數,遇到第一個 1 前,有 x 個 0。目標就是保留位元 x 為 1。其餘位元皆設為 0
    • 假設 bitset = 131210 = 0000010100100000b
    • -bitset = -131210 = 1111101011100000b
    • 所以, -bitset & bitset 結果如下。
      ​​​​​​  1111101011100000
      ​​​​​​& 0000010100100000
      ​​​​​​---------------------
      ​​​​​​  0000000000100000
      
  • 用在哪些真實案例中

    • working

延伸問題 2. 設計實驗,檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進?應考慮到不同的 bitmap density

  • working

延伸問題 3. 思考進一步的改進空間

  • working

延伸問題 4. 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例

  • working

測驗 5

題目

以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作:

#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 (PPP > 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; MMM(&node->link, EEE); *q++ = (remainder * 10) / d + '0'; remainder = (remainder * 10) % d; } strcpy(p, decimal); return result; }

請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫。

PPP = ? (表示式)
MMM = ? (巨集)
EEE = ? (表示式)

作答

  • PPP = pos--
  • MMM = list_add
  • EEE = &heads[remainder % size]

延伸問題 1. 解釋上述程式碼運作原理,指出其中不足,並予以改進

例如,判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms

  • 第 26~24 行。
    • malloc 動態宣告一個長度為 1024 bytes 的記憶體空間。用這個記憶體空間存字串。並用 result 這個指標指向這個記憶體空間的起始位址。然後再宣告一個指標 p 用來操作 result 所指向的記憶體空間。原則上,就是用 result 所指向的記憶體空間做出一個 C sytle string。
    • 根據題意,將計算結果表示為字串,此字串長度小於 104。所以,將變數 size 初始化為 1024 並以此宣告記憶體大小,顯然有問題。

      It is guaranteed that the length of the answer string is less than 104 for all the given inputs.

    • 若考慮 C style string 的 null terminator。 size 應初始化為 10001 較為恰當。
  • 第 30~32 行。
    • denominator (分母)為 0,則回傳空字串。
    • 事實上,這個判斷可以刪除,不需要實作這三行。因為題目的 constraints 中已經明白的說明了分子與分母的數值範圍。根據題意,分母不可能為 0。

      Constraints:

      • -231 <= numerator, denominator <= 231 - 1
      • denominator != 0
  • 第 35~39 行。
    • numerator 為 0,則計算結果必為 0。所以直接在 result 所指向的記憶體空間的第一個字元填 0,第二個字元填 \0 (null terminator)。並回傳此 C style string。
  • 第 41~53 行。
    • 用兩個型態為 long long 的變數 nd 分別儲存 numeratordenominator 的數值。並對 nd 取絕對值。若 numerator 除以 denominator 是負數,在第 51~53 行中,把負號填入 result 所指向的記憶體空間的第一個字元。然後,指標 p 往後移一個 byte。
      • 第 51~53 行中判斷最後的答案是否有負號,可改為下列的實作。因為 numeratordenominator 不同時為正數或不同時為負數,最後的答案就會有負號。所以可用 XOR 實作。
        ​​​​​​​​​​bool sign = (numerator < 0) ^ (denominator < 0); ​​​​​​​​​​if (sign) ​​​​​​​​​​ *p++ = '-';
  • 第 55~63 行。
    • 分別把 n 除以 d 的餘數與商數指派給 remainderdivision 兩個變數中。
    • 以指標 p 所指的記憶體位址為起始,用 sprintf 與格式化字串把 division 列印到 result 所指向的記憶體空間。
      • 因為第 46~53 已經處理了正負號的問題,所以執行到第 58 行時, division 必為正數。第 58 行應改為:
        ​​​​​​​​​​sprintf(p, "%ld", (long) division);
    • remainder (餘數)為 0 ,表示整除。可以直接回傳 result 所指向的記憶體空間內的字串。
    • remainder (餘數)不為 0 ,表示有小數位數。所以將指標 p 移到字串的尾端(第 62 行)後,在字串尾端加入小數點。
  • 第 68~70 行。
    • 以指標 decimal 指向以 size 為大小所動態宣告的記憶體空間。並將此記憶體空間的內容清為 0。
    • 以指標 q 為操作 decimal 所指向的記憶體空間。
      • 因為題目已經保證最後的答案部會超過 104,所以第 68~69 行可以改為
        ​​​​​​​​​​char *decimal = malloc(size - strlen(result)); ​​​​​​​​​​memset(decimal, 0, size - strlen(result)); ​​​​​​​​​​char *q = decimal;
  • 第 72~75 行。
    • 建立並初始化一個有 1333 個 bucket 的 hash table (指標 heads 所指的記憶體空間)。每個 bucket 都是一個環狀雙向鏈結串列。
    • 不了解為什麼要 1333 個 bucket。
  • 第 77~97 行。
    • 這個 for 迴圈會一直執行到 remainder 等於 0 為止。
      • for 迴圈的 i 等於 0,表示小數點後第一位;i 等於 1,表示小數點後第二位
    • 若在 hash table 中找到 remainder,代表發生循環小數。
      • 透過指標 p 的操作,把 decimal 裡的資料複製到 result 所指向的記憶體空間中。 (第 80~81 行)
        • pos 是循環小數開始的位置,所以先將尚未循環的小數位數填到 result 所指向的記憶體空間中。
      • 透過指標 p 的操作,在字串最後加上 open parenthesis。(第 82 行)
      • 透過指標 p 的操作,再把 decimal 中剩下的循環小數填到 result 所指向的記憶體空間中。(第 83~84 行)
      • 透過指標 p 的操作,在字串最後加上 closing parenthesis。(第 85 行)
      • 最後,透過指標 p 的操作,填上 '\0' (null terminator)。然後回傳結果(就是 result` 所指向的記憶體空間中的 C style string)。 (第 86~87 行)
    • 若在 hash table 中找不到 remainder,代表沒有發生循環小數。
      • 用動態記憶體宣告產生一個 struct rem_node 型態的 object,並以指標 node 指向它。利用此物件把這一次的 numeratori 記錄在 hash table (指標 heads 所指的記憶體空間)中。 (第 89~91 行)
      • 透過指標 q 的操作,將小數點後的第一位寫入 decimal 所指向的記憶體空間中的字串的尾端。 (第 95 行)
      • 更新 remainder 。 (第 96 行)
  • 第 99~100 行
    • 若第 77~97 行的 for 迴圈結束(remainder 歸 0),表示沒有循環小數發生。把 decimal 裡的所有字元全部複製到 result 所指向的記憶體空間中的字串的尾端。
    • 回傳最後結果。
完整程式碼

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

#define list_entry(node, type, member) container_of(node, type, member)

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}


static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

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 = 10001;
    char *result = malloc(size);
    char *p = 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 = (numerator < 0) ^ (denominator < 0);
    if (sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", (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 - strlen(result));
    memset(decimal, 0, size - strlen(result));
    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;
}

延伸問題 2. 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中,找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例,予以探討和解說其應用場景

  • working

測驗 6

題目

alignof 是 GNU extension,以下是其可能的實作方式:

/*
 * 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)->M) - (char *)X)

請補完上述程式碼,使得功能與 alignof 等價。

請補完,使得程式碼符合預期,儘量以最簡短且符合一致排版的形式來撰寫

M = ?
X = ?

作答

  • M = _h
  • X = 0
  • test my answer
    ​​#include <stdio.h>
    ​​#include <stddef.h>
    
    ​​//#define ALIGNOF(t) \
    ​​//    ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)(&((struct { char c; t _h; } *)0)->c))
    
    ​​#define ALIGNOF(t) \
    ​​    ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
    
    ​​int main()
    ​​{
    ​​    printf("char, %ld\n", __alignof__(char));
    ​​    printf("unsigned char, %ld\n", __alignof__(unsigned char));
    ​​    printf("int, %ld\n", __alignof__(int));
    ​​    printf("long, %ld\n", __alignof__(long));
    ​​    printf("long long, %ld\n", __alignof__(long long));
    ​​    printf("unsigned ing, %ld\n", __alignof__(unsigned int));
    ​​    printf("unsigned long, %ld\n", __alignof__(unsigned long));
    ​​    printf("unsigned long long, %ld\n", __alignof__(unsigned long long));
    ​​    printf("double, %ld\n", __alignof__(double));
    ​​    printf("float, %ld\n", __alignof__(float));
    
    ​​    printf("---------------\n");
    
    ​​    printf("char, %ld\n", ALIGNOF(char));
    ​​    printf("unsigned char, %ld\n", ALIGNOF(unsigned char));
    ​​    printf("int, %ld\n", ALIGNOF(int));
    ​​    printf("long, %ld\n", ALIGNOF(long));
    ​​    printf("long long, %ld\n", ALIGNOF(long long));
    ​​    printf("unsigned ing, %ld\n", ALIGNOF(unsigned int));
    ​​    printf("unsigned long, %ld\n", ALIGNOF(unsigned long));
    ​​    printf("unsigned long long, %ld\n", ALIGNOF(unsigned long long));
    ​​    printf("double, %ld\n", ALIGNOF(double));
    ​​    printf("float, %ld\n", ALIGNOF(float));
    ​
    ​​    return 0;
    ​​}
    
    • output
      ​​​​​​char, 1
      ​​​​​​unsigned char, 1
      ​​​​​​int, 4
      ​​​​​​long, 8
      ​​​​​​long long, 8
      ​​​​​​unsigned ing, 4
      ​​​​​​unsigned long, 8
      ​​​​​​unsigned long long, 8
      ​​​​​​double, 8
      ​​​​​​float, 4
      ​​​​​​---------------
      ​​​​​​char, 1
      ​​​​​​unsigned char, 1
      ​​​​​​int, 4
      ​​​​​​long, 8
      ​​​​​​long long, 8
      ​​​​​​unsigned ing, 4
      ​​​​​​unsigned long, 8
      ​​​​​​unsigned long long, 8
      ​​​​​​double, 8
      ​​​​​​float, 4
      
  • 參考資料:

延伸問題 1. 解釋上述程式碼運作原理

  • (char *)(&((struct { char c; t _h; } *)0)->_h)
  • 同理,(char *)0 就是取得位址 0 。
  • 兩者相減就是型態 t 的 alignment。
  • 編譯器處理 &((TYPE *)0)->MEMBER 時,不會真正去存取地址為 0 的記憶體區段,只是將 0 看做指標操作的一個運算元。也就是說,編譯器只是把記憶體位址拿來當數字一樣做運算。並不會真的對記憶體位址所表示的記憶體區間做存取的動作。

延伸問題 2. 在 Linux 核心原始程式碼中找出 alignof 的使用案例 2 則,並針對其場景進行解說

  • working

延伸問題 3. 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集,探討其實作機制和用途,並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻,儘量共用相同的巨集

  • working

測驗 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 << KK1) << KK2; char fmt[9]; strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length); fmt[length] = '\0'; printf(fmt, i); printf("\n"); } return 0; }

作答

  • KK1 = div3
  • KK2 = div5
  • KK3 = div3 << 2
    • note: 第 17 行應改為
      ​​​​​​strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
      否則,當 i 不為 3、5 或 15 的倍數時,無法印出 i 的值。
完整程式碼
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>

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"[(8 >> div5) >> (div3 << 2)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

延伸問題 解釋上述程式運作原理並評估 naive.cbitwise.c 效能落差 (避免 stream I/O 帶來的影響,可將 printf 更換為 sprintf)

延伸問題 2. 分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論),並設計另一種 bitmask,如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」,然後再改寫 bitwise.c 程式碼,試圖運用更少的指令來實作出 branchless; (參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware)

延伸問題 3. 研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論,提出 throughput (吞吐量) 更高的 Fizzbuzz 實作

延伸問題 4. 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制,探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)

過程中,你可能會發現可貢獻到 Linux 核心的空間,請充分討論


答案卷