Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < rickywu0421 >
題目連結

測驗 1

題目

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

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

這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:

#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

接著我們可改寫為以下等價的實作:

#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);
}

解題

第一種實作方式為將 a 與 b 分別 right shift 1 bit 後相加, 此時還考慮到進位: a 與 b 的 LSB 是否都為 1, 故 EXP1 = a & b & 1。

第二種實作方式為加法器的概念, x ^ y 表示為位元和, x & y 表示為進位, 則
a + b = x ^ y + (x & y) << 1 =>
(a + b) / 2 = ((x ^ y) + (x & y) << 1) >> 1 = (x & y) + (x ^ y) >> 1
故 EXP2 = x & y, EXP3 = x ^ y

測驗 2

題目

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

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

解題

我們可以透過回傳值猜測題目中的表示式：

  • 當 a > b 時, 回傳 a;
  • 當 b > a 時, 回傳 b;

又 XOR 有兩個特性 (x 為任一整數)：

  • x ^ x = 0
  • 0 ^ x = x

故我們可以使用這兩個特性猜測題目的解,

  • 當 a > b 時, 回傳 a ^ 0 = a
  • 當 a < b 時, 回傳 a ^ a ^ b = b

因此 EXP4 = a ^ b。

再根據上面的判斷, a > b 時 EXP4 & -(EXP5) = 0, a < b 時 EXP4 & -(EXP5) = a ^ b 可知, EXP5 在 a > b 時為 0, 在 a < b 時為 -1 (全部位元為 1), 故可知 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;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

#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;
}

解題

第二種實作與第一種實作均是輾轉相除法, 但作法略為不同, 第一種利用除法運算, 而第二種利用減法運算, 以下是運算時會用到的操作, 以及對應的程式碼片段：

  1. gcd(0,0)=0
  2. gcd(u,0)=u    ,
    gcd(0,v)=v
if (!u || !v) return u | v;
  1. 若
    u     與
    v     均是偶數, 則
    gcd(u,v)=2∗gcd(u2,v2)
for (shift = 0; !((u | v) & 1); shift++) {
    u /= 2, v /= 2;
}
  1. 若
    u     為偶數,
    v     為奇數, 則
    gcd(u,v)=gcd(u2,v)
while (!(u & 1))
    u /= 2;
  1. 若
    u     為奇數,
    v     為偶數, 則
    gcd(u,v)=gcd(u,v2)
while (!(v & 1))
    v /= 2;

這個部分的程式碼是在 do-while loop 裡的, 因為每次 loop 完 v 都會更新而有機會變成 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;

loop 中首先進行上述的操作 5, 接著判斷

u 與
v 兩者誰大, 用大數剪去小數,
v 值更新為相減後的數,
u 值更新為
u,
v 中較小的數, 重複進行上述操作直到兩數相減為 0。

故 COND = v, return 值則需要乘上透過操作 3 除去的倍率 (2 的冪), 故 RET = u << shift。

測驗 4

題目

在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼:

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

考慮 GNU extension 的 __builtin_ctzll 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。

範例: 當 a = 16
16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
從低位元 (即右側) 往高位元，我們可發現
0 → 0 → 0 → 0 → 1，於是 ctz 就為 4，表示最低位元往高位元有 4 個 0

用以改寫的程式碼如下:

















#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 的特性)。

若 bitmap 越鬆散 (即 1 越少)，於是 improved 的效益就更高。

解題

根據原程式碼片段：

size_t p = k * 64;
for (int i = 0; i < 64; i++) {
    if ((bitset >> i) & 0x1)
        out[pos++] = p + i;
}

其意義為從 LSB, 迭代檢查 bitset 的該 bit 是否為 1, 若是, 則 out[pos++] = k * 64 + 該 bit 的位置。

改良的程式碼片段如下：

uint64_t t = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;

其概念為透過 __builtin_ctzll() 找出 bitset 中從低位元往高位元數來的第一個 1, 再透過 bitset ^= t 把那一個 1 clear, 以便進行下一個 set bit 的搜索。

假設 bitset = 0001 0100, 則做完一次上述的操作後位置 2 的 bit 會被 clear：bitset = 0001 0000, 而要怎麼達成這件事呢？

根據題目的提示 (-bitset), 根據二補數, -bitset = 1110 1100, 我們可發現, 將 t = bitset & -bitset 後可以得到一個 bit string = 0000 0100, 其只有一個 bit 被 set, 那就是 bitset 中最小位元為 1 的位置, 之後再透過 bitset ^= t 把 bitset 中最小位元的 1 clear 掉 (根據 xor 的特性), 故 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;
}

解題

以下我們以循環小數

12/11=0.090909... 作為該題的例子。

該題記錄小數的作法為：用 hash table 記錄每次迭代的餘數及其在小數中的位置。

iter 1

每次迭代時首先會檢查該次的餘數是否存在於 hash table 中,

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;

但首次進入迴圈時因尚未有餘數加入到 hash table 中, 故 if 判斷不成立, 所以我們先往後看：

以下操作不難看出為將目前的餘數及餘數的位置加入到 hash table 中, 以當前的狀態, 餘數為 12 % 11 = 1, index 為 i = 0。

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

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

