PCMPxSTRx 命令の使い方

作成日:2012.11.17

更新履歴
(2012.11.17) 作成。


目次

命令の解説

PCMPESTRI、PCMPESTRM、PCMPISTRI、PCMPISTRM の 4 命令は SSE 4.2 からサポートされた文字列比較のための命令だ。 この命令グループには String and Text Processing Instructions という名前がついているが、この文章ではまとめて PCMPxSTRx 命令と呼ぶことにする。

PCMPxSTRx 命令は 2 つの XMM レジスタをオペランドにとり 16 バイトの文字列とみなして比較操作を行う。 第二オペランドは XMM レジスタではなくメモリオペランドを指定することも可能。 とりあえずこの文書では第一オペランドを xmm1、第二オペランドを xmm2 に呼ぶことにする。 xmm1 は %xmm1 ではないことに注意。

PCMPxSTRx 命令は 4 つのバリエーションがある。 最初に文字列の長さをどう扱うかと、結果をどのように受け取るかを選択する。

これによって PCMPESTRI、PCMPESTRM、PCMPISTRI、PCMPISTRM の命令のどれを使うかが決まる。

 Return Index
結果は文字の位置
%rcxで受け取る
Return Mask
結果はビットマップ
%xmm0に
Explicit Length Strings
文字長を指定
xmm1を%raxで
xmm2を%rdxで指定
PCMPESTRIPCMPESTRM
Implicit Length Strings
文字は NULL 終端
PCMPISTRIPCMPISTRM

PCMPxSTRx 命令はオペランドとして指定した xmm1xmm2 (メモリオペランドの場合はアドレッシングに指定したレジスタ)以外に暗黙のレジスタを使用する。 64 ビットモードでは PCMPESTRI と PCMPESTRM 命令は %rax%rdx を暗黙のうちに入力レジスタとする。 また PCMPESTRI と PCMPISTRI は %rcx を出力先として、PCMPESTRM と PCMPISTRM は %xmm0 を出力先として暗黙のうちに出力レジスタとする。 32ビットモードではそれぞれ %eax、%eax、%ecx となる。

以降の説明は全て 64 ビットモードで説明するが、32 ビットモードでも同じことができる。

PCMPESTRx は %rax と %rdx で文字長(要素数)を指定するが、これは要素をバイトとして扱う場合(Imm[0] が 0)はバイト単位、ワードとして扱う場合(Imm[0] が 1)の場合はワード単位で数える。 つまり XMM レジスタが 16 バイトなので、バイト扱いの場合は 0-15、 ワード扱いの場合は 0-7 を指定する。

また文字長(%rax、%rdx) に XMM レジスタを越える値(バイト単位の場合は 16 バイト以上、ワード単位の場合は 8 以上)を指定することもできる。 この場合は XMM レジスタ全体が比較対象となり、原則的には 15(バイト単位) または 7 (ワード単位) を指定したのと同じように振舞う(フラグの扱いが一部違う)。

さらに以下を選択する。

Byte or Word
バイト(1バイト)として比較するかワード(2バイト)として比較するか?
Signed or Unsigned
データを符号付き整数として比較するか符号なし整数として比較するか?
Aggregation operation
各要素をどのように比較するか?
Polarity
各要素の比較の中間結果をどのように処理するか?
Output selection
中間結果を受けてどのようにまとめるか?

要素の型(Byte or Word / Signed or Unsigned)

要素をどのような型と見なすかを指定する。

Imm[0] が 0 ならバイトとして、1 ならワードとして扱う。 Imm[1] が 0 なら符号なしとして、1 なら符号付きとして扱う。

Imm8[0:1]DescriptionExpression
00bUnsigned bytesuint8_t data[16]
01bUnsigned wordsuint16_t data[8]
10bSigned bytesint8_t data[16]
11bSigned wordsint16_t data[8]

比較操作(Aggregation Operation)

各要素の比較の方法を 4つの比較方式の中から選択する。 PCMPxSTRx 命令においてこの選択が最も重要である。

基本的に比較の対象となるのは xmm2 である。 xmm2 の各要素を xmm1 を使って指定の比較を行い、それを IntRes1[i] に格納する。 xmm2 が比較対象になっているのは、xmm2 がメモリオペランドをとれるためであろう。

IntRes1[] は PCMPxSTRx 命令の中間結果の結果を保持する一時的なレジスタのようなものである。 各要素位置の結果を 0 または 1 で記録するビットベクタを思い浮かべればよい。 IntRes1[] の値を外部から知ることはできない。

UpperBound = imm8[0] ? 7 : 15;

for (i=0 ; i<UpperBound ; i++) {
    IntRes1[i] = Comparator(Operand2[i], i);
}

要素のサイズは Imm[0] でバイトかワードが決まっている。

Imm[1] で決まる要素の符号付き・符号なしの違いは Ranges を選択した場合のみ有効である。 他は「一致」を比較しているので符号付き・符号なしの違いは関係ない。

