2020q3 Homework3 (quiz3)

contributed by < grb72t3yde >

tags: sysprog2020

---

Links

• 第三週測驗題
• 作業區

測驗 1

依據 ISO/IEC 9899:TC2 (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁):

“The result of E1 >> E2 is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is implementation-defined.”

在 C 語言中，對有號型態的物件進行算術右移 (arithmetic right shift，以下簡稱 ASR 或 asr) 歸屬於 unspecified behavior，包含 Cppcheck 在內的靜態分析器會嘗試找出 C 程式中這項 unspecified behavior。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在二補數系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到:

$-5{\gg }^{arith}1=-3$
上述

$-3$ 正是

${\displaystyle \frac{-5}{2}}$ 的輸出, 並向

$-\mathrm{\infty }$ 進位(rounding)。
針對有號整數的跨平台 ASR 實作如下:

int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) OP1) > 0;
    unsigned int fixu = -(logical & (OP2));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

解題思路

OP1 = ? OP2 = ?

首先看題目給的資訊 :

• 參考 Unspecified_behavior, 得知此種行為是 source code 在基於使用不同的編譯器或是編譯器設定會有不同的表現。
• 以 ASR 來說, 當我們欲對負數進行算數右移卻沒有補入對應個數的 1 sign bits 時, 這種 Unspecified_behavior 就會產生 "錯 (不如預期) 的結果"; 因此, 我們需要對其手動補入對應個數的 1。

開始看程式碼 :

1. 我看到 line 6 的 return value, 判斷 | (fix ^ (fix >> n) 為修正操作
2. 繼續往 (fix ^ (fix >> n) 來想, 作為修正值, 必須要是 :

• $\stackrel{\text{32 bits}}{\overbrace{\underset{\text{n bit(s)}}{\underbrace{11...11}}\underset{\text{32-n bit(s)}}{\underbrace{00...00}}}}$ 或是 0 (不用修正的情況下)。

3. 回推至 line 4, 這邊製作出修正值 fixu, 已知 logical 和 OP2 都為 equality-expression, 所以 fixu 非 -1 即 0, 這應証了修正值的結果 (如 2. 提到的形式或是 0)
4. 考慮我們必須同時滿足 logical 和 OP2 才需要修正, 我從選項判斷 OP2 應為 m < 0 (即 m 為一個負數)
5. 回頭檢視此程式對 "跨平台" 的需求, OP1 選擇 >> 1
   (在不支援 ASR 的環境下, 使 0xffffffff 做"算數右移"將得到 0x7fffffff, 此數在被視為 signed int type 的情況下, 大於 0; 反之, 支援 ASR 的平台仍給我們 0xffffffff)

line 5 和使用 int fix = (int) fixu 有何差別？

延伸問題

• 練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度;

• char, unsigned long

測驗 2

在 C 語言：數值系統篇 中，我們介紹過 power of 2 (漢字可寫作「二的冪」)。

女星楊冪的名字裡，也有一個「冪」字。且，她取這個名字，就有「次方」的意義，因為她一家三口都姓楊，所以是「楊的三次方」。

GCC extension 其中兩個是 ctz 和 clz:

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.
  Built-in Function: int __builtin_clz (unsigned int x)
• Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

我們可用 __builtin_ctz 來實作 LeetCode 342. Power of Four，假設 int 為 32 位元寬度。實作程式碼如下:

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) OPQ);  
}

解題思路

OPQ = ?

• 思考如果一個正整數能被表示成

  $4^n$, 其二進位應該是
  • $\underset{\text{32 - (2n+1) bits}}{\underbrace{00...00}}\underset{\text{1 bit}}{\underbrace{1}}\underset{\text{2n個0}}{\underbrace{00...00}}$

  也就是它能被算術右移 n 次後得到 1

• 觀察 line 3 的 return 判斷了三件事情, 分別為 :

1. num > 0 : 0 和 負數 不可能是 power of 4
2. (num & (num - 1) == 0 : 判斷 1-bit 的個數, 在只有一個 1-bit 下此條件成立
3. !(__builtin_ctz(num) OPQ) : 有了前兩個條件成立, 此條件必須是要判斷 trailing 0-bits 是否為偶數個, 因此選擇 & 0x1

延伸問題

• 改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;

• 練習 LeetCode 1009. Complement of Base 10 Integer 和 41. First Missing Positive，應善用 clz;

• 研讀 2017 年修課學生報告，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告;

  x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 Selecting the Golomb Parameter in Rice Coding。

測驗 3

population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 CRC32 和 POPCNT 指令，POPCNT 可處理 16-bit, 32-bit, 64-bit 整數。

針對 LeetCode 1342. Number of Steps to Reduce a Number to Zero，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下:

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}

解題思路

AAA = ?

• 根據題目敘述, 我們想知道給定的 int type 輸入 num 最少可以透過幾個 steps 來變成 0, 其中:

  • 我們透過 devide by 2 以及 subtract 1 兩種操作使 num 逐步變成 0
  • 以上兩種操作都稱為一個 step

• 當我們遇到 LSB 為 1 的數字(此數字為奇數)時, 我們必須施以 subtract 1 的操作, 則我們需要使用 __builtin_popcount(num) 次的 subtract 1 操作, 可判斷 AAA 為__builtin_popcount(num)

BBB = ?

• 除去 1, 剩下的 0 我們可利用 >> 操作處理, 然而, 我們需要知道最左邊的 1 位於何處
• 因為最後一次的 subtract 1 已被算在 __builtin_popcount(num) 內, 我們先將 32 減一, 接著透過減掉 leading zero 的個數, 可以知道我們需要施以 >> 多少次, 因此判斷 BBB 為 __builtin_clz(num)

延伸問題

• 改寫上述程式碼，提供等價功能的不同實作並解說

  提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用，如 bit inverse、abs 等等，是極好的參考材料。

• 避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 LeetCode 1342. Number of Steps to Reduce a Number to Zero，實作出 branchless 解法，儘量縮減程式碼行數和分支數量

測驗 4

考慮以下 64-bit 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 (XXX);
    return YYY;
}

解題思路

XXX = ?

1. 觀察 line5 的 for loop, 當 u 與 v 的 LSB 同時為 0 時, 迴圈將繼續執行, 得知此迴圈計算的 shift 為 u, v 共同的 tailing zero 個數
2. 觀察到 line8, 的 while loop, 在做把 tailing zero 全部除去, 這也相當於 "將 u 的 2 因數全部除去"
3. 因為我們已記錄下共同的 2 質因數個數, 接下來在做輾轉相除法時就不需考慮 2, 而終止條件一樣選 v

YYY = ?

• 此動作補回 tailing zero 的個數, 因此選 u << shift

延伸問題

1. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升

---

測驗 5

在影像處理中，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;
}

可用 clz 改寫為效率更高且等價的程式碼:

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

解題思路

KKK = ?

TODO

延伸問題

1. 設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
2. 思考進一步的改進空間;