2017q1 Homework1 (clz)
===
contributed by <`vtim9907`>

### Reviewed by <`andycom12000`>

- 第一部分的效能分析可能需要做一些較為實質的分析
> 例如: 分為前半部是0，後半部是0之類的方式做分析
- 可以找一些clz的應用
- 作業中有提到要使用_Generic()改寫程式碼，但在repo中沒看到

# 開發環境
- OS : Ubuntu 16.04.2 LTS
- Kernel Version : 4.8.0-36-generic
- Memory : 32 GB
- CPU : Intel® Core™ i5-6600 Processor
- cache :
- L1i cache : 4*32 KB
- L1d cache : 4*32 KB
- L2 cache : 4*256 KB
- L3 cache : 6144 KB
- L1 cache imformation ( sudo dmidecode -t cache ) :

Handle 0x001E, DMI type 7, 19 bytes
Cache Information
	Socket Designation: L1 Cache
	Configuration: Enabled, Not Socketed, Level 1
	Operational Mode: Write Back
	Location: Internal
	Installed Size: 256 kB
	Maximum Size: 256 kB
	Supported SRAM Types:
		Synchronous
	Installed SRAM Type: Synchronous
	Speed: Unknown
	Error Correction Type: Parity
	System Type: Unified
	Associativity: 8-way Set-associative

# 分析效能 ＆ 正確性
## Iteration version

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    int n = 32, c = 16;
    do {
        uint32_t y = x >> c;
        if (y) { n -= c; x = y; }
        c >>= 1;
    } while (c);
    return (n - x);
}

>設定一個類似遮罩功能的 c 的值為 16，每跑一次就除以 2 ，然後用 while 去判斷，若 c 大於零就繼續跑，而每跑一次迴圈就去測原來要測的 $x$ 值是否大於 $2^{c}$ ，是的話 $x$ 就除以 $2^{c}$，以此逼近到 $x$ 值小於 1 後，n 就不會再下降，最終得到 n - x 的值就是高位的 0 的個數。

需要做的判斷有點多，感覺效能不會太好。
## Binary search technique

unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
    if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
    if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
    if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
    return n;
}

> 與 iteration version 最大的不同是，這個方法是假定輸入的值是一個小數，因為它一開始假定高位 0 的個數 $n$ 為 0，然後每當數字小於某個門檻，$n$ 就加上應有的 0 的個數。

這個方法其實跟 iteration version 意思有點不相同，程式碼更簡單明瞭， branch 的次數也更少，有 iteration version + loop unrolling 的感覺。

## Byte-shift version

unsigned clz(uint32_t x)
{
    if (x == 0) return 32;
    int n = 1;
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8; x <<= 8; }
    if ((x >> 28) == 0) { n += 4; x <<= 4; }
    if ((x >> 30) == 0) { n += 2; x <<= 2; }
    n = n - (x >> 31);
    return n;
}

除了最後一段，處理 $2^{31}$ 的 case 的方式不同，其他整體程式碼用到的指令跟 binary search technique 相似，兩者效能應該差不了多少。

## Recursive

