Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < StevenChou499 >

測驗 1

考慮以下對二個無號整數取平均值的程式碼:






#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

我們再次改寫為以下等價的實作:





uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

思考與想法

題目中的第一題因為想到要做平均，所以應該要用 >> 來做除以二的動作。但是因為再二進位制中，若兩數的同一位皆為 1 則需要進位，而只有 & 可以提取出兩數同時出現的 1 ，因此 EXP1 應該是 a & b 才對。

而下一題的在再次改寫，因為後面有一個 >> 1 ，應該是除以二的結果，而如果 a 與 b 皆需要除以二，應該以 ^ 的方式提取兩者各單獨擁有的位元，再使用 & 來找出兩者共同擁有的位元，而因為＼兩者皆擁有此位元，所以不需要進行除以二的動作。所以 EXP2 為 a & b ，且 EXP3 為 a ^ b 。

EXP1 : a & b
EXP2 : a & b
EXP3 : a ^ b

延伸問題

比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用

測驗 2

改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):






#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

思考與想法

因為答案需要回傳 a 或是 b ，所以首先想到的是若要回傳 a 則需要利用 ^ 的特性，也就是任何數值在與 0 做 EXR 後，還會是自己本身。因此我們可以知道 ((EXP4) & -(EXP5)) 等於 0 。而若是需要回傳 b ，則可以想到 b 在與 a 做兩次 ^ 後又會回到 b ，因此若需要回傳 b ，則 ((EXP4) & -(EXP5)) 等於 a ^ b ，以下為兩種結果的表格：

情況 a > b (回傳a) a < b (回傳b)
((EXP4) & -(EXP5)) 0 a ^ b

而因為需要回傳 0 或是 a ^ b 且中間還需要做 & 的操作，因此 (EXP4) 應該要等於 a ^ b ，且 -(EXP5) 在 a > b 時應該要等於 0x0 ，在 a < b 時應該要等於 0xFFFFFFFF ，也就是 -1 。依據這樣的條件，在加上去除加上負號後的轉換， (EXP5) 應該要是 0 或 1 ，因此 (EXP5) 應該為 (a < b) ，此時若 a > b ，會回傳 0 ，加上負號後為 0 ，與 a ^ b 做 ^ 後為 0 ，而 a ^ 0 等於 a ，就會回傳 a 。若 a < b ，會回傳 1 ，加上負號後為 0xFFFFFFFF ，與 a ^ b 做 ^ 後為 a ^ b ，最後則會回傳 b，以下為詳細講述計算過程的表格：

情況 a > b (回傳a) a < b (回傳b)
a < b 0 1
-(a < b) 0x0 0xFFFFFFFF
a ^ b a ^ b a ^ b
(a ^ b) & -(a < b) 0 a ^ b
a ^ (a ^ b) & -(a < b) a b

因此我們可以得知 EXP4 等於 a ^ b ， EXP5 等於 a < b 。

EXP4 : a ^ b
EXP5 : a < b

延伸問題

測驗 3

考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:
























#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);
    return RET;
}

思考與想法

因為是要求兩數之最大公因數，因此前面的程式碼:




for (shift = 0; !((u | v) & 1); shift++) {
    u /= 2, v /= 2;
}

此階段為利用 shift 紀錄下總共有幾次方的 2 兩數可以進行整除，






while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;

接著下方的程式碼則是將剩下無法成為公因數的 2 去除。

而最後一段的 do while 迴圈則可以看出是用來計算最大公因數的輾轉相除法。而輾轉相除法的結束條件為兩數字相等也就是兩者相減為 0 ，且因為當最後兩數相等時， do while 迴圈中會進入 else 的流程，此時 v 會等於 0 ，因此 while 結束的條件為 v == 0 ，所以 COND 為 v ，當 v 不為 0 時代表還需要進行下一次的輾轉相除法，直到 v 等於 0 為止。而因為最後要回傳兩者之最大公因數，此時之 u 為去除二倍數之最大公因數，所以最後還需要再利用一開始求出的 shift 乘回算出來的 u ，因此 RET 為 u << shift 。

COND : v
RET : u << shift

延伸問題

測驗 4

改寫的程式碼如下:

















#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;
        }
    }
    return pos;
}

其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 000101b，那 t 就會變成000001b，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

