aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--libj2/bit-shifting.h171
-rw-r--r--libj2_j2i_lsh.c134
-rw-r--r--libj2_ji_lsh_overflow_p.c2
-rw-r--r--libj2_ji_lsh_to_j2i.c3
-rw-r--r--libj2_ji_lsh_to_j2i_overflow.c2
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
generated by cgit v1.2.3-70-g09d2 (git 2.51.0) at 2025-12-25 18:24:49 +0000