位元處理大全

本文翻譯、改寫自 Sean Eron AndersonBit Twiddling Hacks 一文。為了方便直接把代碼貼到程式裡,我盡量把長的算式寫成函數,短的算式就只列出。

本文在計算運算量時,一個 C 運算子計作一次運算。中途指派 (intermediate assignments) 因為不須寫入 RAM,所以不計。當然,這樣的計量方法只是機器指令數與 CPU 時間的估計值。所有的指令都假設消耗相同時間,與實況不符,但近來 CPU 的確朝這個方向發展。有許多微擾也決定了系統執行程式會跑得多快,像是快取大小、記憶體頻寬指令集等。倒頭來,評測 (benchmarking) 才是判斷某方法是否比另一方法快的正途,所以請把以下的手法視為在你的目標架構上的評測單元。

基本運算

本章主要探討符號、大小相關的議題,並在分支很慢的硬體上尋找替代方案。

計算數的符號

(v > 0) - (v < 0)

雖然本文是位元處理大全,但這個對浮點數也能奏效。

判斷兩整數是否異號

(x ^ y) < 0

計算整數的絕對值,不用分支

為了簡潔,這裡採用 C++函數模板

template<typename T>
T abs(T v)
{
	T mask = v < 0;
	return (v + mask) ^ mask;

//	有專利的變體
//	return (v ^ mask) - mask;
}

有些 CPU 沒有計算整數絕對值的指令,或編譯器可能無法利用它。在分支較慢的機器上,以上的函數會跑得比 v < 0 ? -v : v 快。

找出兩整數中較小的或較大的,不用分支

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))

快速骯髒版

如果你確定 xy 不會溢位,則你也可以採用以下的作法處理有號整數。為了簡潔,此處用 C++ 的寫法。對於有號整數,std::numeric_limits<T>::digits == sizeof(T) * CHAR_BIT - 1,其中 CHAR_BIT 定義在 limits.h 中。

#include <climits>
#define bitsof(T) (sizeof(T) * CHAR_BIT)

template<typename T>
T min(T x, T y)
{
	T z = x - y;
	return y + (z & (z >> std::numeric_limits<T>::digits));
}

template<typename T>
T max(T x, T y)
{
	T z = x - y;
	return x + (z & (z >> std::numeric_limits<T>::digits));
}

注意 C 並未規定負數右移的結果,所以這可能無法移植。

判斷整數是否為 2 的整數次方

如果你確定參數 v 非零,就可以用

v & (v - 1) == 0

注意當 v 是零,上述表達式仍為真。否則就得用

v && !(v & (v - 1))

符號擴展

對於 char, int 等內建類別,符號擴展是自動的。但假設你有一個有號二補數 x,只想耗費 b 位元儲存。甚者,假設你要把 x 轉成較大的 int。當 x 非負,只需要簡單的複製;但如果是負數,則負號需要擴展。例如若我們只用 4 位元儲存 −3,那麼 −3 在二進制中就是 1101。若我們有 8 位元,則 −3 在二進制中就是 11111101。在 4 位元表示中的最高位複製、填滿了目的地中多出來的、更高的 4 位。

固定寬度的符號擴展

在 C 中,固定寬度的符號擴展是平凡的,因為在 structunion 的定義當中可以指定位段 (bit field)。以下的程式把 5 位元的整數轉成 int

int x;  /* 只有最低 5 位有資料 */
int r;  /* 結果儲存在這裡 */
struct { signed int x: 5; } s;
r = s.x = x;

以下是 C++ 的模板函數,利用語言特性能以一次運算就把 b 位元的整數填滿類別 T

template<typename T, int b>
T signExtend(T x)
{
	struct { T x: b; } s;
	return s.x = x;
}

int result = signExtend<signed int, 5>(x);

變動寬度的符號擴展

有時候我們需要符號擴展,但事先不知道寬度;抑或我們用其他語言寫程式,沒有位段可用。

template<typename T>
T signExtend(T x, int b)
{
	T m = (T)1 << (b - 1);
	x &= ((T)1 << b) - 1;  // 若 x 的高位已為零可略過
	return (x ^ m) - m;
}

這需要四次運算,但當寬度是已知時,若高位已填零,則只需要二次運算。

還有另一個稍快,也不需要把高位填零,但不見得可移植的方法。

#include <climits>

template<typename T>
T signExtend(T x, int b)
{
	int m = sizeof(T) * CHAR_BIT - b;
	return (x << m) >> m;
}

移植性的問題在於 C 並未規定負數右移的結果,不過當代系統大多選擇實作算術移位。此外,若你對 limits.h 很不滿的話,可以試著寫 int m = -b,可能管用。

位元陣列

整數類別除了可以進行整數運算外,還可以當位元陣列使用。一個 n 位元的整數可以視為長度為 n 的位元陣列,其中的第 k 位就是陣列的 k 號單元。

