movemaskでbitboardを転置するやつ

最近broadcast+sllv+movmskでbitmatrixの転置ができることを知ってスゲーになりました

— そすうぽよ(すごい)(早寝早起き) (@_primenumber) 2021年10月1日

このツイートを見かけたんですがやり方が見当たらなくて一瞬考えてしまったたので、備忘録として以下に書き残しておきます。

まず、符号なし64bit整数を8x8 bitboardとみなして転置する方法として、基本的な命令のみを用いるならば以下のように書けます。

uint64_t transpose_bitboard(uint64_t b) {
	//引数が8x8 bitboardだとして、転置して返す。

	uint64_t t;

	t = (b ^ (b >> 7)) & 0x00AA00AA00AA00AAULL;
	b = b ^ t ^ (t << 7);
	t = (b ^ (b >> 14)) & 0x0000CCCC0000CCCCULL;
	b = b ^ t ^ (t << 14);
	t = (b ^ (b >> 28)) & 0x00000000F0F0F0F0ULL;
	b = b ^ t ^ (t << 28);

	return b;
}

上記のコードは、以下のオセロソフトのコードで用いられていました。

github.com

一方、AVX2を使うと等価な処理を以下のようにも書けます。

uint64_t transpose_bitboard_avx2(uint64_t b) {
	//引数が8x8 bitboardだとして、転置して返す。

	const __m256i bb = _mm256_set1_epi64x(b);
	const __m256i x1 = _mm256_sllv_epi64(bb, _mm256_set_epi64x(0, 1, 2, 3));
	const __m256i x2 = _mm256_sllv_epi64(bb, _mm256_set_epi64x(4, 5, 6, 7));
	const int y1 = _mm256_movemask_epi8(x1);
	const int y2 = _mm256_movemask_epi8(x2);

	return (uint64_t(uint32_t(y1)) << 32) + uint64_t(uint32_t(y2));
}

_mm256_movemask_epi8関数は、256bit整数を8bit整数32個として解釈したうえで、各8bit整数の最上位ビットを集めて1つの32bit整数にして返り値とする関数です。なので、64bit整数を0～7bit左シフトしてから_mm256_movemask_epi8関数に与えることで転置ができます。