win32: use #ifdef _WIN32
[olsrd.git] / src / hashing.c
index c5eccd6..a283c72 100644 (file)
@@ -1,33 +1,34 @@
+
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
- * Copyright (c) 2004, Andreas TΓΈnnesen(andreto@olsr.org)
+ * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
  * All rights reserved.
  *
- * Redistribution and use in source and binary forms, with or without 
- * modification, are permitted provided that the following conditions 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
  * are met:
  *
- * * Redistributions of source code must retain the above copyright 
+ * * Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright 
- *   notice, this list of conditions and the following disclaimer in 
- *   the documentation and/or other materials provided with the 
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
  *   distribution.
- * * Neither the name of olsr.org, olsrd nor the names of its 
- *   contributors may be used to endorse or promote products derived 
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
  *   from this software without specific prior written permission.
  *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
- * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
- * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
- * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  *
  * Visit http://www.olsr.org for more information.
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: hashing.c,v 1.7 2004/11/21 11:28:56 kattemat Exp $
  */
 
-
 #include "olsr_protocol.h"
 #include "hashing.h"
+#include "defs.h"
+
+/*
+ * Taken from lookup2.c by Bob Jenkins.  (http://burtleburtle.net/bob/c/lookup2.c).
+ * --------------------------------------------------------------------
+ * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
+ * You can use this free for any purpose.  It has no warranty.
+ * --------------------------------------------------------------------
+ */
+
+#define __jhash_mix(a, b, c) \
+{ \
+  a -= b; a -= c; a ^= (c>>13); \
+  b -= c; b -= a; b ^= (a<<8); \
+  c -= a; c -= b; c ^= (b>>13); \
+  a -= b; a -= c; a ^= (c>>12);  \
+  b -= c; b -= a; b ^= (a<<16); \
+  c -= a; c -= b; c ^= (b>>5); \
+  a -= b; a -= c; a ^= (c>>3);  \
+  b -= c; b -= a; b ^= (a<<10); \
+  c -= a; c -= b; c ^= (b>>15); \
+}
+
+static uint32_t
+jenkins_hash(const uint8_t * k, uint32_t length)
+{
+  /* k: the key
+   * length: length of the key
+   * initval: the previous hash, or an arbitrary value
+   */
+  uint32_t a, b, c, len;
+
+  /* Set up the internal state */
+  len = length;
+  a = b = 0x9e3779b9;           /* the golden ratio; an arbitrary value */
+  c = 0;                        /* the previous hash value */
+
+  /* handle most of the key */
+  while (len >= 12) {
+    a += (k[0] + ((uint32_t) k[1] << 8) + ((uint32_t) k[2] << 16) + ((uint32_t) k[3] << 24));
+    b += (k[4] + ((uint32_t) k[5] << 8) + ((uint32_t) k[6] << 16) + ((uint32_t) k[7] << 24));
+    c += (k[8] + ((uint32_t) k[9] << 8) + ((uint32_t) k[10] << 16) + ((uint32_t) k[11] << 24));
 
+    __jhash_mix(a, b, c);
+
+    k += 12;
+    len -= 12;
+  }
+
+  c += length;
+  switch (len) {
+  case 11:
+    c += ((uint32_t) k[10] << 24);
+    /* no break */
+  case 10:
+    c += ((uint32_t) k[9] << 16);
+    /* no break */
+  case 9:
+    c += ((uint32_t) k[8] << 8);
+    /* the first byte of c is reserved for the length */
+    /* no break */
+  case 8:
+    b += ((uint32_t) k[7] << 24);
+    /* no break */
+  case 7:
+    b += ((uint32_t) k[6] << 16);
+    /* no break */
+  case 6:
+    b += ((uint32_t) k[5] << 8);
+    /* no break */
+  case 5:
+    b += k[4];
+    /* no break */
+  case 4:
+    a += ((uint32_t) k[3] << 24);
+    /* no break */
+  case 3:
+    a += ((uint32_t) k[2] << 16);
+    /* no break */
+  case 2:
+    a += ((uint32_t) k[1] << 8);
+    /* no break */
+  case 1:
+    a += k[0];
+    break;
+
+  default:
+         break;
+  }
+  __jhash_mix(a, b, c);
+
+  return c;
+}
 
 /**
- *Hashing function. Creates a key based on
- *an 32-bit address.
- *@param address the address to hash
- *@return the hash(a value in the 0-31 range)
+ * Hashing function. Creates a key based on an IP address.
+ * @param address the address to hash
+ * @return the hash(a value in the (0 to HASHMASK-1) range)
  */
-olsr_u32_t
-olsr_hashing(union olsr_ip_addr *address)
+uint32_t
+olsr_ip_hashing(const union olsr_ip_addr * address)
 {
-  olsr_u32_t hash;
-  char *tmp;
-
-  if(olsr_cnf->ip_version == AF_INET)
-    /* IPv4 */  
-    hash = (ntohl(address->v4));
-  else
-    {
-      /* IPv6 */
-      tmp = (char *) &address->v6;
-      hash = (ntohl(*tmp));
-    }
-
-  /* REMOVE */
-#ifdef DEBUG
-#warning Remove debug output in hash.c
-  olsr_printf(1, "HASH %s->%d:", olsr_ip_to_string(address), hash);
-#endif
-
-  //hash &= 0x7fffffff; 
-  hash &= HASHMASK;
-
-#ifdef DEBUG
-  olsr_printf(1, "%d\n", hash);
-#endif
-
-
-  return hash;
+  uint32_t hash;
+
+  switch (olsr_cnf->ip_version) {
+  case AF_INET:
+    hash = jenkins_hash((const uint8_t *)&address->v4, sizeof(uint32_t));
+    break;
+  case AF_INET6:
+    hash = jenkins_hash((const uint8_t *)&address->v6, sizeof(struct in6_addr));
+    break;
+  default:
+    hash = 0;
+    break;
+
+  }
+  return hash & HASHMASK;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * indent-tabs-mode: nil
+ * End:
+ */