2022q1 Homework2 (quiz2)

contributed by < jim12312321 >

測驗題目

測驗 1 ：兩數取平均





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

解析：
在 2 進位中左移/右移 1 個 bit ，相當於對原本的數字乘/除 2 ，因此 (a >> 1) + (b >> 1) 就相當於

\frac{a}{2} + \frac{b}{2}

。

但是要特別注意一點，整數除法是無條件捨去，因此當 a 和 b 同為奇數時，需補 1。

因此可以知道， EXP1 需要判斷 a 和 b 同為奇數時等於 1 ，否則等於 0 。

EXP1

\to

a & b & 1




uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

解析：
考慮 1 個 bit 的平均，可知首先要兩 bit 相加(不考慮進位)，則這個操作等同取 ^ ，接著要考慮是否有可能進位，這個操作等同取 & ，之後還要除 2 (對應題目中的 >> 1) 。

操作的步數與題目要求的空格數吻合，我們可以合理猜測在 EXP2 和 EXP3 中有一個為 a ^ b ，另一個為 a & b ！

接著繼續考慮 1 個 bit 的平均，並以 1+1 為例。

依照取平均的正常流程可知步驟應為：
1.兩數相加( 1 ^ 1)
2.補上進位( (1 ^ 1) + (1 & 1) << 1)
3.除以 2( ((1 ^ 1) + (1 & 1) << 1) >> 1)

接著我們對 ((1 ^ 1) + (1 & 1) << 1) >> 1 進行化簡。
((1 ^ 1) + (1 & 1) << 1) >> 1
= (1 ^ 1) >> 1 + (1 & 1) << 1 >> 1 (乘法分配律)
= (1 ^ 1) >> 1 + (1 & 1) (化簡)

因此根據上述化簡，我們可以得知
EXP2

\to

a & b
EXP3

\to

a ^ b

延伸問題 2

設定

以下使用引數 -O3 -S -fverbose-asm

-O3
- 使用最高等級最佳化
-S
- 輸出組合語言代碼
-fverbose-asm
- 輸出更多資訊

組合語言代碼解析

第一小題組合語言代碼

movl    %edi, %eax      # a, tmp91
movl    %esi, %edx      # b, tmp92
andl    %esi, %edi      # b, tmp94
shrl    %eax            # tmp91
shrl    %edx            # tmp92
andl    $1, %edi        #, tmp95
addl    %edx, %eax      # tmp92, tmp93
addl    %edi, %eax      # tmp95, tmp90
ret

步驟解析：

movl %edi, %eax
- 將 a 中存的值傳給暫存器 ％eax
movl %esi, %edx
- 將 b 中存的值傳給暫存器 ％edx
andl %esi, %edi
- b &= a (a & b)
shrl %eax
- 將暫存器 %eax 右移 1 個 bit (a >> 1)
shrl %edx
- 將暫存器 %edx 右移 1 個 bit (b >> 1)
andl $1, %edi
- %edx &= 1 (a & b & 1)
addl %edx, %eax
- %eax += %edx ((a >> 1) + (b >> 1))
addl %edi, %eax
- %eax += b ((a >> 1) + (b >> 1) + (a & b & 1))
ret
- return
第二小題組合語言代碼

movl    %edi, %eax      # a, tmp89
andl    %esi, %edi      # b, tmp91
xorl    %esi, %eax      # b, tmp89
shrl    %eax            # tmp90
addl    %edi, %eax      # tmp91, tmp88
ret

步驟解析：

movl %edi, %eax
- 將 a 中存的值傳給暫存器 ％eax
andl %esi, %edi
- a &= b (a & b)
xorl %esi, %eax
- %eax ^= b (a ^ b)
shrl %eax
- 將暫存器 %eax 右移 1 個 bit ((a ^ b) >> 1)
addl %edi, %eax
- %eax += a ((a & b) + ((a ^ b) >> 1))
ret
- return

參考資料：

x86 Instruction Set Reference

3 GNU lightning’s instruction set

AT&T assembly syntax and IA-32 instructions

雜記︰
我其實沒有查到 x86_64-linux-gnu 的完整組合語言指令集，只能透過一些上面的參考資料去腦補指令集的操作流程，如果後續有找到會再補充上來。

