# 2025q1 Homework1 (lab0)
contributed by < `MuChengChen` >

### Reviewed by `EricccTaiwan`
1. 開發環境不須使用 `shell=`，使用 `shell` 即可。
2. 實作 `queue.c` 的筆記，建議補上各自功能的 commit，方便讀者們搭配著筆記閱讀程式碼。

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:             x86_64
CPU op-mode(s):         32-bit, 64-bit
Address sizes:          39 bits physical, 48 bits virtual
Byte Order:             Little Endian
CPU(s):                   8
On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
Model name:             11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU family:           6
Model:                140
Thread(s) per core:   2
Core(s) per socket:   4
Socket(s):            1
Stepping:             1
CPU(s) scaling MHz:   21%
CPU max MHz:          4200.0000
CPU min MHz:          400.0000
BogoMIPS:             4838.40
Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_
                      tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg f
                      ma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb cat_l2 cdp_l2 
                      ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdt_a avx512f avx512dq rdseed 
                      adx smap avx512ifma clflushopt clwb intel_pt avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves split_lock_detect user_shstk dtherm ida arat pln
                       pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req vnmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopc
                      ntdq rdpid movdiri movdir64b fsrm avx512_vp2intersect md_clear ibt flush_l1d arch_capabilities
Virtualization features:  
Virtualization:         VT-x
Caches (sum of all):      
L1d:                    192 KiB (4 instances)
L1i:                    128 KiB (4 instances)
L2:                     5 MiB (4 instances)
L3:                     8 MiB (1 instance)
NUMA:                     
NUMA node(s):           1
NUMA node0 CPU(s):      0-7
Vulnerabilities:          
Gather data sampling:   Mitigation; Microcode
Itlb multihit:          Not affected
L1tf:                   Not affected
Mds:                    Not affected
Meltdown:               Not affected
Mmio stale data:        Not affected
Reg file data sampling: Not affected
Retbleed:               Not affected
Spec rstack overflow:   Not affected
Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, KVM SW loop
Srbds:                  Not affected
Tsx async abort:        Not affected

## 如何利用 git rebase 更新 fork 的專案
Step 1:增加源專案到 remote 並命名為 "upstream"
`git remote add upstream https://github.com/sysprog21/lab0-c.git`

Step 2:fetch 源專案的所有分支
`git fetch upstream`

Step 3:利用 git rebase 將本地的 master 改寫為源專案的 master
`git rebase upstream/master`

Step 4:將改寫的本地 master 推回自己帳號的專案
`git push origin master --force`

## 佇列操作實作

