---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < [`jj97181818`](https://github.com/jj97181818) >
## 測驗 1
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
| | (a >> 1) + (b >> 1) + (a & b & 1) |
| -------- | -------- |
| a = 2, b = 2 | 1 + 1 + 0 |
| a = 2, b = 3 | 1 + 1 + 0 |
| a = 3, b = 2 | 1 + 1 + 0 |
| a = 3, b = 3 | 1 + 1 + 1 |
在 a 和 b 右移 1 位之後，最低位元可能會出現需要進位的狀況，因此要將最低位元考慮進來，也就是加上第三項 `EXP1` = `a & b & 1`。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
在 [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator) 有提到用加法器來思考：`x + y = x ^ y + (x & y) << 1`
其中，`x ^ y` 可求得位元相加不進位的總和，`x & y` 則求得進位，並將進位的值左移一位，與總和相加。
```
(x + y) / 2
= (x ^ y + (x & y) << 1) >> 1
= ((x ^ y) >> 1) + (x & y)
```
現在要求 `(x + y) / 2` 就是將 `x ^ y + (x & y) << 1` 整個右移一位，求得 `((x ^ y) >> 1) + (x & y)`，因此，EXP2 = `a & b`, EXP3 = `a ^ b`。
### 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出
> 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
### 研讀 Linux 核心原始程式碼 include/linux/average.h
> 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用
## 測驗 2
先看 [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E4%B8%8D%E9%9C%80%E8%A6%81%E5%88%86%E6%94%AF%E7%9A%84%E8%A8%AD%E8%A8%88) 提供 min 的程式碼：
```c
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
+ a > b：會因為 diff 是正的，`diff >> 31` 為 0，`(diff & (diff >> 31))` 就會是 0，直接回穿 b。
+ a < b：會因為 diff 是負的，`diff >> 31` 32 個 bit 都是 1，因此 `(diff & (diff >> 31))` 就會是 `diff` 本身，所以 `b + diff` = `b + (a - b)` = `a`，最後回傳 a。
這題 max 的程式碼：
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
限制：
+ EXP4 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。
+ EXP5 為 a 和 b 的比較操作，亦即 logical operator，限定用 >, <, ==, >=, <=, != 這 6 個運算子。
1. 這個程式最後要回傳 a 或是 b，看誰比較大。而 `a ^ 0` 會是 a 自己，而 `a ^ (b - a)` 會是 b（會寫 `b - a` 是參考 min 程式碼中 `diff` 的想法），所以 `((EXP4) & -(EXP5))` 會是 0 或是 `(b - a)`。
2. 因為 EXP5 是做比較運算，會回傳 0 或 1，在 EXP5 為 0 的情況下，不論 EXP4 是什麼，`((EXP4) & -(EXP5))` 都會是 0，也就是最後會回傳 a，是 a 比較大的情況。
3. 因此 EXP5 為 1 就會是 b 比較大的情況，EXP5 即為 `a < b`，-(EXP5) 為 -1，每個 bit 皆為 1，任何值與 -1 做 AND 運算都還會是自己，也就是 `((EXP4) & -(EXP5))` 的值會被 `EXP4` 決定。
4. 會希望 `EXP4` 會是 `b - a`，但是限定使用 OR, AND, XOR。當 `EXP4` 為 `a ^ b` 時，回傳的值會是 `a ^ (a ^ b)`，a 和 a 自己做 XOR 會是 0，0 再和 b 做 XOR 就會是 b 本身了。
因此 `EXP4` = `a ^ b`, `EXP5` = `a < b`
### 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
針對有號整數的實作和無號整數的實作一樣，因為這裡做的 XOR 的結果對於有號與無號沒有差別，後面 `a < b` 的部分就是按照兩者的大小比較，是 0 或 1，對有號無號也沒有影響。
```c
#include <stdint.h>
int32_t max(int32_t a, int32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
### Linux 核心也有若干 branchless / branch-free 的實作
> 請在 Linux 核心原始程式碼中，找出更多類似的實作手法，請善用 git log 檢索。
在 `drivers/gpu/drm/radeon/r600_blit.c` 的[第 492 行](https://github.com/torvalds/linux/blob/747f49ba67b8895a5831ab539de551b916f3738c/drivers/gpu/drm/radeon/r600_blit.c#L492)有 branchless 的實作：
int2float 是將 int 轉成 float，這裡避免 branch 的方法是先用 `__fls` 找出 MSB 的位置，然後用旋轉指令將 unsigned int 擴展成浮點數。
```c
/* 23 bits of float fractional data */
#define I2F_FRAC_BITS 23
#define I2F_MASK ((1 << I2F_FRAC_BITS) - 1)
/*
* Converts unsigned integer into 32-bit IEEE floating point representation.
* Will be exact from 0 to 2^24. Above that, we round towards zero
* as the fractional bits will not fit in a float. (It would be better to
* round towards even as the fpu does, but that is slower.)
*/
uint32_t int2float(uint32_t x)
{
uint32_t msb, exponent, fraction;
/* Zero is special */
if (!x) return 0;
/* Get location of the most significant bit */
msb = __fls(x);
/*
* Use a rotate instead of a shift because that works both leftwards
* and rightwards due to the mod(32) behaviour. This means we don't
* need to check to see if we are above 2^24 or not.
*/
fraction = ror32(x, (msb - I2F_FRAC_BITS) & 0x1f) & I2F_MASK;
exponent = (127 + msb) << I2F_FRAC_BITS;
return fraction + exponent;
}
```
也一併附上原本有 branch 的[程式碼](https://github.com/torvalds/linux/commit/747f49ba67b8895a5831ab539de551b916f3738c?diff=split)：
```c
uint32_t int2float(uint32_t input)
{
u32 result, i, exponent, fraction;
if ((input & 0x3fff) == 0)
result = 0; /* 0 is a special case */
else {
exponent = 140; /* exponent biased by 127; */
fraction = (input & 0x3fff) << 10; /* cheat and only
handle numbers below 2^^15 */
for (i = 0; i < 14; i++) {
if (fraction & 0x800000)
break;
else {
fraction = fraction << 1; /* keep
shifting left until top bit = 1 */
exponent = exponent - 1;
}
}
result = exponent << 23 | (fraction & 0x7fffff); /* mask
off top bit; assumed 1 */
}
return result;
}
```
## 測驗 3
```c
#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;
}
```
1. 在做 do while 的輾轉相除法之前，如果 u 和 v 皆為 2 的倍數，就將 u, v 都除以 2，直到至少其中一個不為 2 的倍數，shift 紀錄著除以 2 的次數（右移的次數）。
2. 輾轉相除法只關心每次除法的餘數是否為 0，為 0 時即得到最大公因數。這裡我們用相減的方式，當 `t = u - v` 的差為零時，表示得到最大公因數，又 `v = t`，因此`COND` = `v`。
3. 最後回傳的最大公因數為 `u`，但因為在做輾轉相除法之前有先將 u 除以 2（右移），因此要乘 2 shift 次（左移）。
因此 `COND` = `v`, `RET` = `u << shift`
### 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升
將原本判斷是偶數時，用迴圈不停地除以 2 的程式，都改成用 `__builtin_ctz` 算出從 LSB 到最低位元 1 之前的 0 的數量，然後透過右移來達到除以 2 的效果。
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift = min(__builtin_ctz(u), __builtin_ctz(v));
u >>= shift;
v >>= shift;
u >>= __builtin_ctz(u);
do {
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
### 解釋其實作手法和探討在核心內的應用場景
> Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。
在 `lib/math/gcd.c` 中有實作兩種 GCD，如果能使用 `__ffs`（find first bit in word），就用第一種 GCD 實作，反之用第二種。`__ffs.h` 會針對不同架構做不同的實作，通用版本的 `__ffs.h` 在 `linux/include/asm-generic/bitops/__ffs.h` 中：
在使用 `__ffs.h` 的 GCD 實作中，和以 `__builtin_ctz` 改寫 GCD 程式中的 `__builtin_ctz` 很像，只是換成使用 `__ffs`（這裡的 `__ffs` 是從 0 開始從 LSB 算到最低位元 1，`__builtin_ctz` 是從 1 開始算到最低位元 1 的前一個，剛好結果會是一樣的）。
`r & -r` 和測驗 4 的答案 `EXP6` = `bitwise & -bitwise` 是同樣意思，會留下最低位元的 1，其餘位元為 0。
```c
#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
/* If __ffs is available, the even/odd algorithm benchmarks slower. */
/**
* gcd - calculate and return the greatest common divisor of 2 unsigned longs
* @a: first value
* @b: second value
*/
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;
}
}
#else
/* If normalization is done by loops, the even/odd algorithm is a win. */
unsigned long gcd(unsigned long a, unsigned long b)
{
unsigned long r = a | b;
if (!a || !b)
return r;
/* Isolate lsbit of r */
r &= -r;
while (!(b & r))
b >>= 1;
if (b == r)
return r;
for (;;) {
while (!(a & r))
a >>= 1;
if (a == r)
return r;
if (a == b)
return a;
if (a < b)
swap(a, b);
a -= b;
a >>= 1;
if (a & r)
a += b;
a >>= 1;
}
}
#endif
```
## 測驗 4
```c
#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;
}
```
這個程式是將 bitmap 陣列裡面所有 uint64_t 型別的整數中，bit 為 1 的位置都記錄到 out 裡面。
```c=
#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;
}
```
限制：
+ 考慮到 -bitwise 的特性
1. 如果 bitwise = 01101**100**，那 -bitwise = 10010**100**，可以發現 bitwise 和 -bitwise 最低位元的 1 往右的位元都一樣。
2. 在 bitset 不是 0 的時候就繼續在迴圈裡面找最低位元的 1，因此在第 12 行的 `bitset ^= t;` 應該要將 bitwise 該次找到最低位元的 1 改成 0，這裡的 t 要只有最低位元的 1，其餘位元都是 0，才能讓 bitset 和 t 做 XOR 之讓最低位元的 1 改為 0。
3. `t = bitwise & -bitwise` 可以讓 t 只留下最低位元的 1。
因此 `EXP6` = `bitwise & -bitwise`
### 舉出這樣的程式碼用在哪些真實案例中
因為只儲存 1 的位置，所以可以用在壓縮儲存大小的場景，例如：壓縮圖片。
### 檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進
> 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
### 思考進一步的改進空間
### 舉出 Linux 核心使用 bitmap 的案例
> 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例
## 測驗 5
```c=
#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;
}
```
+ 13~23 行：`hash = key % size;` 用 remainder % size 的方式決定要把節點塞在哪一個 heads 的 linked list。在這個 function 裡面，我們嘗試在特定 linked list 找尋是否有相同的餘數（key）的節點，如果有就回傳 index（value），如果找不到就回傳 -1。
+ 72~75 行：先替 heads 配置記憶體，產生有 1333 個 bucket 的 hashtable，可以用 index 去指定特定 bucket。並將每個 bucket 的頭都先指向自己，因為還沒有任何值放進來。
+ 77~93 行：當還有餘數 remainder 的時候，就在這個迴圈裡處理小數點後面的數字。先去 hash table 找特定 linked list 有沒有一樣的餘數。
+ 79~88 行：如果有一樣的餘數，pos >= 0，處理循環小數的部分。
+ 89~96 行：如果沒有，pos 為 -1，並配置一個節點加到 linked list 上面，其中 key 為餘數，index 為小數點後第幾位（從第 0 位開始算）。要將節點加在 hashtable 上的某個 bucket，用 find 函式尋找特定餘數的方式一樣，用 `ramainder % size` 來決定要在哪個 heads 的 linked list 找餘數。
(remainder * 10) / d
+ 95~96 行： `(remainder * 10) / d` 是算出這位的小數數字，`+ '0'` 讓前面數字轉成字元，然後加到 `dicimal` 裡。`(remainder * 10) % d` 會算出下一輪的餘數。
因此 `PPP` = `pos--`, `MMM` = `list_add`, `EEE` = `&heads[remainder % size]`
### 指出其中不足，並予以改進
#### 改進一：
第 58 行，不需要特別做 division > 0 的條件判斷：
```c
sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
```
因為在第 45 行已經處理過為負數的 n 和 d 了：
```c
/* deal with negtive cases */
if (n < 0)
n = -n;
if (d < 0)
d = -d;
```
所以可以改成：
```c
sprintf(p, "%ld", (long) division);
```
#### 改進二：
第 51 行的判斷正負號：
```c
bool sign = (float) numerator / denominator >= 0;
```
可以改成：
```c
bool sign = numerator < 0 ^ denominator < 0;
```
### 找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例
> 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
## 測驗 6
```c
/*
* 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)
```
1. 解釋 ALIGNOF(t)
+ `(struct { char c; t _h; } *)0` 表示將 0 轉型成指向 `struct { char c; t _h; }` 的 pointer，他的特殊意義為空指標，但不能確定空指標指向的位置。
+ `(&((struct { char c; t _h; } *)0)->M)` 是取得 struct 中某個成員 `M` 的位址
+ `(char *)(&((struct { char c; t _h; } *)0)->M)` 是將 struct 中某成員 `M` 的位址轉型成 char*
+ `((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)` 就是將 struct 中某成員 `M` 的位址減去 X
2. [offsetof](https://en.wikipedia.org/wiki/Offsetof) 是找某個 struct st 中的成員 m 與 struct 起始位置間的距離（指定成員和起始位置的偏移量）。比較好的寫法是第二種，用位址減去另外一個位址，得到位址的偏移量，第一種是直接得到 m 的位址，但是不能保證空指標的值為多少。
```c
#define offsetof(st, m) ((size_t)&(((st *)0)->m))
```
```c
#define offsetof(st, m) ((size_t)((char *)&((st *)0)->m - (char *)0))
```
3. ALIGNOF 可以用 offsetof 來實作，這題 ALIGNOF 實作的前半 `(char *)(&((struct { char c; t _h; } *)0)->M)` 和 offsetof 一樣作用，後半減掉一個 X，X = 0。
ALIGNOF 改用 offsetof 實作：
```c
#define ALIGNOF(t) offset(struct { char c; t _h; }, M)
```
4. 有發現 struct 的第一個成員放 char 可能是因為它做 alignment 的大小是最小的（1 byte），如果後面 t 型別變數 `_h` 需要比較大的 alignment 的話，那 `char c` 也需要 padding 到跟 `_h` 一樣的 alignment size，所以才會去算 `char c` 的大小（指定成員 `_h` 和 struct 起始位置的偏移量），所以這裡的 M 為 `_h`，即可得到 t 型別 `_h` alignment 的大小。
因此 `M` = `_h`, `X` =`0`
### 在 Linux 核心原始程式碼中找出 `__alignof__` 的使用案例 2 則
> 針對其場景進行解說
#### 第一則：
在 `linux/include/linux/kstrtox.h` 的[第 30 行](https://github.com/torvalds/linux/blob/35e43538af8fd2cb39d58caca1134a87db173f75/include/linux/kstrtox.h#L30)：
```c
static inline int __must_check kstrtoul(const char *s, unsigned int base, unsigned long *res)
{
/*
* We want to shortcut function call, but
* __builtin_types_compatible_p(unsigned long, unsigned long long) = 0.
*/
if (sizeof(unsigned long) == sizeof(unsigned long long) &&
__alignof__(unsigned long) == __alignof__(unsigned long long))
return kstrtoull(s, base, (unsigned long long *)res);
else
return _kstrtoul(s, base, res);
}
```
kstrtoul 是將一個字串轉成 unsigned long，實作有用到 `__alignof__` 來判斷 `unsigned long` 和 `unsigned long long` 的 alignment 大小是否一樣。可能是要確保在該 data model 下 `unsigned long` 和 `unsigned long long` 的大小是一樣的，例如在 LP64 下，就都是 64 bit。
#### 第二則：
在 `linux/crypto/aegis.h` 的[第 18 行](https://github.com/torvalds/linux/blob/68453767131a5deec1e8f9ac92a9042f929e585d/crypto/aegis.h#L18)：
```c
union aegis_block {
__le64 words64[AEGIS_BLOCK_SIZE / sizeof(__le64)];
__le32 words32[AEGIS_BLOCK_SIZE / sizeof(__le32)];
u8 bytes[AEGIS_BLOCK_SIZE];
};
struct aegis_state;
extern int aegis128_have_aes_insn;
#define AEGIS_BLOCK_ALIGN (__alignof__(union aegis_block))
```
有一個巨集 `AEGIS_BLOCK_ALIGN` 會取得 union `aegis_block` 的 alignment 大小。
### 在 Linux 核心原始程式碼找出 `ALIGN`, `ALIGN_DOWN`, `ALIGN_UP` 等巨集
> 探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)
+ 在 `linux/tools/testing/selftests/vm/pkey-helpers.h` 的[第 180 行](https://github.com/torvalds/linux/blob/bf4eebf8cfa2cd50e20b7321dfb3effdcdc6e909/tools/testing/selftests/vm/pkey-helpers.h#L180)有 `ALIGN_DOWN` 和 `ALIGN_UP` 的巨集：
```c
#define ALIGN_UP(x, align_to) (((x) + ((align_to)-1)) & ~((align_to)-1))
#define ALIGN_DOWN(x, align_to) ((x) & ~((align_to)-1))
```
+ 在 `linux/tools/testing/selftests/vm/hmm-tests.c` 的[第 54 行](https://github.com/torvalds/linux/blob/68453767131a5deec1e8f9ac92a9042f929e585d/tools/testing/selftests/vm/hmm-tests.c#L54)有 `ALIGN` 的巨集：
```c
#define ALIGN(x, a) (((x) + (a - 1)) & (~((a) - 1)))
```
#### ALIGN_UP
ALIGN_UP 的參數 `x` 是原本的大小，align_to 是要用多少 bit 為倍數來對齊。
左段的程式 `((x) + ((align_to) - 1)) ` 是將 `x` 加上 `align_to` 的大小再減去 1，讓原本大小不足 `align_to` 的部分，能向上進 1 位到 `align_to`，例如：`x` = 5, `align_to` = 32，為了讓 5 能夠對齊變成 32 位元，就讓 5 + (32 - 1) = 36，讓值超過 32。
右段的程式 `~((align_to)-1))` 是要去除不足 align_to 的餘數，因為最後算出來的值應該是 align_to 的倍數。延續上面的例子來解釋，就是 ~(32 - 1) 用二進位來表達 1110 0000，再與 36 做 AND 運算，會將不足 32 的部分都 clear 掉，就從 5 向上對齊成 32 了。
#### ALIGN_DOWN
向下對齊不需要加上`(align_to) - 1` 來補足不到 `align_to` 的餘數，而是直接捨棄不到 `align_to` 的部分。同樣用 `~((align_to)-1))` 去除不足 `align_to` 的餘數，最後算出來的值也是 `align_to` 的倍數。
#### ALIGN
在 linux 核心程式碼找到的 ALIGN 巨集看起來和向下對齊一樣。
## 測驗 7
```c
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;
}
```
1. length 代表著要印出字串的長度，可被 3 整除要輸出 Fizz（4 個字元），可被 5 整除要輸出 Buzz（4 個字元），同時可被 3 和 5 整除要輸出 FizzBuzz（8 個字元），其餘的輸出數字本身（length 預設是 2 個字元）。
2. `unsigned int length = (2 << KK1) << KK2;` 會先將 2（0010）左移 KK1 位，再左移 KK2 位。當 KK1 為 div3，KK2 為 div5 時，就可以根據 div3 和 div5 為 1（可被整除）或 0（不可被整除），來調整 length，如下表。
| | 左移位數 | length |
| -------- | -------- | -------- |
| 只被 3 整除 | 一位 | 0100 = 4 |
| 只被 5 整除 | 一位 | 0100 = 4 |
| 被 3 和 5 整除 | 兩位 | 1000 = 8 |
| 其餘 | 零位 | 0010 = 2 |
3. `strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);` 的 9 要改成 8，因為一個數在不能被 3 和 5 整除的時候，是要將 "%u" 複製到 fmt 裡面，而 % 的位置在第 8 位。
4. 當 div5 為 1 時（被 5 整除），8 右移一位為 4，從第四位開始複製 4 個字元長度，剛好是 Buzz。所以接下來要處理只被 3 整除和被 15 整除的情況，都需要從第 0 位開始複製，因為 div5 的關係，這時候的值可能是 8（1000）或 4（0100），要保證能變成 0 的話需要右移 4 位，因此 KK3 為 div3 << 2，就可以右移 4 位了。
因此 `KK1` = `div3`, `KK2` = `div5`, `KK3` = `div3 << 2`
### 評估 naive.c 和 bitwise.c 效能落差
> 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
### 改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless
> 分析 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
### 提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
> 研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
### 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c
> 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)
> + 過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論
Sign in with Wallet
Connect another wallet