apt_p2p_Khashmir/khash.py

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