folly/detail/IPAddress.h

   1 /*
   2  * Copyright 2014 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 }
  44
  45 #include <folly/Conv.h>
  46 #include <folly/Format.h>
  47
  48 namespace folly { namespace detail {
  49
  50 inline std::string familyNameStr(sa_family_t family) {
  51   switch (family) {
  52     case AF_INET:
  53       return "AF_INET";
  54     case AF_INET6:
  55       return "AF_INET6";
  56     case AF_UNSPEC:
  57       return "AF_UNSPEC";
  58     case AF_UNIX:
  59       return "AF_UNIX";
  60     default:
  61       return folly::format("sa_family_t({})",
  62           folly::to<std::string>(family)).str();
  63   }
  64 }
  65
  66 template<typename IPAddrType>
  67 inline bool getNthMSBitImpl(const IPAddrType& ip, uint8_t bitIndex,
  68     sa_family_t family) {
  69   if (bitIndex >= ip.bitCount()) {
  70     throw std::invalid_argument(folly::to<std::string>("Bit index must be < ",
  71           ip.bitCount(), " for addresses of type :", familyNameStr(family)));
  72   }
  73   //Underlying bytes are in n/w byte order
  74   return (ip.getNthMSByte(bitIndex / 8) & (0x80 >> (bitIndex % 8))) != 0;
  75 }
  76
  77 /**
  78  * Helper for working with unsigned char* or uint8_t* ByteArray values
  79  */
  80 struct Bytes : private boost::noncopyable {
  81   // return true if all values of src are zero
  82   static bool isZero(const uint8_t* src, std::size_t len) {
  83     for (auto i = 0; i < len; i++) {
  84       if (src[i] != 0x00) {
  85         return false;
  86       }
  87     }
  88     return true;
  89   }
  90
  91   // mask the values from two byte arrays, returning a new byte array
  92   template<std::size_t N>
  93   static std::array<uint8_t, N> mask(const std::array<uint8_t, N>& a,
  94                                      const std::array<uint8_t, N>& b) {
  95     static_assert(N > 0, "Can't mask an empty ByteArray");
  96     std::size_t asize = a.size();
  97     std::array<uint8_t, N> ba{{0}};
  98     for (int i = 0; i < asize; i++) {
  99       ba[i] = a[i] & b[i];
 100     }
 101     return ba;
 102   }
 103
 104   template<std::size_t N>
 105   static std::pair<std::array<uint8_t, N>, uint8_t>
 106   longestCommonPrefix(
 107     const std::array<uint8_t, N>& one, uint8_t oneMask,
 108     const std::array<uint8_t, N>& two, uint8_t twoMask) {
 109     static constexpr auto kBitCount = N * 8;
 110     static constexpr std::array<uint8_t, 8> kMasks {{
 111       0x80, // /1
 112       0xc0, // /2
 113       0xe0, // /3
 114       0xf0, // /4
 115       0xf8, // /5
 116       0xfc, // /6
 117       0xfe, // /7
 118       0xff  // /8
 119     }};
 120     if (oneMask > kBitCount || twoMask > kBitCount) {
 121       throw std::invalid_argument(folly::to<std::string>("Invalid mask "
 122             "length: ", oneMask > twoMask ? oneMask : twoMask,
 123             ". Mask length must be <= ", kBitCount));
 124     }
 125
 126     auto mask = std::min(oneMask, twoMask);
 127     uint8_t byteIndex = 0;
 128     std::array<uint8_t, N> ba{{0}};
 129     // Compare a byte at a time. Note - I measured compared this with
 130     // going multiple bytes at a time (8, 4, 2 and 1). It turns out
 131     // to be 20 - 25% slower for 4 and 16 byte arrays.
 132     while (byteIndex * 8 < mask && one[byteIndex] == two[byteIndex]) {
 133       ba[byteIndex] = one[byteIndex];
 134       ++byteIndex;
 135     }
 136     auto bitIndex = std::min(mask, (uint8_t)(byteIndex * 8));
 137     // Compute the bit up to which the two byte arrays match in the
 138     // unmatched byte.
 139     // Here the check is bitIndex < mask since the 0th mask entry in
 140     // kMasks array holds the mask for masking the MSb in this byte.
 141     // We could instead make it hold so that no 0th entry masks no
 142     // bits but thats a useless iteration.
 143     while (bitIndex < mask && ((one[bitIndex / 8] & kMasks[bitIndex % 8]) ==
 144         (two[bitIndex / 8] & kMasks[bitIndex % 8]))) {
 145       ba[bitIndex / 8] = one[bitIndex / 8] & kMasks[bitIndex % 8];
 146       ++bitIndex;
 147     }
 148     return {ba, bitIndex};
 149   }
 150
 151   // create an in_addr from an uint8_t*
 152   static inline in_addr mkAddress4(const uint8_t* src) {
 153     union {
 154       in_addr addr;
 155       uint8_t bytes[4];
 156     } addr;
 157     std::memset(&addr, 0, 4);
 158     std::memcpy(addr.bytes, src, 4);
 159     return addr.addr;
 160   }
 161
 162   // create an in6_addr from an uint8_t*
 163   static inline in6_addr mkAddress6(const uint8_t* src) {
 164     in6_addr addr;
 165     std::memset(&addr, 0, 16);
 166     std::memcpy(addr.s6_addr, src, 16);
 167     return addr;
 168   }
 169
 170   // convert an uint8_t* to its hex value
 171   static std::string toHex(const uint8_t* src, std::size_t len) {
 172     static const char* const lut = "0123456789abcdef";
 173     std::stringstream ss;
 174     for (int i = 0; i < len; i++) {
 175       const unsigned char c = src[i];
 176       ss << lut[c >> 4] << lut[c & 15];
 177     }
 178     return ss.str();
 179   }
 180
 181  private:
 182   Bytes() = delete;
 183   ~Bytes() = delete;
 184 };
 185
 186 }}  // folly::detail