hash.py

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