2019q3 第 7 週測驗題

目的: 檢驗學員對 bitwise 與 floating point 內部表示法的認知

測驗 `1`

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:

從 1 數到 n，如果是 3的倍數，印出 "Fizz"
如果是 5 的倍數，印出 "Buzz"
如果是 15 的倍數，印出 "FizzBuzz"
如果都不是，就印出數字本身

直覺的實作程式碼如下: (naive.c)

#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 的(格式)字串，可分類為以下三種:

整數格式字串 "%d" : 長度為 2 B
"Fizz" 或 "Buzz" : 長度為 4 B
"FizzBuzz" : 長度為 8 B

考慮下方程式碼:

#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 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bit-wise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)

#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，甚至 gcc-9 還內建了 FizzBuzz optimization (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

延伸問題:

解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
- 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
分析 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
printf 本身就是個直譯器，甚至符合 Turing complete，這意味著你可以用 printf 的字串處理來實作出各式程式，包含實作出另一個 Turing complete 的程式語言，例如 Brainf*ck: printbf – Brainfuck interpreter in printf
- 閱讀簡報 Memory corruption: why we can't have nice things
- 對照 CS:APP 第 3 版一書的第 3 章研讀
- 記錄你的認知並重現實驗

測驗 `2`

CS:APP 第 3 版一書的第 2 章家庭作業 2.97 (Page 97) 題目:

依據浮點數位元編碼規則，實作出符合以下原型定義和作用的函式: (float-i2f.c)

/* compute (float) i */
float_bits float_i2f(int i);

給定整數 i, 此函式計算 (float) i 逐位元的表示法。
其中

typedef unsigned float_bits;

並假設 int 長度為 32-bit 且在 little endian 機器上執行。

可用的工具函式:

/* 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 版一書的第 3 章家庭作業 3.70 (Page 224) 題目:

考慮到以下 union 宣告

union ele {
    struct {
        long *p, y;
    } e1;
    struct {
        long x;
        union ele *next;
    } e2;
};

編譯器產生以下組合語言程式碼:

proc:
    movq    8(%rdi), %rdx
    movq    (%rdx), %rax
    movq    (%rax), %rax
    subq    8(%rdx), %rax
    movq    %rax, (%rdi)
    ret

對應的 C 語言程式如下:

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

延伸問題:

解釋你反組譯的過程中，是如何答題
在 gcc -Os -S 的輸出中，可見 .cfi_startproc 和 .cfi_endproc 這兩道假指令 (pseudo instruction)，其作用為何？gcc 程式碼產生器透過這樣的假指令要達到什麼效果？
在 GitHub 的組合語言版本 linked list 實作中挑一個為基礎，改寫為有效的 x86_64 組合語言程式碼，並確保其具備針對 singly-linked 的 list push, pop, print 等功能

2019q3 第 7 週測驗題

測驗 1

測驗 2

測驗 3

測驗 `1`

測驗 `2`

測驗 `3`