001package squidpony.squidmath;
002
003/**
004 * Simple hashing functions that we can rely on staying the same cross-platform.
005 * These use the Fowler/Noll/Vo Hash (FNV-1a) algorithm, which is public domain.
006 * The hashes this returns are always 0 when given null to hash. Arrays with identical
007 * elements of identical types will hash identically. Arrays with identical numerical
008 * values but different types will hash differently. There are faster hashes out there,
009 * but many of them are intended to run on very modern desktop processors (not, say,
010 * Android phone processors, and they don't need to worry about uncertain performance
011 * on GWT regarding 64-bit math). We probably don't need to hash arrays or Strings so
012 * often that this (still very high-performance!) hash would be a bottleneck.
013 * <br>
014 * Note: This class was formerly called StableHash, but since that refers to a specific
015 * category of hashing algorithm that this is not, and since the goal is to be cross-
016 * platform, the name was changed to CrossHash.
017 * Created by Tommy Ettinger on 1/16/2016.
018 * @author Glenn Fowler
019 * @author Phong Vo
020 * @author Landon Curt Noll
021 * @author Tommy Ettinger
022 */
023public class CrossHash {
024    public static int hash(boolean[] data)
025    {
026        if(data == null)
027            return 0;
028        int h = -2128831035, len = data.length, o = 0;
029        for (int i = 0; i < len; i++) {
030            o |= (data[i]) ? (1 << (i % 8)) : 0;
031            if(i % 8 == 7 || i == len - 1) {
032                h ^= o;
033                h *= 16777619;
034                o = 0;
035            }
036        }
037        return h;
038    }
039    public static int hash(byte[] data)
040    {
041        if(data == null)
042            return 0;
043        int h = -2128831035, len = data.length;
044        for (int i = 0; i < len; i++) {
045            h ^= data[i];
046            h *= 16777619;
047        }
048        return h;
049    }
050    public static int hash(char[] data)
051    {
052        if(data == null)
053            return 0;
054        int h = -2128831035, len = data.length;
055        for (int i = 0; i < len; i++) {
056            h ^= data[i] & 0xff;
057            h *= 16777619;
058            h ^= data[i] >>> 8;
059            h *= 16777619;
060        }
061        return h;
062    }
063    public static int hash(short[] data)
064    {
065        if(data == null)
066            return 0;
067        int h = -2128831035, len = data.length;
068        for (int i = 0; i < len; i++) {
069            h ^= data[i] & 0xff;
070            h *= 16777619;
071            h ^= data[i] >>> 8;
072            h *= 16777619;
073        }
074        return h;
075    }
076    public static int hash(int[] data)
077    {
078        if(data == null)
079            return 0;
080        int h = -2128831035, len = data.length;
081        for (int i = 0; i < len; i++) {
082            h ^= data[i] & 0xff;
083            h *= 16777619;
084            h ^= (data[i] >>> 8) & 0xff;
085            h *= 16777619;
086            h ^= (data[i] >>> 16) & 0xff;
087            h *= 16777619;
088            h ^= data[i] >>> 24;
089            h *= 16777619;
090        }
091        return h;
092    }
093    public static int hash(long[] data)
094    {
095        if(data == null)
096            return 0;
097        int h = -2128831035, len = data.length;
098        for (int i = 0; i < len; i++) {
099            h ^= (int)(data[i] & 0xff);
100            h *= 16777619;
101            h ^= (int)((data[i] >>> 8) & 0xff);
102            h *= 16777619;
103            h ^= (int)((data[i] >>> 16) & 0xff);
104            h *= 16777619;
105            h ^= (int)((data[i] >>> 24) & 0xff);
106            h *= 16777619;
107            h ^= (int)((data[i] >>> 32) & 0xff);
108            h *= 16777619;
109            h ^= (int)((data[i] >>> 40) & 0xff);
110            h *= 16777619;
111            h ^= (int)((data[i] >>> 48) & 0xff);
112            h *= 16777619;
113            h ^= (int)(data[i] >>> 56);
114            h *= 16777619;
115        }
116        return h;
117    }
118
119    public static int hash(float[] data)
120    {
121        if(data == null)
122            return 0;
123        int h = -2128831035, len = data.length, t;
124        for (int i = 0; i < len; i++) {
125            t = Float.floatToIntBits(data[i]);
126            h ^= t & 0xff;
127            h *= 16777619;
128            h ^= (t >>> 8) & 0xff;
129            h *= 16777619;
130            h ^= (t >>> 16) & 0xff;
131            h *= 16777619;
132            h ^= t >>> 24;
133            h *= 16777619;
134        }
135        return h;
136    }
137    public static int hash(double[] data)
138    {
139        if(data == null)
140            return 0;
141        int h = -2128831035, len = data.length;
142        long t;
143        for (int i = 0; i < len; i++) {
144            t = Double.doubleToLongBits(data[i]);
145            h ^= (int)(t & 0xff);
146            h *= 16777619;
147            h ^= (int)((t >>> 8) & 0xff);
148            h *= 16777619;
149            h ^= (int)((t >>> 16) & 0xff);
150            h *= 16777619;
151            h ^= (int)((t >>> 24) & 0xff);
152            h *= 16777619;
153            h ^= (int)((t >>> 32) & 0xff);
154            h *= 16777619;
155            h ^= (int)((t >>> 40) & 0xff);
156            h *= 16777619;
157            h ^= (int)((t >>> 48) & 0xff);
158            h *= 16777619;
159            h ^= (int)(t >>> 56);
160            h *= 16777619;
161        }
162        return h;
163    }
164    public static int hash(String s)
165    {
166        if(s == null)
167            return 0;
168        return hash(s.toCharArray());
169    }
170
171    public static int hash(String[] data)
172    {
173        if(data == null)
174            return 0;
175        int h = -2128831035, len = data.length, t;
176        for (int i = 0; i < len; i++) {
177            t = hash(data[i]);
178            h ^= t & 0xff;
179            h *= 16777619;
180            h ^= (t >>> 8) & 0xff;
181            h *= 16777619;
182            h ^= (t >>> 16) & 0xff;
183            h *= 16777619;
184            h ^= t >>> 24;
185            h *= 16777619;
186        }
187        return h;
188    }
189
190    public static int hash(String[]... data)
191    {
192        if(data == null)
193            return 0;
194        int h = -2128831035, len = data.length, t;
195        for (int i = 0; i < len; i++) {
196            t = hash(data[i]);
197            h ^= t & 0xff;
198            h *= 16777619;
199            h ^= (t >>> 8) & 0xff;
200            h *= 16777619;
201            h ^= (t >>> 16) & 0xff;
202            h *= 16777619;
203            h ^= t >>> 24;
204            h *= 16777619;
205        }
206        return h;
207    }
208    public static long hash64(boolean[] data)
209    {
210        if(data == null)
211            return 0;
212        long h = -3750763034362895579L, len = data.length, o = 0;
213        for (int i = 0; i < len; i++) {
214            o |= (data[i]) ? (1 << (i % 8)) : 0;
215            if(i % 8 == 7 || i == len - 1) {
216                h ^= o;
217                h *= 1099511628211L;
218                o = 0;
219            }
220        }
221        return h;
222    }
223    public static long hash64(byte[] data)
224    {
225        if(data == null)
226            return 0;
227        long h = -3750763034362895579L, len = data.length;
228        for (int i = 0; i < len; i++) {
229            h ^= data[i];
230            h *= 1099511628211L;
231        }
232        return h;
233    }
234    public static long hash64(char[] data)
235    {
236        if(data == null)
237            return 0;
238        long h = -3750763034362895579L, len = data.length;
239        for (int i = 0; i < len; i++) {
240            h ^= data[i] & 0xff;
241            h *= 1099511628211L;
242            h ^= data[i] >>> 8;
243            h *= 1099511628211L;
244        }
245        return h;
246    }
247    public static long hash64(short[] data)
248    {
249        if(data == null)
250            return 0;
251        long h = -3750763034362895579L, len = data.length;
252        for (int i = 0; i < len; i++) {
253            h ^= data[i] & 0xff;
254            h *= 1099511628211L;
255            h ^= data[i] >>> 8;
256            h *= 1099511628211L;
257        }
258        return h;
259    }
260    public static long hash64(int[] data)
261    {
262        if(data == null)
263            return 0;
264        long h = -3750763034362895579L, len = data.length;
265        for (int i = 0; i < len; i++) {
266            h ^= data[i] & 0xff;
267            h *= 1099511628211L;
268            h ^= (data[i] >>> 8) & 0xff;
269            h *= 1099511628211L;
270            h ^= (data[i] >>> 16) & 0xff;
271            h *= 1099511628211L;
272            h ^= data[i] >>> 24;
273            h *= 1099511628211L;
274        }
275        return h;
276    }
277    public static long hash64(long[] data)
278    {
279        if(data == null)
280            return 0;
281        long h = -3750763034362895579L, len = data.length;
282        for (int i = 0; i < len; i++) {
283            h ^= (data[i] & 0xff);
284            h *= 1099511628211L;
285            h ^= ((data[i] >>> 8) & 0xff);
286            h *= 1099511628211L;
287            h ^= ((data[i] >>> 16) & 0xff);
288            h *= 1099511628211L;
289            h ^= ((data[i] >>> 24) & 0xff);
290            h *= 1099511628211L;
291            h ^= ((data[i] >>> 32) & 0xff);
292            h *= 1099511628211L;
293            h ^= ((data[i] >>> 40) & 0xff);
294            h *= 1099511628211L;
295            h ^= ((data[i] >>> 48) & 0xff);
296            h *= 1099511628211L;
297            h ^= (data[i] >>> 56);
298            h *= 1099511628211L;
299        }
300        return h;
301    }
302    public static long hash64(float[] data)
303    {
304        if(data == null)
305            return 0;
306        long h = -3750763034362895579L, len = data.length, t;
307        for (int i = 0; i < len; i++) {
308            t = Float.floatToIntBits(data[i]);
309            h ^= t & 0xff;
310            h *= 1099511628211L;
311            h ^= (t >>> 8) & 0xff;
312            h *= 1099511628211L;
313            h ^= (t >>> 16) & 0xff;
314            h *= 1099511628211L;
315            h ^= t >>> 24;
316            h *= 1099511628211L;
317        }
318        return h;
319    }
320    public static long hash64(double[] data)
321    {
322        if(data == null)
323            return 0;
324        long h = -3750763034362895579L, len = data.length, t;
325        for (int i = 0; i < len; i++) {
326            t = Double.doubleToLongBits(data[i]);
327            h ^= (t & 0xff);
328            h *= 1099511628211L;
329            h ^= ((t >>> 8) & 0xff);
330            h *= 1099511628211L;
331            h ^= ((t >>> 16) & 0xff);
332            h *= 1099511628211L;
333            h ^= ((t >>> 24) & 0xff);
334            h *= 1099511628211L;
335            h ^= ((t >>> 32) & 0xff);
336            h *= 1099511628211L;
337            h ^= ((t >>> 40) & 0xff);
338            h *= 1099511628211L;
339            h ^= ((t >>> 48) & 0xff);
340            h *= 1099511628211L;
341            h ^= (t >>> 56);
342            h *= 1099511628211L;
343        }
344        return h;
345    }
346    public static long hash64(String s)
347    {
348        if(s == null)
349            return 0;
350        return hash64(s.toCharArray());
351    }
352    public static long hash64(String[] data)
353    {
354        if(data == null)
355            return 0;
356        long h = -3750763034362895579L, len = data.length, t;
357        for (int i = 0; i < len; i++) {
358            t = hash64(data[i]);
359            h ^= (t & 0xff);
360            h *= 1099511628211L;
361            h ^= ((t >>> 8) & 0xff);
362            h *= 1099511628211L;
363            h ^= ((t >>> 16) & 0xff);
364            h *= 1099511628211L;
365            h ^= ((t >>> 24) & 0xff);
366            h *= 1099511628211L;
367            h ^= ((t >>> 32) & 0xff);
368            h *= 1099511628211L;
369            h ^= ((t >>> 40) & 0xff);
370            h *= 1099511628211L;
371            h ^= ((t >>> 48) & 0xff);
372            h *= 1099511628211L;
373            h ^= (t >>> 56);
374            h *= 1099511628211L;
375        }
376        return h;
377    }
378    public static long hash64(Iterable<String> data)
379    {
380        if(data == null)
381            return 0;
382        long h = -3750763034362895579L, t;
383        for (String datum : data) {
384            t = hash64(datum);
385            h ^= (t & 0xff);
386            h *= 1099511628211L;
387            h ^= ((t >>> 8) & 0xff);
388            h *= 1099511628211L;
389            h ^= ((t >>> 16) & 0xff);
390            h *= 1099511628211L;
391            h ^= ((t >>> 24) & 0xff);
392            h *= 1099511628211L;
393            h ^= ((t >>> 32) & 0xff);
394            h *= 1099511628211L;
395            h ^= ((t >>> 40) & 0xff);
396            h *= 1099511628211L;
397            h ^= ((t >>> 48) & 0xff);
398            h *= 1099511628211L;
399            h ^= (t >>> 56);
400            h *= 1099511628211L;
401        }
402        return h;
403    }
404    public static long hash64(String[]... data)
405    {
406        if(data == null)
407            return 0;
408        long h = -3750763034362895579L, len = data.length, t;
409        for (int i = 0; i < len; i++) {
410            t = hash64(data[i]);
411            h ^= (t & 0xff);
412            h *= 1099511628211L;
413            h ^= ((t >>> 8) & 0xff);
414            h *= 1099511628211L;
415            h ^= ((t >>> 16) & 0xff);
416            h *= 1099511628211L;
417            h ^= ((t >>> 24) & 0xff);
418            h *= 1099511628211L;
419            h ^= ((t >>> 32) & 0xff);
420            h *= 1099511628211L;
421            h ^= ((t >>> 40) & 0xff);
422            h *= 1099511628211L;
423            h ^= ((t >>> 48) & 0xff);
424            h *= 1099511628211L;
425            h ^= (t >>> 56);
426            h *= 1099511628211L;
427        }
428        return h;
429    }
430
431    /**
432     * Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
433     * @param data the char array to hash
434     * @param start the start of the section to hash (inclusive)
435     * @param end the end of the section to hash (exclusive)
436     * @return
437     */
438    public static long hash64(char[] data, int start, int end)
439    {
440        if(data == null)
441            return 0;
442        long h = -3750763034362895579L, len = data.length;
443        start %= len;
444        end %= len;
445        if(end <= start || start < 0 || end <= 0)
446            return 0;
447        for (int i = start; i < end; i++) {
448            h ^= data[i] & 0xff;
449            h *= 1099511628211L;
450            h ^= data[i] >>> 8;
451            h *= 1099511628211L;
452        }
453        return h;
454    }
455}