加入 hash table 後將餘數 * 10 後除以除數：
*q++ = (1 * 10) / 11 + '0' = '0' =>result = '0'
餘數則進行以下更新：
remainder = (1 * 10) % 11 = 10。

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

iter 2

此時 remainder = 10, 故以下條件仍然不成立。

int pos = find(heads, size, remainder);

之後的操作與 iter 1 類似, 接近 loop end 時
*q++ = (10 * 10) / 11 + '0' = '9' => result = '09'
remainder = (10 * 10) % 11 = 1

iter 3

此時 remainder = 1, 故 if 條件成立：

第一個 while loop 的功能為是將像 1.34(15) 中未循環的小數寫入 result 中, 故 PPP = pos--。(12 / 11 中不存在未循環的小數)。

之後將循環的小數用小括號包起來, 最後回傳 result = '0.(09)'。

if (pos >= 0) {
    while (PPP > 0)
        *p++ = *decimal++;
    *p++ = '(';
    while (*decimal != '\0')
        *p++ = *decimal++;
    *p++ = ')';
    *p = '\0';
    return result;
}

測驗 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)

解題

透過題目的 struct { char c; t _h; } 可以猜到 __alignof__ 的實作想法為將欲驗證的 type 之變數宣告在 struct 中的 char 變數之後, 透過 _h 的位置減去 c 之位置可得之 type t 之 alignment。

故 M = _h, 則 ((char *)(&((struct { char c; t _h; } *)0)->_h) 表示為變數 _h 的相對於 struct 起始的位置, 又因起始位置為 0, 則 X = 0。

測驗7

題目

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

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

直覺的實作程式碼如下: (naive.c)

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        if (i % 3 == 0) printf("Fizz");
        if (i % 5 == 0) printf("Buzz");
        if (i % 15 == 0) printf("FizzBuzz");
        if ((i % 3) && (i % 5)) printf("%u", i);
        printf("\n");
    }
    return 0;
}

觀察 printf 的(格式)字串，可分類為以下三種:

  1. 整數格式字串 "%d" : 長度為 2 B
  2. “Fizz” 或 “Buzz” : 長度為 4 B
  3. “FizzBuzz” : 長度為 8 B
    考慮下方程式碼:
char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 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"[(8 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

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

其中 is_divisible 函式技巧來自 Faster remainders when the divisor is a constant: beating compilers and libdivide，甚至 gcc-9 還內建了 FizzBuzz optimization (Bug 82853 - Optimize x % 3 == 0 without modulo)。

請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。

對於處理器來說，每個運算所花的成本是不同的，比如 add, sub 就低於 mul，而這些運算的 cost 又低於 div 。依據〈Infographics: Operation Costs in CPU Clock Cycles〉，可發現整數除法的成本幾乎是整數加法的 50 倍。

作答區
KK1 = ? (變數名稱)
KK2 = ? (變數名稱)
KK3 = ? (表示式，不包含小括號)

解題

首先看題目的這段敘述：

string literal: "fizzbuzz%u"
        offset:  0   4   8

根據是否能被 3 (div3) 或 5 (div5) 整除而產生的 offset 以及 length 變化可以做成下列表格, 以下欄位以 (div3, div5) 呈現：

(div3, div5) (0, 0) (1, 0) (0, 1) (1, 1)
offset 8 0 4 0
length 2 4 4 8

回到程式碼, 根據上述表格可以作答：

  • length 部分
uint8_t div3 = is_divisible(i, M3);
uint8_t div5 = is_divisible(i, M5);
unsigned int length = (2 << KK1) << KK2;

KK1 = div3, KK2 = div5

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

KK3 = div3 << 2

Last changed by 
 
吳恩緯
1
382

Read more

2022q1 vwifi

contributed by < rickywu0421 > sysprog21/vwifi [toc] PR #27 - Implement real AP and STA mode [ ] commit: 97f03a

Nov 15, 2022
2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi)」作業 1

&#x5FC3;&#x5BBF;&#x4E8C; - Alpha Scorpii &#x1F43C; : interviewer &#x1F436; : interviewee &#x6A21;&#x64EC;&#x9762;&#x8A66;&#x9304;&#x5F71;(&#x6F22;) &#x6A21;&#x64EC;&#x9762;&#x8A66;&#x9304;&#x5F71;(&#x82F1;) 226. Invert Binary Tree &#x540C;&#x5115;&#x6AA2;&#x8A0E; interviewer

Oct 23, 2022
wtap 備份

install a jail from an ISO export DESTDIR=/usr/jail/net80211_0 sudo mkdir -p $DESTDIR Mount the install media on /mnt(change cdimage.iso to your ISO). sudo mount -t cd9660 /dev/`mdconfig -f cdimage.iso` /mnt cd /mnt/usr/freebsd-dist/ Install just the base system.

Jun 12, 2022
2022-04-04 [rickywu0421](https://github.com/rickywu0421?tab=repositories)

&#x6E2C;&#x9A57; 1 &#x984C;&#x76EE; #include <stddef.h> #include <stdint.h> #include <limits.h> #include <string.h> /* Nonzero if either X or Y is not aligned on a "long" boundary */ #define UNALIGNED(X) ((long) X & (sizeof(long) - 1))

Apr 5, 2022
Read more from 吳恩緯
Published on HackMD