# 2018q3 Homework4 (assessment)
###### tags: `sysprog2018`
Contributed by <[`aben20807`](https://github.com/aben20807)>
## 測驗 `1`
### 題目與解答
+ 利用**二補數**特性完成無分支版本的 `abs()` (取絕對值)
```c
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
```
### 想法
+ 這題其實很直觀，因為**二補數**的提示相當明顯
+ 首先用 `y` 來拿到 `x` 的 sign bit
+ 注意，因為 sign extension，所以 `y` 可能為 `0b000...0 (0)` 或 `0b111...1 (-1)`
+ 接著，若 `y` 為 `0` (`x` 正數)，則 `(x ^ 0) - 0` 還是 `x` 本身
+ 若 `y` 為 `-1` (`x` 負數)，則 `(x ^ -1) - (-1)` 恰好是透過二補數將負轉正
### 延伸
#### 1. overflow
+ 找出 `int64_t` 的最小值
```c
#include <limits.h>
printf("%ld\n", LONG_MIN); // -9223372036854775808
```
+ 接著使用時發生怪異事件：compile warning
```bash
warning: integer constant is so large that it is unsigned
int64_t t = -9223372036854775808;
^~~~~~~~~~~~~~~~~~~
```
+ 原因是因為 `9223372036854775808` 已經超出範圍了，而 `-9223372036854775808` 其實是用 unary operator
+ 正確用法為 `-9223372036854775807 - 1`, `0x8000000000000000 ` 或直接使用 `LONG_MIN`
+ 參考資料：[Hard to C - INT_MIN](http://hardtoc.com/2009/07/16/int-min.html)
+ 與一開始想的情況一樣，最小值是沒辦法取絕對值
+ 最小值取絕對值過程 `(0b1000...0 ^ (-1)) + 1 = 0b0111...1 + 1 = 0b1000...0` 又變回自己
#### 2. pseudo-random number generator (PRNG)
+ 關於 `0xdeadbeef`
+ 在 `dlist` 的作業中也有印象 [[link]](https://github.com/sysprog21/lab0-c/blob/master/harness.c#L19)
+ google 搜尋會推薦 `deadbeef-dead-beef-dead-beef deadbeef` 奇怪的字串，然後就出現 [wiki - Hexspeak](https://en.wikipedia.org/wiki/Hexspeak)
+ 比較神奇的在於只使用 `a` 到 `f` 的字母
+ PRNG (http://xoshiro.di.unimi.it/)
```c
static uint64_t r = 0xdeadbeef
int64_t rand64() {
r ^= r >> 12;
r ^= r << 25;
r ^= r >> 27;
return (int64_t) (r * 2685821657736338717);
}
```
+ 關於程式碼，來源應該是來自 [Sebastiano Vigna](https://en.wikipedia.org/wiki/Sebastiano_Vigna) 的 paper: [An experimental exploration of Marsaglia’s xorshift generators,
scrambled](http://vigna.di.unimi.it/ftp/papers/xorshift.pdf)，在第 20 頁有提及
:::warning
### 問題
對於測試這點我還是無法聯想和 PRNG 有什麼關聯
1. 若要對整個 int64_t 數值範圍測試，那使用迴圈直接從最小跑到最大不是才能保證有測試完整個範圍 (雖然要跑超久)？ 使用 PRNG 反而無法保證有完整測試
3. 如何偵錯？
```c
for (int64_t i = LONG_MIN; i <= LONG_MAX; i++) {
int64_t abs_i = (i < 0) ? -i : i;
if (abs64(i) != abs_i)
printf("error!\n");
}
```
但是，`abs_i` 其實也是錯的，因為 `-1 * LONG_MIN` 就會發生 integer overflow
:::
+ 應用
+ [**BitShares (BTS)**](https://zh.wikipedia.org/wiki/%E6%AF%94%E7%89%B9%E8%82%A1) - [db_witness_schedule](https://github.com/bitshares/bitshares-core/blob/master/libraries/chain/db_witness_schedule.cpp#L122-L126)
+ **ROS** - [Pseudo Random Number Generator Script (xorshift64* )](https://forum.mikrotik.com/viewtopic.php?t=100868)
+ 其他
+ 竟然有歌 ... [Yoshino Yoshikawa - PRNG](https://www.youtube.com/watch?v=oOVINg5rH1s)
## 測驗 `2`
### 題目
+ TOC
+ `test.h` 展開後
+ [x] 1. TCO：可直接在 `first` 中展開
```c
void second_zero (void);
void first_zero (void) {
second_zero ();
}
void second_zero (void) {
}
```
---
+ [x] 2. TCO：可直接在 `first` 中展開
```c
void second_one (int a);
void first_one (int a) {
second_one (0);
}
void second_one (int a) {
}
```
---
+ [x] 3. TCO
```c
void second_zero_one (int a);
void first_zero_one (void) {
second_zero_one (0);
}
void second_zero_one (int a) {
}
```
---
+ [x] 4. TCO
```c
void second_one_zero (void);
void first_one_zero (int a) {
second_one_zero ();
}
void second_one_zero (void) {
}
```
---
+ [ ] 5. TCO
```c
char second_ret_int_char (void);
int first_ret_int_char (void) {
return second_ret_int_char ();
}
char second_ret_int_char (void) {
return 0;
}
```
---
+ [ ] 6. TCO
```c
int second_ret_char_int (void);
char first_ret_char_int (void) {
return second_ret_char_int ();
}
int second_ret_char_int (void) {
return 0;
}
```
---
+ [x] 7. TCO
```c
int second_ret_void_int (void);
void first_ret_void_int (void) {
second_ret_void_int ();
}
int second_ret_void_int (void) {
return 0;
}
```
+ 題目可以用 TOC ？ [[link]](https://godbolt.org/z/TIEQqk)
:::warning
問題：無法解釋以下現象
:::
```c
void g(int *p);
void f(void) {
int x = 3;
g(&x);
}
void g(int *p) {
printf("%d\n", *p);
}
```
+ `gcc 8.2 -O2` result:
```asm
.LC0:
.string "%d\n"
f:
movl $3, %esi
movl $.LC0, %edi
xorl %eax, %eax
jmp printf
g:
movl (%rdi), %esi
xorl %eax, %eax
movl $.LC0, %edi
jmp printf
main:
subq $8, %rsp
movl $3, %esi
movl $.LC0, %edi
xorl %eax, %eax
call printf
xorl %eax, %eax
addq $8, %rsp
ret
```
+ 在 `g()` 中對指標取值再操作也可以 [[link]](https://godbolt.org/z/Hm3PSK)
```c
void g(int *p) {
*p += 1;
printf("%d\n", *p);
}
```
+ 在 `g()` 中印兩次 `*p` 才不行 [[link]](https://godbolt.org/z/L7Y45g)
```c
void g(int *p) {
printf("%d\n", *p);
printf("%d\n", *p);
}
```
+ 或是印出 `__builtin_return_address(0)` 也不行 [[link]](https://godbolt.org/z/ob1hyA)
```c
void f(void) {
printf("%p\n", __builtin_return_address(0));
int x = 3;
g(&x);
}
void g(int *p) {
printf("%p\n", __builtin_return_address(0));
printf("%d\n", *p);
}
```
+ `__builtin_return_address(level)`：
+ `level` 為 `0` 回傳目前函式的位址，為 `1` 回傳 caller 函式的位址
+ 利用回傳值是否相同即可判斷是否為同一個 stack frame
+ [Jserv's blog: GCC 函式追蹤功能](http://blog.linux.org.tw/~jserv/archives/001870.html) 中有介紹除了 `__builtin_return_address` 還有其他選擇
+ 例如用 inline **建議**編譯器 inline
+ 輸出的位址不一樣，代表失敗
```c
#include <stdio.h>
static inline void func();
int main()
{
printf("%p\n", __builtin_return_address(0)); // 0x7fa6ed31eb97
func();
return 0;
}
static inline void func()
{
printf("%p\n", __builtin_return_address(0)); // 0x559cf3ed2670
}
```
+ 強制 gcc 做 inline
+ 輸出位址相同
```c
#include <stdio.h>
static inline void func() __attribute__((always_inline));
int main()
{
printf("%p\n", __builtin_return_address(0)); // 0x7f7b4dbe4b97
func();
return 0;
}
static inline void func()
{
printf("%p\n", __builtin_return_address(0)); // 0x7f7b4dbe4b97
}
```
### 延伸
+ Android 原始程式碼中的 `__builtin_return_address`
+ google 搜尋 `__builtin_return_address site::https://android.googlesource.com/`
## 測驗 `3`
### 題目
```c
int main() {
int *ptr = 0;
return *ptr;
}
```
+ result:
```bash
terminated by signal SIGSEGV (Address boundary error)
```
---
+ `ptr1.c`
```c
int main() { return *((int *) 0); }
```
+ result:
```bash
terminated by signal SIGSEGV (Address boundary error)
```
---
+ `ptr2.c`
```c
int main() { return &*((int *) 0); }
```
+ result:
```bash
warning: return makes integer from pointer without a cast [-Wint-conversion]
int main() { return &*((int *) 0); }
^~~~~~~~~~~~~
```
---
+ `ptr3.c`
```c
#include <stddef.h>
int main() { return &*NULL; }
```
+ result:
```bash
warning: dereferencing ‘void *’ pointer
int main() { return &*NULL; }
^
warning: return makes integer from pointer without a cast [-Wint-conversion]
int main() { return &*NULL; }
^
```
---
+ `ptr4.c`
```c
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
+ result:
```bash
warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*(*main - (ptrdiff_t) **main);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
```
### 想法
+ 首先確認 `NULL` 是什麼
+ 規格書 [N1256](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 找到 §6.3.2.3 下方 (55) 提到
> The macro NULL is defined in <stddef.h>
+ 要怎麼找到這個 `stddef.h` 寫什麼呢，我先去 google 搜尋，但是有很多種版本，突然想到透過 `gcc -E` 來找，發現我的程式會去 include `/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h`，接著找到內容有這一段，合理猜測 `NULL` 是定義成 `((void *)0)`
```c
/* A null pointer constant. */
#if defined (_STDDEF_H) || defined (__need_NULL)
#undef NULL /* in case <stdio.h> has defined it. */
#ifdef __GNUG__
#define NULL __null
#else /* G++ */
#ifndef __cplusplus
#define NULL ((void *)0)
#else /* C++ */
#define NULL 0
#endif /* C++ */
#endif /* G++ */
#endif /* NULL not defined and <stddef.h> or need NULL. */
#undef __need_NULL
```
## 因為自動飲料機而延畢的那一年
Sign in with Wallet
Connect another wallet