[Zucchini] Introduce bit operations into algorithm.h.
This CL makes algorithm.h in Chromium match trunk's version. Details:
- Add {GetBit(), GetSignedBits(), GetUnsignedBits(), SignedFit()}.
These will be used by the ARM Disassembler.
- Rename ceil() to AlignCeil() to avoid confusion with ceil() from
<cmath>.
- Extensive unit tests.
- Minor enum type fix in disassembler_win32.h (offset_t should not
be used to represent lengths).
Change-Id: Icf9ce254bce2e5a3e9c286dbb5a704aeacd8bc35
Reviewed-on: https://chromium-review.googlesource.com/1098556
Reviewed-by: Samuel Huang <huangs@chromium.org>
Reviewed-by: Greg Thompson <grt@chromium.org>
Commit-Queue: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#566893}
NOKEYCHECK=True
GitOrigin-RevId: 2c50b5af45fa271f06317419f6b8bfc5f4a80be0
diff --git a/algorithm.h b/algorithm.h
index 7143a95..463aca3 100644
--- a/algorithm.h
+++ b/algorithm.h
@@ -48,7 +48,7 @@
// Returns the minimum multiple of |m| that's no less than |x|. Assumes |m > 0|
// and |x| is sufficiently small so that no overflow occurs.
template <class T>
-constexpr T ceil(T x, T m) {
+constexpr T AlignCeil(T x, T m) {
static_assert(std::is_unsigned<T>::value, "Value type must be unsigned.");
return T((x + m - 1) / m) * m;
}
@@ -62,6 +62,47 @@
container->shrink_to_fit();
}
+// Extracts a single bit at |pos| from integer |v|.
+template <int pos, typename T>
+constexpr T GetBit(T v) {
+ return (v >> pos) & 1;
+}
+
+// Extracts bits in inclusive range [|lo|, |hi|] from integer |v|, and returns
+// the sign-extend result. For example, let the (MSB-first) bits in a 32-bit int
+// |v| be:
+// xxxxxxxx xxxxxSii iiiiiiii iyyyyyyy,
+// hi^ lo^ => lo = 7, hi = 18
+// To extract "Sii iiiiiiii i", calling
+// GetSignedBits<7, 18>(v);
+// produces the sign-extended result:
+// SSSSSSSS SSSSSSSS SSSSSiii iiiiiiii.
+template <int lo, int hi, typename T>
+constexpr typename std::make_signed<T>::type GetSignedBits(T v) {
+ constexpr int kNumBits = sizeof(T) * 8;
+ using SignedType = typename std::make_signed<T>::type;
+ // Assumes 0 <= |lo| <= |hi| < |kNumBits|.
+ // How this works:
+ // (1) Shift-left by |kNumBits - 1 - hi| to clear "left" bits.
+ // (2) Shift-right by |kNumBits - 1 - hi + lo| to clear "right" bits. The
+ // input is casted to a signed type to perform sign-extension.
+ return static_cast<SignedType>(v << (kNumBits - 1 - hi)) >>
+ (kNumBits - 1 - hi + lo);
+}
+
+// Similar to GetSignedBits(), but returns the zero-extended result. For the
+// above example, calling
+// GetUnsignedBits<7, 18>(v);
+// results in:
+// 00000000 00000000 0000Siii iiiiiiii.
+template <int lo, int hi, typename T>
+constexpr typename std::make_unsigned<T>::type GetUnsignedBits(T v) {
+ constexpr int kNumBits = sizeof(T) * 8;
+ using UnsignedType = typename std::make_unsigned<T>::type;
+ return static_cast<UnsignedType>(v << (kNumBits - 1 - hi)) >>
+ (kNumBits - 1 - hi + lo);
+}
+
// Copies bits at |pos| in |v| to all higher bits, and returns the result as the
// same int type as |v|.
template <typename T>
@@ -79,6 +120,13 @@
return static_cast<typename std::make_signed<T>::type>(v << kShift) >> kShift;
}
+// Determines whether |v|, if interpreted as a signed integer, is representable
+// using |digs| bits. |1 <= digs <= sizeof(T)| is assumed.
+template <int digs, typename T>
+constexpr bool SignedFit(T v) {
+ return v == SignExtend<digs - 1, T>(v);
+}
+
} // namespace zucchini
#endif // COMPONENTS_ZUCCHINI_ALGORITHM_H_
diff --git a/algorithm_unittest.cc b/algorithm_unittest.cc
index 2c685db..a395b1e 100644
--- a/algorithm_unittest.cc
+++ b/algorithm_unittest.cc
@@ -131,18 +131,99 @@
InclusiveClamp<uint32_t>(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF));
}
-TEST(AlgorithmTest, Ceil) {
- EXPECT_EQ(0U, ceil<uint32_t>(0U, 2U));
- EXPECT_EQ(2U, ceil<uint32_t>(1U, 2U));
- EXPECT_EQ(2U, ceil<uint32_t>(2U, 2U));
- EXPECT_EQ(4U, ceil<uint32_t>(3U, 2U));
- EXPECT_EQ(4U, ceil<uint32_t>(4U, 2U));
- EXPECT_EQ(11U, ceil<uint32_t>(10U, 11U));
- EXPECT_EQ(11U, ceil<uint32_t>(11U, 11U));
- EXPECT_EQ(22U, ceil<uint32_t>(12U, 11U));
- EXPECT_EQ(22U, ceil<uint32_t>(21U, 11U));
- EXPECT_EQ(22U, ceil<uint32_t>(22U, 11U));
- EXPECT_EQ(33U, ceil<uint32_t>(23U, 11U));
+TEST(AlgorithmTest, AlignCeil) {
+ EXPECT_EQ(0U, AlignCeil<uint32_t>(0U, 2U));
+ EXPECT_EQ(2U, AlignCeil<uint32_t>(1U, 2U));
+ EXPECT_EQ(2U, AlignCeil<uint32_t>(2U, 2U));
+ EXPECT_EQ(4U, AlignCeil<uint32_t>(3U, 2U));
+ EXPECT_EQ(4U, AlignCeil<uint32_t>(4U, 2U));
+ EXPECT_EQ(11U, AlignCeil<uint32_t>(10U, 11U));
+ EXPECT_EQ(11U, AlignCeil<uint32_t>(11U, 11U));
+ EXPECT_EQ(22U, AlignCeil<uint32_t>(12U, 11U));
+ EXPECT_EQ(22U, AlignCeil<uint32_t>(21U, 11U));
+ EXPECT_EQ(22U, AlignCeil<uint32_t>(22U, 11U));
+ EXPECT_EQ(33U, AlignCeil<uint32_t>(23U, 11U));
+}
+
+TEST(AlgorithmTest, GetBit) {
+ // 0xC5 = 0b1100'0101.
+ constexpr uint8_t v = 0xC5;
+ EXPECT_EQ(uint8_t(1), (GetBit<0>(v)));
+ EXPECT_EQ(int8_t(0), (GetBit<1>(signed8(v))));
+ EXPECT_EQ(uint8_t(1), (GetBit<2>(v)));
+ EXPECT_EQ(int8_t(0), (GetBit<3>(signed8(v))));
+ EXPECT_EQ(uint8_t(0), (GetBit<4>(v)));
+ EXPECT_EQ(int8_t(0), (GetBit<5>(signed8(v))));
+ EXPECT_EQ(uint8_t(1), (GetBit<6>(v)));
+ EXPECT_EQ(int8_t(1), (GetBit<7>(signed8(v))));
+
+ EXPECT_EQ(int16_t(1), (GetBit<3, int16_t>(0x0008)));
+ EXPECT_EQ(uint16_t(0), (GetBit<14, uint16_t>(0xB000)));
+ EXPECT_EQ(uint16_t(1), (GetBit<15, uint16_t>(0xB000)));
+
+ EXPECT_EQ(uint32_t(1), (GetBit<0, uint32_t>(0xFFFFFFFF)));
+ EXPECT_EQ(int32_t(1), (GetBit<31, int32_t>(0xFFFFFFFF)));
+
+ EXPECT_EQ(uint32_t(0), (GetBit<0, uint32_t>(0xFF00A596)));
+ EXPECT_EQ(int32_t(1), (GetBit<1, int32_t>(0xFF00A596)));
+ EXPECT_EQ(uint32_t(1), (GetBit<4, uint32_t>(0xFF00A596)));
+ EXPECT_EQ(int32_t(1), (GetBit<7, int32_t>(0xFF00A596)));
+ EXPECT_EQ(uint32_t(0), (GetBit<9, uint32_t>(0xFF00A596)));
+ EXPECT_EQ(int32_t(0), (GetBit<16, int32_t>(0xFF00A59)));
+ EXPECT_EQ(uint32_t(1), (GetBit<24, uint32_t>(0xFF00A596)));
+ EXPECT_EQ(int32_t(1), (GetBit<31, int32_t>(0xFF00A596)));
+
+ EXPECT_EQ(uint64_t(0), (GetBit<62, uint64_t>(0xB000000000000000ULL)));
+ EXPECT_EQ(int64_t(1), (GetBit<63, int64_t>(0xB000000000000000LL)));
+}
+
+TEST(AlgorithmTest, GetBits) {
+ // Zero-extended: Basic cases for various values.
+ uint32_t test_cases[] = {0, 1, 2, 7, 137, 0x10000, 0x69969669, 0xFFFFFFFF};
+ for (uint32_t v : test_cases) {
+ EXPECT_EQ(uint32_t(v & 0xFF), (GetUnsignedBits<0, 7>(v)));
+ EXPECT_EQ(uint32_t((v >> 8) & 0xFF), (GetUnsignedBits<8, 15>(v)));
+ EXPECT_EQ(uint32_t((v >> 16) & 0xFF), (GetUnsignedBits<16, 23>(v)));
+ EXPECT_EQ(uint32_t((v >> 24) & 0xFF), (GetUnsignedBits<24, 31>(v)));
+ EXPECT_EQ(uint32_t(v & 0xFFFF), (GetUnsignedBits<0, 15>(v)));
+ EXPECT_EQ(uint32_t((v >> 1) & 0x3FFFFFFF), (GetUnsignedBits<1, 30>(v)));
+ EXPECT_EQ(uint32_t((v >> 2) & 0x0FFFFFFF), (GetUnsignedBits<2, 29>(v)));
+ EXPECT_EQ(uint32_t(v), (GetUnsignedBits<0, 31>(v)));
+ }
+
+ // Zero-extended: Reading off various nibbles.
+ EXPECT_EQ(uint32_t(0x4), (GetUnsignedBits<20, 23>(0x00432100U)));
+ EXPECT_EQ(uint32_t(0x43), (GetUnsignedBits<16, 23>(0x00432100)));
+ EXPECT_EQ(uint32_t(0x432), (GetUnsignedBits<12, 23>(0x00432100U)));
+ EXPECT_EQ(uint32_t(0x4321), (GetUnsignedBits<8, 23>(0x00432100)));
+ EXPECT_EQ(uint32_t(0x321), (GetUnsignedBits<8, 19>(0x00432100U)));
+ EXPECT_EQ(uint32_t(0x21), (GetUnsignedBits<8, 15>(0x00432100)));
+ EXPECT_EQ(uint32_t(0x1), (GetUnsignedBits<8, 11>(0x00432100U)));
+
+ // Sign-extended: 0x3CA5 = 0b0011'1100'1010'0101.
+ EXPECT_EQ(signed16(0xFFFF), (GetSignedBits<0, 0>(0x3CA5U)));
+ EXPECT_EQ(signed16(0x0001), (GetSignedBits<0, 1>(0x3CA5)));
+ EXPECT_EQ(signed16(0xFFFD), (GetSignedBits<0, 2>(0x3CA5U)));
+ EXPECT_EQ(signed16(0x0005), (GetSignedBits<0, 4>(0x3CA5)));
+ EXPECT_EQ(signed16(0xFFA5), (GetSignedBits<0, 7>(0x3CA5U)));
+ EXPECT_EQ(signed16(0xFCA5), (GetSignedBits<0, 11>(0x3CA5)));
+ EXPECT_EQ(signed16(0x0005), (GetSignedBits<0, 3>(0x3CA5U)));
+ EXPECT_EQ(signed16(0xFFFA), (GetSignedBits<4, 7>(0x3CA5)));
+ EXPECT_EQ(signed16(0xFFFC), (GetSignedBits<8, 11>(0x3CA5U)));
+ EXPECT_EQ(signed16(0x0003), (GetSignedBits<12, 15>(0x3CA5)));
+ EXPECT_EQ(signed16(0x0000), (GetSignedBits<4, 4>(0x3CA5U)));
+ EXPECT_EQ(signed16(0xFFFF), (GetSignedBits<5, 5>(0x3CA5)));
+ EXPECT_EQ(signed16(0x0002), (GetSignedBits<4, 6>(0x3CA5U)));
+ EXPECT_EQ(signed16(0x1E52), (GetSignedBits<1, 14>(0x3CA5)));
+ EXPECT_EQ(signed16(0xFF29), (GetSignedBits<2, 13>(0x3CA5U)));
+ EXPECT_EQ(int32_t(0x00001E52), (GetSignedBits<1, 14>(0x3CA5)));
+ EXPECT_EQ(int32_t(0xFFFFFF29), (GetSignedBits<2, 13>(0x3CA5U)));
+
+ // 64-bits: Extract from middle 0x66 = 0b0110'0110.
+ EXPECT_EQ(uint64_t(0x0000000000000009LL),
+ (GetUnsignedBits<30, 33>(int64_t(0x2222222661111111LL))));
+ EXPECT_EQ(int64_t(0xFFFFFFFFFFFFFFF9LL),
+ (GetSignedBits<30, 33>(uint64_t(0x2222222661111111LL))));
}
TEST(AlgorithmTest, SignExtend) {
@@ -203,4 +284,38 @@
(SignExtend<9, uint64_t>(0xFFFFFFFFFFFFFD6AULL)));
}
+TEST(AlgorithmTest, SignedFit) {
+ for (int v = -0x80; v < 0x80; ++v) {
+ EXPECT_EQ(v >= -1 && v < 1, (SignedFit<1, int8_t>(v)));
+ EXPECT_EQ(v >= -1 && v < 1, (SignedFit<1, uint8_t>(v)));
+ EXPECT_EQ(v >= -2 && v < 2, (SignedFit<2, int8_t>(v)));
+ EXPECT_EQ(v >= -4 && v < 4, (SignedFit<3, uint8_t>(v)));
+ EXPECT_EQ(v >= -8 && v < 8, (SignedFit<4, int16_t>(v)));
+ EXPECT_EQ(v >= -16 && v < 16, (SignedFit<5, uint32_t>(v)));
+ EXPECT_EQ(v >= -32 && v < 32, (SignedFit<6, int32_t>(v)));
+ EXPECT_EQ(v >= -64 && v < 64, (SignedFit<7, uint64_t>(v)));
+ EXPECT_TRUE((SignedFit<8, int8_t>(v)));
+ EXPECT_TRUE((SignedFit<8, uint8_t>(v)));
+ }
+
+ EXPECT_TRUE((SignedFit<16, uint32_t>(0x00000000)));
+ EXPECT_TRUE((SignedFit<16, uint32_t>(0x00007FFF)));
+ EXPECT_TRUE((SignedFit<16, uint32_t>(0xFFFF8000)));
+ EXPECT_TRUE((SignedFit<16, uint32_t>(0xFFFFFFFF)));
+ EXPECT_TRUE((SignedFit<16, int32_t>(0x00007FFF)));
+ EXPECT_TRUE((SignedFit<16, int32_t>(0xFFFF8000)));
+
+ EXPECT_FALSE((SignedFit<16, uint32_t>(0x80000000)));
+ EXPECT_FALSE((SignedFit<16, uint32_t>(0x7FFFFFFF)));
+ EXPECT_FALSE((SignedFit<16, uint32_t>(0x00008000)));
+ EXPECT_FALSE((SignedFit<16, uint32_t>(0xFFFF7FFF)));
+ EXPECT_FALSE((SignedFit<16, int32_t>(0x00008000)));
+ EXPECT_FALSE((SignedFit<16, int32_t>(0xFFFF7FFF)));
+
+ EXPECT_TRUE((SignedFit<48, int64_t>(0x00007FFFFFFFFFFFLL)));
+ EXPECT_TRUE((SignedFit<48, int64_t>(0xFFFF800000000000LL)));
+ EXPECT_FALSE((SignedFit<48, int64_t>(0x0008000000000000LL)));
+ EXPECT_FALSE((SignedFit<48, int64_t>(0xFFFF7FFFFFFFFFFFLL)));
+}
+
} // namespace zucchini
diff --git a/buffer_view.h b/buffer_view.h
index 8dbe817..0db36dd 100644
--- a/buffer_view.h
+++ b/buffer_view.h
@@ -184,7 +184,7 @@
DCHECK_LE(origin.first_, first_);
DCHECK_GE(origin.last_, last_);
size_type aligned_size =
- ceil(static_cast<size_type>(first_ - origin.first_), alignment);
+ AlignCeil(static_cast<size_type>(first_ - origin.first_), alignment);
if (aligned_size > static_cast<size_type>(last_ - origin.first_))
return false;
first_ = origin.first_ + aligned_size;
diff --git a/disassembler_win32.h b/disassembler_win32.h
index 8e410ee..29033ce 100644
--- a/disassembler_win32.h
+++ b/disassembler_win32.h
@@ -30,7 +30,7 @@
static constexpr ExecutableType kExeType = kExeTypeWin32X86;
enum : uint16_t { kMagic = 0x10B };
enum : uint16_t { kRelocType = 3 };
- enum : offset_t { kVAWidth = 4 };
+ enum : uint32_t { kVAWidth = 4 };
static const char kExeTypeString[];
using ImageOptionalHeader = pe::ImageOptionalHeader;
@@ -43,7 +43,7 @@
static constexpr ExecutableType kExeType = kExeTypeWin32X64;
enum : uint16_t { kMagic = 0x20B };
enum : uint16_t { kRelocType = 10 };
- enum : offset_t { kVAWidth = 8 };
+ enum : uint32_t { kVAWidth = 8 };
static const char kExeTypeString[];
using ImageOptionalHeader = pe::ImageOptionalHeader64;
diff --git a/reloc_utils.cc b/reloc_utils.cc
index 84f488e..c9fb432 100644
--- a/reloc_utils.cc
+++ b/reloc_utils.cc
@@ -81,7 +81,7 @@
offset_t cur_reloc_units_offset = cur_reloc_units_.begin() - image_.begin();
if (lo > cur_reloc_units_offset) {
offset_t delta =
- ceil<offset_t>(lo - cur_reloc_units_offset, kRelocUnitSize);
+ AlignCeil<offset_t>(lo - cur_reloc_units_offset, kRelocUnitSize);
cur_reloc_units_.Skip(delta);
}
}