RISC-Vのビット操作系拡張(B拡張)のまとめ(その5)

ブール環( \mathbb{F}_2 \mathbb{Z}/2\mathbb{Z}、“足し算”がxorで“掛け算”がandであるような演算体系、“2で割ったあまり”)に関係する命令群です。

clmul, clmulh, clmulr

繰上りなしの掛け算です。ビット列の畳み込みと考えることもできます。

clmulは掛け算の結果の下32/64ビットを返します。 clmulhは掛け算の結果の上32/64ビット(下から32~63/64~127ビット目)を返します。 ここで、繰上りがないため、clmulhの最上位ビットは常に0です。

clmulrはその再上位ビットを除いた上32/64ビット(下から31~62/63~126ビット目)を返します。 名前のrは、reverseに由来します。clmulrの結果は、ビット順序逆転した結果同士のclmulの結果のビット順序逆転と同じになるからです。

巡回冗長検査(Cyclic Redundancy Check, CRC)やハッシュ関数の実装などに有用だそうです。 自分自身とのclmul/clmulhを使うと、0を00に、1を01に変換する(32/64ビットのビット列の各ビットの間に0を挿入して64/128ビットのビット列にする)操作を実現します。 また、-1とのclmulはprefix sum(ここで言うsumはxor)を求めるのに使えます(グレイコードのデコードに使えます)。

crc32, crc32c

巡回冗長検査(CRC)をまさにそのまま計算する命令です。

bmatxor, bmator, bmatflip

64bitのレジスタを、8×8のビット行列だとみなして、行列演算を行う命令です。

bmatxorは、“足し算”がxorであるような行列乗算、bmatorは“足し算”がorであるような凝結乗算、bmatflipは行列転置です。

bmatflipは、zip三回分に相当します。