# 2016q3 Homework 1 (clz-tests)
###### tags: `sysprog21` `not-done` `louielu`

## files

├── clz.c
├── clz.h
├── README.md
└── test_clz.c

### `clz.h`

宣告各個 clz 的 function

uint8_t clz_recursive(uint32_t x);
uint8_t clz_iteration(uint32_t x);
uint8_t clz_binary_search(uint32_t x);
uint8_t clz_bit_shift(uint32_t x);
uint8_t clz_harley(uint32_t x);
uint8_t clz_debug(uint32_t x);

### `clz.c`

定義各個 clz function

### `test_clz.c`

各個 clz function 與 clz_debug (__builtin_clz) 做比較。

* gcc builtin function: [__builtin_clz](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)

## 先寫 TDD

static void test_clz(void *f)
{
	uint8_t (*clz)(uint32_t) = f;
	uint32_t i;

	test_count++;
	for (i = 0; i < UINT_MAX; ++i) {
		if (clz(i) != clz_debug(i)) {
			printf("%d: except: %u, got: %u\n", i, clz_debug(i), clz(i));
			return;
		}
	}

	test_pass++;
}

### `__builtin_clz` result undefined

使用 `__builtin_clz` 當作 debug clz 但是出錯了！

0: except: 31, got: 211
0/1 (0.00%) passed
0: except: 31, got: 202
0/1 (0.00%) passed

每次的結果還都不一樣咧

用 gdb 看是正常的

(gdb) p clz(0)
$1 = 31 '\037'
(gdb) p clz_debug(0)
$2 = 31 '\037'

最後發現.........

> — Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

這告訴我們，看 Documentation看 Documentation看 Documentation看 Documentation看 Documentation看 Documentation看 Documentation。

> If x is 0, the result is undefined.

### function pointer

這邊使用 function pointer 來傳入每個 clz function，簡化程式碼。

static void test_all(void)bbb
{
	test_clz((void *) clz_debug, "debug");
	test_clz((void *) clz_recursive, "recursive");
}

static void test_clz(void *f)
{
	uint8_t (*clz)(uint32_t) = f;
	...
}

>> TODO: 比照 Linux 核心的 [Crypto API](https://en.wikipedia.org/wiki/Crypto_API_(Linux))，將 algo 和 data source 區隔 [name=jserv]
>>> 不太清楚 data source 以及 algo / data source 區隔的意思，是指各個 algo modulize 然後提供 API 來接上去嗎？ [name=louielu]

#### Crypto API like interface
* [crypto api-intro](http://lxr.free-electrons.com/source/Documentation/crypto/api-intro.txt)
* [LINUX KERNEL Crypto API](https://www.kernel.org/doc/htmldocs/crypto-API/index.html)
* [The Linux Kernel Cryptographic API - 2003](http://www.linuxjournal.com/article/6451#)
* Crypto API 是 Linux kernel 中用來處理有關密碼演算的框架，諸如 IPSec 或是 dm-crypt。
* 2000年左右提出，到現在基本上所有 kernel 與 crypto 相關的機制都使用這個框架來處理。
* Crypto API supports five main types of transforms
* AEAD:
* Block Chipers: AES, DES, Blowfish...etc
* Chipers:
* Compressors: LZS, Deflate
* Hashes: 單向雜湊函數, e.g. md5, sha1

##### impl
* [crypto api in kernel](https://breakpoint.cc/Thesis/html/diplomarbeitch4.html#x12-300004)
* [Linux 2.6.38 User-space interface for Crypto API
](http://blog.yufeng.info/archives/1150)

## clz impl

### 先接 CI

travis CI

### API structure

typedef uint8_t (*clz_t)(uint32_t x);

struct clz_alg {
	char name[CLZ_MAX_ALG_NAME];
	clz_t clz;
}

### Harley's algorithm

* [miscellaneous material - Hacker's Delight / Variations of Harley's algorithm for computing nlz(x)](http://www.hackersdelight.org/corres.txt)
* [looking fast algorithm for leading zero count](http://www.avrfreaks.net/forum/looking-fast-algorithm-count-leading-zero)
* [Hacker's Delight](http://www.hackersdelight.org/)
* [The aggregrate MAGIC Algorithm](http://aggregate.org/MAGIC/)

### gnuplot 畫圖

#### 作畫技巧

`yerrorlines` 可以畫出 confidence interval

### 統計結果

每個 algorithm 跑 50 萬次，跑 50 次取 95% 信賴區間資料。

#### input 1


#### input 1024


#### input 50505050


#### input 2147483648


#### gif


#### 3d version