Try   HackMD

2022q1 Homework2 (quiz2)

contributed by < Xx-oX >

題目

測驗 1

考慮對兩個無號整數取平均值的程式碼

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

可以改寫成以下等價的實作

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

或者

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

填入 EXPx ，並

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

A

a >> 1 表示

⌊a2⌋
而
⌊a2⌋+⌊b2⌋ 在
a,b 均為奇數時，會比預期的結果少 1

e.g. a = 11, b = 13, 均為 unsigned (實行邏輯右移)

(11 >> 1) + (13 >> 1) 
= (b'1011 >> 1) + (b'1101 >> 1) 
= b'0101 + b'0110 
= b'1011 = 11

比預期的答案 (12) 少一
原因是右移會把 LSB 捨去，而兩個奇數 LSB 加總的進位也就被忽略了

因此，EXP1 要判斷 a, b 是否均為奇數，如果成立，則加上被捨去的 1
判斷奇數 => 判斷 LSB => 跟 1 做 & (AND) => a & b & 1

B

考慮半加器

s = a ^ b  //　和 a XOR b
c = a & b  //進位 a AND b

a 和 b 的平均 =

⌊a+b2⌋
比照 A 右移 s 而省略的 LSB 以及進位由 c 補上
因此

s = ((a ^ b) >> 1)
c = a & b

EXP2 填入 a & b
EXP3 填入 a ^ b

以 a = 11, b = 13 驗證

(11 & 13) + ((11 ^ 13) >> 1)
= (b'1011 & b'1101) + ((b'1011 ^ b'1101) >> 1)
= b'1001 + (b'0110 >> 1)
= b'1001 + b'0011 = b'1100 = 12

比較在編譯器最佳化開啟時的組合語言輸出

環境: gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
命令: gcc -S -O3 t.c

之後會嘗試改用 compiler explorer，以圖方便
測試程式 t.c

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

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

A 的對應組合語言

movl	%edi, %eax
movl	%esi, %edx
andl	%esi, %edi    ;// a & b
shrl	%eax          ;// a >> 1
shrl	%edx          ;// b >> 1
andl	$1, %edi      ;// (a & b) & 1
addl	%edx, %eax    ;// （a >> 1）+ (b >> 1)
addl	%edi, %eax    ;// 加上 (a & b & １)
ret

B 的對應組合語言

movl	%edi, %eax
andl	%esi, %edi    ;// a & b
xorl	%esi, %eax    ;// a ^ b
shrl	%eax          ;// (a ^ b) >> 1
addl	%edi, %eax    ;// 相加 
ret

發現 B 版本相比 A 版本

  • 少了 1 次 mov 操作
  • 少了 2 次 and 操作
  • 少了 1 次 shr 操作
  • 多了 1 次 xor 操作

註: 後綴 l 表示是針對 32-bit 暫存器的指令
TODO: 以第一手資料解釋

測驗 2

考慮以下程式碼

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

填入 EXPx ，並

  • 解釋上述程式碼運作的原理
  • 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
  • Linux 核心也有若干 branchless / branch-free 的實作，例如 lib/sort.c… 請在 Linux 核心原始程式碼中，找出更多類似的實作手法。(請善用 git log 檢索)

運作原理

參考用真假值表

⊕		 0 1
∧		 0 1
0 0 1 0 0 0
1 1 0 1 0 1

先不考慮兩者相等的情形
觀察程式碼，發現回傳 a ^ (…)
根據 XOR (

⊕, c:^) 的特性進行判斷

  • A⊕0=A 恆等律
    得知當
    a>b     時， (EXP4 & -(EXP5)) 的值為 0

  • A⊕B⊕B=A 自反律

由

A⊕A=0 歸零律 且
(A⊕B)⊕C=A⊕(B⊕C) 結合律 得知

得知當

a<b 時， (EXP4 & -(EXP5)) 的值為 a ^ b

a ^ a ^ b = b

