text: // Copyright 2002 Google Inc. All Rights Reserved.
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  //     http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS-IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  //
  
  #ifndef S2_UTIL_BITS_BITS_H_
  #define S2_UTIL_BITS_BITS_H_
  
  //
  // Various bit-twiddling functions, all of which are static members of the Bits
  // class (making it effectively a namespace). Operands are unsigned integers.
  // Munging bits in _signed_ integers is fraught with peril! For example,
  // -5 << n has undefined behavior (for some values of n).
  //
  // Bits provide the following:
  //
  //   * Count(Ones.*|LeadingZeros.*)? . In a similar vein, there's also the
  //     Find[LM]SBSetNonZero.* family of functions. You can think of them as
  //     (trailing|leading) zero bit count + 1. Also in a similar vein,
  //     (Capped)?Difference, which count the number of one bits in foo ^ bar.
  //
  //   * ReverseBits${power_of_two}
  //
  //   * Log2(Floor|Ceiling)(NonZero)?.* - The NonZero variants have undefined
  //     behavior if argument is 0.
  //
  //   * Bytes(ContainByte(LessThan)?|AllInRange) - These scan a sequence of bytes
  //     looking for one with(out)? some property.
  //
  //   * (Get|Set|Copy)Bits
  //
  //   * GetLowBits - Extract N lowest bits from value.
  //
  // The only other thing is BitPattern, which is a trait class template (not in
  // Bits) containing a few bit patterns (which vary based on value of template
  // parameter).
  
  #include "absl/base/casts.h"
  #include "absl/numeric/int128.h"
  #if defined(__i386__) || defined(__x86_64__)
  #include <x86intrin.h>
  #endif
  
  #include <type_traits>
  
  #include "s2/base/integral_types.h"
  #include "s2/base/logging.h"
  #include "s2/base/port.h"
  #include "absl/base/macros.h"
  
  namespace s2 {
  
  class Bits {
   public:
    // A traits class template for unsigned integer type sizes. Primary
    // information contained herein is corresponding (unsigned) integer type.
    // E.g. UnsignedTypeBySize<32>::Type is uint32. Used by UnsignedType.
    template<int size /* in bytes */>
    struct UnsignedTypeBySize;
  
    // Auxiliary struct for figuring out an unsigned type for a given type.
    template<typename T> struct UnsignedType {
      typedef typename UnsignedTypeBySize<sizeof(T)>::Type Type;
    };
  
    // Return the number of one bits in the given integer.
    static int CountOnesInByte(unsigned char n);
  
    static int CountOnes(uint32 n) {
  #if defined(__powerpc64__) && defined(__GNUC__)
      // Use popcount builtin if we know it is inlined and fast.
      return PopcountWithBuiltin(n);
  #elif (defined(__i386__) || defined(__x86_64__)) && defined(__POPCNT__) && \
      defined(__GNUC__)
      return PopcountWithBuiltin(n);
  #else
      n -= ((n >> 1) & 0x55555555);
      n = ((n >> 2) & 0x33333333) + (n & 0x33333333);
      return static_cast<int>((((n + (n >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24);
  #endif
    }
  
    // Count bits using sideways addition [WWG'57]. See Knuth TAOCP v4 7.1.3(59)
    static inline int CountOnes64(uint64 n) {
  #if defined(__powerpc64__) && defined(__GNUC__)
      return PopcountWithBuiltin(n);
  #elif defined(__x86_64__) && defined(__POPCNT__) && defined(__GNUC__)
      return PopcountWithBuiltin(n);
  #elif defined(_LP64)
      n -= (n >> 1) & 0x5555555555555555ULL;
      n = ((n >> 2) & 0x3333333333333333ULL) + (n & 0x3333333333333333ULL);
      return static_cast<int>(
          (((n + (n >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56);
  #else
      return CountOnes(n >> 32) + CountOnes(n & 0xffffffff);
  #endif
    }
  
    // Count bits in uint128
    static inline int CountOnes128(absl::uint128 n) {
      return Bits::CountOnes64(absl::Uint128High64(n)) +
             Bits::CountOnes64(absl::Uint128Low64(n));
    }
  
    // Count leading zeroes.  This is similar to wordsize - 1 - floor(log2(n)).
    // Returns number of bits if n is 0.
    static inline int CountLeadingZeros32(uint32 n) {
      // Instead of using __builtin_clz(), we explicitly write target specific
      // assembly because we want to handle n == 0.  If we used __builtin_clz(),
      // we would need to use something like "n ? __builtin_clz(n) : 32".  The
      // check is not necessary on POWER and aarch64 but we cannot depend on
      // that because __builtin_clz(0) is documented to be undefined.
  #if defined(__aarch64__) && defined(__GNUC__)
      int32 count;
      asm("clz %w0,%w1" : "=r"(count) : "r"(n));
      return count;
  #elif (defined(__i386__) || defined(__x86_64__)) && defined(__LZCNT__) && \
      defined(__GNUC__)
      return __lzcnt32(n);
  #elif (defined(__i386__) || defined(__x86_64__)) && defined(__GNUC__)
      if (n == 0) return 32;
      int32 idx;
      asm("bsr %1, %0"
          : "=r"(idx)
          : "ro"(n)
          : "cc");              // bsr writes Z flag
      return 31 ^ idx;
  #elif defined(__powerpc64__) && defined(__GNUC__)
      int32 count;
      asm("cntlzw %0,%1" : "=r"(count) : "r"(n));
      return count;
  #elif defined(__GNUC__)
      return CountLeadingZerosWithBuiltin(n);
  #else
      return CountLeadingZeros32_Portable(n);
  #endif
    }
  
    static inline int CountLeadingZeros64(uint64 n) {
  #if defined(__aarch64__) && defined(__GNUC__)
      int64 count;
      asm("clz %0,%1" : "=r"(count) : "r"(n));
      return static_cast<int>(count);
  #elif defined(__powerpc64__) && defined(__GNUC__)
      int64 count;
      asm("cntlzd %0,%1" : "=r"(count) : "r"(n));
      return static_cast<int>(count);
  #elif (defined(__i386__) || defined(__x86_64__)) && defined(__LZCNT__) && \
      defined(__GNUC__)
      return __lzcnt64(n);
  #elif defined(__x86_64__) && defined(__GNUC__)
      if (n == 0) return 64;
      int64 idx;
      asm ("bsr %1, %0"
           : "=r"(idx)
           : "ro"(n)
           : "cc");              // bsr writes Z flag
      return static_cast<int>(63 ^ idx);
  #elif defined(__GNUC__)
      return CountLeadingZerosWithBuiltin(n);
  #else
      return CountLeadingZeros64_Portable(n);
  #endif
    }
  
    static inline int CountLeadingZeros128(absl::uint128 n) {
      if (uint64 hi = absl::Uint128High64(n))
        return Bits::CountLeadingZeros64(hi);
      return Bits::CountLeadingZeros64(absl::Uint128Low64(n)) + 64;
    }
  
    // Reverse the bits in the given integer.
    static uint8 ReverseBits8(uint8 n);
    static uint32 ReverseBits32(uint32 n);
    static uint64 ReverseBits64(uint64 n);
    static absl::uint128 ReverseBits128(absl::uint128 n);
  
    // Return the number of one bits in the byte sequence.
    static int Count(const void *m, int num_bytes);
  
    // Return the number of different bits in the given byte sequences.
    // (i.e., the Hamming distance)
    static int Difference(const void *m1, const void *m2, int num_bytes);
  
    // Return the number of different bits in the given byte sequences,
    // up to a maximum.  Values larger than the maximum may be returned
    // (because multiple bits are checked at a time), but the function
    // may exit early if the cap is exceeded.
    static int CappedDifference(const void *m1, const void *m2,
                                int num_bytes, int cap);
  
    // Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0.
    static int Log2Floor(uint32 n);
    static int Log2Floor64(uint64 n);
    static int Log2Floor128(absl::uint128 n);
  
    // Potentially faster version of Log2Floor() that returns an
    // undefined value if n == 0
    static int Log2FloorNonZero(uint32 n);
    static int Log2FloorNonZero64(uint64 n);
    static int Log2FloorNonZero128(absl::uint128 n);
  
    // Return ceiling(log2(n)) for positive integer n.  Returns -1 iff n == 0.
    static int Log2Ceiling(uint32 n);
    static int Log2Ceiling64(uint64 n);
    static int Log2Ceiling128(absl::uint128 n);
  
    // Return the first set least / most significant bit, 0-indexed.  Returns an
    // undefined value if n == 0.  FindLSBSetNonZero() is similar to ffs() except
    // that it's 0-indexed, while FindMSBSetNonZero() is the same as
    // Log2FloorNonZero().
    static int FindLSBSetNonZero(uint32 n);
    static int FindLSBSetNonZero64(uint64 n);
    static int FindLSBSetNonZero128(absl::uint128 n);
    static int FindMSBSetNonZero(uint32 n) { return Log2FloorNonZero(n); }
    static int FindMSBSetNonZero64(uint64 n) { return Log2FloorNonZero64(n); }
    static int FindMSBSetNonZero128(absl::uint128 n) {
      return Log2FloorNonZero128(n);
    }
  
    // Viewing bytes as a stream of unsigned bytes, does that stream
    // contain any byte equal to c?
    template <class T> static bool BytesContainByte(T bytes, uint8 c);
  
    // Viewing bytes as a stream of unsigned bytes, does that stream
    // contain any byte b < c?
    template <class T> static bool BytesContainByteLessThan(T bytes, uint8 c);
  
    // Viewing bytes as a stream of unsigned bytes, are all elements of that
    // stream in [lo, hi]?
    template <class T> static bool BytesAllInRange(T bytes, uint8 lo, uint8 hi);
  
    // Extract 'nbits' consecutive bits from 'src'.  Position of bits are
    // specified by 'offset' from the LSB.  'T' is a scalar type (integral,
    // float or pointer) whose size is the same as one of the unsigned types.
    // The return type is an unsigned type having the same size as T.
    template<typename T>
    static typename UnsignedType<T>::Type GetBits(const T src,
                                                  const int offset,
                                                  const int nbits) {
      typedef typename UnsignedType<T>::Type UnsignedT;
      const UnsignedT unsigned_src = absl::bit_cast<UnsignedT>(src);
      S2_DCHECK_GT(sizeof(UnsignedT) * 8, offset);
      S2_DCHECK_GE(sizeof(UnsignedT) * 8, offset + nbits);
      return GetBitsImpl(unsigned_src, offset, nbits);
    }
  
    // Overwrite 'nbits' consecutive bits of 'dest.'.  Position of bits are
    // specified by an offset from the LSB.  'T' is a scalar type (integral,
    // float or pointer) whose size is the same as one of the unsigned types.
    template<typename T>
    static void SetBits(const typename UnsignedType<T>::Type value,
                        const int offset,
                        const int nbits,
                        T* const dest) {
      typedef typename UnsignedType<T>::Type UnsignedT;
      const UnsignedT unsigned_dest = absl::bit_cast<UnsignedT>(*dest);
      S2_DCHECK_GT(sizeof(UnsignedT) * 8, offset);
      S2_DCHECK_GE(sizeof(UnsignedT) * 8, offset + nbits);
      const UnsignedT mask = NBitsFromLSB<UnsignedT>(nbits);
      const UnsignedT unsigned_result =
          (unsigned_dest & ~(mask << offset)) | ((value & mask) << offset);
      *dest = absl::bit_cast<T>(unsigned_result);
    }
  
    // Combine SetBits and GetBits for convenience.  This is meant to be a
    // replacement for BitCopy() for some use cases.  Unlike BitCopy(),
    // Bits::CopyBits() operating on multibyte types has the same behavior on
    // big-endian and little-endian machines. Sample usage:
    //
    // uint32 a, b;
    // Bits::CopyBits(&a, 0, b, 12, 3);
    template<typename DestType, typename SrcType>
    static void CopyBits(DestType* const dest,
                         const int dest_offset,
                         const SrcType src,
                         const int src_offset,
                         const int nbits) {
      const typename UnsignedType<SrcType>::Type value =
          GetBits(src, src_offset, nbits);
      SetBits(value, dest_offset, nbits, dest);
    }
  
    // Extract the lowest 'nbits' consecutive bits from 'src'.
    // Bits::GetLowBits(13, 3); /* = 5 (0b1101 => 0b101) */
    template<typename T>
    static typename UnsignedType<T>::Type GetLowBits(const T src,
                                                     const int nbits) {
      typedef typename UnsignedType<T>::Type UnsignedT;
      const UnsignedT unsigned_src = absl::bit_cast<UnsignedT>(src);
      S2_DCHECK_GE(sizeof(UnsignedT) * 8, nbits);
      return GetLowBitsImpl(unsigned_src, nbits);
    }
  
   private:
    // We only use this for unsigned types and for 0 <= n <= sizeof(UnsignedT).
    template<typename UnsignedT>
    static UnsignedT NBitsFromLSB(const int nbits) {
      const UnsignedT all_ones = ~static_cast<UnsignedT>(0);
      return nbits == 0 ? static_cast<UnsignedT>(0)
                        : all_ones >> (sizeof(UnsignedT) * 8 - nbits);
    }
  
    template<typename UnsignedT>
    static inline UnsignedT GetBitsImpl(const UnsignedT src,
                                        const int offset,
                                        const int nbits);
    template <typename UnsignedT>
    static inline UnsignedT GetLowBitsImpl(const UnsignedT src, const int nbits);
  
  #ifdef __GNUC__
    static int CountLeadingZerosWithBuiltin(unsigned n);
    // NOLINTNEXTLINE(runtime/int)
    static int CountLeadingZerosWithBuiltin(unsigned long n);
    // NOLINTNEXTLINE(runtime/int)
    static int CountLeadingZerosWithBuiltin(unsigned long long n);
    static int PopcountWithBuiltin(unsigned n);
    static int PopcountWithBuiltin(unsigned long n);       // NOLINT(runtime/int)
    static int PopcountWithBuiltin(unsigned long long n);  // NOLINT(runtime/int)
  #if defined(__BMI__) && (defined(__i386__) || defined(__x86_64__))
    static inline uint32 GetBitsImpl(const uint32 src,
                                     const int offset,
                                     const int nbits);
  #endif
  #if defined(__BMI__) && defined(__x86_64__)
    static inline uint64 GetBitsImpl(const uint64 src,
                                     const int offset,
                                     const int nbits);
  #endif
  #if defined(__BMI2__) && (defined(__i386__) || defined(__x86_64__))
    static inline uint32 GetLowBitsImpl(const uint32 src, const int nbits);
  #endif
  #if defined(__BMI2__) && defined(__x86_64__)
    static inline uint64 GetLowBitsImpl(const uint64 src, const int nbits);
  #endif
  #endif  // __GNUC__
  
    // Portable implementations.
    static int Log2Floor_Portable(uint32 n);
    static int Log2Floor64_Portable(uint64 n);
    static int Log2FloorNonZero_Portable(uint32 n);
    static int Log2FloorNonZero64_Portable(uint64 n);
    static int CountLeadingZeros32_Portable(uint32 n);
    static int CountLeadingZeros64_Portable(uint64 n);
    static int FindLSBSetNonZero_Portable(uint32 n);
    static int FindLSBSetNonZero64_Portable(uint64 n);
  
    static const char num_bits[];
    Bits(Bits const&) = delete;
    void operator=(Bits const&) = delete;
  };
  
  // A utility class for some handy bit patterns.  The names l and h
  // were chosen to match Knuth Volume 4: l is 0x010101... and h is 0x808080...;
  // half_ones is ones in the lower half only.  We assume sizeof(T) is 1 or even.
  template <class T> struct BitPattern {
    typedef typename std::make_unsigned<T>::type U;
    static const U half_ones = (static_cast<U>(1) << (sizeof(U) * 4)) - 1;
    static const U l =
        (sizeof(U) == 1) ? 1 : (half_ones / 0xff * (half_ones + 2));
    static const U h = ~(l * 0x7f);
  };
  
  // ------------------------------------------------------------------------
  // Implementation details follow
  // ------------------------------------------------------------------------
  
  #if defined(__GNUC__)
  
  inline int Bits::Log2Floor(uint32 n) {
    return n == 0 ? -1 : 31 ^ __builtin_clz(n);
  }
  
  inline int Bits::Log2FloorNonZero(uint32 n) {
    return 31 ^ __builtin_clz(n);
  }
  
  inline int Bits::FindLSBSetNonZero(uint32 n) {
    return __builtin_ctz(n);
  }
  
  inline int Bits::Log2Floor64(uint64 n) {
    return n == 0 ? -1 : 63 ^ __builtin_clzll(n);
  }
  
  inline int Bits::Log2FloorNonZero64(uint64 n) {
    return 63 ^ __builtin_clzll(n);
  }
  
  inline int Bits::FindLSBSetNonZero64(uint64 n) {
    return __builtin_ctzll(n);
  }
  
  #elif defined(_MSC_VER)
  
  inline int Bits::FindLSBSetNonZero(uint32 n) {
    return Bits::FindLSBSetNonZero_Portable(n);
  }
  
  inline int Bits::FindLSBSetNonZero64(uint64 n) {
    return Bits::FindLSBSetNonZero64_Portable(n);
  }
  
  inline int Bits::Log2FloorNonZero(uint32 n) {
  #ifdef _M_IX86
    _asm {
      bsr ebx, n
      mov n, ebx
    }
    return n;
  #else
    return Bits::Log2FloorNonZero_Portable(n);
  #endif
  }
  
  inline int Bits::Log2Floor(uint32 n) {
  #ifdef _M_IX86
    _asm {
      xor ebx, ebx
      mov eax, n
      and eax, eax
      jz return_ebx
      bsr ebx, eax
  return_ebx:
      mov n, ebx
    }
    return n;
  #else
    return Bits::Log2Floor_Portable(n);
  #endif
  }
  
  inline int Bits::Log2Floor64(uint64 n) {
    return Bits::Log2Floor64_Portable(n);
  }
  
  inline int Bits::Log2FloorNonZero64(uint64 n) {
    return Bits::Log2FloorNonZero64_Portable(n);
  }
  
  #else  // !__GNUC__ && !_MSC_VER
  
  inline int Bits::Log2Floor(uint32 n) {
    return Bits::Log2Floor_Portable(n);
  }
  
  inline int Bits::Log2FloorNonZero(uint32 n) {
    return Bits::Log2FloorNonZero_Portable(n);
  }
  
  inline int Bits::FindLSBSetNonZero(uint32 n) {
    return Bits::FindLSBSetNonZero_Portable(n);
  }
  
  inline int Bits::Log2Floor64(uint64 n) {
    return Bits::Log2Floor64_Portable(n);
  }
  
  inline int Bits::Log2FloorNonZero64(uint64 n) {
    return Bits::Log2FloorNonZero64_Portable(n);
  }
  
  inline int Bits::FindLSBSetNonZero64(uint64 n) {
    return Bits::FindLSBSetNonZero64_Portable(n);
  }
  
  #endif
  
  inline int Bits::Log2Floor128(absl::uint128 n) {
    if (uint64 hi = absl::Uint128High64(n)) return 64 + Log2FloorNonZero64(hi);
    return Log2Floor64(absl::Uint128Low64(n));
  }
  
  inline int Bits::Log2FloorNonZero128(absl::uint128 n) {
    if (uint64 hi = absl::Uint128High64(n)) return 64 + Log2FloorNonZero64(hi);
    return Log2FloorNonZero64(absl::Uint128Low64(n));
  }
  
  inline int Bits::FindLSBSetNonZero128(absl::uint128 n) {
    if (uint64 lo = absl::Uint128Low64(n)) return Bits::FindLSBSetNonZero64(lo);
    return 64 + Bits::FindLSBSetNonZero64(absl::Uint128High64(n));
  }
  
  inline int Bits::CountOnesInByte(unsigned char n) {
    return num_bits[n];
  }
  
  inline uint8 Bits::ReverseBits8(unsigned char n) {
  #if defined(__aarch64__) && defined(__GNUC__)
    // aarch64 has a reverse bits instruction but there is no gcc builtin.
    uint32 result;
    const uint32 n_shifted = static_cast<uint32>(n) << 24;
    asm("rbit %w0, %w1" : "=r"(result) : "r"(n_shifted));
    return static_cast<uint8>(result);
  #elif defined (__powerpc64__)
    uint64 temp = n;
    // bpermd selects a byte's worth of bits from its second input. Grab one byte
    // at a time, in reversed order. 0x3f is the lowest order bit of a 64-bit int.
    // Bits 0x0 through 0x37 will all be zero, and bits 0x38 through 0x3f will
    // hold the 8 bits from `n`.
    uint64 result = __builtin_bpermd(0x3f3e3d3c3b3a3938, temp);
    return static_cast<unsigned char>(result);
  #else
    n = static_cast<unsigned char>(((n >> 1) & 0x55) | ((n & 0x55) << 1));
    n = static_cast<unsigned char>(((n >> 2) & 0x33) | ((n & 0x33) << 2));
    return static_cast<unsigned char>(((n >> 4) & 0x0f)  | ((n & 0x0f) << 4));
  #endif
  }
  
  inline uint32 Bits::ReverseBits32(uint32 n) {
  #if defined(__aarch64__) && defined(__GNUC__)
    uint32 result;
    asm("rbit %w0, %w1" : "=r"(result) : "r"(n));
    return result;
  #elif defined(__powerpc64__)
    uint64 temp = n;
    uint64 result_0 = __builtin_bpermd(0x3f3e3d3c3b3a3938, temp) << 24;
    uint64 result_1 = __builtin_bpermd(0x3736353433323130, temp) << 16;
    uint64 result_2 = __builtin_bpermd(0x2f2e2d2c2b2a2928, temp) << 8;
    uint64 result_3 = __builtin_bpermd(0x2726252423222120, temp);
    return static_cast<uint32>(result_0 | result_1 | result_2 | result_3);
  #else
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
    n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
    return bswap_32(n);
  #endif
  }
  
  inline uint64 Bits::ReverseBits64(uint64 n) {
  #if defined(__aarch64__) && defined(__GNUC__)
    uint64 result;
    asm("rbit %0, %1" : "=r"(result) : "r"(n));
    return result;
  #elif defined(__powerpc64__)
    uint64 result_lo0 = __builtin_bpermd(0x3f3e3d3c3b3a3938, n) << 56;
    uint64 result_lo1 = __builtin_bpermd(0x3736353433323130, n) << 48;
    uint64 result_lo2 = __builtin_bpermd(0x2f2e2d2c2b2a2928, n) << 40;
    uint64 result_lo3 = __builtin_bpermd(0x2726252423222120, n) << 32;
    uint64 result_hi0 = __builtin_bpermd(0x1f1e1d1c1b1a1918, n) << 24;
    uint64 result_hi1 = __builtin_bpermd(0x1716151413121110, n) << 16;
    uint64 result_hi2 = __builtin_bpermd(0x0f0e0d0c0b0a0908, n) << 8;
    uint64 result_hi3 = __builtin_bpermd(0x0706050403020100, n);
    return (result_lo0 | result_lo1 | result_lo2 | result_lo3 |
            result_hi0 | result_hi1 | result_hi2 | result_hi3);
  #elif defined(_LP64)
    n = ((n >> 1) & 0x5555555555555555ULL) | ((n & 0x5555555555555555ULL) << 1);
    n = ((n >> 2) & 0x3333333333333333ULL) | ((n & 0x3333333333333333ULL) << 2);
    n = ((n >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((n & 0x0F0F0F0F0F0F0F0FULL) << 4);
    return bswap_64(n);
  #else
    return ReverseBits32( n >> 32 ) |
           (static_cast<uint64>(ReverseBits32(n &  0xffffffff)) << 32);
  #endif
  }
  
  inline absl::uint128 Bits::ReverseBits128(absl::uint128 n) {
    return absl::MakeUint128(ReverseBits64(absl::Uint128Low64(n)),
                             ReverseBits64(absl::Uint128High64(n)));
  }
  
  inline int Bits::Log2FloorNonZero_Portable(uint32 n) {
    // Just use the common routine
    return Log2Floor(n);
  }
  
  // Log2Floor64() is defined in terms of Log2Floor32(), Log2FloorNonZero32()
  inline int Bits::Log2Floor64_Portable(uint64 n) {
    const uint32 topbits = static_cast<uint32>(n >> 32);
    if (topbits == 0) {
      // Top bits are zero, so scan in bottom bits
      return Log2Floor(static_cast<uint32>(n));
    } else {
      return 32 + Log2FloorNonZero(topbits);
    }
  }
  
  // Log2FloorNonZero64() is defined in terms of Log2FloorNonZero32()
  inline int Bits::Log2FloorNonZero64_Portable(uint64 n) {
    const uint32 topbits = static_cast<uint32>(n >> 32);
    if (topbits == 0) {
      // Top bits are zero, so scan in bottom bits
      return Log2FloorNonZero(static_cast<uint32>(n));
    } else {
      return 32 + Log2FloorNonZero(topbits);
    }
  }
  
  // FindLSBSetNonZero64() is defined in terms of FindLSBSetNonZero()
  inline int Bits::FindLSBSetNonZero64_Portable(uint64 n) {
    const uint32 bottombits = static_cast<uint32>(n);
    if (bottombits == 0) {
      // Bottom bits are zero, so scan in top bits
      return 32 + FindLSBSetNonZero(static_cast<uint32>(n >> 32));
    } else {
      return FindLSBSetNonZero(bottombits);
    }
  }
  
  template <class T>
  inline bool Bits::BytesContainByteLessThan(T bytes, uint8 c) {
    auto l = BitPattern<T>::l;
    auto h = BitPattern<T>::h;
    // The c <= 0x80 code is straight out of Knuth Volume 4.
    // Usually c will be manifestly constant.
    return c <= 0x80 ?
        ((h & (bytes - l * c) & ~bytes) != 0) :
        ((((bytes - l * c) | (bytes ^ h)) & h) != 0);
  }
  
  template <class T> inline bool Bits::BytesContainByte(T bytes, uint8 c) {
    // Usually c will be manifestly constant.
    return Bits::BytesContainByteLessThan<T>(bytes ^ (c * BitPattern<T>::l), 1);
  }
  
  template <class T>
  inline bool Bits::BytesAllInRange(T bytes, uint8 lo, uint8 hi) {
    auto l = BitPattern<T>::l;
    auto h = BitPattern<T>::h;
    // In the common case, lo and hi are manifest constants.
    if (lo > hi) {
      return false;
    }
    if (hi - lo < 128) {
      auto x = bytes - l * lo;
      auto y = bytes + l * (127 - hi);
      return ((x | y) & h) == 0;
    }
    return !Bits::BytesContainByteLessThan(bytes + (255 - hi) * l,
                                           lo + (255 - hi));
  }
  
  // Specializations for Bits::UnsignedTypeBySize.  For unsupported type
  // sizes, a compile-time error will be generated.
  template<>
  struct Bits::UnsignedTypeBySize<1> {
    typedef uint8 Type;
  };
  
  template<>
  struct Bits::UnsignedTypeBySize<2> {
    typedef uint16 Type;
  };
  
  template<>
  struct Bits::UnsignedTypeBySize<4> {
    typedef uint32 Type;
  };
  
  template<>
  struct Bits::UnsignedTypeBySize<8> {
    typedef uint64 Type;
  };
  
  template<>
  struct Bits::UnsignedTypeBySize<16> {
    typedef absl::uint128 Type;
  };
  
  #ifdef __GNUC__
  inline int Bits::CountLeadingZerosWithBuiltin(unsigned n) {
    if (n == 0) {
      return sizeof(n) * 8;  // __builtin_clz(0) is undefined.
    }
    return __builtin_clz(n);
  }
  // NOLINTNEXTLINE(runtime/int)
  inline int Bits::CountLeadingZerosWithBuiltin(unsigned long n) {
    if (n == 0) {
      return sizeof(n) * 8;  // __builtin_clzl(0) is undefined.
    }
    return __builtin_clzl(n);
  }
  // NOLINTNEXTLINE(runtime/int)
  inline int Bits::CountLeadingZerosWithBuiltin(unsigned long long n) {
    if (n == 0) {
      return sizeof(n) * 8;  // __builtin_clzll(0) is undefined.
    }
    return __builtin_clzll(n);
  }
  
  inline int Bits::PopcountWithBuiltin(unsigned n) {
    return __builtin_popcount(n);
  }
  // NOLINTNEXTLINE(runtime/int)
  inline int Bits::PopcountWithBuiltin(unsigned long n) {
    return __builtin_popcountl(n);
  }
  // NOLINTNEXTLINE(runtime/int)
  inline int Bits::PopcountWithBuiltin(unsigned long long n) {
    return __builtin_popcountll(n);
  }
  
  #if defined(__BMI__) && (defined(__i386__) || defined(__x86_64__))
  inline uint32 Bits::GetBitsImpl(const uint32 src,
                                  const int offset,
                                  const int nbits) {
    return _bextr_u32(src, offset, nbits);
  }
  #endif
  
  #if defined(__BMI__) && defined(__x86_64__)
  inline uint64 Bits::GetBitsImpl(const uint64 src,
                                  const int offset,
                                  const int nbits) {
    return _bextr_u64(src, offset, nbits);
  }
  #endif
  
  #if defined(__BMI2__) && (defined(__i386__) || defined(__x86_64__))
  inline uint32 Bits::GetLowBitsImpl(const uint32 src, const int nbits) {
    return _bzhi_u32(src, nbits);
  }
  #endif
  
  #if defined(__BMI2__) && defined(__x86_64__)
  inline uint64 Bits::GetLowBitsImpl(const uint64 src, const int nbits) {
    return _bzhi_u64(src, nbits);
  }
  #endif
  
  #endif  // __GNUC__
  
  template<typename UnsignedT>
  inline UnsignedT Bits::GetBitsImpl(const UnsignedT src,
                                     const int offset,
                                     const int nbits) {
    const UnsignedT result = (src >> offset) & NBitsFromLSB<UnsignedT>(nbits);
    return result;
  }
  
  template<typename UnsignedT>
  inline UnsignedT Bits::GetLowBitsImpl(const UnsignedT src, const int nbits) {
    return GetBitsImpl(src, 0, nbits);
  }
  
  }  // namespace s2
  
  #endif  // S2_UTIL_BITS_BITS_H_
  