PCMPxSTRx 命令の使い方

作成日：2012.11.17

更新履歴
(2012.11.17) 作成。 (2017.12.24) Equal Ordered の疑似プログラムが誤っていたのを修正。

目次

• 命令の解説
  • 要素の型(Byte or Word / Signed or Unsigned)
  • 比較操作(Aggregation Operation)
    • 文字列の終わり以降の扱い
  • ビット反転(Polarity)
  • Output Selection
  • フラグ変化
• 余談
• コメント

命令の解説

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 つのバリエーションがある。 最初に文字列の長さをどう扱うかと、結果をどのように受け取るかを選択する。

• 文字長が分からない 0 終端文字列として比較するか、文字長はあらかじめ分かっているとして比較するか。
• 結果として違っている文字の位置が分かればいいか、違っている文字がある場所のビットマップが欲しいか。

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

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

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 なら符号付きとして扱う。

比較操作(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 を選択した場合のみ有効である。 他は「一致」を比較しているので符号付き・符号なしの違いは関係ない。

bool Comparator(Element2, ) {
    for (j=0 ; j<UpperBound ; j++) {
        if (Element2 == Operand1[j]) {
            return true;
        } 
    }
    return false;
}

bool Comparator(Element2, ) {
    for (j=0 ; j<UpperBound ; j += 2) {
        if (Operand1[j] <= Element2 && Element2 <= Operand1[j+1]) {
            return true;
        } 
    }
    return false;
}

bool Comparator(Element2, i) {
    return (Element2 == Operand1[i]);
}

UpperBound = imm8[0] ? 7 : 15;
IntRes1 = 0;
for (i=0 ; i<UpperBound ; i++) {
    IntRes1[i] = (Operand1[i] == Operand2[i]);
}

bool Comparator(, i) {
    for (k=i, j=0; k < UpperBound  && j < UpperBound - i; k++, j++) {
        if (Operand2[k] != Operand1[j]) {
            return false;   
        }
    }
    return true;
}

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

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

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 を含めることも可能である。

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

• Equal Anay の場合、比較対象となる xmm2 内の文字が xmm1 の文字のいずれかと一致しているかどうかを判断している。xmm2 が Invalid ならそれは一致しないと判断すべきなので False である。また xmm1 内の文字が Invalid であれば当然 False である。両方が invalid の場合も False であるのは妥当であろう。
• Ranges も Equal Any と同様である。
• Equal Each の場合、strcmp 型の比較を行う。xmm1 と xmm2 は同等の存在で、どちらかの文字列が先に終われば一致しないと考えるべきである。そのため (2) と (3) が False となっている。
  一方、両方の終端位置が同じであれば一致と考えたい。"ABC\0hoge" と "ABC\0moge" を一致と判断するため (4) が True である必要がある。
• Equal Ordered の場合、部分一致の比較する対象の xmm2 とキーワード xmm1 は同質ではない。
  キーワードの xmm1 が短ければ一致と判断したいので (3) と (4) は True となっている。
  一方、比較対象の xmm2 がキーワードの xmm1 よりも短ければそれは不一致と判断したいので (2) は False となっている。

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

ビット反転(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 の文字列の終端以降の要素」という意味である。

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

Output Selection

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

Return Index

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

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

Return Mask

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

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));
}

フラグ変化

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

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

余談

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

コメント