guid.py
Go to the documentation of this file.
00001 #!/usr/bin/env python
00002 
00003 """
00004 usage: %(progname)s [args]
00005 """
00006 
00007 # GUID.py
00008 # Version 2.1. 
00009 #
00010 # Copyright (C) 2003  Dr. Conan C. Albrecht <conan_albrechtATbyu.edu>
00011 #
00012 # This library is free software; you can redistribute it and/or
00013 # modify it under the terms of the GNU Lesser General Public
00014 # License as published by the Free Software Foundation; either
00015 # version 2.1 of the License, or (at your option) any later version.
00016 #
00017 # This library is distributed in the hope that it will be useful,
00018 # but WITHOUT ANY WARRANTY; without even the implied warranty of
00019 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00020 # Lesser General Public License for more details.
00021 #
00022 # You should have received a copy of the GNU Lesser General Public
00023 # License along with this library; if not, write to the Free Software
00024 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00025 
00026 
00027 
00028 ##################################################################################################
00029 ###   A globally-unique identifier made up of time and ip and 8 random digits: 16 characters wide
00030 ###  
00031 ###   A globally unique identifier that combines ip, time, and random bits.  Since the 
00032 ###   time is listed first, you can sort records by guid.  You can also extract the time 
00033 ###   and ip if needed.  
00034 ###     
00035 ###   GUIDs make wonderful database keys.  They require no access to the 
00036 ###   database (to get the max index number), they are extremely unique, and they sort 
00037 ###   automatically by time.   GUIDs prevent key clashes when merging
00038 ###   two databases together, combining data, or generating keys in distributed
00039 ###   systems.
00040 ###
00041 ###   There is an Internet Draft for UUIDs, but this module does not implement it.
00042 ###   If the draft catches on, perhaps I'll conform the module to it.
00043 ###
00044 
00045 
00046 # Changelog
00047 # Sometime, 1997     Created the Java version of GUID
00048 #                    Went through many versions in Java
00049 # Sometime, 2002     Created the Python version of GUID, mirroring the Java version
00050 # November 24, 2003  Changed Python version to be more pythonic, took out object and made just a module
00051 # December 2, 2003   Fixed duplicating GUIDs.  Sometimes they duplicate if multiples are created
00052 #                    in the same millisecond (it checks the last 100 GUIDs now and has a larger random part)
00053 # December 9, 2003   Fixed MAX_RANDOM, which was going over sys.maxint
00054 # November 21, 2005  Changed to pack the guid using 64 bit encoding 0-9, A-Z, a-z, @, [
00055 #                    Now, the guid is only 16 bytes long.
00056 #
00057 
00058 import math
00059 import random
00060 import socket
00061 import os, sys
00062 import time
00063 import threading
00064 import string, struct
00065 
00066 import getopt
00067 
00068 # The size of the circular queue.  Larger sizes give more assurance for uniqueness.
00069 # Smaller sizes take less memory and are a tiny bit faster
00070 QUEUE_SIZE = 100
00071 
00072 
00073 #############################
00074 ###   global module variables
00075 
00076 MAX_RANDOM = sys.maxint # converted to hex goes to 8 chars (at least, in Python 2.3)
00077 rand = random.Random()
00078 ip = ''
00079 lock = threading.RLock()
00080 lastguid = ''
00081 try:
00082   ip = socket.gethostbyname(socket.gethostname())
00083 except (socket.gaierror): # if we don't have an ip, default to someting in the 10.x.x.x private range
00084   ip = '10'
00085   for i in range(3):
00086     ip += '.' + str(rand.randrange(1, 254))
00087 hexip = ''.join(["%04x" % long(i) for i in ip.split('.')]) # leave space for ip v6 (65K in each sub)
00088 ipaddrStr = socket.inet_aton(ip)
00089 (ipaddr, ) = struct.unpack(">I", ipaddrStr)
00090 
00091 def encode64Char(i):
00092   if i<10: return chr(i+48)
00093   elif i<38: return chr(i-10+64)
00094   elif i<64: return chr(i-38+97)
00095   raise Error
00096   
00097 def pack64(i, bytes=6):
00098   parts = []
00099   for j in range(bytes):
00100     a = i & 0x3f
00101     i = (i >> 6)
00102     parts.append(encode64Char(a))
00103   parts.reverse()
00104   p = string.join(parts, "")
00105   return p
00106 
00107 def decode64Char(c):
00108   n = ord(c)
00109   if n>=48 and n<=58:
00110     return n-48
00111   elif n >= 64 and n <= 91:
00112     return n - 54
00113   elif n >= 97 and n <= 122:
00114     return n - 59
00115   raise Error
00116 
00117 def unpack64(s, bytes=6):
00118   i = 0L
00119 
00120   for j in range(bytes):
00121     c = s[j]
00122     a = decode64Char(c)
00123     i = i | a
00124     if j < bytes-1:
00125       i = i << 6
00126   return i
00127 
00128 if 0:
00129   for i in range(64):
00130     c = encode64Char(i)
00131     j = decode64Char(c)
00132     if i != j:
00133       print i, c, j
00134   
00135 ipaddr64 = pack64(ipaddr)
00136 
00137 #######################################
00138 ###   A simple circular set
00139 ###   to ensure we don't duplicate
00140 ###   GUIDs in the same millisecond
00141   
00142 class CircularSet:
00143   '''A circular set.  A set that maxes at a given size, replacing the oldest element after maximum size.
00144      This implementation is NOT thread safe.  (generate() below is thread safe, though)
00145   '''
00146   def __init__(self):
00147     self.queue = []
00148     self.queue_map = {} # for efficiency, we keep a map of everything
00149     self.queueindex = 0
00150 
00151   def add(self, val):
00152     '''Adds a value to the queue'''
00153     # check to see if we have this value.  If so, throw an exception
00154     assert not self.queue_map.has_key(val), 'This value is already in the set!'
00155     
00156     # add the new one to the list
00157     if len(self.queue) > self.queueindex:
00158       # first remove the previous key at this location
00159       del self.queue_map[self.queue[self.queueindex]]
00160       self.queue[self.queueindex] = val
00161     else:
00162       self.queue.append(val)
00163       
00164     # now add to the map for efficiency
00165     self.queue_map[val] = val
00166     
00167     # increment the queue index
00168     self.queueindex += 1
00169     if self.queueindex >= QUEUE_SIZE:
00170       self.queueindex = 0
00171       
00172 queue = CircularSet()
00173   
00174 #################################
00175 ###   Public module functions
00176 
00177 
00178 def generate(time_t = None):
00179   '''Generates a new guid'''
00180   global lock, queue  # since we modify the module variable
00181   if time_t > 1136102400:
00182     raise ValueError, "time_t is too large %s" % time_t
00183 
00184   try:
00185     lock.acquire() # can't generate two guids at the same time
00186     while 1:
00187       # time part
00188       if time_t == None:
00189         t = long(time.time() * 100)
00190       else:
00191         t = time_t * 100
00192 
00193       # random part
00194       r = int(rand.random() * MAX_RANDOM) & 0xffff
00195       n = 0L | (long(t)<<48) | (ipaddr<<16) | r
00196       guid = pack64(n, bytes=16)
00197 
00198       try:
00199         queue.add(guid)  # throws the AssertionError if this GUID is a duplicate of the queue
00200         return guid
00201       except AssertionError: # signals we already have this GUID in the queue
00202         pass
00203   finally:
00204     lock.release()
00205     
00206 InvalidGUID = "Invalid GUID"
00207 
00208 def extract_time(guid):
00209   '''Extracts the time portion out of the guid and returns the 
00210      number of seconds since the epoch as a float'''
00211   if len(guid) != 16: raise InvalidGUID
00212   n = unpack64(guid, bytes=16)
00213   t = long(n >> 48) / 100
00214   return t
00215 
00216 
00217 def extract_ip(guid):
00218   '''Extracts the ip portion out of the guid and returns it
00219      as a string like 10.10.10.10'''
00220 
00221   if len(guid) != 16: raise InvalidGUID
00222 
00223   n = unpack64(guid, bytes=16)
00224   n = n >> 16
00225   n = n & 0xffffffffL
00226 
00227   ip = struct.pack(">L", n)
00228   ipaddrStr = socket.inet_ntoa(ip)
00229   return ipaddrStr
00230 
00231 
00232 def extract_random(guid):
00233   '''Extracts the random bits from the guid (returns the bits in decimal)'''
00234   if len(guid) != 16: raise InvalidGUID
00235 
00236   n = unpack64(guid, bytes=16)
00237   r = int(n & 0xffff)
00238   return r
00239 
00240 
00241 ### TESTING OF GUID CLASS ###
00242 def test():
00243   pass
00244 
00245 def usage(progname):
00246   print __doc__ % vars()
00247 
00248 def main(argv, stdout, environ):
00249   progname = argv[0]
00250   optlist, args = getopt.getopt(argv[1:], "", ["help", "test", "debug"])
00251 
00252   testflag = 0
00253 
00254   for (field, val) in optlist:
00255     if field == "--help":
00256       usage(progname)
00257       return
00258     elif field == "--debug":
00259       debugfull()
00260     elif field == "--test":
00261       testflag = 1
00262 
00263   if testflag:
00264     test()
00265     return
00266 
00267   guids = []
00268   if len(args) == 0:
00269     guids.append(generate())
00270   else:
00271     for arg in args:
00272       guids.append(arg)
00273 
00274   for guid in guids:
00275     print "GUID:", guid
00276     print "Time:", time.strftime('%a, %d %b %Y %H:%M:%S', time.localtime(extract_time(guid)))
00277     print "IP:  ", extract_ip(guid)
00278     print "Rand:", extract_random(guid)
00279     print
00280 
00281 
00282 if __name__ == "__main__":
00283   main(sys.argv, sys.stdout, os.environ)
00284 
00285   


pyclearsilver
Author(s): Scott Hassan/hassan@willowgarage.com
autogenerated on Sat Dec 28 2013 17:47:30