# 20160923 Sysprog
## 課堂測驗
Q1 以下程式作用為何？
```
int p(int i, int N){
return (i<N && printf("%d\n", i )&& !p(i +1, N))\
|| printf("%d\n",i);
}
int main(){
p(1,5);
return 0;
}
```
* `&&` 前後的敘述對調，是否影響輸出？
* 從 `i < N && printf("%d\n", i)` 變更為 `printf("%d\n", i) && (i < N)` 的話，程式輸出為何？
A:
當 `i<N` 成立時
會執行 `printf("%d\n", i)` 直到 `i = N` (`!p(i + 1, N)`形成遞迴)停止
執行 `||` 後的 `printf`
當 `i = N` 時停止 call function 並且執行 `||` 後的 `printf` 回傳不為零的 integer
利用 gdb bt 可以查看到堆疊追蹤
印出 :
```
1
2
3
4
5
4
3
2
1
```
對調是會影響，讓原本`i=N`時先印出數字再判斷判別式，不成立時讓 `||` 後再印出一次
印出：
```
1
2
3
4
5
5
4
3
2
1
```
### 延伸題：
Q : 需要聲明「有效數值範圍」，比方說參數 i 與 N ?
A : i < N
Q : 使用遞迴，stack depth 的限制為何 ?
A :
unix stack size default : 8MBytes
windows stack size default : 1MBytes
利用 `$ ulimit -s` 可以查出 stack size
在電腦上查到是 8192kB ，以這題為例在遞迴時會將變數暫存再stack，每呼叫一次會存入回傳位址 8bytes, int i, N 變數共 8bytes, printf()*2 8 bytes, p回傳回來值int 4bytes ，總共 32 bytes
8MB = 8,388,608 bytes
8,388,608 / 32 =262,144 次
>一開始算的時候發現很多因素未考量只算出 20bytes
算出來值在程式去驗證，發現再 261899 次時出現 segmentation fault ，通過 8388608 / x = 261899 算出大概是32bytes
bytes很多沒考量到，所以開gdb disass 開始探討
```
Dump of assembler code for function p:
0x0000000000400526 <+0>: push %rbp
0x0000000000400527 <+1>: mov %rsp,%rbp
0x000000000040052a <+4>: sub $0x10,%rsp
0x000000000040052e <+8>: mov %edi,-0x4(%rbp)
0x0000000000400531 <+11>: mov %esi,-0x8(%rbp)
0x0000000000400534 <+14>: mov -0x4(%rbp),%eax
0x0000000000400537 <+17>: mov %eax,%esi
0x0000000000400539 <+19>: mov $0x400634,%edi
0x000000000040053e <+24>: mov $0x0,%eax
0x0000000000400543 <+29>: callq 0x400400 <printf@plt>
0x0000000000400548 <+34>: test %eax,%eax
0x000000000040054a <+36>: je 0x40056a <p+68>
0x000000000040054c <+38>: mov -0x4(%rbp),%eax
0x000000000040054f <+41>: cmp -0x8(%rbp),%eax
0x0000000000400552 <+44>: jge 0x40056a <p+68>
0x0000000000400554 <+46>: mov -0x4(%rbp),%eax
0x0000000000400557 <+49>: lea 0x1(%rax),%edx
0x000000000040055a <+52>: mov -0x8(%rbp),%eax
0x000000000040055d <+55>: mov %eax,%esi
0x000000000040055f <+57>: mov %edx,%edi
0x0000000000400561 <+59>: callq 0x400526 <p>
0x0000000000400566 <+64>: test %eax,%eax
0x0000000000400568 <+66>: je 0x400582 <p+92>
0x000000000040056a <+68>: mov -0x4(%rbp),%eax
0x000000000040056d <+71>: mov %eax,%esi
0x000000000040056f <+73>: mov $0x400634,%edi
0x0000000000400574 <+78>: mov $0x0,%eax
0x0000000000400579 <+83>: callq 0x400400 <printf@plt>
0x000000000040057e <+88>: test %eax,%eax
0x0000000000400580 <+90>: je 0x400589 <p+99>
0x0000000000400582 <+92>: mov $0x1,%eax
0x0000000000400587 <+97>: jmp 0x40058e <p+104>
0x0000000000400589 <+99>: mov $0x0,%eax
0x000000000040058e <+104>: leaveq
0x000000000040058f <+105>: retq
End of assembler dump.
```
0 < N - i < 262,144
在計算中還有未考量因素，在用程式去驗證時，實際上還會更小。
## Q2: 考慮以下 swap 程式:
```C
void swap(int *a, int *b)
{
int t; t = *a; *a = *b; *b = t;
}
```
能否避免使用區域變數 t？又，可否改用 bit-wise operator 來改寫？
A:
算術運算-利用兩個相差距離做運算
但如果遇到一個很大的整數與一個負數(足夠讓他超過最大整數)兩個相減時，會產生益位
```
*a = *a - *b; //兩數相差
*b = *a + *b; //相加得出*b
*a = *b - *a; //相減得出*a
```
邏輯運算-運用邏輯運算查看出兩個不同相差的位元
真值表
```
*a = *a XOR *b //算出相差位元
*b = *a XOR *b //與相差位元做XOR得出*a
*a = *a XOR *b //與相差位元做XOR得出*b
```
* 參考資料 [wiki](https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96)
邏輯運算的好處是，可避免前述算術會遇到的 integer overflow，而且不限定位元數。
## Q3: 用 C 語言實做 `char *reverse(char *s)` 來反轉 NULL 結尾的字串，限定 in-place 與遞迴
參考實作 (都還可以大幅改進，只是列出來給大家看)
* [Day2](https://embedded2015.hackpad.com/GGI4IhFdLUW)
**C-style string reverse (遞迴 + in-place)**
* 先想想這個版本可用嗎? (以及對應的問題)
```C
void reverse (char *s) {
if (*s == ’\0’) return;
reverse (s+1);
printf ("%c", *s);
}
```
```C
char reverse(char *s){
return (*s == '\0') || reverse(s+1) && printf("%c",*s);
}
```
A : 一開始想法:兩兩交換，但可能字串太長回圈會耗太多時間
```c=
char *reverse(char *s){
static int time = -1;
static int length = -1;
int first = 1;
if (time == -1){
time = strlen(s) - 1;
length = strlen(s);
first = time;
}
//想法:兩兩交換
while(first--){
if(*(s+ (length-time)) == '\0' ){
return s;
}
*s = (s ^ *(s+1);
*(s+1) =*(s+1) ^ *s;
*s = *s ^ *(s+1);
reverse(s+1);
if(first) time = first;
}
return s;
}
int main(){
char s[] ="123456789";
printf("%s \n", reverse(s));
return 0 ;
}
```
經過老師延伸問題提問,發現有 Reentrancy 問題，程式碼還有很大的改進空間，可以再優化，詳細看延伸題。
>> 以上實做不符合需求，應該是輸入一個 pointer to character，回傳一個 pointer to character，這兩者的起始位址可以不同，也能相同，後者稱為 in-place。注意看題目要求！ [name=jserv]
>>> 好的老師，修正好了謝謝
[name=HuangWenChen]
### 延伸題：
Q ： 是否存在 Reentrancy 問題？
A : 是
* 參考資料
* [Reentrancy wiki]( https://en.wikipedia.org/wiki/Reentrancy_(computing))
Reentrancy 問題是否能重複去使用。
Reentrancy 規則：
1. Reentrant code may not hold any static (or global) non-constant data.
2. Reentrant code may not modify its own code.
3. Reentrant code may not call non-reentrant computer programs or routines.
而我再上面code運用到 static 變數再次使用會有問題。
優化改進
```c=
char *reverse(char *s){
static int time = -1;
static int length = -1;
int first = 1;
if (time == -1){
time = strlen(s) - 1;
length = strlen(s);
first = time;
}
//想法:兩兩交換
while(first--){
if(*(s+ (length-time)) == '\0' ) return s;
//swap
*s ^= *(s+1) ^= *s ^= *(s+1);
reverse(s+1);
if(first) time = first;
}
if(time == 1) time = -1;
return s;
}
```
時間複雜度 O(n) 僅能在 single thread 重複使用
multithread 會有共用變數問題
Sign in with Wallet
Connect another wallet