src/main/gov/nasa/jpf/util/OATHash.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 package gov.nasa.jpf.util;
  20
  21 /**
  22  * Bob Jenkins One-at-a-Time Hash (http://www.burtleburtle.net/bob/hash/doobs.html),
  23  * a simple yet sufficiently avalanching hash that doesn't require a-priori knowledge
  24  * of the key length and is much faster than lookup3
  25  */
  26 public class OATHash {
  27
  28   //--- the hash primitives
  29
  30   public static int hashMixin (int h, int key){
  31     int k = key & 0xff;
  32     h += k; h += (h <<10); h ^= (h >>> 6);
  33
  34     key >>= 8;
  35     k = key & 0xff;
  36     h += k; h += (h <<10); h ^= (h >>> 6);
  37
  38     key >>= 8;
  39     k = key & 0xff;
  40     h += k; h += (h <<10); h ^= (h >>> 6);
  41
  42     key >>= 8;
  43     k = key & 0xff;
  44     h += k; h += (h <<10); h ^= (h >>> 6);
  45
  46     return h;
  47   }
  48
  49   public static int hashMixin (int h, long key) {
  50     h = hashMixin( h, (int)key);
  51     h = hashMixin( h, (int)(key >> 32));
  52     return h;
  53   }
  54
  55   public static int hashFinalize (int h){
  56     h += (h << 3);
  57     h ^= (h >>> 11);
  58     h += (h << 15);
  59
  60     return h;
  61   }
  62
  63   //--- the one step public hashers
  64
  65   public static int hash (int key){
  66     return hashFinalize( hashMixin(0,key));
  67   }
  68
  69   public static int hash (int key1, int key2){
  70     int h = hashMixin(0,key1);
  71     h = hashMixin(h, key2);
  72     return hashFinalize(h);
  73   }
  74
  75   public static int hash (long key) {
  76     int h = hashMixin(0, (int)key);
  77     h = hashMixin( h, (int)(key>>32));
  78     return hashFinalize(h);
  79   }
  80
  81   public static int hash (int key1, int key2, int key3) {
  82     int h = hashMixin( 0, key1);
  83     h = hashMixin( h, key2);
  84     h = hashMixin( h, key3);
  85
  86     return hashFinalize(h);
  87   }
  88
  89   public static int hash (int[] keys){
  90     int h = 0;
  91     for (int i=0; i<keys.length; i++){
  92       h = hashMixin( h, keys[i]);
  93     }
  94     return hashFinalize(h);
  95   }
  96 }