unsigned clz2(uint32_t x,int c)
{
    if (!x && !c) return 32;

    uint32_t upper = (x >> (16>>c)); 
    uint32_t lower = (x & (0xFFFF>>mask[c]));
    if (c == 3) return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

每次進 function 就要宣告兩個變數來做紀錄，以及做兩次 if 判斷，雖然已經是 tail recursion，但顯然光是做靜態分析就大致能確定這個程式的複雜度高過前三種方法，效能肯定不太好。
## Harley

unsigned clz(uint32_t x)
{
    // CTZ table
#ifdef CTZ
    static uint8_t const Table[] = {
        0xFF,    0, 0xFF,   15, 0xFF,    1,   28, 0xFF,
          16, 0xFF, 0xFF, 0xFF,    2,   21,   29, 0xFF,
        0xFF, 0xFF,   19,   17,   10, 0xFF,   12, 0xFF,
        0xFF,    3, 0xFF,    6, 0xFF,   22,   30, 0xFF,
          14, 0xFF,   27, 0xFF, 0xFF, 0xFF,   20, 0xFF,
          18,    9,   11, 0xFF,    5, 0xFF, 0xFF,   13,
          26, 0xFF, 0xFF,    8, 0xFF,    4, 0xFF,   25,
        0xFF,    7,   24, 0xFF,   23, 0xFF,   31, 0xFF,
    };

    // CLZ table
#else
    static uint8_t const Table[] = {
        32, 31,  0, 16,  0, 30,  3, 0, 15,  0,  0,  0, 29, 10, 2,  0,
         0,  0, 12, 14, 21,  0, 19, 0,  0, 28,  0, 25,  0,  9, 1,  0,
        17,  0,  4,  0,  0,  0, 11, 0, 13, 22, 20,  0, 26,  0, 0, 18,
         5,  0,  0, 23,  0, 27,  0, 6,  0, 24,  7,  0,  8,  0, 0,  0
    };
#endif
    /* Propagate leftmost 1-bit to the right */
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
 
    /* x = x * 0x6EB14F9 */
    x = (x << 3) - x;   /* Multiply by 7. */
    x = (x << 8) - x;   /* Multiply by 255. */
    x = (x << 8) - x;   /* Again. */
    x = (x << 8) - x;   /* Again. */

    return Table[(x >> 26)];
}

> Code 上半部有特別註明是 CTZ table，在本次 CLZ 作業就先姑且忽略。

中間 | 運算的目的主要是確保 x 裡最高位的 1 之後，全部都為 1 ，也就是把所有可能的低位 0 都用 | operator 算為 1，如此，如果不包含 32 個 bit 全部都為 1 的情況，總共只會出現 32 種 case，這個步驟我認為是這個演算法的核心。
而後半段的運算我覺得有點想把數字經過了類似 hash 的步驟，然後一一 map 進 table，而細看後半段的運算過程：
經過化簡大約等於

$X * 2^{27} - (x + x*7 + x*7*255 + x*7*255*255)$

化簡一下等於

$X * 133760760$ ，換成二進位 -> $X * (111,1111,1001,0000,0110,1111,1000)_2$

再看到最後 return 的值右移了 26 bit，也就是除以 $2^{26}$，不過還是以二進位比較好理解，看到上面換成二進位的數字，只要乘上 $X$ 再丟掉 26 位，就是 table 的 index，需要特別注意的地方是，一般直覺會認為 $X$ 值越大，在 table 的 index 就會越大，但其實要注意是要先將 $X$ 乘上上面那串二進位數字 (或 $133760760_{10}$)，才開始執行右移的動作，可是在右移之前，數字就可能因為超過 32 bits 而在左移的過程中就捨棄掉高位的一些數字，所以當 X 大到一個程度超過 32 bits 之後，X 值對應到的 index 就又會由小再往上增長；特別的是這 32 種 cases 的 index 剛好都不會衝突到。
> 目前想到證明這個演算法正確的方式就是窮舉 32 種 case 並確定 index 不會碰撞，就能確保算法正確。 ( 不過感覺應該有比較正確的證法@@"

所以結論我還是認為 harley 有點類似 hash table，把 $2^{32}$ 個數字經過類似 hash 的過程，最後只會得到 32 個 cases ，並正確的 map 到正確的 index ( 有點神奇，但想想其實又還好 )；雖然感覺直接 map 到對的值感覺很快，但是它所作的運算量其實不少，所以我認為 performance 不一定好，但因為每個數字的運算量都一樣，所以應該是效能應該是相對較穩定的。
## 驗證正確性

### __builtin_clz()

根據 [Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 說明，__builtin_clz() 是一個內建函數，也是回傳 number 的高位有幾個 0，若 number == 0，則回傳 undefined。

既然有內建的函數，就可以以這個 function 為基準，來測其他版本的 clz 的正確性。

原來想自己寫驗證的 function ，不過後來發現 main() 裡面已經有了@@" 測試完之後結果為正確。

## 效能分析
將原本幾個版本執行後，把結果畫出來比較看看是否跟預期的效能差不多：


果然 recursive 版本的效能最差，而 byte-shift 和 binary 都很快，效能最好。

## 問題討論

- 找至少 3 個案例，說明 clz 的應用場合
1. Null suppression
- 一種簡單、快速的資料壓縮方法。

# Reference

- [重新理解數值](https://hackmd.io/s/Hy-pTh8Fl)