# D06: c-review
contributed by < `rex662624` >
## [第 4 週測驗題](https://hackmd.io/s/SyK-WApKM)
### 測驗 `1`
#### 解題
##### 1. FuncA 的作用是
```clike=
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;
}
```
這題觀察程式碼，關鍵是在第12行的部分，做了:插入的 node 下一個 node 是 start 。剩下的13~15行則是做了把插入的 node 放到合適的位置與把指標只好。因此 start 仍然為本來的 start ，但是start 前面卻多了一個 node，也就是在結尾的位置加入一個 node 。
而 2~8 行，則是在做尚未有任何一個 node 的狀況，因此在結尾插入的 node 也等於是 start。
故答案是: `(e)` 建立新節點，內容是 `value`，並安插在結尾
##### 2. FuncB 的作用是
```clike=
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;
}
```
這題本來我在想是不是與 funcA 是相同的。後來發現，差別在於第8行，它把 start 指向了新 node，因此是在開頭的地方插入新 node 。
答案是`(d)` 建立新節點，內容是 `value`，並安插在開頭
##### 3. FuncC 的作用是
```clike=
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;
}
```
首先第3行把新 node 值設為 value1 。而後從 start 一路找到值 = value2 的 node ，而後將 value1 的 node 放在 value2 node後面。
答案是 `(e)` 找到節點內容為 `value2` 的節點，並在之後插入新節點，內容為 `value1`
不過這裡好像有幾個沒有考慮的點:
1. 若是 start 是指向 NULL ，也就是尚未有任何 node 的時候，則程式應該會 core dumped ，因為有 temp->data 這個動作。
2. 若是根本沒有 value2 這個值，會進入無限迴圈，因為這是 circular linked list ，一路 next 到尾巴後又會從頭開始，永遠無法結束。因此user 必須自己保證 list 內一定有 value2 。
##### 4. 在程式輸出中，訊息 `Traversal in forward direction` 後依序印出哪幾個數字呢？
首先先看main
```clike=
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;
}
```
做到第 5 行結束時， list 是長這樣
```
[48]<->[51]<->[63]<->[72]<->[86]
```
觀察`Traversal in forward direction` 後做了
```clike=
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);
```
因此是從開頭一路印出 data，直到 start 的 prev 就跳出，因為最後又有印一次(第五行)，所以本來 for 沒有印出的最後一個 data 會被這行印出來。
因此答案順序為 48 51 63 72 86 。
##### 5. 在程式輸出中，訊息 `Traversal in reverse direction` 後依序印出哪幾個數字呢？
同樣的， list 是
```
[48]<->[51]<->[63]<->[72]<->[86]
```
程式碼:
```clike=
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");
```
這次是從 start 的前一個人開始印，一路往 prev 走直到走到 start ，這裡 start 並不會在 for 裡面印出來，而是跳出。直到第5行因為又做了一次 print ，才被印出來。
因此答案是 86 72 63 51 48
### 測驗 `2`
#### 解題
##### 1. `FuncX` 的作用是
首先觀察程式碼
```clike=
int FuncX(struct node *head, int *data) {
struct node *node;
for (node = head->next; node && node != head; node = node->next)
data++;
return node - head;
}
```
這裡看到 for 裡面，首先指向 head 的下一人，如果 node 是 NULL 或是 head 就會跳出，最後 return node - head 。在這裡如果是由於 NULL而跳出，則 node - head 不會是 0 ，而如果是因為回到 head 而跳出，則最後return 的會是 head 的 address 減掉自己，所以會是 0。而這也代表它是 circular linked list 。
因此答案是`(e)` 判斷是否為 circular linked list，若為 circular 則回傳 `0`，其他非零值
##### 2. ~ 6. `K1 >>` ~ `K5 >>`後面接的輸出為何
```clike=
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;
}
```
首先必須要知道 node_new() 是如何運作。發現裡面只是要一塊空間並把值填入，然後把 next 指向 NULL 。
首先 9~13 行的圖形將會是以下:
```
9 head->[0]
10 head->[0]->[1]
11 head->[0]->[1]->[2]
12 head->[0]->[1]->[2]->[3]
13 head->[0]->[1]->[2]->[3]->[4]
```
因此`printf("K1 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");` 會印出YES，因為這裡會回傳非0值，所以等於if ( true ) ，會印出前面的YES。**K1=YES**。
再來繼續觀察程式碼
```clike=
head->next->next->next->next = head;
printf("K2 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");
```
本來的list是`head->[0]->[1]->[2]->[3]->[4]` 。`head->next->next->next->next `是[3]的next，因此[3]又會指向[0]成為 circular list，則 **K2=NO**。(但這裡[4]有 memory leak)
再處理K3
```clike=
head->next->next->next->next->next = head->next;
printf("K3 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");
```
現在的list是head->[0]~[3]的單向 circular list 。而等號左邊的是[0]的next，等號右邊的也是[0]的next，因此list不變，這裡同樣**K3=NO**。
```clike=
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);
```
現在的list是head->[0]~[3]的單向 circular list 。而這裡等號左邊是[0]的next，要指向的是[0]，因此[0]自己指向自己，這裡同樣[1]~[3]會造成 memory leak 。因此最後也是一個circular linked list **K4=NO**
K5: head ([0]) 的next仍為[0]自己，因此印出的**K5=0**。
##### 7. `count >>` 後面接的輸出為何
這裡也同樣解釋了為何 1.並非 f 而是 e的原因。function 內宣告的 parameter 是 `int *data` ，而程式碼走訪每個 node 後做的是 data++; 這裡如果要輸出到底有多少 node 應該用`*data++`，而這裡 data++只不過加了 address ，而且因為對 address 是 pass by value ，所以並不會養想到 function scope 外面的任何值。
因此最後 count 仍然為原來的 0 。**K5=0**。
## [第 5 週測驗題 (上)](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 = ?**
觀察程式碼，發現做的動作是 recursive call Func32，途中 x 會不斷的右移 1 bits，直到最後 x 已經 =0，會 return 32 ，再一步一步的往上 -1 。而這個動作的意義在，右移到全部都為0了，就表示剛才 recursive call 的次數就等於尾數有幾位不為0。因此用32減掉尾數不為0有幾位，我們就可以得知開頭有幾個0。
==Ans:計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32==
**M1、M2、M3=?**
參考[ st9007a 的 clz ](https://hackmd.io/s/rywfL4tj-)。
這裡是利用 if 來分別確認 `x` 的前 16 , 8 , 4 , 2 個 bits 是否為零，如果為零則將他們加入 `n`，並且左移 `x` 確保下個 if 能檢查到正確的位置，如果不為零則直接做下一個 if 檢查，最後 `x` 剩下 最前面的 1 bit 沒有被檢查到，在第9行做處理，如果是0就等於不做動作，如果是1就減掉1。~~第9行其實也可以在一開始做處理，多寫一個`if(x>>31==1)retrun 0 ;`，就可以把第9行刪掉。~~
因此答案是==M1=24 M2=28 M3=30==
>你這邊好像想錯了，n 一開始設為 1，所以所有"開頭有偶數個 0 "的情況第九行都是有意義的(x>>31=1)否則無法輸出偶數的 n，例如：
>開頭有 16 個 0 的話會跑if (!(x >> 16)) { n += 16; x <<= 16; }
>跑完後 n = 17, x = 10..0,到第九行 n = 17 - 1 = 16
[name=e94046165][color=green]
>>
>>感謝指正!的確 x 在中間就會被改值了。所以你說的是對的，若是偶數個 0 的狀況，因為 n 初值是1，最後跑完 if 就都會多1，要在第9行做處理。
>>[name=rex662624][color=#662624]
### 測驗 `2`
#### 解題
**Func64 的作用為？**
```clike=
union u_qword {
struct {
uint32_t low;
uint32_t high;
} dwords;
uint64_t qword;
};
struct udiv_result {
union u_qword q;
union u_qword r;
};
static inline int Func64(uint64_t val)
{
uint32_t lo = (uint32_t) val;
uint32_t hi = (uint32_t) (val >> 32);
return hi ? Func32(hi) : 32 + Func32(lo);
}
```
這裡將測驗1的 Func32 擴展為 64-bit 版本。方法是先把 64bits 分為前後 32bits，分別為 hi 和 lo 。 然後第18行判斷最高 32bits 是不是皆為0，若不是的話就呼叫 Func(32) 看看到底有0在最高位。如果前 32bits 都是0，則是用32+最低位又有幾個 leading 0 算出答案。
答案是==計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64==
```clike=
static int do_udiv32(uint32_t dividend,
uint32_t divisor,
struct udiv_result *res)
{
/* Ensure dividend is always greater than or equal to the divisor. */
uint32_t mask = Func32(divisor) - Func32(dividend);
divisor <<= mask; /* align divisor */
mask = 1U << mask; /* align dividend */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.dwords.low |= mask;
}
divisor >>= 1;
} while ((P1) && dividend);
res->r.dwords.low = dividend;
return 0;
}
int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res)
{
uint64_t mask;
uint64_t bits;
res->q.qword = res->r.qword = 0;
if (divisor == 0) { /* division by 0 ? */
res->q.qword = 0xffffffffffffffffull;
return -1;
}
if (divisor == dividend) {
res->q.qword = 1;
return 0;
}
if (divisor > dividend) {
res->r.qword = dividend;
return 0;
}
/* only 32 bit operands that the preconditions are fulfilled. */
if (!(divisor >> 32) && !(dividend >> 32))
return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res);
bits = Func64(divisor) - Func64(dividend);
divisor <<= bits; /* align divisor and dividend */
mask = 1ULL << bits;
/* division loop */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.qword |= mask;
}
divisor >>= 1;
mask >>= 1;
} while ((P2) && dividend);
res->r.qword = dividend;
return 0;
}
```
首先理解 do_udiv32 ，這裡用到的演算法與計算機組織用到的有點相似。
mask 是表示最後的商值有幾位數。do 裡面的演算法為，若 dividend > divisor ，dividend 就減去 divisor ，而最後的中止條件為直到(~(P1) | dividend==0) 這裡後面的 divided==0 是整除的情況跳出機制，所以可以推測 ~(P1) 是不整除的情況，也就是要用到 mask 來看商數是否已經夠長了。所以用 mask>>1 ，每次 while 迴圈算出一位數就右移一位，直到最後 mask \=\=0就跳出，因此==P1\:mask>>\=1==
同理可以推廣到下面的 64-bit 版本。這裡加上了一些除錯的機制。例如第27行是用來偵測是否除以0。
而這裡的答案==P2=bits - -==，與 32-bit 的跳出機制相同，都是偵測商數是否已經到達目標位數。
```clike=
int main()
{
char digitbuff[20];
char *pos = digitbuff + sizeof(digitbuff);
union u_qword v; /* current value */
union u_qword nv; /* next value */
struct udiv_result d;
int64_t value = 0xCAFEBABE; /* Java classfile magic number */
v.qword = (unsigned long long) value;
while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
/* determine digits from right to left */
udiv64(v.qword, 10, &d);
*--pos = d.r.dwords.low + P3;
v.qword = d.q.qword;
}
do { /* process 32 bit (or reduced 64 bit) value */
nv.dwords.low = v.dwords.low / P4;
*--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5;
} while ((v.dwords.low = nv.dwords.low) != 0);
int len = digitbuff + sizeof(digitbuff) - pos;
char *p = pos;
while (len--)
putchar(*p++);
printf("\n");
return 0;
}
```
首先P3和P5，都是做一樣的動作，把原本的數字存進 char 裡面，而這裡要把原本的數字變成 ascii 碼，所以要加上(48)~10~=(0x30)~16~。這裡參考[e94046165 同學](https://hackmd.io/6WXM0FXOR3C8T_E3f501Ww?view#%E6%B8%AC%E9%A9%97-21)找出的錯誤。
最後 P4 的部分，是因為我們要印出十進位，所以我們每次都要除10，如同我們如果要 1bit 1bit 印出二進位值，必須要用 number>>1(就是number/2)一樣。
## [第 5 週測驗題 (中)](https://hackmd.io/s/HkQjgqI5G)
### 解題
首先理解題目`jserv++C` ：
`puts((char *) &(double []){ 3823806048287157.0, 96 });`這行，把`3823806048287157.0`這個數字用 char * 型態印出來，因此透過[轉換](http://www.binaryconvert.com/convert_double.html)我們知道了在記憶體內的真實儲存資料為==01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010==
而因為一個字元就佔了 1byte ，所以我們可以知道上面的數字要用 8 bits為一個單位切割。透過[轉換](https://codebeautify.org/binary-string-converter)我們知道，答案會是 ==C++vresj== 。但這是在big-endian的狀況，而我們的環境若是little-endian，最大的 8 bit 反而會儲存在最後面。也就是其實答案是倒過來的==jserv++C==。
回過頭來看題目，實際上是把`3823806048287157.0`乘上了96次的2，因此在 IEEE-754 double-precision 等於是把次方的11個 bits 加上了96，因此影響的只有前兩個 byte ，也就是`+C`的部份。原本的 前兩個byte是 01000011 00101011 ，次方的11 bits 為1000011 0010，加上96之後會成為1001001 0010，也就是前兩個byte是 01001001 00101011 ，最後整個數字轉為 ascii 後就成為==I++vresj==，在 little-endian 印出的就是 ==jserv++I==
### 延伸題目[(github)](https://github.com/rex662624/2018D06-c-review/tree/master/W5_mid)
#### 修改程式，允許輸出你的 GitHub 帳號名稱
程式碼如下：
```clike=
#include <stdio.h>
int main() {
printf("%s",(char *) &(double []){8.2330057975734170815348646124E-67, 96 });
puts((char *) &(double []){6.0134700169990949837211519873E-154, 96 });
}
```
我的 id 是 rex662624 ，因此64 bits是無法印出來的，因此需要兩行才能印出來。我的策略是：第一個數字先印出rex66262，第二個數字則印出4。
因次透過上面那兩個轉換網址，[ double-precision to deciaml ](http://www.binaryconvert.com/result_double.html?hexadecimal=2020202020202034)，[ string to binary ](https://codebeautify.org/string-binary-converter)，可以知道 rex66262 換成 decimal 是 8.2330057975734170815348646124E-67 ，而因為第二個字串只要印出4，我的 6.0134700169990949837211519873E-154 其實印出的是 =="4_______"== (去掉底線)，後面有七個空白，這樣剛好滿足 8 bytes。
如此一來，就能成功印出 rex662624 並換行。
#### 修改 gen() 函式，透過特定的轉換，讓 `m[]` 的內容變為你的英文姓氏 (last name)
jserv++C :`0` `10010010010` `1011001010110111011001110010011001010111001101101010`
rex_____: `0` `01000000010` `0000001000000010000000100000011110000110010101110010`
第一行是題目字串與它在記憶體的儲存方式，第二行則是目標產生的字串。
因此我把它分成三個部份處理，signed，exponent，mantissa。
首先第一個部份，因為 signed 一樣，所以不需要做處理。
第二個部份是 exponent，我採用了與原來相似的方式，讓它除上656次的2，就相當於把 exponent 減去656，達到我想要的數字。
第三個部份與第二個部份相關，我的方法是直接做加減法成我要的數字，而 ieee754的加減法，次方部份要做對齊才會是對的結果，因此次方的地方， m[0] 已經在第二部份被調整成目標的次方了，這裡就要用目標的次方去作加減法。
如此一來就成功輸出==rex==
```clike=
#include <stdio.h>
double m[] = { 3823806048287157.0, 656 };
void gen() {
if (m[1]--) {
m[0] /= 2;
gen();
} else
{
m[0]-=1.79805224261238405855038489163E44;
puts((char *) m);
}
}
int main() { gen(); return 0; }
```
#### 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？
* 就範例程式提供的 jserv++C 來說:
1. 因為由上面的轉換，我們知道轉換出來的答案其實是 C\+\+vresj ，因此只要存入 jserv\+\+C 的數值，在big-endian 的環境就能達到正確的效果。
2. 參考[ stackoverflow ](https://stackoverflow.com/questions/2782725/converting-float-values-from-big-endian-to-little-endian)。也可以不改變數值，但是另外用一個函式ReverseFloat() 一個一個 char 轉過來。(注意網址中是只有32 bits ，因此只有 4個 char 空間，而若是適用於這題需要 0~7 ，8個空間。)
* 就題目主體gen()來說:
1. 與上一題的2.相同，gen()完再呼叫 ReverseFloat() 把它一個一個char轉過來。
2. 因為本來 C\+\+vresj ，改為 I\+\+vresj ，改變的是最前面的一個 byte 數值而已。而若是在 big-endian 的環境下則改變的是最後一個 byte 。因此不關 exponent 的事 ，而是要改 mantissa 部分，因此要用加減法去做改變 mantissa。
## [第 5 週測驗題 (下)](https://hackmd.io/s/Sk30MXDqM)
考慮某款 MIPS 實作，其 data path 如下:
上圖紅色的 `1`, `2`, `3` 對 MIPS 做了對應的修改，請考慮以下狀況，分別解釋對應的程式碼是否能運作。
### 解題
做這個測驗時，發現計算機組織忘記許多，備受打擊。但忘記就跟不會一樣意思，因此也不需要找藉口，只好回到白算盤尋覓過去的時光。
#### Q11:
**做了 `1: Stuck at 0 left of cut` 的修改，`sw $s1, 0($s2)` 能否運作？**
根據上面的這張圖(參考連結在最下方)，知道了這條線是控制 MemtoReg RegWr 這兩條訊號線，因此若沒有了這條線，Reg永遠不能被寫入， lw 、 add 等需要寫入 reg 的指令都會失效。
而sw不會失效，因為他不牽涉到寫回 reg 的動作。因此這題的答案是==可以運作==。
#### Q12:
**承上，下方程式能否運作？**
```
lw $s1, 0($s2)
add $s1,$2,$3
```
因為 lw 牽涉到寫回 reg ，而因為切掉這條訊號線導致 reg 不能被寫入，因此這個指令不能被運作。(第二個指令也不能運作，因為 add 需要加起來後把答案寫入 reg $s1)。答案是==不能運作==
#### Q21:
**做了 `2: Cut here` 的修改後，以下程式能否運作？**
```
add $s1, $s1, $s1
add $s1, $t0, $t1
```
這題的訊號線連接到的這個 mux ，是用來做選擇進入 ALU 的第一個 operand 來自 指令的部分，抑或是 Data forwarding 取上一個指令的值，這裡必須注意的是，只切了其中一條，因此 $Rs 或 $Rt 其中一個仍可以正常 Forwarding。
回頭看題目發現，這裡並不需要 Data forwarding ，因為這裡沒有 Data Hazard 發生，因此這題的答案為==可以運作==
#### 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
```
觀察3這條訊號，發現它是傳送 PC+4+(imm\*4) 的值，而最後會送到 program counter 前的 mux 選擇要取的值。因此若把這條線去掉了，則會使 beq bne 這種需要 PC+4+(imm\*4) 的 branch 指令失效。
回到題目發現這題沒有用到 bne beq 這類指令，而是用 jump ，因此這題答案是==可以運作==。
#### Q32:
**承上，以下程式能否運作？**
```
addi $s2, $zero, 2
addi $s1, $zero, 2
beq $s2, $s1, exit
```
這裡有用到 beq ，因此答案是==無法運作==。
## 參考資料
* [計算機組織結構](https://hackmd.io/s/H1sZHv4R#)
* 白算盤書 & 計算機組織林英超老師上課講義
Sign in with Wallet
Connect another wallet