TODO: 延伸問題 3

測驗 2 ：兩數取最大值





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

解析︰
XOR 可理解為「找不同」，因此 ((EXP4) & -(EXP5)) 中的值應為 a 與最大值間相同位元處是 0 ，不同處是 1 的數字。

e.g.
1.
a = 15, b = 14
a 為最大值，因此 ((EXP4) & -(EXP5)) 應為
$0000_{2}$
2.
a = 14, b = 15
b 為最大值，因此 ((EXP4) & -(EXP5)) 應為
$0001_{2}$

由上面的例子我們可以推知，當 a > b 時，((EXP4) & -(EXP5)) 應該要是全為 0 的 bitmask ，而當 a < b 時，((EXP4) & -(EXP5)) 應該要是 a ^ b 的 bitmask 。

另外根據題目要求我們可以得知 EXP5 為 a 和 b 的比較操作，因此 -(EXP5) 只有兩種可能的值，即為 0 或 -1 ，而 0 就是全為 0 的 bitmask ， -1 是全為 1 的 bitmask。

因此我們可以得知 EXP4 的作用為取出 a,b 間的不同， EXP5 的作用為製造 bitmask ，使特定情況下 EXP4 能發揮作用

EXP4

\to

a ^ b

EXP5

\to

a < b or a <= b

延伸問題 2





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

解析：
因為在有號數或無號數時， XOR 都能發揮「找不同」的作用，因此以下就後面的 a < b 進行討論。
在有號數的版本中情況和無號數相同，當 a >= b 應該回傳 a ，因此此時的 bitmask （原本 EXP5 的位置）應該應該輸出 0 ，使得回傳值變成 a ^ 0 。當 a < b 應該回傳 b ，因此此時的 bitmask （原本 EXP5 的位置）應該應該輸出 -1 ，使得回傳值變成 a ^ (a ^ b)。

因此有號數的版本中原先 EXP5 的位置中一樣可填入 a < b 或 a <= b 達成取最大值的效果。

TODO: 延伸問題 3

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

解析：

首先先來看在測驗 3 中提供的 GCD 演算法

If both x and y are 0, gcd is zero
$g c d (0, 0) = 0$ .

$g c d (x, 0) = x$ and
$g c d (0, y) = y$ because everything divides 0.

If x and y are both even,
$g c d (x, y) = 2 \times g c d (\frac{x}{2}, \frac{y}{2})$ because 2 is a common divisor.
Multiplication with 2 can be done with bitwise shift operator.

If x is even and y is odd,
$g c d (x, y) = g c d (\frac{x}{2}, y)$ .

On similar lines, if x is odd and y is even, then
$g c d (x, y) = g c d (x, \frac{y}{2})$ . It is because 2 is not a common divisor.

了解完演算法後，接著就來看程式碼的實現方式！


if (!u || !v) return u | v;

這行對應演算法中的第 1 步和第 2 步。



for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }

這段中可以先看迴圈的中止條件 !((u| v) & 1) ，從這裡可以發現，當 u 和 v 同時為偶數時迴圈繼續，否則終止，因此此時 shift 就是用來計算直到 u 和 v 不同時為偶數時，他們兩個間的最大公因數是 2 的幾次方。對應演算法中的第 3 行。


while (!(u & 1))
        u /= 2;

接著這段是在把 u 中含有的 2 因數全部去除 (因為上一段中已經確定 u 和 v 沒有 2 的因數了)，可以把這段對應到演算法中的第 4 行。
(當然此時我們並不能確定到底 u 或 v 是奇或偶，但在執行完這段後，我們可以確定 u 一定為奇數)











do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);

接著由於是 do-while 迴圈，因此我們先看內容最後再來看 COND 。首先根據驗算法第 5 行的做法，將 v 也變成奇數，此時可以確定 u 和 v 都是奇數。接下來的一段 if-else 就是透過相減，確保 u 是目前 u 和 v 的最大奇數公因數，因此終止條件 (COND) 就是用來判斷是否還需要繼續找最大奇數公因數。

COND

\to

