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