2022q1 Homework2 (quiz2)

contributed by < 2020leon >

作業要求

重新回答第 2 周測驗題^{從測驗一到測驗七}，附帶的「延伸問題」也需要完成
- 解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析
比照課前測驗參考解答: Q1, Linked list 題目分析和參考題解的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。
將你的共筆加到 2022q1 Homework2 (作業區)
截止日期：
- Mar 13, 2022 (含) 之前

測驗題目

測驗 `1`

本題之函式均在求二整數之平均值。

測驗 `1` 填空

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

觀察陳述式 (a >> 1) + (b >> 1) + (EXP1) 可以了解到 EXP1 的功能為判斷其是否進位，即其範圍為零到一之間。將奇數和偶數分別代入變數 a 和變數 b 後可發現，唯一需要進位的情況為 a 和 b 同時為奇數之時。

由於現代電腦是以二進位表示數值，數值之最低有效位可用於判斷整數之奇偶性。目前目標為分別「兩個變數同時為奇數」及「其他」以上二者，因此使用 & 運算子；又僅需取出最低有效位，因此再與 1 做 & 運算。 EXP1 應填入 a & b & 1 。

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

首先觀察 EXP3 ，對其進行右移一的運算可推得其可能與類似加號的位元運算有關，而 XOR 可是為位元和，因此 EXP3 應填入 a ^ b 。

然 a ^ b 未考慮進位問題，我們可以觀察到當兩個位元均為一時才需進位。在加法時可用 (a & b) >> 1 表示 a + b 的進位。而本題旨在計算平均，因此應為 (a & b) >> 1 << 1 。所以 EXP2 應填入 a & b 。

陳述式	答案
`EXP1`	`a & b & 1`
`EXP2`	`a & b`
`EXP3`	`a ^ b`

參見：數值系統篇#運用 bit-wise operator

測驗 `1` 組合語言

將所有在測驗 1 名為 average 的函式以 gcc -S -masm=intel -Os foo.c 化為組合語言，並去蕪存菁，僅保留指令部份。

首先是相加除以二的版本。

uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

average:
	lea	eax, [rdi+rsi]
	shr	eax
	ret

以下是未去蕪存菁， gcc 的原始輸出：

	.globl	average
	.type	average, @function
average:
.LFB0:
	.cfi_startproc
	endbr64
	lea	eax, [rdi+rsi]
	shr	eax
	ret
	.cfi_endproc
.LFE0:
	.size	average, .-average

lea 即「 load effective address 」，後者為所謂「 effective address 」，中文謂之「有效位址」，其功能為將後者做完運算後賦值予前者。此例即 eax 的值會被賦為 rdi + rsi 。

shr 即「 shift right 」，將暫存器內的值向右移一位後存回。此例即將 eax 的值除以二。

ret 即「 return from procedure 」，回到原呼叫函式之處。

接著是避免 overflow 版。

uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

average:
	mov	eax, esi
	sub	eax, edi
	shr	eax
	add	eax, edi
	ret

此處指令命名皆直觀易解，即 eax = esi - edi ， eax >>= 1 ， eax += edi ，最後結果存於 eax 。

接著是第一次改寫版。

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

average:
	mov	eax, edi
	mov	edx, esi
	and	edi, esi
	shr	eax
	shr	edx
	and	edi, 1
	add	eax, edx
	add	eax, edi
	ret

第三個指令實做 a & b 並存在 edi ，第四和第五個指令實做 a >> 1 和 b >> 1 並存回原位，第六個指令實做 edi & 1 並存回 edi ，第七和第八個指令將三者相加後存在 eax 。

最後是第二次改寫版。

uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

average:
	mov	eax, edi
	and	edi, esi
	xor	eax, esi
	shr	eax
	add	eax, edi
	ret

第二個指令實做 a & b 並存於 edi ，第三個指令實做 a ^ b 並存於 eax ，第四個指令實做 eax >> 1 並存回原位，第五個指令將二者相加後存於 eax 。

在此可觀查到此版本比上一個版本的指令數還少。

研讀 `include/linux/average.h`

