SSEを用いたbsr/bsf命令の実現に向けて　その6 - Bonanzaソース完全解析ブログ

integer→float変換を使うぐらいなら、乗算を使えばどうかというのは自然な流れでして、コツがわかったところで、完全ハッシュを使うことを考えます。

参考:http://d.hatena.ne.jp/siokoshou/20090704

まず1になっている最下位のビットを得るところは、普通、こうするのですが、

x &= -x; // 1になっている最下位のビットが得られる

SSEにはneg(符号反転命令)がなかったと思うのでnotしたものに1を足すとしまして…。ああ、notもないのでandnotを使うとしまして…。

packed s32(signed int)に対して、1になっている最下位のビットが得られたとしまして、そこに完全ハッシュであるpacked s32を乗算してその下位32ビットを得る命令(_mm_mullo_epi32。アセンブリ命令はPMULLD -- Multiply Packed Signed Dword Integers and Store Low Resultの略らしいです。)を用いますとpacked s32の上位6bitに1になっていたビット位置を示す値が入ってくると。

各packed s32の上位6bitにはビット位置を示す値が入ってくるので、昨日の記事と同じ要領で、適当にオフセットを足りたりしまして…

  bb += (u128)0x00000000d80000006c00000000000000;
  //  27*4 = 0x6c , 27*2*4 = 0xd8

  bb |= (u128)0xffffffff03ffffff03ffffff03ffffff;
  // 関係ないところを1で潰しておく必要がある。

そのあとpacked s16の最小値を_mm_minpos_epu16で取ってきて、BoardPosition(盤面上の座標)に変換するためのテーブルを1回lookupするというのが基本的な流れになります。

・bsr/bsfのどちらかにするかというこだわりはなく、盤面(Bitboard)上のどこでもいいから1になっているビットを1つとってこれればいいだけだと考えています。

・BoardPositionに変換するためのテーブルをlookupするのが馬鹿らしいので、駒の利きのBitboardとかを事前にそのテーブルで逆変換した順番に格納しておけば、そのテーブルをlookupする処理がはしょれます。

・packed s32の掛け算を使いましたが、packed s16の掛け算(packedされたそれぞれのs16のうち下位12bitを、将棋盤の12升ずつ割り当てるだとか、そういう変則的なBitboardを考えます)でもいけるかも知れません。packed s32よりpacked s16の掛け算のほうが高速であるなら、そういうアプローチもありかな、と。

・bsr/bsf相当の値を得たあと、1になっていたビットを消すのが Xor(bitboard , masks[boardPosition] )のようにテーブルをlookupしてxorしないといけないのは嫌ですね。

ということで完全ハッシュを使う方法がうまくハマればいいのですが、いまの命令セットではなかなか難しいということでした。まあ、どこかに応用できるかも知れないのでアイデアだけ羅列しておきました。