[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_