2024q1 Homework5 (assessment)

contributed by < randyuncle >

前 4 週的測驗題選出 3 題改進

[進行中] 第一週測驗二 – Timsort 改進

CS:APP 第二章閱讀紀錄

閱讀此章節時也一併參照：
你所不知道的 C 語言: 數值系統篇
 你所不知道的 C 語言: bitwise 操作
 你所不知道的 C 語言: 浮點數運算
 你所不知道的 C 語言: 編譯器和最佳化原理篇

2.1 Information Storage

Data types

C standard 不保證 char 是 signed 資料。
指標會佔有一個資料型態中的所有 word size。
Programmers should strive to make thier programs portable across different machines and compilers.
- One aspect: Making the program intensitive to the exact sizes of the different data types.
  - In C: The data types defined in <stdint.h> – int32_t, int64_t, uint32_t, uint64_t, etc..
- The C standards establish only the lower bounds on numeric data types, leaving the upper bounds unset, except with the fixed sizes.
  - The hidden word size dependencies in the transition from 32-bit to 64-bit machines.

Addressing and Byte Ordering

位元組順序（Byte Ordering）在某些場合和應用中是一個必須考量到的事:
- 網路應用：不同位元組排列法（endian）的機器之間互相傳輸資料的場合。
- 查看代表整數的位元序列時。
- 當需要編寫非常規資料型態系統的程式時（對應到 C 語言中，為 union、cast 所定義的結構體）。

Shist Operations in C

C 語言對 shift 操作的是由左到右的方向做讀取及處理。
在 C 語言中，+ 和 - 運算子的優先度比 shift 要高。
在右移中，可分成 logical shift 和 arithmetic shift 兩種類型的移位。
- 通常來說，logical shift 會應用在 signed numbers；arithmetic shift 則應用在 unsigned numbers。
  - logical shift: 左測補 0。
  - arithmetic shift: 左側補原二位數之 MST 的值（即為 signed bit）
- C 語言未準確定義對 signed numbers 的右移應當適用哪種規則。
[Undefined Behavior] Shift by k, for large values of k:
- 在 C 語言規範中，沒有定義當左移的位元數比被移位的位元數更多時的行為。
- 通常在多種機器來說，應對這個情境的解決方法是，對移位的位元數做取餘數的操作。

2.2 Integer Representation

unsigned encoding

每個二位數和無號數是一對一對應的。

Two's-complement encoding ( signed encoding )

每個二位數和二補數的有號數是一對一對應的。
令二補數有號數的最大值為
$T M a x_{w}$ 、最小值為
$T M i n_{w}$ ，則其之間有以下關係：

$| T M a x_{w} | = | T M i n_{w} | + 1$ 也側面表示
$T M i n_{w}$ 在二補數有號數的表示中沒有其對應的正整數。
在 C23 標準之前，C 語言之有號數沒有完全採納二補數表示法。

ISO/IEC 9899:2023 6.2.6.2 Integer types
6. NOTE2 The sign representation defined in this document is called two’s complement. Previous revisions of this document additionally allowed other sign representations.

Conversions between signed and unsigned

在相同位元數轉換的前提下，C 語言基本上是以原數值本身的二進位表示直接做轉換。
- 假設有以下的 C 程式節錄：
```
short int v = -12345;
unsigned short int uv = v;
```
  short int 是一個 16 位元的整數資料型態。
  變數
  $v$ 的二進位值為
  $1100111111000111$ ，為帶有 signed bit 的二補數表示法。在 C 程式中，在做有號數和無號數的內部赴值並不會改變其原本的位元表示。也就是說，變數
  $u v$ 的二位數也會是
  $1100111111000111$ ，只是其 MST 的位元並非代表 signed bit，使其最終的變數內容變為
  $u v = 53191$ 。
繼上一點，若假設在
$w$ 二進位值，且 MST 位元為 1（也就是其在 signed 整數值為負值）的情況下，無號數的值為
$U_{w}$ ，二補數有號數的值為
$T_{w}$ ，則有以下的關係存在
$| U_{w} | + | T_{w} | = 2^{w} 。$

signed versus unsigned

C 語言支援 signed 和 unsigned 之間的顯性（explicit）及隱性（implicity）轉換。
在數值的最後加上 U 或 u 字元，即代表該數為 unsigned 整數值。
- e.g. 12345U、0x0608u。
當有同時涵蓋 signed 以及 unsigned 數值的操作時，C 會隱性的將所有的數值以 unsigned 數值，也就是都以非負整數的角度，去處理該操作。
- e.g. 假設有一布林不等式 -2147483647 - 1U < -2147483647 在 32 位元表示的程式中，因有 1U 在不等式裡的關係，所以 C 以 unsigned 的角度去處理不等式中的所有數值，最後會回傳 True。

