apt_p2p_Khashmir/khash.py

   1
   2 """Functions to deal with hashes (node IDs and keys).
   3
   4 @var HASH_LENGTH: the length of the hash to use in bytes
   5 """
   6
   7 from sha import sha
   8 from os import urandom
   9
  10 from twisted.trial import unittest
  11
  12 HASH_LENGTH = 20
  13
  14 def intify(hstr):
  15     """Convert a hash (big-endian) to a long python integer."""
  16     assert len(hstr) == HASH_LENGTH
  17     return long(hstr.encode('hex'), 16)
  18
  19 def stringify(num):
  20     """Convert a long python integer to a hash."""
  21     str = hex(num)[2:]
  22     if str[-1] == 'L':
  23         str = str[:-1]
  24     if len(str) % 2 != 0:
  25         str = '0' + str
  26     str = str.decode('hex')
  27     return (HASH_LENGTH - len(str)) *'\x00' + str
  28
  29 def distance(a, b):
  30     """Calculate the distance between two hashes expressed as strings."""
  31     return intify(a) ^ intify(b)
  32
  33 def newID():
  34     """Get a new pseudorandom globally unique hash string."""
  35     h = sha()
  36     h.update(urandom(HASH_LENGTH))
  37     return h.digest()
  38
  39 def newIDInRange(min, max):
  40     """Get a new pseudorandom globally unique hash string in the range."""
  41     return stringify(randRange(min,max))
  42
  43 def randRange(min, max):
  44     """Get a new pseudorandom globally unique hash number in the range."""
  45     return min + intify(newID()) % (max - min)
  46
  47 def newTID():
  48     """Get a new pseudorandom transaction ID number."""
  49     return randRange(-2**30, 2**30)
  50
  51 class TestNewID(unittest.TestCase):
  52     """Test the newID function."""
  53     def testLength(self):
  54         self.failUnlessEqual(len(newID()), HASH_LENGTH)
  55     def testHundreds(self):
  56         for x in xrange(100):
  57             self.testLength
  58
  59 class TestIntify(unittest.TestCase):
  60     """Test the intify function."""
  61     known = [('\0' * HASH_LENGTH, 0),
  62             ('\xff' * HASH_LENGTH, 2L**(HASH_LENGTH*8) - 1),
  63             ]
  64     def testKnown(self):
  65         for str, value in self.known:
  66             self.failUnlessEqual(intify(str),  value)
  67     def testEndianessOnce(self):
  68         h = newID()
  69         while h[-1] == '\xff':
  70             h = newID()
  71         k = h[:-1] + chr(ord(h[-1]) + 1)
  72         self.failUnlessEqual(intify(k) - intify(h), 1)
  73     def testEndianessLots(self):
  74         for x in xrange(100):
  75             self.testEndianessOnce()
  76
  77 class TestDisantance(unittest.TestCase):
  78     """Test the distance function."""
  79     known = [
  80             (("\0" * HASH_LENGTH, "\xff" * HASH_LENGTH), 2L**(HASH_LENGTH*8) -1),
  81             ((sha("foo").digest(), sha("foo").digest()), 0),
  82             ((sha("bar").digest(), sha("bar").digest()), 0)
  83             ]
  84     def testKnown(self):
  85         for pair, dist in self.known:
  86             self.failUnlessEqual(distance(pair[0], pair[1]), dist)
  87     def testCommutitive(self):
  88         for i in xrange(100):
  89             x, y, z = newID(), newID(), newID()
  90             self.failUnlessEqual(distance(x,y) ^ distance(y, z), distance(x, z))
  91
  92 class TestRandRange(unittest.TestCase):
  93     """Test the randRange function."""
  94     def testOnce(self):
  95         a = intify(newID())
  96         b = intify(newID())
  97         if a < b:
  98             c = randRange(a, b)
  99             self.failUnlessEqual(a <= c < b, True, "output out of range %d  %d  %d" % (b, c, a))
 100         else:
 101             c = randRange(b, a)
 102             self.failUnlessEqual(b <= c < a, True, "output out of range %d  %d  %d" % (b, c, a))
 103
 104     def testOneHundredTimes(self):
 105         for i in xrange(100):
 106             self.testOnce()