# 2018q3 Homework4 (assessment)

### 測驗 `1`

考慮以下求絕對值的程式碼:

#include <stdint.h>
int64_t abs64(int x) {
    if (x < 0) return -x;
    return x;
}

移除分支並善用[二補數](https://en.wikipedia.org/wiki/Two%27s_complement)特性，改寫為下方程式碼:

#include <stdint.h>
int64_t abs64(int64_t x) {
    int64_t y = x A1 (A2 - 1);
    return (x A3 y) - y;
}

請補完，其中 `A1` 和 `A3` 都是 operator。

==作答區==

A1 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` >>

A2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 61
* `(d)` 62
* `(e)` 63
* `(f)` 64

A3 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` >>

首先猜測與 sign bit 有關。但在選項中，`>>` 與 `<<` 均可取得與 sign bit 有關的資訊

:::success
延伸問題:
1. 解釋運作原理，並探討可能的 overflow/underflow 議題;
2. 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 `abs64` 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？)

static uint64_t r = 0xdeadbeef
int64_t rand64() {
    r ^= r >> 12;
    r ^= r << 25;
    r ^= r >> 27;
    return (int64_t) (r * 2685821657736338717);
}

3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關
:::

---

### 測驗 `3`

以下程式碼編譯並執行後，在 x86_64 GNU/Linux 會遇到記憶體存取錯誤:

$ cat ptr.c
int main() {
    int *ptr = 0;
    return *ptr;
}
$ gcc -o ptr ptr.c
$ ./ptr
Segmentation fault: 11

分別考慮以下 4 個程式，探討其行為。
- [ ] `ptr1.c`

int main() { return *((int *) 0); }

- [ ] `ptr2.c`

int main() { return &*((int *) 0); }

- [ ] `ptr3.c`

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

- [ ] `ptr4.c`

#include <stddef.h>
int main() {
    return &*(*main -  (ptrdiff_t) **main);                                                                                                                  
}

==作答區==

K1 = ?
* `(a)` `ptr1.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr1.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr1.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

(a)

規格書中提到：

> 3. An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. 55) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

以及：

> 4. Conversion of a null pointer to another pointer type yields a null pointer of that type.Any two null pointers shall compare equal.

因此可知：

1. 將 0 轉型成任何指標，結果都會得到一個空指標
2. 空指標不可能指向任何 object

故不可能有

K2 = ?
* `(a)` `ptr2.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr2.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr2.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

( c )

根據規格書註解 83)：

> Thus, &*E is equivalent to E (even if E is a null pointer), and &(E1[E2]) to ((E1)+(E2)). It is always true that if E is a function designator or an lvalue that is a valid operand of the unary & operator, *&E is a function designator or an lvalue equal to E. If *P is an lvalue and T is the name of an object pointer type, *(T)P is an lvalue that has a type compatible with that to which T points.

&*((int *) 0)

與

((int *) 0)

是等價的。因此回傳的值是將 0 轉型成一個整數的指標。接下來的問題是把 0 轉型成整數指標之後，再當作整數回傳究竟會發生什麼事？參閱 6.3.2.3 Pointer 一章節，可以找到以下敘述：

> 3. An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. 55) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
> 4. Conversion of a null pointer to another pointer type yields a null pointer of that type.Any two null pointers shall compare equal.
> 5. An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation. ^56)^
> 6. Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

第 3. 說明 0 是空指標常數，將空指標常數轉形成任何指標，將得到一個空指標。

K3 = ?
* `(a)` `ptr3.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr3.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr3.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

實際上使用 gcc 8.2.0-7 編譯會得出：

3.c: In function ‘main’:
3.c:1:21: error: ‘NULL’ undeclared (first use in this function)
 int main(){return &*NULL;}
                     ^~~~
3.c:1:21: note: ‘NULL’ is defined in header ‘<stddef.h>’; did you forget to ‘#include <stddef.h>’?
+#include <stddef.h>
 int main(){return &*NULL;}
                     ^~~~
3.c:1:21: note: each undeclared identifier is reported only once for each function it appears in

若將未引入適當標頭視為語法錯誤，答案應該選 (b) 。但假定有加上適當標頭。由註解 83) 可知 `&*NULL` 與 `NULL` 等價。接著要查證如果回傳的型別跟函數定義的回傳型別不同時，規格書怎麼規範？參考 6.8.6.4 The return statement 的內容：

>If a return statement with an expression is executed, the value of the expression is returned to the caller as the value of the function call expression. If the expression has a type different from the return type of the function in which it appears, the value is converted as if by assignment to an object having the return type of the function. 135)

因此，回傳 `NULL` 的行為，跟把 `NULL` assign 給一個整數的行為一樣。參考 6.5.16.1 Simple assignment 中的內容：

> 2. In simple assignment (=), the value of the right operand is converted to the type of the assignment expression and replaces the value stored in the object designated by the left operand.

這樣的敘述會將 `NULL` 轉型成 `int` 並回傳。所以最後的問題變成 `NULL` 轉型成 `int` ，會是什麼結果？

K4 = ?
* `(a)` `ptr4.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr4.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr4.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

:::success
延伸問題:
1. 參照 C 語言規格書，充分解釋其原理
2. 解析 clang/gcc 編譯器針對上述程式碼的警告訊息
3. 思考 `Segmentation fault` 的訊息是如何顯示出來，請以 GNU/Linux 為例解說。提示: Page fault handler
:::

---