# 2016q3 Homework1 (clz)
contributed by <`KobeYu`>
github:https://github.com/kobe0308/clz-tests.git
作業說明: https://hackmd.io/s/B1LHefQ6
###### tags: `kobeyu`
## status: ongoing
## 作業目標
實作clz並對各種演算法進行效能分析,須實作下列演算法:
* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley’s algorithm

## 執行環境 @c9.io

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: 62
Stepping: 4
CPU MHz: 2499.998
BogoMIPS: 4999.99
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 30720K
NUMA node0 CPU(s): 0-7

## 資料夾結構
我將所有clz的實作方式都放在clz.[ch],而在main.c中呼叫各種演算法並確認結果時否符合預期.

.
├── Makefile
├── README.md
├── clz
├── clz.c
├── clz.h
└── main.c

0 directories, 6 files

## Git Branch
過去養成的開發習慣是走git flow的流程,所以至少會開一個develop分支做開發.([git flow](https://ihower.tw/blog/archives/5140))

kobe0308:~/workspace/ncku/2016_fall_system_programming/clz-tests (develop) $ git branch -v
* develop 0f6e3d1 implement clz_iteration
master d3707ca [ahead 1] add all clz api in main.c

## TDD in main.c
TDD先寫測試再開發,作業目的是要找出32bit的變數中從最高為元往低位元計算第一個1以前0的總數,所以要傳全0與0x0001左移32次,共33個測試案例.
在我的main.c會觀察目前傳入的x與預期輸出一開始我用事%d去印出x,發現在最後一筆資料(0X8000)印出的是負數,%d是印出有號數的整數,應該要改成%u才能正確印出數值,但仍不直觀,所以最後版本是印出無號數的16進制%x

for (uint32_t x = 1,exp=31; x < ceiling && x; x=x<<1,exp--) {
	printf("x:%u, exp:%u\n",x,exp);

在還沒實作之前的函式都先回傳-1,因為無論clz的結果不會是負值.

assert((clz_recursive(0)==32) && "clz_recursive(0) failure!!! ");
assert((clz_iteration(0)==32) && "clz_iteration(0) failure!!! ");
assert((clz_binarySearch(0)==32) && "clz_binarySearch(0) failure!!! ");
assert((clz_byteShift(0)==32) && "clz_recursive(0) failure!!! ");
assert((clz_harley(0)==32) && "clz_harley(0) failure!!! ");

for (uint32_t i = 1,j=31; i < pow(2,31) && i; i=i<<1,j--) {
assert((clz_recursive(i)==j) && "clz_recursive failure!!! ");
assert((clz_iteration(i)==j) && "clz_iteration failure!!! ");
assert((clz_binarySearch(i)==j) && "clz_binarySearch failure!!! ");
assert((clz_byteShift(i)==j) && "clz_byteShift failure!!! ");
assert((clz_harley(i)==j) && "clz_harley failure!!! ");
}

printf("end of clz test\n");
return 0;

## 量測執行時間
預計量測以下執行時間
1.量測輸入0x0001~0x8000,各種演算法連續執行一萬次的時間

繪製三個維度的圖表:
1. x : 0x0001~0x8000
2. 迴圈次數 一萬到一百萬,每次增加一萬
3. 時間刻度
4. 五種資料點:五種演算法

---

思考次數的意義:

clock_gettime(CLOCK_REALTIME, &startTime);
for (loop_i = 0; loop_i < loop; loop_i++) clz_harley(x);
clock_gettime(CLOCK_REALTIME, &endTime);
double exectime_harley = diff_in_second(startTime, endTime);

## 參考資料

* [louielu](https://hackmd.io/IwMwDCCsCmAsCcBaeBmA7AJkbDIAciAhgEazGK4aGQrzTQDGTQA=) : 參考了部分gnuplot的語法以及繪圖的內容.
* [plot](http://dsec.pku.edu.cn/dsectest/dsec_cn/gnuplot/plot-5.html#datafile) 參考了部分gnuplot的語法
---