hash.py

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