commit 3ae8c069900514c1785fe4a84b6cdb0157dff59e
parent 5810e189b55eaf51912dace3f338e1c4f68c199c
Author: Mattias Andrée <maandree@kth.se>
Date: Wed, 2 Mar 2016 21:07:08 +0100
Add zand, zor, zxor, znot, zbtest, zsplit, and the newly introduced ztrunc
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
13 files changed, 304 insertions(+), 1 deletion(-)
diff --git a/man/zinit.3 b/man/zinit.3
@@ -43,6 +43,7 @@ typedef struct {
.BR znot (3),
.BR zlsh (3),
.BR zrsh (3),
+.BR ztrunc (3),
.BR zsplit (3),
.BR zadd (3),
.BR zsub (3),
diff --git a/man/zlsh.3 b/man/zlsh.3
@@ -25,6 +25,7 @@ with
.BR zxor (3),
.BR znot (3),
.BR zrsh (3),
+.BR ztrunc (3),
.BR zsplit (3),
.BR zbtest (3),
.BR zlsb (3),
diff --git a/man/zrsh.3 b/man/zrsh.3
@@ -25,6 +25,7 @@ with
.BR zxor (3),
.BR znot (3),
.BR zlsh (3),
+.BR ztrunc (3),
.BR zsplit (3),
.BR zbtest (3),
.BR zlsb (3),
diff --git a/man/zset.3 b/man/zset.3
@@ -25,4 +25,5 @@ remains unchanged.
.BR zsets (3),
.BR zswap (3),
.BR zabs (3),
-.BR zneg (3)
+.BR zneg (3),
+.BR ztrunc (3)
diff --git a/man/ztrunc.3 b/man/ztrunc.3
@@ -0,0 +1,39 @@
+.TH ZTRUNC 3 libzahl
+.SH NAME
+ztrunc - Truncate a big integer
+.SH SYNOPSIS
+.nf
+#include <zahl.h>
+
+void ztrunc(z_t \fIa\fP, z_t \fIb\fP, size_t \fIbits\fP);
+.fi
+.SH DESCRIPTION
+.B ztrunc
+makes a truncated copy of
+.I b
+and stores it in
+.I a .
+Only the first
+.I bits
+from
+.I b
+and
+.IR b 's
+sign is copied to
+.I a .
+.P
+It is safe to call
+.B zsplit
+with non-unique parameters.
+.SH RATIONALE
+This was useful for improving the performance of
+.BR zsplit (3).
+.SH SEE ALSO
+.BR zand (3),
+.BR zor (3),
+.BR zxor (3),
+.BR znot (3),
+.BR zlsh (3),
+.BR zrsh (3),
+.BR zsplit (3),
+.BR zbits (3)
diff --git a/src/zand.c b/src/zand.c
@@ -0,0 +1,42 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+#include <string.h>
+
+
+void
+zand(z_t a, z_t b, z_t c)
+{
+ size_t n;
+
+ if (zzero(b) || zzero(c)) {
+ SET_SIGNUM(a, 0);
+ return;
+ }
+
+ n = b->used < c->used ? b->used : c->used;
+ while (n--)
+ if (b->chars[n] & c->chars[n])
+ goto found_highest;
+ SET_SIGNUM(a, 0);
+ return;
+
+found_highest:
+ a->used = ++n;
+ if (a == b) {
+ while (n--)
+ a->chars[n] &= c->chars[n];
+ } else if (a == c) {
+ while (n--)
+ a->chars[n] &= b->chars[n];
+ } else {
+ if (a->alloced < a->used) {
+ a->alloced = a->used;
+ a->chars = realloc(a->chars, a->used * sizeof(*(a->chars)));
+ }
+ memcpy(a->chars, c->chars, a->used * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] &= b->chars[n];
+ }
+ SET_SIGNUM(a, (zsignum(b) > 0 || zsignum(c) > 0) * 2 - 1);
+}
diff --git a/src/zbtest.c b/src/zbtest.c
@@ -0,0 +1,18 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+
+int
+zbtest(z_t a, size_t bit)
+{
+ size_t chars;
+ if (zzero(a))
+ return 0;
+
+ chars = bit >> LB_BITS_PER_CHAR;
+ if (chars >= a->used)
+ return 0;
+
+ bit &= BITS_PER_CHAR - 1;
+ return (a->chars[chars] >> bit) & 1;
+}
diff --git a/src/znot.c b/src/znot.c
@@ -0,0 +1,30 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+
+void
+znot(z_t a, z_t b)
+{
+ size_t bits, n;
+
+ if (zzero(b)) {
+ SET_SIGNUM(a, 0)
+ return;
+ }
+
+ bits = zbits(b);
+ if (a != b)
+ zset(a, b);
+ SET_SIGNUM(a, -zsignum(a));
+
+ for (n = a->used; n--;)
+ a->chars[n] = ~(a->chars[n]);
+ bits &= BITS_PER_CHAR - 1;
+ a->chars[a->used - 1] &= ((zahl_char_t)1 << bits) - 1;
+
+ while (; a->used; a->used--)
+ if (a->chars[a->used - 1])
+ break;
+ if (!a->used)
+ SET_SIGNUM(a, 0);
+}
diff --git a/src/zor.c b/src/zor.c
@@ -0,0 +1,51 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+
+void
+zor(z_t a, z_t b, z_t c)
+{
+ size_t n, m;
+
+ if (zzero(b)) {
+ if (zzero(c)) {
+ SET_SIGNUM(a, 0);
+ } else {
+ if (a != c)
+ zset(a, c);
+ }
+ return;
+ } else if (zzero(c)) {
+ if (a != b)
+ zset(a, b);
+ return;
+ }
+
+ m = b->used > c->used ? b->used : c->used;
+ n = b->used + c->used - m;
+
+ if (a->alloced < m) {
+ a->alloced = m;
+ a->chars = realloc(a->chars, m * sizeof(*(a->chars)));
+ }
+
+ if (a == b) {
+ memcpy(a->chars + n, m == b->used ? b->chars : c->chars, (m - n) * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] |= c->chars[n];
+ } else if (a == c) {
+ memcpy(a->chars + n, m == b->used ? b->chars : c->chars, (m - n) * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] |= b->chars[n];
+ } else if (m == b->used) {
+ memcpy(a->chars, b->chars, m * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] |= c->chars[n];
+ } else {
+ memcpy(a->chars, c->chars, m * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] |= b->chars[n];
+ }
+
+ SET_SIGNUM(a, (zsignum(b) > 0 && zsignum(c) > 0) * 2 - 1);
+}
diff --git a/src/zsplit.c b/src/zsplit.c
@@ -0,0 +1,31 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+
+void
+zsplit(z_t high, z_t low, z_t a, size_t delim)
+{
+ size_t chars;
+
+ if (zzero(a)) {
+ SET_SIGNUM(high, 0);
+ SET_SIGNUM(low, 0);
+ return;
+ }
+
+ chars = delim >> LB_BITS_PER_CHAR;
+
+ if (high == a) {
+ if (a->used < chars)
+ SET_SIGNUM(low, 0);
+ else
+ ztrunc(low, a, delim);
+ zrsh(high, a, delim);
+ } else {
+ zrsh(high, a, delim);
+ if (a->used < chars)
+ SET_SIGNUM(low, 0);
+ else
+ ztrunc(low, a, delim);
+ }
+}
diff --git a/src/ztrunc.c b/src/ztrunc.c
@@ -0,0 +1,31 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+#include <stdlib.h>
+#include <string.h>
+
+
+void
+ztrunc(z_t a, z_t b, size_t bits)
+{
+ zahl_char_t mask = 1;
+ size_t chars;
+ if (zzero(b)) {
+ SET_SIGNUM(a, 0);
+ } else {
+ chars = CEILING_BITS_TO_CHARS(bits);
+ a->sign = b->sign;
+ a->used = chars < b->used ? chars : b->used;
+ if (a->alloced < b->alloced) {
+ a->alloced = b->alloced;
+ a->chars = realloc(a->chars, b->alloced * sizeof(*(a->chars)));
+ }
+ memcpy(a->chars, b->chars, a->used * sizeof(*(a->chars)));
+ bits = BITS_IN_LAST_CHAR(bits);
+ if (bits) {
+ mask <<= bits;
+ mask -= 1;
+ a->chars[a->used - 1] &= mask;
+ }
+ }
+}
diff --git a/src/zxor.c b/src/zxor.c
@@ -0,0 +1,56 @@
+/* See LICENSE file for copyright and license details. */
+#include "internals"
+
+
+void
+zxor(z_t a, z_t b, z_t c)
+{
+ size_t n, m;
+
+ if (zzero(b)) {
+ if (zzero(c)) {
+ SET_SIGNUM(a, 0);
+ } else {
+ if (a != c)
+ zset(a, c);
+ }
+ return;
+ } else if (zzero(c)) {
+ if (a != b)
+ zset(a, b);
+ return;
+ }
+
+ m = b->used > c->used ? b->used : c->used;
+ n = b->used + c->used - m;
+
+ if (n == m && !memcmp(b->chars, c->chars, m * sizeof(*(b->chars)))) {
+ SET_SIGNUM(a, 0);
+ return;
+ }
+
+ if (a->alloced < m) {
+ a->alloced = m;
+ a->chars = realloc(a->chars, m * sizeof(*(a->chars)));
+ }
+
+ if (a == b) {
+ memcpy(a->chars + n, m == b->used ? b->chars : c->chars, (m - n) * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] ^= c->chars[n];
+ } else if (a == c) {
+ memcpy(a->chars + n, m == b->used ? b->chars : c->chars, (m - n) * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] ^= b->chars[n];
+ } else if (m == b->used) {
+ memcpy(a->chars, b->chars, m * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] ^= c->chars[n];
+ } else {
+ memcpy(a->chars, c->chars, m * sizeof(*(a->chars)));
+ while (n--)
+ a->chars[n] ^= b->chars[n];
+ }
+
+ SET_SIGNUM(a, 1 - 2 * ((zsignum(b) ^ zsignum(c)) < 0);
+}
diff --git a/zahl.h b/zahl.h
@@ -92,6 +92,7 @@ void zxor(z_t, z_t, z_t); /* a := b ^ c */
void znot(z_t, z_t); /* a := ~b */
void zlsh(z_t, z_t, size_t); /* a := b << c */
void zrsh(z_t, z_t, size_t); /* a := b >> c */
+void ztrunc(z_t, z_t, size_t); /* a := b & ((1 << c) - 1) */
int zbtest(z_t, size_t); /* (a >> b) & 1 */
void zsplit(z_t, z_t, z_t, size_t); /* a := c >> d, b := c - (a << d) */
size_t zbits(z_t); /* ⌊log₂ |a|⌋ + 1, 1 if a = 0 */
