khash.py

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