OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 // | 4 // |
5 // Defines methods for hashing a pair of integers. | 5 // Defines methods for hashing a pair of integers. |
6 | 6 |
7 #ifndef CC_BASE_HASH_PAIR_H_ | 7 #ifndef CC_BASE_HASH_PAIR_H_ |
8 #define CC_BASE_HASH_PAIR_H_ | 8 #define CC_BASE_HASH_PAIR_H_ |
9 | 9 |
10 #include "base/hash_tables.h" | 10 #include "base/hash_tables.h" |
(...skipping 22 matching lines...) Expand all Loading... |
33 #endif // COMPILER | 33 #endif // COMPILER |
34 | 34 |
35 namespace BASE_HASH_NAMESPACE { | 35 namespace BASE_HASH_NAMESPACE { |
36 | 36 |
37 // Implement hashing for pairs of at-most 32 bit integer values. | 37 // Implement hashing for pairs of at-most 32 bit integer values. |
38 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using | 38 // When size_t is 32 bits, we turn the 64-bit hash code into 32 bits by using |
39 // multiply-add hashing. This algorithm, as described in | 39 // multiply-add hashing. This algorithm, as described in |
40 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in | 40 // Theorem 4.3.3 of the thesis "Über die Komplexität der Multiplikation in |
41 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: | 41 // eingeschränkten Branchingprogrammmodellen" by Woelfel, is: |
42 // | 42 // |
43 // h32(x32, y32) = (h64(x32, y32) * randOdd64 + rand16 * 2^16) % 2^64 / 2^32 | 43 // h32(x32, y32) = (h64(x32, y32) * rand_odd64 + rand16 * 2^16) % 2^64 / 2^32 |
44 | 44 |
45 #define DEFINE_32BIT_PAIR_HASH(type1, type2) \ | 45 #define DEFINE_32BIT_PAIR_HASH(type1, type2) \ |
46 DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \ | 46 DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \ |
47 uint64 first = value.first; \ | 47 uint64 first = value.first; \ |
48 uint32 second = value.second; \ | 48 uint32 second = value.second; \ |
49 uint64 hash64 = (first << 32) | second; \ | 49 uint64 hash64 = (first << 32) | second; \ |
50 \ | 50 \ |
51 if (sizeof(std::size_t) >= sizeof(uint64)) \ | 51 if (sizeof(std::size_t) >= sizeof(uint64)) \ |
52 return static_cast<std::size_t>(hash64); \ | 52 return static_cast<std::size_t>(hash64); \ |
53 \ | 53 \ |
54 uint64 oddRandom = 481046412LL << 32 | 1025306954LL; \ | 54 uint64 odd_random = 481046412LL << 32 | 1025306954LL; \ |
55 uint32 shiftRandom = 10121U << 16; \ | 55 uint32 shift_random = 10121U << 16; \ |
56 \ | 56 \ |
57 hash64 = hash64 * oddRandom + shiftRandom; \ | 57 hash64 = hash64 * odd_random + shift_random; \ |
58 std::size_t highBits = static_cast<std::size_t>( \ | 58 std::size_t high_bits = static_cast<std::size_t>( \ |
59 hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \ | 59 hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \ |
60 return highBits; \ | 60 return high_bits; \ |
61 } \ | 61 } \ |
62 DEFINE_PAIR_HASH_FUNCTION_END(); | 62 DEFINE_PAIR_HASH_FUNCTION_END(); |
63 | 63 |
64 DEFINE_32BIT_PAIR_HASH(short, short); | 64 DEFINE_32BIT_PAIR_HASH(short, short); |
65 DEFINE_32BIT_PAIR_HASH(short, unsigned short); | 65 DEFINE_32BIT_PAIR_HASH(short, unsigned short); |
66 DEFINE_32BIT_PAIR_HASH(short, int); | 66 DEFINE_32BIT_PAIR_HASH(short, int); |
67 DEFINE_32BIT_PAIR_HASH(short, unsigned); | 67 DEFINE_32BIT_PAIR_HASH(short, unsigned); |
68 DEFINE_32BIT_PAIR_HASH(unsigned short, short); | 68 DEFINE_32BIT_PAIR_HASH(unsigned short, short); |
69 DEFINE_32BIT_PAIR_HASH(unsigned short, unsigned short); | 69 DEFINE_32BIT_PAIR_HASH(unsigned short, unsigned short); |
70 DEFINE_32BIT_PAIR_HASH(unsigned short, int); | 70 DEFINE_32BIT_PAIR_HASH(unsigned short, int); |
(...skipping 10 matching lines...) Expand all Loading... |
81 #undef DEFINE_32BIT_PAIR_HASH | 81 #undef DEFINE_32BIT_PAIR_HASH |
82 | 82 |
83 // Implement hashing for pairs of up-to 64-bit integer values. | 83 // Implement hashing for pairs of up-to 64-bit integer values. |
84 // We use the compound integer hash method to produce a 64-bit hash code, by | 84 // We use the compound integer hash method to produce a 64-bit hash code, by |
85 // breaking the two 64-bit inputs into 4 32-bit values: | 85 // breaking the two 64-bit inputs into 4 32-bit values: |
86 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 | 86 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 |
87 // Then we reduce our result to 32 bits if required, similar to above. | 87 // Then we reduce our result to 32 bits if required, similar to above. |
88 | 88 |
89 #define DEFINE_64BIT_PAIR_HASH(type1, type2) \ | 89 #define DEFINE_64BIT_PAIR_HASH(type1, type2) \ |
90 DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \ | 90 DEFINE_PAIR_HASH_FUNCTION_START(type1, type2) { \ |
91 uint32 shortRandom1 = 842304669U; \ | 91 uint32 short_random1 = 842304669U; \ |
92 uint32 shortRandom2 = 619063811U; \ | 92 uint32 short_random2 = 619063811U; \ |
93 uint32 shortRandom3 = 937041849U; \ | 93 uint32 short_random3 = 937041849U; \ |
94 uint32 shortRandom4 = 3309708029U; \ | 94 uint32 short_random4 = 3309708029U; \ |
95 \ | 95 \ |
96 uint64 value1 = value.first; \ | 96 uint64 value1 = value.first; \ |
97 uint64 value2 = value.second; \ | 97 uint64 value2 = value.second; \ |
98 uint32 value1a = static_cast<uint32>(value1 & 0xffffffff); \ | 98 uint32 value1a = static_cast<uint32>(value1 & 0xffffffff); \ |
99 uint32 value1b = static_cast<uint32>((value1 >> 32) & 0xffffffff); \ | 99 uint32 value1b = static_cast<uint32>((value1 >> 32) & 0xffffffff); \ |
100 uint32 value2a = static_cast<uint32>(value2 & 0xffffffff); \ | 100 uint32 value2a = static_cast<uint32>(value2 & 0xffffffff); \ |
101 uint32 value2b = static_cast<uint32>((value2 >> 32) & 0xffffffff); \ | 101 uint32 value2b = static_cast<uint32>((value2 >> 32) & 0xffffffff); \ |
102 \ | 102 \ |
103 uint64 product1 = static_cast<uint64>(value1a) * shortRandom1; \ | 103 uint64 product1 = static_cast<uint64>(value1a) * short_random1; \ |
104 uint64 product2 = static_cast<uint64>(value1b) * shortRandom2; \ | 104 uint64 product2 = static_cast<uint64>(value1b) * short_random2; \ |
105 uint64 product3 = static_cast<uint64>(value2a) * shortRandom3; \ | 105 uint64 product3 = static_cast<uint64>(value2a) * short_random3; \ |
106 uint64 product4 = static_cast<uint64>(value2b) * shortRandom4; \ | 106 uint64 product4 = static_cast<uint64>(value2b) * short_random4; \ |
107 \ | 107 \ |
108 uint64 hash64 = product1 + product2 + product3 + product4; \ | 108 uint64 hash64 = product1 + product2 + product3 + product4; \ |
109 \ | 109 \ |
110 if (sizeof(std::size_t) >= sizeof(uint64)) \ | 110 if (sizeof(std::size_t) >= sizeof(uint64)) \ |
111 return static_cast<std::size_t>(hash64); \ | 111 return static_cast<std::size_t>(hash64); \ |
112 \ | 112 \ |
113 uint64 oddRandom = 1578233944LL << 32 | 194370989LL; \ | 113 uint64 odd_random = 1578233944LL << 32 | 194370989LL; \ |
114 uint32 shiftRandom = 20591U << 16; \ | 114 uint32 shift_random = 20591U << 16; \ |
115 \ | 115 \ |
116 hash64 = hash64 * oddRandom + shiftRandom; \ | 116 hash64 = hash64 * odd_random + shift_random; \ |
117 std::size_t highBits = static_cast<std::size_t>( \ | 117 std::size_t high_bits = static_cast<std::size_t>( \ |
118 hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \ | 118 hash64 >> (sizeof(uint64) - sizeof(std::size_t))); \ |
119 return highBits; \ | 119 return high_bits; \ |
120 } \ | 120 } \ |
121 DEFINE_PAIR_HASH_FUNCTION_END(); | 121 DEFINE_PAIR_HASH_FUNCTION_END(); |
122 | 122 |
123 DEFINE_64BIT_PAIR_HASH(short, int64); | 123 DEFINE_64BIT_PAIR_HASH(short, int64); |
124 DEFINE_64BIT_PAIR_HASH(short, uint64); | 124 DEFINE_64BIT_PAIR_HASH(short, uint64); |
125 DEFINE_64BIT_PAIR_HASH(unsigned short, int64); | 125 DEFINE_64BIT_PAIR_HASH(unsigned short, int64); |
126 DEFINE_64BIT_PAIR_HASH(unsigned short, uint64); | 126 DEFINE_64BIT_PAIR_HASH(unsigned short, uint64); |
127 DEFINE_64BIT_PAIR_HASH(int, int64); | 127 DEFINE_64BIT_PAIR_HASH(int, int64); |
128 DEFINE_64BIT_PAIR_HASH(int, uint64); | 128 DEFINE_64BIT_PAIR_HASH(int, uint64); |
129 DEFINE_64BIT_PAIR_HASH(unsigned, int64); | 129 DEFINE_64BIT_PAIR_HASH(unsigned, int64); |
(...skipping 11 matching lines...) Expand all Loading... |
141 DEFINE_64BIT_PAIR_HASH(uint64, int64); | 141 DEFINE_64BIT_PAIR_HASH(uint64, int64); |
142 DEFINE_64BIT_PAIR_HASH(uint64, uint64); | 142 DEFINE_64BIT_PAIR_HASH(uint64, uint64); |
143 | 143 |
144 #undef DEFINE_64BIT_PAIR_HASH | 144 #undef DEFINE_64BIT_PAIR_HASH |
145 } | 145 } |
146 | 146 |
147 #undef DEFINE_PAIR_HASH_FUNCTION_START | 147 #undef DEFINE_PAIR_HASH_FUNCTION_START |
148 #undef DEFINE_PAIR_HASH_FUNCTION_END | 148 #undef DEFINE_PAIR_HASH_FUNCTION_END |
149 | 149 |
150 #endif // CC_BASE_HASH_PAIR_H_ | 150 #endif // CC_BASE_HASH_PAIR_H_ |
OLD | NEW |