Source code: com/vinculum/engine/HashUtil.java
1 /* * ** ** BEGIN LICENSE BLOCK * ** **
2 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
3 *
4 * The contents of this file are subject to the Mozilla Public License Version
5 * 1.1 (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 * http://www.mozilla.org/MPL/
8 *
9 * Software distributed under the License is distributed on an "AS IS" basis,
10 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
11 * for the specific language governing rights and limitations under the
12 * License.
13 *
14 * The Original Code is Vinculum Open Source.
15 *
16 * The Initial Developer of the Original Code is
17 * Gerard Toonstra.
18 * Portions created by the Initial Developer are Copyright (C) 2003
19 * the Initial Developer. All Rights Reserved.
20 *
21 * Contributor(s):
22 *
23 * Alternatively, the contents of this file may be used under the terms of
24 * either the GNU General Public License Version 2 or later (the "GPL"), or
25 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
26 * in which case the provisions of the GPL or the LGPL are applicable instead
27 * of those above. If you wish to allow use of your version of this file only
28 * under the terms of either the GPL or the LGPL, and not to allow others to
29 * use your version of this file under the terms of the MPL, indicate your
30 * decision by deleting the provisions above and replace them with the notice
31 * and other provisions required by the GPL or the LGPL. If you do not delete
32 * the provisions above, a recipient may use your version of this file under
33 * the terms of any one of the MPL, the GPL or the LGPL.
34 *
35 * ** ** * END LICENSE BLOCK * ** **
36 */
37
38 /***************************************************************************
39 $RCSfile: HashUtil.java,v $ - description
40 -------------------
41 begin : $Date: 2003/09/12 17:50:42 $
42 copyright : Vinculum (C) 2002
43 author : $Author: chiraz $
44 ***************************************************************************/
45
46 /*
47 * $Log: HashUtil.java,v $
48 * Revision 1.1 2003/09/12 17:50:42 chiraz
49 * Changes to support cleaning up objects belonging to specific sessions.
50 *
51 */
52
53 //
54 // A Java Hash Class
55 // Including Constructors and Methods for Dealing with Hash Values
56 //
57 // Copyright (c)1996 Robert Uzgalis, All Rights Reserved.
58 //
59
60 package com.vinculum.engine;
61
62 /**
63 * @author chilan
64 */
65 public class HashUtil
66 {
67 private long hash_code;
68
69 private static long initial_hash = 0xe12398c6d9ae3b8aL; // initial values
70 private static long hash_true = 0x851dcaa2656c6af4L; // are arbitrary
71 private static long hash_false = 0x1af84a6b589285f7L; // 64-bit rands
72 private static long mix_master[/* 0:255 */] = {
73 /* 000 */ 0x4476081a7043a46fL, 0x45768b8a6e7eac19L, 0xebd556c1cf055952L,
74 /* */ 0x72ed2da1bf010101L, 0x3ff2030b128e8a64L,
75 /* 005 */ 0xcbc330238adcfef2L, 0x737807fe42e20c6cL, 0x74dabaedb1095c58L,
76 /* */ 0x968f065c65361d67L, 0xd3f4018ac7a4b199L,
77 /* 010 */ 0x954b389b52f24df2L, 0x2f97a9d8d0549327L, 0xb9bea2b49a3b180fL,
78 /* */ 0xaf2f42536b21f2ebL, 0x85d991663cff1325L,
79 /* 015 */ 0xb9e1260207b575b9L, 0xf3ea88398a23b7e2L, 0xfaf8c83ffbd9091dL,
80 /* */ 0x4274fe90834dbdf9L, 0x3f20b157b68d6313L,
81 /* 020 */ 0x68b48972b6d06b93L, 0x694837b6eba548afL, 0xeecb51d1acc917c9L,
82 /* */ 0xf1c633f02dffbcfaL, 0xa6549ec9d301f3b5L,
83 /* 025 */ 0x451dc944f1663592L, 0x446d6acef6ce9e4fL, 0x1c8a5b3013206f02L,
84 /* */ 0x5908ca36f2dc50f7L, 0x4fd55d3f3e880a87L,
85 /* 030 */ 0xa03a8dbeabbf065dL, 0x3ccbbe078fabcb6dL, 0x1da53a259116f2d0L,
86 /* */ 0xfb27a96fcb9af152L, 0x50aba242e85aec09L,
87 /* 035 */ 0x24d4e414fc4fc987L, 0x83971844a9ce535eL, 0xc26a3fdeb849398eL,
88 /* */ 0xc2380d044d2e70d8L, 0xab418aa8ae19b18fL,
89 /* 040 */ 0xd95b6b9247d5ebeaL, 0x8b3b2171fdc60511L, 0xe15cd0ae3fcc44afL,
90 /* */ 0x5a4e27f914a68f17L, 0x377bd28ca09aafdcL,
91 /* 045 */ 0xbbeb9828594a3294L, 0x7c8df263ae1de1b9L, 0xba0a48a5fd1c1dd0L,
92 /* */ 0x57cc1b8818b98ee6L, 0x8c570975d357dabcL,
93 /* 050 */ 0x76bdcd6f2e8826aaL, 0x529b15b6ec4055f1L, 0x9147c7a54c34f8a9L,
94 /* */ 0x2f96a7728170e402L, 0xe46602f455eca72eL,
95 /* 055 */ 0x22834c4dd1bde03fL, 0x2644cf5a25e368ffL, 0x907c6de90b120f4aL,
96 /* */ 0xadfe8ba99028f728L, 0xa85199ae14df0433L,
97 /* 060 */ 0x2d749b946dd3601eL, 0x76e35457aa052772L, 0x90410bf6e427f736L,
98 /* */ 0x536ad04d13e35041L, 0x8cc0d76769b76914L,
99 /* 065 */ 0xae0249f6e3b3c01cL, 0x1bdfd075307d6fafL, 0xd8e04f70c221deccL,
100 /* */ 0x4ab23622a4281a5dL, 0x37a5613da2fcaba7L,
101 /* 070 */ 0x19a56203666d4a9fL, 0x158ffab502c4be93L, 0x0bee714e332ecb2fL,
102 /* */ 0x69b71a59f6f74ab0L, 0x0fc7fc622f1dfe8fL,
103 /* 075 */ 0x513966de7152a6f9L, 0xc16fae9cc2ea9be7L, 0xb66f0ac586c1899eL,
104 /* */ 0x11e124aee3bdefd7L, 0x86cf5a577512901bL,
105 /* 080 */ 0x33f33ba6994a1fbdL, 0xde6c4d1d3d47ff0dL, 0x6a99220dc6f78e66L,
106 /* */ 0x2dc06ca93e2d25d2L, 0x96413b520134d573L,
107 /* 085 */ 0xb4715ce8e1023afaL, 0xe6a75900c8c66c0aL, 0x6448f13ad54c12edL,
108 /* */ 0xb9057c28cf6689f0L, 0xf4023daf67f7677aL,
109 /* 090 */ 0x877c2650767b9867L, 0xb7ea587dcd5b2341L, 0xc048cf111733f9bcL,
110 /* */ 0x112012c15bc867bfL, 0xc95f52b1d9418811L,
111 /* 095 */ 0xa47e624ee7499083L, 0x26928606df9b12e8L, 0x5d020462ec3e0928L,
112 /* */ 0x8bbde651f6d08914L, 0xd5db83db758e524aL,
113 /* 100 */ 0x3105e355c000f455L, 0xdd7fe1b81a786c79L, 0x1f3a818c8e012db1L,
114 /* */ 0xd902de819d7b42faL, 0x4200e63325cda5f0L,
115 /* 105 */ 0x0e919cdc5fba9220L, 0x5360dd54605a11e1L, 0xa3182d0e6cb23e6cL,
116 /* */ 0x13ee462c1b483b87L, 0x1b1b6087b997ee22L,
117 /* 110 */ 0x81c36d0b877f7362L, 0xc24879932c1768d4L, 0x1faa756e1673f9adL,
118 /* */ 0x61651b24d11fe93dL, 0x30fe3d9304e1cde4L,
119 /* 115 */ 0x7be867c750747250L, 0x973e52c7005b5db6L, 0x75d6b699bbaf4817L,
120 /* */ 0x25d2a9e97379e196L, 0xe65fb599aca98701L,
121 /* 120 */ 0x6ac27960d24bde84L, 0xdfacc04c9fabbcb6L, 0xa46cd07f4a97882bL,
122 /* */ 0x652031d8e59a1fd8L, 0x1185bd967ec7ce10L,
123 /* 125 */ 0xfc9bd84c6780f244L, 0x0a0c59872f61b3ffL, 0x63885727a1c71c95L,
124 /* */ 0x5e88b4390b2d765cL, 0xf0005ccaf988514dL,
125 /* 130 */ 0x474e44280a98e840L, 0x32de151c1411bc42L, 0x2c4b86d5aa4482c2L,
126 /* */ 0xccd93deb2d9d47daL, 0x3743236ff128a622L,
127 /* 135 */ 0x42ed2f2635ba5647L, 0x99c74afd18962dbdL, 0x2d663bb870f6d242L,
128 /* */ 0x7912033bc7635d81L, 0xb442862f43753680L,
129 /* 140 */ 0x94b1a5400aeaab4cL, 0x5ce285fe810f2220L, 0xe8a7dbe565d9c0b1L,
130 /* */ 0x219131af78356c94L, 0x7b3a80d130f27e2fL,
131 /* 145 */ 0xbaa5d2859d16b440L, 0x821cfb6935771070L, 0xf68cfb6ee9bc2336L,
132 /* */ 0x18244132e935d2fdL, 0x2ed0bda1f4720cffL,
133 /* 150 */ 0x4ed48cdf6975173cL, 0xfd37a7a2520e2405L, 0x82c102b2a9e73ce2L,
134 /* */ 0xadac6517062623a7L, 0x5a1294d318e26104L,
135 /* 155 */ 0xea84fe65c0e4f061L, 0x4f96f8a9464cfee9L, 0x9831dff8ccdc534aL,
136 /* */ 0x4ca927cd0f192a14L, 0x030900b294b71649L,
137 /* 160 */ 0x644b263b9aeb0675L, 0xa601d4e34647e040L, 0x34d897eb397f1004L,
138 /* */ 0xa6101c37f4ec8dfcL, 0xc29d2a8bbfd0006bL,
139 /* 165 */ 0xc6b07df8c5b4ed0fL, 0xce1b7d92ba6bccbeL, 0xfa2f99442e03fe1bL,
140 /* */ 0xd8863e4c16f0b363L, 0x033b2cccc3392942L,
141 /* 170 */ 0x757dc33522d6cf9cL, 0xf07b1ff6ce55fec5L, 0x1569e75f09b40463L,
142 /* */ 0xfa33fa08f14a310bL, 0x6eb79aa27bbcf76bL,
143 /* 175 */ 0x157061207c249602L, 0x25e5a71fc4e99555L, 0x5df1fe93de625355L,
144 /* */ 0x235b56090c1aa55dL, 0xe51068613eaced91L,
145 /* 180 */ 0x45bd47b893b9ff1eL, 0x6595e1798d381f2dL, 0xc9b5848cbcdb5ba8L,
146 /* */ 0x65985146ff7792bcL, 0x4ab4a17bf05a19a0L,
147 /* 185 */ 0xfd94f4ca560ffb0cL, 0xcf9bad581a68fa68L, 0x92b4f0b502b1ce1aL,
148 /* */ 0xbcbec0769a610474L, 0x8dbd31ded1a0fecbL,
149 /* 190 */ 0xdd1f5ed9f90e8533L, 0x61c1e6a523f84d95L, 0xf24475f383c110c4L,
150 /* */ 0xdb2dffa66f90588dL, 0xac06d88e9ee04455L,
151 /* 195 */ 0xa215fc47c40504baL, 0x86d7caebfee93369L, 0x9eaec31985804099L,
152 /* */ 0x0fba2214abe5d01bL, 0x5a32975a4b3865d6L,
153 /* 200 */ 0x8cceebc98a5c108fL, 0x7e12c4589654f2dcL, 0xa49ad49fb0d19772L,
154 /* */ 0x3d142dd9c406152bL, 0x9f13589e7be2b8a5L,
155 /* 205 */ 0x5e8dbac1892967adL, 0xcc23b93a6308e597L, 0x1ef35f5fe874e16aL,
156 /* */ 0x63ae9cc08d2e274fL, 0x5bbabee56007fc05L,
157 /* 210 */ 0xabfd72994230fc39L, 0x9d71a13a99144de1L, 0xd9daf5aa8dcc89b3L,
158 /* */ 0xe145ec0514161bfdL, 0x143befc2498cd270L,
159 /* 215 */ 0xa8e192557dbbd9f8L, 0xcbeda2445628d7d0L, 0x997f0a93205d9ea4L,
160 /* */ 0x01014a97f214ebfaL, 0x70c026ffd1ebedafL,
161 /* 220 */ 0xf8737b1b3237002fL, 0x8afcbef3147e6e5eL, 0x0e1bb0684483ebd3L,
162 /* */ 0x4cbad70ae9b05aa6L, 0xd4a31f523517c363L,
163 /* 225 */ 0xdb0f057ae8e9e8a2L, 0x400894a919d89df6L, 0x6a626a9b62defab3L,
164 /* */ 0xf907fd7e14f4e201L, 0xe10e4a5657c48f3fL,
165 /* 230 */ 0xb17f9f54b8e6e5dcL, 0x6b9e69045fa6d27aL, 0x8b74b6a41dc3078eL,
166 /* */ 0x027954d45ca367f9L, 0xd07207b8fdcbb7ccL,
167 /* 235 */ 0xf397c47d2f36414bL, 0x05e4e8b11d3a034fL, 0x36adb3f7122d654fL,
168 /* */ 0x607d9540eb336078L, 0xb639118e3a8b9600L,
169 /* 240 */ 0xd0a406770b5f1484L, 0x3cbee8213ccfb7c6L, 0x467967bb2ff89cf1L,
170 /* */ 0xb115fe29609919a6L, 0xba740e6ffa83287eL,
171 /* 245 */ 0xb4e51be9b694b7cdL, 0xc9a081c677df5aeaL, 0x2e1fbcd8944508ccL,
172 /* */ 0xf626e7895581fbb8L, 0x3ce6e9b5728a05cbL,
173 /* 250 */ 0x46e87f2664a31712L, 0x8c1dc526c2f6acfaL, 0x7b4826726e560b10L,
174 /* */ 0x2966e0099d8d7ce1L, 0xbb0dd5240d2b2adeL, 0x0d527cc60bbaa936L
175 };
176
177
178 // Utility Methods for Hash Values
179 //
180
181 // Move the bits in an integer long into a StringBuffer without
182 // conversion, then hash the string buffer, returning a long.
183
184 private static long lhv (long arg) // Hash a long
185 { StringBuffer tmp = new StringBuffer(4);
186 long aval = arg;
187
188 tmp.setLength(4);
189 for ( int i=0; i<4; ++i, aval >>>= 16 )
190 tmp.setCharAt( i, (char) aval);
191
192 return buzhash( tmp );
193 }
194
195 // This is buzhash the hash function on which most other Hash methods
196 // and constructors are built.
197
198 private static long buzhash (StringBuffer arg) /* Hash StringBuffer */
199 { long h = initial_hash;
200 for ( int i=0; i<arg.length(); ++i )
201 h = (h<<1) ^ (h>>>63) ^
202 mix_master[ ( arg.charAt(i) ^ (arg.charAt(i)>>>8) ) & 0xff ];
203 return h;
204 }
205
206 // Constructors for Hash values;
207 // invoked as: new Hash( some-key-to-be-hashed )
208 // they operate on the key and return a Hash value.
209
210 public HashUtil() // The Hash of nothing
211 { this.hash_code = initial_hash; }
212
213 public HashUtil ( HashUtil hc ) // The next extension of a Hash value
214 { this.hash_code = lhv( hc.hash_code ); }
215
216 public HashUtil (boolean arg) // Make Hash from boolean
217 { this.hash_code = ( arg ? hash_true : hash_false ) ; }
218
219 public HashUtil (byte arg) // Make Hash from byte
220 { this.hash_code = mix_master[ (((int)(arg))+183) & 0xff ]; }
221
222 public HashUtil (short arg) // Make Hash from short
223 { this.hash_code = lhv( (long) arg ); }
224
225 public HashUtil (char arg) // Make Hash from char
226 { this.hash_code = lhv( (long) arg ); }
227
228 public HashUtil (int arg) // Make Hash from int
229 { this.hash_code = lhv( (long) arg ); }
230
231 public HashUtil (long arg) // Make Hash from long
232 { this.hash_code = lhv( arg ); }
233
234 // These are commented out because they require a C routine
235 // to give back the floating point bits back unconverted
236 // as a long integer.
237 //
238 // public Hash (float arg) // Make Hash from float
239 // { this.hash_code = lhv( bytes8( (double) arg ) ); }
240 //
241 // public Hash (double arg) // Make Hash from double
242 // { this.hash_code = lhv( bytes8( (double) arg ) ); }
243
244 public HashUtil (String arg) // Make Hash from String
245 { this.hash_code = buzhash( new StringBuffer(arg) ); }
246
247 public HashUtil (StringBuffer arg) // Make Hash from StringBuffer
248 { this.hash_code = buzhash( arg ); }
249
250 // These are all the constructors supported here, one could think
251 // of others, there should be one for every type for which an
252 // an equal comparison works.
253
254
255 // Hash Abstract Type Methods for manipulating Hash Values
256
257 // Methods to Compare Hash Values and Return Boolean.
258
259 public boolean equal ( HashUtil b ) // Test Equivalence of two Hashes
260 { return ( this.hash_code == b.hash_code ); }
261
262 public boolean not_equal ( HashUtil b ) // Test Equivalence of two Hashes
263 { return ( this.hash_code != b.hash_code ); }
264
265 public boolean more ( HashUtil b ) // Test Hash Value a bigger than b
266 { if ( (this.hash_code>>>1) > (b.hash_code>>>1) )
267 return true;
268 else if ( (this.hash_code>>>1) < (b.hash_code>>>1) )
269 return false;
270 else return (this.hash_code&0x1) > (b.hash_code&0x1);
271 }
272
273 public boolean less ( HashUtil b ) // Test Hash Value a less than b
274 { return b.more(this); }
275
276 // Methods for Combining Two Hash Values.
277
278 public HashUtil wag ( HashUtil b ) // Weak Agglomeration of two Hashes
279 { HashUtil result = new HashUtil();
280 result.hash_code = this.hash_code ^ b.hash_code;
281 return result;
282 }
283
284 public HashUtil sag ( HashUtil b ) // Strong Agglomeration of two Hashes
285 { StringBuffer tmp = new StringBuffer(8);
286 HashUtil result = new HashUtil();
287 long aval = this.hash_code;
288 long bval = b.hash_code;
289
290 tmp.setLength(8);
291 for( int i=0; i<4; i+=2 )
292 { tmp.setCharAt( i, (char) aval );
293 aval >>>= 16;
294 tmp.setCharAt( i+1, (char) bval );
295 bval >>>= 16;
296 }
297
298 result.hash_code = buzhash( tmp );
299 return result;
300 }
301
302 // Methods which Convert Hash Values to Integers.
303
304 private static long NOSIGN = 0x7fffffffffffffffL;
305
306 public byte bag ( byte b ) // Convert Hash to byte
307 { return (byte) ((this.hash_code & NOSIGN ) % (b<0? -b : b )); }
308
309 public short bag ( short b ) // Convert Hash to short
310 { return (short)((this.hash_code & NOSIGN ) % (b<0? -b : b )); }
311
312 public char bag ( char b ) // Convert Hash to char
313 { return (char) ((this.hash_code & NOSIGN ) % b); }
314
315 public int bag ( int b ) // Convert Hash to int
316 { return (int) ((this.hash_code & NOSIGN ) % (b<0? -b : b )); }
317
318 public long bag ( long b ) // Convert Hash to long
319 { return (this.hash_code & NOSIGN ) % (b<0? -b : b ); }
320
321 public String getStringHash()
322 {
323 Long code = new Long( hash_code );
324 String result = code.toString();
325 return result;
326 }
327 }
328