folly/detail/IPAddressSource.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 <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/Conv.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] = 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(folly::to<std::string>(
  78           "Invalid mask "
  79           "length: ",
  80           oneMask > twoMask ? oneMask : twoMask,
  81           ". Mask length must be <= ",
  82           kBitCount));
  83     }
  84
  85     auto mask = std::min(oneMask, twoMask);
  86     uint8_t byteIndex = 0;
  87     std::array<uint8_t, N> ba{{0}};
  88     // Compare a byte at a time. Note - I measured compared this with
  89     // going multiple bytes at a time (8, 4, 2 and 1). It turns out
  90     // to be 20 - 25% slower for 4 and 16 byte arrays.
  91     while (byteIndex * 8 < mask && one[byteIndex] == two[byteIndex]) {
  92       ba[byteIndex] = one[byteIndex];
  93       ++byteIndex;
  94     }
  95     auto bitIndex = std::min(mask, (uint8_t)(byteIndex * 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 && ((one[bitIndex / 8] & kMasks[bitIndex % 8]) ==
 103                                (two[bitIndex / 8] & kMasks[bitIndex % 8]))) {
 104       ba[bitIndex / 8] = one[bitIndex / 8] & kMasks[bitIndex % 8];
 105       ++bitIndex;
 106     }
 107     return {ba, bitIndex};
 108   }
 109
 110   // create an in_addr from an uint8_t*
 111   static inline in_addr mkAddress4(const uint8_t* src) {
 112     union {
 113       in_addr addr;
 114       uint8_t bytes[4];
 115     } addr;
 116     std::memset(&addr, 0, 4);
 117     std::memcpy(addr.bytes, src, 4);
 118     return addr.addr;
 119   }
 120
 121   // create an in6_addr from an uint8_t*
 122   static inline in6_addr mkAddress6(const uint8_t* src) {
 123     in6_addr addr;
 124     std::memset(&addr, 0, 16);
 125     std::memcpy(addr.s6_addr, src, 16);
 126     return addr;
 127   }
 128
 129   // convert an uint8_t* to its hex value
 130   static std::string toHex(const uint8_t* src, std::size_t len) {
 131     static const char* const lut = "0123456789abcdef";
 132     std::string out(len * 2, 0);
 133     for (std::size_t i = 0; i < len; i++) {
 134       const unsigned char c = src[i];
 135       out[i * 2 + 0] = lut[c >> 4];
 136       out[i * 2 + 1] = lut[c & 15];
 137     }
 138     return out;
 139   }
 140
 141  private:
 142   Bytes() = delete;
 143   ~Bytes() = delete;
 144 };
 145
 146 //
 147 // Write a maximum amount of base-converted character digits, of a
 148 // given base, from an unsigned integral type into a byte buffer of
 149 // sufficient size.
 150 //
 151 // This function does not append null terminators.
 152 //
 153 // Output buffer size must be guaranteed by caller (indirectly
 154 // controlled by DigitCount template parameter).
 155 //
 156 // Having these parameters at compile time allows compiler to
 157 // precompute several of the values, use smaller instructions, and
 158 // better optimize surrounding code.
 159 //
 160 // IntegralType:
 161 //   - Something like uint8_t, uint16_t, etc
 162 //
 163 // DigitCount is the maximum number of digits to be printed
 164 //   - This is tied to IntegralType and Base. For example:
 165 //     - uint8_t in base 10 will print at most 3 digits ("255")
 166 //     - uint16_t in base 16 will print at most 4 hex digits ("FFFF")
 167 //
 168 // Base is the desired output base of the string
 169 //   - Base 10 will print [0-9], base 16 will print [0-9a-f]
 170 //
 171 // PrintAllDigits:
 172 //   - Whether or not leading zeros should be printed
 173 //
 174 template <
 175     class IntegralType,
 176     IntegralType DigitCount,
 177     IntegralType Base = 10,
 178     bool PrintAllDigits = false,
 179     class = typename std::enable_if<
 180         std::is_integral<IntegralType>::value &&
 181             std::is_unsigned<IntegralType>::value,
 182         bool>::type>
 183 inline void writeIntegerString(IntegralType val, char** buffer) {
 184   char* buf = *buffer;
 185
 186   if (!PrintAllDigits && val == 0) {
 187     *(buf++) = '0';
 188     *buffer = buf;
 189     return;
 190   }
 191
 192   IntegralType powerToPrint = 1;
 193   for (int i = 1; i < DigitCount; ++i) {
 194     powerToPrint *= Base;
 195   }
 196
 197   bool found = PrintAllDigits;
 198   while (powerToPrint) {
 199     if (found || powerToPrint <= val) {
 200       IntegralType value = val / powerToPrint;
 201       if (Base == 10 || value < 10) {
 202         value += '0';
 203       } else {
 204         value += ('a' - 10);
 205       }
 206       *(buf++) = value;
 207       val %= powerToPrint;
 208       found = true;
 209     }
 210
 211     powerToPrint /= Base;
 212   }
 213
 214   *buffer = buf;
 215 }
 216
 217 inline std::string fastIpv4ToString(const in_addr& inAddr) {
 218   const uint8_t* octets = reinterpret_cast<const uint8_t*>(&inAddr.s_addr);
 219   char str[sizeof("255.255.255.255")];
 220   char* buf = str;
 221
 222   writeIntegerString<uint8_t, 3>(octets[0], &buf);
 223   *(buf++) = '.';
 224   writeIntegerString<uint8_t, 3>(octets[1], &buf);
 225   *(buf++) = '.';
 226   writeIntegerString<uint8_t, 3>(octets[2], &buf);
 227   *(buf++) = '.';
 228   writeIntegerString<uint8_t, 3>(octets[3], &buf);
 229
 230   return std::string(str, buf - str);
 231 }
 232
 233 inline std::string fastIpv6ToString(const in6_addr& in6Addr) {
 234 #ifdef _MSC_VER
 235   const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.u.Word);
 236 #else
 237   const uint16_t* bytes = reinterpret_cast<const uint16_t*>(&in6Addr.s6_addr16);
 238 #endif
 239   char str[sizeof("2001:0db8:0000:0000:0000:ff00:0042:8329")];
 240   char* buf = str;
 241
 242   for (int i = 0; i < 8; ++i) {
 243     writeIntegerString<
 244         uint16_t,
 245         4, // at most 4 hex digits per ushort
 246         16, // base 16 (hex)
 247         true>(htons(bytes[i]), &buf);
 248
 249     if (i != 7) {
 250       *(buf++) = ':';
 251     }
 252   }
 253
 254   return std::string(str, buf - str);
 255 }
 256 }
 257 }