変数がそれ自体の値と等しくない可能性がある方法

最近、私の友人がエラーを示しました。これは、intオーバーフローのある文字列から多項式ハッシュを計算する単純な関数に現れます。 彼女は負の数を返しましたが、そうすべきではありません。 関数自体は次のとおりです。

unsigned MAX_INT = 2147483647; int hash_code(std::string x) { int h = 13; for (unsigned i = 0; i < 3; i++) { h += h * 27752 + x[i]; } if (h < 0) h += MAX_INT; return h; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一部の行、特に「さようなら」行、およびサーバーのみ（興味深いことに、すべてがコンピューター上で正常に処理されていた）では、関数は負の数を返しました。 しかし、それはどうですか。数値が負の場合、MAX_INTが追加され、正になるはずです。



ここでは、サーバーとローカルコンピューターの違いに注目する価値があります。最初に、OS Xはローカルコンピューター上にあり、clangコンパイラーが使用され、Gentooはgccコンパイラーを持つサーバー上にあり、次に、-O2フラグでコンパイルされたサーバーです。 さて、コマンドでコンパイルしましょう

 g++ -O2 -S -masm=intel a.cpp
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

サーバー側でこの関数のアセンブラーコードを参照してください。

 _Z9hash_codeNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE: .LFB661: .cfi_startproc mov rdx, QWORD PTR [rdi] mov eax, 13 lea rsi, [rdx+3] .L2: # begin of the cycle movsx ecx, BYTE PTR [rdx] add rdx, 1 imul eax, eax, 27753 add eax, ecx cmp rsi, rdx jne .L2 # end of the cycle rep ret # returning the value right away
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、ループ後のアセンブラコードには比較がありません。 コンパイラーは、負でない値を格納し、増加するだけの変数はゼロより小さくすることはできないと判断しました。これは、intが実装する整数演算の観点から正しいです。 つまり、ゼロとの比較は不要であり、デッドコードの除去（デッドコードの除去）を実行できます。 intオーバーフローが未定義の動作を引き起こすと警告されました。



しかし、変数がそれ自体の値と等しいかどうかを推測したらどうでしょうか？

 printf("%i\n", h == -348700627);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

出力では0になり、アセンブラコードでは次のようになります。

  xor edx, edx mov esi, OFFSET FLAT:.LC0 mov edi, 1 xor eax, eax call __printf_chk
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

edxレジスタでは、出力への引数が渡されます。 ゼロに等しく、チェックは実行されません。 一般に、数値がゼロより小さくない場合は論理的です。負の数値と比較してください。 したがって、オーバーフロー中に整数を比較する関数が機能せず、変数が固有値と等しくない可能性があります！ しかし、そのためには未定義の動作です。



変数を正の数と比較してみましょう。 もちろん、結果は偽になりますが、コンパイラが実際のチェックを行うのだろうか？ バイナリ検索を使用して、コンパイラが数値360662以上で比較が行われた場合にのみ、実際のチェックを行うことがわかりました。 この数は27752 * 13.に非常に近いです。偶然かどうか。 知りません



OS Xで-O2最適化を使用している場合、このようなエラーは検出されなかったことにも言及する価値があります。 確かに、gccではなくclangが使用されました。 アセンブラーコードでは、正直ですが、魔法のチェックが実行されます。

 ## BB#1: shr eax, 8 movsx eax, al movsx ecx, byte ptr [rdi + 2] inc rdi jmp LBB0_3 LBB0_2: mov rdi, qword ptr [rdi + 16] movsx eax, byte ptr [rdi] movsx ecx, byte ptr [rdi + 1] LBB0_3: imul eax, eax, 27753 lea eax, [rax + rcx + 1423042525] movsx ecx, byte ptr [rdi + 2] imul edx, eax, 27753 add edx, ecx mov eax, edx sar eax, 31 # some magic check and eax, dword ptr [rip + _MAX_INT] # yet another magic add eax, edx pop rbp ret
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、単純なintオーバーフローであっても、コードが動作不能になり、多くの問題が発生する可能性があります。



PSそれでも、多項式ハッシュは大きな素数に基づいて書かれるべきです。 そして、比較は機能し、機能を損なう行を見つけるのははるかに困難です。