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 long python integer
   7 def intify(hstr):
   8     assert(len(hstr) == 20)
   9     return eval('0x' + hstr.encode('hex') + 'L')
  10
  11 ## takes a long int and returns a 20-character string
  12 def stringify(int):
  13     str = hex(int)[2:]
  14     if str[-1] == 'L':
  15         str = str[:1]
  16     str = str.decode('hex')
  17     return (20 - len(str)) *'\x00' + str
  18
  19 ## returns the distance between two 160-bit hashes expressed as 20-character strings
  20 def distance(a, b):
  21     return intify(a) ^ intify(b)
  22
  23
  24 ## returns a new pseudorandom globally unique ID string
  25 def newID():
  26     h = sha()
  27     for i in range(20):
  28         h.update(chr(randrange(0,256)))
  29     return h.digest()
  30
  31 def newIDInRange(min, max):
  32     return stringify(randRange(min,max))
  33
  34 def randRange(min, max):
  35     return min + intify(newID()) % (max - min)
  36
  37 import unittest
  38
  39 class NewID(unittest.TestCase):
  40     def testLength(self):
  41         self.assertEqual(len(newID()), 20)
  42     def testHundreds(self):
  43         for x in xrange(100):
  44             self.testLength
  45
  46 class Intify(unittest.TestCase):
  47     known = [('\0' * 20, 0),
  48              ('\xff' * 20, 2L**160 - 1),
  49             ]
  50     def testKnown(self):
  51         for str, value in self.known:
  52             self.assertEqual(intify(str),  value)
  53     def testEndianessOnce(self):
  54         h = newID()
  55         while h[-1] == '\xff':
  56             h = newID()
  57         k = h[:-1] + chr(ord(h[-1]) + 1)
  58         self.assertEqual(intify(k) - intify(h), 1)
  59     def testEndianessLots(self):
  60         for x in xrange(100):
  61             self.testEndianessOnce()
  62
  63 class Disantance(unittest.TestCase):
  64     known = [
  65             (("\0" * 20, "\xff" * 20), 2**160L -1),
  66             ((sha("foo").digest(), sha("foo").digest()), 0),
  67             ((sha("bar").digest(), sha("bar").digest()), 0)
  68             ]
  69     def testKnown(self):
  70         for pair, dist in self.known:
  71             self.assertEqual(distance(pair[0], pair[1]), dist)
  72     def testCommutitive(self):
  73         for i in xrange(100):
  74             x, y, z = newID(), newID(), newID()
  75             self.assertEqual(distance(x,y) ^ distance(y, z), distance(x, z))
  76
  77 class RandRange(unittest.TestCase):
  78     def testOnce(self):
  79         a = intify(newID())
  80         b = intify(newID())
  81         if a < b:
  82             c = randRange(a, b)
  83             self.assertEqual(a <= c < b, 1, "output out of range %d  %d  %d" % (b, c, a))
  84         else:
  85             c = randRange(b, a)
  86             assert b <= c < a, "output out of range %d  %d  %d" % (b, c, a)
  87
  88     def testOneHundredTimes(self):
  89         for i in xrange(100):
  90             self.testOnce()
  91
  92
  93
  94 if __name__ == '__main__':
  95     unittest.main()
  96
  97