2022q1 Homework2 (quiz2)

contributed by < steven1lung >

測驗一

瞭解程式碼

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

這幾行的程式碼很簡單地將兩個輸入的無號整數進行相加再除以二，但是如果可慮到相加完會有溢位的問題，可以將程式碼改成下列的方式。

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

但是這份程式碼的前提是需要知道兩個無號整數的大小，將大的先減去小的再除以二，再將原本減去的小加回去。直接看會不太直覺，但把式子拆開來看就清楚了。

$\frac{high-low}{2}+low=\frac{high}{2}-\frac{low}{2}+low=\frac{high}{2}+\frac{low}{2}$

接著可以再改成以下的方式：

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

其中裡面的 >> 是右移運算子，而直接對一個無號整數進行右移就是除以二不留餘數。所以上方的程式碼就是將兩個無號整數 a 跟 b 右移除以二並且相加，最後在加上一個 EXP1。但是 >> 運算子有一個問題是餘數會被忽略，有可能兩個數 a、b 都是奇數，那直接右移再相加會少 1。

(3 >> 1) + (5 >> 1) = 1 + 2 = 3 跟正確答案差了 1

所以我們要多一個判斷式來判斷 a、b 是不是奇數，判斷奇數可以直接比對兩個數的 LSB 是否為 1 即可，故 EXP1 可以寫成 a & b & 1。

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

可以再將上方的程式碼改寫成以下：

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

這裡的程式碼如果用加法器來思考會更好瞭解，EXP2 可以想成是兩個數相加的進位，EXP3 可以想成是兩個數的相加且不考慮進位。EXP3 的相加就可以使用 XOR 來進行，EXP2 的進位可以用 AND 來達到，這樣我們可以使用 (a & b) << 1 + (a ^ b) 做到兩數的相加。最後的除以二就用一個大括號包在外面就能得到平均了， ((a & b) << 1 + (a ^ b)) >> 1，稍微化簡就可以得到答案了。

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

比較上述實作的組合語言輸出

編譯環境：gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

要看到組合語言輸出可以使用 -S，在進行組譯之前停止，我這邊使用的命令是 gcc -S -O2 xxx.c，-O2 就是將最佳化程度開到最大。

第一個實作（相加再除以二）

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

.LFB23:
	.cfi_startproc
	endbr64
	leal	(%rdi,%rsi), %eax
	shrl	%eax
	ret
	.cfi_endproc

.cfi_startproc 是代表一個函式的開始而且必須要有對應的 .cfi_endproc 來結束。

The .cfi_startproc directive, is used at the beginning of each function that should have an entry in .eh_frame. It initializes some internal data structures and emits architecture dependent initial CFI instructions. Each .cfi_startproc directive has to be closed by .cfi_endproc.

endbr64 意思是 End Branch 64 bit，終結分支跳躍。