C 語言中的
$T M i n$

在 C 標頭檔 limits.h 中，可以發現到 C 的有號數整數值的上下限是這樣定義的：

/* Minimum and maximum values a ‘signed int’ can hold. */ 
#define INT_MAX 2147483647 
#define INT_MIN (-INT_MAX - 1)

在對 INT_MIN 的巨集定義中，並沒有直接將其定義為 -2147483648，而是 (-INT_MAX - 1)。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

在以 32 位元為主的程式中，如果直接定義 INT_MIN 為 -2147483648，因為在 C 語言編譯器中，碰到 -X 的場合，會先找符合 X 的資料型態，再將其 negative，所以對 -2147483648 的處裡就會先尋找符合 2147483648 的資料型態，再將其 negative。因此，在編譯階段，編譯器會先發現到 2147483648 比常規的 int 來得大，之後就找到 long，但 long 是 32 位元的 signed，所以再接著找到可以容納的目標資料型態 unsigned。又因為 -2147483648 和 2147483648 有相同的二進位表示，所以最終就停止在 unsigned。

不過以上是 C90 的情況，如果在 C99 編譯的場合，編譯器最後找到的目標資料型態為 64 位元的 signed 資料型態 long long。

另一方面，以 64 位元為主的程式中，則會因為其是 64 位元表示，所以它的 long 會是 64 位元的大小。因此，在尋找符合 -2147483648 的資料型態地任務中，會找到 long 資料型態就停止。

換個角度來說，如果編譯 INT_MIN 為十六進位數 0x80000000 的話，那在以 32 位元或 64 位元的程式中，不管是 C90 或 C99 標準，都會找到 unsigned 後，就停止搜尋符合的資料型態。

那這會有什麼問題呢？從以上的描述，可以發現到不同的 C 語言標準，以及不同位元（N-bit）程式，甚至是不同的進位法，會因為 C 語言對數值做隱性轉換的原因，都對數值 -2147483648 有不同的資料型態定義，使得 -2147483648 成為陷阱表示法。在這種場合，該程式只能在特定的機器上運行，而不能在所有的機器普遍運作，產生嚴重的錯誤。

在 CS:APP 作者提供的公開文件中，有舉了以下程式碼為例子：

int dpos32 = (-2147483648 > 0); 
int hpos32 = (0x80000000 > 0);

若將此程式編譯執行後，根據不同的編譯器版本，以及 word size，會得到 dpos 的結果為 0 或 1，表示十進位的數值也可能為 0 或 1；另一方面，十六進位數 hpos 的執行結果，不管編譯器版本和 word size 為哪個，皆穩定為 1。此實驗也突出了，若要定義有號二進位數的常數數值，需要格外的警惕該數值可能造成的影響。

signed 和 unsigned 的混用可能會造成整數溢位

在 2002 年 FreeBSD 裡一個名叫 getpeername() 的 library function，被回報其實作存在安全性問題。其原實作簡化為以下：

#define KSIZE 1024
char kbuf[KSIZE];

int copy_from_kernel(void *user_dest, int maxlen) {
    int len = KSIZE < maxlen ? KSIZE : maxlen;
    memcpy(user_dest, kbuf, len);
    return len;
}

其中 memcpy() 函式的原始宣告為以下：

void *memcpy(void *dest, void *src, size_t n);

乍看之下可能沒感覺到有什麼問題，但如果有工程師惡意的將負數值做為 maxlen 引數代入進 copy_from_kernel()，會發生什麼事呢？

我們假設 maxlen 的數值為負，那在對 int len 的賦值中，會因為 maxlen < KSIZE 的關係，使得 maxlen 的數值賦予給變數 len，變數 len 成為一個負數值。

接下來，變數 len 會被帶入進函式 memcpy() 的引數 n 中。但是，引數 n 的資料型態為 size_t，是一個 unsigned 類型的資料型態，因此原來的變數 len 會被 C 語言從 signed 隱性轉換為 unsigned，且不會改變其原本的位元表示。

此時，一個很嚴重的問題就出現了：假設此程式運行在 32 位元的裝置，因為變數 len 是負數的關係，所以其位元表示中的 sign bit 為 1。若將其隱性轉換為 unsigned 表示的話，則其數值至少為 2³¹，遠遠超過此程式定義的上限 KSIZE，使得 memcpy() 函式會以該規模的數值，將核心記憶體複製到 user's buffer 中，其中就會複製到只有核心才有權限讀取的記憶體空間，形成資安風險。

Expanding and Truncating the Bit Representation of a Number

