# 2016q3 Homework1 (clz)
contributed by <`jayfeng0225`>
reviewed by <`kobeyu`>
- 輸入的值域並沒有走訪所有的32位元,另外產生測試資料的方式可以更直觀(0x1 << 1)
- 由於需要計算clz的時間非常的少,少到可能會測量不出來,所以建議計算時間的loop次數可以再增加(目前是25次)
- 建議可以想想各種演算法在位移相同的輸入值所需要的時間比較(ex x=0x01 vs x = 0x80000000連續執行10000次各種演算法所需要的時間比較)
- 建議把各種演算法的clz拆分到其他檔案與主程式分離,可思考REUSE的可能
- git commit的內容可以在多描述一些改動的部分
- 關於branch可以參考[git flow](https://ihower.tw/blog/archives/5140)的開發流程
- 看到好的部分是對於演算法的分析蠻詳細的
## 作業要求
閱讀 [重新理解數值](/s/SkKZBXZT) 裡頭關於 count leading zero ([clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ)) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：
* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley's algorithm
## 作業環境
:::info
OS : Ubuntu 16.04 LTS
CPU : Intel® Core™ i3-2350M @ 2.3GHz
Cache :
* L1d 快取： 32K
* L1i 快取： 32K
* L2 快取： 256K
* L3 快取： 3072K
Mem : 4G
:::
## CLZ的實作
* iteration ver.
```clike=
int 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 techique
```clike=
int 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 version
```clike=
int 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;
}
```
首先驗證基本的三個方法的正確性：
接著利用clock_gettime()來紀錄三種方法的執行時間，並且將其繪製成點狀分佈圖。
:::danger
因為電腦設備較舊，要輸出所有整數的執行結果需要花費很多時間，因此目前僅僅列出執行至 200000的結果。
:::
---
## 需要修改的版本
這部份有先參考[作業區](https://hackmd.io/s/H1B7-hGp)其他的同學的結果，所以思考比較快。
### Recursive ver.
:::info
__Recursive需要修改的問題為__
1. 沒有終止條件
2. shift bit與mask需要隨著遞迴改變
* shift bit : 16 -> 8 -> 4 -> 2 -> 1
* mask : 0xFFFF -> 0xFF -> 0xF
:::
* 原來的版本
```clike=
uint8_t clz(uint32_t x)
{
/* shift upper half down, rest is filled up with 0s */
uint16_t upper = (x >> 16);
// mask upper half away
uint16_t lower = (x & 0xFFFF);
return upper ? clz(upper) : 16 + clz(lower);
}
```
* 修正後的版本
```clike=
int clz_recursive(uint32_t x,uint32_t shift , uint32_t mask) {
if(x == 0) return 32;
if(shift == 1)
return !(x>>1);
/* shift upper half down, rest is filled up with 0s */
uint16_t upper = (x >> shift);
// mask upper half away
uint16_t lower = (x & mask);
uint32_t shift_temp = shift >> 1;
return upper ? clz_recursive(upper, shift_temp , mask >> shift_temp) :
shift + clz_recursive(lower, shift_temp, mask >> shift_temp );
}
```
* 驗證結果
:::success
驗證結果我使用原來的iteration版本將1~50000的答案輸出到檔案result，並且執行recursive版本輸出到檔案result_recu。最後在使用vimdiff檢查兩者是否有差異，而結果是輸出相同。
:::
### Harley's algorithm
:::info
原來提供的harley algorithm的程式碼是ctz的結果（也就是最後面有幾個0)，根據[workfunction筆記](/s/Byyd3nua)內[網站](http://www.hackersdelight.org/hdcodetxt/nlz.c.txt)所提到的，要修改成CLZ的版本需要改變Table的值。
:::
```clike=
#define u 99
static char table[64] =
{
32,31, u,16, u,30, 3, u, 15, u, u, u,29,
10, 2, u, u, u,12,14,21, u,19, u, u,28,
u,25, u, 9, 1, u, 17, u, 4, u, u,
u,11, u, 13,22,20, u,26, u, u,18, 5, u,
u,23, u,27, u, 6, u,24, 7, u, 8, u, 0, u
};
```
其中u代表不會使用到的值，因此將其定義為99
```clike=
uint8_t clz_harley(uint32_t x)
{
static char table[64] =
{
32,31, u,16, u,30, 3, u, 15, u, u, u,29,
10, 2, u, u, u,12,14,21, u,19, u, u,28,
u,25, u, 9, 1, u, 17, u, 4, u, u,
u,11, u, 13,22,20, u,26, u, u,18, 5, u,
u,23, u,27, u, 6, u,24, 7, u, 8, u, 0, u
};
/* 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];
}
```
* 驗證結果
:::success
驗證結果同樣輸出1~50000的結果，並且儲存在result_har檔案中再使用vimdiff做比較。結果是輸出相同，因此結果也是正確。
:::
## 時間落點分析圖
## 參考資料
* [重新理解數值](/s/SkKZBXZT)
* [workfunction筆記](https://hackmd.io/s/Byyd3nua)
###### tags: `jayfeng0225`
Sign in with Wallet
Connect another wallet