Bit Boardの反転
上下反転・左右反転
#Bit_reverse の途中まで/途中からを行うとできる。特に、バイトレベルで反転できる(x86のbswap, armのrev)場合や、ビット列の反転ができる(armのrbit)場合は、それを用いることで改善できることもある。 転置(斜めに反転)
code:transpose
0123
4567
89ab
cdef
↓ mask: 0b0000000011001100, delta: 6
0189
45cd
23ab
67ef
↓ mask: 0b0000101000001010, delta: 3
048c
159d
26ae
37bf
movmsk(move mask)命令は、SIMDレーンの各バイトのMSBを集めたビット列を汎用レジスタに持ってくることができる。
これを用いると、
code:transpose_move_mask
0123
4567
89ab
cdef
↓1バイトに1行、それを列の大きさかSIMD幅いっぱいまで複製
0123xxxx 4567xxxx 89abxxxx cdefxxxx 0123xxxx 4567xxxx 89abxxxx cdefxxxx 0123xxxx 4567xxxx 89abxxxx cdefxxxx 0123xxxx 4567xxxx 89abxxxx cdefxxxx
↓先頭の4行分を0bit、次の4行分を1bit、その次の4行分を2bit、…と複製ごとに1bitずらしでシフトする(ここでAVXが必要になる)
0123xxxx 4567xxxx 89abxxxx cdefxxxx 123xxxxx 567xxxxx 9abxxxxx defxxxxx 23xxxxxx 67xxxxxx abxxxxxx efxxxxxx 3xxxxxxx 7xxxxxxx bxxxxxxx fxxxxxxx
↓ move mask
048c 159d 26ae 37bf
1行が8bit未満だと、行ごとに分配する操作が必要だが、例えば1行4bitであれば、vpunpckhbwを使って次のようにできる。
code:unpack
01234567 89abcdef xxxxxxxx xxxxxxxx
↓自分自身とvpunpckhbw
01234567 01234567 89abcdef 89abcdef
↓16bit単位で(x & 0xf) << 4 | (x & 0xf000)
0123xxxx 4567xxxx