雖然 C++ 中有 std::bitset 和 std::vector<bool>,但它們的實作仍仰賴整數。

依條件設定多個位元,不用分支

template<typename T>
T setBits(T word, T mask, bool flag)
{
	return flag ? word | mask : word & mask;
}

我們可以避免分支。但要特別注意一點,就是 flag 的類型必須是 bool,或者你要事先把所有真值轉成 1,因為我們利用了 -1 == ~0。

word ^ ((-flag ^ word) & mask)

而在超純量架構上,還有另一種算法。

(word & ~mask) | (-flag & mask)

依條件給出負值,不用分支

若你想在條件為真時拿到負值,這樣做可以避免分支。

(v ^ -fNegate) + fNegate

反之,若要在條件為假時拿到負值,就用這個。

(fDontNegate ^ (fDontNegate - 1)) * v

遮罩合併兩值

明顯的作法是

(a & ~mask) | (b & mask)

但是以下的作法可以節省一次運算。

a ^ ((a ^ b) & mask)

不過如果遮罩是常數,則兩者沒有差異。

漢明重量

漢明重量常簡稱為 popcount,是二進位整數中 1 的數量。

樸素方法

template<typename T>
int popcount(T v)
{
	int c;
	for (c = 0; v; v >>= 1)
		c += v & 1;
	return c;
}

這樸素方法每次迭代只走一位元,直到更高位的位元都為零為止。所以若輸入 1 << 31 則要迭代 32 次。

查表法

template<typename T>
int popcount(T v)
{
	static const unsigned char PopcountTable[256] =
	{
#		define B2(n) n,	 n+1,	 n+1,	 n+2
#		define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#		define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
		B6(0), B6(1), B6(1), B6(2)
	};

	unsigned char *p = reinterpret_cast<unsigned char*>(&v);
	int c = 0;

	// sizeof 在編譯期已知,編譯器能展開迴圈。
	for (int k = 0; k < sizeof(T); ++k)
		c += PopcountTable[p[k]];

	return c;
}

Brian Kernighan 計算漢明重量的方法

template<typename T>
int popcount(T v)
{
	int c;
	for (c = 0; v; ++c)
		v &= v - 1;
	return c;
}

跟樸素法相比。此方法只為已設立(為一)的位元迭代。

以 64 位元指令計算 14 位元的漢明重量

int popcount14(unsigned int v)
{
	return (v * 0x200040008001ull & 0x111111111111111ull) % 0xf;
}

這要有 64 位元的 CPU 與快速的模除才會快,只要 3 次運算。如果要計算更多位元,可以利用位移與遮罩。

int popcount28(unsigned long v)
{
	return popcount14(v & 0x3fff) + popcount14(v >> 14);
}

int popcount42(unsigned long long v)
{
	return popcount28(v & 0xfffffff) + popcount14(v >> 28);
}

解說

popcount(v & 0x1111) == (v & 0x1111) % 0xf
popcount(v & 0x2222) == (v << 15 & 0x11110000ul) % 0xf
popcount(v & 0x4444) == (v << 30 & 0x111100000000ull) % 0xf
popcount(v & 0x888) == (v << 45 & 0x111000000000000ull) % 0xf

乍看之下好像可以求 15 位元,但別忘了除以 15 的餘數不可能是 15,所以 0x7fff 就杯具了。

平行計算漢明重量

對於 32, 64, 128 位元的整數類別 T,計算漢明重量的最佳作法如下。

#include <climits>