而當迴圈終止時，此時的 u 就是原本 u 和 v 間的最大奇數公因數。因此要再將原先算好的兩者之間最大 2 的次方的公因數補回去。

RET

\to

u << shift

延伸問題 2

在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升






























int min(int a, int b)
{
    return a ^ ((a ^ b) & -(a > b));
}

uint64_t gcd64_ctz(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    /*because __builtin_ctz(0) is undefined behavior*/
    if (u)
        shift = __builtin_ctz(u);
    if (v)
        shift = min(shift,__builtin_ctz(v));

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

搭配 min 取得兩數之間最小的 ctz 。

效能分析

使用方法

$perf record -F 'max' ./your_executable_file
$perf report

使用數字

u = 6515616114612142224
v = 2164452161421431516

gcd64
gcd64_ctz

延伸問題 3

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

gcd 實作手法解析

在 lib/math/gcd.c 中有提供兩種實作方法，但本質上沒什麼差別，只差在判斷 __ffs 能不能用。

在進入程式碼解釋及探討應用場景前，我們先來看看 __ffs 是什麼？
__ffs(unsigned long word) 的作用找到 word 中第 1 個 1 的位置，要注意當 word 中沒有任何 1 的時候， __ffs(unsigned long word) 屬於未定義行為。

參考：
__ffs

備註：
ffs (linux) 與 ffs (wiki) 中有一點落差，直接看例子能直觀的感受。

e.g.

$000100_{2}$
In Linux: ffs
$\to$ 2
In Wiki example: ffs
$\to$ 3

接著來看在 lib/math/gcd.c 中提供的 gcd 實現演算法吧！























unsigned long gcd(unsigned long a, unsigned long b)
{
	unsigned long r = a | b;

	if (!a || !b)
		return r;

	b >>= __ffs(b);
	if (b == 1)
		return r & -r;

	for (;;) {
		a >>= __ffs(a);
		if (a == 1)
			return r & -r;
		if (a == b)
			return a << __ffs(r);

		if (a < b)
			swap(a, b);
		a -= b;
	}
}

由於 gcd 的演算法上面已經列過，這邊就不重複說明。要進入解析之前，可以先來看看在程式碼中每當出現 b == 1 或 a == 1 時就會出現的 r & -r 是什麼。 r = a | b 就跟原本題目中程式碼的 u | v 的效果一樣，但是在特定條件下要回傳的 r & -r 就是很棒的寫法了(至少我這麼覺得)，由於 2 補數的運算邏輯，因此 r & -r 在 a && b 的情況下必為 a 和 b 之間的最大 2 的次方的公因數。

因此當 ((b >>= __ffs(b)) == 1) || ((a >>= __ffs(a)) == 1) 時就表示兩者間沒有除了 r & -r 以外的其他公因數了(類似題目中 shift 的作用)，因此要回傳 r & -r 。

接著在理解 r 跟 __ffs 的作用後，就能直覺的了解當 a == b 時，回傳 a << __ffs(r) 的用意了(將最大 2 的次方的公因數補回去當前的最大公因數！)。

應用場景

先來個簡單的，以下程式碼是利用 lib/math/gcd.c 中提供的 gcd 實作 Lowest common multiple (最小公倍數)。

來源： linux/lib/math/lcm.c









/* Lowest common multiple */
unsigned long lcm(unsigned long a, unsigned long b)
{
	if (a && b)
		return (a / gcd(a, b)) * b;
	else
		return 0;
}
EXPORT_SYMBOL_GPL(lcm);

可以看到這個想法很簡單，也很直覺。

接著來看到在 linux/drivers/iio/afe/iio-rescale.c 中的 gcd 應用。

節錄自 linux/drivers/iio/afe/iio-rescale.c 第 196 至 211 行。
















/*
 * Calculate the scaling factor, 1 / (gain * sense), or
 * gain_div / (gain_mult * sense), while trying to keep the
 * numerator/denominator from overflowing.
 */
factor = gcd(sense, 1000000);
rescale->numerator = 1000000 / factor;
rescale->denominator = sense / factor;

factor = gcd(rescale->numerator, gain_mult);
rescale->numerator /= factor;
rescale->denominator *= gain_mult / factor;

factor = gcd(rescale->denominator, gain_div);
rescale->numerator *= gain_div / factor;
rescale->denominator /= factor;

先不管 iio 到底是什麼(我也不懂…)，但是從註解還有程式碼中我們可以很清楚的看到，透過 gcd 能幫助找到兩特定值之間的最大公因數，進而防止某些值 overflow 。

測驗 4 ： BitMap














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

從 naive 的版本中可以發現，整個程式的目的是為了紀錄 bitmap 裡每個 bitset 中的第一個 1 位於從最低位元算起的哪個位置，若 bitset 中沒有 1 則不紀錄，最後回傳有多少不為 0 的 bitset 。

在簡單了解程式碼的目的後，我們再來看 improved 的板本。
















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

再根據題目的提示後可知， EXP6 的目的在於找出目前最低位元的 1 ，其他更高位元全部清 0 。

若達成這種效果可以利用 & 搭配反轉所有 bits 僅留最低位元的 1 來完成。

EXP6

\to

bitset & -bitset

應用場景

我暫時找不到該下什麼關鍵字才能更明確的找到應用實例。因此以下我先講我覺得這樣的程式碼能怎樣被應用。

壓縮

能把一個 bitmap 轉換成用 out 、 pos 和將裡面的每筆資料進行去除 tailing zeros 之後的 bitmap 就能表示的方式，能壓縮原本 bitmap 所需的空間，若 bitmap 越稀疏，則壓縮效果越好。

以下例子直接沿用上面的程式碼及程式邏輯
e.g.
假設今天有一個 bitsize 為 4 的bitmap bm

bm:

0xFEDCBA9876543210
0xEFCDAB8967452301
0x1111000011110000
0x8888888888888888

經過上面程式運算之後可得 out 和 pos

pos = 4

out[0] =
$0 \times 64 + 4 = 4$
out[1] =
$1 \times 64 + 0 = 64$
out[2] =
$2 \times 64 + 16 = 144$
out[3] =
$3 \times 64 + 3 = 195$

搭配經過對每個內容去除 tailing zeros後的 bm_rtz

bm_rtz:

0x0FEDCBA987654321
0xEFCDAB8967452301
0x0000111100001111
0x1111111111111111

就能還原成原本的 bitmap 了！

若是今天 bitmap 中 set bits 是稀疏的，壓縮效果會更好。

bm:

0x0000000000010000
0x0010110102100000
0x0F0E000100600000
0x0000000100000000

pos = 4

out[0] =
$0 \times 64 + 16 = 16$
out[1] =
$1 \times 64 + 20 = 84$
out[2] =
$2 \times 64 + 21 = 149$
out[3] =
$3 \times 64 + 32 = 224$

搭配經過對每個內容去除 tailing zeros後的 bm_rtz

bm_rtz:

0x0000000000000001
0x0000000101101021
0x000000F0E0001006
0x0000000000000001

TODO: 延伸問題 2 3 4

測驗 5 ： LeetCode 166. Fraction to Recurring Decimal

結構體





struct rem_node {
    int key;
    int index;
    struct list_head link;
};

結構圖解：

find 函式










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

根據 hash 值在對應的 heads 中尋找對應的 key ，若有則回傳該 key 的 index ，若沒有則回傳 -1 。

fractionToDecimal 函式
由於程式很長，所以會分段講解。

判斷除數被除數是否為 0 ，除數為 0 回傳 0 ，被除數為 0 回傳空字串。

if (denominator == 0) {
    result[0] = '\0';
    return result;
}

if (numerator == 0) {
    result[0] = '0';
    result[1] = '\0';
    return result;
}

將除數及被除數進行 abs

if (n < 0)
    n = -n;
if (d < 0)
    d = -d;

改進： branchless


n = n ^ ((n ^ -n) & -(n < 0));
d = d ^ ((d ^ -d) & -(d < 0));

判斷輸出結果正負

bool sign = (float) numerator / denominator >= 0;
if (!sign)
    *p++ = '-';

改進： bitwise operation

bool sign = (numerator < 0) ^ (denominator < 0);

計算結果與輸出

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

sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
if (remainder == 0)
    return result;

改進： branchless

sprintf(p, "%ld", division ^ ((division ^ -division) & -(division < 0)));

有餘數，繼續

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;

建立並初始化存放所有餘數的 heads

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

餘數處理
由於一開始並不會立刻進入循環小數的處理因此先跳過 pos == -1 的情況，先講解後續的程式碼。

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;

建立一個 node 並把當前的餘數存進 key 跟把目前的 i (當前重複處理幾次餘數)存進 index 。
接著把這個 node 放進 heads 中的前端，，並依據在 find 中對應的 hash 方式放進對應的 heads[hash] 中。
最後更新 decimal 和 remainder 。
MMM

\to

list_add
EEE

\to

&heads[remainder % size]

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

若在 heads 中找到 remainder 則表示已經進入重複循環了，接著從當前的餘數開始往回找重複幾個數字，最後輸出結果。
PPP

\to

pos–

延伸問題 2

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

TODO: 延伸問題 2

測驗 6 ： `alignof` 實作

在進入程式碼前，我們先來看 __alignof__ 是什麼。

The keyword __alignof__ determines the alignment requirement of a function, object, or a type, or the minimum alignment usually required by a type. –__alignof__








/*
 * 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)

逐步拆解這個 marco 可以發現它的本質是兩個 (char *) (pointer of char) 相減的結果，並藉此取得兩個地址間相差多少 bytes 。但是對 c 不熟的人看到這裡可能會開始冒出一堆疑惑(就像是我!)，(struct { char c; t _h; } *)0 是什麼寫法？為什麼 struct 中還要多一個 char c ？

(struct { char c; t _h; } *)0 是什麼?

首先 (struct { char c; t _h; } *) 只是表示內含 { char c; t _h; } 的 pointer of struct ，本質上他還是某種型態的 pointer ，所以像是 (char *) 或是 (void *) 都是合法的。回到正題，(struct { char c; t _h; } *)0 是什麼？上網搜尋會找到很多有關這個問題的討論。

Is (int *)0 a null pointer? -stackoverflow
What does (char*) 0 mean? -stackoverflow
What does (char *)0 mean in c? -stackoverflow
what is the meaning of (char*)1? -stackoverflow

相信概念不夠清楚的人看完這些討論後，應該會更一頭霧水，有人說

(char*) 0 Is not a null character, but a pointer to a character at address 0.

而在其他篇中有人認為

In C (char *) 0 is treated in a special way - it is guaranteed to produce a null-pointer value of type char *.

還有人補充

In both C and C++, (int *)0 is a constant expression whose value is a null pointer. It is not, however, a null pointer constant.

因此還是來找找 C99 standard 吧！
乍看之下，(char *)0 這種表示法挺像是 cast 的，因此來看看 C99 standard 中 §6.5.4 (Cast operators) 的說明，可以在第 3 點中看到以下說明：

Conversions that involve pointers, other than where permitted by the constraints of 6.5.16.1, shall be specified by means of an explicit cast.

由於這是一個有關指標的轉換但不確定是不是 §6.5.16.1 中規定的例外狀況，因此我們再跳到 §6.5.16.1 看有關指標轉型的說明。
而在 §6.5.16.1 中規定有關 pointer assignment 的規定，因為與這個無關就不放上來了。

看到這裡似乎可以把 (char *)0 當成把 0 轉換成 pointer of char 。這樣第一個回復的內容似乎是正確的？接著我們再來看看 §6.3.2.3 第 3 點中的說明。

根據 C99 standard 中 §6.3.2.3 第 3 點中的說明。

An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.
If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

來舉個例子說明吧！

e.g
int *p = 0; //null pointer constant
int *p = (void *)0; //null pointer constant
int *p = (int *)0; //null pointer

所以 (struct { char c; t _h; } *)0 是一種 null pointer 。

題外話，那 (int *)1 是什麼呢？按照以上的說明可知， (int *)1 是把 1 cast 成 pointer of int ，所以 (int *)0 跟 (int *)1 是不一樣的。

為什麼 struct 中還要多一個 char c ？
根據你所不知道的 C 語言：記憶體管理、對齊及硬體特性中 data alignment 的章節提到， struct 會自動做 alignment 以達到最好的存取速度。
因此 struct 中的 char c 會依據後續的資料來決定要 padding 多少。

e.g.
後面接 char ，因為一樣是 char 所以不用 padding。
後面接 int ，以 int （4 bytes）為基準，因此 padding 3 bytes 。
後面接 long ，以 long （8 bytes）為基準，因此 padding 7 bytes 。

利用這個特性就可以從 char 經過 padding 之後的地址，知道後面我們好奇的那個資料型態需要用多少 bytes 來 align 。

M

\to

X

\to

延伸問題 2

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

在 linux/drivers/usb/gadget/u_f.h 可以看到 __alignof__ 被拿來計算與下一個 groupname (groupname##__next) 間的 offset 。
















#define vla_item(groupname, type, name, n) \
	size_t groupname##_##name##__offset = ({			       \
		size_t offset = 0;					       \
		if (groupname##__next != SIZE_MAX) {			       \
			size_t align_mask = __alignof__(type) - 1;	       \
			size_t size = array_size(n, sizeof(type));	       \
			offset = (groupname##__next + align_mask) &	       \
				  ~align_mask;				       \
			if (check_add_overflow(offset, size,		       \
					       &groupname##__next)) {          \
				groupname##__next = SIZE_MAX;		       \
				offset = 0;				       \
			}						       \
		}							       \
		offset;							       \
	})

延伸問題 3

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

在 linux/include/uapi/linux/const.h 中可以找到對齊相關的程式碼

以下程式碼節錄自 const.h 第 31,32 行


#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))

__ALIGN_KERNEL_MASK
針對特定的 bitmask (e.g.
$15_{10} = 1111_{2}$ ) 進行向上對齊
__ALIGN_KERNEL
在 __ALIGN_KERNEL_MASK 的基礎上，對特定長度的數字(通常是
$2^{n}, n \in N$ ) 進行向上對齊

接著在 linux/include/linux/align.h 中可以找到向上對齊/向下對齊的程式碼。

以下程式碼節錄自 align.h 第 7 至 9 行



/* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)	__ALIGN_KERNEL((x) - ((a) - 1), (a))

ALIGN
本來在 __ALIGN_KERNEL 中就是向上對齊了，所以他就是向上對齊。
ALIGN_DOWN
在要對齊的地址中先 - ((a) - 1) ，達到把 a - 1以下的位元全部 clear 並且不 +1 ，完成向下對齊。

測驗 7 ： FizzBuzz
























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

直接看 length 會不知道他要做什麼，因此我們先從&"FizzBuzz%u"[(9 >> div5) >> (KK3)] 說起。當 div5 等於 1 時（輪到 5 的倍數，先不討論 15 的倍數），要輸出 Buzz ，而此時 &"FizzBuzz%u"[(9 >> div5)] 會等於 Buzz%u ，另外 strncpy 會把 src 中的字串從前到後根據 length 複製到 dest 。
因此可知 KK3 的作用是在 3 的倍數（包含 15 的倍數）時，讓字串變成 "FizzBuzz%u" ，接著要讓

1001_{2}

變成

0000_{2}

至少要右移 4 。

KK3

\to

div3 << 2

接著來看 length 在 3 的倍數時（字串此時是 FizzBuzz%u ），要等於 4 ；在 5 的倍數時（字串此時是 Buzz%u ），要等於 4 ；最後在 15 的倍數時（字串此時是 FizzBuzz%u ）要等於 8 。

KK1

\to

div3
KK2

\to

div5

2022q1 Homework2 (quiz2)

測驗 1 ： 兩數取平均

延伸問題 2

設定

組合語言代碼解析

測驗 2 ：兩數取最大值

延伸問題 2

測驗 3 ： 求最大公因數

延伸問題 2

延伸問題 3

gcd 實作手法解析

應用場景

測驗 4 ： BitMap

應用場景

測驗 5 ： LeetCode 166. Fraction to Recurring Decimal

延伸問題 2

測驗 6 ： __alignof__ 實作

延伸問題 2

延伸問題 3

測驗 7 ： FizzBuzz

測驗 1 ：兩數取平均

測驗 3 ：求最大公因數

測驗 6 ： `alignof` 實作