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