001    // Copyright (c) 2001 Hursh Jain (http://www.mollypages.org) 
002    // The Molly framework is freely distributable under the terms of an
003    // MIT-style license. For details, see the molly pages web site at:
004    // http://www.mollypages.org/. Use, modify, have fun !
005    
006    package fc.util;
007    
008    import java.util.*;
009    import java.util.regex.*;
010    import java.security.*;
011    
012    /* 
013    UUID and token utilities
014    
015    @author hursh jain
016    */
017    public final class UUIDUtil
018    {
019    static MessageDigest digester = null;
020    
021    static {
022      try {
023        digester = MessageDigest.getInstance("SHA-1");
024        }
025      catch (Exception e) {
026        e.printStackTrace();
027        }
028      }
029    
030    /**
031    Returns a ID suitable for a session/cookie identifier.
032    <pre>
033    See: cookies.lcs.mit.edu
034    See: www.across.si
035    
036    There are 2 issues with generating sessionid's. 
037    
038    1) uniqueness - 2 or more sessionid's should not end up being 
039       the same.
040    2) hard-to-guess - For example, sequential values like 
041       1, 2, 3 are unique but easy to guess and therefore easy
042       to session hijack.
043    
044    Our sessionid's have 2 parts:
045    a) a timestamp for guaranteed uniqueness  (easy to guess)
046    b) random data (hard to guess)
047    </pre>
048    */
049    public static String newSessionID() 
050      {
051      //although this function has been written for some time,
052      //i recently looked this over with webscarab (around aug 2007)
053      //and it visually appears fairly scattered/random. (9999 sid's)
054      //dunno, maybe hotbits retrieved/cached every minute via a background
055      //thread is good if one wants to be hardcore but it's pretty good
056      //as-is 
057      
058      //there is also no visual difference between nanos & millis. intuitively
059      //nanos should have more differences in the lower bits but after
060      //all the bits get churned/digested, there is no diff that i can tell,
061      //at least visually via webscarab. so i've left this as millis.
062      
063      final long time = System.currentTimeMillis();   
064    
065      Random random = new java.util.Random();
066      final int rand = random.nextInt(); 
067      final String cookie = String.valueOf(time) + rand;
068    
069      byte[] digestbuf = null;
070      
071      //digests always returns 16 bytes         
072      synchronized (UUIDUtil.class) {   
073        digestbuf = digester.digest(cookie.getBytes());
074          }
075        
076      /*
077      we simply convert bytes toHex. note, we don't use Base64
078      because '/' and '+' are valid Base64 chars and they can
079      mess up url's. 
080      */
081        
082        char[] encoded = null;
083        encoded = encode(digestbuf);
084        return new String(encoded);
085        
086        //note, we don't ever need to use the decode() method
087        //but it's there for testing foo->encode->decode->foo
088        }
089    
090    
091    //well, i was very...young...when I wrote this... :-]
092    //
093    //all right, as of 2014, i took out the original string, a bit too risque
094    //new lookup string is less embarassing
095    //                1..............16 [or 0-15, 16 things]  
096    //                0123456789ABCDEF
097    static final char[] lookup="wInteEMubY2169x0".toCharArray();
098    
099    /*
100    base16 encoding
101         0 -> some ascii code
102           1 -> some ascii code
103           ...
104           15-> some ascii code
105           
106    when ascii codes are for 0...F it's called "hex" encoding. 
107    */
108    
109    //we need a reverse lookup table since are ain't
110    //using straight hexadecimal to encode
111    //encode: half byte [0-16] -> char value from lookup string
112    //decode: char value from lookup string (0-128) -> half byte
113    static final int[] reverselookup = new int[128];
114      
115    static  
116      {
117      for (int n = 0; n < 16; n++) {
118        int x =  lookup[n] & 0xFF; //x ='c'('c'&0xff->99), 'n'(110) etc
119        reverselookup[x] = n;  //this is why reverselookup[128] above, not 16
120        }
121      }
122      
123    private static final char[] encode(byte[] buf) 
124      {
125      final int len = buf.length;
126    
127      char[] tmp = new char[len * 2];  
128      
129      for (int n = 0, i = 0; n < len ; n++, i+=2)
130        {
131        int high4 =  (buf[n] >> 4) & 0x0F;
132        int low4  =  buf[n] & 0x0F;
133        
134        tmp[i]   = lookup [high4];
135        tmp[i+1] = lookup [low4];
136        }
137      return tmp;
138      }
139    
140    private static final byte[] decode(char[] buf) 
141      {
142      final int len = buf.length;
143    
144      byte[] tmp = new byte[(len/2) + (len%2)];
145    
146      for (int n = 0, tmp_n = 0; n < len; n+=2, tmp_n++) 
147        {
148        //0xFF makes it an int. we could cast to (int)
149        //too but then that would sign extend the char
150        //in the general case [but since all are chars
151        //are < 127], it would be ok to do so in this
152        //case. Used 0xFF because that's the right thing
153        //generally speaking
154    
155        int c1 = buf[n] & 0xFF;   //'w', 'I', 'n', 't' etc.. 
156        int c2 = buf[n+1] & 0xFF;
157    
158        if ( c1 > 127 || c2 > 127)
159          throw new IllegalArgumentException("malformed bufing, encoded with characters I don't understand [" + c1 + "] and [" + c2 + "]");
160            
161        int i = (reverselookup[c1] << 4  | reverselookup [c2]); 
162        //System.out.println( (reverselookup[c1] << 4) + ", " + reverselookup[c2] + ",->" + i);
163    
164        tmp[tmp_n] = (byte) i;
165        }
166      return tmp;
167      }
168      
169    
170    static char[] URL_safe_chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_-.~".toCharArray();
171    
172    /**
173    Returns a N-char string suitable for tracking, affiliate, short codes, etc. Uses
174    characters safe for all URL's.
175    
176    @param  len the length of the returned string
177    */
178    public static String newID(int len)
179      {
180      final Random r = new Random();
181      final char[] buf = new char[len];
182      for (int n = 0; n < len; n++) {
183        buf[n] = URL_safe_chars[r.nextInt(URL_safe_chars.length)];
184        }
185      
186      return new String(buf);
187      }
188    
189    /**
190    Returns a 8 character string suitable for tracking, affiliate, short codes, etc. Uses
191    characters safe for all URL's.
192    */
193    public static String newID()
194      {
195      return newID(8);
196      }
197        
198    public static void main (String args[])
199      {
200      Args myargs = new Args(args);
201      int LOOP = myargs.getInt("loop", 100000);
202      myargs.setUsage("java fc.util.UUIDUtil [-loop <int, default 100,000>]");
203      
204      if (myargs.flagExists("help")) {
205        myargs.showError();
206        return;
207        }
208      System.out.println("Session ID: " + newSessionID());
209      System.out.println("Generating " + LOOP + " test session ids...");
210    
211      fc.util.Watch w = new fc.util.Watch();
212      Map map = null;
213      int count = -1;
214      
215      w.start();  
216      for (int n = 0; n < LOOP; n++) {
217        String s = newSessionID();
218        }
219      System.out.println("Time for " + LOOP + ": " + w.time() + " ms");
220      
221      System.out.println("Now testing for collisions...");
222      w.restart();
223    
224      map = new HashMap();
225      count = 0;
226      for (int n = 0; n < LOOP; n++) 
227        {
228        String s = newSessionID();
229        if (map.containsKey(s)) {
230          System.out.println("collision found with key: " + s);
231          count++;
232          }
233        if (n > 0 && n % 20000 == 0) {
234          w.stop();
235          System.out.println("generated: " + n + " (+ " + w.time() + " ms)");
236          w.restart();
237          }
238        map.put(s, null);
239        }
240      if (count == 0) {
241        System.out.println("No collisions found...");
242        }
243      else{
244        System.out.println(count + " collisions found...");
245        }
246    
247      System.out.println("------------------------------");
248      w.restart();  
249      System.out.println("newID (8): " + newID(8));
250      System.out.println("Generating " + LOOP + " test session ids...");
251    
252      for (int n = 0; n < LOOP; n++) {
253        String s = newID(8);
254        }
255      System.out.println("Time for " + LOOP + ": " + w.time() + " ms");
256    
257      System.out.println("Now testing for collisions...");
258      w.restart();
259    
260      map = new HashMap();
261      count = 0;
262      for (int n = 0; n < LOOP; n++) 
263        {
264        String s = newID(8);
265        if (map.containsKey(s)) {
266          System.out.println("collision found with key: " + s);
267          count++;
268          }
269        if (n > 0 && n % 20000 == 0) {
270          w.stop();
271          System.out.println("generated: " + n + " (+ " + w.time() + " ms)");
272          w.restart();
273          }
274        map.put(s, null);
275        }
276      if (count == 0) {
277        System.out.println("No collisions found...");
278        }
279      else{
280        System.out.println(count + " collisions found...");
281        }
282      }
283      
284    
285    }