diff options
-rw-r--r-- | algorithm.h | 50 | ||||
-rw-r--r-- | algorithm_unittest.cc | 139 | ||||
-rw-r--r-- | buffer_view.h | 2 | ||||
-rw-r--r-- | disassembler_win32.h | 4 | ||||
-rw-r--r-- | reloc_utils.cc | 2 |
5 files changed, 180 insertions, 17 deletions
diff --git a/algorithm.h b/algorithm.h index 7143a95..463aca3 100644 --- a/algorithm.h +++ b/algorithm.h @@ -48,7 +48,7 @@ T InclusiveClamp(T value, T lo, T hi) { // 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 @@ void SortAndUniquify(std::vector<T>* container) { 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 @@ constexpr T SignExtend(T v) { 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 @@ TEST(AlgorithmTest, InclusiveClamp) { 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 @@ TEST(AlgorithmTest, SignExtendTemplated) { (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 @@ class BufferViewBase { 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 @@ struct Win32X86Traits { 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 @@ struct Win32X64Traits { 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 @@ RelocRvaReaderWin32::RelocRvaReaderWin32( 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); } } |