YugabyteDB (2.13.1.0-b60, 21121d69985fbf76aa6958d8f04a9bfa936293b5)

// Copyright 2002 and onwards Google Inc.

//

// The following only applies to changes made to this file as part of YugaByte development.

//

// Portions Copyright (c) YugaByte, Inc.

//

// 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.

//

// A collection of useful (static) bit-twiddling functions.

#ifndef YB_GUTIL_BITS_H

#define YB_GUTIL_BITS_H

#include <glog/logging.h>

#include "yb/gutil/integral_types.h"

#include "yb/gutil/logging-inl.h"

#include "yb/gutil/macros.h"

class Bits {

 public:

  // Return the number of one bits in the given integer.

  static int CountOnesInByte(unsigned char n);

  static int CountOnes(uint32 n) {

    n -= ((n >> 1) & 0x55555555);

    n = ((n >> 2) & 0x33333333) + (n & 0x33333333);

    return (((n + (n >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;

  }

  // Count bits using sideways addition [WWG'57]. See Knuth TAOCP v4 7.1.3(59)

  static inline int CountOnes64(uint64 n) {

#if defined(__x86_64__)

    n -= (n >> 1) & 0x5555555555555555ULL;

    n = ((n >> 2) & 0x3333333333333333ULL) + (n & 0x3333333333333333ULL);

    return (((n + (n >> 4)) & 0xF0F0F0F0F0F0F0FULL)

            * 0x101010101010101ULL) >> 56;

#else

    return CountOnes(n >> 32) + CountOnes(n & 0xffffffff);

#endif

  }

  // Reverse the bits in the given integer.

  static uint8 ReverseBits8(uint8 n);

  static uint32 ReverseBits32(uint32 n);

  static uint64 ReverseBits64(uint64 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);

  // Potentially faster version of Log2Floor() that returns an

  // undefined value if n == 0

  static int Log2FloorNonZero(uint32 n);

  static int Log2FloorNonZero64(uint64 n);

  // Return ceiling(log2(n)) for positive integer n.  Returns -1 iff n == 0.

  static int Log2Ceiling(uint32 n);

  static int Log2Ceiling64(uint64 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 FindMSBSetNonZero(uint32 n) { return Log2FloorNonZero(n); }

  static int FindMSBSetNonZero64(uint64 n) { return Log2FloorNonZero64(n); }

  // Portable implementations

  static int Log2Floor_Portable(uint32 n);

  static int Log2FloorNonZero_Portable(uint32 n);

  static int FindLSBSetNonZero_Portable(uint32 n);

  static int Log2Floor64_Portable(uint64 n);

  static int Log2FloorNonZero64_Portable(uint64 n);

  static int FindLSBSetNonZero64_Portable(uint64 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);

 private:

  static const char num_bits[];

  static const unsigned char bit_reverse_table[];

  DISALLOW_COPY_AND_ASSIGN(Bits);

};

// 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 {

  static const T half_ones = (static_cast<T>(1) << (sizeof(T)*4)) - 1;

  static const T l = (sizeof(T) == 1) ? 1 :

                       (half_ones / 0xff * (half_ones + 2));

  static const T h = ~(l * 0x7f);

};

// ------------------------------------------------------------------------

// Implementation details follow

// ------------------------------------------------------------------------

// use GNU builtins where available

#if defined(__GNUC__) && \

    ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4)

inline int Bits::Log2Floor(uint32 n) {

  return n == 0 ? 
-10
 : 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 ? 
-10
 : 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)

#include "yb/gutil/bits-internal-windows.h"

#else

#include "yb/gutil/bits-internal-unknown.h"

#endif

inline int Bits::CountOnesInByte(unsigned char n) {

  return num_bits[n];

}

inline uint8 Bits::ReverseBits8(unsigned char n) {

  n = ((n >> 1) & 0x55) | ((n & 0x55) << 1);

  n = ((n >> 2) & 0x33) | ((n & 0x33) << 2);

  return ((n >> 4) & 0x0f)  | ((n & 0x0f) << 4);

}

inline uint32 Bits::ReverseBits32(uint32 n) {

  n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);

  n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);

  n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);

  n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);

  return ( n >> 16 ) | ( n << 16);

}

inline uint64 Bits::ReverseBits64(uint64 n) {

#if defined(__x86_64__)

  n = ((n >> 1) & 0x5555555555555555ULL) | ((n & 0x5555555555555555ULL) << 1);

  n = ((n >> 2) & 0x3333333333333333ULL) | ((n & 0x3333333333333333ULL) << 2);

  n = ((n >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((n & 0x0F0F0F0F0F0F0F0FULL) << 4);

  n = ((n >> 8) & 0x00FF00FF00FF00FFULL) | ((n & 0x00FF00FF00FF00FFULL) << 8);

  n = ((n >> 16) & 0x0000FFFF0000FFFFULL) | ((n & 0x0000FFFF0000FFFFULL) << 16);

  return ( n >> 32 ) | ( n << 32);

#else

  return ReverseBits32( n >> 32 ) |

         (static_cast<uint64>(ReverseBits32( n &  0xffffffff )) << 32);

#endif

}

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) {

  T l = BitPattern<T>::l;

  T 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) {

  T l = BitPattern<T>::l;

  T h = BitPattern<T>::h;

  // In the common case, lo and hi are manifest constants.

  if (lo > hi) {

    return false;

  }

  if (hi - lo < 128) {

    T x = bytes - l * lo;

    T y = bytes + l * (127 - hi);

    return ((x | y) & h) == 0;

  }

  return !Bits::BytesContainByteLessThan(bytes + (255 - hi) * l,

                                         lo + (255 - hi));

}

#endif // YB_GUTIL_BITS_H