以下の説明で Operand1[i] は xmm1 の i 番目の要素を、Operand2[j] は xmm2 の j 番目の要素を取り出すことを意味する。
Imm8[3:2] Name Expression 用途
00b Equal Any 比較対象の xmm2 の中の要素が、xmm1 の中の要素のいずれかと一致するかどうかを判定している。 一致するものがあれば IntRes1[i] は 1 に、いずれとも一致しなければ 0 になる。
bool Comparator(Element2, ) {
    for (j=0 ; j<UpperBound ; j++) {
        if (Element2 == Operand1[j]) {
            return true;
        } 
    }
    return false;
}
Tokenizatoin, XML parser
01b Ranges xmm1 の中の要素は偶数番要素と奇数番要素でペアを作って下限と上限を記録している。 比較対象の xmm2 の中の要素が、xmm1 のペアの範囲に入っているかどうかを判定する。 どれか一組の範囲内に入っていれば IntRes1[i] は 1 に、いずれの範囲にも入っていなければ 0 になる。
bool Comparator(Element2, ) {
    for (j=0 ; j<UpperBound ; j += 2) {
        if (Operand1[j] <= Element2 && Element2 <= Operand1[j+1]) {
            return true;
        } 
    }
    return false;
}
xmm1 内の範囲の組は、要素がバイト扱いの場合は 8 組、ワード扱いの場合は 4 組作れる。
Subsetting, Case handling, XML parser, Schema validation
10b Equal Each 比較対象の xmm2 の中の要素が、同じ位置にある xmm1 の要素と一致しているかどうかを判定する。 一致すれば IntRes1[i] は 1 に、一致しなければ 0 になる。
bool Comparator(Element2, i) {
    return (Element2 == Operand1[i]);
}
もっと簡単に言うと以下のような比較をしている。 これは strcmpmemcmp が行うような比較である。
UpperBound = imm8[0] ? 7 : 15;
IntRes1 = 0;
for (i=0 ; i<UpperBound ; i++) {
    IntRes1[i] = (Operand1[i] == Operand2[i]);
}
memcmp, strcmp
11b Equal Ordered 比較対象の xmm2 の i 以下の要素が、キーワード xmm1 と一致しているかどうかを比較する。 一致すれば IntRes1[i] は 1 に、一致しなければ 0 になる。
bool Comparator(, i) {
    for (k=i, j=0; k < UpperBound  && j < UpperBound - i; k++, j++) {
        if (Operand2[k] == Operand1[j]) {
            return false;   
        }
    }
    return true;
}

もう少し解説すると、以下のように xmm2xmm1 が入っていた場合、 Operand2[0] の位置から Operand1 の内容との一致をバイト比較する。

Operand2[16] = "0123ABC789ABCDEF" // 終端文字は無視して
Operand1[16] = "ABCDEFGHIJKLMNOP" // 終端文字は無視して

まず Operand2[0] 〜 Operand2[3] までは最初の 1 要素から一致しない。 IntRes1[0] 〜 IntRes1[3] は 0 になる。

Operand2[4] は 'A' なので Operand1[0] に一致する。 ここから 3 要素一致するが Operand2[7] が 'D' にならず比較は失敗する。 結局、IntRes1[4] は 0 になる。

Operand2[10] で再び 'A' が出現し Operand1[0] に一致する。 ここから 6 要素が一致する、ここで Operand2 は要素が尽きてしまう。 しかし部分一致には成功しているので IntRes1[10] は 1 になる。

結局、IntRes1[10] が 1 で、他の IntRes1[i] は 0 となる。

Substring Searches, KMP, strstr

文字列の終わり以降の扱い

PCMPxSTRx は文字列長を指定(Explicit Length)か NULL 終端(Implicit Length)のどちらかで文字列の有効範囲を定めている。 逆に文字列長よりも後の部分は「無効(Invalid)」な要素であり、この部分の比較には特別なルールが適用される。

PCMPISTRx 命令は NULL 終端として扱う。そのため 0 要素を「無効」とし、0 要素以降の要素も「無効」となる。

PCMPISTRx 命令で Ranges(Imm8[3:2]=01b)の xmm1 は偶数要素と奇数要素で上限と下限を決めるペアを作っているが、どちらかが 0 要素の場合はペア全体が「無効」となる。 また xmm1 で続く ペアも「無効」となる。 そのため PCMPISTRx 命令の Ranges では 0 を含むような比較は上限・下限は作れず、比較対象にも 0 は置けない。 一方、PCMPESTRx は文字長を %rax と %rdx で指定するため、0 を含むような上限・下限を作ることも、比較対象に 0 を含めることも可能である。

 xmm1 の要素xmm2 の要素Equal Any
(00b)
Ranges
(01b)
Equal Each
(10b)
Equal Ordered
(11b)
(1)ValidValidCompareCompareComapreCompare
(2)ValidInvalidForce False(0)Force False(0)Force False(0)Force False(0)
(3)InvalidValidForce False(0)Force False(0)Force False(0)Force True(1)
(4)InvalidInvalidForce False(0)Force False(0)Force True(1)Force True(1)

上記の表は一見複雑だが合理的にできている。

