特定の値を一次元配列内から探し、そのインデックス値を返します。指定した値が配列内に存在しない時は-1を返します。特定の値が一次元配列内に複数含まれる場合は、一番若いインデックス値を返します。以降に処理の概要図を示します。
64ビット整数型
呼び出し側・符号付
以降に、呼び出し側のC++コードを示します。common.hをincludeしていますがSIMDで記述したアセンブリ言語の関数と等価な機能を持つC++言語で記述した共通関数のヘッダです。最下部にソースコードを示します。条件は関数名に含まれます。
#include "..\common.h" // TEMPLATES #define T long long extern "C" { int asrchsq(const T*, const T, const size_t); } // main int main(void) { const size_t ArrLen = 4096; static_assert(ArrLen % 16 == 0, "number of elements must be an integral multiple of 16."); T a[ArrLen]; T value = 80; init(a, ArrLen); int cindex = cSrch (a, value, ArrLen); int aindex = asrchsq(a, value, ArrLen); string okng = cindex == aindex ? " OK!" : " NG!"; cout << "cpp: " << cindex << ", asm: " << aindex << okng << endl; // 検証用 for (size_t j = 1; j < 10; j++) { init(a, ArrLen); a[j] = value; int cindex = cSrch (a, value, ArrLen); int aindex = asrchsq(a, value, ArrLen); string okng = cindex == aindex ? " OK!" : " NG!"; cout << "cpp: " << cindex << ", asm: " << aindex << okng << endl; } return 0; }
一次元配列にランダムな値を与え、先ほどの関数を呼び出し一次元配列内に目的の値があるか調べます。
呼び出され側
64ビット整数型一次元配列に含まれる値を探し、そのインデックス値ます。以降に、マクロを使って開発したアセンブラーのコードを示します。符号ごとに関数を記述するのは面倒なのでマクロを使って記述します。本関数へ渡されるレジスターとデータの関係を以降の表に示します。
レジスタ | 内容 |
---|---|
rcx | 入力配列の先頭アドレス |
rdx | 探す値 |
r8 | 配列の要素数 |
: _MM_CMPINT_EQ EQU 0 ; - 等しい == ;------------------------------------------------------------------- ; macro mymacro macro MNAME, MINST public MNAME align 16 MNAME proc vpbroadcastq zmm1, rdx ; zmm1 = search value xor rax, rax ; clear index loop_f: MINST k1, zmm1, zmmword ptr [rcx+rax*8], _MM_CMPINT_EQ ktestb k1, k1 ; test mask bit jz short to_next kmovb rdx, k1 serch_bitpos: ror dl, 1 ; lsbから最初に立っているビットを探す jc short done_serch inc rax jmp short serch_bitpos ; ktestbで必ず立っているので、上限のチェックは不要 to_next: add rax, 8 cmp rax, r8 jb short loop_f ; loop mov eax, -1 ; not found done_serch: ; eaxに位置が入っている ret MNAME endp endm ;------------------------------------------------------------------- ; code _TEXT segment mymacro asrchsq, vpcmpq mymacro asrchuq, vpcmpuq _TEXT ends end end
mymacro マクロを定義し、これを使ってasrchsq関数とasrchuq関数を作ります。各関数の機能を表で示します。
関数名 | 機能 |
---|---|
asrchsq | 特定の値が、一次元符号付64ビット整数配列に含まれるか検査し、含まれるなら一番若いインデックス値を返します。特定の値が配列に存在しなければ-1を返します。 |
asrchuq | 特定の値が、一次元符号なし64ビット整数配列に含まれるか検査し、含まれるなら一番若いインデックス値を返します。特定の値が配列に存在しなければ-1を返します。 |
関数の内容を先頭から説明します。vpbroadcastq命令で、zmm1レジスターに特定の値(=探す値)をブロードキャストします。次にraxレジスターをクリアします。このraxレジスターは配列を参照するインデックスを保持します。次に、MINST を指定していますが、これはマクロの引数でvpcmpq命令かvpcmpuq命令へ置き換えられます。MINSTの第三引数は比較の条件で、ここでは_MM_CMPINT_EQを指定し、同じ値であるか調べます。対象とする一次元配列の要素に探す値と同じものが存在すると、マスクレジスターk1の対応するビットがオンになります。結果のk1レジスターをktestb命令で調べ、すべてのビットがオフなら次の要素の処理に移ります。そうでなければ、対象要素が見つかったときです。その時は、何番目のビットがオンであるか調べ、インデックス値を求めます。
対象要素が見つからない場合は、次の要素を処理するための前処理へ移ります。もし、全要素を処理済みなら、探す値が存在しなかったときですので -1 を返します。
common.h、共通関数
ヘッダーファイルの一部を示します。簡単な内容なので、説明は省きします。
: // sarch template <typename T> int cSrch(const T* a, const T value, const size_t length) { int r = -1; for (size_t i = 0; i < length; i++) { if ( a[i] == value) { r = i; break; } } return r; } :
すべての型に対応させるため、テンプレート関数とします。cSrch 関数は一次元配列に指定された値が存在するか調べ、存在するなら一番若いインデックス値を返します。指定した値が配列に存在しないときは-1を返します。
このプログラムの実行例を示します。
実行結果(signed)
C:\>ml64 /c srchAsm.asm
…
C:\>cl /O2 /EHsc srchQ.cpp srchAsm.obj
…
C:\>srchQ
cpp: -1, asm: -1 OK!
cpp: 1, asm: 1 OK!
cpp: 2, asm: 2 OK!
cpp: 3, asm: 3 OK!
cpp: 4, asm: 4 OK!
cpp: 5, asm: 5 OK!
cpp: 6, asm: 6 OK!
cpp: 7, asm: 7 OK!
cpp: 8, asm: 8 OK!
cpp: 9, asm: 9 OK!
正常に処理されているのが分かります。