SSE4.2 にある、文字（列）検索に適した 4 つの命令
PCMPESTRI , PCMPESTRM , PCMPISTRI , PCMPISTRM
の動作をマニュアルを見つつ調べてみます。
4つの PCMPxSTRy 命令
まとめて PCMP<x>STR<y> 命令とすると、アセンブリ言語では
PCMP<x>STR<y> xmm1, xmm2, imm8
PCMP<x>STR<y> xmm1, m128, imm8
の記述になっています。 xmm1 が検索内容で、xmm2/m128 が検索対象です。
<x> と <y> は入力形式（x：E または I）と出力形式（y：I または M）の指定です。
入力形式<x> と出力形式<y>
指定したオペランドとフラグ レジスタのほかに、入力形式 <x> と出力形式 <y> により決まったレジスタが使用されます。
| - | y = I : Index | y = M : Mask | 入力用レジスタ |
|---|---|---|---|
| x = E : Explicit | PCMPESTRI | PCMPESTRM | EAX(RAX) と EDX(RDX) |
| x = I : Implicit | PCMPISTRI | PCMPISTRM | なし |
| 出力用レジスタ | ECX(RCX) | XMM0 | - |
文字の種類と数
オペランドに指定する xmm1 および xmm2/m128 のデータ形式は、第3オペランド imm8 の下位 2 ビット
imm8[0] = 文字のビット幅
imm8[1] = 符号の有無
で指定します。
| imm8 | +0（8 ビット） | +1（16 ビット） |
|---|---|---|
| +0（符号なし） | 符号なし 8 ビット 16 文字 uint8_t [16] |
符号なし 16 ビット 8 文字 uint16_t [8] |
| +2（符号あり） | 符号あり 8 ビット 16 文字 int8_t [16] |
符号あり 16 ビット 8 文字 int16_t [8] |
以下、文字数（8 ビットなら 16 文字、16 ビットなら 8 文字）を PLEN とします。
有効な文字数
各オペランドと有効な文字数は以下のとおりです。
| 命令 ＼ オペランド | xmm1 | xmm2/m128 | 内容 |
|---|---|---|---|
| x=E 形式 PCMPESTR<y> |
EAX(RAX) | EDX(RDX) | レジスタによる指定 |
| x=I 形式 PCMPISTR<y> |
strlen(xmm1) | strlen(xmm2/m128) | NULL(を含まない)文字まで |
レジスタによる指定では、負の値も絶対値として正の値に変換されるので有効です。実際に有効な文字数の上限は imm8 に指定した文字数 PLEN になります。
以下、有効な文字数を
XLEN1 を第 1 オペランド xmm1 に対するもの
XLEN2 を第 2 オペランド xmm2/m128 に対するもの
とします。
動作モード（Mode）
検索の目的を imm8 の第 2 および第 3 ビットで指定します。
| Mode imm8[3:2] |
比較方法 | 内容 |
|---|---|---|
| 0 | 一致 | xmm1 を文字セットとします |
| 1 | 範囲 | xmm1 を文字の範囲情報とします |
| 2 | 一致 | xmm1 と xmm2/m128 の配列一致 |
| 3 | 一致 | xmm1 を部分文字列として検索します |
比較方法は、"一致" と "範囲" の 2 種類になります。
比較判定表（BoolRes）
xmm2/m128 の 1 文字に対して xmm1 の PLEN 文字と比較し、比較判定表（PLEN×PLEN）が作られます。
以下の比較判定表では、横軸を xmm1、縦軸を xmm2/m128 とします。
比較方法：一致（eq）
| BoolRes | 1 文字目 | … | PLEN 文字目 |
|---|---|---|---|
| 1 文字目 | eq | … | eq |
| … | … | … | … |
| PLEN 文字目 | eq | … | eq |
比較方法：範囲（ge,le）
xmm1 は 2 文字で 1 つの範囲を構成します。よって、最大で (PLEN÷2) 個の範囲を指定できます。
| BoolRes | 1 文字目 範囲開始 |
2 文字目 範囲終了 |
… | PLEN-1 文字目 範囲開始 |
PLEN 文字目 範囲終了 |
|---|---|---|---|---|---|
| 1 文字目 | ge | le | … | ge | le |
| … | … | … | … | … | |
| PLEN 文字目 | ge | le | … | ge | le |
有効文字数による修正
xmm1 では XLEN1 文字より後を、xmm2/m128 では XLEN2 文字より後を固定の真偽値として比較判定表（BoolRes）が修正されます。（以下の表では「文字目」を省きます）
Mode 0
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN |
|---|---|---|---|---|---|---|
| 1 | eq | … | eq | false | … | false |
| … | … | … | … | … | … | … |
| XLEN2 | eq | … | eq | false | … | false |
| XLEN2+1 | false | … | false | false | … | false |
| … | … | … | … | … | … | … |
| PLEN | false | … | false | false | … | false |
Mode 1
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN |
|---|---|---|---|---|---|---|
| 1 | ge | … | ge/le | false | … | false |
| … | … | … | … | … | … | … |
| XLEN2 | ge | … | ge/le | false | … | false |
| XLEN2+1 | false | … | false | false | … | false |
| … | … | … | … | … | … | … |
| PLEN | false | … | false | false | … | false |
Mode 0 と 1 の修正は同じです。
Mode 2
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN |
|---|---|---|---|---|---|---|
| 1 | eq | … | eq | false | … | false |
| … | … | … | … | … | … | … |
| XLEN2 | eq | … | eq | false | … | false |
| XLEN2+1 | false | … | false | true | … | true |
| … | … | … | … | … | … | … |
| PLEN | false | … | false | true | … | true |
Mode 3
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN |
|---|---|---|---|---|---|---|
| 1 | eq | … | eq | true | … | true |
| … | … | … | … | … | … | … |
| XLEN2 | eq | … | eq | true | … | true |
| XLEN2+1 | false | … | false | true | … | true |
| … | … | … | … | … | … | … |
| PLEN | false | … | false | true | … | true |
結果生成（その1：IntRes1）
修正された比較判定表（BoolRes）から xmm2/m128 の各文字に対する真偽値表（IntRes1）が生成されます。値は PLEN ビット列で表現されます。IntRes1 があるということは、加工された IntRes2 も生成されます。
以下の表では XLEN2 文字目より後の結果が固定になっていますが、これは XLEN1 や XLEN2 が PLEN より小さい場合で、比較判定表が修正された場合に限ります。
Mode 0：文字セット
xmm2/m128 の文字が xmm1 に含まれていたら true になります。
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN | 結果（IntRes1） |
|---|---|---|---|---|---|---|---|
| 1 | eq | … | eq | false | … | false | この行の論理和 |
| … | … | … | … | … | … | … | … |
| XLEN2 | eq | … | eq | false | … | false | この行の論理和 |
| XLEN2+1 | false | … | false | false | … | false | false |
| … | … | … | … | … | … | … | … |
| PLEN | false | … | false | false | … | false | false |
C
IntRes1 = 0;
for (x2 = 0; x2 < PLEN; x2++)
for (x1 = 0; x1 < PLEN; x1++)
IntRes1 |= BoolRes[x2][x1] << x2;
上記でのインデックスは 0 からです。
Mode 1：範囲
xmm2/m128 の文字は、xmm1 にある最大（PLEN÷2）個の範囲指定のいずれかならば true になります。
| BoolRes | 1 と 2 | 3 と 4 | … | XLEN1 | XLEN1+1 | … | PLEN | 結果（IntRes1） |
|---|---|---|---|---|---|---|---|---|
| 1 | ge and le | ge and le | … | ge/le | false | … | false | この行の論理和 |
| … | … | … | … | … | … | … | … | |
| XLEN2 | ge and le | ge and le | … | ge/le | false | … | false | この行の論理和 |
| XLEN2+1 | false | false | … | false | false | … | false | false |
| … | … | … | … | … | … | … | … | … |
| PLEN | false | false | … | false | false | … | false | false |
各行は「開始と終了の対を論理積」とした後の（PLEN÷2）個の論理和になります。
C
IntRes1 = 0;
for (x2 = 0; x2 < PLEN; x2++)
for (x1 = 0; x1 < PLEN; x1 += 2)
IntRes1 |= (BoolRes[x2][x1] & BoolRes[x2][x1+1]) << x2;
上記でのインデックスは 0 からです。
Mode 2：配列一致
文字列を配列で比較し、一致する文字を選択します。よって、表の左上から右下への対角が結果になります。
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN | 結果（IntRes1） |
|---|---|---|---|---|---|---|---|
| 1 | eq | … | eq | false | … | false | 1 文字目 |
| … | … | … | … | … | … | … | … |
| XLEN2 | eq | … | eq | false | … | false | XLEN2 文字目 |
| XLEN2+1 | false | … | false | true | … | true | XLEN1 と XLEN2 が同じ場合は true |
| … | … | … | … | … | … | … | … |
| PLEN | false | … | false | true | … | true | true |
C
IntRes1 = 0;
for (x2 = 0; x2 < PLEN; x2++)
IntRes1 |= BoolRes[x2][x2] << x2;
上記でのインデックスは 0 からです。
Mode 3：部分一致
xmm1 の文字列が xmm2/m128 に含まれている場合の開始位置が true になります。
以下の比較判定表
| BoolRes | 1 | … | XLEN1 | XLEN1+1 | … | PLEN |
|---|---|---|---|---|---|---|
| 1 | eq | … | eq | true | … | true |
| … | … | … | … | … | … | … |
| XLEN2 | eq | … | eq | true | … | true |
| XLEN2+1 | false | … | false | true | … | true |
| … | … | … | … | … | … | … |
| PLEN | false | … | false | true | … | true |
に対して
| BoolRes | 1 | … | … | … | PLEN |
|---|---|---|---|---|---|
| 1 | … | … | … | … | … |
| … | … | … | … | … | … |
| N | true | … | … | … | … |
| … | … | true | … | … | … |
| PLEN | … | … | true | … | … |
となっているならば N 文字目は true になります。
xmm1="ab", xmm2/m128="abcab" だと、2箇所の 'a' の位置が true です。
C
IntRes1 = ((1 << PLEN) - 1);
for (x2 = 0; x2 < PLEN; x2++)
for (x1 = 0; x1 < (PLEN - x2); x1++)
IntRes1 &= (BoolRes[x2+x1][x1] << x2) | ~(1 << x2);
上記でのインデックスは 0 からです。
結果生成（その2：IntRes2）
第 3 オペランド imm8 の第 4 および第 5 ビットの指定により IntRes1 を加工して IntRes2 が生成されます。
| Polarity imm8[5:4] |
操作 | 内容 |
|---|---|---|
| 0 | Positive Polarity | IntRes2 = IntRes1 |
| 1 | Negative Polarity | IntRes2 = ~IntRes1 |
| 2 | Masked (+) | IntRes2 = IntRes1 |
| 3 | Masked (-) | IntRes2 = ~IntRes1 ^ ((1 << PLEN) - (1 << XLEN2)) |
結果出力
命令によって出力先と内容が異なります。
| 形式 | レジスタ | 内容 | 命令 |
|---|---|---|---|
| y=I 形式 | ECX(RCX) | 文字位置 | PCMPESTRI , PCMPISTRI |
| y=M 形式 | XMM0 | ビット列 | PCMPESTRM , PCMPISTRM |
y=I 形式 PCMP<x>STRI 命令
ECX(RCX) レジスタの内容は、第 3 オペランド imm8 第6 ビットの指定により変化します。
| imm8[6] | ECX(RCX) レジスタ |
|---|---|
| 0 | IntRes2 で "1" となっている最小ビット位置： BSF(IntRes2) 相当 |
| 1 | IntRes2 で "1" となっている最大ビット位置： BSR(IntRes2) 相当 |
y=M 形式 PCMP<x>STRM 命令
XMM0 レジスタの内容は、第 3 オペランド imm8 第6 ビットの指定により変化します。
| imm8[6] | XMM0 レジスタ |
|---|---|
| 0 | IntRes2 を 128 ビットにゼロ拡張 |
| 1 | IntRes2 の各ビットを文字単位に拡張する （PCMPEQB や PCMPEQW と同じ形式） |
フラグ・レジスタ
| 内容 | |
|---|---|
| CF | IntRes2 != 0 |
| ZF | XLEN2 < PLEN |
| SF | XLEN1 < PLEN |
| OF | IntRes2 & 1 |
| AF | 0 |
| PF | 0 |
まとめ
PCMP<x>STR<y> xmm1, xmm2, imm8
PCMP<x>STR<y> xmm1, m128, imm8
| 命令 | op1 | op2 | op3 |
|---|---|---|---|
| PCMPESTRI | xmm1 | xmm2 m128 |
imm8 |
| PCMPESTRM | xmm1 | xmm2 m128 |
imm8 |
| PCMPISTRI | xmm1 | xmm2 m128 |
imm8 |
| PCMPISTRM | xmm1 | xmm2 m128 |
imm8 |
m128 のアドレスは 16 バイト境界でなくてもよいハズ。
命令形式と固定レジスタ
| y = I : Index | y = M : Mask | 入力用レジスタ | |
|---|---|---|---|
| x = E : Explicit | PCMPESTRI | PCMPESTRM | EAX(RAX) と EDX(RDX) |
| x = I : Implicit | PCMPISTRI | PCMPISTRM | なし |
| 出力用レジスタ | ECX(RCX) | XMM0 | - |
x=E 形式の有効文字数
| レジスタ | 対象 |
|---|---|
| EAX(RAX) | xmm1 |
| EDX(RDX) | xmm2/m128 |
負の場合は、絶対値として正の値に変換されます。
第 3 オペランド imm8
| ビット | 7 | 6 | 5:4 | 3:2 | 1:0 |
|---|---|---|---|---|---|
| 内容 | - | 出力形式 | Polarity | Mode | データ形式 |
| データ形式 imm8[1:0] |
+0（8 ビット） | +1（16 ビット） |
|---|---|---|
| +0（符号なし） | 符号なし 8 ビット 16 文字 uint8_t [16] |
符号なし 16 ビット 8 文字 uint16_t [8] |
| +2（符号あり） | 符号あり 8 ビット 16 文字 int8_t [16] |
符号あり 16 ビット 8 文字 int16_t [8] |
| Mode imm8[3:2] |
比較方法 | 内容 |
|---|---|---|
| 0 | 一致 | xmm1 を文字セットとします |
| 1 | 範囲 | xmm1 を文字の範囲情報とします 範囲は最小と最大の 2 文字で一組とする |
| 2 | 一致 | xmm1 と xmm2/m128 の配列一致 |
| 3 | 一致 | xmm1 を部分文字列として検索します |
| Polarity imm8[5:4] |
操作 | 内容 |
|---|---|---|
| 0 | Positive Polarity | IntRes2 = IntRes1 |
| 1 | Negative Polarity | IntRes2 = ~IntRes1 |
| 2 | Masked (+) | IntRes2 = IntRes1 |
| 3 | Masked (-) | IntRes2 = ~IntRes1 ^ ((1 << PLEN) - (1 << XLEN2)) |
出力形式： y=I 形式 PCMP<x>STRI 命令
| imm8[6] | ECX(RCX) レジスタ |
|---|---|
| 0 | IntRes2 で "1" となっている最小ビット位置： BSF(IntRes2) 相当 |
| 1 | IntRes2 で "1" となっている最大ビット位置： BSR(IntRes2) 相当 |
出力形式： y=M 形式 PCMP<x>STRM 命令
| imm8[6] | XMM0 レジスタ |
|---|---|
| 0 | IntRes2 を 128 ビットにゼロ拡張 |
| 1 | IntRes2 の各ビットを文字単位に拡張する （PCMPEQB や PCMPEQW と同じ形式） |
フラグ・レジスタ
| 内容 | |
|---|---|
| CF | IntRes2 != 0 |
| ZF | XLEN2 < PLEN |
| SF | XLEN1 < PLEN |
| OF | IntRes2 & 1 |
| AF | 0 |
| PF | 0 |
テスト・プログラム
動作環境
macOS BigSur 11.6
コンパイラ
Apple clang version 12.0.5 (clang-1205.0.22.11)
C++ ソース・コード
test_pcmpxstry.cpp
#include <cctype>
#include <cinttypes>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <nmmintrin.h>
/*
*
*/
static const char *program = NULL;
static bool flag_verbose = false;
/*
*
*/
union __x128
{
__m128 v;
__m128i vi;
__m128d vd;
int8_t i8[16];
int16_t i16[8];
int32_t i32[4];
int64_t i64[2];
uint8_t u8[16];
uint16_t u16[8];
uint32_t u32[4];
uint64_t u64[2];
void clear()
{
i64[0] = 0;
i64[1] = 0;
}
};
/*
*
*/
struct res_pcmpxstrx
{
__m128 m;
uint64_t i;
uint64_t f;
void clear()
{
m = _mm_setzero_si128();
i = 0;
f = 0;
}
};
#define CASE_IMM8_1(name, imm8) case imm8: return name<imm8>(xmm1, xmm2, regA, regD)
#define CASE_IMM8_2(name, imm8) CASE_IMM8_1(name, imm8 + 0); CASE_IMM8_1(name, imm8 + 1)
#define CASE_IMM8_4(name, imm8) CASE_IMM8_2(name, imm8 + 0); CASE_IMM8_2(name, imm8 + 2)
#define CASE_IMM8_8(name, imm8) CASE_IMM8_4(name, imm8 + 0); CASE_IMM8_4(name, imm8 + 4)
#define CASE_IMM8_16(name, imm8) CASE_IMM8_8(name, imm8 + 0); CASE_IMM8_8(name, imm8 + 8)
#define CASE_IMM8_32(name, imm8) CASE_IMM8_16(name, imm8 + 0); CASE_IMM8_16(name, imm8 + 16)
#define CASE_IMM8_64(name, imm8) CASE_IMM8_32(name, imm8 + 0); CASE_IMM8_32(name, imm8 + 32)
#define CASE_IMM8_128(name, imm8) CASE_IMM8_64(name, imm8 + 0); CASE_IMM8_64(name, imm8 + 64)
#define CASE_IMM8_256(name) CASE_IMM8_128(name, 0); CASE_IMM8_128(name, 128)
#define SWITCH_CASE_256(name, imm8) switch (imm8) { CASE_IMM8_256(name); default: break; }
#define IMPL_PCMPxSTRx(name) \
template <int imm8> \
inline static res_pcmpxstrx name(__m128i xmm1, __m128i xmm2, int regA, int regD) \
{ \
res_pcmpxstrx r; \
\
__m128i mask; \
uint64_t index; \
uint64_t flags; \
\
__asm__ volatile ("xorq %%rcx, %%rcx": "=c" (index)); \
__asm__ volatile ("pxor %%xmm0, %%xmm0": "=Yz" (mask)); \
\
__asm__ volatile (#name "\t" "%[imm8],%[xmm2],%[xmm1]\n" \
"pushfq\n" "popq" "\t" "%[freg]" \
: [freg] "=r" (flags), "=c" (index), "=Yz" (mask) \
: [xmm1] "x" (xmm1), [xmm2] "x" (xmm2), [imm8] "N" (imm8), \
"a" (regA), "d" (regD)); \
\
r.m = mask; \
r.i = index; \
r.f = flags & 0x08d5; /* 0000_1000_1101_0101 */ \
return r; \
} \
static res_pcmpxstrx name(__m128i xmm1, int regA, __m128i xmm2, int regD, int imm8) \
{ \
SWITCH_CASE_256(name, imm8); \
res_pcmpxstrx r; \
r.clear(); \
return r; \
}
IMPL_PCMPxSTRx(pcmpestri)
IMPL_PCMPxSTRx(pcmpestrm)
IMPL_PCMPxSTRx(pcmpistri)
IMPL_PCMPxSTRx(pcmpistrm)
typedef res_pcmpxstrx (*pcmpxstrx)(__m128i, int, __m128i, int, int);
static __m128i setbxmm(const char *s)
{
__x128 u;
int l = (s == NULL) ? 0 : strlen(s);
for (int i = 0; i < 16; i++)
u.i8[i] = (i < l) ? s[i] : 0;
return u.vi;
}
static __m128i setwxmm(const char *s)
{
__x128 u;
int l = (s == NULL) ? 0 : strlen(s);
for (int i = 0; i < 8; i++)
u.i16[i] = (i < l) ? s[i] : 0;
return u.vi;
}
static int strlen_x128b(const __x128 &s)
{
for (int i = 0; i < 16; i++)
if (s.i8[i] == 0)
return i;
return 16;
}
static int strlen_x128w(const __x128 &s)
{
for (int i = 0; i < 8; i++)
if (s.i16[i] == 0)
return i;
return 8;
}
typedef bool BoolRes[16][16];
static res_pcmpxstrx PCMPxSTRy(bool implicit /* <x> */,
bool mask /* <y> */,
__m128i xmm1, __m128i xmm2, uint8_t imm8,
int64_t rax, int64_t rdx,
BoolRes b_res,
uint16_t &i_res1,
uint16_t &i_res2,
int64_t &rcx)
{
res_pcmpxstrx res;
__x128 s1;
__x128 s2;
bool f_word = !!(imm8 & 0x01);
bool f_signed = !!(imm8 & 0x02);
int mode = (imm8 >> 2) & 3;
bool f_negative = !!(imm8 & 0x10);
bool f_masked = !!(imm8 & 0x20);
bool f_outsel = !!(imm8 & 0x40);
int ecnt = !f_word ? 16 : 8;
// bool b_res[16][16];
res.clear();
s1.v = xmm1;
s2.v = xmm2;
for (int i2 = 0; i2 < 16; i2++)
for (int i1 = 0; i1 < 16; i1++)
b_res[i2][i1] = false;
int32_t c1[16];
int32_t c2[16];
for (int i = 0; i < 16; i++)
c1[i] = c2[i] = 0;
if (!f_signed)
{
if (!f_word)
{
for (int i = 0; i < 16; i++)
{
c1[i] = s1.u8[i];
c2[i] = s2.u8[i];
}
}
else
{
for (int i = 0; i < 8; i++)
{
c1[i] = s1.u16[i];
c2[i] = s2.u16[i];
}
}
}
else
{
if (!f_word)
{
for (int i = 0; i < 16; i++)
{
c1[i] = s1.i8[i];
c2[i] = s2.i8[i];
}
}
else
{
for (int i = 0; i < 8; i++)
{
c1[i] = s1.i16[i];
c2[i] = s2.i16[i];
}
}
}
if (!implicit)
{
if (rax < 0) rax = -rax;
if (rdx < 0) rdx = -rdx;
}
else
{
rax = !f_word ? strlen_x128b(s1) : strlen_x128w(s1);
rdx = !f_word ? strlen_x128b(s2) : strlen_x128w(s2);
}
if (rax > ecnt) rax = ecnt;
if (rdx > ecnt) rdx = ecnt;
int l1 = int(rax);
int l2 = int(rdx);
if (mode != 1)
{
for (int i2 = 0; i2 < ecnt; i2++)
for (int i1 = 0; i1 < ecnt; i1++)
b_res[i2][i1] = (c1[i1] == c2[i2]);
}
else
{
for (int i2 = 0; i2 < ecnt; i2++)
{
for (int i1 = 0; i1 < ecnt; i1 += 2)
{
b_res[i2][i1 + 0] = (c1[i1 + 0] <= c2[i2]);
b_res[i2][i1 + 1] = (c1[i1 + 1] >= c2[i2]);
}
}
}
bool o1 = false;
bool o2 = false;
bool o3 = false;
switch (mode)
{
case 3: o1 = true;
case 2: o3 = true;
default: break;
}
for (int i1 = l1; i1 < ecnt; i1++)
for (int i2 = 0; i2 < l2; i2++)
b_res[i2][i1] = o1;
for (int i2 = l2; i2 < ecnt; i2++)
{
for (int i1 = 0; i1 < l1; i1++)
b_res[i2][i1] = o2;
for (int i1 = l1; i1 < ecnt; i1++)
b_res[i2][i1] = o3;
}
bool i_res[16];
for (int i = 0; i < 16; i++)
i_res[i] = false;
switch (mode)
{
case 0:
for (int i2 = 0; i2 < ecnt; i2++)
for (int i1 = 0; i1 < ecnt; i1++)
i_res[i2] |= b_res[i2][i1];
break;
case 1:
for (int i2 = 0; i2 < ecnt; i2++)
for (int i1 = 0; i1 < ecnt; i1 += 2)
i_res[i2] |= (b_res[i2][i1 + 0] & b_res[i2][i1 + 1]);
break;
case 2:
for (int i = 0; i < ecnt; i++)
i_res[i] = b_res[i][i];
break;
case 3:
for (int i2 = 0; i2 < ecnt; i2++)
{
i_res[i2] = true;
for (int i1 = 0; i1 < (ecnt - i2); i1++)
i_res[i2] &= b_res[i2 + i1][i1];
}
break;
default:
break;
}
// uint16_t i_res1;
i_res1 = 0;
for (int i = 0; i < ecnt; i++)
i_res1 |= (i_res[i] << i);
if (f_negative)
{
int ncnt = !f_masked ? ecnt : l2;
for (int i = 0; i < ncnt; i++)
i_res[i] = !i_res[i];
}
// uint16_t i_res2;
i_res2 = 0;
for (int i = 0; i < ecnt; i++)
i_res2 |= (i_res[i] << i);
// int64_t rcx;
rcx = ecnt;
if (i_res2 != 0)
{
int i;
if (!f_outsel)
{
for (i = 0; i < ecnt; i++)
if (i_res[i])
break;
}
else
{
for (i = ecnt - 1; i >= 0; i--)
if (i_res[i])
break;
}
rcx = i;
}
__x128 xmm0;
xmm0.clear();
if (!f_outsel)
xmm0.u16[0] = i_res2;
else if (!f_word)
for (int i = 0; i < 16; i++)
xmm0.i8[i] = (i_res[i] ? -1 : 0);
else
for (int i = 0; i < 8; i++)
xmm0.i16[i] = (i_res[i] ? -1 : 0);
if (!mask)
res.i = rcx;
else
res.m = xmm0.v;
if (i_res2 != 0)
res.f |= (1 << 0);
if (l2 < ecnt)
res.f |= (1 << 6);
if (l1 < ecnt)
res.f |= (1 << 7);
if ((i_res2 & 1))
res.f |= (1 << 11);
return res;
}
static const char *format_flag(uint64_t flags)
{
static char msg[16];
char *d = msg;
*d++ = (flags & (1 << 0)) ? 'C' : '-';
*d++ = (flags & (1 << 6)) ? 'Z' : '-';
*d++ = (flags & (1 << 7)) ? 'S' : '-';
*d++ = (flags & (1 << 11)) ? 'O' : '-';
*d++ = (flags & (1 << 4)) ? 'A' : '-';
*d++ = (flags & (1 << 2)) ? 'P' : '-';
*d++ = 0;
return msg;
}
static void print_xmm_char(__m128i xmm)
{
__x128 u;
u.vi = xmm;
for (int i = 0; i < 16; i++)
printf("%c", isprint(u.u8[i]) ? u.u8[i] : '.');
}
static void print_xmm_hex(__m128i xmm)
{
__x128 u;
u.vi = xmm;
const char *sep = "";
for (int i = 0; i < 4; i++)
{
printf("%s%08x", sep, u.u32[3 - i]);
sep = "_";
}
}
static int test(const char *insn, pcmpxstrx func, const char *s1, const char *s2, int imm8, int len1, int len2)
{
bool flag_wchar = (imm8 & 1);
__m128i xmm1 = (flag_wchar ? setwxmm(s1) : setbxmm(s1));
__m128i xmm2 = (flag_wchar ? setwxmm(s2) : setbxmm(s2));
bool implicit = (insn[4] == 'i');
bool mask = (insn[8] == 'm');
printf("%s:\n", insn);
printf(" <-- xmm1 = ");
print_xmm_hex(xmm1);
if (!implicit)
printf(", EAX = %d", len1);
printf("\n");
printf(" <-- xmm2 = ");
print_xmm_hex(xmm2);
if (!implicit)
printf(", EDX = %d", len2);
printf("\n");
printf(" <-- imm8 = 0x%02x\n", imm8);
res_pcmpxstrx res = func(xmm1, len1, xmm2, len2, imm8);
printf(" --> FLAG = %s\n", format_flag(res.f));
if (!mask)
printf(" --> ECX(RCX) = %2"PRIu64"\n", res.i);
else
printf(" --> XMM0 = "), print_xmm_hex(res.m), printf("\n");
BoolRes b_res;
uint16_t i_res1, i_res2;
int64_t rcx;
res_pcmpxstrx emu = PCMPxSTRy(implicit, mask, xmm1, xmm2, imm8, len1, len2, b_res, i_res1, i_res2, rcx);
printf("PCMPxSTRy:\n");
printf(" --> FLAG = %s\n", format_flag(emu.f));
if (!mask)
printf(" --> ECX(RCX) = %2"PRIu64"\n", emu.i);
else
printf(" --> XMM0 = "), print_xmm_hex(emu.m), printf("\n");
int ecnt = (imm8 & 1) ? 8 : 16;
__x128 x1;
__x128 x2;
x1.v = xmm1;
x2.v = xmm2;
printf(" BoolRes: ");
for (int i = 0; i < ecnt; i++)
{
int c = flag_wchar ? x1.i16[i] : x1.i8[i];
printf("%c", isprint(c) ? c : ' ');
}
printf("\n");
for (int i2 = 0; i2 < ecnt; i2++)
{
char b[32];
for (int i1 = 0; i1 < ecnt; i1++)
b[i1] = (b_res[i2][i1] ? '1' : '.');
b[ecnt] = 0;
int c = flag_wchar ? x2.i16[i2] : x2.i8[i2];
if (!isprint(c))
c = ' ';
printf(" '%c'[%d]: %s\n", c, bool(i_res1 & (1 << i2)), b);
}
printf(" IntRes1: 0x%08x\n", i_res1);
printf(" IntRes2: 0x%08x\n", i_res2);
printf(" Index : %"PRId64"\n", rcx);
return 0;
}
#define IMPL_TEST(name) \
static int test_##name(const char *s1, const char *s2, int imm8, int len1, int len2) \
{ \
return test(#name, name, s1, s2, imm8, len1, len2); \
}
IMPL_TEST(pcmpestri);
IMPL_TEST(pcmpestrm);
IMPL_TEST(pcmpistri);
IMPL_TEST(pcmpistrm);
/*
* main / usage
*/
static int usage()
{
printf("Usage: %s [options] instruction str1 str2 imm8 [len1 len2]\n"
"\n"
"imm8:\n"
" binary - 0bBBBBBBBBBB, xBBBBBBBB\n"
" hex - 0xHH, xHH\n"
" %%[format]\n"
" b - byte\n"
" w - word\n"
" u - unsigned\n"
" s - signed\n"
" 0 - Mode 0\n"
" 1 - Mode 1\n"
" 2 - Mode 2\n"
" 3 - Mode 3\n"
" P - Positive Polarity\n"
" p - Negative Polarity\n"
" M - Masked (+)\n"
" m - Masked (-)\n"
" O - least significant index / bit mask\n"
" o - most significant index / byte/word mask\n"
"\n"
, program);
return 1;
}
static char *shift_arg(int &argc, char **&argv)
{
char *arg = NULL;
if (argc > 0)
{
arg = *argv;
--argc;
++argv;
}
return arg;
}
#define shift() (shift_arg(argc, argv))
int main(int argc, char **argv)
{
int new_argc = 0;
char **new_argv = argv;
program = shift();
while (argc > 0)
{
char *arg = shift();
if ((arg[0] != '-') || (arg[1] == 0))
{
new_argv[new_argc++] = arg;
continue;
}
int s_opt;
while ((s_opt = *(++arg)) != 0)
{
switch (s_opt)
{
case 'v':
flag_verbose = true;
continue;
default:
return usage();
}
}
}
argc = new_argc;
argv = new_argv;
if (argc < 4)
return usage();
const char *instruction = argv[0];
const char *str1 = argv[1];
const char *str2 = argv[2];
const char *imm8s = argv[3];
int len1 = strlen(str1);
int len2 = strlen(str2);
if (argc > 4)
{
if (argc != 6)
return usage();
len1 = strtol(argv[4], NULL, 10);
len2 = strtol(argv[5], NULL, 10);
}
int imm8 = 0;
{
if (imm8s[0] == '0' &&
(imm8s[1] == 'b' || imm8s[1] == 'x'))
++imm8s;
switch (imm8s[0])
{
case '%':
while ((++imm8s)[0])
{
switch (imm8s[0])
{
// Source Data Format
case 'b': // byte
imm8 &= ~1;
continue;
case 'w': // word
imm8 |= 1;
continue;
case 'u': // unsigned
imm8 &= ~2;
continue;
case 's': // signed
imm8 |= 2;
continue;
// Mode
case '0': // Mode 0
imm8 &= ~0x0c;
continue;
case '1': // Mode 1
imm8 &= ~0x0c;
imm8 |= 0x04;
continue;
case '2': // Mode 2
imm8 &= ~0x0c;
imm8 |= 0x08;
continue;
case '3': // Mode 3
imm8 |= 0x0C;
continue;
// Polarity
case 'P': // Positive Polarity
imm8 &= ~0x30;
continue;
case 'p': // Negative Polarity
imm8 &= ~0x30;
imm8 |= 0x10;
continue;
case 'M': // Masked (+)
imm8 &= ~0x30;
imm8 |= 0x20;
continue;
case 'm': // Masked (-)
imm8 |= 0x30;
continue;
// Output Selection
case 'O':
imm8 &= ~0x40;
continue;
case 'o':
imm8 |= 0x40;
continue;
default:
return usage();
}
}
break;
case 'b':
imm8 = strtol(imm8s + 1, NULL, 2);
break;
case 'x':
imm8 = strtol(imm8s + 1, NULL, 16);
break;
default:
imm8 = strtol(imm8s, NULL, 10);
break;
}
}
if (!strcasecmp(instruction, "PCMPESTRI")) return test_pcmpestri(str1, str2, imm8, len1, len2);
if (!strcasecmp(instruction, "PCMPESTRM")) return test_pcmpestrm(str1, str2, imm8, len1, len2);
if (!strcasecmp(instruction, "PCMPISTRI")) return test_pcmpistri(str1, str2, imm8, len1, len2);
if (!strcasecmp(instruction, "PCMPISTRM")) return test_pcmpistrm(str1, str2, imm8, len1, len2);
printf("unknown instruction: %s\n", instruction);
return 2;
}
実験結果
モード 0：文字セット
文字列に含まれている文字 "aeiou" を判定する。
$ ./test_pcmpxstry pcmpistrm "aeiou" "honjitsuhaseiten" %0
pcmpistrm:
<-- xmm1 = 00000000_00000000_00000075_6f696561
<-- xmm2 = 6e657469_65736168_75737469_6a6e6f68
<-- imm8 = 0x00
--> FLAG = C-S---
--> XMM0 = 00000000_00000000_00000000_00005a92
PCMPxSTRy:
--> FLAG = C-S---
--> XMM0 = 00000000_00000000_00000000_00005a92
BoolRes: aeiou
'h'[0]: ................
'o'[1]: ...1............
'n'[0]: ................
'j'[0]: ................
'i'[1]: ..1.............
't'[0]: ................
's'[0]: ................
'u'[1]: ....1...........
'h'[0]: ................
'a'[1]: 1...............
's'[0]: ................
'e'[1]: .1..............
'i'[1]: ..1.............
't'[0]: ................
'e'[1]: .1..............
'n'[0]: ................
IntRes1: 0x00005a92
IntRes2: 0x00005a92
Index : 1
モード 1：文字範囲
文字列に含まれている文字を regex の "[0-9A-Za-z]" 相当で判定する。'_' は文字数を明示して意図的に外した。
$ ./test_pcmpxstry pcmpestrm "09AZaz__" "int sample_1234;" %1 6 16
pcmpestrm:
<-- xmm1 = 00000000_00000000_5f5f7a61_5a413930, EAX = 6
<-- xmm2 = 3b343332_315f656c_706d6173_20746e69, EDX = 16
<-- imm8 = 0x04
--> FLAG = C-SO--
--> XMM0 = 00000000_00000000_00000000_00007bf7
PCMPxSTRy:
--> FLAG = C-SO--
--> XMM0 = 00000000_00000000_00000000_00007bf7
BoolRes: 09AZaz__
'i'[1]: 1.1.11..........
'n'[1]: 1.1.11..........
't'[1]: 1.1.11..........
' '[0]: .1.1.1..........
's'[1]: 1.1.11..........
'a'[1]: 1.1.11..........
'm'[1]: 1.1.11..........
'p'[1]: 1.1.11..........
'l'[1]: 1.1.11..........
'e'[1]: 1.1.11..........
'_'[0]: 1.1..1..........
'1'[1]: 11.1.1..........
'2'[1]: 11.1.1..........
'3'[1]: 11.1.1..........
'4'[1]: 11.1.1..........
';'[0]: 1..1.1..........
IntRes1: 0x00007bf7
IntRes2: 0x00007bf7
Index : 0
モード 2：各文字の比較
文字列の各文字を比較する。モードに Negative Polarity をセットすると CF=0 で文字列の一致を判定できる。
$ ./test_pcmpxstry pcmpistri "instruction" "instruction" %2p
pcmpistri:
<-- xmm1 = 00000000_006e6f69_74637572_74736e69
<-- xmm2 = 00000000_006e6f69_74637572_74736e69
<-- imm8 = 0x18
--> FLAG = -ZS---
--> ECX(RCX) = 16
PCMPxSTRy:
--> FLAG = -ZS---
--> ECX(RCX) = 16
BoolRes: instruction
'i'[1]: 1.......1.......
'n'[1]: .1........1.....
's'[1]: ..1.............
't'[1]: ...1...1........
'r'[1]: ....1...........
'u'[1]: .....1..........
'c'[1]: ......1.........
't'[1]: ...1...1........
'i'[1]: 1.......1.......
'o'[1]: .........1......
'n'[1]: .1........1.....
' '[1]: ...........11111
' '[1]: ...........11111
' '[1]: ...........11111
' '[1]: ...........11111
' '[1]: ...........11111
IntRes1: 0x0000ffff
IntRes2: 0x00000000
Index : 16
モード 3：文字列の部分一致
文字列から部分文字列の先頭を見つける。以下の例では、"abcdef" が2箇所ある。
$ ./test_pcmpxstry pcmpistrm "abcdef" "01abcdefabcdefgh" %3
pcmpistrm:
<-- xmm1 = 00000000_00000000_00006665_64636261
<-- xmm2 = 68676665_64636261_66656463_62613130
<-- imm8 = 0x0c
--> FLAG = C-S---
--> XMM0 = 00000000_00000000_00000000_00000104
PCMPxSTRy:
--> FLAG = C-S---
--> XMM0 = 00000000_00000000_00000000_00000104
BoolRes: abcdef
'0'[0]: ......1111111111
'1'[0]: ......1111111111
'a'[1]: 1.....1111111111
'b'[0]: .1....1111111111
'c'[0]: ..1...1111111111
'd'[0]: ...1..1111111111
'e'[0]: ....1.1111111111
'f'[0]: .....11111111111
'a'[1]: 1.....1111111111
'b'[0]: .1....1111111111
'c'[0]: ..1...1111111111
'd'[0]: ...1..1111111111
'e'[0]: ....1.1111111111
'f'[0]: .....11111111111
'g'[0]: ......1111111111
'h'[0]: ......1111111111
IntRes1: 0x00000104
IntRes2: 0x00000104
Index : 2
PCMPxSTRy を使ったサンプル・プログラム
コンパイラ: Apple clang version 13.0.0 (clang-1300.0.29.3)
実行環境: macOS Big Sur (11.6)
メモリ・アクセスを 16 バイト境界の 16 バイト単位行う strlen 関数(x86:64ビット)
最初の 16 バイト内の調査では PCMPESTRM を、後続は PCMPESTRI を使用する。
strlen_sse4_2.c
#include <inttypes.h>
#include <x86intrin.h>
size_t strlen_sse4_2(const char *s)
{
size_t len;
intptr_t is = (intptr_t)s;
int os = (int)(is & 15);
const __m128i *p;
__m128i x0, xm;
int im;
int n;
/* とりあえず prefetch を発行してみる */
_mm_prefetch(s, _MM_HINT_T0);
/* 16 バイト境界で処理しないと SEGV の恐れあり */
p = (const __m128i *)(is - os);
/* 先頭 16 バイトの調査 */
x0 = _mm_setzero_si128();
xm = _mm_cmpestrm(x0, 16, _mm_load_si128(p++), 16, _SIDD_CMP_EQUAL_EACH);
im = _mm_cvtsi128_si32(xm) & (-1 << os);
if (im != 0)
return (_bit_scan_forward(im) - os);
/* 後続の調査 */
len = 16 - os;
do
{
/* 16 文字の中で 0 の部分を検索: 16 で次へ */
n = _mm_cmpestri(x0, 16, _mm_load_si128(p++), 16, _SIDD_CMP_EQUAL_EACH);
len += n;
}
while (n >= 16);
return len;
}
アセンブラ版
strlen_sse4_2.S
.section __TEXT,__text,regular,pure_instructions
.build_version macos, 11, 0 sdk_version 11, 3
.globl _strlen_sse4_2
_strlen_sse4_2:
.cfi_startproc
prefetcht0 (%rdi)
movq %rdi, %rcx
movq %rdi, %rsi
andq $15, %rcx
pxor %xmm2, %xmm2
subq %rcx, %rdi
movq $16, %rax
movq $16, %rdx
pcmpestrm $8, (%rdi), %xmm2
movq $-1, %r8
shlq %cl, %r8
movq %xmm0, %rcx
andq %r8, %rcx
bsfq %rcx, %rcx
jnz 2f
1: pcmpestri $8, 16(%rdi), %xmm2
lea 16(%rdi), %rdi
jnc 1b
2: lea (%rcx, %rdi), %rax
subq %rsi, %rax
retq
.cfi_endproc
.subsections_via_symbols