1 | /* |
2 | * Copyright 2014-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <glog/logging.h> |
20 | #include <sys/types.h> |
21 | #include <algorithm> |
22 | #include <array> |
23 | #include <cstring> |
24 | #include <string> |
25 | #include <type_traits> |
26 | |
27 | #include <folly/Format.h> |
28 | #include <folly/detail/IPAddress.h> |
29 | |
30 | // BSDish platforms don't provide standard access to s6_addr16 |
31 | #ifndef s6_addr16 |
32 | #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__NetBSD__) || \ |
33 | defined(__OpenBSD__) |
34 | #define s6_addr16 __u6_addr.__u6_addr16 |
35 | #endif |
36 | #endif |
37 | |
38 | namespace folly { |
39 | namespace detail { |
40 | |
41 | /** |
42 | * Helper for working with unsigned char* or uint8_t* ByteArray values |
43 | */ |
44 | struct Bytes { |
45 | // mask the values from two byte arrays, returning a new byte array |
46 | template <std::size_t N> |
47 | static std::array<uint8_t, N> mask( |
48 | const std::array<uint8_t, N>& a, |
49 | const std::array<uint8_t, N>& b) { |
50 | static_assert(N > 0, "Can't mask an empty ByteArray" ); |
51 | std::size_t asize = a.size(); |
52 | std::array<uint8_t, N> ba{{0}}; |
53 | for (std::size_t i = 0; i < asize; i++) { |
54 | ba[i] = uint8_t(a[i] & b[i]); |
55 | } |
56 | return ba; |
57 | } |
58 | |
59 | template <std::size_t N> |
60 | static std::pair<std::array<uint8_t, N>, uint8_t> longestCommonPrefix( |
61 | const std::array<uint8_t, N>& one, |
62 | uint8_t oneMask, |
63 | const std::array<uint8_t, N>& two, |
64 | uint8_t twoMask) { |
65 | static constexpr auto kBitCount = N * 8; |
66 | static constexpr std::array<uint8_t, 8> kMasks{{ |
67 | 0x80, // /1 |
68 | 0xc0, // /2 |
69 | 0xe0, // /3 |
70 | 0xf0, // /4 |
71 | 0xf8, // /5 |
72 | 0xfc, // /6 |
73 | 0xfe, // /7 |
74 | 0xff // /8 |
75 | }}; |
76 | if (oneMask > kBitCount || twoMask > kBitCount) { |
77 | throw std::invalid_argument(sformat( |
78 | "Invalid mask length: {}. Mask length must be <= {}" , |
79 | std::max(oneMask, twoMask), |
80 | kBitCount)); |
81 | } |
82 | |
83 | auto mask = std::min(oneMask, twoMask); |
84 | uint8_t byteIndex = 0; |
85 | std::array<uint8_t, N> ba{{0}}; |
86 | // Compare a byte at a time. Note - I measured compared this with |
87 | // going multiple bytes at a time (8, 4, 2 and 1). It turns out |
88 | // to be 20 - 25% slower for 4 and 16 byte arrays. |
89 | while (byteIndex * 8 < mask && one[byteIndex] == two[byteIndex]) { |
90 | ba[byteIndex] = one[byteIndex]; |
91 | ++byteIndex; |
92 | } |
93 | auto bitIndex = std::min(mask, uint8_t(byteIndex * 8)); |
94 | uint8_t bI = uint8_t(bitIndex / 8); |
95 | uint8_t bM = uint8_t(bitIndex % 8); |
96 | // Compute the bit up to which the two byte arrays match in the |
97 | // unmatched byte. |
98 | // Here the check is bitIndex < mask since the 0th mask entry in |
99 | // kMasks array holds the mask for masking the MSb in this byte. |
100 | // We could instead make it hold so that no 0th entry masks no |
101 | // bits but thats a useless iteration. |
102 | while (bitIndex < mask && |
103 | ((one[bI] & kMasks[bM]) == (two[bI] & kMasks[bM]))) { |
104 | ba[bI] = uint8_t(one[bI] & kMasks[bM]); |
105 | ++bitIndex; |
106 | bI = uint8_t(bitIndex / 8); |
107 | bM = uint8_t(bitIndex % 8); |
108 | } |
109 | return {ba, bitIndex}; |
110 | } |
111 | |
112 | // create an in_addr from an uint8_t* |
113 | static inline in_addr mkAddress4(const uint8_t* src) { |
114 | union { |
115 | in_addr addr; |
116 | uint8_t bytes[4]; |
117 | } addr; |
118 | std::memset(&addr, 0, 4); |
119 | std::memcpy(addr.bytes, src, 4); |
120 | return addr.addr; |
121 | } |
122 | |
123 | // create an in6_addr from an uint8_t* |
124 | static inline in6_addr mkAddress6(const uint8_t* src) { |
125 | in6_addr addr; |
126 | std::memset(&addr, 0, 16); |
127 | std::memcpy(addr.s6_addr, src, 16); |
128 | return addr; |
129 | } |
130 | |
131 | // convert an uint8_t* to its hex value |
132 | static std::string toHex(const uint8_t* src, std::size_t len) { |
133 | static const char* const lut = "0123456789abcdef" ; |
134 | std::string out(len * 2, 0); |
135 | for (std::size_t i = 0; i < len; i++) { |
136 | const unsigned char c = src[i]; |
137 | out[i * 2 + 0] = lut[c >> 4]; |
138 | out[i * 2 + 1] = lut[c & 15]; |
139 | } |
140 | return out; |
141 | } |
142 | |
143 | private: |
144 | Bytes() = delete; |
145 | ~Bytes() = delete; |
146 | }; |
147 | |
148 | // |
149 | // Write a maximum amount of base-converted character digits, of a |
150 | // given base, from an unsigned integral type into a byte buffer of |
151 | // sufficient size. |
152 | // |
153 | // This function does not append null terminators. |
154 | // |
155 | // Output buffer size must be guaranteed by caller (indirectly |
156 | // controlled by DigitCount template parameter). |
157 | // |
158 | // Having these parameters at compile time allows compiler to |
159 | // precompute several of the values, use smaller instructions, and |
160 | // better optimize surrounding code. |
161 | // |
162 | // IntegralType: |
163 | // - Something like uint8_t, uint16_t, etc |
164 | // |
165 | // DigitCount is the maximum number of digits to be printed |
166 | // - This is tied to IntegralType and Base. For example: |
167 | // - uint8_t in base 10 will print at most 3 digits ("255") |
168 | // - uint16_t in base 16 will print at most 4 hex digits ("FFFF") |
169 | // |
170 | // Base is the desired output base of the string |
171 | // - Base 10 will print [0-9], base 16 will print [0-9a-f] |
172 | // |
173 | // PrintAllDigits: |
174 | // - Whether or not leading zeros should be printed |
175 | // |
176 | template < |
177 | class IntegralType, |
178 | IntegralType DigitCount, |
179 | IntegralType Base = IntegralType(10), |
180 | bool PrintAllDigits = false, |
181 | class = typename std::enable_if< |
182 | std::is_integral<IntegralType>::value && |
183 | std::is_unsigned<IntegralType>::value, |
184 | bool>::type> |
185 | inline void writeIntegerString(IntegralType val, char** buffer) { |
186 | char* buf = *buffer; |
187 | |
188 | if (!PrintAllDigits && val == 0) { |
189 | *(buf++) = '0'; |
190 | *buffer = buf; |
191 | return; |
192 | } |
193 | |
194 | IntegralType powerToPrint = 1; |
195 | for (IntegralType i = 1; i < DigitCount; ++i) { |
196 | powerToPrint *= Base; |
197 | } |
198 | |
199 | bool found = PrintAllDigits; |
200 | while (powerToPrint) { |
201 | if (found || powerToPrint <= val) { |
202 | IntegralType value = IntegralType(val / powerToPrint); |
203 | if (Base == 10 || value < 10) { |
204 | value += '0'; |
205 | } else { |
206 | value += ('a' - 10); |
207 | } |
208 | *(buf++) = char(value); |
209 | val %= powerToPrint; |
210 | found = true; |
211 | } |
212 | |
213 | powerToPrint /= Base; |
214 | } |
215 | |
216 | *buffer = buf; |
217 | } |
218 | |
219 | inline size_t fastIpV4ToBufferUnsafe(const in_addr& inAddr, char* str) { |
220 | const uint8_t* octets = reinterpret_cast<const uint8_t*>(&inAddr.s_addr); |
221 | char* buf = str; |
222 | |
223 | writeIntegerString<uint8_t, 3>(octets[0], &buf); |
224 | *(buf++) = '.'; |
225 | writeIntegerString<uint8_t, 3>(octets[1], &buf); |
226 | *(buf++) = '.'; |
227 | writeIntegerString<uint8_t, 3>(octets[2], &buf); |
228 | *(buf++) = '.'; |
229 | writeIntegerString<uint8_t, 3>(octets[3], &buf); |
230 | |
231 | return buf - str; |
232 | } |
233 | |
234 | inline std::string fastIpv4ToString(const in_addr& inAddr) { |
235 | char str[sizeof("255.255.255.255" )]; |
236 | return std::string(str, fastIpV4ToBufferUnsafe(inAddr, str)); |
237 | } |
238 | |
239 | inline void fastIpv4AppendToString(const in_addr& inAddr, std::string& out) { |
240 | char str[sizeof("255.255.255.255" )]; |
241 | out.append(str, fastIpV4ToBufferUnsafe(inAddr, str)); |
242 | } |
243 | |
244 | inline size_t fastIpv6ToBufferUnsafe(const in6_addr& in6Addr, char* str) { |
245 | #ifdef _MSC_VER |
246 | const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.u.Word); |
247 | #else |
248 | const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.s6_addr16); |
249 | #endif |
250 | char* buf = str; |
251 | |
252 | for (int i = 0; i < 8; ++i) { |
253 | writeIntegerString< |
254 | uint16_t, |
255 | 4, // at most 4 hex digits per ushort |
256 | 16, // base 16 (hex) |
257 | true>(htons(bytes[i]), &buf); |
258 | |
259 | if (i != 7) { |
260 | *(buf++) = ':'; |
261 | } |
262 | } |
263 | |
264 | return buf - str; |
265 | } |
266 | |
267 | inline std::string fastIpv6ToString(const in6_addr& in6Addr) { |
268 | char str[sizeof("2001:0db8:0000:0000:0000:ff00:0042:8329" )]; |
269 | return std::string(str, fastIpv6ToBufferUnsafe(in6Addr, str)); |
270 | } |
271 | |
272 | inline void fastIpv6AppendToString(const in6_addr& in6Addr, std::string& out) { |
273 | char str[sizeof("2001:0db8:0000:0000:0000:ff00:0042:8329" )]; |
274 | out.append(str, fastIpv6ToBufferUnsafe(in6Addr, str)); |
275 | } |
276 | } // namespace detail |
277 | } // namespace folly |
278 | |