1

次の 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
4

2 に答える 2

2

派手な uint32 を気にしないでください。標準の Python を使用してintください。result &= 0xFFFFFFFF不要な上位ビットを削除することにより、必要に応じて演算の結果を制限します。

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        # hashed += ((hashed << 19) + ord(char)) & 0xFFFFFFFF
        # the above is wrong; it's not masking the final addition.
        hashed = (hashed + (hashed << 19) + ord(char)) & 0xFFFFFFFF
    return hashed

最終的なマスキングを 1 つだけ行うこともできますが、中間のマスキングがhashedかなり大きな数になるため、長い入力ではかなり遅くなります。

ところで、上記はあまり良いハッシュ関数ではありません。rotinは、シフトではなく、回転rotl意味します。

あなたが必要

# hashed += ((hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF
# the above is wrong; it's not masking the final addition.
hashed = (hashed + (hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF

編集... 比較; このコード:

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 khash(data):
    h = 0
    for c in data:
        assert 0 <= h <= 0xFFFFFFFF
        h = (h + (h << 19) + (h >> 13) + ord(c)) & 0xFFFFFFFF
    assert 0 <= h <= 0xFFFFFFFF
    return h

guff = "twas brillig and the slithy toves did whatever"
print "yours: %08X" % key_hash(guff)
print "mine : %08X" % khash(guff)

生成:

yours: A20352DB4214FD
mine : DB4214FD
于 2012-05-19T00:38:40.360 に答える
1

以下は私にとってはうまくいきますが、少し不自然かもしれません:

from numpy import uint32

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = uint32()
    for char in data:
        hashed += hashed << uint32(19) + uint32(ord(char))
    return hashed

x = key_hash("testkey")
print type(x)

問題は、数値が少ないビット数ではなく多いビット数に強制されることです。

于 2012-05-19T00:38:06.337 に答える