# [2019q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 7 週測驗題
:::info
目的: 檢驗學員對 bitwise 與 floating point 內部表示法的認知
:::
---
### 測驗 `1`
考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
* 從 1 數到 n，如果是 3的倍數，印出 "Fizz"
* 如果是 5 的倍數，印出 "Buzz"
* 如果是 15 的倍數，印出 "FizzBuzz"
* 如果都不是，就印出數字本身
直覺的實作程式碼如下: (`naive.c`)
```cpp
#include <stdio.h>
int main() {
for (unsigned int i = 1; i < 100; i++) {
if (i % 3 == 0) printf("Fizz");
if (i % 5 == 0) printf("Buzz");
if (i % 15 == 0) printf("FizzBuzz");
if ((i % 3) && (i % 5)) printf("%u", i);
printf("\n");
}
return 0;
}
```
觀察 `printf` 的(格式)字串，可分類為以下三種:
1. 整數格式字串 `"%d"` : 長度為 2 B
2. "Fizz" 或 "Buzz" : 長度為 4 B
3. "FizzBuzz" : 長度為 8 B
考慮下方程式碼:
```cpp
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:
```cpp
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下是利用 bit-wise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)
```cpp
#define MSG_LEN 8
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[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
其中 `is_divisible` 函式技巧來自 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/)，甚至 gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。
請補完。
==作答區==
KK1 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 2
* `(d)` div3
* `(e)` div5
KK2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 2
* `(d)` div3
* `(e)` div5
KK3 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 2
* `(d)` div3
* `(e)` div5
:::success
延伸問題:
1. 解釋上述程式運作原理並評估 `naive.c` 和 `bitwise.c` 效能落差
* 避免 stream I/O 帶來的影響，可將 `printf` 更換為 `sprintf`
2. 分析 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/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](https://github.com/lemire/fastmod)
3. `printf` 本身就是個直譯器，甚至符合 [Turing complete](https://en.wikipedia.org/wiki/Turing_completeness)，這意味著你可以用 `printf` 的字串處理來實作出各式程式，包含實作出另一個 [Turing complete](https://en.wikipedia.org/wiki/Turing_completeness) 的程式語言，例如 Brainf*ck: [printbf -- Brainfuck interpreter in printf](https://github.com/HexHive/printbf)
* 閱讀簡報 [Memory corruption: why we can't have nice things](https://github.com/HexHive/printbf/blob/master/BalCCon-presentation.pdf)
* 對照 [CS:APP 第 3 版](https://hackmd.io/@sysprog/S1vGugaDQ) 一書的第 3 章研讀
* 記錄你的認知並重現實驗
:::
---
### 測驗 `2`
[CS:APP 第 3 版](https://hackmd.io/@sysprog/S1vGugaDQ) 一書的第 2 章家庭作業 `2.97` (Page 97) 題目:
> 依據浮點數位元編碼規則，實作出符合以下原型定義和作用的函式: (`float-i2f.c`)
```cpp
/* compute (float) i */
float_bits float_i2f(int i);
```
> 給定整數 `i`, 此函式計算 (float) i 逐位元的表示法。
> 其中
```cpp
typedef unsigned float_bits;
```
> 並假設 `int` 長度為 32-bit 且在 little endian 機器上執行。
可用的工具函式:
```cpp
/* Assuming i > 0, calculate an integer's bit length */
/* * e.g. 0x3 => 2, 0xFF => 8 */
static inline int bits_length(int i) { return 32 - __builtin_clz(i); }
/* generating bitmask. e.g. 3 => 0x00000007, 16 => 0x0000FFFF */
static inline unsigned bits_mask(int l) { return (unsigned) -1 >> (32 - l); }
```
==本題採問答形式進行==
---
### 測驗 `3`
[CS:APP 第 3 版](https://hackmd.io/@sysprog/S1vGugaDQ) 一書的第 3 章家庭作業 `3.70` (Page 224) 題目:
> 考慮到以下 union 宣告
```cpp
union ele {
struct {
long *p, y;
} e1;
struct {
long x;
union ele *next;
} e2;
};
```
> 編譯器產生以下組合語言程式碼:
```cpp
proc:
movq 8(%rdi), %rdx
movq (%rdx), %rax
movq (%rax), %rax
subq 8(%rdx), %rax
movq %rax, (%rdi)
ret
```
對應的 C 語言程式如下:
```cpp
void proc(union ele *ptr) {
ptr->AAA.x = *(ptr->BBB.CCC->DDD.p) - (ptr->EEE.FFF->GGG.HHH);
}
```
提示: 可用 `gcc -Os -S` 輸出來檢驗
請補完程式碼。
==作答區==
AAA = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
BBB = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
CCC = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
next
DDD = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
EEE = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
FFF = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
GGG = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
HHH = ?
* `(a)` e1
* `(b)` e2
* `(c)` p
* `(d)` y
* `(e)` x
* `(f)` next
:::success
延伸問題:
1. 解釋你反組譯的過程中，是如何答題
2. 在 `gcc -Os -S` 的輸出中，可見 `.cfi_startproc` 和 `.cfi_endproc` 這兩道假指令 ([pseudo instruction](https://nasm.us/doc/nasmdoc3.html))，其作用為何？gcc 程式碼產生器透過這樣的假指令要達到什麼效果？
3. 在 GitHub 的 [組合語言版本 linked list 實作](https://github.com/search?l=assembly&p=2&q=linked+list&type=Repositories) 中挑一個為基礎，改寫為有效的 x86_64 組合語言程式碼，並確保其具備針對 singly-linked 的 list push, pop, print 等功能
:::
---
Sign in with Wallet
Connect another wallet