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

## 系統環境

$ uname -a
Linux ncku-ProLiant-ML350-Gen9 4.10.0-35-generic #39~16.04.1-Ubuntu SMP Wed Sep 13 09:02:42 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux


$ lscpu
Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                32
On-line CPU(s) list:   0-31
每核心執行緒數：2
每通訊端核心數：8
Socket(s):             2
NUMA 節點：         2
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              79
Model name:            Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
製程：              1
CPU MHz：             1218.000
CPU max MHz:           2100.0000
CPU min MHz:           1200.0000
BogoMIPS:              4190.34
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           20480K
NUMA node0 CPU(s):     0-7,16-23
NUMA node1 CPU(s):     8-15,24-31
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch epb cat_l3 cdp_l3 intel_ppin intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm cqm rdt_a rdseed adx smap xsaveopt cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local dtherm ida arat pln pts

$ free
              total        used        free      shared  buff/cache   available
Mem:       65839000      496496    64905824       95408      436680    64678636
置換：    31998972           0    31998972

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

> * 呼叫函式時 `c` 帶入 0 。`c` 依序每層遞迴增加至 3(分別代表 32 bits 、 16 bits 、 8 bits、 4 bits 。
> * 如果 `x` 為 0 的話回傳 32。
> * `upper` 計算前半段 ; `lower` 計算後半段。
> * `upper` 有值代表大於這層的 bits 數 / 2，切一半後 `c` 加 1 在往下一層。
> * `upper` 沒有值代表小於這層的 bits 數 / 2，切一半後 `c` 加 1 在往下一層。並且記錄可以確定的 0 的個數。
> * `c = 3` 時用 `magic` 判斷最後兩個 bits 有幾個 0。

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

>* `n` 紀錄 clz ; `y` 紀錄每圈 `x` 的前半部。
>* `y` 不為 0 ，就用前半部再去切一半，並扣掉後半部的 bits 數。
>* `y` 為 0 ，就所小後半部的範圍。
>* `c` 跑 5 次後跳出迴圈 。
>* 最後回傳`n-x` ，`x` 為最後一個bit 。

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

>* `n` 紀錄 clz 。每個 `if` 都比一半。
>* 每一圈都可以當作是一個 mask 。
>* 小於就代表前半部都是 0 。`n` 加上前半部 0 的個數，並把後半部左移去下一圈。
>* 大於就把前半部再去比較下一圈。

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

> * 跟 `binary search` 類似，`n` 紀錄 clz 。每個 `if` 都比一半。
> * 如果 `== 0` 則前半部都是 0 。`n` 加上前半部的 bits 數後，把後半部左移。
> * 不等於 0 ，則下一圈再把前半部切一半。

### Harley's algorithm

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

    /* 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];
}

>* `Table[]` 為 Hash Table 。
>* `14~19` 為程式第一部分，將最高位的 `1` 以下的 bits 都變為 `1`。
> * `21~27` 為程式第二部分， `0x6EB14F9` 為 **De Bruijn sequence** 。
> * 將最後的前六位當作 `Table[] ` 的 `index` 去查表，直接知道結果。

## 32-bits各版本 clz 演算法效能比較



* 依 cycles 是 `binary` $\approx$ `byte` $<$ `iteration` $<$ `harley` $<$ `resursive`

## 參考資料：
* [baimao8437同學筆記](https://hackmd.io/IwTgbMDsAmIMYFpoENoA4EBZICNoJwDMBmQgkYgVkwFNhDIAGNTIA)
* [ktvexe學長筆記](https://hackmd.io/s/BJBZn6Q6)