Branch data Line data Source code
1 : : // Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : /*! \file
16 : : * Some parts of this code were copied from BIND-9, which in turn was derived
17 : : * from universal hash function libraries of Rice University.
18 : :
19 : : \section license UH Universal Hashing Library
20 : :
21 : : Copyright ((c)) 2002, Rice University
22 : : All rights reserved.
23 : :
24 : : Redistribution and use in source and binary forms, with or without
25 : : modification, are permitted provided that the following conditions are
26 : : met:
27 : :
28 : : * Redistributions of source code must retain the above copyright
29 : : notice, this list of conditions and the following disclaimer.
30 : :
31 : : * Redistributions in binary form must reproduce the above
32 : : copyright notice, this list of conditions and the following
33 : : disclaimer in the documentation and/or other materials provided
34 : : with the distribution.
35 : :
36 : : * Neither the name of Rice University (RICE) nor the names of its
37 : : contributors may be used to endorse or promote products derived
38 : : from this software without specific prior written permission.
39 : :
40 : :
41 : : This software is provided by RICE and the contributors on an "as is"
42 : : basis, without any representations or warranties of any kind, express
43 : : or implied including, but not limited to, representations or
44 : : warranties of non-infringement, merchantability or fitness for a
45 : : particular purpose. In no event shall RICE or contributors be liable
46 : : for any direct, indirect, incidental, special, exemplary, or
47 : : consequential damages (including, but not limited to, procurement of
48 : : substitute goods or services; loss of use, data, or profits; or
49 : : business interruption) however caused and on any theory of liability,
50 : : whether in contract, strict liability, or tort (including negligence
51 : : or otherwise) arising in any way out of the use of this software, even
52 : : if advised of the possibility of such damage.
53 : : */
54 : :
55 : : #include <cassert>
56 : : #include <stdlib.h>
57 : : #include <algorithm>
58 : : #include <cassert>
59 : : #include <string>
60 : :
61 : : #include <config.h>
62 : :
63 : : #include "hash.h"
64 : :
65 : : using namespace std;
66 : :
67 : : namespace isc {
68 : : namespace nsas {
69 : :
70 : : // Constructor.
71 : :
72 : 233 : Hash::Hash(uint32_t tablesize, uint32_t maxkeylen, bool randomise) :
73 : : tablesize_(tablesize), maxkeylen_(min<uint32_t>(maxkeylen,
74 : 699 : (255 - sizeof(uint16_t))))
75 : : {
76 : : // (Code taken from BIND-9)
77 : : //
78 : : // Check to see that we can cope with the maximum key length which, due
79 : : // to the limitations, should not be more than 255 in total. The actual
80 : : // number of characters in the name that are considered is reduced to
81 : : // ensure that the class is taken into account in the hash. (This accounts
82 : : // for the "+ sizeof(uint16_t)" in the calculations below.
83 : : //
84 : : // Overflow check. Since our implementation only does a modulo
85 : : // operation at the last stage of hash calculation, the accumulator
86 : : // must not overflow.
87 : : hash_accum_t overflow_limit =
88 : 233 : 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
89 [ - + ]: 233 : if (overflow_limit < (maxkeylen_ + sizeof(uint16_t) + 1) * 0xff) {
90 [ # # ][ # # ]: 0 : isc_throw(KeyLengthTooLong, "Hash key length too long for Hash class");
91 : : }
92 : :
93 : : // Initialize the random number generator with the current time.
94 : : // TODO: Use something other than pseudo-random numbers.
95 : : union {
96 : : unsigned int seed;
97 : : time_t curtime;
98 : : } init_value;
99 : :
100 [ + + ]: 233 : if (randomise) {
101 : 230 : init_value.curtime = time(NULL);
102 : : } else {
103 : 3 : init_value.seed = 1;
104 : : }
105 : 233 : srandom(init_value.seed);
106 : :
107 : : // Fill in the random vector.
108 [ + - ]: 233 : randvec_.reserve(maxkeylen_ + sizeof(uint16_t) + 1);
109 [ + + ]: 60119 : for (uint32_t i = 0; i < (maxkeylen + sizeof(uint16_t) + 1); ++i) {
110 : 59886 : randvec_.push_back(static_cast<hash_random_t>(random() & 0xffff));
111 : : }
112 : : assert(sizeof(hash_random_t) == 2); // So that the "& 0xffff" is valid
113 : :
114 : : // Finally, initialize the mapping table for uppercase to lowercase
115 : : // characters. A table is used as indexing a table is faster than calling
116 : : // the tolower() function.
117 : 233 : casemap_.reserve(256);
118 [ + + ]: 59881 : for (int i = 0; i < 256; ++i) {
119 : 59648 : casemap_.push_back(i);
120 : : }
121 [ + + ]: 6291 : for (int i = 'A'; i <= 'Z'; ++i) {
122 : 12116 : casemap_[i] += ('a' - 'A');
123 : : }
124 : 233 : }
125 : :
126 : :
127 : 2856 : uint32_t Hash::operator()(const HashKey& key, bool ignorecase) const
128 : : {
129 : : // Calculation as given in BIND-9.
130 : 2856 : hash_accum_t partial_sum = 0;
131 : 2856 : uint32_t i = 0; // Used after the end of the loop
132 : :
133 : : // Perform the hashing. If the key length if more than the maximum we set
134 : : // up this hash for, ignore the excess.
135 [ + + ]: 2856 : if (ignorecase) {
136 [ + + ]: 77506 : for (i = 0; i < min(key.keylen, maxkeylen_); ++i) {
137 : 37326 : partial_sum += mapLower(key.key[i]) * randvec_[i];
138 : : }
139 : : } else {
140 [ + + ]: 38 : for (i = 0; i < min(key.keylen, maxkeylen_); ++i) {
141 : 72 : partial_sum += key.key[i] * randvec_[i];
142 : : }
143 : : }
144 : :
145 : : // Add the hash of the class code
146 : : union {
147 : : uint16_t class_code; // Copy of the class code
148 : : char bytes[sizeof(uint16_t)]; // Byte equivalent
149 : : } convert;
150 : :
151 : 5712 : convert.class_code = key.class_code.getCode();
152 [ + + ]: 8568 : for (int j = 0; j < sizeof(uint16_t); ++j, ++i) {
153 : 11424 : partial_sum += convert.bytes[j] * randvec_[i];
154 : : }
155 : :
156 : : // ... and finish up.
157 : 5712 : partial_sum += randvec_[i];
158 : :
159 : : // Determine the hash value
160 : 2856 : uint32_t value = partial_sum % prime32_;
161 : :
162 : : // ... and round it to fit the table size
163 : 2856 : return (value % tablesize_);
164 : : }
165 : :
166 : : } // namespace nsas
167 : 91632 : } // namespace isc
|
