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
38namespace folly {
39namespace detail {
40
41/**
42 * Helper for working with unsigned char* or uint8_t* ByteArray values
43 */
44struct 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//
176template <
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>
185inline 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
219inline 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
234inline 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
239inline 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
244inline 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
267inline 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
272inline 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