---
tags: sysprog
---
# 2019q3 Homework5 (quiz7)
contributed by < `yxguo2536` >
### 測驗 `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;
}
```
求 KK1 ~ KK3。
---
| div | (MSG_LEN >> KK1) >> (KK2 << KK3) |
| -- | -- |
| div3 = 1, div5 = 1 | 0 |
| div3 = 1, div5 = 0 | 0 |
| div3 = 0, div5 = 1 | 4 |
| div3 = 0, div5 = 0 | 8 |
我們先從 div3 = 1, div5 = 0 的情況去分析，因為最終結果為 0 ， 我們知道 ：
1. `(8 >> KK1) >> X` 等效於 `8 >> 4` ( 以 `8` 取代 `MSG_LEN`、以 `X` 代表 `KK2 << KK3` )。
因此 (KK1,X) 有可能是 (0,4) (1,3) (2,2) (3,1) (4,0)。 但其中 (1,3) (3,1) 很明顯是不可能的，因為光用 shift 算不出 3。
2. `(8 >> 4) >> 0` 是不可能的，因為 KK1 最大只到 2
3. `(8 >> 2) >> 2` 是不可能的，因為代表 KK1 只能是常數 2，但這樣結果最大也是 `(8 >> 2) >> 0` = 2，沒辦法表示 4 和 8 的結果。
4. 由刪去法知道，div3 = 1, div5 = 0 時運算式會是 `(8 >> 0) >> 4`
- **KK1 = 0 或 div5**
- (KK2 << KK3) 有可能是 (1 << 2) 或 (2 << 1)，目前還無法確定順序。 但可以確定 **1 一定來自於 div3**，因為如果 1、2 都固定是常數，那麼算式 `(8 >> KK1) >> 4` 最大結果就是 1 ，不可能表達出 4 和 8 的結果。
現在，我們將算式選項縮減為`( 8 >> {0|div5} ) >> ( {2|div3} << {div3|2} )`，接下來從其他情況推敲 KK1 ~ KK3 ：
5. 考慮到 div3 = 0, div5 = 0 結果為 8 : 根據第 4 點我們知道 KK1 只能是 0 。 但 `(8 >> 0) >> ( 2 << 0 )` 不等於 4，`(8 >> 0) >> ( 0 << 2 )` 才是。 所以 **KK2 = div3, KK3 = 2**
現在，我們知道算式為`( 8 >> {0|div5} ) >> ( div3 << 2 )`，繼續從其他情況推敲 KK1 :
6. 考慮到 div3 = 0, div5 = 1 結果為 4 : 我們知道 `(8 >> 0) >> (0 << 2)` 不會是答案，所以 **KK1 = div5**
算式為 `(MSG_LEN >> div5) >> (div3 << 2)`
這一題最大的陷阱應該是在 div3 = 1, div5 = 1 的情況，因為此時算式是 `(MSG_LEN >> 1) >> (1 << 2)` == `8 >> 5`，很直覺的會認為他不對，但其實不管是 `8 >> 5` 或是 `8 >> 4` 結果都是 0 ，所以也是對的。
### 測驗 `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` 輸出來檢驗
請補完程式碼。
---
開始分析組語之前，我們可以先縮減一些選項 ：
1. `AAA.x`，代表 `AAA` = **e2**, 因為一開始只有 struct e2 才有 x 成員
2. `DDD.p`，代表 `DDD` = **e1**, 因為一開始只有 struct e1 才有 p 成員
3. `CCC->e1.p`，代表 `CCC` = **next**，因為只有 next 後面有辦法接 `->` 運算子
4. `BBB.next.e1.p`，代表 `BBB` = **e2**， 因為只有 struct e2 才有 next 成員
5. `FFF->GGG`，代表 `FFF` = **next**，理由同 3
6. `EEE.next`，代表 `EEE` = **e2**, 理由同4
7. `next->GGG`，則 `GGG` 只可能是 e1 或 e2 ，因為前面是 `next->`
8. `{e1|e2}.HHH` 則 `HHH` 可以大膽參測是 y(當 `GGG` 是e1) 或 x(當 `GGG` 是e2)，因為 p 和 next 兩者都是地址，不該拿來做減法運算。
整理一下，現在我們知道原程式碼應該是：
`ptr->e2.x = *(ptr->e2.next->e1.p) - (ptr->e2.next->{e1|e2}.{y|x})`
所以，真正的未知數其實只有 `GGG` 和 `HHH`
1. 先看最後一行 ： `movq %rax, (%rdi)`，代表 dereference of %rdi == ptr->e2.x，換句話說， %rdi 存放的值是 x 的地址。
2. 回頭看第一行 ： `movq 8(%rdi), %rdx`，因為 %rdi 是 x 的地址，所以 %rdx == *(&x+8) == next，更具體來說是 `ptr->e2.next`
3. 第二行： `movq (%rdx), %rax`，因為 %rdx 是 next， 所以 %rax 儲存的值是 *next，這邊有可能是 `next->e1.p` 或 `next->e2.x` （但根據接下來的第三行指令，我們知道它應該是代表 `next->e1.p`）
4. 第三行： `movq (%rax), %rax`，這邊又對 %rax 做了 dereference， 我們知道 %rax 有可能是 e1.p 或 e2.x ，但如果要對 (long) e2.x 做 dereference 說不過去，所以唯一的可能就是 `*(e1.p)`
根據1~4點的解析，我們知道組語第一到三行對應的 C 語言應為 `*(ptr->e2.next->e1.p)`
5. 第四行： `subq 8(%rdx), %rax`， 我們可以把它改寫成比較容易理解的形式 ` %rax = %rax - 8(%rdx) `，因為 %rax = `*(ptr->e2.next->e1.p)`， 所以我們知道 8(%rdx) = `ptr->e2.next->{e1|e2}.{y|x}`
6. 根據 2， 我們知道 %rdx 是 next，所以 8(%rdx) 等同於 *(next+8)，而根據 3 我們知道 next 的地址應該是指向 e1， 所以 *(e1+8) == (*e1).y == e1->y
至此，我們知道 `GGG->HHH` = **e1->y**
Sign in with Wallet
Connect another wallet