FNV-0 in Python
Piccolo code snippet per estimatori del pitone.
def fnv_hash(data):
"""
Returns a 32bit FNV-0 hash of the given string.
>>> fnv_hash('3dcb910fb26bafb97e4a9660493afd9704536743')
-1588890617L
>>> fnv_hash('deb114355f8b912c4f7c7f0aceac7adceaa5db10')
317390073L
"""
h = long(0)
for i in xrange(len(data)):
h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24)
h ^= ord(data[i])
# Everything after the 32th bit is meaningless
h &= 0xffffffffL
# Perform sign extension
if h & 0x80000000L:
h = -(~(h - 1) & 0xffffffffL)
return h
I compagni di merende che masticano C avranno sicuramente storto il naso vedendo sia l'AND che l'estensione di segno fatta in quel modo becero, quindi precisiamo:
- Python promuove automaticamente gli interi alla storage class superiore (ANCHE oltre i 64 bit) per evitare l'overflow, quindi solo i 32 bit inferiori contengono valori sensati;
- per quanto appena esposto, l'estensione di segno non può essere effettuata con un banale OR (che promuoverebbe l'intero per conservare il segno!) ma è necessario fare ricorso alla definizione scolastica di complemento a 2.
Commenti
blog comments powered by Disqus