1 files changed, 239 insertions, 0 deletions
diff --git a/src/include/common/int128.h b/src/include/common/int128.h
index addef99bfa5..62aae1bc6a7 100644
--- a/src/include/common/int128.h
+++ b/src/include/common/int128.h
@@ -37,11 +37,18 @@
  * that a native int128 type would (probably) have.  This makes no difference
  * for ordinary use of INT128, but allows union'ing INT128 with int128 for
  * testing purposes.
+ *
+ * PG_INT128_HI_INT64 and PG_INT128_LO_UINT64 allow the (signed) high and
+ * (unsigned) low 64-bit integer parts to be extracted portably on all
+ * platforms.
  */
 #if USE_NATIVE_INT128
 
 typedef int128 INT128;
 
+#define PG_INT128_HI_INT64(i128)	((int64) ((i128) >> 64))
+#define PG_INT128_LO_UINT64(i128)	((uint64) (i128))
+
 #else
 
 typedef struct
@@ -55,7 +62,28 @@ typedef struct
 #endif
 } INT128;
 
+#define PG_INT128_HI_INT64(i128)	((i128).hi)
+#define PG_INT128_LO_UINT64(i128)	((i128).lo)
+
+#endif
+
+/*
+ * Construct an INT128 from (signed) high and (unsigned) low 64-bit integer
+ * parts.
+ */
+static inline INT128
+make_int128(int64 hi, uint64 lo)
+{
+#if USE_NATIVE_INT128
+	return (((int128) hi) << 64) + lo;
+#else
+	INT128		val;
+
+	val.hi = hi;
+	val.lo = lo;
+	return val;
 #endif
+}
 
 /*
  * Add an unsigned int64 value into an INT128 variable.
@@ -110,6 +138,58 @@ int128_add_int64(INT128 *i128, int64 v)
 }
 
 /*
+ * Add an INT128 value into an INT128 variable.
+ */
+static inline void
+int128_add_int128(INT128 *i128, INT128 v)
+{
+#if USE_NATIVE_INT128
+	*i128 += v;
+#else
+	int128_add_uint64(i128, v.lo);
+	i128->hi += v.hi;
+#endif
+}
+
+/*
+ * Subtract an unsigned int64 value from an INT128 variable.
+ */
+static inline void
+int128_sub_uint64(INT128 *i128, uint64 v)
+{
+#if USE_NATIVE_INT128
+	*i128 -= v;
+#else
+	/*
+	 * This is like int128_add_uint64(), except we must propagate a borrow to
+	 * (subtract 1 from) the .hi part if the new .lo part is greater than the
+	 * old .lo part.
+	 */
+	uint64		oldlo = i128->lo;
+
+	i128->lo -= v;
+	i128->hi -= (i128->lo > oldlo);
+#endif
+}
+
+/*
+ * Subtract a signed int64 value from an INT128 variable.
+ */
+static inline void
+int128_sub_int64(INT128 *i128, int64 v)
+{
+#if USE_NATIVE_INT128
+	*i128 -= v;
+#else
+	/* Like int128_add_int64() with the sign of v inverted */
+	uint64		oldlo = i128->lo;
+
+	i128->lo -= v;
+	i128->hi -= (i128->lo > oldlo) + (v >> 63);
+#endif
+}
+
+/*
  * INT64_HI_INT32 extracts the most significant 32 bits of int64 as int32.
  * INT64_LO_UINT32 extracts the least significant 32 bits as uint32.
  */
