This adds a bunch of static functions that implement unsigned

two's complement bignum arithmetic.  They could be used to
implement much of APInt, but the idea is they are enough to
implement APFloat as well, which the current APInt interface
is not suited for.

Patch by Neil Booth!



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41124 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 126 insertions, 0 deletions

diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index 7e7c67b..ce3696f 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -19,8 +19,16 @@
 #include <cassert>
 #include <string>
 
+#define HOST_CHAR_BIT 8
+#define compileTimeAssert(cond) extern int CTAssert[(cond) ? 1 : -1]
+#define integerPartWidth (HOST_CHAR_BIT * sizeof(llvm::integerPart))
+
 namespace llvm {
 
+  /* An unsigned host type used as a single part of a multi-part
+     bignum.  */
+  typedef uint64_t integerPart;
+
 //===----------------------------------------------------------------------===//
 //                              APInt Class
 //===----------------------------------------------------------------------===//
@@ -1038,6 +1046,124 @@ public:
       return -(*this);
     return *this;
   }
+
+  /// @}
+
+  /// @}
+  /// @name Building-block Operations for APInt and APFloat
+  /// @{
+
+  // These building block operations operate on a representation of
+  // arbitrary precision, two's-complement, bignum integer values.
+  // They should be sufficient to implement APInt and APFloat bignum
+  // requirements.  Inputs are generally a pointer to the base of an
+  // array of integer parts, representing an unsigned bignum, and a
+  // count of how many parts there are.
+
+  /// Sets the least significant part of a bignum to the input value,
+  /// and zeroes out higher parts.  */
+  static void tcSet(integerPart *, integerPart, unsigned int);
+
+  /// Assign one bignum to another.
+  static void tcAssign(integerPart *, const integerPart *, unsigned int);
+
+  /// Returns true if a bignum is zero, false otherwise.
+  static bool tcIsZero(const integerPart *, unsigned int);
+
+  /// Extract the given bit of a bignum; returns 0 or 1.  Zero-based.
+  static int tcExtractBit(const integerPart *, unsigned int bit);
+
+  /// Set the given bit of a bignum.  Zero-based.
+  static void tcSetBit(integerPart *, unsigned int bit);
+
+  /// Returns the bit number of the least or most significant set bit
+  /// of a number.  If the input number has no bits set -1U is
+  /// returned.
+  static unsigned int tcLSB(const integerPart *, unsigned int);
+  static unsigned int tcMSB(const integerPart *, unsigned int);
+
+  /// Negate a bignum in-place.
+  static void tcNegate(integerPart *, unsigned int);
+
+  /// DST += RHS + CARRY where CARRY is zero or one.  Returns the
+  /// carry flag.
+  static integerPart tcAdd(integerPart *, const integerPart *,
+			   integerPart carry, unsigned);
+
+  /// DST -= RHS + CARRY where CARRY is zero or one.  Returns the
+  /// carry flag.
+  static integerPart tcSubtract(integerPart *, const integerPart *,
+				integerPart carry, unsigned);
+
+  ///  DST += SRC * MULTIPLIER + PART   if add is true
+  ///  DST  = SRC * MULTIPLIER + PART   if add is false
+  ///
+  ///  Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
+  ///  they must start at the same point, i.e. DST == SRC.
+  ///
+  ///  If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is
+  ///  returned.  Otherwise DST is filled with the least significant
+  ///  DSTPARTS parts of the result, and if all of the omitted higher
+  ///  parts were zero return zero, otherwise overflow occurred and
+  ///  return one.
+  static int tcMultiplyPart(integerPart *dst, const integerPart *src,
+			    integerPart multiplier, integerPart carry,
+			    unsigned int srcParts, unsigned int dstParts,
+			    bool add);
+
+  /// DST = LHS * RHS, where DST has the same width as the operands
+  /// and is filled with the least significant parts of the result.
+  /// Returns one if overflow occurred, otherwise zero.  DST must be
+  /// disjoint from both operands.
+  static int tcMultiply(integerPart *, const integerPart *,
+			const integerPart *, unsigned);
+
+  /// DST = LHS * RHS, where DST has twice the width as the operands.
+  /// No overflow occurs.  DST must be disjoint from both operands.
+  static void tcFullMultiply(integerPart *, const integerPart *,
+			     const integerPart *, unsigned);
+
+  /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
+  /// Otherwise set LHS to LHS / RHS with the fractional part
+  /// discarded, set REMAINDER to the remainder, return zero.  i.e.
+  ///
+  ///  OLD_LHS = RHS * LHS + REMAINDER
+  ///
+  ///  SCRATCH is a bignum of the same size as the operands and result
+  ///  for use by the routine; its contents need not be initialized
+  ///  and are destroyed.  LHS, REMAINDER and SCRATCH must be
+  ///  distinct.
+  static int tcDivide(integerPart *lhs, const integerPart *rhs,
+		      integerPart *remainder, integerPart *scratch,
+		      unsigned int parts);
+
+  /// Shift a bignum left COUNT bits.  Shifted in bits are zero.
+  /// There are no restrictions on COUNT.
+  static void tcShiftLeft(integerPart *, unsigned int parts,
+			  unsigned int count);
+
+  /// Shift a bignum right COUNT bits.  Shifted in bits are zero.
+  /// There are no restrictions on COUNT.
+  static void tcShiftRight(integerPart *, unsigned int parts,
+			   unsigned int count);
+
+  /// The obvious AND, OR and XOR and complement operations.
+  static void tcAnd(integerPart *, const integerPart *, unsigned int);
+  static void tcOr(integerPart *, const integerPart *, unsigned int);
+  static void tcXor(integerPart *, const integerPart *, unsigned int);
+  static void tcComplement(integerPart *, unsigned int);
+  
+  /// Comparison (unsigned) of two bignums.
+  static int tcCompare(const integerPart *, const integerPart *,
+		       unsigned int);
+
+  /// Increment a bignum in-place.  Return the carry flag.
+  static integerPart tcIncrement(integerPart *, unsigned int);
+
+  /// Set the least significant BITS and clear the rest.
+  static void tcSetLeastSignificantBits(integerPart *, unsigned int,
+					unsigned int bits);
+
   /// @}
 };