次の IETF ドラフトで説明されているように、Python で CARP ハッシュを実装しようとしています。
https://datatracker.ietf.org/doc/html/draft-vinod-carp-v1-03#section-3.1
具体的には:
3.1. ハッシュ関数
ハッシュ関数は、ゼロで終わる ASCII 入力文字列に基づいて 32 ビットの符号なし整数を出力します。URL のマシン名とドメイン名、プロトコル、および各メンバー プロキシのマシン名は、URL のその部分で大文字と小文字が区別されないため、小文字で評価する必要があります。
このアプリケーションでは不可逆性と強力な暗号化機能は不要であるため、ビットごとの左回転演算子に基づく非常に単純で高速なハッシュ関数が使用されます。
(URL の各文字): URL_Hash += _rotl(URL_Hash, 19) + char ;
メンバー プロキシ ハッシュは、同様の方法で計算されます。
(MemberProxyName の各文字) の場合: MemberProxy_Hash += _rotl(MemberProxy_Hash, 19) + char ;
メンバー名は互いに似ていることが多いため、それらのハッシュ値は、次の追加操作によってハッシュ空間全体にさらに分散されます。
MemberProxy_Hash += MemberProxy_Hash * 0x62531965 ; MemberProxy_Hash = _rotl (MemberProxy_Hash, 21) ;
3.2. ハッシュの組み合わせ
ハッシュは、最初に URL ハッシュをマシン名で排他的論理和 (XOR) し、次に定数を掛けてビットごとのローテーションを実行することによって結合されます。
最終値と中間値はすべて 32 ビットの符号なし整数です。
Combined_Hash = (URL_hash ^ MemberProxy_Hash) ; 結合ハッシュ += 結合ハッシュ * 0x62531965 ; Combined_Hash = _rotl(Combined_Hash, 21) ;
numpy を使用して 32 ビットの符号なし整数を作成しようとしました。最初の問題は、左ビット シフトが実装されている場合に発生します。Numpy は結果を 64 ビット符号なし整数として自動的に再キャストします。32 ビットをオーバーフローする演算についても同じです。
例えば:
from numpy import uint32
def key_hash(data):
# hash should be a 32-bit unsigned integer
hashed = uint32()
for char in data:
hashed += hashed << 19 + ord(char)
return hashed
x = key_hash("testkey")
print type(x)
戻り値:
「numpy.int64」と入力します
これをすべて 32 ビット空間に制限する方法のヒントはありますか? また、ハッシュを計算しているため、「MemberProxy_Hash += MemberProxy_Hash * 0x62531965」のようなこれらの操作のいくつかを実行する方法が 32 ビットに収まるかどうかについて、仕様に少し混乱しています。
編集:
フィードバックに基づくと、適切な解決策は次のようになります。
def key_hash(data):
# hash should be a 32-bit unsigned integer
hashed = 0
for char in data:
hashed += ((hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF
return hashed
def server_hash(data):
# hash should be a 32-bit unsigned integer
hashed = 0
for char in data:
hashed += ((hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF
hashed += (hashed * 0x62531965) & 0xFFFFFFFF
hashed = ((hashed << 21) + (hashed >> 11)) & 0xFFFFFFFF
return hashed
def hash_combination(key_hash, server_hash):
# hash should be a 32-bit unsigned integer
combined_hash = (key_hash ^ server_hash) & 0xFFFFFFFF
combined_hash += (combined_hash * 0x62531965) & 0xFFFFFFFF
return combined_hash
編集#2:
別の固定バージョン。
def rotate_left(x, n, maxbit=32):
# assumes 32 bit
x = x & (2 ** maxbit - 1)
return ((x << n) | (x >> (maxbit - n)))
def key_hash(data):
# hash should be a 32-bit unsigned integer
hashed = 0
for char in data:
hashed = (hashed + rotate_left(hashed, 19) + ord(char))
return hashed
def server_hash(data):
# hash should be a 32-bit unsigned integer
hashed = 0
for char in data:
hashed = (hashed + rotate_left(hashed, 19) + ord(char))
hashed = hashed + hashed * 0x62531965
hashed = rotate_left(hashed, 21)
return hashed
def hash_combination(key_hash, server_hash):
# hash should be a 32-bit unsigned integer
combined_hash = key_hash ^ server_hash
combined_hash = combined_hash + combined_hash * 0x62531965
return combined_hash & 0xFFFFFFFF