| 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 |