2016q3 Homework1 (clz)

contributed by <Claude51315>

目標

了解重新理解數值
練習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後，發現明明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

Coding環境

重構專案

目前的實做的方式為每個不同版本的clz都有自己的main function，其中重複的地方很多，參考phonebook的方式來整理程式碼

makefile

$@: 目前的target名稱
$?: 需要被更新的相依性
makefile

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
astyle check

改用複製的把pre-commit.hook複製到.git/hooks/pre-commit
把剛剛的commit取消後，再commit一次後這次astyle就有被觸發了
astyle check success

git hook 不能用symbolic link觸發？Miao Chiang YenTue, Sep 27, 2016 2:00 PM