2022q1 Homework2 (quiz2)

contributed by < Korin777 >

測驗一

延伸問題一

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

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

• 先將大數中的 low 提出後 , 在對兩數差取平均

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

• (a >> 1) + (b >> 1) 相當於 2/a + 2/b ， 當兩數皆為奇數時多出來的餘數會使得 a/2 + b/2比(a+b)/2少1
• 因此我們要判斷兩數是否皆為奇數 , 透過檢查最低位元是否為1(即&1)來達成

uint32_t average(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

• a & b會找出2進位表示中 , 兩數皆為1的位元
• a ^ b會找出2進位表示中 , 只有一數為1的位元
• 而後者因為來源只有一數 , 所以要在除以2

延伸問題二

透過 objdump -d 來查看對應的組合語言輸出

1. (a + b) / 2
   ​​​​lea    (%rdi,%rsi,1),%eax
   ​​​​shr    %eax
   ​​​​retq   
   

   • rdi : 儲存函式第一個 argument ,rsi : 儲存函式第二個 argument
   • eax : return value ,為 rax 的 Low 32-bits
   • (%rdi,%rsi,1) : rdi 裡的值與 1 倍的 rsi 裡的值的和 => a + b
   • lea (%rdi,%rsi,1),%eax : 複製 (%rdi,%rsi,1) 的值到 %eax => %eax = a + b
   • shr %eax : 將 %eax 裡的值右移一位 => %eax = (a + b) / 2
   • retq : 結束 callee, 回到 caller 原本執行的地方
2. low + (high - low) / 2
   ​​​​mov    %esi,%eax
   ​​​​sub    %edi,%eax
   ​​​​shr    %eax
   ​​​​add    %edi,%eax
   ​​​​retq
   

   • edi : 儲存函式第一個 argument ,esi : 儲存函式第二個 argument
   • rdi 佔 64 bits,而 edi 則是 rdi 的 Low 32-bits
   • mov %esi,%eax : 將 %esi 裡的值複製到 %eax => %eax = low
   • sub %edi,%eax : 將 %eax 裡的值與 %edi 裡的值差存在 %eax => %eax = low - high
   • shr %eax : %eax = (low - high) / 2
   • add %edi,%eax : 將 %eax 裡的值與 %edi 裡的值和存在 %eax => %eax = low + (low - high) / 2
3. (a >> 1) + (b >> 1) + (a & b & 1)
   ​​​​mov    %esi,%edx
   ​​​​shr    %esi
   ​​​​and    $0x1,%edx
   ​​​​and    %edi,%edx
   ​​​​shr    %edi
   ​​​​add    %edx,%edi
   ​​​​lea    (%rdi,%rsi,1),%eax
   ​​​​retq
   

   • %edx : 儲存函式第三個 argument,因為函式只有兩個參數,這裡應該是用來暫存計算中的值
   • mov %esi,%edx : %edx = a
   • shr %esi : %esi = a >> 1
   • and $0x1,%edx : 將常數 0x1 與 %edx 裡的值做 & 運算並存在 %edx => %edx = a & 1
   • and %edi,%edx : %edx = a & 1 & b
   • shr %edi : %edi = b >> 1
   • add %edx,%edi : %edi = (b >> 1) + (a & b & 1)
   • lea (%rdi,%rsi,1),%eax : %eax = (a >> 1) + (b >> 1) + (a & b & 1)
4. (a & b) + ((a ^ b) >> 1)
   ​​​​mov    %edi,%eax
   ​​​​and    %esi,%edi
   ​​​​xor    %esi,%eax
   ​​​​shr    %eax
   ​​​​lea    (%rax,%rdi,1),%eax
   ​​​​retq
   

   • mov %edi,%eax : %eax = a
   • and %esi,%edi : %edi = a & b
   • xor %esi,%eax : %eax = a ^ b
   • shr %eax : %eax = (a ^ b) >> 1
   • lea (%rax,%rdi,1),%eax : %eax = (a & b) + ((a ^ b) >> 1)

參考資料

• Guide to x86-64
• CS107, Lecture 11
  Assembly: Arithmetic and Logic

測驗二

延伸問題一

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

• 當 b > a
  1. a ^ ((a ^ b) & 0xffff) => x & 1 = x
  2. a ^ (a ^ b) => xor associative
  3. (a ^ a) ^ b => x ^ x = 0
  4. 0 ^ b => 0 ^ x = x
  5. b
• 當 a >= b
  1. a ^ ((a ^ b) & 0) => x & 0 = 0
  2. a ^ 0 => x ^ 0 = x
  3. a

延伸問題二

參考上面 32 位元無號整數實作，撰寫針對 32 位元有號並同樣 branchless 的實作

int32_t max(int32_t a, int32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

• 可以從上面的推導得知,整數有號或無號並不會影響上面的各個運算結果,因此只須將參數及回傳值型態改為 int32_t

測驗三

延伸問題一

#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 (u | v);
    return u << shift;
}

1. 當 u 為 0 回傳 v , 反之回傳 u , 兩者皆為 0 回傳 0
2. 當 u 和 v 皆為偶數 ,
   $gcd(u,v)=2\ast gcd(\frac{u}{2},\frac{v}{2})$ , shift 用來記錄之後要乘回 2 多少次
3. 如果 u 還是偶數 , 因為 v 是奇數
   $gcd(u,v)=gcd(\frac{u}{2},v)$
4. 透過輾轉相除法來求出 u 和 v 的最大公因數 , 在這過程中因為 u 一直保持為奇數 , 因此
   $gcd(u,v)=gcd(u,\frac{v}{2})$
5. 最後要將這個最大公因數乘回 2 的 shift 次方
   註 :while(u | v) 應該改成 while(v),否則會陷入無窮迴圈,因為 v 才是過程中會減到 0 的數, 而 u 則是最大公因數

延伸問題二

透過 __builtin_ctz 改寫 GCD

uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift, shitf_u = __builtin_ctz(u), shift_v = __builtin_ctz(v);
    shift = shitf_u ^ ((shitf_u ^ shift_v) & -(shitf_u > shift_v));
    u >>= shitf_u, v >>= shift_v;
    do {
        shift_v = __builtin_ctz(v);
        v >>= shift_v;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

測驗四

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

• 上面函式會將 bitmap 資料中 , 出現 1 的位置記錄在 out , 並回傳 bitmap 出現 1 的次數 pos
  • 假設 bitmap[i] 資料為 3 個 bit
  • bitmapsize : 2
  • bitmap: bitmap[0] = 3'b101 , bitmap[1] = 3'b010
  • out : [0,2,4]
  • pos : 3

#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 = bitset & -bitset;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

• 一個數的2補數會將比該數 1 的最低位元還低位的位元都變成 0 => 可知上述位元皆為 0 , 1補數變成 1 , 加一變為2補數上述位元變為 0 , 而 1 的最低位元依舊為 1 ; 高位元則會跟原數相反
• 因此可以得知 bitset & -bitset 會保留 bitset 中 1 的最低位元 , 而將其他位元變成 0
• 再透過 XOR 就可以把該位消除 , 並保留其他位元
• 相比於原本需要將 bitmap 資料都看過一遍 , 這裡每次就只會看位元為 1 的位置

測驗五

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

    strcpy(p, decimal); // 沒循環小數
    return result;
}

• rem_node->key 儲存已經出現過的餘數,當在一次遇到同樣的餘數,表示小數循環了
• rem_node->index 儲存該餘數前有幾個數,這些數為小數沒循環的部分
  註:sprintf(p, "%ld", division > 0 ? (long) division : (long) -division); 應可改為 sprintf(p, "%ld", division);,因為 division = n / d 又 n、d 皆為正數

測驗六

/*
 * 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)->_h) - (char *)0)

• Structure Padding : a struct instance will have the alignment of its widest scalar member
• 因為 struct 中 type t 最小也只會跟 char 一樣佔 1 byte,所以 struct 一定會跟 type t 對齊
• 因此先將 struct 地址變更為 0 ,再加上成員 _h 的偏移量就可以知道 type t 對齊幾個byte
• pointer 的運算都是遞增或遞移 1 個「單位」, (char *) - 1 會減少1 byte,而 (float *) - 1 則會減少 4 byte,這也是為什麼要強制轉型成 (char *),因為我們不知道前面是什麼pointer,而當後面不是減 0 時,可能會產生上述的錯誤
• 參考資料
  • Linux 核心原始程式碼巨集: container_of
  • The Lost Art of Structure Packing
  • The (char *) casting in container_of() macro in linux kernel

測驗七

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 << div3) << div5;

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

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

• 如果單獨為 3 或 5 的倍數字串長度 length 為 4 , 同時為 3 及 5 的倍數字串長度為 8,因此可得知 length = 2 << div3 << div5
• 不為 3、5、15 的倍數印出數字本身,在字串 index 為 8 的位置,此時 KK3 應為 0
• 5 的倍數印出 "Buzz" ,在字串 index 為 4 的位置,即 8 >> div5,此時 KK3 應為 0
• 3 及 15 的倍數分別印出 "Fizz" 和 "FizzBuzz" ,在字串 index 為 0 的位置,兩者會使 div3 為 1,又 3 的倍數會使 div5 為 0,可知 8 >> KK3 應為 0,因此可知 KK3 >= 4 即 div3 << 2
  註:strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length); 中的 9 應改為 8,因 "%u" 開頭在字串 index 為 8 的位置

題目連結