info: java: update workspace
[olsrd.git] / src / hashing.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon (olsrd)
3  *
4  * (c) by the OLSR project
5  *
6  * See our Git repository to find out who worked on this file
7  * and thus is a copyright holder on it.
8  *
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * * Redistributions of source code must retain the above copyright
16  *   notice, this list of conditions and the following disclaimer.
17  * * Redistributions in binary form must reproduce the above copyright
18  *   notice, this list of conditions and the following disclaimer in
19  *   the documentation and/or other materials provided with the
20  *   distribution.
21  * * Neither the name of olsr.org, olsrd nor the names of its
22  *   contributors may be used to endorse or promote products derived
23  *   from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36  * POSSIBILITY OF SUCH DAMAGE.
37  *
38  * Visit http://www.olsr.org for more information.
39  *
40  * If you find this software useful feel free to make a donation
41  * to the project. For more information see the website or contact
42  * the copyright holders.
43  *
44  */
45
46 #include "olsr_protocol.h"
47 #include "hashing.h"
48 #include "defs.h"
49
50 /*
51  * Taken from lookup2.c by Bob Jenkins.  (http://burtleburtle.net/bob/c/lookup2.c).
52  * --------------------------------------------------------------------
53  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
54  * You can use this free for any purpose.  It has no warranty.
55  * --------------------------------------------------------------------
56  */
57
58 #define __jhash_mix(a, b, c) \
59 { \
60   a -= b; a -= c; a ^= (c>>13); \
61   b -= c; b -= a; b ^= (a<<8); \
62   c -= a; c -= b; c ^= (b>>13); \
63   a -= b; a -= c; a ^= (c>>12);  \
64   b -= c; b -= a; b ^= (a<<16); \
65   c -= a; c -= b; c ^= (b>>5); \
66   a -= b; a -= c; a ^= (c>>3);  \
67   b -= c; b -= a; b ^= (a<<10); \
68   c -= a; c -= b; c ^= (b>>15); \
69 }
70
71 static uint32_t
72 jenkins_hash(const uint8_t * k, uint32_t length)
73 {
74   /* k: the key
75    * length: length of the key
76    * initval: the previous hash, or an arbitrary value
77    */
78   uint32_t a, b, c, len;
79
80   /* Set up the internal state */
81   len = length;
82   a = b = 0x9e3779b9;           /* the golden ratio; an arbitrary value */
83   c = 0;                        /* the previous hash value */
84
85   /* handle most of the key */
86   while (len >= 12) {
87     a += (k[0] + ((uint32_t) k[1] << 8) + ((uint32_t) k[2] << 16) + ((uint32_t) k[3] << 24));
88     b += (k[4] + ((uint32_t) k[5] << 8) + ((uint32_t) k[6] << 16) + ((uint32_t) k[7] << 24));
89     c += (k[8] + ((uint32_t) k[9] << 8) + ((uint32_t) k[10] << 16) + ((uint32_t) k[11] << 24));
90
91     __jhash_mix(a, b, c);
92
93     k += 12;
94     len -= 12;
95   }
96
97   c += length;
98   switch (len) {
99   case 11:
100     c += ((uint32_t) k[10] << 24);
101     /* no break */
102     // fallthrough
103   case 10:
104     c += ((uint32_t) k[9] << 16);
105     /* no break */
106     // fallthrough
107   case 9:
108     c += ((uint32_t) k[8] << 8);
109     /* the first byte of c is reserved for the length */
110     /* no break */
111     // fallthrough
112   case 8:
113     b += ((uint32_t) k[7] << 24);
114     /* no break */
115     // fallthrough
116   case 7:
117     b += ((uint32_t) k[6] << 16);
118     /* no break */
119     // fallthrough
120   case 6:
121     b += ((uint32_t) k[5] << 8);
122     /* no break */
123     // fallthrough
124   case 5:
125     b += k[4];
126     /* no break */
127     // fallthrough
128   case 4:
129     a += ((uint32_t) k[3] << 24);
130     /* no break */
131     // fallthrough
132   case 3:
133     a += ((uint32_t) k[2] << 16);
134     /* no break */
135     // fallthrough
136   case 2:
137     a += ((uint32_t) k[1] << 8);
138     /* no break */
139     // fallthrough
140   case 1:
141     a += k[0];
142     break;
143
144   default:
145           break;
146   }
147   __jhash_mix(a, b, c);
148
149   return c;
150 }
151
152 /**
153  * Hashing function. Creates a key based on an IP address.
154  * @param address the address to hash
155  * @return the hash(a value in the (0 to HASHMASK-1) range)
156  */
157 uint32_t
158 olsr_ip_hashing(const union olsr_ip_addr * address)
159 {
160   uint32_t hash;
161
162   switch (olsr_cnf->ip_version) {
163   case AF_INET:
164     hash = jenkins_hash((const uint8_t *)&address->v4, sizeof(uint32_t));
165     break;
166   case AF_INET6:
167     hash = jenkins_hash((const uint8_t *)&address->v6, sizeof(struct in6_addr));
168     break;
169   default:
170     hash = 0;
171     break;
172
173   }
174   return hash & HASHMASK;
175 }
176
177 /*
178  * Local Variables:
179  * c-basic-offset: 2
180  * indent-tabs-mode: nil
181  * End:
182  */