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