template<typename T>
int popcount(T v)
{
	v = v - ((v >> 1) & ~(T)0/3);
	v = (v & ~(T)0/5) + ((v >> 2) & ~(T)0/5);
	v = (v + (v >> 4)) & ~(T)0/17;
	return (T)(v * (~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT;
}

此法需要 12 次運算,與 32 位元的查表法相同,但使用較少的記憶體並避免了快取失效

解說

我們利用除法在編譯期就製造好需要的遮罩。

~0
全滿
...1111111111111111 = 0x...ffff
~0/3
偶數位為一,奇數位為零。
...0101010101010101 = 0x...5555
~0/5
4k 與 4k + 1 位為一,其他為零。
...0011001100110011 = 0x...3333
~0/17
8k 至 8k + 3 位為一,其他為零。
...0000111100001111 = 0x...0f0f
~0/255
8k 位為一,其他為零。
...0000000100000001 = 0x...0101

有興趣的人可以證明 8n 位元的 ~0 是 255 的倍數。對了,255 = 3 · 5 · 17。

奇偶性

本章所要探討的,是計算位元陣列的奇偶函數值。

樸素方法

template<typename T>
bool parity(T v)
{
	bool p = false;
	while (v)
	{
		p = !p;
		v &= v - 1;
	}
	return p;
}

這跟上述 Brian Kernighan 計算漢明重量的方法非常類似,並耗費相當的時間。

查表法

#include <stdint.h>  /* C99 */

int parity8(uint8_t v)
{
	static const char ParityTable[256] =
	{
#		define P2(n) n, n^1, n^1, n
#		define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#		define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
		P6(0), P6(1), P6(1), P6(0)
	};
	return ParityTable[v];
}

int parity16(uint_fast16_t v)
{
	return parity8(v ^ v >> 8);
}

int parity32(uint_fast32_t v)
{
	return parity16(v ^ v >> 16);
}

int parity64(uint_fast64_t v)
{
	return parity32(v ^ v >> 32);
}

利用 64 位元乘法與模除計算八位元組的奇偶性

((byte * 0x0101010101010101ull & 0x8040201008040201ull) % 0x1ff) & 1

這個方法只需要 4 次運算,但只對八位元組管用。

利用乘法計算奇偶性

template<typename T>
bool parity(T v)
{
	const T mask = ~(T)0/15;
	v ^= v >> 1;
	v ^= v >> 2;
	v = (v & mask) * mask;
	return (v >> sizeof(T) * CHAR_BIT - 4) & 1;
}

此法無論如何都運算 8 次。

平行計算奇偶性

(0x6996 >> ((byte ^ byte >> 4) & 0xf)) & 1

0x6996 以二進位表示為 0110 1001 1001 0110,是 4 位元的奇偶性表。

交換

沒錯,這章要談的就是大名鼎鼎的 swap。如果你有 C++ 可以用就別鬧了,快去用 std::swap

以 XOR 交換

a ^= b; b ^= a; a ^= b;

這個是不耗費額外空間進行交換的老哏了。注意 ab 不可指向同一變數,否則這個變數會變成 0。

一般來說,在現代的處理器架構上,多操作一個暫存器比這樣快多了。不過這個演算法擴展後有其他用途。

以 XOR 交換位元陣列的位元

以下的演算法可以交換連續的幾個位元。

template<typename T>
T swapBits(T v, int i, int j, int n)
{
	T x = ((v >> i) ^ (v >> j)) & ((T)1 << n) - 1;
	return v ^ ((x << i) | (x << j));
}

假設我們有 v = 001011112,要交換連續 n = 3 個位元,位於 i = 1 與 j = 5 的位置,則結果為 111000112

反轉

就是把高位跟低位對調。

樸素方法

template<typename T>
T reverse(T v)
{
	T r = v;
	int s = sizeof(v) * CHAR_BIT - 1;

	for (v >>= 1; v; v >>= 1)
	{
		r <<= 1;
		r |= v & 1;
		--s;
	}
	return r << s;
}

全文未完

給 nginx 和 php-fpm 的 AppArmor 設定檔

[English version]

AppArmor 是 Ubuntu 預設的 MAC 模組。不像傳統 Unix 的 DAC,AppArmor 設定檔列出什麼是行程存取的。處於強制模式 (enforced) 的行程只能存取已列舉的路徑。處於抱怨模式 (complaining) 的行程存取未列舉的路徑會發出警告。

然而 nginxphp-fpm 沒有預設的設定檔。為了避免網頁伺服器遭駭造成系統性感染,自己的設定檔自己寫!我們有 aa-genprof 這個有用的工具完成大部份的工作,但是它還是會遺漏一些路徑,特別是 sockets。因此我把我的設定檔放上來作為他山之石。

以下是 nginx 的設定檔。

#include <tunables/global>

/usr/sbin/nginx {
    #include <abstractions/apache2-common>
    #include <abstractions/base>
    #include <abstractions/nis>

    capability dac_override,
    capability net_bind_service,
    capability setgid,
    capability setuid,

    /etc/nginx/** r,
    /etc/ssl/openssl.cnf r,
    /proc/*/auxv r,
    /run/nginx.pid rw,
    /run/nginx.pid.oldbin w,
    /run/php5-fpm.sock rw,
    /srv/www/** r,
    /usr/sbin/nginx mr,
    /var/log/nginx/* w,
}

以下是 php-fpm 的設定檔。

#include <tunables/global>

/usr/sbin/php5-fpm {
    #include <abstractions/base>
    #include <abstractions/nameservice>
    #include <abstractions/php5>

    capability kill,
    capability setgid,
    capability setuid,

    /etc/php5/** r,
    /proc/*/auxv r,
    /proc/sys/kernel/ngroups_max r,
    /run/mysqld/mysqld.sock rw,
    /run/php5-fpm.pid rw,
    /run/php5-fpm.sock w,
    /srv/www/** r,
    /srv/www/html/wp-content/** rw,
    /srv/www/html/wp-content/cache/** rwk,
    /srv/www/magento/media/** rw,
    /srv/www/magento/var/** rwk,
    /tmp/ r,
    /tmp/** rwk,
    /usr/sbin/php5-fpm mrix,
    /var/log/php5-fpm.log* w,
}