folly/detail/IPAddress.h

   1 /*
   2  * Copyright 2015 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 <boost/noncopyable.hpp>
  20 #include <glog/logging.h>
  21
  22 #include <algorithm>
  23 #include <array>
  24 #include <cstring>
  25 #include <string>
  26 #include <sstream>
  27 #include <type_traits>
  28 #include <vector>
  29
  30 extern "C" {
  31 #ifndef _MSC_VER
  32 #include <arpa/inet.h>
  33 #include <netinet/in.h>
  34 #include <sys/socket.h>
  35 #else
  36 #include <winsock2.h>
  37 #include <ws2tcpip.h>
  38 // missing in socket headers
  39 #define sa_family_t ADDRESS_FAMILY
  40 #endif
  41
  42 #include <sys/types.h>
  43 #include <netdb.h>
  44 }
  45
  46 #include <folly/Conv.h>
  47 #include <folly/Format.h>
  48
  49 // BSDish platforms don't provide standard access to s6_addr16
  50 #ifndef s6_addr16
  51 # if defined(__APPLE__) || defined(__FreeBSD__) || \
  52      defined(__NetBSD__) || defined(__OpenBSD__)
  53 #  define s6_addr16 __u6_addr.__u6_addr16
  54 # endif
  55 #endif
  56
  57 namespace folly { namespace detail {
  58
  59 inline std::string familyNameStr(sa_family_t family) {
  60   switch (family) {
  61     case AF_INET:
  62       return "AF_INET";
  63     case AF_INET6:
  64       return "AF_INET6";
  65     case AF_UNSPEC:
  66       return "AF_UNSPEC";
  67     case AF_UNIX:
  68       return "AF_UNIX";
  69     default:
  70       return folly::format("sa_family_t({})",
  71           folly::to<std::string>(family)).str();
  72   }
  73 }
  74
  75 template<typename IPAddrType>
  76 inline bool getNthMSBitImpl(const IPAddrType& ip, uint8_t bitIndex,
  77     sa_family_t family) {
  78   if (bitIndex >= ip.bitCount()) {
  79     throw std::invalid_argument(folly::to<std::string>("Bit index must be < ",
  80           ip.bitCount(), " for addresses of type :", familyNameStr(family)));
  81   }
  82   //Underlying bytes are in n/w byte order
  83   return (ip.getNthMSByte(bitIndex / 8) & (0x80 >> (bitIndex % 8))) != 0;
  84 }
  85
  86 /**
  87  * Helper for working with unsigned char* or uint8_t* ByteArray values
  88  */
  89 struct Bytes : private boost::noncopyable {
  90   // return true if all values of src are zero
  91   static bool isZero(const uint8_t* src, std::size_t len) {
  92     for (std::size_t i = 0; i < len; i++) {
  93       if (src[i] != 0x00) {
  94         return false;
  95       }
  96     }
  97     return true;
  98   }
  99
 100   // mask the values from two byte arrays, returning a new byte array
 101   template<std::size_t N>
 102   static std::array<uint8_t, N> mask(const std::array<uint8_t, N>& a,
 103                                      const std::array<uint8_t, N>& b) {
 104     static_assert(N > 0, "Can't mask an empty ByteArray");
 105     std::size_t asize = a.size();
 106     std::array<uint8_t, N> ba{{0}};
 107     for (std::size_t i = 0; i < asize; i++) {
 108       ba[i] = a[i] & b[i];
 109     }
 110     return ba;
 111   }
 112
 113   template<std::size_t N>
 114   static std::pair<std::array<uint8_t, N>, uint8_t>
 115   longestCommonPrefix(
 116     const std::array<uint8_t, N>& one, uint8_t oneMask,
 117     const std::array<uint8_t, N>& two, uint8_t twoMask) {
 118     static constexpr auto kBitCount = N * 8;
 119     static constexpr std::array<uint8_t, 8> kMasks {{
 120       0x80, // /1
 121       0xc0, // /2
 122       0xe0, // /3
 123       0xf0, // /4
 124       0xf8, // /5
 125       0xfc, // /6
 126       0xfe, // /7
 127       0xff  // /8
 128     }};
 129     if (oneMask > kBitCount || twoMask > kBitCount) {
 130       throw std::invalid_argument(folly::to<std::string>("Invalid mask "
 131             "length: ", oneMask > twoMask ? oneMask : twoMask,
 132             ". Mask length must be <= ", kBitCount));
 133     }
 134
 135     auto mask = std::min(oneMask, twoMask);
 136     uint8_t byteIndex = 0;
 137     std::array<uint8_t, N> ba{{0}};
 138     // Compare a byte at a time. Note - I measured compared this with
 139     // going multiple bytes at a time (8, 4, 2 and 1). It turns out
 140     // to be 20 - 25% slower for 4 and 16 byte arrays.
 141     while (byteIndex * 8 < mask && one[byteIndex] == two[byteIndex]) {
 142       ba[byteIndex] = one[byteIndex];
 143       ++byteIndex;
 144     }
 145     auto bitIndex = std::min(mask, (uint8_t)(byteIndex * 8));
 146     // Compute the bit up to which the two byte arrays match in the
 147     // unmatched byte.
 148     // Here the check is bitIndex < mask since the 0th mask entry in
 149     // kMasks array holds the mask for masking the MSb in this byte.
 150     // We could instead make it hold so that no 0th entry masks no
 151     // bits but thats a useless iteration.
 152     while (bitIndex < mask && ((one[bitIndex / 8] & kMasks[bitIndex % 8]) ==
 153         (two[bitIndex / 8] & kMasks[bitIndex % 8]))) {
 154       ba[bitIndex / 8] = one[bitIndex / 8] & kMasks[bitIndex % 8];
 155       ++bitIndex;
 156     }
 157     return {ba, bitIndex};
 158   }
 159
 160   // create an in_addr from an uint8_t*
 161   static inline in_addr mkAddress4(const uint8_t* src) {
 162     union {
 163       in_addr addr;
 164       uint8_t bytes[4];
 165     } addr;
 166     std::memset(&addr, 0, 4);
 167     std::memcpy(addr.bytes, src, 4);
 168     return addr.addr;
 169   }
 170
 171   // create an in6_addr from an uint8_t*
 172   static inline in6_addr mkAddress6(const uint8_t* src) {
 173     in6_addr addr;
 174     std::memset(&addr, 0, 16);
 175     std::memcpy(addr.s6_addr, src, 16);
 176     return addr;
 177   }
 178
 179   // convert an uint8_t* to its hex value
 180   static std::string toHex(const uint8_t* src, std::size_t len) {
 181     static const char* const lut = "0123456789abcdef";
 182     std::stringstream ss;
 183     for (std::size_t i = 0; i < len; i++) {
 184       const unsigned char c = src[i];
 185       ss << lut[c >> 4] << lut[c & 15];
 186     }
 187     return ss.str();
 188   }
 189
 190  private:
 191   Bytes() = delete;
 192   ~Bytes() = delete;
 193 };
 194
 195 //
 196 // Write a maximum amount of base-converted character digits, of a
 197 // given base, from an unsigned integral type into a byte buffer of
 198 // sufficient size.
 199 //
 200 // This function does not append null terminators.
 201 //
 202 // Output buffer size must be guaranteed by caller (indirectly
 203 // controlled by DigitCount template parameter).
 204 //
 205 // Having these parameters at compile time allows compiler to
 206 // precompute several of the values, use smaller instructions, and
 207 // better optimize surrounding code.
 208 //
 209 // IntegralType:
 210 //   - Something like uint8_t, uint16_t, etc
 211 //
 212 // DigitCount is the maximum number of digits to be printed
 213 //   - This is tied to IntegralType and Base. For example:
 214 //     - uint8_t in base 10 will print at most 3 digits ("255")
 215 //     - uint16_t in base 16 will print at most 4 hex digits ("FFFF")
 216 //
 217 // Base is the desired output base of the string
 218 //   - Base 10 will print [0-9], base 16 will print [0-9a-f]
 219 //
 220 // PrintAllDigits:
 221 //   - Whether or not leading zeros should be printed
 222 //
 223 template<class IntegralType,
 224          IntegralType DigitCount,
 225          IntegralType Base = 10,
 226          bool PrintAllDigits = false,
 227          class = typename std::enable_if<
 228            std::is_integral<IntegralType>::value &&
 229            std::is_unsigned<IntegralType>::value,
 230            bool>::type>
 231   inline void writeIntegerString(
 232     IntegralType val,
 233     char** buffer) {
 234   char* buf = *buffer;
 235
 236   if (!PrintAllDigits && val == 0) {
 237     *(buf++) = '0';
 238     *buffer = buf;
 239     return;
 240   }
 241
 242   IntegralType powerToPrint = 1;
 243   for (int i = 1; i < DigitCount; ++i) {
 244     powerToPrint *= Base;
 245   }
 246
 247   bool found = PrintAllDigits;
 248   while (powerToPrint) {
 249
 250     if (found || powerToPrint <= val) {
 251       IntegralType value = val/powerToPrint;
 252       if (Base == 10 || value < 10) {
 253         value += '0';
 254       } else {
 255         value += ('a'-10);
 256       }
 257       *(buf++) = value;
 258       val %= powerToPrint;
 259       found = true;
 260     }
 261
 262     powerToPrint /= Base;
 263   }
 264
 265   *buffer = buf;
 266 }
 267
 268 inline std::string fastIpv4ToString(
 269   const in_addr& inAddr) {
 270   const uint8_t* octets = reinterpret_cast<const uint8_t*>(&inAddr.s_addr);
 271   char str[sizeof("255.255.255.255")];
 272   char* buf = str;
 273
 274   writeIntegerString<uint8_t, 3>(octets[0], &buf);
 275   *(buf++) = '.';
 276   writeIntegerString<uint8_t, 3>(octets[1], &buf);
 277   *(buf++) = '.';
 278   writeIntegerString<uint8_t, 3>(octets[2], &buf);
 279   *(buf++) = '.';
 280   writeIntegerString<uint8_t, 3>(octets[3], &buf);
 281
 282   return std::string(str, buf-str);
 283 }
 284
 285 inline std::string fastIpv6ToString(const in6_addr& in6Addr) {
 286 #ifdef _MSC_VER
 287   const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.u.Word);
 288 #else
 289   const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.s6_addr16);
 290 #endif
 291   char str[sizeof("2001:0db8:0000:0000:0000:ff00:0042:8329")];
 292   char* buf = str;
 293
 294   for (int i = 0; i < 8; ++i) {
 295     writeIntegerString<uint16_t,
 296                        4,  // at most 4 hex digits per ushort
 297                        16, // base 16 (hex)
 298                        true>(htons(bytes[i]), &buf);
 299
 300     if(i != 7) {
 301       *(buf++) = ':';
 302     }
 303   }
 304
 305   return std::string(str, buf-str);
 306 }
 307
 308 }}  // folly::detail