2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <glog/logging.h>
20 #include <sys/types.h>
25 #include <type_traits>
27 #include <folly/Format.h>
28 #include <folly/detail/IPAddress.h>
30 // BSDish platforms don't provide standard access to s6_addr16
32 #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__NetBSD__) || \
34 #define s6_addr16 __u6_addr.__u6_addr16
42 * Helper for working with unsigned char* or uint8_t* ByteArray values
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]);
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,
63 const std::array<uint8_t, N>& two,
65 static constexpr auto kBitCount = N * 8;
66 static constexpr std::array<uint8_t, 8> kMasks{{
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),
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];
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
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]);
106 bI = uint8_t(bitIndex / 8);
107 bM = uint8_t(bitIndex % 8);
109 return {ba, bitIndex};
112 // create an in_addr from an uint8_t*
113 static inline in_addr mkAddress4(const uint8_t* src) {
118 std::memset(&addr, 0, 4);
119 std::memcpy(addr.bytes, src, 4);
123 // create an in6_addr from an uint8_t*
124 static inline in6_addr mkAddress6(const uint8_t* src) {
126 std::memset(&addr, 0, 16);
127 std::memcpy(addr.s6_addr, src, 16);
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];
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
153 // This function does not append null terminators.
155 // Output buffer size must be guaranteed by caller (indirectly
156 // controlled by DigitCount template parameter).
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.
163 // - Something like uint8_t, uint16_t, etc
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")
170 // Base is the desired output base of the string
171 // - Base 10 will print [0-9], base 16 will print [0-9a-f]
174 // - Whether or not leading zeros should be printed
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,
185 inline void writeIntegerString(IntegralType val, char** buffer) {
188 if (!PrintAllDigits && val == 0) {
194 IntegralType powerToPrint = 1;
195 for (IntegralType i = 1; i < DigitCount; ++i) {
196 powerToPrint *= Base;
199 bool found = PrintAllDigits;
200 while (powerToPrint) {
201 if (found || powerToPrint <= val) {
202 IntegralType value = IntegralType(val / powerToPrint);
203 if (Base == 10 || value < 10) {
208 *(buf++) = char(value);
213 powerToPrint /= Base;
219 inline size_t fastIpV4ToBufferUnsafe(const in_addr& inAddr, char* str) {
220 const uint8_t* octets = reinterpret_cast<const uint8_t*>(&inAddr.s_addr);
223 writeIntegerString<uint8_t, 3>(octets[0], &buf);
225 writeIntegerString<uint8_t, 3>(octets[1], &buf);
227 writeIntegerString<uint8_t, 3>(octets[2], &buf);
229 writeIntegerString<uint8_t, 3>(octets[3], &buf);
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));
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));
244 inline size_t fastIpv6ToBufferUnsafe(const in6_addr& in6Addr, char* str) {
246 const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.u.Word);
248 const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.s6_addr16);
252 for (int i = 0; i < 8; ++i) {
255 4, // at most 4 hex digits per ushort
257 true>(htons(bytes[i]), &buf);
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));
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));
276 } // namespace detail