CARP хеш в Python
Я пытаюсь реализовать хэш CARP в Python, как описано в следующем проекте IETF:
http://tools.ietf.org/html/draft-vinod-carp-v1-03
В частности:
3.1. Хэш-функция
Хеш-функция выводит 32-разрядные целые числа без знака на основе строки ввода ASCII с нулевым символом в конце. Имя компьютера и доменные имена URL, протокол и имена компьютеров каждого прокси-члена-члена должны оцениваться в нижнем регистре, поскольку эта часть URL не учитывает регистр.
Поскольку необратимость и сильные криптографические функции не нужны для этого приложения, используется очень простая и быстрая хэш-функция, основанная на побитовом операторе левого поворота.
Для (каждый символ в URL): URL_Hash += _rotl(URL_Hash, 19) + char;
Хэши прокси-членов вычисляются аналогичным образом:
Для (каждый символ в MemberProxyName): MemberProxy_Hash += _rotl(MemberProxy_Hash, 19) + char;
Имена членов Becaues часто похожи друг на друга, их хеш-значения дополнительно распределяются по хеш-пространству с помощью следующих дополнительных операций:
MemberProxy_Hash + = MemberProxy_Hash * 0x62531965; MemberProxy_Hash = _rotl (MemberProxy_Hash, 21);
3.2. Хэш-комбинация
Хэши объединяются путем сначала эксклюзивного или (XOR) хэша URL-адреса по имени машины, а затем умножения на константу и выполнения побитового вращения.
Все конечные и промежуточные значения представляют собой 32-разрядные целые числа без знака.
Combined_Hash = (URL_hash ^ MemberProxy_Hash); Combined_Hash + = Combined_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
2 ответа
Не беспокойся с NumPy 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
Вы могли бы сделать только одну заключительную маскировку, но это было бы довольно медленно при длинном вводе в качестве промежуточного hashed было бы довольно большое количество.
Кстати, вышеописанное не будет очень хорошей хэш-функцией. rot в 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
Следующее работает для меня, хотя, возможно, немного не в духе:
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)
Проблема в том, что числа приводятся к большему количеству бит, а не к меньшему.