Create some helpers for generating bit masks

[zturner]

Summary

Often you want a bit-mask with the first N bits or the last N bits set to 1. This is surprisingly confusing to get right, in part because X << (8*sizeof(X)) is undefined, so trying to produce a mask of all 1s won't work, and also in part because the branch-free implementation is not obvious.

[chandlerc]

Nice, LGTM!

[amccarth]

llvm/trunk/include/llvm/Support/MathExtras.h

207

Be aware that this can lead to compiler warnings, at least in MSVC, if T is an unsigned type:

C4146: unary minus operator applied to unsigned type, result still unsigned

Depending on the specific details, this can be a level 2 or level 3 warning. I'm surprised the tests aren't triggering it. We must disable this warning somewhere.

llvm/trunk/include/llvm/Support/MathExtras.h

 ///   valid arguments.
 template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
   if (ZB == ZB_Max && Val == 0)
     return std::numeric_limits<T>::max();
 
   return countTrailingZeros(Val, ZB_Undefined);
 }
 
+/// \brief Create a bitmask with the N right-most bits set to 1, and all other
+/// bits set to 0.  Only unsigned types are allowed.
+template <typename T> T maskTrailingOnes(unsigned N) {
+  static_assert(std::is_unsigned<T>::value, "Invalid type!");
+  const unsigned Bits = CHAR_BIT * sizeof(T);
+  assert(N <= Bits && "Invalid bit index");
+  return -T(N != 0) & (T(-1) >> (Bits - N));
+}
+
+/// \brief Create a bitmask with the N left-most bits set to 1, and all other
+/// bits set to 0.  Only unsigned types are allowed.
+template <typename T> T maskLeadingOnes(unsigned N) {
+  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
+}
+
 /// \brief Get the index of the last set bit starting from the least
 ///   significant bit.
 ///
 /// Only unsigned integral types are allowed.
 ///
 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
 ///   valid arguments.
 template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {

llvm/trunk/unittests/Support/MathExtrasTest.cpp

TEST(MathExtras, countLeadingZeros) {
 
   EXPECT_EQ(8u, countLeadingZeros(0x00F1234500F12345ULL));
   EXPECT_EQ(1u, countLeadingZeros(1ULL << 62));
   for (unsigned i = 0; i <= 62; ++i) {
     EXPECT_EQ(63 - i, countLeadingZeros(1ULL << i));
   }
 }
 
+TEST(MathExtras, onesMask) {
+  EXPECT_EQ(0U, maskLeadingOnes<uint8_t>(0));
+  EXPECT_EQ(0U, maskTrailingOnes<uint8_t>(0));
+  EXPECT_EQ(0U, maskLeadingOnes<uint16_t>(0));
+  EXPECT_EQ(0U, maskTrailingOnes<uint16_t>(0));
+  EXPECT_EQ(0U, maskLeadingOnes<uint32_t>(0));
+  EXPECT_EQ(0U, maskTrailingOnes<uint32_t>(0));
+  EXPECT_EQ(0U, maskLeadingOnes<uint64_t>(0));
+  EXPECT_EQ(0U, maskTrailingOnes<uint64_t>(0));
+
+  EXPECT_EQ(0x00000003U, maskTrailingOnes<uint32_t>(2U));
+  EXPECT_EQ(0xC0000000U, maskLeadingOnes<uint32_t>(2U));
+
+  EXPECT_EQ(0x000007FFU, maskTrailingOnes<uint32_t>(11U));
+  EXPECT_EQ(0xFFE00000U, maskLeadingOnes<uint32_t>(11U));
+
+  EXPECT_EQ(0xFFFFFFFFU, maskTrailingOnes<uint32_t>(32U));
+  EXPECT_EQ(0xFFFFFFFFU, maskLeadingOnes<uint32_t>(32U));
+}
+
 TEST(MathExtras, findFirstSet) {
   uint8_t Z8 = 0;
   uint16_t Z16 = 0;
   uint32_t Z32 = 0;
   uint64_t Z64 = 0;
   EXPECT_EQ(0xFFULL, findFirstSet(Z8));
   EXPECT_EQ(0xFFFFULL, findFirstSet(Z16));
   EXPECT_EQ(0xFFFFFFFFULL, findFirstSet(Z32));