# 2018q3 Homework1
contributed by < `brad84622` >
# 開發工具和規格標準篇
- 從 C99 開始， C 語言與 C++ 就分道揚鑣
- C99 用 Designated initializers 而 C++ 認為該由 Constructor 執行，因 Constructor 實作很可能發生在main之前
## ISO/IEC 9899 (簡稱C99)
- [C 語言規格書](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf)能澄清很多誤解
``` clike
int main(){
char str[] = "Hello World";
int *p = &str;
printf("%x %x\n", str, p + 1);
}
```
- 上式可以正確運行
``` clike
int main(){
char str[] = "Hello World";
int *p = &str;
printf("%x %x\n", str, p / 1);
}
```
- 但下式會出現 ==invalid operands to binary==，為什麼?
這就要看C99規格書，**6.5.3.3 Unary arithmetic operators**部分，就會發現在**Address and indirection operators**的部分只提供 `+` , `-` , `~` , `!` 這幾種運算
這就是為什麼我們需要閱讀規格書，而不是腦補"應該"有哪些功能
- Sizeof() 是Operator,而非Function
# 指標篇
- C語言只有Call-by-Value
- C語言中執行時期明確佔用空間的,就是物件(object)
- Array, function, and pointer types都被稱為derived declarator types
## `void *`
- `void *` 與 `char *` 應有相同的表示法
```clike
int main() {
void *A = 0;
char B = *(char *) A; //需要強制轉型
}
```
- 但在存取時需要強制轉型，否則無法編譯過，因 void* 並無佔有明確的空間
## 指標的指標(a pointer of a pointer)
- 是個常見用來改變 **「傳入變數原始數值」** 的技巧
- 考慮以下 2 段程式碼:
```Clike
int B = 2;
void func(int *p) { p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(ptrA);
printf("%d\n", *ptrA); //*ptrA=1
return 0;
}
```
```Clike
int B = 2;
void func(int **p) { *p = &B; }
int main() {
int A = 1, C = 3;
int *ptrA = &A;
func(&ptrA);
printf("%d\n", *ptrA); //*ptrA=2
return 0;
}
```
- 上段副本p之lifetime僅於func內，而下段副本p之lifetime卻在於整個main
>中英文、數字間都應以空白隔開
>[name=課程助教][color=red]
## Pointers vs. Arrays
- in declaration
- extern, 如 extern char x[]; => 不能變更為 pointer 的形式
- definition/statement, 如 char x[10] => 不能變更為 pointer 的形式
- parameter of function, 如 func(char x[]) => 可變更為 pointer 的形式 => func(char *x)
- in expression
- array 與 pointer 可互換
- 在取值時，array 的行為與 pointer 幾乎一樣，但 array 會是用兩步取值，而 pointer 是三步。（array 的位址本身加上 offset，共兩步，而使用 pointer時，cpu 需先載入 pointer 位址，再用 pointer 的值當作位址並加上 offset 取值）
:::info
避免用「兩步」或「三步」這類不精準用語，可作點實驗，對照輸出的組合語言需要幾道指令
:notes: jserv
:::
範例如下
```clike=
int main() {
int Array[3]={0,1,2};
int *p;
p=Array;
int B=Array[2];
int C=*(p+2);
}
```
其轉成組合語言為
```=
main:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-28], 0
mov DWORD PTR [rbp-24], 1
mov DWORD PTR [rbp-20], 2
lea rax, [rbp-28]
mov QWORD PTR [rbp-8], rax
mov eax, DWORD PTR [rbp-20] // 9 - 10 行為 int B=Array[2];
mov DWORD PTR [rbp-12], eax
mov rax, QWORD PTR [rbp-8] //11 - 13 行為 int C=*(p+2);
mov eax, DWORD PTR [rax+8]
mov DWORD PTR [rbp-16], eax
mov eax, 0
pop rbp
ret
```
可以看出同樣是取Array的第三個值 **2**，pointer(11-13行)在組合語言會比array(9-10行)多出一道指令
# 函式呼叫篇
## 藏在 Heap 裡的細節
- free() 釋放的是 pointer 指向位於 heap 的連續記憶體，而非 pointer 本身佔有的記憶體 (*ptr)。
:::warning
:question:
請問:
```clike
#include <stdlib.h>
int main() {
int *p = (int *) malloc(1024);
free(p);
free(p);
return 0;
}
```
照[函式呼叫篇](https://hackmd.io/s/SJ6hRj-zg)所言，double free執行應該會出現以下失敗訊息
```
*** Error in './free': double free or corruption (top):
0x000000000067a010 ***
```
但我在windows10及ubuntu18.04都能執行，請問為什麼呢？
:::
:::info
參見 [Diagnosing Memory Heap Corruption in glibc with MALLOC_CHECK_](https://www.novell.com/support/kb/doc.php?id=3113982)，設定好 `MALLOC_CHECK_` 環境變數 (注意有底線)，再做實驗
:notes: jserv
:::
# 遞迴呼叫篇
## 遞迴程式沒有你想像中的慢
- 因現代的編譯器最佳化技術，遞迴的程式不一定比迭代 (iterative) 的版本來得慢。
好比找最大公因數(GCD)常用的歐幾里得演算法(輾轉相除法)，以下為範例。
- [ ]遞迴版本
```clike
unsigned gcd_rec(unsigned a, unsigned b) {
if (!b) return a;
return gcd_rec(b, a % b);
}
```
- [ ]迭代版本
```clike
unsigned gcd_itr(unsigned a, unsigned b) {
while (b) {
unsigned tmp = b;
b = a % b;
a = tmp;
}
return a;
}
```
- 分析 clang/llvm 編譯的輸出 (參數 -S -O2)，發現兩者轉譯出的 inner loop 的組合語言完全一樣:
```
LBB0_2:
movl %edx, %ecx
xorl %edx, %edx
divl %ecx
testl %edx, %edx
movl %ecx, %eax
jne LBB0_2
```
- 但遞迴版本的原始程式碼更簡潔，且對應輾轉相除法的數學定義。
# goto 和流程控制
## switch 背後的 goto 和實作考量
- switch 可依據整數索引值進行多重分支 (multiway branching)，不僅能提高 C 程式的可讀性，而且相較於大量的 if-else 敘述，switch 透過跳躍表 (jump table) 的實作技巧可提升效率。
- 考慮到以下程式:
```clike
void switch_eg(long x, long n, long *dest) {
long val = x;
switch (n) {
case 100:
val *= 13;
break;
case 102:
val += 10;
/* Fall through */
case 103:
val += 11;
break;
case 104:
case 106:
val *= val;
break;
default:
val = 0;
}
*dest = val;
}
```
- 為了有效處理 switch 一類的多重分支，GCC 引入 computed goto 這個 GNU extension，可以將 label 的記憶體地址存入 void * 型態的 pointer 中，之前 switch_eg 函式的程式碼在 GCC 內部會轉換成以下等價程式:
```clike
void switch_eg_impl(long x, long n, long *dest) {
/* table of code pointers */
static void *jt[7] = {
&&loc_A, &&loc_def, &&loc_B, &&loc_C,
&&loc_D, &&loc_def, &&loc_D,
};
unsigned long index = n - 100;
long val;
if (index > 6) goto loc_def;
/* multiway branch */
goto *jt[index];
loc_A: /* case 100 */
val = x * 13;
goto done;
loc_B: /* case 102 */
x = x + 10;
/* Fall through */
loc_C:
val = x + 11;
goto done;
loc_D: /* case 104, case 106 */
val = x * x;
goto done;
loc_def: /* default case */
val = 0;
done:
*dest = val;
}
```
- 比對 switch_eg 和 switch_eg_impl，原程式對 100, 102 到 104，以及 106 情況給予特定的處置，變數 n 可以是任意有效範圍內的整數。
編譯器首先將 n 減去 100，以便讓取值範圍移到 0 到 6 之間，並透過新建立的變數 index 作為跳躍表的索引值，而跳躍表正是由 ==computed goto== 組成。
# linked list 和非連續記憶體操作
- 3 exceptional cases, we need to take care of:
- list is empty
- delete the head node
- node is not in the list
## 從刪除 linked-list node 看程式設計的品味
- 原本的程式碼
```clike
void remove_list_node(List *list, Node *target){
Node *prev = NULL;
Node *current = list->head; // Walk the list
while (current != target) {
prev = current;
current = current->next;
}// Remove the target by updating the head or the previous node.
if (!prev)
list->head = target->next;
else
prev->next = target->next;
}
```
- 有品味的程式碼
```clike
void remove_list_node(List *list, Node *target){
// The "indirect" pointer points to the *address* of the thing we'll update.
Node **indirect = &list->head;
// Walk the list, looking for the thing that points to the node we want to remove.
while (*indirect != target)
indirect = &(*indirect)->next;
*indirect = target->next;
}
```
- 從「要更新什麼位置的資料」思考，無論是 head 或者非 head，更新的是同一類型的資料，不用特別操作，自然省下額外的處理
# 技巧篇
## 明確初始化特定結構的成員
- C99 規格給予許多便利之處，比如:
```clike
const char *lookup[] = {
[0] = "Zero",
[1] = "One",
[4] = "Four"
};
assert(!strcasecmp(lookup[0], "ZERO"));
```
- 也可變化如下:
```clike
enum cities { Taipei, Tainan, Taichung, };
int zipcode[] = {
[Taipei] = 100,
[Tainan] = 700,
[Taichung] = 400,
};
```
## C99 Variable Length Arrays
```clike
void f(int m, int C[m][m])
{
double v1[m];
...
#pragma omp parallel firstprivate(C, v1)
...
}
```
- Visual C++ 不目前支援可變長度陣列
- 一個特例是 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html)
# 心得
作為一個土木系的跨考生，以往寫程式都僅以能夠正確執行為目標，沒有考慮過規格、可讀性、執行效能...等等的議題，經歷這次作業有種重新學程式的感覺。
:::info
在這個世紀，只要你做不出有強度 (讓上萬人每天使用的資訊系統) 的成果，就是「非本科」，反之，你過去做了什麼都沒關係。
:notes: jserv
:::
看了教材才知道有太多不了解的地方，也讓我知道自己最大的問題是「==不知道自己問題在哪==」，以前不覺得是問題的地方才知道有著大學問，為了搞懂這些問題就去google，爬到不懂的地方又再google下去，雖然花費很多時間，但也因此了解到很多知識。
這次教材花費時間比我預計多出很多，一部分是自己根基不穩所導致，也可惜沒來得及全部看完，之後希望能陸續將其補完。
Sign in with Wallet
Connect another wallet