# 2017q1 Homework1 (clz)
###### tags: `embedded`
contributed by <`Cayonliow`>
tags:

## Reviewed by `Billy4195`
* 可以稍微解釋一下產生出來的圖表具有什麼意義
* 圖表上為什麼會有些不穩定的點??(起伏很大的)
* 要提出clz的應用
* 嘗試C11 的 _Generic 可以參考別人寫的[`laochanlam` clz](https://hackmd.io/s/HyKilAfcx)

## 作業
* 題目： [B04: clz](https://hackmd.io/s/ry1u0uDFg#)
* github(原來的): [clz-tests](https://hackmd.io/s/ry1u0uDFg#)
* 解說影片: [Count Leading Zero](https://www.youtube.com/watch?v=DRkXFjLfaVg)
* [劉亮谷的實驗紀錄](https://hackmd.io/s/BJBZn6Q6#)
* [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/s/S1maxCXMl#)

### 開發環境

cayon@cayon-X550JX:~$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 60
Model name:            Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping:              3
CPU MHz:               2423.484
CPU max MHz:           3600.0000
CPU min MHz:           800.0000
BogoMIPS:              5188.45
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K
NUMA node0 CPU(s):     0-7

## 工具

## 原理與概念
* 數值
* 文章： [重新理解數值](https://hackmd.io/s/Hy-pTh8Fl#)

## 開發記錄
### 影片筆記
#### 實作方式的講解
* iteration version
* 對切 （c = 16）
* 跑 5 次後跳出迴圈
* 計算 0 的次數

include "clz.h"

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

* binary search version
* max 一半

#include "clz.h"
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;
}

* byte shift verison
* 位移

#include "clz.h"
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;
}

* Harley’s algorithm version
* 數字 0 或 0xFF 在 CTZ table 跟 CLZ table 裏頭是沒有意義的數字 （不會用到的）
* 在 CLZ table裏， 存有數字 0 的位置是代表計算後不會存取到的位置

#include "clz.h"

static inline __attribute((always_inline))
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)];
}

* `$ make plot` 看圖