D06: c-review

contributed by < rex662624 >

第 4 週測驗題

測驗 `1`

解題

1. FuncA 的作用是
















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 的作用是









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 的作用是












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

不過這裡好像有幾個沒有考慮的點:

若是 start 是指向 NULL ，也就是尚未有任何 node 的時候，則程式應該會 core dumped ，因為有 temp->data 這個動作。
若是根本沒有 value2 這個值，會進入無限迴圈，因為這是 circular linked list ，一路 next 到尾巴後又會從頭開始，永遠無法結束。因此user 必須自己保證 list 內一定有 value2 。

4. 在程式輸出中，訊息 `Traversal in forward direction` 後依序印出哪幾個數字呢？

首先先看main








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 後做了





    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]

程式碼:






    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` 的作用是

首先觀察程式碼






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 >>`後面接的輸出為何
























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。

再來繼續觀察程式碼


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


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。



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 週測驗題 (上)

測驗 `1`

考慮以下程式碼，推敲其作用 (選出最符合行為的描述)




uint8_t Func32(uint32_t x) {
    return x ? Func32(x >> 1) - 1 : 32;
}

將 Func32 改寫為以下功能等價的程式碼:











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 。

這裡是利用 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
e94046165

感謝指正!的確 x 在中間就會被改值了。所以你說的是對的，若是偶數個 0 的狀況，因為 n 初值是1，最後跑完 if 就都會多1，要在第9行做處理。
rex662624

測驗 `2`

解題

Func64 的作用為？




















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



























































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) | dividend0) 這裡後面的 divided0 是整除的情況跳出機制，所以可以推測 ~(P1) 是不整除的情況，也就是要用到 mask 來看商數是否已經夠長了。所以用 mask>>1 ，每次 while 迴圈算出一位數就右移一位，直到最後 mask ==0就跳出，因此P1:mask>>=1

同理可以推廣到下面的 64-bit 版本。這裡加上了一些除錯的機制。例如第27行是用來偵測是否除以0。

而這裡的答案P2=bits - -，與 32-bit 的跳出機制相同，都是偵測商數是否已經到達目標位數。






























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)₁₀=(0x30)₁₆。這裡參考e94046165 同學找出的錯誤。

最後 P4 的部分，是因為我們要印出十進位，所以我們每次都要除10，如同我們如果要 1bit 1bit 印出二進位值，必須要用 number>>1(就是number/2)一樣。

第 5 週測驗題 (中)

解題

首先理解題目jserv++C ：

puts((char *) &(double []){ 3823806048287157.0, 96 });這行，把3823806048287157.0這個數字用 char * 型態印出來，因此透過轉換我們知道了在記憶體內的真實儲存資料為01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010
而因為一個字元就佔了 1byte ，所以我們可以知道上面的數字要用 8 bits為一個單位切割。透過轉換我們知道，答案會是 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)

修改程式，允許輸出你的 GitHub 帳號名稱

程式碼如下：






#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 ， string to binary ，可以知道 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














#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 來說:

因為由上面的轉換，我們知道轉換出來的答案其實是 C++vresj ，因此只要存入 jserv++C 的數值，在big-endian 的環境就能達到正確的效果。
參考 stackoverflow 。也可以不改變數值，但是另外用一個函式ReverseFloat() 一個一個 char 轉過來。(注意網址中是只有32 bits ，因此只有 4個 char 空間，而若是適用於這題需要 0~7 ，8個空間。)

就題目主體gen()來說:

與上一題的2.相同，gen()完再呼叫 ReverseFloat() 把它一個一個char轉過來。
因為本來 C++vresj ，改為 I++vresj ，改變的是最前面的一個 byte 數值而已。而若是在 big-endian 的環境下則改變的是最後一個 byte 。因此不關 exponent 的事，而是要改 mantissa 部分，因此要用加減法去做改變 mantissa。

第 5 週測驗題 (下)

考慮某款 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 ，因此答案是無法運作。

參考資料

計算機組織結構
白算盤書 & 計算機組織林英超老師上課講義

D06: c-review

第 4 週測驗題

測驗 1

解題

1. FuncA 的作用是

2. FuncB 的作用是

3. FuncC 的作用是

4. 在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？

5. 在程式輸出中，訊息 Traversal in reverse direction 後依序印出哪幾個數字呢？

測驗 2

解題

1. FuncX 的作用是

2. ~ 6. K1 >> ~ K5 >>後面接的輸出為何

7. count >> 後面接的輸出為何

第 5 週測驗題 (上)

測驗 1

解題

測驗 2

解題

第 5 週測驗題 (中)

解題

延伸題目(github)

修改程式，允許輸出你的 GitHub 帳號名稱

修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)

如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？

第 5 週測驗題 (下)

解題

Q11:

Q12:

Q21:

Q31:

Q32:

參考資料

測驗 `1`

4. 在程式輸出中，訊息 `Traversal in forward direction` 後依序印出哪幾個數字呢？

5. 在程式輸出中，訊息 `Traversal in reverse direction` 後依序印出哪幾個數字呢？

測驗 `2`

1. `FuncX` 的作用是

2. ~ 6. `K1 >>` ~ `K5 >>`後面接的輸出為何

7. `count >>` 後面接的輸出為何

測驗 `1`

測驗 `2`

修改 gen() 函式，透過特定的轉換，讓 `m[]` 的內容變為你的英文姓氏 (last name)