folly/detail/IPAddress.h

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