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