folly/detail/IPAddressSource.h

   1 /*
   2  * Copyright 2017 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