なお後述の Polarity を Masked(-) (Imm8[5:4] = 11b) にした場合は、xmm2 の無効な要素の IntRes1[] がビット反転するので、判定が以下のように変わる(実際この上にさらに全体がビット反転する)。

xmm1 の要素xmm2 の要素Equal Any
(00b)
Ranges
(01b)
Equal Each
(10b)
Equal Ordered
(11b)
ValidValidCompareCompareComapreCompare
ValidInvalidForce True(1)Force True(1)Force True(1)Force True(1)
InvalidValidForce False(0)Force False(0)Force False(0)Force True(1)
InvalidInvalidForce True(1)Force True(1)Force False(0)Force False(0)

ビット反転(Polarity)

中間結果 IntRes1[] をそのまま or 反転することができる。 結果は次の中間結果 IntRes2[] に格納される。

00b と 10b は結果的に同じ操作で、IntRes1[] の内容をそのまま IntRes2[] に格納する。

01b は IntRes1[] の内容をビット反転して IntRes2[] に格納する。

11b は 基本的に IntRes2[i] = ~IntRes1[i] だが、xmm2 の i 番目の要素が無効なら IntRes2[i] = IntRes1[i] とする。 xmm2 の i 番目の要素が「無効」とは、「xmm2 の文字列の終端以降の要素」という意味である。

Imm8[5:4]OperationNameDescription
00bPositive Polarity(+)No changeIntRes2[i] = IntRes1[i]
01bNegative Polarity(-)InvertIntRes2[i] = ~IntRes1[i]
10bMasked(+)No changeIntRes2[i] = IntRes1[i]
11bMasked(-)Mask Negative基本的に IntRes2[i] = ~IntRes1[i] だが、xmm2 の i 番目の要素が無効なら IntRes2[i] = IntRes1[i] とする。

極性は %rcx にインデックスを受け取る PCMPESTRI と PCMPISTRI において、結果として「最初に一致した要素のインデックス」が欲しいのか、「最初に不一致だった要素のインデックス」のどちらを得るのかに重要になる。 IntRes1[] の結果は一致した部分に 1 が、不一致だった部分に 0 となっている。 次にある Output Selection では IntRes2[] のうち最上位ビットからあるいは最下位ビットから 1 が立っている位置を探すからである。

Output Selection

出力方法を決める。 IntRes2[] を解釈して %rcx か %xmm0 に値を設定する。

Return Index

PCMPESTRI と PCMPISTRI の場合は %rcx を出力先とすることは決まっているが、その内容は Imm8[6] による。

Imm8[6]OperationDescription
0bLeast significant indexIntRes2[] の 0 要素目から見て最初に 1 が立っている要素の位置を %rcx にいれる。
1bMost significant indexIntRes2[] の最後の要素から見て最初に 1 が立っている要素の位置を %rcx にいれる。

IntRes2[] に 1 が立っている箇所がない場合には %rcx は 16 を返す。

Return Mask

PCMPESTRM と PCMPISTRM の場合は %xmm0 を出力先とするが、その内容を Imm8[6] による。

Imm8[6]OperationDescription
0bBit maskIntRes2[] の内容が %xmm0 の下位ビットにビット単位で格納される。あまった上位ビットはゼロ拡張される。
1bByte/word maskIntRes2[] の内容が %xmm0 の下位からバイトまたはワード単位で格納される。
バイトなのかワードなのかは imm8[1] によって決まる。
要素がバイト扱いの場合は、
for (i=0 ; i<16  ; i++) {
    %xmm0 |= ((IntRes2[i] ? 0xFF : 0x00) << (8 * i));
}
要素がワード扱いの場合は、
for (i=0 ; i<8  ; i++) {
    %xmm0 |= ((IntRes2[i] ? 0xFFFF : 0x0000) << (16 * i));
}

フラグ変化

演算結果は以下のようになる。

EFLAGDescription
CFIntRes2[] が全て 0 の場合は 0 となり、それ以外は 1 になる。
ZFxmm2 の要素が全部有効だった場合は 0、それ以外は 1
PCMPESTRx では %rdx が 16(8) 未満なら 0 になる。
PCMPISTRx では xmm2 の中に 0 の要素があった場合は 0 になる。
SFxmm1 の要素が全部有効だった場合は 0、それ以外は 1
PCMPESTRx では %rax が 16(8) 未満なら 0 になる。
PCMPISTRx では xmm1 の中に 0 の要素があった場合は 0 になる。
OFIntRes2[0] の値がコピーされる。

AF と PF は常にリセットされる。

余談

AVX2 は 256 ビットの YMM レジスタを使った演算が可能だが、そのオペコードマップには VPCMPESTRM、VPCMESTRI、VPCMPISTRM、VPCMPISTRI が定義されている。 将来的に 256 ビット(32 バイト)幅の PCMPxSTRx 命令が使えるようになるかも。

コメント

トラックバック   [Trackback URL: http://www.nminoru.jp/cgi-bin/tb.cgi/programming__pcmpxstrx]
コメントを書き込む

TOP    掲示板    戻る
Written by NAKAMURA Minoru, Email: nminoru atmark nminoru dot jp, Twitter:@nminoru_jp