[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

1 files changed, 49 insertions, 1 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_