# 2016q3 Homework1 (clz)
contributed by <`Claude51315`>

## 目標

* 了解[重新理解數值](https://hackmd.io/s/SkKZBXZT)
* 練習jserv大大的作業
* 了解各個clz實作方式
- [x]recursive
- [x]iterate
- [x]binary search technique
- [ ]Harley's Algorithm
* 學習gnuplot
* 了解clock測量
## CLZ 實驗

### recursive version

uint8_t recursive_clz(uint32_t x, uint32_t shifter)
{
    /* if x's lowest bit == 0, return 1*/
    if(shifter == 0) return ((x+1) & 1) ;
    uint16_t upper = (x >> shifter);
    /* mask out the lower-half bits*/
    uint16_t lower = x & (0xFFFFFFFF >> (32-shifter));
    return upper ? recursive_clz(upper , shifter >>1) : shifter + recursive_clz(lower, shifter>>1);
}

作法和binary search的方式很像，先看前一半的bit數目是不是皆為0，是的話就接著從後面的bits繼續找，否則就從前面的bit找

### iterate version

uint8_t iterate_clz(uint32_t x)
{
    int n = 32 , shifter = 16 ;
    do {
        uint32_t y = x >> shifter;
        if(y) {
            n -= shifter;
            x = y;
        }
        shifter >>=1;
    }while(shifter);
    return (n-x);
}

### binary search

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

# Harley's alogorithm
這個演算法是拿來算log2，也就是算二進位數字中尾端有幾個0，本來以為算出ctz之後，在用31減掉就是clz，想了一下錯了，要先對原本的數字做reverse之後，再算ctz

# Performance observation



比較劉亮谷同學的[clz]((https://hackmd.io/s/BJBZn6Q6))後，發現明明code一樣，測量到的cycle數目卻不一樣，有待發現原因。

# clock_gettime(clock_id, *struct timespec)

CLOCK_MONOTONIC: 計算從cpu boot 後經過了多少時間

CLOCK_REALTIME: (Default)Its time reference is the epoch which is defined to be the first of January 1970

The time reference can be changed, so CLOCK_REALTIME is ++not monotonic++

* [how-does-clockgettime-work](http://linuxmogeb.blogspot.tw/2013/10/how-does-clockgettime-work.html)
* [taskset](https://blog.gtwang.org/linux/run-program-process-specific-cpu-cores-linux/)

# Coding環境

## 重構專案
目前的實做的方式為每個不同版本的clz都有自己的main function，其中重複的地方很多，參考[phonebook](https://hackmd.io/s/S1RVdgza)的方式來整理程式碼

#### makefile
* $@: 目前的target名稱
* $?: 需要被更新的相依性
[makefile](http://dywang.csie.cyut.edu.tw/dywang/linuxProgram/node50.html)

#### gcc flag
* -D[name]: name is defined

## 啟用 git hook 來執行astyle程式碼風格檢查

把 phonebook 中的pre-commit.hook複製到clz-tests的根目錄

`$ ln -sf pre-commit.hook .git/hooks/pre-commit`

接著把recusive_clz.c排版亂改看看，測試在 commit 之前會不會執行astyle檢查

uint8_t recursive_clz(uint32_t x, uint32_t shifter)
{
    /* if x's lowest bit == 0, return 1*/
      if(shifter == 0) return ((x+1) & 1) ;
        uint16_t upper = (x >> shifter);
    /* mask out the lower-half bits*/
     uint16_t lower = x & (0xFFFFFFFF >> (32-shifter));
          return upper ? recursive_clz(upper , shifter >>1) : shifter + recursive_clz(lower, shifter>>1);
}

astyle沒被觸發，可以直接commit

改用複製的把pre-commit.hook複製到.git/hooks/pre-commit
把剛剛的commit取消後，再commit一次後這次astyle就有被觸發了
> git hook 不能用symbolic link觸發？[name=Miao Chiang Yen][time=Tue, Sep 27, 2016 2:00 PM]