將小的資料型態轉換為較大的資型型態的操作必須永遠成立。
對於一個數值的位元表示的擴增（Expanding）來說：
- 若該數值是 unsigned，對該數值的 MST 做 zero extension。
- 若為 signed，則對擴增的位元補為原本數值之 MST 的位元表示，此操作稱為 sign extension。
對於一個數值的位元表示的縮減（Truncating）來說：
- 不管其為 unsigned 或 signed 表示，位元表示的縮減都會直接從 MST 削除多餘的位元，且剩餘的位元表示不會做任何的更動。
在做資料型態的轉換時，若該操作同時涉及到資料型態大小和無號數有號數轉換的場合，在 C 語言中，會先轉換資料型態大小，再做無號數有號數之間的轉換。
- e.g. 假如有以下程式碼：
```
short sx = -12345;
unsigned uy = sx;
```
  則在 C 語言中，會先把 short sx 轉換成 int sx，接著再由 int sx 轉成 unsigned int sx，最後把結果 assigned 給 unsigned uy。

Advice on Singed versus Unsigned

C 語言中對 signed 和 unsigned 之間的隱性類型轉換會使得一些非直覺的行為出現，導致程式出現難以察覺的 bug。
有一種避免出現類似的 bug 的方法是直接不採用 unsigned 數值，例如說 Java 就是如此。
但 unsigned 有不少的好處，例如說：
- 在系統程式中，可以使用 unsigned 型態紀錄 addresses。
- 包裝 words 為非數值意義的位元表示。
- 實作取餘數和乘法運算的數學模組。

2.3 Interger Arithmetic ( To be modified )

Unsigned Addition

以兩個非負 w 位元的整數做加法，會需要 w + 1 個位元做表示。
以上的這個情況，會導致整數溢位的發生。在 C 語言程式裡，整數溢位不會被回報為錯誤，且計算的結果會從 w + 1 個位元被縮減回 w 個位元。
- 偵測溢位的方式：令有兩非負 w 位元的整數
  $x$ 和
  $y$ ，兩數值之加法結果為
  $s = x + y$ ，且
  $s$ 在被 assigned 後必為 w 位元。若
  $s < x$ 或
  $s < y$ ，則表示此非負整數的加法出現了溢位。
- 以程式實作的角度，可以用 XOR 檢查是否出現溢位。
```
unsigned int a, b, x;
x = a + b;
if ((x ^ a) >= 0 || (x ^ b) >= 0)
...
```

Two's-Complement Addition

和 unsigned 加法相似，以兩個 w 位元的整數做加法，會需要 w + 1 個位元做表示。
假設有兩個 w 位元的整數
$x$ 和
$y$ ，兩數值之加法結果為
$s = x + y$ ，且 s 在被 assigned 後必為 w 位元。則二補數加法的溢位會有以下情況：
- $x > 0$ 和
  $y > 0$ ，且
  $s <= 0$ ：此二補數加法結果是 positive overflow。
- $x < 0$ 和
  $y < 0$ ，且
  $s >= 0$ ：此二補數加法結果是 negative overflow。
簡單來說，若兩數相加後的正負號和原本兩者都不同，即代表有整數溢位的發生。

阿貝爾群（Abelian group）和群的特性

考慮整數集（

Z

）的情況，若要表示整數加法為群，則兩整數（

x

、

y

）的加法有以下的特性：

封閉性：若
$x$ 和
$y$ 屬於
$Z$ ，則
$x + y$ 也屬於
$Z$ 。
結合性：排序固定之三整數之合和其加法執行順序沒有關係。
$(x + y) + z = x + (y + z)$
存在一整數 0，使得任何整數與其相加皆不變。
$x + 0 = 0 + x = x$
任意加法都可「回復」，也就是說每一整數皆存在逆元。
$x + (- x) = (- x) + x = 0$

綜合以上，我們可以稱整數加法為群。

若我們增加以下的條件：

交換性：兩整數之和與其計算位置無關。
$x + y = y + x$

則我們可以稱整數的加法為－阿貝爾群。

若整數的加法擁有群的特性，則可額外取得以下的特性：

每個整數元素是唯一的。
每個整數逆元也是唯一的；亦即，對於整數
$x$ 存在一個
$y = - x$ ，使得
$x + y = 0$ 。

其中，第二小點的特性，若以整數加法的角度來看，代表說每一組的整數加法，都有一組唯一對應的整數減法。

Unsigned and Two's-Complement Multiplication

以兩個 w 位元的整數做乘法，會需要 2w 個位元做表示，並在賦予回指定變數時會被縮減回 w 位元。

Multiplication can overflow without any notice being given to the program

在 2002 年，Sun Microsystem 裡的 External data representation (XDR) library 被回報一件和乘法有關的整數溢位案例。