再觀察 (EXP4 & -(EXP5))
根據 AND (

∧, c:&) 的特性

  • 任意 bit
    a∧1=a     保真性
    => A & 0xFFFFFFFF = A 其中 0xFFFFFFFF 為 -1 (2's complement)
  • A∧0=0     保假性

得知應控制 EXP5 的值，使其在

a<b 時為 1，
a>b 時為 0
而 EXP4 則填入 a ^ b 使得
a<b 時 a ^ (...) = a ^ a ^ b = b

綜上所述

  • EXP4 應填入 a ^ b
  • EXP5 應填入 a < b 或 a <= b （a, b 相等時回傳何者皆可）

使得結果 a ^ ((a ^ b) & -(a < b)) 等於 max(a, b)

針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作

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

無號數的情形即為題目的情形 （uint32_t）
而有號數也可用相同的方法求最大值
驗證如下

取 a = -5, b = 3

a = -5 = b'1011
b =  3 = b'0011
a ^ b  = b'0111
a < b  = b'0001 (true)
-b'0001 = b'1111
b'0111 & b'1111 = b'0111
b'1011 ^ b'0111 = b'0011 = 3

取 a = -5, b = -3

a = -3 = b'1011
b = -5 = b'1101
a ^ b  = b'0110
a < b  = b'0001 (true)
-b'0001 = b'1111
b'0110 & b'1111 = b'0110
b'1101 ^ b'0110 = b'1011 = -3

因此使用相同的程式碼即可對有/無號數作找最大值的運算

測驗 3

考慮以下 64 位元 GCD 求值函式

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

補完上述程式碼，並

  • 解釋上述程式運作原理
  • 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
  • Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。

運作原理

註: GCD 演算法
以測驗題目提供的演算法為基底，並補上兩者皆為奇數的情形，參考自 Binary GCD algorithm

function GCD(x, y: integer): integer;
begin
  if x = y and x = 0 then result := 0;
  if y = 0 then result := x;
  if x = 0 then result := y;
  (*because everything divides 0*)
  if x mod 2 = 0 and y mod 2 = 0 then result := 2 * GCD(x/2, y/2);
  (*because 2 is a common divisor, 
    multiplication with 2 can be done with bitwise shift operation*)
  if x mod 2 = 0 and y mod 2 = 1 then result := GCD(x/2, y);
  if x mod 2 = 1 and y mod 2 = 0 then result := GCD(x, y/2);
  (*because 2 is not a common divisor*)
  if x mod 2 = 1 and y mod 2 = 1 then result := GCD(Abs(u - v), Min(u, v));
  (*gcd(u, v) = gcd(|u − v|, min(u, v)), if u and v are both odd.*)
end;

參考上述 GCD 演算法
並以 u 紀錄結果，搭配 do-while 迴圈將遞迴去除

第 4 行是判斷 u, v 中是否有一者（或兩者）為 0

A∨0=A
0∨0=0

第 6 到第 8 行的 for 迴圈是當 u, v 皆為偶數時，將兩者均除以 2 ，並用 shift 紀錄待會要乘以 2 的次數

第 9 到第 10 行的迴圈不斷將 u 除以 2 直到它變成奇數

第 12 到第 13 行的迴圈不斷將 v 除以 2 直到它變成奇數

第 14 到第 20 行則是兩者皆為奇數的情形，相減並對 u - v 以及 u, v 中較小者作 GCD 直到出現 0

因此 21 行的 COND 應填入 v 判斷被減數 v 是否不為 0
而 RET 應填入 u << shift 將前面沒乘上的 2 通通乘回來

透過 __builtin_ctz 改寫

Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

e.g. 6 = b'0110
__builtin_ctz(6) = 1 -> 最右邊的 1 右邊有 1 個 0

將連續除 2 的動作用 __builtin_ctz 替代

e.g.

連續除以 2
4 = b'0100
2 = b'0010
0 = b'0001
使用__builtin_ctz()
__builtin_ctz(4) = 2
4 >> 2 = b'0100 >> 2 = b'0010 = 0

本來還想把判斷 0 的動作也替換，後來發現當它為 0 時行為未定

改寫實作

因為是 uint64_t 故使用 __builtin_ctzll (unsigned long long 版本)

uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;

    int shift = (__builtin_ctzll(u) > __builtin_ctzll(v)) ? __builtin_ctzll(v) : __builtin_ctzll(u);
    u >>= __builtin_ctzll(u);
    v >>= __builtin_ctzll(v);

    do {
        v >>= __builtin_ctzll(v); 
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

測驗 4

在影像處理中，bit array 被廣泛使用，如

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

使用 builtin_ctzll 改寫

















#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 為 b'000101，那 t 就會變成 b'000001，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

填入 EXP6 ，並

  • 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中
  • 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density
  • 思考進一步的改進空間
  • 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例

填空

3 bits 時二補數的編碼

1 2 3
+ 001 010 011
- 111 110 101
+&- 001 010 001

可以發現將

A∧(∼A+1) (c: A & (-A)) 會得到最低位元的 1

以 bitset = 20 = b'00010100 為例
-bitset = ~bitset + 1 = b'11101011 + 1 = 11101100
bitset & -bitset = b'00000100 即為所求

其中 unsigned 與 signed 僅為判讀上的差異，實際上存的 bitmap 皆相同
在 bitwise 操作時使用 unsigned 以獲得更大的可攜性 你所不知道的 c 語言 - bitwise 操作

printf(…) 中 %d 會以 signed 的方式判讀，而 %u 會以 unsigned 的方式判讀

因此 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;
}

補完程式碼，並

  • 解釋上述程式碼運作原理，指出其中不足，並予以改進

例如，判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms

  • 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景

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

補完程式碼，並

  • 解釋上述程式碼運作原理
  • 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
  • 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集

填空







g_align



s

char c

padding

t _h



0
0



0->s:c





p
p



p->s:h

如圖，利用 struct 自動 alignment 來算出 alignment 大小

char: 1 byte
t: ? byte，

≥ 1，mod 4 = 0
所以會以 t 的大小作對齊

將 p 的記憶體位置減去 0 即為所求

因此 M 應填入 _h 以取得第三個區塊的開頭位置
而由前面 (struct {char c; t _h} *)0 可知 X 應填入 0 ，才會在同個起始位置

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

測驗 7

考慮針對 FizzBuzz

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

的實作

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

補完，並

  • 解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
    • 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
  • 分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
    • 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
  • 研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
  • 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)
    • 過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論
