Fix and test signed left-shift

Signed-off-by: Mattias Andrée <m@maandree.se>

5 files changed, 224 insertions, 88 deletions

diff --git a/libj2/bit-shifting.h b/libj2/bit-shifting.h
index 9cf8958..7cf44bf 100644
--- a/libj2/bit-shifting.h
+++ b/libj2/bit-shifting.h
@@ -817,6 +817,89 @@ libj2_ji_lsh_to_j2i(intmax_t a, unsigned b, struct libj2_j2i *res)
 
 
 /**
+ * Predict whether `libj2_j2i_lsh_overflow` or
+ * `libj2_j2i_lsh_to_j2i_overflow` will return
+ * a result-overflow signal
+ * 
+ * `libj2_j2i_lsh_overflow_p(a, b)` implements
+ * `libj2_j2i_lsh_to_j2i_overflow(a, b, &(struct libj2_j2i){})`
+ * in an efficient manner
+ * 
+ * @param   a  The integer to shift (dry-run)
+ * @param   b  The number of positions to shift each bit
+ * @return     +1 if `*a` is non-negative and a set bit
+ *             would be shifted out of precision (discarded
+ *             or into the sign-bit position), that is, a
+ *             positive overflow,
+ *             -1 if `*a` is negative and a cleared bit
+ *             would be shifted out of precision (discarded
+ *             or into the sign-bit position), that is, a
+ *             negative overflow,
+ *             0 otherwise
+ * 
+ * @since  1.1
+ */
+inline int
+libj2_j2i_lsh_overflow_p(const struct libj2_j2i *a, unsigned b)
+{
+	if (!b) {
+		return 0;
+	} else if (!libj2_j2i_is_negative(a)) {
+		if (b >= LIBJ2_J2I_BIT)
+			return a->high || a->low;
+		else if (b >= LIBJ2_JU_BIT)
+			return a->high || a->low >> (LIBJ2_J2U_BIT - 1U - b);
+		else
+			return !!(a->high >> (LIBJ2_JU_BIT - 1U - b));
+	} else if (b >= LIBJ2_J2I_BIT) {
+		return -1;
+	} else if (b == LIBJ2_JU_BIT) {
+		return a->high != UINTMAX_MAX ? -1 : (a->low & (UINTMAX_MAX ^ (UINTMAX_MAX >> 1))) ? 0 : -1;
+	} else if (b > LIBJ2_JU_BIT) {
+		return (a->high != UINTMAX_MAX || ~a->low >> (LIBJ2_J2U_BIT - 1U - b)) ? -1 : 0;
+	} else {
+		return ~(a->high << 1) >> (LIBJ2_JU_BIT - b) ? -1 : 0;
+	}
+}
+
+
+/**
+ * Predict whether `libj2_ji_lsh_to_j2i_overflow`
+ * will return a result-overflow signal
+ * 
+ * `libj2_ji_lsh_overflow_p(a, b)` implements
+ * `libj2_ji_lsh_to_j2i_overflow(a, b, &(struct libj2_j2i){})`
+ * in an efficient manner
+ * 
+ * @param   a  The integer to shift (dry-run)
+ * @param   b  The number of positions to shift each bit
+ * @return     +1 if `a` is non-negative and a set bit
+ *             would be shifted out of precision (discarded
+ *             or into the sign-bit position), that is, a
+ *             positive overflow,
+ *             -1 if `a` is negative and a cleared bit
+ *             would be shifted out of precision (discarded
+ *             or into the sign-bit position), that is, a
+ *             negative overflow,
+ *             0 otherwise
+ * 
+ * @since  1.1
+ */
+inline int
+libj2_ji_lsh_overflow_p(intmax_t a, unsigned b)
+{
+	if (b >= LIBJ2_J2I_BIT)
+		return a < 0 ? -1 : a > 0;
+	else if (b <= LIBJ2_JU_BIT)
+		return 0;
+	else if (a >= 0)
+		return (uintmax_t)a >> (LIBJ2_J2I_VBIT - b) ? +1 : 0;
+	else
+		return ~(uintmax_t)a >> (LIBJ2_J2I_VBIT - b) ? -1 : 0;
+}
+
+
+/**
  * Shift the bits in a signed double-max precision
  * integer to more signficant positions (left-shift)
  * 
@@ -848,15 +931,9 @@ libj2_ji_lsh_to_j2i(intmax_t a, unsigned b, struct libj2_j2i *res)
 inline int
 libj2_j2i_lsh_overflow(struct libj2_j2i *a, unsigned b)
 {
-	if (libj2_j2i_is_negative(a)) {
-		int overflow;
-		libj2_not_j2u((void *)a);
-		overflow = libj2_j2u_lsh_overflow((void *)a, b) || libj2_j2i_is_negative(a);
-		libj2_not_j2u((void *)a);
-		return -overflow;
-	} else {
-		return libj2_j2u_lsh_overflow((void *)a, b) || libj2_j2i_is_negative(a);
-	}
+	int overflow = libj2_j2i_lsh_overflow_p(a, b);
+	libj2_j2i_lsh(a, b);
+	return overflow;
 }
 
 
@@ -892,8 +969,9 @@ libj2_j2i_lsh_overflow(struct libj2_j2i *a, unsigned b)
 inline int
 libj2_j2i_lsh_to_j2i_overflow(const struct libj2_j2i *a, unsigned b, struct libj2_j2i *res)
 {
-	*res = *a;
-	return libj2_j2i_lsh_overflow(res, b);
+	int overflow = libj2_j2i_lsh_overflow_p(a, b);
+	libj2_j2i_lsh_to_j2i(a, b, res);
+	return overflow;
 }
 
 
@@ -1153,77 +1231,6 @@ libj2_ji_rsh_to_j2i_underflow(intmax_t a, unsigned b, struct libj2_j2i *res)
 
 
 /**
- * Predict whether `libj2_j2i_lsh_overflow` or
- * `libj2_j2i_lsh_to_j2i_overflow` will return
- * a result-overflow signal
- * 
- * `libj2_j2i_lsh_overflow_p(a, b)` implements
- * `libj2_j2i_lsh_to_j2i_overflow(a, b, &(struct libj2_j2i){})`
- * in an efficient manner
- * 
- * @param   a  The integer to shift (dry-run)
- * @param   b  The number of positions to shift each bit
- * @return     +1 if `*a` is non-negative and a set bit
- *             would be shifted out of precision (discarded
- *             or into the sign-bit position), that is, a
- *             positive overflow,
- *             -1 if `*a` is negative and a cleared bit
- *             would be shifted out of precision (discarded
- *             or into the sign-bit position), that is, a
- *             negative overflow,
- *             0 otherwise
- * 
- * @since  1.1
- */
-inline int
-libj2_j2i_lsh_overflow_p(const struct libj2_j2i *a, unsigned b)
-{
-	struct libj2_j2u t;
-	int overflow;
-	libj2_j2i_xor_sign_to_j2u(a, &t);
-	b = b > LIBJ2_J2I_BIT ? LIBJ2_J2I_BIT + 1U : b + 1U;
-	overflow = libj2_j2u_lsh_overflow_p(&t, b);
-	return overflow && libj2_j2i_is_negative(a) ? -1 : overflow;
-}
-
-
-/**
- * Predict whether `libj2_ji_lsh_to_j2i_overflow`
- * will return a result-overflow signal
- * 
- * `libj2_ji_lsh_overflow_p(a, b)` implements
- * `libj2_ji_lsh_to_j2i_overflow(a, b, &(struct libj2_j2i){})`
- * in an efficient manner
- * 
- * @param   a  The integer to shift (dry-run)
- * @param   b  The number of positions to shift each bit
- * @return     +1 if `a` is non-negative and a set bit
- *             would be shifted out of precision (discarded
- *             or into the sign-bit position), that is, a
- *             positive overflow,
- *             -1 if `a` is negative and a cleared bit
- *             would be shifted out of precision (discarded
- *             or into the sign-bit position), that is, a
- *             negative overflow,
- *             0 otherwise
- * 
- * @since  1.1
- */
-inline int
-libj2_ji_lsh_overflow_p(intmax_t a, unsigned b)
-{
-	if (b >= LIBJ2_J2I_BIT)
-		return a < 0 ? -1 : a > 0;
-	else if (b <= LIBJ2_JU_BIT)
-		return 0;
-	else if (a >= 0)
-		return !!((uintmax_t)a >> (LIBJ2_J2I_BIT - b));
-	else
-		return !!(~(uintmax_t)a >> (LIBJ2_J2I_BIT - b));
-}
-
-
-/**
  * Predict whether `libj2_j2i_rsh_underflow` or
  * `libj2_j2i_rsh_to_j2i_underflow` will return
  * a result-underflow signal
diff --git a/libj2_j2i_lsh.c b/libj2_j2i_lsh.c
index 14ea251..289a0a8 100644
--- a/libj2_j2i_lsh.c
+++ b/libj2_j2i_lsh.c
@@ -8,7 +8,137 @@ extern inline void libj2_j2i_lsh(struct libj2_j2i *a, unsigned b);
 
 #else
 
-CONST int main(void) { return 0; }
-/* TODO test libj2_j2i_lsh{,_to_j2i}{,_overflow}, libj2_j2i_lsh_overflow_p */
+static void
+check(const struct libj2_j2i *a, unsigned shift, const struct libj2_j2i *expected, int overflow)
+{
+	struct libj2_j2i a_saved = *a, r;
+	intmax_t v;
+
+	r = *a;
+	libj2_j2i_lsh(&r, shift);
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	r = *a;
+	EXPECT(libj2_j2i_lsh_overflow_p((const struct libj2_j2i *)&r, shift) == overflow);
+	EXPECT(libj2_j2i_eq_j2i(&r, a));
+
+	r = *a;
+	EXPECT(libj2_j2i_lsh_overflow(&r, shift) == overflow);
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	r = (struct libj2_j2i){111, 222};
+	libj2_j2i_lsh_to_j2i((const struct libj2_j2i *)a, shift, &r);
+	EXPECT(libj2_j2i_eq_j2i(a, &a_saved));
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	r = *a;
+	libj2_j2i_lsh_to_j2i(&r, shift, &r);
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	r = (struct libj2_j2i){111, 222};
+	EXPECT(libj2_j2i_lsh_to_j2i_overflow((const struct libj2_j2i *)a, shift, &r) == overflow);
+	EXPECT(libj2_j2i_eq_j2i(a, &a_saved));
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	r = *a;
+	EXPECT(libj2_j2i_lsh_to_j2i_overflow(&r, shift, &r) == overflow);
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	if (libj2_j2i_is_negative(a)) {
+		if (a->high != UINTMAX_MAX || ~a->low > UINTMAX_MAX >> 1)
+			return;
+		v = -(intmax_t)~a->low - 1;
+	} else {
+		if (a->high || a->low > UINTMAX_MAX >> 1)
+			return;
+		v = (intmax_t)a->low;
+	}
+
+	EXPECT(libj2_ji_lsh_overflow_p(v, shift) == overflow);
+
+	r = (struct libj2_j2i){111, 222};
+	libj2_ji_lsh_to_j2i(v, shift, &r);
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+
+	r = (struct libj2_j2i){111, 222};
+	EXPECT(libj2_ji_lsh_to_j2i_overflow(v, shift, &r) == overflow);
+	EXPECT(libj2_j2i_eq_j2i(&r, expected));
+}
+
+
+int
+main(void)
+{
+	struct libj2_j2i a, b;
+	struct libj2_j2u t;
+	unsigned i, j, k, s;
+	int overflow;
+
+	srand((unsigned)time(NULL));
+
+	for (j = 0; j <= LIBJ2_J2I_BIT + 4U; j++) {
+		libj2_j2i_zero(&a);
+		libj2_j2i_zero(&b);
+		check(&a, j, &b, 0);
+
+		libj2_not_j2u((void *)&a);
+		libj2_not_j2u((void *)&b);
+		libj2_j2u_lsh((void *)&b, j);
+		check(&a, j, &b, j >= LIBJ2_J2I_BIT ? -1 : 0);
+
+		for (i = 0; i < LIBJ2_J2I_BIT; i++) {
+			libj2_j2i_zero(&a);
+			libj2_j2u_or_bit((void *)&a, i);
+			libj2_j2i_zero(&b);
+			if (i + j < LIBJ2_J2I_BIT)
+				libj2_j2u_or_bit((void *)&b, i + j);
+			overflow = i == LIBJ2_J2I_VBIT ? j ? -1 : 0 : i + j < LIBJ2_J2I_VBIT ? 0 : +1;
+			check(&a, j, &b, overflow);
+
+			libj2_j2i_zero(&a);
+			libj2_j2u_or_bit((void *)&a, i);
+			libj2_not_j2u((void *)&a);
+			libj2_j2i_zero(&b);
+			if (i + j < LIBJ2_J2I_BIT)
+				libj2_j2u_or_bit((void *)&b, i + j);
+			for (k = 0; k < j; k++)
+				libj2_j2u_or_bit((void *)&b, k);
+			libj2_not_j2u((void *)&b);
+			overflow = i == LIBJ2_J2I_VBIT ? j ? +1 : 0 : i + j < LIBJ2_J2I_VBIT ? 0 : -1;
+			check(&a, j, &b, overflow);
+		}
+	}
+
+	for (i = 0; i < 32; i++) {
+		for (j = 0; j < LIBJ2_J2I_BIT - 1U; j++) {
+			for (k = 0; k <= LIBJ2_J2I_BIT + 1U; k++) {
+				libj2_j2i_zero(&a);
+				libj2_j2i_zero(&b);
+				for (s = 0; s <= j; s++) {
+					if (rand() < rand())
+						continue;
+					libj2_j2u_or_bit((void *)&a, s);
+					libj2_j2u_or_bit((void *)&b, s + k);
+				}
+				overflow = libj2_co_j2u((const void *)&a) > libj2_co_j2u((const void *)&b);
+				overflow |= libj2_j2i_is_negative(&b);
+				check(&a, k, &b, overflow);
+
+				libj2_not_j2u((void *)&a);
+				libj2_not_j2u((void *)&b);
+				libj2_ju_lsh_to_j2u(1, k, &t);
+				libj2_j2u_sub_ju(&t, 1);
+				libj2_not_j2u(&t);
+				libj2_j2u_and_j2u((void *)&b, &t);
+				overflow = -overflow;
+				if (a.high == UINTMAX_MAX && a.low == UINTMAX_MAX && k >= LIBJ2_J2I_BIT)
+					overflow = -1;
+				check(&a, k, &b, overflow);
+			}
+		}
+	}
+
+	return 0;
+}
 
 #endif
