folly/IPAddressV6.cpp

   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 #include <folly/IPAddressV6.h>
  18
  19 #include <ostream>
  20 #include <string>
  21
  22 #include <folly/Format.h>
  23 #include <folly/IPAddress.h>
  24 #include <folly/IPAddressV4.h>
  25 #include <folly/MacAddress.h>
  26 #include <folly/detail/IPAddressSource.h>
  27
  28 using std::ostream;
  29 using std::string;
  30
  31 namespace folly {
  32
  33 // public static const
  34 const uint32_t IPAddressV6::PREFIX_TEREDO = 0x20010000;
  35 const uint32_t IPAddressV6::PREFIX_6TO4 = 0x2002;
  36
  37 // free functions
  38 size_t hash_value(const IPAddressV6& addr) {
  39   return addr.hash();
  40 }
  41 ostream& operator<<(ostream& os, const IPAddressV6& addr) {
  42   os << addr.str();
  43   return os;
  44 }
  45 void toAppend(IPAddressV6 addr, string* result) {
  46   result->append(addr.str());
  47 }
  48 void toAppend(IPAddressV6 addr, fbstring* result) {
  49   result->append(addr.str());
  50 }
  51
  52 bool IPAddressV6::validate(StringPiece ip) {
  53   if (ip.size() > 0 && ip.front() == '[' && ip.back() == ']') {
  54     ip = ip.subpiece(1, ip.size() - 2);
  55   }
  56
  57   constexpr size_t kStrMaxLen = INET6_ADDRSTRLEN;
  58   std::array<char, kStrMaxLen + 1> ip_cstr;
  59   const size_t len = std::min(ip.size(), kStrMaxLen);
  60   std::memcpy(ip_cstr.data(), ip.data(), len);
  61   ip_cstr[len] = 0;
  62   struct in6_addr addr;
  63   return 1 == inet_pton(AF_INET6, ip_cstr.data(), &addr);
  64 }
  65
  66 // public default constructor
  67 IPAddressV6::IPAddressV6() {
  68 }
  69
  70 // public string constructor
  71 IPAddressV6::IPAddressV6(StringPiece addr) {
  72   auto ip = addr.str();
  73
  74   // Allow addresses surrounded in brackets
  75   if (ip.size() < 2) {
  76     throw IPAddressFormatException(
  77         to<std::string>("Invalid IPv6 address '", ip, "': address too short"));
  78   }
  79   if (ip.front() == '[' && ip.back() == ']') {
  80     ip = ip.substr(1, ip.size() - 2);
  81   }
  82
  83   struct addrinfo* result;
  84   struct addrinfo hints;
  85   memset(&hints, 0, sizeof(hints));
  86   hints.ai_family = AF_INET6;
  87   hints.ai_socktype = SOCK_STREAM;
  88   hints.ai_flags = AI_NUMERICHOST;
  89   if (!getaddrinfo(ip.c_str(), nullptr, &hints, &result)) {
  90     struct sockaddr_in6* ipAddr = (struct sockaddr_in6*)result->ai_addr;
  91     addr_.in6Addr_ = ipAddr->sin6_addr;
  92     scope_ = uint16_t(ipAddr->sin6_scope_id);
  93     freeaddrinfo(result);
  94   } else {
  95     throw IPAddressFormatException(
  96         to<std::string>("Invalid IPv6 address '", ip, "'"));
  97   }
  98 }
  99
 100 // in6_addr constructor
 101 IPAddressV6::IPAddressV6(const in6_addr& src)
 102   : addr_(src)
 103 {
 104 }
 105
 106 // sockaddr_in6 constructor
 107 IPAddressV6::IPAddressV6(const sockaddr_in6& src)
 108   : addr_(src.sin6_addr)
 109   , scope_(uint16_t(src.sin6_scope_id))
 110 {
 111 }
 112
 113 // ByteArray16 constructor
 114 IPAddressV6::IPAddressV6(const ByteArray16& src)
 115   : addr_(src)
 116 {
 117 }
 118
 119 // link-local constructor
 120 IPAddressV6::IPAddressV6(LinkLocalTag, MacAddress mac)
 121   : addr_(mac) {
 122 }
 123
 124 IPAddressV6::AddressStorage::AddressStorage(MacAddress mac) {
 125   // The link-local address uses modified EUI-64 format,
 126   // See RFC 4291 sections 2.5.1, 2.5.6, and Appendix A
 127   const auto* macBytes = mac.bytes();
 128   memcpy(&bytes_.front(), "\xfe\x80\x00\x00\x00\x00\x00\x00", 8);
 129   bytes_[8] = uint8_t(macBytes[0] ^ 0x02);
 130   bytes_[9] = macBytes[1];
 131   bytes_[10] = macBytes[2];
 132   bytes_[11] = 0xff;
 133   bytes_[12] = 0xfe;
 134   bytes_[13] = macBytes[3];
 135   bytes_[14] = macBytes[4];
 136   bytes_[15] = macBytes[5];
 137 }
 138
 139 Optional<MacAddress> IPAddressV6::getMacAddressFromLinkLocal() const {
 140   // Returned MacAddress must be constructed from a link-local IPv6 address.
 141   if (!(addr_.bytes_[0] == 0xfe && addr_.bytes_[1] == 0x80 &&
 142         addr_.bytes_[2] == 0x00 && addr_.bytes_[3] == 0x00 &&
 143         addr_.bytes_[4] == 0x00 && addr_.bytes_[5] == 0x00 &&
 144         addr_.bytes_[6] == 0x00 && addr_.bytes_[7] == 0x00 &&
 145         addr_.bytes_[11] == 0xff && addr_.bytes_[12] == 0xfe)) {
 146     return folly::none;
 147   }
 148   // The link-local address uses modified EUI-64 format,
 149   // See RFC 4291 sections 2.5.1, 2.5.6, and Appendix A
 150   std::array<uint8_t, MacAddress::SIZE> bytes;
 151   // Step 1: first 8 bytes are fe:80:00:00:00:00:00:00, and can be stripped
 152   // Step 2: invert the universal/local (U/L) flag (bit 7)
 153   bytes[0] = addr_.bytes_[8] ^ 0x02;
 154   // Step 3: copy thhese bytes are they are
 155   bytes[1] = addr_.bytes_[9];
 156   bytes[2] = addr_.bytes_[10];
 157   // Step 4: strip bytes (0xfffe), which are bytes_[11] and bytes_[12]
 158   // Step 5: copy the rest.
 159   bytes[3] = addr_.bytes_[13];
 160   bytes[4] = addr_.bytes_[14];
 161   bytes[5] = addr_.bytes_[15];
 162   return Optional<MacAddress>(MacAddress::fromBinary(range(bytes)));
 163 }
 164
 165 void IPAddressV6::setFromBinary(ByteRange bytes) {
 166   if (bytes.size() != 16) {
 167     throw IPAddressFormatException(to<std::string>(
 168         "Invalid IPv6 binary data: length must ",
 169         "be 16 bytes, got ",
 170         bytes.size()));
 171   }
 172   memcpy(&addr_.in6Addr_.s6_addr, bytes.data(), sizeof(in6_addr));
 173   scope_ = 0;
 174 }
 175
 176 // static
 177 IPAddressV6 IPAddressV6::fromInverseArpaName(const std::string& arpaname) {
 178   auto piece = StringPiece(arpaname);
 179   if (!piece.removeSuffix(".ip6.arpa")) {
 180     throw IPAddressFormatException(sformat(
 181         "Invalid input. Should end with 'ip6.arpa'. Got '{}'", arpaname));
 182   }
 183   std::vector<StringPiece> pieces;
 184   split(".", piece, pieces);
 185   if (pieces.size() != 32) {
 186     throw IPAddressFormatException(sformat("Invalid input. Got '{}'", piece));
 187   }
 188   std::array<char, IPAddressV6::kToFullyQualifiedSize> ip;
 189   size_t pos = 0;
 190   int count = 0;
 191   for (size_t i = 1; i <= pieces.size(); i++) {
 192     ip[pos] = pieces[pieces.size() - i][0];
 193     pos++;
 194     count++;
 195     // add ':' every 4 chars
 196     if (count == 4 && pos < ip.size()) {
 197       ip[pos++] = ':';
 198       count = 0;
 199     }
 200   }
 201   return IPAddressV6(folly::range(ip));
 202 }
 203
 204 // public
 205 IPAddressV4 IPAddressV6::createIPv4() const {
 206   if (!isIPv4Mapped()) {
 207     throw IPAddressFormatException("addr is not v4-to-v6-mapped");
 208   }
 209   const unsigned char* by = bytes();
 210   return IPAddressV4(detail::Bytes::mkAddress4(&by[12]));
 211 }
 212
 213 // convert two uint8_t bytes into a uint16_t as hibyte.lobyte
 214 static inline uint16_t unpack(uint8_t lobyte, uint8_t hibyte) {
 215   return uint16_t((uint16_t(hibyte) << 8) | lobyte);
 216 }
 217
 218 // given a src string, unpack count*2 bytes into dest
 219 // dest must have as much storage as count
 220 static inline void unpackInto(const unsigned char* src,
 221                               uint16_t* dest,
 222                               size_t count) {
 223   for (size_t i = 0, hi = 1, lo = 0; i < count; i++) {
 224     dest[i] = unpack(src[hi], src[lo]);
 225     hi += 2;
 226     lo += 2;
 227   }
 228 }
 229
 230 // public
 231 IPAddressV4 IPAddressV6::getIPv4For6To4() const {
 232   if (!is6To4()) {
 233     throw IPAddressV6::TypeError(format(
 234             "Invalid IP '{}': not a 6to4 address", str()).str());
 235   }
 236   // convert 16x8 bytes into first 4x16 bytes
 237   uint16_t ints[4] = {0,0,0,0};
 238   unpackInto(bytes(), ints, 4);
 239   // repack into 4x8
 240   union {
 241     unsigned char bytes[4];
 242     in_addr addr;
 243   } ipv4;
 244   ipv4.bytes[0] = (uint8_t)((ints[1] & 0xFF00) >> 8);
 245   ipv4.bytes[1] = (uint8_t)(ints[1] & 0x00FF);
 246   ipv4.bytes[2] = (uint8_t)((ints[2] & 0xFF00) >> 8);
 247   ipv4.bytes[3] = (uint8_t)(ints[2] & 0x00FF);
 248   return IPAddressV4(ipv4.addr);
 249 }
 250
 251 // public
 252 bool IPAddressV6::isIPv4Mapped() const {
 253   // v4 mapped addresses have their first 10 bytes set to 0, the next 2 bytes
 254   // set to 255 (0xff);
 255   const unsigned char* by = bytes();
 256
 257   // check if first 10 bytes are 0
 258   for (int i = 0; i < 10; i++) {
 259     if (by[i] != 0x00) {
 260       return false;
 261     }
 262   }
 263   // check if bytes 11 and 12 are 255
 264   if (by[10] == 0xff && by[11] == 0xff) {
 265     return true;
 266   }
 267   return false;
 268 }
 269
 270 // public
 271 IPAddressV6::Type IPAddressV6::type() const {
 272   // convert 16x8 bytes into first 2x16 bytes
 273   uint16_t ints[2] = {0,0};
 274   unpackInto(bytes(), ints, 2);
 275
 276   if ((((uint32_t)ints[0] << 16) | ints[1]) == IPAddressV6::PREFIX_TEREDO) {
 277     return Type::TEREDO;
 278   }
 279
 280   if ((uint32_t)ints[0] == IPAddressV6::PREFIX_6TO4) {
 281     return Type::T6TO4;
 282   }
 283
 284   return Type::NORMAL;
 285 }
 286
 287 // public
 288 string IPAddressV6::toJson() const {
 289   return format(
 290       "{{family:'AF_INET6', addr:'{}', hash:{}}}", str(), hash()).str();
 291 }
 292
 293 // public
 294 size_t IPAddressV6::hash() const {
 295   if (isIPv4Mapped()) {
 296     /* An IPAddress containing this object would be equal (i.e. operator==)
 297        to an IPAddress containing the corresponding IPv4.
 298        So we must make sure that the hash values are the same as well */
 299     return IPAddress::createIPv4(*this).hash();
 300   }
 301
 302   static const uint64_t seed = AF_INET6;
 303   uint64_t hash1 = 0, hash2 = 0;
 304   hash::SpookyHashV2::Hash128(&addr_, 16, &hash1, &hash2);
 305   return hash::hash_combine(seed, hash1, hash2);
 306 }
 307
 308 // public
 309 bool IPAddressV6::inSubnet(StringPiece cidrNetwork) const {
 310   auto subnetInfo = IPAddress::createNetwork(cidrNetwork);
 311   auto addr = subnetInfo.first;
 312   if (!addr.isV6()) {
 313     throw IPAddressFormatException(to<std::string>(
 314         "Address '", addr.toJson(), "' ", "is not a V6 address"));
 315   }
 316   return inSubnetWithMask(addr.asV6(), fetchMask(subnetInfo.second));
 317 }
 318
 319 // public
 320 bool IPAddressV6::inSubnetWithMask(const IPAddressV6& subnet,
 321                                    const ByteArray16& cidrMask) const {
 322   const ByteArray16 mask = detail::Bytes::mask(toByteArray(), cidrMask);
 323   const ByteArray16 subMask = detail::Bytes::mask(subnet.toByteArray(),
 324                                                   cidrMask);
 325   return (mask == subMask);
 326 }
 327
 328 // public
 329 bool IPAddressV6::isLoopback() const {
 330   // Check if v4 mapped is loopback
 331   if (isIPv4Mapped() && createIPv4().isLoopback()) {
 332     return true;
 333   }
 334   auto socka = toSockAddr();
 335   return IN6_IS_ADDR_LOOPBACK(&socka.sin6_addr);
 336 }
 337
 338 bool IPAddressV6::isRoutable() const {
 339   return
 340     // 2000::/3 is the only assigned global unicast block
 341     inBinarySubnet({{0x20, 0x00}}, 3) ||
 342     // ffxe::/16 are global scope multicast addresses,
 343     // which are eligible to be routed over the internet
 344     (isMulticast() && getMulticastScope() == 0xe);
 345 }
 346
 347 bool IPAddressV6::isLinkLocalBroadcast() const {
 348   static const IPAddressV6 kLinkLocalBroadcast("ff02::1");
 349   return *this == kLinkLocalBroadcast;
 350 }
 351
 352 // public
 353 bool IPAddressV6::isPrivate() const {
 354   // Check if mapped is private
 355   if (isIPv4Mapped() && createIPv4().isPrivate()) {
 356     return true;
 357   }
 358   return isLoopback() || inBinarySubnet({{0xfc, 0x00}}, 7);
 359 }
 360
 361 // public
 362 bool IPAddressV6::isLinkLocal() const {
 363   return inBinarySubnet({{0xfe, 0x80}}, 10);
 364 }
 365
 366 bool IPAddressV6::isMulticast() const {
 367   return addr_.bytes_[0] == 0xff;
 368 }
 369
 370 uint8_t IPAddressV6::getMulticastFlags() const {
 371   DCHECK(isMulticast());
 372   return uint8_t((addr_.bytes_[1] >> 4) & 0xf);
 373 }
 374
 375 uint8_t IPAddressV6::getMulticastScope() const {
 376   DCHECK(isMulticast());
 377   return uint8_t(addr_.bytes_[1] & 0xf);
 378 }
 379
 380 IPAddressV6 IPAddressV6::getSolicitedNodeAddress() const {
 381   // Solicted node addresses must be constructed from unicast (or anycast)
 382   // addresses
 383   DCHECK(!isMulticast());
 384
 385   uint8_t bytes[16] = { 0xff, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 386                         0x00, 0x00, 0x00, 0x01, 0xff, 0x00, 0x00, 0x00 };
 387   bytes[13] = addr_.bytes_[13];
 388   bytes[14] = addr_.bytes_[14];
 389   bytes[15] = addr_.bytes_[15];
 390   return IPAddressV6::fromBinary(ByteRange(bytes, 16));
 391 }
 392
 393 // public
 394 IPAddressV6 IPAddressV6::mask(size_t numBits) const {
 395   static const auto bits = bitCount();
 396   if (numBits > bits) {
 397     throw IPAddressFormatException(
 398         to<std::string>("numBits(", numBits, ") > bitCount(", bits, ")"));
 399   }
 400   ByteArray16 ba = detail::Bytes::mask(fetchMask(numBits), addr_.bytes_);
 401   return IPAddressV6(ba);
 402 }
 403
 404 // public
 405 string IPAddressV6::str() const {
 406   char buffer[INET6_ADDRSTRLEN] = {0};
 407   sockaddr_in6 sock = toSockAddr();
 408   if (!getnameinfo(
 409         (sockaddr*)&sock, sizeof(sock),
 410         buffer, INET6_ADDRSTRLEN,
 411         nullptr, 0, NI_NUMERICHOST)) {
 412     string ip(buffer);
 413     return ip;
 414   } else {
 415     throw IPAddressFormatException(to<std::string>(
 416         "Invalid address with hex ",
 417         "'",
 418         detail::Bytes::toHex(bytes(), 16),
 419         "'"));
 420   }
 421 }
 422
 423 // public
 424 string IPAddressV6::toFullyQualified() const {
 425   return detail::fastIpv6ToString(addr_.in6Addr_);
 426 }
 427
 428 // public
 429 string IPAddressV6::toInverseArpaName() const {
 430   constexpr folly::StringPiece lut = "0123456789abcdef";
 431   std::array<char, 32> a;
 432   int j = 0;
 433   for (int i = 15; i >= 0; i--) {
 434     a[j] = (lut[bytes()[i] & 0xf]);
 435     a[j + 1] = (lut[bytes()[i] >> 4]);
 436     j += 2;
 437   }
 438   return sformat("{}.ip6.arpa", join(".", a));
 439 }
 440
 441 // public
 442 uint8_t IPAddressV6::getNthMSByte(size_t byteIndex) const {
 443   const auto highestIndex = byteCount() - 1;
 444   if (byteIndex > highestIndex) {
 445     throw std::invalid_argument(to<string>("Byte index must be <= ",
 446         to<string>(highestIndex), " for addresses of type :",
 447         detail::familyNameStr(AF_INET6)));
 448   }
 449   return bytes()[byteIndex];
 450 }
 451
 452 // protected
 453 const ByteArray16 IPAddressV6::fetchMask(size_t numBits) {
 454   static const size_t bits = bitCount();
 455   if (numBits > bits) {
 456     throw IPAddressFormatException("IPv6 addresses are 128 bits.");
 457   }
 458   // masks_ is backed by an array so is zero indexed
 459   return masks_[numBits];
 460 }
 461
 462 // public static
 463 CIDRNetworkV6 IPAddressV6::longestCommonPrefix(
 464     const CIDRNetworkV6& one,
 465     const CIDRNetworkV6& two) {
 466   auto prefix = detail::Bytes::longestCommonPrefix(
 467       one.first.addr_.bytes_, one.second, two.first.addr_.bytes_, two.second);
 468   return {IPAddressV6(prefix.first), prefix.second};
 469 }
 470
 471 // protected
 472 bool IPAddressV6::inBinarySubnet(const std::array<uint8_t, 2> addr,
 473                                  size_t numBits) const {
 474   auto masked = mask(numBits);
 475   return (std::memcmp(addr.data(), masked.bytes(), 2) == 0);
 476 }
 477
 478 // static private
 479 const std::array<ByteArray16, 129> IPAddressV6::masks_ = {{
 480 /* /0   */ {{ 0x00,0x00,0x00,0x00,
 481              0x00,0x00,0x00,0x00,
 482              0x00,0x00,0x00,0x00,
 483              0x00,0x00,0x00,0x00 }},
 484 /* /1   */ {{ 0x80,0x00,0x00,0x00,
 485              0x00,0x00,0x00,0x00,
 486              0x00,0x00,0x00,0x00,
 487              0x00,0x00,0x00,0x00 }},
 488 /* /2   */ {{ 0xc0,0x00,0x00,0x00,
 489              0x00,0x00,0x00,0x00,
 490              0x00,0x00,0x00,0x00,
 491              0x00,0x00,0x00,0x00 }},
 492 /* /3   */ {{ 0xe0,0x00,0x00,0x00,
 493              0x00,0x00,0x00,0x00,
 494              0x00,0x00,0x00,0x00,
 495              0x00,0x00,0x00,0x00 }},
 496 /* /4   */ {{ 0xf0,0x00,0x00,0x00,
 497              0x00,0x00,0x00,0x00,
 498              0x00,0x00,0x00,0x00,
 499              0x00,0x00,0x00,0x00 }},
 500 /* /5   */ {{ 0xf8,0x00,0x00,0x00,
 501              0x00,0x00,0x00,0x00,
 502              0x00,0x00,0x00,0x00,
 503              0x00,0x00,0x00,0x00 }},
 504 /* /6   */ {{ 0xfc,0x00,0x00,0x00,
 505              0x00,0x00,0x00,0x00,
 506              0x00,0x00,0x00,0x00,
 507              0x00,0x00,0x00,0x00 }},
 508 /* /7   */ {{ 0xfe,0x00,0x00,0x00,
 509              0x00,0x00,0x00,0x00,
 510              0x00,0x00,0x00,0x00,
 511              0x00,0x00,0x00,0x00 }},
 512 /* /8   */ {{ 0xff,0x00,0x00,0x00,
 513              0x00,0x00,0x00,0x00,
 514              0x00,0x00,0x00,0x00,
 515              0x00,0x00,0x00,0x00 }},
 516 /* /9   */ {{ 0xff,0x80,0x00,0x00,
 517              0x00,0x00,0x00,0x00,
 518              0x00,0x00,0x00,0x00,
 519              0x00,0x00,0x00,0x00 }},
 520 /* /10  */ {{ 0xff,0xc0,0x00,0x00,
 521              0x00,0x00,0x00,0x00,
 522              0x00,0x00,0x00,0x00,
 523              0x00,0x00,0x00,0x00 }},
 524 /* /11  */ {{ 0xff,0xe0,0x00,0x00,
 525              0x00,0x00,0x00,0x00,
 526              0x00,0x00,0x00,0x00,
 527              0x00,0x00,0x00,0x00 }},
 528 /* /12  */ {{ 0xff,0xf0,0x00,0x00,
 529              0x00,0x00,0x00,0x00,
 530              0x00,0x00,0x00,0x00,
 531              0x00,0x00,0x00,0x00 }},
 532 /* /13  */ {{ 0xff,0xf8,0x00,0x00,
 533              0x00,0x00,0x00,0x00,
 534              0x00,0x00,0x00,0x00,
 535              0x00,0x00,0x00,0x00 }},
 536 /* /14  */ {{ 0xff,0xfc,0x00,0x00,
 537              0x00,0x00,0x00,0x00,
 538              0x00,0x00,0x00,0x00,
 539              0x00,0x00,0x00,0x00 }},
 540 /* /15  */ {{ 0xff,0xfe,0x00,0x00,
 541              0x00,0x00,0x00,0x00,
 542              0x00,0x00,0x00,0x00,
 543              0x00,0x00,0x00,0x00 }},
 544 /* /16  */ {{ 0xff,0xff,0x00,0x00,
 545              0x00,0x00,0x00,0x00,
 546              0x00,0x00,0x00,0x00,
 547              0x00,0x00,0x00,0x00 }},
 548 /* /17  */ {{ 0xff,0xff,0x80,0x00,
 549              0x00,0x00,0x00,0x00,
 550              0x00,0x00,0x00,0x00,
 551              0x00,0x00,0x00,0x00 }},
 552 /* /18  */ {{ 0xff,0xff,0xc0,0x00,
 553              0x00,0x00,0x00,0x00,
 554              0x00,0x00,0x00,0x00,
 555              0x00,0x00,0x00,0x00 }},
 556 /* /19  */ {{ 0xff,0xff,0xe0,0x00,
 557              0x00,0x00,0x00,0x00,
 558              0x00,0x00,0x00,0x00,
 559              0x00,0x00,0x00,0x00 }},
 560 /* /20  */ {{ 0xff,0xff,0xf0,0x00,
 561              0x00,0x00,0x00,0x00,
 562              0x00,0x00,0x00,0x00,
 563              0x00,0x00,0x00,0x00 }},
 564 /* /21  */ {{ 0xff,0xff,0xf8,0x00,
 565              0x00,0x00,0x00,0x00,
 566              0x00,0x00,0x00,0x00,
 567              0x00,0x00,0x00,0x00 }},
 568 /* /22  */ {{ 0xff,0xff,0xfc,0x00,
 569              0x00,0x00,0x00,0x00,
 570              0x00,0x00,0x00,0x00,
 571              0x00,0x00,0x00,0x00 }},
 572 /* /23  */ {{ 0xff,0xff,0xfe,0x00,
 573              0x00,0x00,0x00,0x00,
 574              0x00,0x00,0x00,0x00,
 575              0x00,0x00,0x00,0x00 }},
 576 /* /24  */ {{ 0xff,0xff,0xff,0x00,
 577              0x00,0x00,0x00,0x00,
 578              0x00,0x00,0x00,0x00,
 579              0x00,0x00,0x00,0x00 }},
 580 /* /25  */ {{ 0xff,0xff,0xff,0x80,
 581              0x00,0x00,0x00,0x00,
 582              0x00,0x00,0x00,0x00,
 583              0x00,0x00,0x00,0x00 }},
 584 /* /26  */ {{ 0xff,0xff,0xff,0xc0,
 585              0x00,0x00,0x00,0x00,
 586              0x00,0x00,0x00,0x00,
 587              0x00,0x00,0x00,0x00 }},
 588 /* /27  */ {{ 0xff,0xff,0xff,0xe0,
 589              0x00,0x00,0x00,0x00,
 590              0x00,0x00,0x00,0x00,
 591              0x00,0x00,0x00,0x00 }},
 592 /* /28  */ {{ 0xff,0xff,0xff,0xf0,
 593              0x00,0x00,0x00,0x00,
 594              0x00,0x00,0x00,0x00,
 595              0x00,0x00,0x00,0x00 }},
 596 /* /29  */ {{ 0xff,0xff,0xff,0xf8,
 597              0x00,0x00,0x00,0x00,
 598              0x00,0x00,0x00,0x00,
 599              0x00,0x00,0x00,0x00 }},
 600 /* /30  */ {{ 0xff,0xff,0xff,0xfc,
 601              0x00,0x00,0x00,0x00,
 602              0x00,0x00,0x00,0x00,
 603              0x00,0x00,0x00,0x00 }},
 604 /* /31  */ {{ 0xff,0xff,0xff,0xfe,
 605              0x00,0x00,0x00,0x00,
 606              0x00,0x00,0x00,0x00,
 607              0x00,0x00,0x00,0x00 }},
 608 /* /32  */ {{ 0xff,0xff,0xff,0xff,
 609              0x00,0x00,0x00,0x00,
 610              0x00,0x00,0x00,0x00,
 611              0x00,0x00,0x00,0x00 }},
 612 /* /33  */ {{ 0xff,0xff,0xff,0xff,
 613              0x80,0x00,0x00,0x00,
 614              0x00,0x00,0x00,0x00,
 615              0x00,0x00,0x00,0x00 }},
 616 /* /34  */ {{ 0xff,0xff,0xff,0xff,
 617              0xc0,0x00,0x00,0x00,
 618              0x00,0x00,0x00,0x00,
 619              0x00,0x00,0x00,0x00 }},
 620 /* /35  */ {{ 0xff,0xff,0xff,0xff,
 621              0xe0,0x00,0x00,0x00,
 622              0x00,0x00,0x00,0x00,
 623              0x00,0x00,0x00,0x00 }},
 624 /* /36  */ {{ 0xff,0xff,0xff,0xff,
 625              0xf0,0x00,0x00,0x00,
 626              0x00,0x00,0x00,0x00,
 627              0x00,0x00,0x00,0x00 }},
 628 /* /37  */ {{ 0xff,0xff,0xff,0xff,
 629              0xf8,0x00,0x00,0x00,
 630              0x00,0x00,0x00,0x00,
 631              0x00,0x00,0x00,0x00 }},
 632 /* /38  */ {{ 0xff,0xff,0xff,0xff,
 633              0xfc,0x00,0x00,0x00,
 634              0x00,0x00,0x00,0x00,
 635              0x00,0x00,0x00,0x00 }},
 636 /* /39  */ {{ 0xff,0xff,0xff,0xff,
 637              0xfe,0x00,0x00,0x00,
 638              0x00,0x00,0x00,0x00,
 639              0x00,0x00,0x00,0x00 }},
 640 /* /40  */ {{ 0xff,0xff,0xff,0xff,
 641              0xff,0x00,0x00,0x00,
 642              0x00,0x00,0x00,0x00,
 643              0x00,0x00,0x00,0x00 }},
 644 /* /41  */ {{ 0xff,0xff,0xff,0xff,
 645              0xff,0x80,0x00,0x00,
 646              0x00,0x00,0x00,0x00,
 647              0x00,0x00,0x00,0x00 }},
 648 /* /42  */ {{ 0xff,0xff,0xff,0xff,
 649              0xff,0xc0,0x00,0x00,
 650              0x00,0x00,0x00,0x00,
 651              0x00,0x00,0x00,0x00 }},
 652 /* /43  */ {{ 0xff,0xff,0xff,0xff,
 653              0xff,0xe0,0x00,0x00,
 654              0x00,0x00,0x00,0x00,
 655              0x00,0x00,0x00,0x00 }},
 656 /* /44  */ {{ 0xff,0xff,0xff,0xff,
 657              0xff,0xf0,0x00,0x00,
 658              0x00,0x00,0x00,0x00,
 659              0x00,0x00,0x00,0x00 }},
 660 /* /45  */ {{ 0xff,0xff,0xff,0xff,
 661              0xff,0xf8,0x00,0x00,
 662              0x00,0x00,0x00,0x00,
 663              0x00,0x00,0x00,0x00 }},
 664 /* /46  */ {{ 0xff,0xff,0xff,0xff,
 665              0xff,0xfc,0x00,0x00,
 666              0x00,0x00,0x00,0x00,
 667              0x00,0x00,0x00,0x00 }},
 668 /* /47  */ {{ 0xff,0xff,0xff,0xff,
 669              0xff,0xfe,0x00,0x00,
 670              0x00,0x00,0x00,0x00,
 671              0x00,0x00,0x00,0x00 }},
 672 /* /48  */ {{ 0xff,0xff,0xff,0xff,
 673              0xff,0xff,0x00,0x00,
 674              0x00,0x00,0x00,0x00,
 675              0x00,0x00,0x00,0x00 }},
 676 /* /49  */ {{ 0xff,0xff,0xff,0xff,
 677              0xff,0xff,0x80,0x00,
 678              0x00,0x00,0x00,0x00,
 679              0x00,0x00,0x00,0x00 }},
 680 /* /50  */ {{ 0xff,0xff,0xff,0xff,
 681              0xff,0xff,0xc0,0x00,
 682              0x00,0x00,0x00,0x00,
 683              0x00,0x00,0x00,0x00 }},
 684 /* /51  */ {{ 0xff,0xff,0xff,0xff,
 685              0xff,0xff,0xe0,0x00,
 686              0x00,0x00,0x00,0x00,
 687              0x00,0x00,0x00,0x00 }},
 688 /* /52  */ {{ 0xff,0xff,0xff,0xff,
 689              0xff,0xff,0xf0,0x00,
 690              0x00,0x00,0x00,0x00,
 691              0x00,0x00,0x00,0x00 }},
 692 /* /53  */ {{ 0xff,0xff,0xff,0xff,
 693              0xff,0xff,0xf8,0x00,
 694              0x00,0x00,0x00,0x00,
 695              0x00,0x00,0x00,0x00 }},
 696 /* /54  */ {{ 0xff,0xff,0xff,0xff,
 697              0xff,0xff,0xfc,0x00,
 698              0x00,0x00,0x00,0x00,
 699              0x00,0x00,0x00,0x00 }},
 700 /* /55  */ {{ 0xff,0xff,0xff,0xff,
 701              0xff,0xff,0xfe,0x00,
 702              0x00,0x00,0x00,0x00,
 703              0x00,0x00,0x00,0x00 }},
 704 /* /56  */ {{ 0xff,0xff,0xff,0xff,
 705              0xff,0xff,0xff,0x00,
 706              0x00,0x00,0x00,0x00,
 707              0x00,0x00,0x00,0x00 }},
 708 /* /57  */ {{ 0xff,0xff,0xff,0xff,
 709              0xff,0xff,0xff,0x80,
 710              0x00,0x00,0x00,0x00,
 711              0x00,0x00,0x00,0x00 }},
 712 /* /58  */ {{ 0xff,0xff,0xff,0xff,
 713              0xff,0xff,0xff,0xc0,
 714              0x00,0x00,0x00,0x00,
 715              0x00,0x00,0x00,0x00 }},
 716 /* /59  */ {{ 0xff,0xff,0xff,0xff,
 717              0xff,0xff,0xff,0xe0,
 718              0x00,0x00,0x00,0x00,
 719              0x00,0x00,0x00,0x00 }},
 720 /* /60  */ {{ 0xff,0xff,0xff,0xff,
 721              0xff,0xff,0xff,0xf0,
 722              0x00,0x00,0x00,0x00,
 723              0x00,0x00,0x00,0x00 }},
 724 /* /61  */ {{ 0xff,0xff,0xff,0xff,
 725              0xff,0xff,0xff,0xf8,
 726              0x00,0x00,0x00,0x00,
 727              0x00,0x00,0x00,0x00 }},
 728 /* /62  */ {{ 0xff,0xff,0xff,0xff,
 729              0xff,0xff,0xff,0xfc,
 730              0x00,0x00,0x00,0x00,
 731              0x00,0x00,0x00,0x00 }},
 732 /* /63  */ {{ 0xff,0xff,0xff,0xff,
 733              0xff,0xff,0xff,0xfe,
 734              0x00,0x00,0x00,0x00,
 735              0x00,0x00,0x00,0x00 }},
 736 /* /64  */ {{ 0xff,0xff,0xff,0xff,
 737              0xff,0xff,0xff,0xff,
 738              0x00,0x00,0x00,0x00,
 739              0x00,0x00,0x00,0x00 }},
 740 /* /65  */ {{ 0xff,0xff,0xff,0xff,
 741              0xff,0xff,0xff,0xff,
 742              0x80,0x00,0x00,0x00,
 743              0x00,0x00,0x00,0x00 }},
 744 /* /66  */ {{ 0xff,0xff,0xff,0xff,
 745              0xff,0xff,0xff,0xff,
 746              0xc0,0x00,0x00,0x00,
 747              0x00,0x00,0x00,0x00 }},
 748 /* /67  */ {{ 0xff,0xff,0xff,0xff,
 749              0xff,0xff,0xff,0xff,
 750              0xe0,0x00,0x00,0x00,
 751              0x00,0x00,0x00,0x00 }},
 752 /* /68  */ {{ 0xff,0xff,0xff,0xff,
 753              0xff,0xff,0xff,0xff,
 754              0xf0,0x00,0x00,0x00,
 755              0x00,0x00,0x00,0x00 }},
 756 /* /69  */ {{ 0xff,0xff,0xff,0xff,
 757              0xff,0xff,0xff,0xff,
 758              0xf8,0x00,0x00,0x00,
 759              0x00,0x00,0x00,0x00 }},
 760 /* /70  */ {{ 0xff,0xff,0xff,0xff,
 761              0xff,0xff,0xff,0xff,
 762              0xfc,0x00,0x00,0x00,
 763              0x00,0x00,0x00,0x00 }},
 764 /* /71  */ {{ 0xff,0xff,0xff,0xff,
 765              0xff,0xff,0xff,0xff,
 766              0xfe,0x00,0x00,0x00,
 767              0x00,0x00,0x00,0x00 }},
 768 /* /72  */ {{ 0xff,0xff,0xff,0xff,
 769              0xff,0xff,0xff,0xff,
 770              0xff,0x00,0x00,0x00,
 771              0x00,0x00,0x00,0x00 }},
 772 /* /73  */ {{ 0xff,0xff,0xff,0xff,
 773              0xff,0xff,0xff,0xff,
 774              0xff,0x80,0x00,0x00,
 775              0x00,0x00,0x00,0x00 }},
 776 /* /74  */ {{ 0xff,0xff,0xff,0xff,
 777              0xff,0xff,0xff,0xff,
 778              0xff,0xc0,0x00,0x00,
 779              0x00,0x00,0x00,0x00 }},
 780 /* /75  */ {{ 0xff,0xff,0xff,0xff,
 781              0xff,0xff,0xff,0xff,
 782              0xff,0xe0,0x00,0x00,
 783              0x00,0x00,0x00,0x00 }},
 784 /* /76  */ {{ 0xff,0xff,0xff,0xff,
 785              0xff,0xff,0xff,0xff,
 786              0xff,0xf0,0x00,0x00,
 787              0x00,0x00,0x00,0x00 }},
 788 /* /77  */ {{ 0xff,0xff,0xff,0xff,
 789              0xff,0xff,0xff,0xff,
 790              0xff,0xf8,0x00,0x00,
 791              0x00,0x00,0x00,0x00 }},
 792 /* /78  */ {{ 0xff,0xff,0xff,0xff,
 793              0xff,0xff,0xff,0xff,
 794              0xff,0xfc,0x00,0x00,
 795              0x00,0x00,0x00,0x00 }},
 796 /* /79  */ {{ 0xff,0xff,0xff,0xff,
 797              0xff,0xff,0xff,0xff,
 798              0xff,0xfe,0x00,0x00,
 799              0x00,0x00,0x00,0x00 }},
 800 /* /80  */ {{ 0xff,0xff,0xff,0xff,
 801              0xff,0xff,0xff,0xff,
 802              0xff,0xff,0x00,0x00,
 803              0x00,0x00,0x00,0x00 }},
 804 /* /81  */ {{ 0xff,0xff,0xff,0xff,
 805              0xff,0xff,0xff,0xff,
 806              0xff,0xff,0x80,0x00,
 807              0x00,0x00,0x00,0x00 }},
 808 /* /82  */ {{ 0xff,0xff,0xff,0xff,
 809              0xff,0xff,0xff,0xff,
 810              0xff,0xff,0xc0,0x00,
 811              0x00,0x00,0x00,0x00 }},
 812 /* /83  */ {{ 0xff,0xff,0xff,0xff,
 813              0xff,0xff,0xff,0xff,
 814              0xff,0xff,0xe0,0x00,
 815              0x00,0x00,0x00,0x00 }},
 816 /* /84  */ {{ 0xff,0xff,0xff,0xff,
 817              0xff,0xff,0xff,0xff,
 818              0xff,0xff,0xf0,0x00,
 819              0x00,0x00,0x00,0x00 }},
 820 /* /85  */ {{ 0xff,0xff,0xff,0xff,
 821              0xff,0xff,0xff,0xff,
 822              0xff,0xff,0xf8,0x00,
 823              0x00,0x00,0x00,0x00 }},
 824 /* /86  */ {{ 0xff,0xff,0xff,0xff,
 825              0xff,0xff,0xff,0xff,
 826              0xff,0xff,0xfc,0x00,
 827              0x00,0x00,0x00,0x00 }},
 828 /* /87  */ {{ 0xff,0xff,0xff,0xff,
 829              0xff,0xff,0xff,0xff,
 830              0xff,0xff,0xfe,0x00,
 831              0x00,0x00,0x00,0x00 }},
 832 /* /88  */ {{ 0xff,0xff,0xff,0xff,
 833              0xff,0xff,0xff,0xff,
 834              0xff,0xff,0xff,0x00,
 835              0x00,0x00,0x00,0x00 }},
 836 /* /89  */ {{ 0xff,0xff,0xff,0xff,
 837              0xff,0xff,0xff,0xff,
 838              0xff,0xff,0xff,0x80,
 839              0x00,0x00,0x00,0x00 }},
 840 /* /90  */ {{ 0xff,0xff,0xff,0xff,
 841              0xff,0xff,0xff,0xff,
 842              0xff,0xff,0xff,0xc0,
 843              0x00,0x00,0x00,0x00 }},
 844 /* /91  */ {{ 0xff,0xff,0xff,0xff,
 845              0xff,0xff,0xff,0xff,
 846              0xff,0xff,0xff,0xe0,
 847              0x00,0x00,0x00,0x00 }},
 848 /* /92  */ {{ 0xff,0xff,0xff,0xff,
 849              0xff,0xff,0xff,0xff,
 850              0xff,0xff,0xff,0xf0,
 851              0x00,0x00,0x00,0x00 }},
 852 /* /93  */ {{ 0xff,0xff,0xff,0xff,
 853              0xff,0xff,0xff,0xff,
 854              0xff,0xff,0xff,0xf8,
 855              0x00,0x00,0x00,0x00 }},
 856 /* /94  */ {{ 0xff,0xff,0xff,0xff,
 857              0xff,0xff,0xff,0xff,
 858              0xff,0xff,0xff,0xfc,
 859              0x00,0x00,0x00,0x00 }},
 860 /* /95  */ {{ 0xff,0xff,0xff,0xff,
 861              0xff,0xff,0xff,0xff,
 862              0xff,0xff,0xff,0xfe,
 863              0x00,0x00,0x00,0x00 }},
 864 /* /96  */ {{ 0xff,0xff,0xff,0xff,
 865              0xff,0xff,0xff,0xff,
 866              0xff,0xff,0xff,0xff,
 867              0x00,0x00,0x00,0x00 }},
 868 /* /97  */ {{ 0xff,0xff,0xff,0xff,
 869              0xff,0xff,0xff,0xff,
 870              0xff,0xff,0xff,0xff,
 871              0x80,0x00,0x00,0x00 }},
 872 /* /98  */ {{ 0xff,0xff,0xff,0xff,
 873              0xff,0xff,0xff,0xff,
 874              0xff,0xff,0xff,0xff,
 875              0xc0,0x00,0x00,0x00 }},
 876 /* /99  */ {{ 0xff,0xff,0xff,0xff,
 877              0xff,0xff,0xff,0xff,
 878              0xff,0xff,0xff,0xff,
 879              0xe0,0x00,0x00,0x00 }},
 880 /* /100 */ {{ 0xff,0xff,0xff,0xff,
 881              0xff,0xff,0xff,0xff,
 882              0xff,0xff,0xff,0xff,
 883              0xf0,0x00,0x00,0x00 }},
 884 /* /101 */ {{ 0xff,0xff,0xff,0xff,
 885              0xff,0xff,0xff,0xff,
 886              0xff,0xff,0xff,0xff,
 887              0xf8,0x00,0x00,0x00 }},
 888 /* /102 */ {{ 0xff,0xff,0xff,0xff,
 889              0xff,0xff,0xff,0xff,
 890              0xff,0xff,0xff,0xff,
 891              0xfc,0x00,0x00,0x00 }},
 892 /* /103 */ {{ 0xff,0xff,0xff,0xff,
 893              0xff,0xff,0xff,0xff,
 894              0xff,0xff,0xff,0xff,
 895              0xfe,0x00,0x00,0x00 }},
 896 /* /104 */ {{ 0xff,0xff,0xff,0xff,
 897              0xff,0xff,0xff,0xff,
 898              0xff,0xff,0xff,0xff,
 899              0xff,0x00,0x00,0x00 }},
 900 /* /105 */ {{ 0xff,0xff,0xff,0xff,
 901              0xff,0xff,0xff,0xff,
 902              0xff,0xff,0xff,0xff,
 903              0xff,0x80,0x00,0x00 }},
 904 /* /106 */ {{ 0xff,0xff,0xff,0xff,
 905              0xff,0xff,0xff,0xff,
 906              0xff,0xff,0xff,0xff,
 907              0xff,0xc0,0x00,0x00 }},
 908 /* /107 */ {{ 0xff,0xff,0xff,0xff,
 909              0xff,0xff,0xff,0xff,
 910              0xff,0xff,0xff,0xff,
 911              0xff,0xe0,0x00,0x00 }},
 912 /* /108 */ {{ 0xff,0xff,0xff,0xff,
 913              0xff,0xff,0xff,0xff,
 914              0xff,0xff,0xff,0xff,
 915              0xff,0xf0,0x00,0x00 }},
 916 /* /109 */ {{ 0xff,0xff,0xff,0xff,
 917              0xff,0xff,0xff,0xff,
 918              0xff,0xff,0xff,0xff,
 919              0xff,0xf8,0x00,0x00 }},
 920 /* /110 */ {{ 0xff,0xff,0xff,0xff,
 921              0xff,0xff,0xff,0xff,
 922              0xff,0xff,0xff,0xff,
 923              0xff,0xfc,0x00,0x00 }},
 924 /* /111 */ {{ 0xff,0xff,0xff,0xff,
 925              0xff,0xff,0xff,0xff,
 926              0xff,0xff,0xff,0xff,
 927              0xff,0xfe,0x00,0x00 }},
 928 /* /112 */ {{ 0xff,0xff,0xff,0xff,
 929              0xff,0xff,0xff,0xff,
 930              0xff,0xff,0xff,0xff,
 931              0xff,0xff,0x00,0x00 }},
 932 /* /113 */ {{ 0xff,0xff,0xff,0xff,
 933              0xff,0xff,0xff,0xff,
 934              0xff,0xff,0xff,0xff,
 935              0xff,0xff,0x80,0x00 }},
 936 /* /114 */ {{ 0xff,0xff,0xff,0xff,
 937              0xff,0xff,0xff,0xff,
 938              0xff,0xff,0xff,0xff,
 939              0xff,0xff,0xc0,0x00 }},
 940 /* /115 */ {{ 0xff,0xff,0xff,0xff,
 941              0xff,0xff,0xff,0xff,
 942              0xff,0xff,0xff,0xff,
 943              0xff,0xff,0xe0,0x00 }},
 944 /* /116 */ {{ 0xff,0xff,0xff,0xff,
 945              0xff,0xff,0xff,0xff,
 946              0xff,0xff,0xff,0xff,
 947              0xff,0xff,0xf0,0x00 }},
 948 /* /117 */ {{ 0xff,0xff,0xff,0xff,
 949              0xff,0xff,0xff,0xff,
 950              0xff,0xff,0xff,0xff,
 951              0xff,0xff,0xf8,0x00 }},
 952 /* /118 */ {{ 0xff,0xff,0xff,0xff,
 953              0xff,0xff,0xff,0xff,
 954              0xff,0xff,0xff,0xff,
 955              0xff,0xff,0xfc,0x00 }},
 956 /* /119 */ {{ 0xff,0xff,0xff,0xff,
 957              0xff,0xff,0xff,0xff,
 958              0xff,0xff,0xff,0xff,
 959              0xff,0xff,0xfe,0x00 }},
 960 /* /120 */ {{ 0xff,0xff,0xff,0xff,
 961              0xff,0xff,0xff,0xff,
 962              0xff,0xff,0xff,0xff,
 963              0xff,0xff,0xff,0x00 }},
 964 /* /121 */ {{ 0xff,0xff,0xff,0xff,
 965              0xff,0xff,0xff,0xff,
 966              0xff,0xff,0xff,0xff,
 967              0xff,0xff,0xff,0x80 }},
 968 /* /122 */ {{ 0xff,0xff,0xff,0xff,
 969              0xff,0xff,0xff,0xff,
 970              0xff,0xff,0xff,0xff,
 971              0xff,0xff,0xff,0xc0 }},
 972 /* /123 */ {{ 0xff,0xff,0xff,0xff,
 973              0xff,0xff,0xff,0xff,
 974              0xff,0xff,0xff,0xff,
 975              0xff,0xff,0xff,0xe0 }},
 976 /* /124 */ {{ 0xff,0xff,0xff,0xff,
 977              0xff,0xff,0xff,0xff,
 978              0xff,0xff,0xff,0xff,
 979              0xff,0xff,0xff,0xf0 }},
 980 /* /125 */ {{ 0xff,0xff,0xff,0xff,
 981              0xff,0xff,0xff,0xff,
 982              0xff,0xff,0xff,0xff,
 983              0xff,0xff,0xff,0xf8 }},
 984 /* /126 */ {{ 0xff,0xff,0xff,0xff,
 985              0xff,0xff,0xff,0xff,
 986              0xff,0xff,0xff,0xff,
 987              0xff,0xff,0xff,0xfc }},
 988 /* /127 */ {{ 0xff,0xff,0xff,0xff,
 989              0xff,0xff,0xff,0xff,
 990              0xff,0xff,0xff,0xff,
 991              0xff,0xff,0xff,0xfe }},
 992 /* /128 */ {{ 0xff,0xff,0xff,0xff,
 993              0xff,0xff,0xff,0xff,
 994              0xff,0xff,0xff,0xff,
 995              0xff,0xff,0xff,0xff }},
 996 }};
 997
 998 } // folly