@@ -180,6 +260,165 @@ int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
 }
 
 /*
+ * Subtract the 128-bit product of two int64 values from an INT128 variable.
+ */
+static inline void
+int128_sub_int64_mul_int64(INT128 *i128, int64 x, int64 y)
+{
+#if USE_NATIVE_INT128
+	*i128 -= (int128) x * (int128) y;
+#else
+	/* As above, except subtract the 128-bit product */
+	if (x != 0 && y != 0)
+	{
+		int32		x_hi = INT64_HI_INT32(x);
+		uint32		x_lo = INT64_LO_UINT32(x);
+		int32		y_hi = INT64_HI_INT32(y);
+		uint32		y_lo = INT64_LO_UINT32(y);
+		int64		tmp;
+
+		/* the first term */
+		i128->hi -= (int64) x_hi * (int64) y_hi;
+
+		/* the second term: sign-extended with the sign of x */
+		tmp = (int64) x_hi * (int64) y_lo;
+		i128->hi -= INT64_HI_INT32(tmp);
+		int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
+
+		/* the third term: sign-extended with the sign of y */
+		tmp = (int64) x_lo * (int64) y_hi;
+		i128->hi -= INT64_HI_INT32(tmp);
+		int128_sub_uint64(i128, ((uint64) INT64_LO_UINT32(tmp)) << 32);
+
+		/* the fourth term: always unsigned */
+		int128_sub_uint64(i128, (uint64) x_lo * (uint64) y_lo);
+	}
+#endif
+}
+
+/*
+ * Divide an INT128 variable by a signed int32 value, returning the quotient
+ * and remainder.  The remainder will have the same sign as *i128.
+ *
+ * Note: This provides no protection against dividing by 0, or dividing
+ * INT128_MIN by -1, which overflows.  It is the caller's responsibility to
+ * guard against those.
+ */
+static inline void
+int128_div_mod_int32(INT128 *i128, int32 v, int32 *remainder)
+{
+#if USE_NATIVE_INT128
+	int128		old_i128 = *i128;
+
+	*i128 /= v;
+	*remainder = (int32) (old_i128 - *i128 * v);
+#else
+	/*
+	 * To avoid any intermediate values overflowing (as happens if INT64_MIN
+	 * is divided by -1), we first compute the quotient abs(*i128) / abs(v)
+	 * using unsigned 64-bit arithmetic, and then fix the signs up at the end.
+	 *
+	 * The quotient is computed using the short division algorithm described
+	 * in Knuth volume 2, section 4.3.1 exercise 16 (cf. div_var_int() in
+	 * numeric.c).  Since the absolute value of the divisor is known to be at
+	 * most 2^31, the remainder carried from one digit to the next is at most
+	 * 2^31 - 1, and so there is no danger of overflow when this is combined
+	 * with the next digit (a 32-bit unsigned integer).
+	 */
+	uint64		n_hi;
+	uint64		n_lo;
+	uint32		d;
+	uint64		q;
+	uint64		r;
+	uint64		tmp;
+
+	/* numerator: absolute value of *i128 */
+	if (i128->hi < 0)
+	{
+		n_hi = 0 - ((uint64) i128->hi);
+		n_lo = 0 - i128->lo;
+		if (n_lo != 0)
+			n_hi--;
+	}
+	else
+	{
+		n_hi = i128->hi;
+		n_lo = i128->lo;
+	}
+
+	/* denomimator: absolute value of v */
+	d = abs(v);
+
+	/* quotient and remainder of high 64 bits */
+	q = n_hi / d;
+	r = n_hi % d;
+	n_hi = q;
+
+	/* quotient and remainder of next 32 bits (upper half of n_lo) */
+	tmp = (r << 32) + (n_lo >> 32);
+	q = tmp / d;
+	r = tmp % d;
+
+	/* quotient and remainder of last 32 bits (lower half of n_lo) */
+	tmp = (r << 32) + (uint32) n_lo;
+	n_lo = q << 32;
+	q = tmp / d;
+	r = tmp % d;
+	n_lo += q;
+
+	/* final remainder should have the same sign as *i128 */
+	*remainder = i128->hi < 0 ? (int32) (0 - r) : (int32) r;
+
+	/* store the quotient in *i128, negating it if necessary */
+	if ((i128->hi < 0) != (v < 0))
+	{
+		n_hi = 0 - n_hi;
+		n_lo = 0 - n_lo;
+		if (n_lo != 0)
+			n_hi--;
+	}
+	i128->hi = (int64) n_hi;
+	i128->lo = n_lo;
+#endif
+}
+
+/*
+ * Test if an INT128 value is zero.
+ */
+static inline bool
+int128_is_zero(INT128 x)
+{
+#if USE_NATIVE_INT128
+	return x == 0;
+#else
+	return x.hi == 0 && x.lo == 0;
+#endif
+}
+
+/*
+ * Return the sign of an INT128 value (returns -1, 0, or +1).
+ */
+static inline int
+int128_sign(INT128 x)
+{
+#if USE_NATIVE_INT128
+	if (x < 0)
+		return -1;
+	if (x > 0)
+		return 1;
+	return 0;
+#else
+	if (x.hi < 0)
+		return -1;
+	if (x.hi > 0)
+		return 1;
+	if (x.lo > 0)
+		return 1;
+	return 0;
+#endif
+}
+
+/*
  * Compare two INT128 values, return -1, 0, or +1.
  */
 static inline int