CA-2002-25
The xdr_array() function in the XDR library provided by Sun Microsystems contains an integer overflow that can lead to improperly sized dynamic memory allocation. Subsequent problems like buffer overflows may result, depending on how and where the vulnerable xdr_array() function is used.

以下是與當時實作相似的程式碼：

void *copy_elements(void *ele_src[], int ele_cnt, size_t ele_size) {
    void *result = malloc(ele_cnt * ele_size);
    if (result==NULL) return NULL;
    void *next = result;
    for (int i = 0; i < ele_cnt; i++) {
        memcpy(next, ele_src[i], ele_size);
        next += ele_size;
    }
    return result;
}

在這支程式中需要注意的是關於 void *result 指標變數的宣告：

void *result = malloc(ele_cnt * ele_size);

假設這支程式運行在 32 位元的裝置中，如果有工程師將 ele_cnt = 2²⁰ +1，以及 ele_size = 2¹² 帶入此條宣告，將會使得只有 4096 bytes 的記憶體被 allocated，而非 4,294,971,392 bytes 的記憶體，導致程式在運行到 for 迴圈時，會因為 void *result buffer 本身無法容納所有的 void *ele_src[] 二維陣列的資料，出現損毀其他裝置中的資料結構、裝置崩潰、或以下非預期的行為：

CA-2002-25
Exploiting this vulnerability will lead to denial of service, execution of arbitrary code, or the disclosure of sensitive information.
Specific impacts reported include the ability to execute arbitrary code with root privileges (by exploiting dmispd, rpc.cmsd, or kadmind, for example). In addition, intruders who exploit the XDR overflow in MIT KRB5 kadmind may be able to gain control of a Key Distribution Center (KDC) and improperly authenticate to other services within a trusted Kerberos realm.

所以，在使用記憶體分配函式（e.g. malloc, calloc, etc.）時，必須注意帶入進引數的數值是否會出現溢位，且不要直接以四則運算做為引數帶入。

Multiplying by Constants

在本書的 2.1 節中，有介紹 C 語言支援 shift operation。通常來說，在 C 語言中，如果直接使用乘法（*）和除法（/），則會需要使用非常多的 clock cycle 去完成該操作，而若用 bit-level operations、addition、substraction、shifting，則會只要一個 clock cycle。因此，如果想要加速程式的運作，將乘除的程式撰寫思維轉為位元操作是最合適的選擇。

整數的乘法，可以分兩種情況探討：

被乘數剛好是 2 的冪（power of two）：直接對該數值使用 left shift。
被乘數不是 2 的冪（power of two）：根據被乘數的位元表示分批使用 left shift，並將個別結果相加。
- e.g. 假設要做以下的乘法運算：x * 14。在此例子中，被乘數的二位數表示為 14₁₀ = 1110₂，得知其可拆解為 14 = 2³ + 2² + 2¹。因此，我們可以將 x * 14 以 (x << 3) + (x << 2) + (x << 1) 做為代替。

使用 2 的冪的移位乘法依舊會產生 overflow，但就如同直接使用 * operator 一樣，C 程式會直接將多餘的位元做縮回操作。

Dividing by Power of 2

整數的除法，

2.4 Floating point ( To be modified )

IEEE Floating-Point Representation

Rounding

Floating-Point Operations

Floating-Point in C

文章閱讀及課程心得

課程教材研讀

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

專題的進度

TODO:

建立排序演算法的 Linux kernel module 版本。

建立測試程式的 Linux kernel module 版本。

建立以數值比較為主的環境測試排序演算法，以呼應在 kernel module 測試。

了解亂數產生器並應用進測試中 (lab0-c, integration)。

了解統計分析方法 (lab0-c)。

為何 C 語言的 int 是 signed?
signed vs. unsigned
int do_something()
strcmp - https://man7.org/linux/man-pages/man3/strcmp.3.html 為何有 3 種回傳值？]
equal or not => 只有 2 種
unsigned 的風險？

一個有號數意外結果的例子。

int n = 10; 
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
    printf("i: 0x%x\n",i);

這個例子會造成無窮迴圈，因為 sizeof 會回傳值是 unsigned int 型態，i 變數也會被轉換為 unsigned 的形式，無號數 0 再減 1 就會變為 0xFFFFFFFF 而產生無窮迴圈。

(integer promotion, C99)

TODO: 第一週測驗二: Timsort 改進

測試程式: 涵蓋最佳和最差: https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ
改進的策略？
標的: circular doubly-linked list => 問：circular doubly-linked list 相較於 singly-linked linked list 有何優勢？
準備 Linux kernel module 來測試/驗證 => LKM 可避免 preemption 和 interrupt，且可有較高的時間精度 (high-resolutin timer，可精準到 us, ktime)
貢獻？提出針對 Linux 核心 list_sort.c 的改進 (show me the code!)