folly/detail/IPAddressSource.h

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