思考與想法

因為變數 t 是想要將原數字中二進位最低位的 1 保留下來，而由二補數系統(two's complement)的定義，一數字在加上 - （負號）並與原本的數相加後，會因為一直進位而變成零，而最一開始進位的位置就是該數在二進位制中最低位的 1 。因此 EXP6 等於 bitset & -bitset ，這樣第一次進位的位置即是兩數同時擁有 1 的位置。

     6    0110
    -6    1010
  + -----------
     0 (1)0000
            ^
            -開始進位的位置(同時都擁有1)
6 -6 6 & -6
0110 1010 0010

EXP6 : bitset & -bitset

延伸問題

測驗 5

以下是 LeetCode 166. Fraction to Recurring Decimal 的可能實作：






































































































#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
    
struct rem_node {
    int key;
    int index;
    struct list_head link;
};
    
static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

    bool sign = (float) numerator / denominator >= 0;
    if (!sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

    strcpy(p, decimal);
    return result;
}

思考與想法

程式碼講解：
因為其程式碼有一定的長度，因此需要經過 trace code 再做完整的判斷會比較好。

先從程式開始執行的第24行開始：



























char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

此段是在配置足夠的記憶體來存取在做運算後的小數點，並先將分母以及分子為零的狀況排除。

接著是第55行：







    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

此段主要是先計算出該數的商數與餘數，接著利用 sprintf 將 division 存入 %ld 再轉成 char 存入 p 。

第62行：










    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

此段是將小數點加入 p ，再定義一個存放小數的變數 decimal ，配置空間後再用 memset 轉換其全部內容成 0 。

第72行：





    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);

此段開始要真正做小數運算的動作，先重新定義 size 為 1333 ，接著定義一個 heads 並配置記憶體，在利用 INIT_LIST_HEAD ，依序進行初始化。

第77行：













    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }

接著利用 for 迴圈開始進行計算，透過呼叫 find 函式找出是否有相同的 key ，若有則回傳他的 index ，若無則回傳 -1 。

  • find 函式：










static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

而獲得 pos 後，變可以印出小數點的數值，並回傳 result 。

第89行：









        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;

若沒有找到相同的 key ，則需要將其 remainder 與 i 記錄下來，並將其存入配置圍成的 struct list_head* 中，接著最後兩行是存入當前餘數 remainder 的數值至 q 與更新 remainder 的數值。此處的 + '0' ，其實為加上 48 ，將餘數算出後型態從 long long 轉換至 char 。

以下為解釋(以 remainder = 3, d = 6 為例)：

    (remainder * 10) / d + '0';
         3     * 10  / 6 + '0';
             30      / 6 + '0';
                       5 + '0';
                       5 +  48;
                       53 = '5'; // 利用 + '0' 將int轉換成char

0~9 之ASCII編碼：

Binary Decimal Character
0110000 48 0
0110001 49 1
0110010 50 2
0110011 51 3
0110100 52 4
0110101 53 5
0110110 54 6
0110111 55 7
0111000 56 8
0111001 57 9

由上述的運作情況，我們可以知道 PPP 為 pos-- ，因為 pos 為記住小數點後不重複的位數，因此當 pos 等於零時，代表不重複的小數已經計算完了。而在後面的 MMM 與 EEE 則分別是 list_add 與 &heads[remainder % size] 。此處的用意是將餘數與位置放入 struct list_head 的結構 node* 當中，再利用 list_add 加入 head[remainder % size] 中。

整個運作上其實為一個雜湊表，透過雜湊表找出循環與非循環的小數。
以下為實際運作的示意圖（以分母為 90 ，分子為 102 為例）：

  • 找出第一次運算下的商數以及餘數 (102 / 90 = 1 … 12)
    long long n = numerator; // n = 102
    long long d = denominator; // d = 90
    long long remainder = n % d; // remainder = 12
    long long division = n / d; // division = 1
  • 將商數存入 result 並同時加入小數點
    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    // p = result = 1
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.'; // result = 1.
                            ^ ^
                  result的位置 p的位置
  • 初始化 decimal 並準備存入小數
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;
    // q = decimal = '000000000000000...'
  • 建立一雜湊表並初始化
    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);







INIT



heads1332

prev

heads[1332]

next



