最適化されたstrcmpの実装

Question

この関数はhereであった。それはstrcmpの実装です：

int strcmp(const char* s1, const char* s2) 
{ 
    while (*s1 && (*s1 == *s2)) 
     s1++, s2++; 
    return *(const unsigned char*)s1 - *(const unsigned char*)s2; 
} 

私は短いの最後の行で何が起こっているのか、全てが、最後の行を理解できますか？

Answer 1

return *(const unsigned char*)s1-*(const unsigned char*)s2; 

OP：最後に何が起こっていますか？

A：最初の潜在的な文字列の違いが比較されます。両方のcharsは、仕様に応じてunsigned charと参照されます。 2はintに昇格され、その差が返されます。

---

注

1戻り値の符号（< 0、0、> 0）が最も有意義な部分です。これは、C仕様で指定されている唯一の部分です。

2一部のシステムでは、charはsigned（より一般的です）です。他のものでは、charはunsignedです。最後の比較の「看板」を定義することは、移植性を促進する。 fgetc()は、unsigned charという文字を取得することに注意してください。

3文字列の末尾に\0（ASCIIのような一般的な文字コード）が使用されており、バイナリレベルで違いはありません。 2つの文字列が異なる最初のcharの値が65と97の場合、文字エンコーディングがASCIIでなくても、最初の文字列は2番目の文字列よりも小さくなります。OTOH、strcmp("A", "a")は、文字エンコーディングはASCIIの場合に負の数を返しますが、その根底にある価値と秩序のために、異なる文字エンコーディングで正の数を返すことがC.

Answer 2

strcmpは、いずれの文字列もより大きい場合は、より大きいかどうかを返します。

最後の行は、一致しない最初の文字を減算し、どちらが大きいかを調べます。文字列全体が一致する場合は、0-0=0になり、「等しい」結果が得られます。

それがキャッシュラインのアセンブリコードと知識を取るように、この実装は本当によく、最適化されていない、負荷の大きさなど

Answer 3

この実装は間違いなく、内蔵strcmpの最適化ではない、それは単に別です私はそれが組み込みのバージョンよりもおそらく悪いと考えています。

比較関数は、比較する値が等しい場合は0、最初の値が小さい場合は負の数、最初の値が大きい場合は正の数を返します。そして、それは最後の行で起こることです。

最後の行の考え方は、文字を符号なしの文字にキャストすることです。私は、これを標準以外の文字を標準の文字（ASCIIコード0-127）の後に並べ替えることを意味していると思います。

編集：コードにはバグが存在しないと値がs1値がコード128以上で文字の前に標準文字を注文s2で指さよりも小さいことで指された場合には、負の値を返しますすることができます。

Answer 4

によって定義されていない私はprefferこのコードだ：

ARMv4のため

int strcmp(const char *str1, const char *str2) 
{ 
    int s1; 
    int s2; 
    do { 
     s1 = *str1++; 
     s2 = *str2++; 
     if (s1 == 0) 
      break; 
    } while (s1 == s2); 
    return (s1 < s2) ? -1 : (s1 > s2); 
} 

それはとしてコンパイル：あなたはループの下でのみ6指示+最後に[最大5つの命令があります見ることができるように

strcmp: 
    ldrsb r3, [r0], #1 ;r3 = *r0++ 
    ldrsb r2, [r1], #1 ;r2 = *r1++ 
    cmp  r3, #0  ;compare r3 and 0 
    beq  @1   ;if r3 == 0 goto @1 
    cmp  r3, r2  ;compare r3 and r2 
    beq  strcmp  ;if r3 == r2 goto strcmp 
;loop is ended 
@1: 
    cmp  r3, r2  ;compare r3 and r2 
    blt  @2   ;if r3 < r2 goto @2 
    movgt r0, #1  ;if r3 > r2 r0 = 1 
    movle r0, #0  ;if r3 <= r2 r0 = 0 
    bx  lr   ;return r0 
@2: 
    mov  r0, #-1 ;r0 = -1 
    bx  lr   ;return r0 

。したがって、複雑さは6 *（strlen + 1）+ 5です。

while条件に移動すると（s1 == 0）、ARMのマシンコードが悪くなります（なぜわかりません）。

Answer 5

この実装は、さらに、いくつかの比較を削り取る、最適化することができる。

int strcmp(const char *s1, const char *s2) { 
    unsigned char c1, c2; 
    while ((c1 = *s1++) == (c2 = *s2++)) { 
     if (c1 == '\0') 
      return 0; 
    } 
    return c1 - c2; 
} 

文字列が終端のNULLバイトを含むと、最大同一である場合、戻り値は0です。戻り値の符号は、C標準に従ってunsigned charに変換された最初の異なる文字の差の符号です。

• はcharはすべてが、いくつかのまれな組み込みシステムに真であるint、より小さい場合、この違いは単純な引き算で計算することができ、両方c1とc2はintに昇格されているし、この差が収まるように保証されていますタイプintの範囲です。 sizeof(int) == 1システムで

• 、戻り値は、このように計算される必要があります。

  return (c1 < c2) ? -1 : 1;