BitVisorのmemcmp/strcmp/strncmp実装

BitVisorのmemcmp/strcmp/strncmp実装を軽く紹介します。

string.h

このようにmemcmp_builtin, strcmp_builtin, strncmp_builtinを使うマクロが宣言されています。しかし、これを使っていてもmemcmp/strcmp/strncmp関数が呼び出されることがあります。

string.s

ここにmemcmp/strcmp/strncmp関数の実装があります。前半が32ビット、後半が64ビットの実装です。簡単な64ビットのほうを見てみます。

memcmp

    mov %rdx,%rcx
    xor %eax,%eax
    cld
    repe    cmpsb
    je  1f
    sbb %eax,%eax
    xor $-2,%eax
1:
    ret

これだけです。x86には便利な命令があって、memcmpそのものの機能があり、ループを書く必要がないのでそれを使います。ただし、返り値は計算してくれませんので、なんとかします。

通常は引き算結果をそのまま返すのが簡単なやり方ですが、比較命令を使用した場合は引き算結果の値は捨てられます。残るのは引き算の際に設定されるフラグレジスターの内容だけです。そのためフラグレジスターを元に返り値を生成しています。

最初に"xor %eax,%eax"で、一致した時の返り値を準備しています。比較後のjeで、一致した時はret命令にジャンプしています。"sbb %eax,%eax"はキャリーフラグを含めた引き算命令で、同じレジスター同士を引くので、結果はキャリーフラグが0の場合は0、1の場合は-1になります。そして次の"xor $-2,%eax"で、0を-2に、-1を1に変化させて返り値とします。

キャリーフラグ	sbbの結果(A)	(A)の16進数	-2の16進数	xor $-2,%eaxの結果(B)の16進数	(B)の結果
0	0	00000000	FFFFFFFE	FFFFFFFE	-2
1	-1	FFFFFFFF	FFFFFFFE	00000001	1

strcmp

strcmp64:
    xor %eax,%eax
    cld
1:
    lodsb
    scasb
    jne 1f
    test    %al,%al
    jne 1b
    ret
1:
    sbb %eax,%eax
    xor $-2,%eax
    ret

strcmpは終端文字'\0'を見つけたらその時点でループを終了する処理が必要で、memcmpとは異なりループを実装する必要がありますが、結果の処理はmemcmpと同様です。返り値に使われる%eaxレジスターの下位8ビットを壊しながらループしますが、結果が等しい場合はどちらも終端文字'\0'で終わっているので、その値0x00がそのまま返り値の下位8ビットになります。

strncmp

strncmp64:
    xor %eax,%eax
    cld
1:
    test    %edx,%edx
    je  2f
    dec %edx
    lodsb
    scasb
    jne 1f
    test    %al,%al
    jne 1b
    ret
1:
    sbb %eax,%eax
    xor $-2,%eax
    ret
2:
    xor %eax,%eax
    ret

strncmp関数は今年lwIPのアップデートのために追加されたものです。
https://bitbucket.org/bitvisor/bitvisor/commits/3f2b225ec9be828a453f3e45a9c2a4a865ea326d

strcmpと同様の処理に、残りバイト数をチェックしてデクリメントする処理が追加されています。また、残りバイト数が0になったためにループを抜ける際は、返り値を0にしてからリターンするようになっています。

以前の実装

返り値の計算部分は以前は違う方法を用いていました。

-   setnc   %al
-   setc    %ah
-   ror %eax
+   sbb %eax,%eax
+   xor $-2,%eax

このように、setnc, setc, rorの3つの命令を使用していました。

キャリーフラグ	setncの結果	setcの結果	setnc, setc後の%eax(16進数)	rorの結果(16進数)	rorの結果
0	1	0	00000001	80000000	-2147483648
1	0	1	00000100	00000080	128

これもちゃんと動いてはいましたが、見るからにわかりにくいので書き直したというわけです。