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 #include "net/quic/core/quic_utils.h" | 5 #include "net/quic/core/quic_utils.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <cstdint> | 8 #include <cstdint> |
9 #include <vector> | 9 #include <vector> |
10 | 10 |
11 #include "base/containers/adapters.h" | 11 #include "base/containers/adapters.h" |
12 #include "base/logging.h" | 12 #include "base/logging.h" |
13 #include "net/quic/core/quic_constants.h" | 13 #include "net/quic/core/quic_constants.h" |
14 #include "net/quic/core/quic_flags.h" | 14 #include "net/quic/core/quic_flags.h" |
15 | 15 |
16 using base::StringPiece; | |
17 using std::string; | 16 using std::string; |
18 | 17 |
19 namespace net { | 18 namespace net { |
20 namespace { | 19 namespace { |
21 | 20 |
22 // We know that >= GCC 4.8 and Clang have a __uint128_t intrinsic. Other | 21 // We know that >= GCC 4.8 and Clang have a __uint128_t intrinsic. Other |
23 // compilers don't necessarily, notably MSVC. | 22 // compilers don't necessarily, notably MSVC. |
24 #if defined(__x86_64__) && \ | 23 #if defined(__x86_64__) && \ |
25 ((defined(__GNUC__) && \ | 24 ((defined(__GNUC__) && \ |
26 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))) || \ | 25 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8))) || \ |
27 defined(__clang__)) | 26 defined(__clang__)) |
28 #define QUIC_UTIL_HAS_UINT128 1 | 27 #define QUIC_UTIL_HAS_UINT128 1 |
29 #endif | 28 #endif |
30 | 29 |
31 #ifdef QUIC_UTIL_HAS_UINT128 | 30 #ifdef QUIC_UTIL_HAS_UINT128 |
32 uint128 IncrementalHashFast(uint128 uhash, StringPiece data) { | 31 uint128 IncrementalHashFast(uint128 uhash, QuicStringPiece data) { |
33 // This code ends up faster than the naive implementation for 2 reasons: | 32 // This code ends up faster than the naive implementation for 2 reasons: |
34 // 1. uint128 from base/int128.h is sufficiently complicated that the compiler | 33 // 1. uint128 from base/int128.h is sufficiently complicated that the compiler |
35 // cannot transform the multiplication by kPrime into a shift-multiply-add; | 34 // cannot transform the multiplication by kPrime into a shift-multiply-add; |
36 // it has go through all of the instructions for a 128-bit multiply. | 35 // it has go through all of the instructions for a 128-bit multiply. |
37 // 2. Because there are so fewer instructions (around 13), the hot loop fits | 36 // 2. Because there are so fewer instructions (around 13), the hot loop fits |
38 // nicely in the instruction queue of many Intel CPUs. | 37 // nicely in the instruction queue of many Intel CPUs. |
39 // kPrime = 309485009821345068724781371 | 38 // kPrime = 309485009821345068724781371 |
40 static const __uint128_t kPrime = | 39 static const __uint128_t kPrime = |
41 (static_cast<__uint128_t>(16777216) << 64) + 315; | 40 (static_cast<__uint128_t>(16777216) << 64) + 315; |
42 __uint128_t xhash = (static_cast<__uint128_t>(Uint128High64(uhash)) << 64) + | 41 __uint128_t xhash = (static_cast<__uint128_t>(Uint128High64(uhash)) << 64) + |
43 Uint128Low64(uhash); | 42 Uint128Low64(uhash); |
44 const uint8_t* octets = reinterpret_cast<const uint8_t*>(data.data()); | 43 const uint8_t* octets = reinterpret_cast<const uint8_t*>(data.data()); |
45 for (size_t i = 0; i < data.length(); ++i) { | 44 for (size_t i = 0; i < data.length(); ++i) { |
46 xhash = (xhash ^ octets[i]) * kPrime; | 45 xhash = (xhash ^ octets[i]) * kPrime; |
47 } | 46 } |
48 return MakeUint128( | 47 return MakeUint128( |
49 static_cast<uint64_t>(xhash >> 64), | 48 static_cast<uint64_t>(xhash >> 64), |
50 static_cast<uint64_t>(xhash & UINT64_C(0xFFFFFFFFFFFFFFFF))); | 49 static_cast<uint64_t>(xhash & UINT64_C(0xFFFFFFFFFFFFFFFF))); |
51 } | 50 } |
52 #endif | 51 #endif |
53 | 52 |
54 #ifndef QUIC_UTIL_HAS_UINT128 | 53 #ifndef QUIC_UTIL_HAS_UINT128 |
55 // Slow implementation of IncrementalHash. In practice, only used by Chromium. | 54 // Slow implementation of IncrementalHash. In practice, only used by Chromium. |
56 uint128 IncrementalHashSlow(uint128 hash, StringPiece data) { | 55 uint128 IncrementalHashSlow(uint128 hash, QuicStringPiece data) { |
57 // kPrime = 309485009821345068724781371 | 56 // kPrime = 309485009821345068724781371 |
58 static const uint128 kPrime = MakeUint128(16777216, 315); | 57 static const uint128 kPrime = MakeUint128(16777216, 315); |
59 const uint8_t* octets = reinterpret_cast<const uint8_t*>(data.data()); | 58 const uint8_t* octets = reinterpret_cast<const uint8_t*>(data.data()); |
60 for (size_t i = 0; i < data.length(); ++i) { | 59 for (size_t i = 0; i < data.length(); ++i) { |
61 hash = hash ^ MakeUint128(0, octets[i]); | 60 hash = hash ^ MakeUint128(0, octets[i]); |
62 hash = hash * kPrime; | 61 hash = hash * kPrime; |
63 } | 62 } |
64 return hash; | 63 return hash; |
65 } | 64 } |
66 #endif | 65 #endif |
67 | 66 |
68 uint128 IncrementalHash(uint128 hash, StringPiece data) { | 67 uint128 IncrementalHash(uint128 hash, QuicStringPiece data) { |
69 #ifdef QUIC_UTIL_HAS_UINT128 | 68 #ifdef QUIC_UTIL_HAS_UINT128 |
70 return IncrementalHashFast(hash, data); | 69 return IncrementalHashFast(hash, data); |
71 #else | 70 #else |
72 return IncrementalHashSlow(hash, data); | 71 return IncrementalHashSlow(hash, data); |
73 #endif | 72 #endif |
74 } | 73 } |
75 | 74 |
76 } // namespace | 75 } // namespace |
77 | 76 |
78 // static | 77 // static |
79 uint64_t QuicUtils::FNV1a_64_Hash(StringPiece data) { | 78 uint64_t QuicUtils::FNV1a_64_Hash(QuicStringPiece data) { |
80 static const uint64_t kOffset = UINT64_C(14695981039346656037); | 79 static const uint64_t kOffset = UINT64_C(14695981039346656037); |
81 static const uint64_t kPrime = UINT64_C(1099511628211); | 80 static const uint64_t kPrime = UINT64_C(1099511628211); |
82 | 81 |
83 const uint8_t* octets = reinterpret_cast<const uint8_t*>(data.data()); | 82 const uint8_t* octets = reinterpret_cast<const uint8_t*>(data.data()); |
84 | 83 |
85 uint64_t hash = kOffset; | 84 uint64_t hash = kOffset; |
86 | 85 |
87 for (size_t i = 0; i < data.length(); ++i) { | 86 for (size_t i = 0; i < data.length(); ++i) { |
88 hash = hash ^ octets[i]; | 87 hash = hash ^ octets[i]; |
89 hash = hash * kPrime; | 88 hash = hash * kPrime; |
90 } | 89 } |
91 | 90 |
92 return hash; | 91 return hash; |
93 } | 92 } |
94 | 93 |
95 // static | 94 // static |
96 uint128 QuicUtils::FNV1a_128_Hash(StringPiece data) { | 95 uint128 QuicUtils::FNV1a_128_Hash(QuicStringPiece data) { |
97 return FNV1a_128_Hash_Three(data, StringPiece(), StringPiece()); | 96 return FNV1a_128_Hash_Three(data, QuicStringPiece(), QuicStringPiece()); |
98 } | 97 } |
99 | 98 |
100 // static | 99 // static |
101 uint128 QuicUtils::FNV1a_128_Hash_Two(StringPiece data1, StringPiece data2) { | 100 uint128 QuicUtils::FNV1a_128_Hash_Two(QuicStringPiece data1, |
102 return FNV1a_128_Hash_Three(data1, data2, StringPiece()); | 101 QuicStringPiece data2) { |
| 102 return FNV1a_128_Hash_Three(data1, data2, QuicStringPiece()); |
103 } | 103 } |
104 | 104 |
105 // static | 105 // static |
106 uint128 QuicUtils::FNV1a_128_Hash_Three(StringPiece data1, | 106 uint128 QuicUtils::FNV1a_128_Hash_Three(QuicStringPiece data1, |
107 StringPiece data2, | 107 QuicStringPiece data2, |
108 StringPiece data3) { | 108 QuicStringPiece data3) { |
109 // The two constants are defined as part of the hash algorithm. | 109 // The two constants are defined as part of the hash algorithm. |
110 // see http://www.isthe.com/chongo/tech/comp/fnv/ | 110 // see http://www.isthe.com/chongo/tech/comp/fnv/ |
111 // kOffset = 144066263297769815596495629667062367629 | 111 // kOffset = 144066263297769815596495629667062367629 |
112 const uint128 kOffset = | 112 const uint128 kOffset = |
113 MakeUint128(UINT64_C(7809847782465536322), UINT64_C(7113472399480571277)); | 113 MakeUint128(UINT64_C(7809847782465536322), UINT64_C(7113472399480571277)); |
114 | 114 |
115 uint128 hash = IncrementalHash(kOffset, data1); | 115 uint128 hash = IncrementalHash(kOffset, data1); |
116 if (data2.empty()) { | 116 if (data2.empty()) { |
117 return hash; | 117 return hash; |
118 } | 118 } |
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
202 if (old_address.host().InSameSubnet(new_address.host(), kSubnetMaskLength)) { | 202 if (old_address.host().InSameSubnet(new_address.host(), kSubnetMaskLength)) { |
203 // Subnet part does not change (here, we use /24), which is considered to be | 203 // Subnet part does not change (here, we use /24), which is considered to be |
204 // caused by NATs. | 204 // caused by NATs. |
205 return IPV4_SUBNET_CHANGE; | 205 return IPV4_SUBNET_CHANGE; |
206 } | 206 } |
207 | 207 |
208 return IPV4_TO_IPV4_CHANGE; | 208 return IPV4_TO_IPV4_CHANGE; |
209 } | 209 } |
210 | 210 |
211 } // namespace net | 211 } // namespace net |
OLD | NEW |