### `q_new`
[Commit c16d97d](https://github.com/MuChengChen/lab0-c/commit/c16d97dddb5c20d604fda9b94df9ec1a752747a4)
#### 目的
創造空佇列

#### 實作流程
1. 用 `malloc` 取得 list_head 結構體大小的記憶體空間並配置給新的 list_head 結構體指標，若記憶體取得失敗則回傳 NULL
2. 利用 `INIT_LIST_HEAD` 初始化 list_head 結構體指標，將指向的結構體的 next 和 prev 指向結構體本身
3. 回傳 list_head 結構體指標

### `q_free`
[Commit 7e8d20b](https://github.com/MuChengChen/lab0-c/commit/7e8d20b9dc5bc97f4d90ffd0cc5d50a4cf2bf406)
#### 目的
釋放所有佇列使用到的記憶體空間

#### 實作流程
1. 使用 while 迴圈疊代佇列的所有節點
2. 使用巨集 `container_of` 取得節點的位址
3. 使用 `list_del` 斷掉節點與佇列的連結
4. 使用 `q_release_element` 釋放節點使用的記憶體
5. 當釋放完所有節點使用的記憶體後釋放佇列的 head

### `q_insert_head`
[Commit f5a4f90](https://github.com/MuChengChen/lab0-c/commit/f5a4f9061402b8d948901961d14e3b4fc30799f3)
#### 目的
插入新的節點到佇列的第一個節點，且節點中的 value 和 s 字串的內容相同

#### 實作流程
1. 若 head 和 s 為 NULL 回傳 false
2. 用 `malloc` 取得 element_t 結構體大小的記憶體空間並配置給新的 element_t 結構體指標，若記憶體取得失敗則回傳 false
3. 用 `malloc` 取得 s 字串長度 +1 的記憶體空間並配置給 element_t 結構體指標指向的 element_t 結構體中的 value，若記憶體取得失敗則釋放 element_t 結構體中的 value 並回傳 false
4. 使用 `strncpy` 將 s 字串複製到 element_t 結構體中的 value 並在最後加上 '\0'
5. 使用 `list_add` 將新的 element_t 結構體連接到佇列的第一個節點並回傳 true

### `q_insert_tail`
[Commit 5f71875](https://github.com/MuChengChen/lab0-c/commit/5f71875945607990f3e8c7d71a4773c6cc1fd66d)
#### 目的
插入新的節點到佇列的最後一個節點，且節點中的 value 和 s 字串的內容相同

#### 實作流程
1. 若 head 和 s 為 NULL 回傳 false
2. 用 `malloc` 取得 element_t 結構體大小的記憶體空間並配置給新的 element_t 結構體指標，若記憶體取得失敗則回傳 false
3. 用 `malloc` 取得 s 字串長度 +1 的記憶體空間並配置給 element_t 結構體指標指向的 element_t 結構體中的 value，若記憶體取得失敗則釋放 element_t 結構體中的 value 並回傳 false
4. 使用 `strncpy` 將 s 字串複製到 element_t 結構體中的 value 並在最後加上 '\0'
5. 使用 `list_add_tail` 將新的 element_t 結構體連接到佇列的最後一個節點並回傳 true

### `q_remove_head`
[Commit 27d65e9](https://github.com/MuChengChen/lab0-c/commit/27d65e9a734ebbf73485cccede130c10f86d208c)
#### 目的
將佇列的第一個節點移除，且將節點中的 value 字串複製到字串 sp

#### 實作流程
1. 若 head 為 NULL 或佇列為空佇列則回傳 NULL
2. 使用巨集 `container_of` 取得佇列第一個節點的位址
3. 若 sp 不為 NULL 則使用 `strncpy` 複製節點的 value 字串到字串 sp 並在最後加上 '\0'
4. 使用 `list_del` 斷掉節點與佇列的連結並回傳節點的位址

### `q_remove_tail`
[Commit a9b3ded](https://github.com/MuChengChen/lab0-c/commit/a9b3dedb1758a399f4c49697f80a699788b4a9c3)
#### 目的
將佇列的最後一個節點移除，且將節點中的 value 字串複製到字串 sp

#### 實作流程
1. 若 head 為 NULL 或佇列為空佇列則回傳 NULL
2. 使用巨集 `container_of` 取得佇列最後一個節點的位址
3. 若 sp 不為 NULL 則使用 `strncpy` 複製節點的 value 字串到字串 sp 並在最後加上 '\0'
4. 使用 `list_del` 斷掉節點與佇列的連結並回傳節點的位址

### `q_size`
[Commit 275d9b5](https://github.com/MuChengChen/lab0-c/commit/275d9b569ab82cd8b79838fc2b6d39b64738904c)
#### 目的
取得該佇列節點的數量

#### 實作流程
1. 若 head 為 NULL 則回傳 0
2. 利用 `list_for_each` 疊代佇列中所有的節點並加總節點的數量，最後回傳該數量

### `q_delete_mid`
[Commit 03f15f5](https://github.com/MuChengChen/lab0-c/commit/03f15f5ec25b9b9f57baf6d12a32524c59c7da43)
#### 目的
移除並釋放佇列中間的節點

#### 實作流程
1. 若 head 為 NULL 或佇列為空佇列則回傳 false
2. 若佇列只有一個節點則移除並釋放此節點
3. 若佇列不只有一個節點則使用快慢指標的方法找到佇列中間的節點
4. 使用巨集 `container_of` 找到該節點的位址
5. 使用 `list_del` 斷開節點和佇列的連結
6. 釋放節點所使用的記憶體並回傳 true

### `q_delete_dup`
[Commit 0adad8c](https://github.com/MuChengChen/lab0-c/commit/0adad8c378589676492c2c007f6dee9ea3a399d9)
#### 目的
移除並釋放佇列中有相同value的相鄰節點

#### 實作流程
1. 若 head 為 NULL 或佇列為空佇列回傳 false
2. 若只有一個節點回傳 true
3. 配置10個 char 大小的記憶體提供暫時存放節點的 value 的空間
4. 使用 `list_for_each_safe` 疊代佇列的所有節點
5. 若此節點的 value 與前一個節點(暫時存放的節點的 value )相同或是與下一個節點的 value 相同則暫時存放此節點的 value ，斷開此節點與佇列的連結並且釋放此節點使用的記憶體
6. 若此節點的 value 與前一個節點不同或是與下一個節點的 value 不同則將暫時存放節點的空間都存入空字串
7. 最後釋放配置的10個 char 大小的記憶體並回傳 true

### `q_swap`
[Commit d5776aa](https://github.com/MuChengChen/lab0-c/commit/d5776aa0dda7e322c8965b8a7bfb1ba721df2fed)
#### 目的
交換佇列中每兩個節點的位置

#### 實作流程
1. 使用 `list_for_each_safe` 疊代佇列中的每個節點，將 node 和 safe 的位置交換
2. 若全部節點都疊代過了或是只剩下一個節點還沒疊代則停止疊代

### `q_reverse`
[Commit 36d9f0c](https://github.com/MuChengChen/lab0-c/commit/36d9f0c18237c1b20d0bf3f6c76d874f6d939e4f)
#### 目的
倒置佇列中的節點

#### 實作流程
1. 使用 `list_for_each_safe` 疊代佇列中的所有節點
2. 使用 `list_move` 將每個疊代到的節點移動成佇列的第一個節點

### `q_reverseK`
[Commit 00a9b70](https://github.com/MuChengChen/lab0-c/commit/00a9b7026f8b0689ec9beeaad24246dec621da9b)
#### 目的
將佇列中每 k 個節點視為一個要倒置的 list ，若疊代至最後不足 k 個節點則不進行倒置

#### 實作流程
1. 使用 `list_for_each_safe` 疊代佇列中的所有節點
2. 使用 `list_move` 將每個疊代到的節點移動成當前要倒置的 list 的第一個節點
3. 檢查是否已倒置 k 個節點，若已倒置 k 個節點則檢查剩下在佇列中未疊代到的節點數量是否大於或等於 k ，若是則紀錄此 list 的最後一個節點為接下來的 list 中要移動到的位置的前一個節點

### `q_sort`
[Commit b9d003f](https://github.com/MuChengChen/lab0-c/commit/b9d003fc14c2d399e924e1b7702c994d96440f4b)
#### 目的
將佇列中的節點依節點的 value 進行升冪或降冪的排序

#### 實作方法
merge sort

#### 實作流程
1. 將佇列的 head 分離，並初始化 head
2. 將佇列進行 merge sort 排序，以分治法實作
3. 使用快慢指標找到佇列的中點並以此分割成兩個佇列，以此遞迴分割直到每個佇列只剩下一個節點或沒有節點
4. 將分割完的佇列使用 `strcmp` 比較兩個佇列節點之間的 value 並依此排序與合併，直到合併成一個排序好且完整的佇列
5. 將一開始分離的 head 接上佇列

### `q_ascend`
[Commit 873049d](https://github.com/MuChengChen/lab0-c/commit/873049dbca7bb2a7e0cbdce1b7b8a06f51bd9dc1)
#### 目的
將節點中的佇列依升冪的順序排序，若是右邊節點的 value 等於左邊節點的 value 則移除並且釋放此節點

#### 實作流程
1. 使用 `q_sort` 進行升冪排序
2. 使用 `list_for_each_safe` 疊代排序好的佇列中的節點
3. 使用 `strcmp` 比較是否右邊節點的 value 等於左邊節點的 value ，若是則使用 `list_del` 斷掉節點和佇列的連結，最後釋放節點所占用的記憶體
4. 回傳最後佇列剩下的節點總數

### `q_descend`
[Commit 78c3c0e](https://github.com/MuChengChen/lab0-c/commit/78c3c0eaab059d9fb401dc572527b6c4ceefd66e)
#### 目的
將節點中的佇列依降冪的順序排序，若是右邊節點的 value 等於左邊節點的 value 則移除並且釋放此節點

#### 實作流程
1. 使用 `q_sort` 進行降冪排序
2. 使用 `list_for_each_safe` 疊代排序好的佇列中的節點
3. 使用 `strcmp` 比較是否右邊節點的 value 等於左邊節點的 value ，若是則使用 `list_del` 斷掉節點和佇列的連結，最後釋放節點所占用的記憶體
4. 回傳最後佇列剩下的節點總數

### `q_merge`
[Commit bb42a1b](https://github.com/MuChengChen/lab0-c/commit/bb42a1bd785a0aa51a8c83749ab692e955a75d7f)
#### 目的
合併所有佇列並且以升冪或降冪排序

#### 實作流程
1. 若串聯 queue_contex_t 的佇列的 head 為 NULL 或是佇列為空佇列則回傳 0
2. 疊代所有的 queue_contex_t ，每個 queue_contex_t 含有一個佇列
3. 將疊代到的佇列與第一個佇列的 head 分離並且初始化兩個佇列的 head
4. 使用 `strcmp` 比較兩個佇列節點之間的 value 並依此排序與合併，直到合併成一個排序好且完整的佇列
5. 將第一個佇列的 head 接上合併好佇列
6. 若所有佇列皆已合併到第一個佇列則使用 `list_for_each` 疊代此佇列的所有節點以此計算節點的總數，最後回傳佇列中節點的總數

## 新增 shuffle 命令

### Fisher–Yates shuffle 演算法

#### 演示範例 :

#### Step 1

#### Step 2

#### Step 3

#### Step 4

#### Step 5

#### Step 6

### 實作 Fisher–Yates shuffle 演算法
在 `console_init()` 中增加 `shuffle` 命令

static void console_init()
{
    ...
    ADD_COMMAND(descend,
                "Remove every node which has a node with a strictly greater "
                "value anywhere to the right side of it",
                "");
    ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
                "[K]");
+   ADD_COMMAND(shuffle, "Shuffle the queue using the Fisher-Yates algorithm", "");
    ...
}

增加 `do_shuffle` 函式對 queue 實現 Fisher–Yates shuffle 演算法
> commit [34c176](https://reurl.cc/lzDm7E)

### Pearson's chi-squared test

(1)若能符合分配的要求，「觀察值」與「期望值」的比較就不應差太多，卡方值就不會太大而落入拒絕域
(2)卡方檢定是右尾檢定
(3)卡方檢定是屬於無母數分析技巧

#### 檢驗結果

- shuffle [1,2,3,4] 1,000,000 次以測試是否遵守 Uniform distribution

Expectation: 41666

Observation: {'1234': 41583, '1243': 41748, '1324': 41260, '1342': 41425, '1423': 41971, '1432': 41590, '2134': 41414, '2143': 42029, '2314': 41778, '2341': 41921, '2413': 41335, '2431': 41767, '3124': 41561, '3142': 41815, '3214': 41337, '3241': 41656, '3412': 41615, '3421': 41836, '4123': 41881, '4132': 41357, '4213': 41500, '4231': 42002, '4312': 41861, '4321': 41758}

chi square sum: 29.512072193155092


+ $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
+ $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同

由於有24種可能，因此自由度是24-1=23，且 $X^2$ 為 29.512072193155092，27.14<29.512072193155092<32.01，因此由卡方分布表可以得知 P value 落在 0.25~0.1 之間


由於 P value (0.25~0.1)>alpha(0.05)，統計檢定的結果不拒絕虛無假說($H_0$)，也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，從測試結果的圖表來看也大致符合 Uniform distribution

> 在測試 Fisher–Yates shuffle 演算法的腳本中 test_count 並不是真正的測試次數，test_count*4 才是真正的測試次數，因此這部分還需要修改

## 研讀〈Dude, is my code constant time?〉

有參考 [POJU](https://reurl.cc/YYVD9l) 和 [陳麒升](https://reurl.cc/3K7kjM) 的筆記

### lab0-c 程式碼追蹤
首先看到 `constant.h`

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

先將 `DUT_FUNCS` 定義成四個使用 `_` 函式的巨集，再定義 `DUT(x)` 為展開成 `DUT_x` 的巨集，最後定義 `_(x)` 為使用 `DUT(x)` 的巨集，因此 enum 展開為以下形式

enum {
    DUT_insert_head,
    DUT_insert_tail,
    DUT_remove_head,
    DUT_remove_tail,
}

最後取消 `＿` 巨集

再來看到 `fixture.h`

/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

先將 `＿(x)` 定義成資料型態為 `bool` 的 `is_x_const(void)` 函式，再使用 `DUT_FUNCS` 巨集定義 `is_insert_head_const(void)` 、`is_insert_tail_const(void)` 、 `is_remove_head_const(void)` 、 `is_remove_tail_const(void)` ， 最後取消 `＿` 巨集

再來看到 `fixture.c`

#define DUT_FUNC_IMPL(op)                \
    bool is_##op##_const(void)           \
    {                                    \
        return test_const(#op, DUT(op)); \
    }

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _

定義 `DUT_FUNC_IMPL(op)` 為 `is_op_const(void)` 且返回 `test_const(op, DUT(op))`。最後定義 `_(x)` 為使用 `DUT_FUNC_IMPL(x)` 的巨集，使用 `DUT_FUNCS` 執行完 `_(x)` 後取消 `＿` 巨集

再來看到 `test_const` 函式

static bool test_const(char *text, int mode)
{
    bool result = false;

    init_once();

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
             ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }

    for (size_t i = 0; i < DUDECT_TESTS; i++) {
        free(ctxs[i]);
        ctxs[i] = NULL;
    }

    return result;
}

`init_once()` 初始化 `l` 並且檢查 `ctxs` 陣列中每個元素是否都有被初始化
`doit` 函式

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
    uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
    uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));
    int64_t *percentiles = calloc(NUM_PERCENTILES, sizeof(int64_t));

    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data || !percentiles) {
        die();
    }

    prepare_inputs(input_data, classes);

    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    prepare_percentiles(exec_times, percentiles);
    update_statistics(exec_times, classes, percentiles);
    ret &= report();

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);
    free(percentiles);

    return ret;
}

- C23 [7.24.3.2] ***The calloc function***

    void *calloc(size_t nmemb, size_t size);

- Description : The calloc function allocates space for an array of nmemb objects, each of whose size is size. The space is initialized to all bits zero.
- Returns : The calloc function returns either a pointer to the allocated space or a null pointer if the space cannot be allocated or if the product nmemb * size would wraparound size_t.
> `calloc` 會配置 `nmemb` 個元素的陣列，每個元素的大小為 `size`。當無法配置時回傳 `NULL` 指標，成功配置時回傳配置記憶體位置的指標。

再來看到 `die()` 函式

    static void __attribute__((noreturn)) die(void)
    {
        exit(111);
    }

- GCC [6.36] ***Specifying Attributes of Variables***
The keyword `__attribute__` allows you to specify special attributes of variables or structure fields. This keyword is followed by an attribute specification inside double parentheses. Some attributes are currently defined generically for variables. Other attributes are defined for variables on particular target systems. Other attributes are available for functions (see [Function Attributes](https://reurl.cc/Gn5qRZ)) and for types (see [Type Attributes](https://reurl.cc/M36mWv)). Other front ends might define more attributes (see [Extensions to the C++ Language](https://reurl.cc/knMbkr)).
> `__attribute__` 是GCC的一種編譯器指令，後會跟著雙重括號，括號內部會有屬性，而屬性有三種，分別為函式屬性、變數屬性和型別屬性

- Attribute Syntax : noreturn
- A few standard library functions, such as abort and exit, cannot return. GCC knows this automatically. Some programs define their own functions that never return. You can declare them noreturn to tell the compiler this fact. For example

        void fatal () __attribute__ ((noreturn));

              void
              fatal (/* ... */)
              {
                /* ... */ /* Print error message. */ /* ... */
                exit (1);
              }

- The noreturn keyword tells the compiler to assume that fatal cannot return. It can then optimize without regard to what would happen if fatal ever did return. This makes slightly better code. More importantly, it helps avoid spurious warnings of uninitialized variables.
- The noreturn keyword does not affect the exceptional path when that applies: a noreturn-marked function may still return to the caller by throwing an exception or calling longjmp.
- Do not assume that registers saved by the calling function are restored before calling the noreturn function.
- It does not make sense for a noreturn function to have a return type other than void.
> noreturn 是函式屬性，這個屬性是對編譯器說明此函式沒有回傳的特性，或是因為處理 fatal 的情況所以最後 `exit()` 不會回傳。以 `die()` 函式來說，函式內部直接 `exit(111)` 所以確定函式不會回傳，所以加了 noreturn 的屬性。
>
> 標有 noreturn 屬性的函式有可能仍然會以 exception 或 calling longjmp 的方式回傳回 caller ，但不能假設暫存 calling function 的暫存器會被保存下來。
>
> 若 noreturn 屬性的函式不是 `void` 是不合理的。

看到 `prepare_inputs` 函式

    void prepare_inputs(uint8_t *input_data, uint8_t *classes)
    {
        randombytes(input_data, N_MEASURES * CHUNK_SIZE);
        for (size_t i = 0; i < N_MEASURES; i++) {
            classes[i] = randombit();
            if (classes[i] == 0)
                memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
        }

        for (size_t i = 0; i < N_MEASURES; ++i) {
            /* Generate random string */
            randombytes((uint8_t *) random_string[i], 7);
            random_string[i][7] = 0;
        }
    }

其中 `randombytes` 函式

    int randombytes(uint8_t *buf, size_t n)
    {
    #if defined(__linux__) || defined(__GNU__)
    #if defined(USE_GLIBC)
        /* Use getrandom system call */
        return linux_getrandom(buf, n);
    #elif defined(SYS_getrandom)
        /* Use getrandom system call */
        return linux_getrandom(buf, n);
    #else
        /* When we have enough entropy, we can read from /dev/urandom */
        return linux_urandom(buf, n);
    #endif
    #elif defined(BSD)
        return bsd_randombytes(buf, n);
    #else
    #error "randombytes(...) is not supported on this platform"
    #endif
    }

- GCC [4.2.1] ***Ifdef***
The simplest sort of conditional is

    #ifdef MACRO

    controlled text

    #endif /* MACRO */

This block is called a conditional group. controlled text will be included in the output of the preprocessor if and only if MACRO is defined. We say that the conditional succeeds if MACRO is defined, fails if it is not.

The controlled text inside of a conditional can include preprocessing directives. They are executed only if the conditional succeeds. You can nest conditional groups inside other conditional groups, but they must be completely nested. In other words, ‘#endif’ always matches the nearest ‘#ifdef’ (or ‘#ifndef’, or ‘#if’). Also, you cannot start a conditional group in one file and end it in another.

Even if a conditional fails, the controlled text inside it is still run through initial transformations and tokenization. Therefore, it must all be lexically valid C. Normally the only way this matters is that all comments and string literals inside a failing conditional group must still be properly ended.

The comment following the ‘#endif’ is not required, but it is a good practice if there is a lot of controlled text, because it helps people match the ‘#endif’ to the corresponding ‘#ifdef’. Older programs sometimes put MACRO directly after the ‘#endif’ without enclosing it in a comment. This is invalid code according to the C standard. CPP accepts it with a warning. It never affects which ‘#ifndef’ the ‘#endif’ matches.

Sometimes you wish to use some code if a macro is not defined. You can do this by writing ‘#ifndef’ instead of ‘#ifdef’. One common use of ‘#ifndef’ is to include code only the first time a header file is included. See Once-Only Headers.

>依照上面的例子，當 `MACRO` (也就是巨集)被定義 `controlled text` 才會被執行成功， `controlled text` 可以包含前置處理器指示詞，如 `＃define` 、 `#elif` 等等。 Ifdef 也可以組織成巢狀結構，而 `#endif` 會和最近的 `#ifdef` (或 `#ifndef` ,或 `#if` )組合成一個完整的 conditional group ，但不能跨文件。
>
>若條件不成立， `controlled text` 還是會被轉換和分詞，因此 `controlled text` 還是要是合法的 C 語言並且要適當的結束。
>
>`#endif` 不是必要的，但有助於辨別 conditional group 。
>
>若是要使用的程式碼中含有未定義的巨集可以善用 Ifdef 結構。

參考 [Pre-defined C/C++ Compiler Macros](https://github.com/cpredef/predef/tree/master)
`__linux__` 和 `__GNU__` 為 C 和 C++ 編譯器的預定義巨集。預定義巨集可以讓編譯器確認目前的系統是哪種編譯器和作業系統，在寫可攜式軟體時很有用

`USE_GLIBC` 在以下程式碼中被定義

#if (defined(__linux__) || defined(__GNU__)) && defined(__GLIBC__) && \
    ((__GLIBC__ > 2) || (__GLIBC_MINOR__ > 24))
#define USE_GLIBC
#include <sys/random.h>
#endif