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

先寫 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，將 algo 和 data source 區隔 jserv

不太清楚 data source 以及 algo / data source 區隔的意思，是指各個 algo modulize 然後提供 API 來接上去嗎？ louielu

Crypto API like interface

• crypto api-intro
• LINUX KERNEL Crypto API
• The Linux Kernel Cryptographic API - 2003
• 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
• Linux 2.6.38 User-space interface for Crypto API
  

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)
• looking fast algorithm for leading zero count
• Hacker's Delight
• The aggregrate MAGIC Algorithm

gnuplot 畫圖

作畫技巧

yerrorlines 可以畫出 confidence interval

統計結果

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

input 1

input 1024

input 50505050

input 2147483648

gif

3d version