Last changed by 
 
Xx-oX
0
413

Read more

cserv 高效網頁伺服器

contributed by < Xx-oX > cserv cserv is an event-driven and non-blocking web server. cserv 是一個高效的網頁伺服器 採用非阻塞式 I/O 的事件驅動架構 單執行緒、支援多核並具備 CPU 親和性 執行方法

Jun 1, 2023
Cyber Threat Life Cycle (Stages)

The Life Cycles of Cyber Threats The Life Cycles of Cyber Threats 4 stagesdiscovery and development - discovery a vulnerability introduction - an exploit can begin to be used against operational systems growth - malicious actors will know that the exploit can be effectively used against a set of targets maturation - fixes are developed to address the problem Cyber Kill Chain The Cyber Kill Chain

May 9, 2023
SNMP Trap Packet Loss

Q/As 1. 哪些config可以設定buffer 參考 rfc 3416 規範 The maximum size of an SNMP message is limited to the minimum of: (1) the maximum message size which the destination SNMP entity can accept; and, (2) the maximum message size which the source SNMP entity can generate. 可以藉由修改 agent 或 manager 的 maximum messgae size 來限制 SNMP message 的 maximum size

May 9, 2023
Top 22 Data Exchange Platform

reference Definition Data Exchange The process of sending and receiving data so that the information content or meaning attributed to the data is not changed during transmission. &#x7528;&#x8655;

Jul 18, 2022
Read more from Xx-oX
Published on HackMD