# 2018q3 Homework4 (assessment)
###### tags: `C語言`
contributed by < `asd757817` >
## [第一題](https://hackmd.io/s/HyyxpJE5X#2018q3-%E7%AC%AC-4-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C-%E4%B8%8A)
利用二補數的特性完成取絕對值，不需要透過 if 判斷
```C
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x A1 (A2 - 1);
return (x A3 y) - y;
}
```
- 二補數轉換：將數字所有位元反向運算後再+1
- 絕對值計算：
sign bit 為 0 → 運算後 bit 不變
sign bit 為 1 → 所有 bit 做反向運算 +1
因為不使用 if 判斷正負，所以必須藉由 sing bit 達成正負的判斷，推測 y 所進行的運算為取得 sign bit，經由 bit 右移最大位數 -1 可以取得，傳入的 x 為 64 bit，故 A1： >> 、 A2: 64
當 x >= 0 → y = 0 ； x < 0 → y = -1
思考```reutrn (x A3 y) - y```，當 x < 0 ：
- y = -1
- -1 的二進位表示為 0xffffffff
- x 與 y 進行運算後等同於反向運算
- x 以 -1 帶入檢驗：0xffffffff A3 0xffffffff +1 會等於 0x01 → A3： ^ ( XOR )
x 以 1 帶入檢查：
- y = 0
- (1 ^ 0) - 0 = 1 也符合條件
ANS：
A1：>>
A2：64
A3：^
C99 6.5.7 (5)
> The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / $2^{E2}$. ==If E1 has a signed type and a negative value, the resulting value is implementation-defined.==
有號負數進行 right-shift 的結果會根據工具不同而有不同的結果，這個題目是預期 right-shift 時會補 sign bit 的數值(正數補 0、負數補 1)來實作，以 gcc 編譯執行的結果是相符的，但在某些機器上執行可能因為補的數值不同而造成錯誤。
### overflow/underflow
因為使用的是二補數，在 n bits 系統的數值範圍介於 $2^{n-1}-1$ ~ $- 2^{n-1}$，負數會比正數多一個，當傳入最小負數時就會出現 overflow。
## [第二題](https://hackmd.io/s/Syl6me49Q#2018q3-%E7%AC%AC-4-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C-%E4%B8%AD)
tail call： 一個函式最後執行的動作是呼叫另一個函式
一般函式執行中的 stack 變化：
```graphviz
digraph structs{
stack1 [label="{<f0> Caller Frame|<f1> Previous Frame}" shape=record];
stack2 [label="{<f0> Called Frame|<f1> Caller Frame|<f2> Previous Frame}" shape=record]
stack3 [label="{<f0> Caller Frame|<f1> Previous Frame}" shape=record];
stack4 [label="{<f0> Previous Frame}" shape=record];
stack1 -> stack2 -> stack3 -> stack4
}
```
當函式呼叫另一個函式時會將原本函式的資料、return address 保存在 stack 中，並在 stack 規劃出下一個函式所使用的範圍，在部分 tail call 的例子中這樣其實是浪費記憶體空間的，以下列程式碼為例：
```C
int f(){
int a = 1;
int b = 2;
return g(a+b);
}
```
f() 函式實際上等同於 return g(2)，呼叫 f() 的結果等於直接呼叫 g(2)，但是在未最佳化的運作中，執行 g(2) 時 f() 的內容 a、b 還會被保存在 stack 裡，但實際上這些資訊是不需要被保存的，因此 TCO 的效果就是不保留 f() 用不到的資訊，只保留 g(3) 所需要的部分。
[reference](http://www.ruanyifeng.com/blog/2015/04/tail-call.html)
簡易測試 TCO：
1.c
```C
#include "stdio.h"
int f();
int g(int);
int main(){
int x = f();
printf("%d\n", x);
return 0;
}
int f(){
int a=1;
int b=2;
return g(a+b);
}
int g(int x){
return x;
}
```
比較不做最佳化與 O1 最佳化的差異
```shell
gcc -o 1.s -S 1.c
gcc -o 1_O1.s -O1 -S 1.c
```
不做最佳化：
```
main:
.LFB2:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $16, %rsp
movl $0, %eax
call f
movl %eax, -4(%rbp)
movl -4(%rbp), %eax
movl %eax, %esi
movl $.LC0, %edi
movl $0, %eax
call printf
movl $0, %eax
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
f:
.LFB3:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $16, %rsp
movl $1, -8(%rbp)
movl $2, -4(%rbp)
movl -8(%rbp), %edx
movl -4(%rbp), %eax
addl %edx, %eax
movl %eax, %edi
call g
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
g:
.LFB4:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl %edi, -4(%rbp)
movl -4(%rbp), %eax
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE4:
.size g, .-g
.ident "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609"
.section .note.GNU-stack,"",@progbits
```
O1 最佳化：
```
main:
.LFB38:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
movl $3, %edx
movl $.LC0, %esi
movl $1, %edi
movl $0, %eax
call __printf_chk
movl $0, %eax
addq $8, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
f:
.LFB39:
.cfi_startproc
movl $3, %eax
ret
.cfi_endproc
.LFE39:
.size f, .-f
.globl g
.type g, @function
g:
.LFB40:
.cfi_startproc
movl %edi, %eax
ret
.cfi_endproc
.LFE40:
.size g, .-g
.ident "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609"
.section .note.GNU-stack,"",@progbits
```
不做最佳化時 main 函式內呼叫 f、f 函式內呼叫 g，最佳化以後 f 函式內就沒有呼叫 g 了
---
修改程式碼
```C
#include "stdio.h"
int f();
int g();
int * g_ptr;
int main(){
int x = f();
printf("%d\n", x);
return 0;
}
int f(){
int a=1;
g_ptr = &a;
return g();
}
int g(){
return 10;
}
```
不做最佳化
```shell
main:
.LFB2:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $16, %rsp
movl $0, %eax
call f
movl %eax, -4(%rbp)
movl -4(%rbp), %eax
movl %eax, %esi
movl $.LC0, %edi
movl $0, %eax
call printf
movl $0, %eax
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE2:
.size main, .-main
.globl f
.type f, @function
f:
.LFB3:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $16, %rsp
movq %fs:40, %rax
movq %rax, -8(%rbp)
xorl %eax, %eax
movl $1, -12(%rbp)
leaq -12(%rbp), %rax
movq %rax, g_ptr(%rip)
movl $0, %eax
call g
movq -8(%rbp), %rdx
xorq %fs:40, %rdx
je .L5
call __stack_chk_fail
.L5:
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
g:
.LFB4:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl $10, %eax
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE4:
.size g, .-g
.ident "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609"
.section .note.GNU-stack,"",@progbits
```
O1 最佳化
```
main:
.LFB38:
.cfi_startproc
subq $24, %rsp
.cfi_def_cfa_offset 32
movq %fs:40, %rax
movq %rax, 8(%rsp)
xorl %eax, %eax
leaq 4(%rsp), %rax
movq %rax, g_ptr(%rip)
movl $10, %edx
movl $.LC0, %esi
movl $1, %edi
movl $0, %eax
call __printf_chk
movq 8(%rsp), %rcx
xorq %fs:40, %rcx
je .L2
call __stack_chk_fail
.L2:
movl $0, %eax
addq $24, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE38:
.size main, .-main
.globl f
.type f, @function
f:
.LFB39:
.cfi_startproc
subq $24, %rsp
.cfi_def_cfa_offset 32
movq %fs:40, %rax
movq %rax, 8(%rsp)
xorl %eax, %eax
leaq 4(%rsp), %rax
movq %rax, g_ptr(%rip)
movq 8(%rsp), %rdx
xorq %fs:40, %rdx
je .L5
call __stack_chk_fail
.L5:
movl $10, %eax
addq $24, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE39:
.size f, .-f
.globl g
.type g, @function
g:
.LFB40:
.cfi_startproc
movl $10, %eax
ret
.cfi_endproc
.LFE40:
.size g, .-g
.comm g_ptr,8,8
.ident "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609"
.section .note.GNU-stack,"",@progbits
```
觀察 f 函式實際的行為，在這次測驗中因為 g 函式內沒有使用到 g_ptr，因此可以進行 TCO 且不影響程式。
---
再次修改程式
```C
#include "stdio.h"
int f();
int g();
int * g_ptr;
int main(){
int x = f();
printf("%d\n", x);
return 0;
}
int f(){
int a=1;
g_ptr = &a;
return g();
}
int g(){
int b = 20 + *g_ptr;
return b;
}
```
不做最佳化的情況與先前類似，只探討 O1 最佳化後 f 函式的行為：
```shell
f:
.LFB39:
.cfi_startproc
subq $24, %rsp
.cfi_def_cfa_offset 32
movq %fs:40, %rax
movq %rax, 8(%rsp)
xorl %eax, %eax
movl $1, 4(%rsp)
leaq 4(%rsp), %rax
movq %rax, g_ptr(%rip)
movl $0, %eax
call g
movq 8(%rsp), %rdx
xorq %fs:40, %rdx
je .L3
call __stack_chk_fail
.L3:
addq $24, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE39:
.size f, .-f
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d\n"
.text
.globl main
.type main, @function
```
可發現這個例子中 f 函式呼叫了 g 函式，因為回傳值 b 參照了 g_ptr 所指向的內容，而 g_ptr 指向的目標在 f 函式內，這時候 f 函式的 stack frame 必須保留，因此不能進行 TCO。
---
繼續改
```C
#include "stdio.h"
int f();
int g();
int * g_ptr;
int main(){
int x = f();
printf("%d\n", x);
return 0;
}
int f(){
int a=1;
g_ptr = &a;
return g();
}
int g(){
int a = 1 + *g_ptr;
int b = 20;
return b;
}
```
```shell
f:
.LFB39:
.cfi_startproc
subq $24, %rsp
.cfi_def_cfa_offset 32
movq %fs:40, %rax
movq %rax, 8(%rsp)
xorl %eax, %eax
leaq 4(%rsp), %rax
movq %rax, g_ptr(%rip)
movq 8(%rsp), %rdx
xorq %fs:40, %rdx
je .L5
call __stack_chk_fail
.L5:
movl $20, %eax
addq $24, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE39:
.size f, .-f
.globl g
.type g, @function
```
g 函式一樣有參照 g_ptr 指向的目標，但是因為**回傳值的運算與 g_ptr**無關，所以還是可以進行 TCO。
題目：
```C=
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* Can the compiler perform TCO here? */
g();
}
```
思考程式註解，在第 8 行能否施加 TCO 呢？選出最適合的解釋。
ANS：
題目所給的三個案答案都有錯誤
* `(a)` 編譯器不可能施加 TCO
* `(b)` 編譯器一定可施加 TCO
* `(c)` 只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會
從測試結果可知 g 即使對 `global_var` 取值，但回傳值的計算與之無關時還是可以進行 TCO，因此進行 TCO 的判斷不是函式有沒有對 `global_var` 取值，而是回傳值的計算是否需要對 `global_var` 取值，若回傳值運算與 `global_var` 無關就可以進行 TCO。
## [第三題](https://hackmd.io/s/By7Lwz4qm#2018q3-%E7%AC%AC-4-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C-%E4%B8%8B)
**ptr1.c**
```C
int main() { return *((int *) 0); }
```
0 在程式中的意思為 NULL，經過 ( int \*) 強制轉型後變為 NULL pointer，對 NULL pointer 取值會出現 Segmentation fault。
實際執行：
```C
gcc -o 1 1.c && ./1
[1] 7248 segmentation fault (core dumped) ./1
```
**ptr2.c**
```C
int main() { return &*((int *) 0); }
```
根據 C99 規格書 6.5.3.2 註記 87
> 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.
return 可簡化為 return (int \*) 0 ，0 強制轉型成 pointer to integer 此時是 NULL pointer，因為回傳型態為 int 所以會直接將指標視為 int 回傳，這在編譯時會出現警告，NULL pointer 的數值表示是 0，所以執行的結果相當於 return 0。
實際執行：
```C
gcc -o 1 1.c && ./1
1.c: In function ‘main’:
1.c:43:9: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*((int *) 0);
```
**ptr3.c**
```C
#include <stddef.h>
int main() { return &*NULL; }
```
對指標進行 &* 運算等於指標本身，因此程式可以簡化成 return NULL，NULL 等型態是指標，實際上的數值是 0，因為回傳型態是 int，會直接將指標內容作為 int 回傳，因此程式等同於 retrun 0。
實際執行：
```C
gcc -o 1 1.c && ./1
1.c: In function ‘main’:
1.c:44:10: warning: dereferencing ‘void *’ pointer
return &*NULL;
^
1.c:44:9: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*NULL;
```
==**注意**==：&* 一起運算時才可傳入 NULL pointer
若將程式改為 return \*NULL、return &NULL
```shell
# return *NULL
gcc -o 1 1.c && ./1
1.c: In function ‘main’:
1.c:44:9: warning: dereferencing ‘void *’ pointer
return *NULL;
^
1.c:44:9: error: void value not ignored as it ought to be
# return &NULL
gcc -o 1 1.c && ./1
1.c: In function ‘main’:
1.c:44:9: error: lvalue required as unary ‘&’ operand
return &NULL;
^
```
- 對 NULL pointer 取值是一個 Undefined Behavior，可編譯執行，但結果無法預測
- 對 NULL pointer 做 & 運算違反了 & 運算的限制
* C99 6.5.3.2 Address and indirection operators
> Constraints
The operand of the unary & operator shall be either a function designator, the result of a[] or unary * operator, or an lvalue that designates an object that is not a bit-field and is not declared with the register storage-class specifier.
**ptr4.c**
```C
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
&* 的運算可直接省略，直接觀察 (\*main - (ptrdiff_t) \*\*main)
* 在 C99 規格書中提到兩個指標相減：
> When two pointers are subtracted, both shall point to elements of the same array object,or one past the last element of the array object; the result is the difference of the subscripts of the two array elements.The size of the result is implementation-defined,and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header.
* 對 ptrdiff_t 型態的描述：
> which is the signed integer type of the result of subtracting two pointers
兩指標間的距離會因為型態的不同而有所差異，如兩個 int 指標相差一個單位，在記憶體中差了 4 bytes；但 char 指標差一個單位卻是差 1 byte，ptrdiff_t 型態解決了這一個問題，他代表的結果就是該指標相差的單位數量。
以程式檢驗 ptrdiff_t 功能：
1.c
```C
#include "stdio.h"
#include "stdlib.h"
#include "stdint.h"
#include "stddef.h"
int main(){
int num[] = {1,2,3,4,5,6};
int *n = n;
int *m = n + 1;
ptrdiff_t o = m - n;
printf("%ld\n", o);
}
```
輸出結果：
```shell
gcc -o 1 1.c && ./1
0x40073d 0x400741
1
```
指標 n、m 所指向的型態為 int，因此在進行運算時一個單位是 4 bytes，0x40073d、0x400741 兩個數值正好差 4，若型態改為 char 記憶體的位置只會差 1 bytes；而 ptrdiff_t 是用來計算兩個指標相差幾個"單位"，不是記憶體相差的 byte 數，因此 o 的數值為 1。
直接執行 ptr4.c：
```shell
gcc -o 1 1.c && ./1
1.c: In function ‘main’:
1.c:42:12: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*(*main - (ptrdiff_t) **main);
```
main 是 function designator \*main 與 \*\*main 兩者也都是 function designator，所存的數值是 main function 在記憶體中的位置，```(ptrdiff_t) **main``` 把 main 的記憶體位置轉換成指標操作時移動的單位，再以 \*main 相減得到 0，這時候得到的結果是一個內容為 0 的 function designator，程式再將 function designator 轉換成 pointer to function returning type (因為記憶體地址是 0 → NULL pointer)，最後程式將 NULL pointer 的數值 0 直接作為 int 回傳，因此出現型態轉換的警告。
==注意==
若程式改為：
```C
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
```shell
gcc -o 1 1.c && ./1
1.c: In function ‘main’:
1.c:28:10: error: invalid type argument of unary ‘*’ (have ‘long int’)
return &*(*main - **main);
```
```(*main - **main)``` 指標與指標相減，直接使用指標所存的值(記憶體位置)相減，得到的結果為純量，因此無法做 * 或 & 運算，透過 ptrdiff_t 將 \*\*main 轉換成純量，整個運算變成指標減一個純量，得到的結果仍然是指標，所以可以做 &、* 運算。
==轉型成 int、long 可以得到相同的結果，但 int 因長度不同會有警告出現==
Sign in with Wallet
Connect another wallet