folly/IPAddressV6.cpp

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