heads1332:p1332->heads1332:f1332





heads1332:n1332->heads1332:f1332





omit
.
.
.



heads2

prev

heads[2]

next



heads2:p2->heads2:f2





heads2:n2->heads2:f2





heads1

prev

heads[1]

next



heads1:p1->heads1:f1





heads1:n1->heads1:f1





heads0

prev

heads[0]

next



heads0:p0->heads0:f0





heads0:n0->heads0:f0
  • 進入第一個 for 迴圈 (i = 0):
    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (pos-- > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        list_add(&node->link, &heads[remainder % size]);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

pos 回傳為 -1 ，引此不會進入 if 條件式，並且把 remainder 與 i 加入 node* ，並透過 list_add 加入 heads[remainder % size] ，即為 heads[12] 。







INIT



heads1332

prev

heads[1332]

next



heads1332:p1332->heads1332:f1332





heads1332:n1332->heads1332:f1332





omit1
.
.
.



heads12

prev

heads[12]

next



heads12:p12->heads12:f12





node1

prev

node

next

index = 0

key = 12



heads12:n12->node1:n





omit
.
.
.



heads0

prev

heads[0]

next



heads0:p0->heads0:f0





heads0:n0->heads0:f0

加入雜湊表後，接著將餘數記住並加入 q 中，並且重新計算下一次的餘數

        *q++ = (remainder * 10) / d + '0'; // q = 1
        remainder = (remainder * 10) % d; // remainder = 30
  • 再次進入下一個 for 迴圈 (i = 1):
    進入 for 迴圈後， pos 會回傳 -1 ，接著再次加入 heads[30] 中。






INIT



heads1332

prev

heads[1332]

next



heads1332:p1332->heads1332:f1332





heads1332:n1332->heads1332:f1332





omit2
.
.
.



heads30

prev

heads[30]

next



heads30:p30->heads30:f30





node2

prev

node

next

index = 1

key = 30



heads30:n30->node2:n





omit1
.
.
.



heads12

prev

heads[12]

next



heads12:p12->heads12:f12





node1

prev

node

next

index = 0

key = 12



heads12:n12->node1:n





omit
.
.
.



heads0

prev

heads[0]

next



heads0:p0->heads0:f0





heads0:n0->heads0:f0

接著再次紀錄商數至 q ，並刷新餘數。

        *q++ = (remainder * 10) / d + '0'; // q = 1.3
        remainder = (remainder * 10) % d; // remainder = 30
  • 第三次進入 for 迴圈(i = 2):
    進入 for 迴圈後， find 函式會進入 heads[30] 尋找相同的 key ，找到相同的 key 後，便會回傳 1 給 pos 。接著進入 if 判斷式，將 decimal 的內容複製給 p ，因為 pos 等於 1 ，所以只會將 decimal 的第一位的 1 複製給 p ，此時 result 為 1.1 。加上 ( 並複製剩下的內容直到遇到 \0 ，最後在加上 )\0 即可回傳。
        int pos = find(heads, size, remainder); // pos = 1
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++; // result = 1.1
            *p++ = '('; // result = 1.1(
            while (*decimal != '\0')
                *p++ = *decimal++; // result = 1.1(3
            *p++ = ')'; // result = 1.1(3)
            *p = '\0'; // result = 1.1(3)\0
            return result;

PPP : pos–
MMM : list_add
EEE : &heads[remainder % size]

測驗 6

__alignof__ 是 GNU extension，以下是其可能的實作方式:

/*
 * ALIGNOF - get the alignment of a type
 * @t: the type to test
 *
 * This returns a safe alignment for the given type.
 */
#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

思考與想法

其程式碼講解：
先定義一個結構體其中擁有 char c 與 t _h 。

struct { char c; t _h; }

再將其結構之起始位置設定為 0 。

(struct { char c; t _h; } *)0

接著找出其結構中元素 _h 的位置。

((char *)(&((struct { char c; t _h; } *)0)->M)

最後與 X 的位置相減。

((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

因為 __alignof__ 就是計算 type t 的長度，所以 M 就是需要求的 _h ，而 X 就是 0 。

以 _h 是 int 為例：

#include <stdio.h>

#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)

int main(void)
{
    printf("%ld\n", ALIGNOF(int));
    return 0;
}

其結構實際樣貌：







INIT



memforint

char

 

 

 

int

int

int

int




                0:定義結構的起始位置為0
                |
                v
                |    |    |    |    |    |    |    |    |
                {char}              {        int        }
                ^                   ^
                |                   |
                0:char的起始位置      4:int的起始位置

其執行結果：

M : _h
X : 0

測驗 7

考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:

  • 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
  • 如果是 5 的倍數，印出 “Buzz”
  • 如果是 15 的倍數，印出 “FizzBuzz”
  • 如果都不是，就印出數字本身

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: ( bitwise.c )

static inline bool is_divisible(uint32_t n, uint64_t M)
{
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char **argv)
{
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << KK1) << KK2;

        char fmt[9];
        strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

思考與想法

因為題目要求依據各數字是否為 3 或 5 的倍數去做變化，而若只是 3 或是 5 的倍數只需要印出 Fizz 或是 Buzz ，所以我們可以知道 length 在皆否的情況下為 2 ，只為其中一數之倍數為 4 ，同時為兩數之倍數的話為 8 ，而剛好 2 << 1 等於 4 且 2 << 2 等於 8 。因此我們可以知道 KK1 與 KK2 分別為 div3 和 div5 ，也可以互換，因為不管先後都會作到 << 的動作。

情況 3 的倍數 5 的倍數 15 的倍數 皆不是
length 的數值 4 4 8 2

搞定 length 的問題後，後面的 strncpy 則是依據不同情況去複製不同位置以及大小之字串。若是 3 或是同時是 3 與 5 的倍數，則要從 0 的位置開始複製，若是單純 5 的倍數，要從 4 的位置開始複製，而若兩數皆不是的話則要從 8 的位置開始複製。

情況 3 的倍數 5 的倍數 同時為 3 與 5 的倍數 皆不是
開始複製之位置 0 4 0 8 
        strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);

而因為 div5 已經決定好了，所以若是單純為 5 的倍數， 9 >> 5 等於 4 ，剛好是開始複製的位置，此時 KK3 應該要為 0 。而若是 3 的倍數或是 15 的倍數，則需要一直位移直到數值為 0 ，便可以從起始位置開始複製，所以 KK3 應該是 div3 << 2 ，這樣在單純只為 3 的倍數的情況下，也可以讓 9 位移 4 次，變成 0 的結果。

但是當兩數皆不為倍數時，其值為 9 ，此時只會印出 u 的結果，與 8 的結果不符，因此 9 應該改為 8 ，這樣不會影響原本推導的結果，又可以讓兩數皆不為倍數的情況下複製並輸出正確的結果。

        strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);

KK1 : div3
KK2 : div5
KK3 : div3 << 2

Last changed by 
 
StevenChou43
0
418

Read more

Ring buffer 期末報告

contributed by < StevenChou499 > 進行 第 12 週測驗題第二題的延伸問題。過程中參照第 13 週測驗題第一/二題，嘗試開發出高效的 ring buffer。 相關資訊：[ ] ringbuffer 報告 [ ] Super Fast Circular Ring Buffer Using Virtual Memory trick [ ] Using black magic to make a fast circular buffer [ ] linear_ringbuffer/include/bev/linear_ringbuffer.hpp [ ] wuffs/script/mmap-ring-buffer.c

Feb 2, 2024
數位 IC 設計

ModelSim 在終端機使用方法 vlib <name> : 建立名為 name 的設計函式庫。 vlog <files> : 使用 ModelSim 編譯所有 files 的檔案。 vsim <top_level_module> : 使用 ModelSim 開啟編譯完成的檔案。 在 ModelSim 中輸入 run -all : 使用 vsim 開啟檔案後，輸入 run -all 可以執行模擬。 以下為範例 : PS C:\Users\StevenChou\Desktop\Verilog_practice\Chp5\Q3> vlib work ** Warning: (vlib-34) Library already exists at "work".

May 2, 2023
HW4 ATCONV

第一個成功版本 程式碼 : `timescale 1ns/10ps module ATCONV( input clk, input reset, output reg busy, input ready,

May 1, 2023
HDLBits 習題

HDLBits 連結 : https://hdlbits.01xz.net/wiki/Main_Page

Apr 19, 2023
Read more from StevenChou43
Published on HackMD