include/linux/average.h 內定義一個名為 DECLARE_EWMA 的巨集以實現固定精度的 EWMA 演算法。 EWMA 演算法求取移動平均﹐並對越久的歷史資料給予越低的權重。如下式。

S_{t} = {\begin{cases} Y_{0}, & t = 0 \\ α Y_{t} + (1 - α) \cdot S_{t - 1}, & t > 0 \end{cases}

其中

S_{t}

是在時間

t

上的 EWMA 值，

Y_{t}

是在時間

t

上的值，

α

則是一個介於 0 和 1 的參數。

在來看 DECLARE_EWMA 的部份。

#define DECLARE_EWMA(name, _precision, _weight_rcp)			\
	struct ewma_##name {						\
		unsigned long internal;					\
	};								\
	static inline void ewma_##name##_init(struct ewma_##name *e)	\
	{								\
		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
		/*							\
		 * Even if you want to feed it just 0/1 you should have	\
		 * some bits for the non-fractional part...		\
		 */							\
		BUILD_BUG_ON((_precision) > 30);			\
		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
		e->internal = 0;					\
	}								\
	static inline unsigned long					\
	ewma_##name##_read(struct ewma_##name *e)			\
	{								\
		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
		BUILD_BUG_ON((_precision) > 30);			\
		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
		return e->internal >> (_precision);			\
	}								\
	static inline void ewma_##name##_add(struct ewma_##name *e,	\
					     unsigned long val)		\
	{								\
		unsigned long internal = READ_ONCE(e->internal);	\
		unsigned long weight_rcp = ilog2(_weight_rcp);		\
		unsigned long precision = _precision;			\
									\
		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
		BUILD_BUG_ON((_precision) > 30);			\
		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
									\
		WRITE_ONCE(e->internal, internal ?			\
			(((internal << weight_rcp) - internal) +	\
				(val << precision)) >> weight_rcp :	\
			(val << precision));				\
	}

大致觀看程式碼可發現該巨集可謂「程式碼產生器」，產生一個結構及數個函式。再看巨集參數的部份，第一個參數為 name ，可為巨集中的結構即函式命名；第二個參數為 _precision ，定義小數精度，其單位為位元；第三個參數為 _weight_rcp ，即上方公式所提及之

α

的倒數，而其須為二的冪。

接著詳閱 DECLARE_EWMA 巨集。

在此定義一個名為 ewma_##name 的結構，內部僅定義一個 unsigned long 的成員。

struct ewma_##name {
	unsigned long internal;
};

注： ## 即串接。若將 name 帶入 a ，則結構名為 ewma_a 。

接著是 ewma_##name##_init 函式。

static inline void ewma_##name##_init(struct ewma_##name *e)
{
	BUILD_BUG_ON(!__builtin_constant_p(_precision));
	BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
	/*
	 * Even if you want to feed it just 0/1 you should have
	 * some bits for the non-fractional part...
	 */
	BUILD_BUG_ON((_precision) > 30);
	BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
	e->internal = 0;
}

內部可發現名為 BUILD_BUG_ON 的巨集，其定義在 include\linux\build_bug.h 中，其功能為在編譯時期確認其參數是否為真，若為真則停止編譯。其中還可發現名為 __builtin_constant_p 的 gcc 內建函式，其功能為確認該參數是否為編譯時期常數。

該函式唯一的功能為將結構中的成員設為 0 ，且須在呼叫以下函式之前被呼叫。

再來是 ewma_##name##_read 函式，其功能便是讀取 EWMA 值的整數部份。

static inline unsigned long
ewma_##name##_read(struct ewma_##name *e)
{
	BUILD_BUG_ON(!__builtin_constant_p(_precision));
	BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
	BUILD_BUG_ON((_precision) > 30);
	BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
	return e->internal >> (_precision);
}

最後是 ewma_##name##_add 。

static inline void ewma_##name##_add(struct ewma_##name *e,
				     unsigned long val)
{
	unsigned long internal = READ_ONCE(e->internal);
	unsigned long weight_rcp = ilog2(_weight_rcp);
	unsigned long precision = _precision;

	BUILD_BUG_ON(!__builtin_constant_p(_precision));
	BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
	BUILD_BUG_ON((_precision) > 30);
	BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);

	WRITE_ONCE(e->internal, internal ?
		(((internal << weight_rcp) - internal) +
			(val << precision)) >> weight_rcp :
		(val << precision));
}

