hash.py

   1 ## Copyright 2002 Andrew Loewenstern, All Rights Reserved
   2
   3 from sha import sha
   4 from whrandom import randrange
   5
   6 ## takes a 20 bit hash, big-endian, and returns it expressed a python integer
   7 ## ha ha ha ha    if this were a C module I wouldn't resort to such sillyness
   8 def intify(hstr):
   9     assert(len(hstr) == 20)
  10     i = 0L
  11     i = i + ord(hstr[19])
  12     i = i + ord(hstr[18]) * 256L
  13     i = i + ord(hstr[17]) * 65536L
  14     i = i + ord(hstr[16]) * 16777216L
  15     i = i + ord(hstr[15]) * 4294967296L
  16     i = i + ord(hstr[14]) * 1099511627776L
  17     i = i + ord(hstr[13]) * 281474976710656L
  18     i = i + ord(hstr[12]) * 72057594037927936L
  19     i = i + ord(hstr[11]) * 18446744073709551616L
  20     i = i + ord(hstr[10]) * 4722366482869645213696L
  21     i = i + ord(hstr[9]) * 1208925819614629174706176L
  22     i = i + ord(hstr[8]) * 309485009821345068724781056L
  23     i = i + ord(hstr[7]) * 79228162514264337593543950336L
  24     i = i + ord(hstr[6]) * 20282409603651670423947251286016L
  25     i = i + ord(hstr[5]) * 5192296858534827628530496329220096L
  26     i = i + ord(hstr[4]) * 1329227995784915872903807060280344576L
  27     i = i + ord(hstr[3]) * 340282366920938463463374607431768211456L
  28     i = i + ord(hstr[2]) * 87112285931760246646623899502532662132736L
  29     i = i + ord(hstr[1]) * 22300745198530623141535718272648361505980416L
  30     i = i + ord(hstr[0]) * 5708990770823839524233143877797980545530986496L
  31     return i
  32
  33 ## returns the distance between two 160-bit hashes expressed as 20-character strings
  34 def distance(a, b):
  35     return intify(a) ^ intify(b)
  36
  37
  38 ## returns a new pseudorandom globally unique ID string
  39 def newID():
  40     h = sha()
  41     for i in range(20):
  42         h.update(chr(randrange(0,256)))
  43     return h.digest()
  44
  45 def randRange(min, max):
  46     return min + intify(newID()) % (max - min)
  47
  48 import unittest
  49
  50 class NewID(unittest.TestCase):
  51     def testLength(self):
  52         self.assertEqual(len(newID()), 20)
  53     def testHundreds(self):
  54         for x in xrange(100):
  55             self.testLength
  56
  57 class Intify(unittest.TestCase):
  58     known = [('\0' * 20, 0),
  59              ('\xff' * 20, 2L**160 - 1),
  60             ]
  61     def testKnown(self):
  62         for str, value in self.known:
  63             self.assertEqual(intify(str),  value)
  64     def testEndianessOnce(self):
  65         h = newID()
  66         while h[-1] == '\xff':
  67             h = newID()
  68         k = h[:-1] + chr(ord(h[-1]) + 1)
  69         self.assertEqual(intify(k) - intify(h), 1)
  70     def testEndianessLots(self):
  71         for x in xrange(100):
  72             self.testEndianessOnce()
  73
  74 class Disantance(unittest.TestCase):
  75     known = [
  76             (("\0" * 20, "\xff" * 20), 2**160L -1),
  77             ((sha("foo").digest(), sha("foo").digest()), 0),
  78             ((sha("bar").digest(), sha("bar").digest()), 0)
  79             ]
  80     def testKnown(self):
  81         for pair, dist in self.known:
  82             self.assertEqual(distance(pair[0], pair[1]), dist)
  83     def testCommutitive(self):
  84         for i in xrange(100):
  85             x, y, z = newID(), newID(), newID()
  86             self.assertEqual(distance(x,y) ^ distance(y, z), distance(x, z))
  87
  88 class RandRange(unittest.TestCase):
  89     def testOnce(self):
  90         a = intify(newID())
  91         b = intify(newID())
  92         if a < b:
  93             c = randRange(a, b)
  94             self.assertEqual(a <= c < b, 1, "output out of range %d  %d  %d" % (b, c, a))
  95         else:
  96             c = randRange(b, a)
  97             assert b <= c < a, "output out of range %d  %d  %d" % (b, c, a)
  98
  99     def testOneHundredTimes(self):
 100         for i in xrange(100):
 101             self.testOnce()
 102
 103
 104
 105 if __name__ == '__main__':
 106     unittest.main()
 107
 108