diff --git a/libj2_ji_lsh_overflow_p.c b/libj2_ji_lsh_overflow_p.c
index 332a6c9..9664aca 100644
--- a/libj2_ji_lsh_overflow_p.c
+++ b/libj2_ji_lsh_overflow_p.c
@@ -8,6 +8,6 @@ extern inline int libj2_ji_lsh_overflow_p(intmax_t a, unsigned b);
 
 #else
 
-CONST int main(void) { return 0; } /* Tested in libj2_ji_lsh_to_j2i.c */
+CONST int main(void) { return 0; } /* Tested in libj2_j2i_lsh.c */
 
 #endif
diff --git a/libj2_ji_lsh_to_j2i.c b/libj2_ji_lsh_to_j2i.c
index 88b2379..f716d79 100644
--- a/libj2_ji_lsh_to_j2i.c
+++ b/libj2_ji_lsh_to_j2i.c
@@ -8,7 +8,6 @@ extern inline void libj2_ji_lsh_to_j2i(intmax_t a, unsigned b, struct libj2_j2i
 
 #else
 
-CONST int main(void) { return 0; }
-/* TODO test libj2_ji_lsh_to_j2i, libj2_ji_lsh_to_j2i_overflow, libj2_ji_lsh_overflow_p */
+CONST int main(void) { return 0; } /* Tested in libj2_j2i_lsh.c */
 
 #endif
diff --git a/libj2_ji_lsh_to_j2i_overflow.c b/libj2_ji_lsh_to_j2i_overflow.c
index 187d84d..81ea406 100644
--- a/libj2_ji_lsh_to_j2i_overflow.c
+++ b/libj2_ji_lsh_to_j2i_overflow.c
@@ -8,6 +8,6 @@ extern inline int libj2_ji_lsh_to_j2i_overflow(intmax_t a, unsigned b, struct li
 
 #else
 
-CONST int main(void) { return 0; } /* Tested in libj2_ji_lsh_to_j2i.c */
+CONST int main(void) { return 0; } /* Tested in libj2_j2i_lsh.c */
 
 #endif