# 2018q3 Homework5 (bits) contributed by <posutsai> ## bitMask ### 程式碼分析 在實作上這個函數卡了很久，實際上的核心在於不知道怎麼製作連續的 `1` ，後來突破的關鍵是，以下示例皆以 8 bits 做分析，以想製造出 `0b 00111000` 為例，可以想成 `((1 << 3) - 1) << 3` ，但這會有一個問題若是想製造出的目標是 `0b 11111111` 的話必須為 `(0 - 1) << 0` ，所以我先用了一個 one_l 變數去儲存會是多少個 1 最後再用邏輯判斷是否需要回傳 `0xffffffff` 如下方第3行所示，而最後的 conditional 則是用在判斷 `highbit < lowbit` 的狀況下要回傳 0 ```C= int bitMask(int highbit, int lowbit) { int one_l = highbit + (~lowbit) + 2; // 總共需要多少個 1 int pos = conditional(one_l - 32, ((1 << one_l) - 1) << lowbit, 0xffffffff); return conditional(((highbit + (~lowbit) + 1) >> 31) + 1, pos, 0); } ``` ### 使用案例 在 linux 內有提供一系列可以調整或檢查 cpu 內實體核所耗費的資源的工具，稱為 [cpupower](https://manpages.debian.org/testing/linux-cpupower/cpupower.1.en.html) ，以下節錄部分在 linux source code 內關於 cpupower 的程式碼核心。 ```C= struct bitmask { unsigned int size; unsigned long *maskp; }; /* * Parses a comma-separated list of numbers and ranges of numbers, * with optional ':%u' strides modifying ranges, into provided bitmask. * Some examples of input lists and their equivalent simple list: * Input Equivalent to * 0-3 0,1,2,3 * 0-7:2 0,2,4,6 * 1,3,5-7 1,3,5,6,7 * 0-3:2,8-15:4 0,2,8,12 */ int bitmask_parselist(const char *buf, struct bitmask *bmp) { const char *p, *q; bitmask_clearall(bmp); q = buf; while (p = q, q = nexttoken(q, ','), p) { unsigned int a; /* begin of range */ unsigned int b; /* end of range */ unsigned int s; /* stride */ const char *c1, *c2; /* next tokens after '-' or ',' */ char nextc; /* char after sscanf %u match */ int sret; /* sscanf return (number of matches) */ sret = sscanf(p, "%u%c", &a, &nextc); if (!scan_was_ok(sret, nextc, ",-")) goto err; b = a; s = 1; c1 = nexttoken(p, '-'); c2 = nexttoken(p, ','); if (c1 != NULL && (c2 == NULL || c1 < c2)) { sret = sscanf(c1, "%u%c", &b, &nextc); if (!scan_was_ok(sret, nextc, ",:")) goto err; c1 = nexttoken(c1, ':'); if (c1 != NULL && (c2 == NULL || c1 < c2)) { sret = sscanf(c1, "%u%c", &s, &nextc); if (!scan_was_ok(sret, nextc, ",")) goto err; } } if (!(a <= b)) goto err; if (b >= bmp->size) goto err; while (a <= b) { _setbit(bmp, a, 1); // 把所要求應為 1 的位置設為 1 a += s; } } return 0; err: bitmask_clearall(bmp); return -1; } ``` 但和我們自己的實作相比上面的做法是用 while loop 如上方第 53 行，一個一個設為 1，我想這樣作的原因在於，實際上會應用到的硬體核心數並不一定，且還要針對使用者輸入的格式作防呆，不過要是我來實作這樣的功能，不會採取一個一個字元慢慢讀進來的形式，會先過一層 regex 最後再根據實體核心數以我們的 bit operation 的方式實作。 ## countLeadingZero ### 程式碼分析 上方程式碼部分所作的操作會使第一個 `1` 之後的所有位元，皆為 `1` ，實際例子為 `0b 00010110` 轉為 `0b 00011111` 再 `++` 後，則為 `0b 00100000` 之後再逐步左移，判斷是否為 0 ，即可知道第一個 1 的位子，32個 `clz += conditional(x << n, 1, 0)` 這樣的操作即為求 intLog2 ```C= int countLeadingZero(int x) { x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); ++x; int full = conditional(x, 0, 1); int clz = 0; clz += conditional(x << 1, 1, 0); clz += conditional(x << 2, 1, 0); clz += conditional(x << 3, 1, 0); clz += conditional(x << 4, 1, 0); clz += conditional(x << 5, 1, 0); clz += conditional(x << 6, 1, 0); clz += conditional(x << 7, 1, 0); clz += conditional(x << 8, 1, 0); clz += conditional(x << 9, 1, 0); clz += conditional(x << 10, 1, 0); clz += conditional(x << 11, 1, 0); clz += conditional(x << 12, 1, 0); clz += conditional(x << 13, 1, 0); clz += conditional(x << 14, 1, 0); clz += conditional(x << 15, 1, 0); clz += conditional(x << 16, 1, 0); clz += conditional(x << 17, 1, 0); clz += conditional(x << 18, 1, 0); clz += conditional(x << 19, 1, 0); clz += conditional(x << 20, 1, 0); clz += conditional(x << 21, 1, 0); clz += conditional(x << 22, 1, 0); clz += conditional(x << 23, 1, 0); clz += conditional(x << 24, 1, 0); clz += conditional(x << 25, 1, 0); clz += conditional(x << 26, 1, 0); clz += conditional(x << 27, 1, 0); clz += conditional(x << 28, 1, 0); clz += conditional(x << 29, 1, 0); clz += conditional(x << 30, 1, 0); clz += conditional(x << 31, 1, 0); return conditional(full, 0, clz + 1); } ``` ### 使用案例 在 linux 內實作的案例定義在 string.h ，有一個 macro [ffs](https://www.systutorials.com/docs/linux/man/3-ffs/) 用來做到 countLeadingZero 的功能以下為 Linux 內的實作細節 ```C= #define ffs(x) ({ unsigned long __t = (x); fls(__t & -__t); } static inline int constant_fls(int x) { int r = 32; if (!x) return 0; if (!(x & 0xffff0000u)) { x <<= 16; r -= 16; } if (!(x & 0xff000000u)) { x <<= 8; r -= 8; } if (!(x & 0xf0000000u)) { x <<= 4; r -= 4; } if (!(x & 0xc0000000u)) { x <<= 2; r -= 2; } if (!(x & 0x80000000u)) { x <<= 1; r -= 1; } return r; } static inline int fls(int x) { int ret; if (__builtin_constant_p(x)) return constant_fls(x); asm("clz\t%0, %1" : "=r" (ret) : "r" (x) : "cc"); ret = 32 - ret; return ret; } ``` GCC extension __builtin_constant_p 的作用在於檢測某個參數是否為常數，若在編譯時期就知道會是常數的話以 `constant_fls` 處理，不是的話為了加速則以組合語言實作。相比我的實作可以看到 linux kernel 內的手法乾淨許多，藉由 `__t & -__t` 就可以留下最高位的 `1`，在判斷這個 `1`位在哪個位置上的手法也顯得更高竿，以 binary search 的方式每次搜尋一半，而不是像我一樣的線性搜尋。 ## subtrationOk ### 程式碼分析 考慮減法可能發生 overflow 的狀況只有可能在 x 和 y 異號的狀況，故我們只針對異號的狀況處理 overflow 若為同號則直接回傳相減的結果，接著分為兩種狀況分析異號可能產生異位的情形。 * x > 0, y < 0 此時唯一可能發生 positive overflow 的狀況是 x - y < x * x < 0, y > 0 反之若 x 為負，有可能發生 negative overflow 則判斷 x - y > x ```C= int subtractionOK(int x, int y) { int diff_sign = !!((x ^ y) & 0x80000000); int r = conditional(x >> 31, isGreater(x + (~y) + 1, x), isLess(x + (~y) + 1, x)); return conditional(diff_sign, !r, 1); } ``` ### 使用案例 我有找到一個 clang 的 plugin 會自動化的做到 overflow check， [ioc-clang paper](http://www.cs.utah.edu/~regehr/papers/overflow12.pdf) 和 [github](https://github.com/dtzWill/ioc-clang) 但因為他是 llvm 實作的我找不到核心判斷 overflow 的部分 ## satAdd ### 程式碼分析 和 substrationOk 一樣我們先分析可能會出現 overflow 或 underflow 的狀況，在 Add 的狀況只會發生在同號，並記錄若 x 為負則回 saturate 到 tmin 或在 x 為正的狀況回傳 tmax ，而判斷的條件就如同書上 63 頁 2.13 中所列，當 x > 0, y > 0 且 x + y < x 或 x < 0, y < 0 且 x + y > x 會發生溢位，最後用一個判斷式若發生溢位則回傳 saturate 到的值，根據 x 的正負號回傳 tmax 或是 tmin ```C= int satAdd(int x, int y) { int diff_sign = (!!((x ^ y) & 0x80000000)); int x_pos = !!((x >> 31) + 1); return conditional( diff_sign, x + y, conditional(x_pos, conditional(isLess(x + y, x), 0x7fffffff, x + y), conditional(isGreater(x + y, x), 0x80000000, x + y))); } ``` ## bitReverse ### 程式碼分析 網路上的實作通常都是直接對輸入做 bit operation 但這樣的一個功能讓我想到以前老師的作業中也有類似的需求可以用查表的方式實作，以遞迴的方式填表，最後再根據 `a & 0xff` 得到的值查表得到相對應的反向值，並組裝後回傳 ```C= #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) int bitReverse(int a) { const unsigned char BitReverseTable256[256] = {R6(0), R6(2), R6(1), R6(3)}; unsigned int c; c = (BitReverseTable256[a & 0xff] << 24) | (BitReverseTable256[(a >> 8) & 0xff] << 16) | (BitReverseTable256[(a >> 16) & 0xff] << 8) | (BitReverseTable256[(a >> 24) & 0xff]); return c; } ``` ### 案例分析 在 linux 內部為了同時符合 big endian 和 little endian 有實作了之間的轉換或許和我們實作的 reverse 每個 bit 都轉換不太一樣不過也是有異曲同工的地方。要是讓我來實作的話或許第一步也是先取出個相對應位置的 byte 內容，不過會一步步組裝，這樣的組合方式，是我完全想不到的 ```C= #define __bswap_constant_32(x) \ ((((x) & 0xff000000) >> 24) | (((x) & 0x00ff0000) >> 8) | \ (((x) & 0x0000ff00) << 8) | (((x) & 0x000000ff) << 24)) ```