# 2018q3 Homework1
contributed by <`dvsseed`>

參考書目:
[Computer Systems: A Programmer's Perspective, 3/E](http://csapp.cs.cmu.edu/)

---

[TOC]

---

# 為什麼要深入學習 C 語言？

如同老師一開始所闡明的真理~ **回歸第一手資料([ISO/IEC 9899 C 語言規格](http://www.open-std.org/jtc1/sc22/wg14/www/docs/C99RationaleV5.10.pdf))，透過反思 C 語言程式設計的細節，重新學習電腦原理**

>要屏棄自己過往臆測為主的學習方式，探究實際 C 程式的行為並反思箇中原理，並正視自己的盲點，從而打下穩固的基礎。[name=曾令燊][time=Wed, Sep 19, 2018 1:53 PM][color=#d163f9]

## 你所不知道的 C 語言

### 為什麼要深入學習 C 語言？

* 老師提到的 c++ andy c++rush，如下：

    int main()
    {
        [](){};
        []{}();
        {}[]{};
    }

- 我利用 gcc 編譯後出現錯誤[color=#ff0000]，如下：

    c++andy_c++rush.c: In function ‘main’:
    c++andy_c++rush.c:5:5: error: expected expression before ‘[’ token
         [](){};
         ^
    c++andy_c++rush.c:6:5: error: expected expression before ‘[’ token
         []{}();
         ^
    c++andy_c++rush.c:7:7: error: expected expression before ‘[’ token
         {}[]{};
           ^

:::info
需要加上編譯參數，如 `-std=c++11`，明確指定 C++ 標準的版本 (你可以順便思考，為何編譯器不預設都用可支援的最新語言規格？)
:notes: jserv
:::

> **謝謝老師的指導!!**
> 經重新編譯，如下
> ```shell
> $ g++ -std=c++11 -Wall -o candycrush c++andy_c++rush.c
> ```
> 終於成功!!
>
> 另外，針對老師的問題，搜尋 man g++ 如下
> ```shell
> $ man g++ | grep -B l -e '-std.* default'
> gnu++1y
> GNU dialect of -std=c++14. This is the default for C++ code.
> ```
> 猜想~GNU預設都是以支援最新定案為主--`c++14`?!
> [name=曾令燊]

- ISO/IEC 9899 (簡稱 “C99”) 規格書 ([PDF](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf))，重點在於 “everything is object”
> 要下功夫去精讀這本聖經規格工具書~552 pages
> [name=曾令燊]

- 安裝 cdecl 程式

    $ sudo apt-get install cdecl

> 利用 `cdecl` 可瞭解c語法意思及產生c語法
> [name=曾令燊]

- 學習 GDB
> 利用 `cdecl` 可瞭解c語法意思及產生c語法
> [name=曾令燊]

- 安裝 rr (Record and Replay Framework)

    $ cd /tmp
    $ wget https://github.com/mozilla/rr/releases/download/5.2.0/rr-5.2.0-Linux-$(uname -m).deb
    $ sudo dpkg -i rr-5.2.0-Linux-$(uname -m).deb

- 安裝 Vim 及 Visual Studio Code
> 實際安裝後發現其UI操作不錯用,可取代`Sublime Text`,
> 連常用的 `columns select` 也有...如下：
> **In Visual Studio Code version 1.0, you can now select columns by holding down `Shift + Alt`, then click and drag with the mouse.**
> [name=曾令燊]

---

### 你所不知道的 C 語言: 指標篇

* 這個講座並非「頭腦體操」
本篇一開頭~取自 [C Traps and Pitfalls](http://www.literateprogramming.com/ctraps.pdf) 的案例 “Understanding Declarations”

    (*(void(*)())0)();

使用 [godbolt](http://gcc.godbolt.org/) 線上輸入程式碼並加上Assembly output `-Os` (空間最佳化)如下圖

科技公司面試題:

    void **(*d) (int &, char **(*)(char *, char **));

我想到老師說過的工具 `cdecl` 如下

    $ cdecl
    Type `help' or `?' for help
    cdecl> explain void **(*d) (int &, char **(*)(char *, char **));
    Warning: Unsupported in C -- 'reference'
    declare d as pointer to function (reference to int, pointer to function (pointer to char, pointer to pointer to char) returning pointer to pointer to char) returning pointer to pointer to void
    cdecl> 

- 先羅列你已經知道的部分
- void * 之謎
- 要注意 undefined behavior (UB) 問題
- 沒有「雙指標」只有「指標的指標」
- 實作老師的範例C碼後，瞭解了 ** 與 * 的差異，另外，我的理解圖想像如下
==$[ptrA]\Rightarrow[*ptrA|\&A]\rightarrow[A|1]$
$[ptrA]\Rightarrow[**p]\Rightarrow[*p|\&B]\rightarrow[B|2]$==
- array 與 pointer 可互換中，我改了程式碼，如下

    #include <stdio.h>
    int main() {
        int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        printf("%d\n", x[ x[ 2 + 2 ] ]);
    }          

- 在 GDB 實作時，遇到 ==error==，如下

    (gdb) list
    1	int main() {
    2	    int a[3];
    3	    struct { double v[3]; double length; } b[17];
    4	    int calendar[12][31];
    5	}
    6	
    (gdb) b main
    Breakpoint 1 at 0x675: file test2.c, line 1.
    (gdb) r
    Starting program: /home/davis/homework1/test2 
        
    Breakpoint 1, main () at test2.c:1
    1	int main() {
    (gdb) p memcpy(calendar, b, sizeof(b[0]))
    'memcpy' has unknown return type; cast the call to its declared return type

> 給 `memcpy` 一個 `return` 型態就可以。用 `p (void *) memcpy(calendar, b, sizeof(b[0]))` 可以解決。 by @birdca
- Null pointer?
- 有關程式，如下

    #include <stddef.h>
    int main() { return (NULL == 0); }

業經 `gcc` 及 `./null` 執行後...結果是 `1(非零)`

---

### 你所不知道的 C 語言: 函式呼叫篇

C 語言不允許 nested function，這件事簡化了 C 編譯器的設計...
* 再論 Function
- 在 C 語言中，“function” 其實是退化過的形式

- Process 和 C 程式的關聯
- [Done Is Better Than Perfect](http://gghh.name/dibtp/2015/11/10/function-calls-in-c-the-boring-specs.html)

- 從遞迴學習 function call
- 用 GDB 執行和測試 `infinite.c`
- 瞭解 stack空間與C計算語法間的變化
- 依據 [Done Is Better Than Perfect](http://gghh.name/dibtp/2015/11/11/function-calls-in-c-practical-example.html) 實作時，發現記憶體並無 L1、L2 且 無法指定位址(如：`(gdb) break *0x40057d`)

- stack-based buffer overflow
-
- 藏在 Heap 裡的細節
- 在測試實作 free()釋放記憶體時，沒有任何的 error, 如下

    #include <stdlib.h>
    int main() {
        int *p = (int *) malloc(1024);
        free(p);
        free(p);
        return 0;
    }

    $ gcc -g -o free free.c -Wall
    $ ./free
    $ 

- 為什麼 `glibc` 可以偵測出上述程式的 **``“double free or corruption”``** 呢？
- 在搜尋中，找到上述 free.c 強制執行程式以觀察對同一塊記憶體重複 free() 所進行的偵測如下

        $ MALLOC_CHECK_=1 ./free
        free(): invalid pointer
        Aborted (core dumped)

- `Set MALLOC_CHECK_ = 1` to disable this protection feature. This can achieved with the following commands, entered just before starting the application from that terminal:

        $ export MALLOC_CHECK_=1
        $ /<path>/<application name>

- malloc / free
- RAII 實作
- 我改寫了老師的程式碼才能 run，如下

        #include <stdlib.h>
        #define autofree __attribute__((cleanup(free_stack)))
        __attribute__ ((always_inline))
        inline void free_stack(void *ptr) { free(*(void **) ptr); }

        int main(void) {
            autofree int *i = malloc(sizeof (int));
            *i = 1;
            return *i;
        }

---

### 你所不知道的 C 語言: 遞迴呼叫篇
- 遞迴（recurse = A loop within a loop; = A pointer to a pointer; = A recursion within a recursion;）vs. 迴圈/迭代（iterate）
- 遞迴程式沒有你想像中的慢
- 分析 clang/llvm 編譯的輸出 (參數 -S -O2)，不難發現兩者轉譯出的 inner loop 的組合語言完全一樣
> 利用 `$ diff -up gcd_itr gcd_rec` 指令，沒有發現其差別，證明程式一樣!![name=曾令燊]

- 遞迴程式設計
> 原來前人在面對數學及計算機(資料結構、演算法)問題時的思維及解法，可從老師抽絲剝繭可見一般...其中的道理是難深但透過老師專業引導下變成可理解的!!
> 利用動畫來視覺化排序(sorting)，真的較文字容易理解!![name=曾令燊]

---

### 你所不知道的 C 語言: 前置處理器應用篇

- 不要小看 preprocessor
> 查了 unicode，分號 ; (UTF-8: 0x3B)、希臘問號 ; (UTF-8: 0xCD 0xBE [cdbe]，Alt +037E) 真的無法用眼睛去識別...|||
> 搜尋查訪還有一些 prank skill, may be suggest changing all ’n’ characters to the Greek Heta ‘$η$’ (H key) or ‘v’ with Ni ‘$ν$’ (N key).
> 很高興 gcc 可以檢查此錯誤，如下

    $ gcc -o prank prank.c 
    prank.c:2:14: warning: treating Unicode character <U+037E> as identifier character rather than as ';'
          symbol [-Wunicode-homoglyph]
        int a = 5;
                 ^
    prank.c:2:14: error: invalid suffix ';' on integer constant
    prank.c:3:2: error: expected ';' at end of declaration
    }
     ^
     ;
    prank.c:3:2: error: expected '}'
    prank.c:1:12: note: to match this '{'
    int main() {
               ^
    1 warning and 3 errors generated.

> [name=曾令燊]

- 開發物件導向程式時，善用 preprocessor 可大幅簡化開發
> 可用 gcc -E -P 觀察輸出，但不知道老師示範的 每行程式有 ''\\'' backslash，是如何產生的?![name=曾令燊]
- 應用: ADT
> 對於 _Generic 泛型使用方式來簡化程式的品味，感覺方便!![name=曾令燊]
>

---

### 你所不知道的 C 語言: goto 和流程控制

- 和想像中不同的 switch-case
- 真的是想像不到，所以運用之妙存乎一心...

- Duff’s Device
- 有關此段的程式碼，我覺得是這樣才對，如下

    void dsend(int count) {
        if (!count) {
            puts("false");
            return;
        }
        int n = (count + 7) / 8;
        switch (count % 8) {
            case 0:
            do {
                puts("case 8");
            case 7:
                puts("case 7");
            case 6:
                puts("case 6");
            case 5:
                puts("case 5");
            case 4:
                puts("case 4");
            case 3:
                puts("case 3");
            case 2:
                puts("case 2");
            case 1:
                puts("case 1");
            } while (--n > 0);
        }
    }

- C程式可善用數學、巧思來coding...

- co-routine 應用
- 有實作 user_thread 的程式，但對於透過 `互動式操作結束此程式` -- 不知是如何執行?!

---

### 你所不知道的 C 語言: linked list 和非連續記憶體操作

- 資料封裝
- 實作 [**`dlist`**](https://github.com/laserswald/dlist)
> 瞭解利用 header file 來定義 linked list 各項功能

---

### 你所不知道的 C 語言：技巧篇

- Implementing smart pointers for C
- 到原作者的 [libcsptr](https://github.com/Snaipe/libcsptr) 探索，發現真的是需要好好的消化一番！ :sweat_smile:

---

### GNU/Linux 開發工具:
- 為什麼該接觸 GNU/Linux 開發工具(研究平台,專業視野,工作機會,實作導向)
- 輕鬆學會 Windows 10 / Ubuntu 雙系統安裝
- 安裝 GNU/Linux -- Lubuntu 18.04 64-bit 版本
> 為什麼「不該」安裝 Linux 在虛擬機器呢？因為在課程對應的練習中，我們會透過 Linux 存取硬體暫存器和各式周邊...倘若透過額外的虛擬機器，不僅上述執行時間不精確，某些硬體暫存器和周邊 (如：PMU) 甚至無法存取。
> 所以說，目前VM虛擬機無法模擬100%硬體，那 Docker 呢?!
> [name=曾令燊]
- 從無到有學習HackMD
- HackMD – LaTeX 語法與示範
> 實際繕打文件即可練習了，另外，喜歡它有支援 L^a^T~e~x排版及數學式(例：歐拉公式 $e^{i\pi}$ + 1 = 0)...
> [name=曾令燊]
- 熟悉 Git 和 GitHub 操作 (已建立帳號 [dvsseed](https://github.com/dvsseed))
> 因為 GitHub 被 微軟M$ 收購了，好像大家大多搬到 [GitLab](https://about.gitlab.com/) 了
> [name=曾令燊]

- 編輯器：Visual Studio Code (已安裝)
- 終端機和 Vim 設定 (已安裝 Plugin)
- vim 命令圖解 (這個圖解畫的好容易看懂!!)
- Makefile 語法和示範 (實際寫才會記得)
- Linux效能分析工具: Perf (將於後續程式中應用之)
- Linux製圖工具: gnuplot (實際操作發現其視覺功能真棒)

---

# 2018q3 第 1 週測驗題

### 測驗 `1`

考慮以下程式碼:

int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3  OP4 y); }
int main() {
    int x = 3, y = 5;
    return my_xor(x, y); 
}

`my_xor` 嘗試不用 XOR 運算子做出等效的 XOR 運算，其中 OP1, OP2, OP3, OP4 都是 operator，請補完實作。

==作答區==

程式碼，如下

$ cat my_xor.c
int my_xor(int x, int y) { return (x | y) & (~ x |  ~ y); }

int main() {
    int x = 3, y = 5;
    return my_xor(x, y);
}
$ gcc -o my_xor my_xor.c -Wall && ./my_xor
$ echo $?
6

我只會用笨方法(先消去 % mod, & address of, * value of, 再手算 bitwise)...如下

$A \oplus B = (A+B)(\overline{A} + \overline{B}) = (A \vee B) \wedge (\neg{A} \vee \neg{B})$
Ref.[XOR--wikipedia](https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96)

  (x | y) = 0111
  (~x | ~y) = 1110
  (x | y) & (~x | ~y) = 0110

            0011
bitwise  OR)0101
            ----
            0111           1100
bitwise AND)1110 <= bit OR)1010
            ----           ----
            0110           1110

---

:::warning
初步完稿 :sweat:
>[time=Mon, Oct 1, 2018 8:25 PM]
:::

###### tags: `sysprog2018` `C` `CLANG` `HackMD`