The ENDBRANCH (see Section 73 for details) is a new instruction that is used to mark valid jump target addresses of indirect calls and jumps in the program. This instruction opcode is selected to be one that is a NOP on legacy machines such that programs compiled with ENDBRANCH new instruction continue to function on old machines without the CET enforcement. On processors that support CET the ENDBRANCH is still a NOP and is primarily used as a marker instruction by the processor pipeline to detect control flow violations. The CPU implements a state machine that tracks indirect jmp and call instructions. When one of these instructions is seen, the state machine moves from IDLE to WAIT_FOR_ENDBRANCH state. In WAIT_FOR_ENDBRANCH state the next instruction in the program stream must be an ENDBRANCH. If an ENDBRANCH is not seen the processor causes a control protection exception (#CP), else the state machine moves back to IDLE state.

ENDBRANCH 就是一個安全機制，如果程式沒有跳到正確的位置，也就是沒有遇到相對應的 endbr64，那就會發出一個 control exception 的例外。

leal 全名是 load effective address，最後面的 l 代表運算元的大小。但是 leal 可以做的事情不只是讀取，還可以進行加法運算，格式如下：
leal %offset(%base, %index, %scale), %dest 會做到
%dest = %offset + %base + %index * %scale。

所以上述的指令 leal (%rdi, %rsi), %eax 就是將 %rdi 跟 %rsi 相加放到 %eax，最後再右移 %eax 就完成了。

第二個實作 （考慮到溢位問題）

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

average:
.LFB23:
	.cfi_startproc
	endbr64
	movl	%esi, %eax
	subl	%edi, %eax
	shrl	%eax
	addl	%edi, %eax
	ret
	.cfi_endproc

從 C 的程式碼中就看得出來考慮到溢位問題的實作比較長，把原本的相加除以二改變成了相減除以二再加，所以組合語言也會相對比較長。

組合語言裡的操作就變成了把兩個數進行相減再除以二，最後把小的數跟結果相加，addl %edi, %eax，多了把比較小的數加回去的步驟。

第三個實作 （使用 bitwise）

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

average:
.LFB23:
	.cfi_startproc
	endbr64
	movl	%edi, %eax
	movl	%esi, %edx
	andl	%esi, %edi
	shrl	%eax
	shrl	%edx
	andl	$1, %edi
	addl	%edx, %eax
	addl	%edi, %eax
	ret
	.cfi_endproc

因為使用 bitwise 的實作是各自右移相加再將少算的 1 加回去，所以組合語言的輸出就比較多行，所以我們可以直接看第四個實作，將這個版本程式碼優化。

第四個實作 （優化的 bitwise）

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

average:
.LFB23:
	.cfi_startproc
	endbr64
	movl	%edi, %eax
	andl	%esi, %edi
	xorl	%esi, %eax
	shrl	%eax
	addl	%edi, %eax
	ret
	.cfi_endproc

將可以合併的右移使用 xor 相加再與進位的數相加可以減少將近一半的程式碼，並且使用的是 bitwise 操作。

更詳細的介紹可以看你所不知道的 C 語言：編譯器和最佳化原理篇，這邊只對上述的組合語言進行解釋。

研讀 Linux 核心原始程式碼 include/linux/average.h

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

開頭的 ## 意思是 concatenate，將 token 連接起來，所以傳進去的 name 會取代巨集裡的 name 並且合併成新的變數名稱。

BUILD_BUG_ON() 這個巨集被定義在 linux/bug.h 裡，如果裡面回傳的值為真，就會中斷此次的編譯。

#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))

在文件中有說到如果我們使用的程式碼中有一些常數需要是相等的，或是編譯時才會運算出來的，可以使用 BUILD_BUG_ON 來偵測是否有被更改過。實作出來的方式是使用了 gcc 不會建立負陣列的特性，但是 gcc 只會在明顯錯誤的情況才會發出錯誤訊息。也可以退一步使用 optimizer，如果我們不能證明 condition 為真，那就會在 linking 時發出 undefined "__build_bug_on_failed"。

#define BUILD_BUG_ON_NOT_POWER_OF_2(n)          \
   BUILD_BUG_ON((n) == 0 || (((n) & ((n) - 1)) != 0))

直接看這個巨集的名稱就知道是會在變數不是 2 的冪時輸出編譯錯誤訊息。實作的方法也很簡單，利用 2 的冪減去 1 會需要借位的性質，將變數減去 1 再跟原本的數去做 AND 。

((8) & ((8) - 1)) != 0
(1000) & (0111) != 0
(0000) != 0
0
回傳 0 所以 8 是 2 的冪

((15) & ((15) - 1)) != 0
(1111) & (1110) != 0
(1110) != 0
1
回傳 1 所以 15 不是 2 的冪

__builtin_constant_p() 這個巨集會回傳傳進去的變數是否為編譯時期常數（compile-time constant），如果是就會回傳 1，但是回傳 0 並不代表這個數就一定不是編譯時期常數，而是我們的編譯器無法確定這個數是否為變異時期常數。

WRITE_ONCE() 用來防止編譯器將多個寫入合併或是重新抓取，編譯器也不能將連續的 WRITE_ONCE() 程式碼重新排列。

DECLARE_EWMA 巨集總共需要三個參數，name 就是之後結構體跟 helper 函式的名稱，_precision 會決定小數部分或有多少位，_weight_rcp 就是 EWMA 的權重部分，新的值會佔

$\frac{1}{weight-rcp}$，而舊的值會佔

$(1-\frac{1}{weight-rcp})$。

巨集裡的函數都在開頭進行了 4 個檢查，檢查 _precision 跟 _weight_rcp 是否為編譯時期常數，檢查 _precision 是否有超過 30，因為一定有非小數部分，最後再檢查 _weight_rcp 是否為二的冪。

ewma_##name##_init 將結構體裡的變數初始化成 0，ewma_##name##_read 會將結構體裡的變數右移 _precision 位然後回傳。ewma_##name##_add 則是會將傳入的 val 變數與舊的值進行運算，算出新的移動平均後寫入結構體的變數裡。

發現 linux 原始碼不少地方有使用到 EWMA，比如說 drivers/gpu/drm/drm_self_refresh_helper.c 這個檔案就有引用 average.h。

DECLARE_EWMA(psr_time, 4, 4)

struct drm_self_refresh_data {
	struct drm_crtc *crtc;
	struct delayed_work entry_work;

	struct mutex avg_mutex;
	struct ewma_psr_time entry_avg_ms;
	struct ewma_psr_time exit_avg_ms;
};

void
drm_self_refresh_helper_update_avg_times(struct drm_atomic_state *state,
					 unsigned int commit_time_ms,
					 unsigned int new_self_refresh_mask)
{
	struct drm_crtc *crtc;
	struct drm_crtc_state *old_crtc_state;
	int i;

	for_each_old_crtc_in_state(state, crtc, old_crtc_state, i) {
		bool new_self_refresh_active = new_self_refresh_mask & BIT(i);
		struct drm_self_refresh_data *sr_data = crtc->self_refresh_data;
		struct ewma_psr_time *time;

		if (old_crtc_state->self_refresh_active ==
		    new_self_refresh_active)
			continue;

		if (new_self_refresh_active)
			time = &sr_data->entry_avg_ms;
		else
			time = &sr_data->exit_avg_ms;

		mutex_lock(&sr_data->avg_mutex);
		ewma_psr_time_add(time, commit_time_ms);
		mutex_unlock(&sr_data->avg_mutex);
	}
}

大致可以知道這個 helper 是為了要提供一個更簡單的介面來實作 panel self refresh (PSR)，下面的函示是要更新 crtc 的自我刷新時間。算出來的平均之後會被用來計算延遲多久時間來進入自我刷新模式。

測驗二

瞭解程式碼

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

先看 -(a < b) 這邊，如果 a 小於 b 那值會是 -1 不然就是 0，所以整個小括號裡面就可以理解成：如果 a 小於 b ，括號內的運算會變成 ((a ^ b) & -1)，不然會是 ((a ^ b) & 0)。

我們先討論 a 不小於 b 的情況，也就是 a 大於等於 b，所以要運算 a ^ ((a ^ b) & 0)。任何數去 AND 0 都會是 0，所以整個運算會變成 a ^ 0，任何數去 XOR 0 會是自己，所以最後的回傳值是 a。我們的條件是 a 大於等於 b，會回傳 a，所以回傳值是正確的。

// case a >= b :
a ^ ((a ^ b) & -(a < b))
a ^ ((a ^ b) & 0)
a ^ 0
a

如果 a 小於 b，那就要運算 a ^ ((a ^ b) & -1)，-1 在二補數的表示方式是每個位元都是 1，所以 AND -1 就會是自己。可以把剛剛的化簡程 a ^ (a ^ b)，在 XOR 裡我們可以使用交換律，將 a ^ a 先運算得出 0，再去運算 0 ^ b，所以結果是 b，結果也是正確的。

// case a < b :
a ^ ((a ^ b) & -(a < b))
a ^ ((a ^ b) & -1)
a ^ (a ^ b)
(a ^ a) ^ b
0 ^ b
b

針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作

上述的程式碼為 32 位元無號整數的實作，而對有號整數的實作方式也是一樣的。因為 -(a < b) 只會是 0 或是 1，再進行化簡就只會有一個數 a 或是 b，所以只是表示出來的數字不同，裡面的運算都還是一樣的。

找出 linux 原始碼中使用 branch-free 的手法

在 linux/lib/sort.c 中，給予子節點回推父節點的實作裡就有使用到 branch-free 的概念。

size_t i 代表的是子節點的位置。
lsbit 是一個 1-bit 的遮罩，相等於 size & -size，size & -size 就是找到 size 裡第一個 1 的位置。
size_t size 是一個元素的大小。

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

原本是要做 if (i & lsbit) i -= size;但是因為分支不好預測，所以使用了一些技巧讓分支消失。

測驗三

瞭解程式碼

#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 判斷先檢查兩個輸入是否有為零的，如果有就回傳另外一個數，因為任何數都可以整除 0，所以最大公因數一定就是不是 0 的那個數。

shift 這邊可以看成是可以整除 u 或 v 最大的 2 冪，兩個數如果有其中一個的 LSB 為 1 就停止右移。while (!(u & 1)) 這裡的運算是要將 u 變成奇數，也就是一直把 2 除掉。最後的 do 迴圈中就

這個演算法的名稱是 Stein's Algorithm，目的就是要取代除法運算。