PJWハッシュ関数

PJW ハッシュ関数は、 AT&T ベル研究所の Peter J. Weinbergerによって作成された非暗号ハッシュ関数です。

PJW ハッシュのバリアントは、ELF形式の Unix オブジェクト ファイルで使用される ElfHash または Elf64 ハッシュを作成するために使用されていました。

アレン・ホルブはPJWハッシュアルゴリズムのポータブル版を作成したが、このアルゴリズムにはバグがあり、最終的に複数の教科書に掲載された。このことは、教科書の1冊の著者が後に認めた。^[1]

PJWハッシュアルゴリズムは、前のハッシュをシフトし、現在のバイトを追加し、その後上位ビットを移動します。^[2]

アルゴリズムPJW_hash(s)は
    uint h := 0
    bits := uint ビット単位のサイズ
    i := 1 から |S|まで
        h := h << ビット/8 + s[i]
        high := h の左から上位ビット/8ビットを取得
        高さ≠0の場合
            h := h xor (上位 >> ビット * 3/4)
            h := h & ~高さ
    戻るh

以下はUnix ELF形式で使用されるアルゴリズムの実装です: ^[3]

unsigned long ElfHash ( const unsigned char * s ) { unsigned long h = 0 , high ; while ( * s ) { h = ( h << 4 ) + * s ++ ; if ( high = h & 0xF0000000 ) h ^= high >> 24 ; h &= ~ high ; } return h ; }     

           
     
    
              
             
                
          
    
     

このCコードは、がlong32ビットのデータ型であると誤って想定しています。多くの64ビットlongシステムのように、が32ビットよりも広い場合、コードにはバグが含まれます。^[4]

非暗号ハッシュ関数