# 2017q3 Homework1 (clz)
contributed by <`kevin550029`>

## De Bruijn sequence
* a de Bruijn sequence of order n on a **size-k alphabet A** is a cyclic sequence
in which every possible length-n string on A **occurs exactly once** as a substring
* 給定 m 個字母，以及字串長度 k, 這個數列向左做旋轉後, 取出前 k 個字母。
恰好可以湊出所有這 k 個字母可能的組合

## Count Leading Zero
* 參考 [wikipedia: clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ)
* 計算 2 進位數自 MSB(Most sSignificant Bit) 開始往右, 遇到的第一個 1 之前, 所有 0 的數量
* For example, the clz of 0x00000F00 is 20, and the clz of 0x00000001 is 31.
0x00000001
-> 0000 0000 0000 0000 0000 0000 0000 0001
在第一個1前有31個為0的位元, 則 clz 為31
* 計算 clz 的 sample code

    int clz1( uint32_t x )
    {
      int n;
      if (x == 0) return 32;
      for (n = 0; ((x & 0x80000000) == 0); n++, x <<= 1);
      return n;
    }

> line4: x=0時, 直接回傳clz=32
> line5: 0x80000000 為 1000...0000, 當 x 的 MSB=1 和 0x80000000 做 & 之後,
會不等於 0 並跳出迴圈, 因此只要一直將 左移 X,
當迴圈跳出時代表他已經遇到了第一個為1的位元

## 解釋並比較 32-bit 數值對各種實做的效能差異

### Iteration Version

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

> x 傳入後, 會先取出其 upper bits 並放入 y, 再藉由迴圈來增減需要移動的 bits 數
> 最後用減法來計算 leading zero 的個數

### Binary Search Version

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

> 用 bit mask 判斷第一個為1的位元會出現在哪,
> 找出位置後進行適當長度的左移, 並繼續判斷
> line5: 當 x <= 0x0000FFFF 表示 x的前16位元皆為零,
> 則將 x 左移 16位元, 並繼續判斷

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

> Byte-Shift 和 Binary Search 的原理相似,
> Byte-Shift 是將 x 往右移之後, 再判斷是否為 0

### Harley’s Algorithm

unsigned clz(uint32_t x)
{
#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,
    };

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

> Harley’s algorithm 是使用雜湊法來判斷 leading zero 的個數,
> Table 代表的是 hash table
>
> x 輸入後, 會先經過 line:25~29 的處理, 將第一個為1位元後的bits都設為 0
> 例如 0100 0000 0000 0000 0000 0000 0000 0000
> 變成 0111 1111 1111 1111 1111 1111 1111 1111
>
> 經由這個例子可以知道, 這樣處理之後, 真正會進入雜湊函數運算的值只會有32種
> 最後經由查表, 便可以快速地得到 leading zero 的個數

### Recursive Version

static const int mask[] =  { 0, 8, 12,14 };
static const int magic[] = { 2, 1,  0, 0 };

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

### 比較效能


* Binary (圖中淡藍色區塊) 所需要的 cycles 數較少
* Byte 所耗費的 cycles 數 看起來比 Binary 稍長, 但相對於其他方法也算少的
* recursive method 比較不穩定

## 參考資料
[De Bruijn sequence](https://zhouer.org/DeBruijn/)
[共筆 tina0405](https://hackmd.io/MYZgrA7CBG0BwFoBmBDYBOBAWAjAUyQWgCZpgFjiQATPOa6EFYgNiA==?both)
[共筆 jack81306](https://hackmd.io/s/rykb4aR9e)
[wikipedia: clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ)
[你所不知道的C語言：數值系統篇](https://hackmd.io/s/BkRKhQGae)