在函式內的實做可以發現 READ_ONCE 和 WRITE_ONCE 巨集。此二巨集是為了避免編譯器過度優化，即避免其合併指令和調換順序。

此函式的功能為藉由 val 算出下一個 EWMA 值並存回結構的 internal 中。其實做關鍵之處為 (((internal << weight_rcp) - internal) + (val << precision)) >> weight_rcp ，其利用位移的技巧巧妙地算出下一個時間的值。

其在 Linux 核心內的應用如 net/mac80211/sta_info.h 等，與計算來回通訊延遲有關。

測驗 `2`

測驗 `2` 填空

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

在填空之前，先嘗試將上述改成有分支的實做。

uint32_t max(uint32_t a, uint32_t b)
{
    if (a > b)
        return a ^ (0);
    else
        return a ^ (a ^ b);
}

再嘗試展開。

uint32_t max(uint32_t a, uint32_t b)
{
    if (a > b)
        return a ^ ((0) & -(0));
    else
        return a ^ ((a ^ b) & -(1));
}

最後經過比較後，分別於 EXP4 和 EXP5 中填入對應的程式碼。

uint32_t max(uint32_t a, uint32_t b)
{
    // if (a > b)
    //     return a ^ ((a ^ b) & -(a <= b));
    // else
    //     return a ^ ((a ^ b) & -(a <= b));
    return a ^ ((a ^ b) & -(a < b));
}

陳述式	答案
`EXP4`	`a ^ b`
`EXP5`	`a < b` 或 `a <= b`

測驗 `2` branchless 實作

即如下。

uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

Linux 核心的 branchless 實做

arch/x86/kvm/mmu.h 為其中一個 branchless 實做。

/*
 * If CPL < 3, SMAP prevention are disabled if EFLAGS.AC = 1.
 *
 * If CPL = 3, SMAP applies to all supervisor-mode data accesses
 * (these are implicit supervisor accesses) regardless of the value
 * of EFLAGS.AC.
 *
 * This computes (cpl < 3) && (rflags & X86_EFLAGS_AC), leaving
 * the result in X86_EFLAGS_AC. We then insert it in place of
 * the PFERR_RSVD_MASK bit; this bit will always be zero in pfec,
 * but it will be one in index if SMAP checks are being overridden.
 * It is important to keep this branchless.
 */
unsigned long smap = (cpl - 3) & (rflags & X86_EFLAGS_AC);

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

首先第一句 if 陳述式用以判斷所傳入之參數是否為零，若其中之一為零則回傳另一參數之值。即

g c d (0, 0) = 0

、

g c d (x, 0) = x

和

g c d (0, y) = y

。

接下來的 for 迴圈判斷所傳入之參數是否皆為偶數，若皆為偶數則將其同時除以二，並以 shift 記錄迴圈次數（即除以幾個二）。在經過 for 迴圈後，即可保證 u 和 v 其中之一為奇數，且可以推論經過處理過的 u 和 v 目前最大公因數為奇數。以上對應到以下數學式：

g c d (x, y) = 2 * g c d (x / 2, y / 2)

。

由於目前最大公因數為奇數，再來的 while 迴圈則將 u 關於二的因數去除。（

g c d (x, y) = g c d (x / 2, y)

）

緊接著的 do while 迴圈的第一步則同上方的 while 迴圈，只是針對不同的變數做操作。再來的 if else 則是將二數相減，取其差的絕對值存入 v ，取二數較小者存入 u ，即輾轉相除法。

接著是 do while 的迴圈條件 COND 。輾轉相除法的結束條件為其中之一為零。由於 v 為二數之差，故以 v 作為檢查條件，而 u 則為經過處理過的二數之最大公因數。

最後在回傳值的部份需將偶數部份還原，也就是回傳 u << shift 。

陳述式	答案
`COND`	`v`
`RET`	`u << shift`

改寫 GCD

嘗試用 __builtin_ctz 改寫 GCD 。

uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v)
        return u | v;
    int shift_u = __builtin_ctzl(u);
    int shift_v = __builtin_ctzl(v);
    u >>= shift_u, v >>= shift_v;
    do {
        v >>= __builtin_ctzl(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << (shift_u ^
                 ((shift_u ^ shift_v) &
                  -(shift_u > shift_v)));  // u << min(shift_u, shift_v)
}

Linux 核心中也內建 GCD

lib/math/gcd.c 中其中一個實做如下。

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

其中 __ffs 為 find first set ，在此功能同 ctz 相關函式。

r & -r 即對於自己的二補數（一補數加一）進行 AND 運算，所以其結果為 1 << __builtin_ctzl(r) ，必為二的冪，可類比上方實做的 shift 。

其餘邏輯與上方實做相似。

在核心內的應用如 lib/math/lcm.c 、 sound/core/pcm_timer.c 等。

測驗 `4`

測驗 `4` 填空

#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 變數。

我們可以利用二補數的特性來完成 EXP6 的需求。考慮到 xx100 （ x 代表 don't-care term ），其二補數亦為 xx100 。兩者做 AND 運算後亦為 xx100 故填入答案 bitset & -bitset 。

陳述式	答案
`EXP6`	`bitset & -bitset` 或 `-bitset & bitset`

測驗 `5`

測驗 `5` 填空

#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`	`pos--`
`MMM`	`list_add`
`EEE`	`&heads[remainder % size]`

測驗 `6`

測驗 `6` 填空

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

可以觀察到其是利用 struct 對齊性質來實做 alignof 。首先觀察 M ，可發現其接在 -> 運算子之後，所以應為 c 或 _h 其一；又若填入 c 則 &((struct { char c; t _h; } *)0)->c 恆為零，無法體現出 t 的型態，因此填入 _h 。而事實上 &((struct { char c; t _h; } *)0)->c 的值已是正確答案，將 X 填入 0 則不會影響結果。其回傳型態為 ptrdiff_t 。

陳述式	答案
`M`	`_h`
`X`	`0`

找出 `ALIGN`, `ALIGN_DOWN`, `ALIGN_UP` 等巨集

ALIGN 、 ALIGN_DOWN 在 include/linux/align.h 可見； ALIGN_UP 則在 tools/testing/selftests/vm/pkey-helpers.h 可見。

測驗 `7`

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

上方程式碼的 length 變數表示 fmt 的長度。由規則可知，若為三的倍數需印出 Fizz 、五的倍數需印出 Buzz 、十五的倍數需印出 FizzBuzz 、其餘印出該數。因此可製成下表。

數值	`length`
三的倍數	4
五的倍數	4
十五的倍數	8
其他	2

由上表可推論 (2 << KK1) << KK2 為 (2 << div3) << div5 或 (2 << div5) << div3 。

接下來觀察 (9 >> div5) >> (KK3) 的值。

數值	`(9 >> div5) >> (KK3)`	`KK3`
三的倍數	0	4
五的倍數	4	0
十五的倍數	0	4
其他	8	?(0)

校：上方程式碼之 (9 >> div5) >> (KK3) 應為 (8 >> div5) >> (KK3) ，否則該印數字之處會錯誤印出 u 字樣。

可知 KKK3 為 div3 << 2 。

陳述式	答案
`KK1`	`div3`
`KK2`	`div5`
`KK3`	`div3 << 2`

2022q1 Homework2 (quiz2)

作業要求

測驗題目

測驗 1

測驗 1 填空

測驗 1 組合語言

研讀 include/linux/average.h

測驗 2

測驗 2 填空

測驗 2 branchless 實作

Linux 核心的 branchless 實做

測驗 3

測驗 3 填空

改寫 GCD

Linux 核心中也內建 GCD

測驗 4

測驗 4 填空

測驗 5

測驗 5 填空

測驗 6

測驗 6 填空

找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集

測驗 7

測驗 7 填空

Read more

2022q1 Homework1 (lab0)

2022q1 Project (cpumemory)

2022q1 Homework3 (quiz3)

2022q1 Homework3 (fibdrv)