# 2018q1 Homework3 (c-review)
contributed by <`bauuuu1021`>
* [作業要求](https://hackmd.io/s/ByDzIZzjf)
## 第四周
* [題目](https://hackmd.io/s/SyK-WApKM)
### 測驗 1
分析以下程式碼，推敲 `FuncA`, `FuncB`, `FuncC` 的作用，並且推測程式執行結果。
假設條件：
* `malloc` 總是成功而且返回的記憶體空間可讀寫
```Clike
#include <stdlib.h>
#include <stdio.h>
struct node { int data; struct node *next, *prev; };
void FuncA(struct node **start, int value) {
if (!*start) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
void FuncB(struct node **start, int value) {
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
new_node->prev = last;
last->next = (*start)->prev = new_node;
*start = new_node;
}
void FuncC(struct node **start, int value1, int value2) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value1;
struct node *temp = *start;
while (temp->data != value2)
temp = temp->next;
struct node *next = temp->next;
temp->next = new_node;
new_node->prev = temp;
new_node->next = next;
next->prev = new_node;
}
void display(struct node *start) {
struct node *temp = start;
printf("Traversal in forward direction \n");
for (; temp->next != start; temp = temp->next)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\nTraversal in reverse direction \n");
struct node *last = start->prev;
for (temp = last; temp->prev != last; temp = temp->prev)
printf("%d ", temp->data);
printf("%d ", temp->data);
printf("\n");
}
int main() {
struct node *start = NULL;
FuncA(&start, 51); FuncB(&start, 48);
FuncA(&start, 72); FuncA(&start, 86);
FuncC(&start, 63, 51);
display(start);
return 0;
}
```
==作答區==
`FuncA` 的作用是
* `(a)` 偵測輸入是否為 circular linked list，若是則將現有所有節點內容排序，否則不做事
* `(b)` 建立兩個節點並且安插在結尾，內容都是 `value`
* `(c)` 尋找所有節點，當遇到符合給定數值 `value` 的節點時，將 circular linked list 的開頭和剛找到的節點串接
* `(d)` 建立新節點，內容是 `value`，並安插在開頭
* `(e)` 建立新節點，內容是 `value`，並安插在結尾
* `(f)` 建立兩個節點並且安插在開頭，內容都是 `value`
* `(g)`
`FuncB` 的作用是
* `(a)` 偵測輸入是否為 circular linked list，若是則將現有所有節點內容排序，否則不做事
* `(b)` 建立兩個節點並且安插在結尾，內容都是 `value`
* `(c)` 尋找所有節點，當遇到符合給定數值 `value` 的節點時，將 circular linked list 的開頭和剛找到的節點串接
* `(d)` 建立新節點，內容是 `value`，並安插在開頭
* `(e)` 建立新節點，內容是 `value`，並安插在結尾
* `(f)` 建立兩個節點並且安插在開頭，內容都是 `value`
`FuncC` 的作用是
* `(a)` 偵測輸入是否為 circular linked list，若是則將現有所有節點內容排序，否則不做事
* `(b)` 建立兩個節點並且安插在結尾，內容分別是 `value1` 和 `value2`
* `(c)` 建立兩個節點並且安插在開頭，內容分別是 `value1` 和 `value2`
* `(d)` 找到節點內容為 `value2` 的節點，並在之前插入新節點，內容為 `value1`
* `(e)` 找到節點內容為 `value2` 的節點，並在之後插入新節點，內容為 `value1`
* `(f)` 找到節點內容為 `value1` 的節點，並在之前插入新節點，內容為 `value2`
* `(g)` 找到節點內容為 `value1` 的節點，並在之後插入新節點，內容為 `value2`
* `(h)` 尋找所有節點，當遇到符合給定數值 `value1` 和 `value2` 的兩個節點時，將這兩個找到的節點相互串接
在程式輸出中，訊息 `Traversal in forward direction` 後依序印出哪幾個數字呢？
Z1 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z2 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z3 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z4 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z5 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
在程式輸出中，訊息 `Traversal in reverse direction` 後依序印出哪幾個數字呢？
Z6 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z7 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z8 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z9 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
Z10 = ?
* `(a)` 63
* `(b)` 86
* `(c)` 51
* `(d)` 48
* `(e)` 72
* `(f)` 這個程式有缺陷，無法正確輸出數字
**解題策略**
* FuncA 中 `if (!*start)` 會使 *start 指向新建立的節點，否則會透過 `last = (*start)->prev;` 找到最後一個節點，並將新建立的節點放在最後一個節點後。所以答案為 `(e) 建立新節點，內容是 value，並安插在結尾`
* FuncB 所有操作大致與 FuncA 相同，都是找到原本最後一個節點並安插一個新節點再它後面。但唯一不同的是最後一句 `*start = new_node;` 將 *start 指向新節點，因此答案應為 `(d) 建立新節點，內容是 value，並安插在開頭`
:::warning
FuncB 中少了和 FuncA 中有的 `if (!*start)` 判斷式，如果沒有再 initial 時將 prev & next 指向自己可能會發生錯誤存取的問題
:::
* FuncC 先建立數值為 value1 的節點，再以 tmp 從 start 開始 trace 每個節點，直到節點中數值為 value2。並將節點加到這個節點後。因此答案應為 `(e) 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1`
* 根據上面的分析，main() 中的 Func() 會使 *start 指向數列 `48->51->63->72->86`
* display() 則是將傳入的 pointer to pointer 指向的數列從頭印到尾再從尾印到頭，因此 `Z1~Z10` 分別為 `48 51 63 75 86 86 72 63 51 48`
### 測驗 `2`
考慮以下程式碼，推敲程式作用並分析輸出。
假設條件：
* `malloc` 總是成功而且返回的記憶體空間可讀寫
* `malloc()` 得到的地址成嚴格單調遞增函數
```Clike
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct node { int data; struct node *next; };
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
struct node *node_new(int data) {
struct node *temp = malloc(sizeof(struct node));
temp->data = data; temp->next = NULL;
return temp;
}
int main() {
int count = 0;
struct node *head = node_new(0);
head->next = node_new(1);
head->next->next = node_new(2);
head->next->next->next = node_new(3);
head->next->next->next->next = node_new(4);
printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next->next->next->next = head;
printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next->next->next->next->next = head->next;
printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
head->next = head->next->next->next->next->next->next->next->next;
printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
printf("K5 >> %d\n", head->next->data);
printf("count >> %d\n", count);
return 0;
}
```
==作答區==
`FuncX` 的作用是 (涵蓋程式執行行為的正確描述最多者)
* `(a)` 走訪 circular linked list 所有節點，計算節點數量並更新
* `(b)` 走訪 circular linked list 所有節點，計算節點數量並更新，回傳最後一個節點和開頭的地址距離 (offset)
* `(c)` 走訪 circular linked list 所有節點，回傳最後一個節點和開頭的地址距離 (offset)
* `(d)` 判斷是否為 circular linked list，若為 circular 則回傳非零值，其他回傳 `0`
* `(e)` 判斷是否為 circular linked list，若為 circular 則回傳 `0`，其他非零值
* `(f)` 判斷是否為 circular linked list，若為 circular 則回傳 `0`，其他非零值，過程中計算走訪的節點總數
* `(g)` 判斷是否為 circular linked list，若為 circular 則回傳非零值，其他回傳 `0`，過程中計算走訪的節點總數
`K1 >>` 後面接的輸出為何
* `(a)` No
* `(b)` Yes
`K2 >>` 後面接的輸出為何
* `(a)` No
* `(b)` Yes
`K3 >>` 後面接的輸出為何
* `(a)` No
* `(b)` Yes
`K4 >>` 後面接的輸出為何
* `(a)` No
* `(b)` Yes
`K5 >>` 後面接的輸出為何
* `(a)` 5
* `(b)` 4
* `(c)` 3
* `(d)` 2
* `(e)` 1
* `(f)` 0
`count >>` 後面接的輸出為何
* `(a)` 5
* `(b)` 4
* `(c)` 3
* `(d)` 2
* `(e)` 1
* `(f)` 0
## 第五周（上）
* [題目](https://hackmd.io/s/SynmEVIqG)
### 測驗 1
考慮以下程式碼，推敲其作用 (選出最符合行為的描述)
```clike
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
```
將 `Func32` 改寫為以下功能等價的程式碼:
```clike
uint8_t FuncI(uint32_t x)
{
if (!x) return 32;
int n = 1;
if (!(x >> 16)) { n += 16; x <<= 16; }
if (!(x >> M1)) { n += 8; x <<= 8; }
if (!(x >> M2)) { n += 4; x <<= 4; }
if (!(x >> M3)) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
==作答區==
Func32 = ?
* `(a)` 計算對 `x` 的二進位表示法中，總有有幾個 bit 為 `1`，如果全部都是 `1`，那麼回傳 `32`
* `(b)` 計算對 `x` 的二進位表示法中，總有有幾個 bit 為 `0`，如果全部都是 `0`，那麼回傳 `32`
* `(c)` 計算輸入數值 `x` 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 `x` 為 `0x0`，則輸出 32
* `(d)` 計算輸入數值 `x` 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 1，倘若 `x` 每個 bit 均為 `1`，則輸出 32
* `(e)` 計算輸入數值 `x` 的二進位表示中，回傳尾巴 (低位元到高位) 有幾個 1，倘若 `x` 每個 bit 均為 `1`，則輸出 32
* `(f)` 計算輸入數值 `x` 的二進位表示中，回傳尾巴 (低位元到高位) 有幾個 0，倘若 `x` 為 `0x0`，則輸出 32
M1 = ?
* `(a)` 0xF
* `(b)` 0xFF
* `(c)` 0x12
* `(d)` 0x14
* `(e)` 0x16
* `(f)` 0x18
* `(g)` 0x1A
M2 = ?
* `(a)` 0x1F
* `(b)` 0x1E
* `(c)` 0x1D
* `(d)` 0x1C
* `(e)` 0x1B
* `(f)` 0x1A
* `(g)` 0x10
M3 = ?
* `(a)` 0x1E
* `(b)` 0x1D
* `(c)` 0x1C
* `(d)` 0x1B
* `(e)` 0x1A
* `(f)` 0x10
**解題策略**
* Func32 = ?
將極端值代入 `Func32` 中，x 為 0x00 時會得到 32，x 為 0xFF 會得到 0。`return x ? Func32(x >> 1) - 1 : 32;` 中， `Func32(x >> 1)` 最終一定會使傳入參數為 0，return 32。 而每次呼叫 `Func32(x >> 1)` 就會 -1，代表==從 x 往右 shift n 次就會變成 0，則最終答案就是 32-n== 。因此答案為 `(c) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32`
* M1 = ?
if (!(x >> M1)) 則 n += 8 ，代表將 x 往右移 M1 位後若 ==0，就代表 x 的左邊有 8 bits 的 0。而 x 為一個 32 位元數，因此答案應該為 ==32-8=24== ，轉換成 16 進位為 `(f)0x18`
* M2 = ?
同上題，答案應為 ==32-4=28== ，轉換成 16 進位為 `(c)0x1C`
* M3 = ?
同上題，答案應為 ==32-2=30== ，轉換成 16 進位為 `(c)0x1E`
## 第五周（中）
* [題目](https://hackmd.io/s/HkQjgqI5G)
</br>**先大膽假設跟 ASCII 有關**
* 發現將 `double m[] = { 3823806048287157.0,96 }` 改為 `double m[] = {3823806048287157.0}` 或 `double = 3823806048287157.0` 都不影響結果
* 將 `3823806048287157.0` 丟到 [double & binary converter](http://www.binaryconvert.com/convert_double.html) 中，得到
* binary 01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010
* hex 0x432B2B767265736A
* `jserv++C` 共 8 個字元，因此應該是每個字元對應到 hex 的兩個字元
>[color=green] 在解題的時候發現 `j` 的 ascii code 應該為 `6A` 而不是 hex 轉換後的前兩碼 `43` ，~~瞎猜~~思考了好一陣子才想到應該是 little endian 的關係[name=bauuuu1021]
* 將 hex 兩個字元為一組，反向排列後得到 6A 73 65 72 76 2B 2B 43，也確實為 jserv++C hex 編碼的 ascii code，**也證實剛開始的假設正確**
:::success
延伸題目:
1. 修改程式，允許輸出你的 GitHub 帳號名稱
2. 承上，修改 gen() 函式，透過特定的轉換，讓 `m[]` 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼
3. 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？
:::
1. 將我的帳號 `bauuuu1021` 反向排序並對應到 ascii 為 `31 32 30 31 75 75 75 75 61 62`(hex) ，[轉成](https://gregstoll.dyndns.org/~gregstoll/floattohex/) double[ ] 並輸出卻只得到
```
bauuuu1021@X555LB:~$ ./test
bauuuu10
```
* 發現 `bauuuu10` 剛好 8 字元，再加上 ascii 字串去掉最前面的 `31 32` 所得到的 double 值也會相同
* 因此將 `31 32` 另外轉換成一組 double 值並放到 struct 中原本數值的後面，得到結果：
```
bauuuu1021@X555LB:~$ cat test.c
#include <stdio.h>
int main() {
puts((char *) &(double []){ 1.507773427734912e-76,6.2223e-320 });
}
bauuuu1021@X555LB:~$ ./test
bauuuu1021
```
2.
* jserv++C:0 10000110010 1011001010110111011001110010011001010111001101101010
* bau:0 00000000000 0000000000000000000000000000011101010110000101100010
3. 在將字串轉成 ascii 前不需將整個字串轉置，直接轉成 ascii 即可
## 第五周（下）
* [題目](https://hackmd.io/s/Sk30MXDqM)
### 測驗 1
* Q11: 做了 1: Stuck at 0 left of cut 的修改，`sw $s1, 0($s2)` 能否運作？
* Q12: 承上，下方程式能否運作？
```
lw $s1, 0($s2)
add $s1,$2,$3
```
**解題策略**
題目所切掉的是控制是否 write back to register 的線，所以有要寫回到 register 的指令會失效，因此：
Q11：沒有要寫回，`可以運作`
Q12：要寫回，`不可運作`
### 測驗 2
Q21: 做了 2: Cut here 的修改後，以下程式能否運作？
```
add $s1, $s1, $s1
add $s1, $t0, $t1
```
**解題策略**
切斷處並不影響 $rs 及 $rt 輸入到 ALU，而是影響到從 ALU 執行完的 forwarding 的其中一條；但題目的程式並不會用到 forwarding ，所以 `可以運作`
### 測驗 3
* Q31: 做了 3: Cut here 的修改後，以下程式能否運作？ (exit 為某個副程式)
```
cmp:
xor $t1, $s2, $s1
slt $t2, $zero, $t1
sll $t2, 2
add $ra, $ra, $t2
jr $ra
entry:
addi $s2, $zero, 2
addi $s1, $zero, 2
jal cmp
j exit
```
* Q32: 承上，以下程式能否運作？
```
addi $s2, $zero, 2
addi $s1, $zero, 2
beq $s2, $s1, exit
```
**解題策略**
* 圖 1
* 圖 2
* PC 位址跳躍主要可分為 `j` 及 `beq` 兩種類型，從圖 1 和圖 2 與題目做比較可得知，題目所切掉的地方只對 `beq` 有影響，對 `j` 則無。
* 因此 Q31 `可以運作`， Q32 `不可運作`。
###### tags: `bauuuu1021`, `sysprog`
Sign in with Wallet
Connect another wallet