commit 5860237d2f05f6ae45a98569b0d567c2227904c6
parent 8237156ffb390b38c55863d1b14f246af8a1c19c
Author: Mattias Andrée <maandree@kth.se>
Date: Sat, 5 Mar 2016 20:16:14 +0100
Fix bugs and add a randomised testing
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
14 files changed, 892 insertions(+), 55 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -4,3 +4,4 @@
*.a
*.so
/test
+/test-random.c
diff --git a/Makefile b/Makefile
@@ -58,7 +58,7 @@ FUN =\
OBJ = $(FUN:=.o)
MAN = $(foreach F,$(FUN),man/$(F).3) man/libzahl.7
-all: libzahl.a test
+all: libzahl.a
%.o: src/%.c $(HDR) config.mk
$(CC) $(CFLAGS) $(CPPFLAGS) -c -o $@ $<
@@ -67,13 +67,16 @@ libzahl.a: $(OBJ)
$(AR) rc $@ $?
$(RANLIB) $@
-test: test.c libzahl.a
- $(CC) $(LDFLAGS) $(CFLAGS) $(CPPFLAGS) -o $@ $^
+test-random.c: test-generate.py
+ ./test-generate.py > test-random.c
+
+test: test.c libzahl.a test-random.c
+ $(CC) $(LDFLAGS) $(CFLAGS) $(CPPFLAGS) -o $@ test.c libzahl.a
check: test
./test
clean:
- -rm -- *.o *.su *.a *.so test 2>/dev/null
+ -rm -- *.o *.su *.a *.so test test-random.c 2>/dev/null
.PHONY: all check clean
diff --git a/man/zsplit.3 b/man/zsplit.3
@@ -22,7 +22,12 @@ The result stored in
.I high
is shifted
.I n
-bits to the right.
+bits to the right. Both
+.I high
+and
+.I low
+will have the same sign as
+.IR a .
.P
It is safe to call
.B zsplit
diff --git a/src/zadd.c b/src/zadd.c
@@ -9,16 +9,20 @@ zadd_unsigned(z_t a, z_t b, z_t c)
uint32_t carry[] = {0, 0};
zahl_char_t *addend;
- if (a == c) {
- zadd_unsigned(a, c, b);
+ if (zzero(b)) {
+ zabs(a, c);
+ return;
+ } else if (zzero(c)) {
+ zabs(a, b);
return;
}
size = MAX(b->used, c->used);
+ n = b->used + c->used - size;
+
ENSURE_SIZE(a, size + 1);
a->chars[size] = 0;
- n = b->used + c->used - size;
if (a == b) {
if (a->used < c->used) {
n = c->used;
@@ -56,7 +60,7 @@ zadd_unsigned(z_t a, z_t b, z_t c)
if (a->used < i)
a->used = i;
- SET_SIGNUM(a, !zzero(b) | !zzero(c));
+ SET_SIGNUM(a, 1);
}
diff --git a/src/zdivmod.c b/src/zdivmod.c
@@ -32,8 +32,6 @@ zdivmod(z_t a, z_t b, z_t c, z_t d)
zseti(a, sign);
SET_SIGNUM(b, 0);
return;
- } else if (sign < 0) {
- zsub_unsigned(b, d, c);
} else {
SET(b, c);
}
diff --git a/src/zload.c b/src/zload.c
@@ -8,12 +8,9 @@ zload(z_t a, const void *buffer)
const char *buf = buffer;
a->sign = *((const int *)buf), buf += sizeof(int);
a->used = *((const size_t *)buf), buf += sizeof(size_t);
- a->alloced = 0;
- if (a->sign)
+ if (a->sign) {
ENSURE_SIZE(a, a->used);
- else
- a->chars = 0;
- if (!zzero(a))
zmemcpy(a->chars, buf, a->used);
+ }
return sizeof(int) + sizeof(size_t) + (zzero(a) ? 0 : a->used * sizeof(zahl_char_t));
}
diff --git a/src/znot.c b/src/znot.c
@@ -18,12 +18,12 @@ znot(z_t a, z_t b)
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;
+ bits = BITS_IN_LAST_CHAR(bits);
+ if (bits)
+ a->chars[a->used - 1] &= ((zahl_char_t)1 << bits) - 1;
- for (; a->used; a->used--)
- if (a->chars[a->used - 1])
- break;
+ while (a->used && !a->chars[a->used - 1])
+ a->used--;
if (!a->used)
SET_SIGNUM(a, 0);
}
diff --git a/src/zor.c b/src/zor.c
@@ -20,16 +20,17 @@ zor(z_t a, z_t b, z_t c)
m = MAX(b->used, c->used);
n = b->used + c->used - m;
- a->used = m;
ENSURE_SIZE(a, m);
if (a == b) {
- zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n);
+ if (b->used < c->used)
+ zmemcpy(a->chars + n, c->chars + n, m - n);
while (n--)
a->chars[n] |= c->chars[n];
} else if (a == c) {
- zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n);
+ if (c->used < b->used)
+ zmemcpy(a->chars + n, b->chars + n, m - n);
while (n--)
a->chars[n] |= b->chars[n];
} else if (m == b->used) {
@@ -42,5 +43,6 @@ zor(z_t a, z_t b, z_t c)
a->chars[n] |= b->chars[n];
}
+ a->used = m;
SET_SIGNUM(a, (zsignum(b) > 0 && zsignum(c) > 0) * 2 - 1);
}
diff --git a/src/zsplit.c b/src/zsplit.c
@@ -5,27 +5,17 @@
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 = FLOOR_BITS_TO_CHARS(delim);
-
if (high == a) {
- if (a->used < chars)
- SET_SIGNUM(low, 0);
- else
- ztrunc(low, a, delim);
+ 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);
+ ztrunc(low, a, delim);
}
}
diff --git a/src/zsub.c b/src/zsub.c
@@ -5,28 +5,49 @@
void
zsub_unsigned(z_t a, z_t b, z_t c)
{
- int magcmp = zcmpmag(b, c);
- z_t s;
- size_t i, n;
zahl_char_t carry[] = {0, 0};
+ zahl_char_t *s;
+ size_t i, n;
+ int magcmp;
+
+ if (zzero(b)) {
+ zabs(a, c);
+ zneg(a, a);
+ return;
+ } else if (zzero(c)) {
+ zabs(a, b);
+ return;
+ } else if (a == b || a == c) {
+ /* TODO This should not be necessary. */
+ z_t tb, tc;
+ zinit(tb);
+ zinit(tc);
+ zset(tb, b);
+ zset(tc, c);
+ zsub_unsigned(a, tb, tc);
+ zfree(tb);
+ zfree(tc);
+ return;
+ }
+ magcmp = zcmpmag(b, c);
if (magcmp <= 0) {
if (magcmp == 0) {
SET_SIGNUM(a, 0);
return;
}
SET(a, c);
- *s = *b;
+ n = MIN(a->used, b->used);
+ s = b->chars;
} else {
SET(a, b);
- *s = *c;
+ n = MIN(a->used, c->used);
+ s = c->chars;
}
- n = MIN(a->used, s->used);
-
for (i = 0; i < n; i++) {
- carry[~i & 1] = carry[i & 1] ? (a->chars[i] <= s->chars[i]) : (a->chars[i] < s->chars[i]);
- a->chars[i] -= s->chars[i];
+ carry[~i & 1] = carry[i & 1] ? (a->chars[i] <= s[i]) : (a->chars[i] < s[i]);
+ a->chars[i] -= s[i];
a->chars[i] -= carry[i & 1];
}
diff --git a/src/zxor.c b/src/zxor.c
@@ -21,19 +21,16 @@ zxor(z_t a, z_t b, z_t c)
m = MAX(b->used, c->used);
n = b->used + c->used - m;
- if (n == m && !zmemcmp(b->chars, c->chars, m)) {
- SET_SIGNUM(a, 0);
- return;
- }
-
ENSURE_SIZE(a, m);
if (a == b) {
- zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n);
+ if (b->used < c->used)
+ zmemcpy(a->chars + n, c->chars + n, m - n);
while (n--)
a->chars[n] ^= c->chars[n];
} else if (a == c) {
- zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n);
+ if (c->used < b->used)
+ zmemcpy(a->chars + n, b->chars + n, m - n);
while (n--)
a->chars[n] ^= b->chars[n];
} else if (m == b->used) {
@@ -46,5 +43,11 @@ zxor(z_t a, z_t b, z_t c)
a->chars[n] ^= b->chars[n];
}
- SET_SIGNUM(a, 1 - 2 * ((zsignum(b) ^ zsignum(c)) < 0));
+ a->used = m;
+ while (a->used && !a->chars[a->used - 1])
+ a->used--;
+ if (a->used)
+ SET_SIGNUM(a, 1 - 2 * ((zsignum(b) ^ zsignum(c)) < 0));
+ else
+ SET_SIGNUM(a, 0);
}
diff --git a/test-generate.py b/test-generate.py
@@ -0,0 +1,797 @@
+#!/usr/bin/env python3
+# See LICENSE file for copyright and license details.
+
+import random
+
+
+def mod(a, b):
+ return abs(a) % abs(b)
+
+def div(a, b): # Python's division is floored, not truncated.
+ r = abs(a) // abs(b)
+ if a < 0:
+ r = -r
+ if b < 0:
+ r = -r
+ return r
+
+def gcd(u, v):
+ if u == 0:
+ return v
+ if v == 0:
+ return u
+ uneg = u < 0
+ vneg = v < 0
+ u = abs(u)
+ v = abs(v)
+
+ shift = 0
+ while ((u | v) & 1) == 0:
+ u >>= 1
+ v >>= 1
+ shift += 1
+
+ while (u & 1) == 0:
+ u >>= 1
+
+ while True:
+ while (v & 1) == 0:
+ v >>= 1
+ if u > v:
+ (u, v) = (v, u)
+ v -= u
+ if v == 0:
+ break
+
+ u <<= shift
+ if uneg and vneg:
+ u = -u
+ return u
+
+
+def zabs():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ print('zabs(b, a);')
+ print('zabs(a, a);')
+ print('assert(zcmp(a, b), == 0);')
+ print('assert_s(zstr(a, buf), "%i");' % abs(a))
+
+def zadd():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = a + b
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zadd(c, a, b);')
+ print('zset(d, b);')
+ print('zadd(d, a, d);')
+ print('zadd(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+
+def zadd_unsigned():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = abs(a) + abs(b)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zadd_unsigned(c, a, b);')
+ print('zset(d, b);')
+ print('zadd_unsigned(d, a, d);')
+ print('zadd_unsigned(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ c = abs(b) * 2
+ print('zadd_unsigned(c, b, b);')
+ print('zadd_unsigned(b, b, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert(zcmp(b, c), == 0);')
+
+def zand():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = abs(a) & abs(b)
+ if a < 0 and b < 0:
+ c = -c
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zand(c, a, b);')
+ print('zset(d, b);')
+ print('zand(d, a, d);')
+ print('zand(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ print('zsets(a, "%i");' % a)
+ print('zand(d, a, a);')
+ print('zand(a, a, a);')
+ print('assert_s(zstr(d, buf), "%i");' % a)
+ print('assert_s(zstr(a, buf), "%i");' % a)
+
+def zbits():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ a = abs(a)
+ if a == 0:
+ b = 1
+ else:
+ b = 0
+ while a > 0:
+ b += 1
+ a >>= 1
+ print('assert_zu(zbits(a), %i);' % b)
+
+def zbset():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(0, 2 * LIMIT)
+ cs = (abs(a) | (1 << b)) * (-1 if a < 0 else 1)
+ cc = (abs(a) & ~(1 << b)) * (-1 if a < 0 else 1)
+ cf = (abs(a) ^ (1 << b)) * (-1 if a < 0 else 1)
+ print('zsets(a, "%i");' % a)
+ print('zset(d, a);')
+ print('zbset(b, a, %i, 1);' % b)
+ print('assert_s(zstr(b, buf), "%i");' % cs)
+ print('zbset(b, a, %i, 0);' % b)
+ print('assert_s(zstr(b, buf), "%i");' % cc)
+ print('zbset(b, a, %i, -1);' % b)
+ print('assert_s(zstr(b, buf), "%i");' % cf)
+ print('zset(a, d);')
+ print('zbset(a, a, %i, 1);' % b)
+ print('assert_s(zstr(a, buf), "%i");' % cs)
+ print('zset(a, d);')
+ print('zbset(a, a, %i, 0);' % b)
+ print('assert_s(zstr(a, buf), "%i");' % cc)
+ print('zset(a, d);')
+ print('zbset(a, a, %i, -1);' % b)
+ print('assert_s(zstr(a, buf), "%i");' % cf)
+
+def zbtest():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(0, 2 * LIMIT)
+ c = (abs(a) >> b) & 1
+ print('zsets(a, "%i");' % a)
+ print('assert(zbtest(a, %i), == %i);' % (b, c))
+
+def zcmp():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = -1 if a < b else (1 if a > b else 0)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('assert(zcmp(a, b), == %i);' % c)
+
+def zcmpmag():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ a = abs(a)
+ b = abs(b)
+ c = -1 if a < b else (1 if a > b else 0)
+ print('assert(zcmpmag(a, b), == %i);' % c)
+
+def zlsb():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ a = abs(a)
+ if a == 0:
+ b = "SIZE_MAX"
+ else:
+ b = 0
+ while (a & 1) == 0:
+ b += 1
+ a >>= 1
+ b = str(b)
+ print('assert_zu(zlsb(a), %s);' % b)
+
+def zlsh():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, 2 * LIMIT)
+ c = a << bits
+ print('zsets(a, "%i");' % a)
+ print('zlsh(b, a, %i);' % bits)
+ print('zlsh(a, a, %i);' % bits)
+ print('assert(zcmp(a, b), == 0);')
+ print('assert_s(zstr(a, buf), "%i");' % c)
+
+def zneg():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ print('zneg(b, a);')
+ print('zneg(a, a);')
+ print('assert(zcmp(a, b), == 0);')
+ print('assert_s(zstr(a, buf), "%i");' % -a)
+
+def zor():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = abs(a) | abs(b)
+ if a < 0 or b < 0:
+ c = -c
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zor(c, a, b);')
+ print('zset(d, b);')
+ print('zor(d, a, d);')
+ print('zor(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ print('zsets(a, "%i");' % a)
+ print('zor(d, a, a);')
+ print('zor(a, a, a);')
+ print('assert_s(zstr(d, buf), "%i");' % a)
+ print('assert_s(zstr(a, buf), "%i");' % a)
+
+def zrsh():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ c = (abs(a) >> bits) * (-1 if a < 0 else 1)
+ print('zsets(a, "%i");' % a)
+ print('zrsh(b, a, %i);' % bits)
+ print('zrsh(a, a, %i);' % bits)
+ print('assert(zcmp(a, b), == 0);')
+ print('assert_s(zstr(a, buf), "%i");' % c)
+
+def zsplit():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, 2 * LIMIT)
+ sign = -1 if a < 0 else 1
+ c = (abs(a) >> bits) * sign
+ d = (abs(a) - (abs(c) << bits)) * sign
+ print('zsets(a, "%i");' % a)
+ print('zset(b, a);')
+ print('zsplit(b, d, b, %i);' % bits)
+ print('assert_s(zstr(b, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zsplit(c, d, a, %i);' % bits)
+ print('assert(zcmp(b, c), == 0);')
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zsplit(c, a, a, %i);' % bits)
+ print('assert(zcmp(a, d), == 0);')
+ print('assert(zcmp(b, c), == 0);')
+
+def zstr():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ print('assert_s(zstr(a, buf), "%i");' % a)
+
+def zstr_length():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ print('assert_zu(zstr_length(a, 10), %i);' % len(str(a)))
+
+def zsub():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = a - b
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsub(c, a, b);')
+ print('zset(d, b);')
+ print('zsub(d, a, d);')
+ print('zsub(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+
+def zsub_unsigned():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = abs(a) - abs(b)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsub_unsigned(c, a, b);')
+ print('zset(d, b);')
+ print('zsub_unsigned(d, a, d);')
+ print('zsub_unsigned(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ print('zsub_unsigned(a, b, b);')
+ print('assert(zzero(a), == 1);')
+ print('zsub_unsigned(b, b, b);')
+ print('assert(zzero(b), == 1);')
+
+def ztrunc():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, 2 * LIMIT)
+ c = (abs(a) & ((1 << bits) - 1)) * (-1 if a < 0 else 1)
+ print('zsets(a, "%i");' % a)
+ print('ztrunc(b, a, %i);' % bits)
+ print('ztrunc(a, a, %i);' % bits)
+ print('assert(zcmp(a, b), == 0);')
+ print('assert_s(zstr(a, buf), "%i");' % c)
+
+def zxor():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = abs(a) ^ abs(b)
+ if (a < 0) != (b < 0):
+ c = -c
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zxor(c, a, b);')
+ print('zset(d, b);')
+ print('zxor(d, a, d);')
+ print('zxor(a, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % c)
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ print('zsets(a, "%i");' % a)
+ print('zxor(d, a, a);')
+ print('zxor(a, a, a);')
+ print('assert(zzero(d), == 1);')
+ print('assert(zzero(a), == 1);')
+
+def zeven():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = 1 if (abs(a) & 1) == 0 else 0
+ print('zsets(a, "%i");' % a)
+ print('assert(zeven(a), == %i);' % b)
+
+def zodd():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = 1 if (abs(a) & 1) != 0 else 0
+ print('zsets(a, "%i");' % a)
+ print('assert(zodd(a), == %i);' % b)
+
+def zeven_nonzero():
+ bits = random.randint(0, LIMIT)
+ a = 0
+ while a == 0:
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = 1 if (abs(a) & 1) == 0 else 0
+ print('zsets(a, "%i");' % a)
+ print('assert(zeven_nonzero(a), == %i);' % b)
+
+def zodd_nonzero():
+ bits = random.randint(0, LIMIT)
+ a = 0
+ while a == 0:
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = 1 if (abs(a) & 1) != 0 else 0
+ print('zsets(a, "%i");' % a)
+ print('assert(zodd_nonzero(a), == %i);' % b)
+
+def zzero():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = 1 if a == 0 else 0
+ print('zsets(a, "%i");' % a)
+ print('assert(zzero(a), == %i);' % b)
+
+def zsignum():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = -1 if a < 0 else (1 if a > 0 else 0)
+ print('zsets(a, "%i");' % a)
+ print('assert(zsignum(a), == %i);' % b)
+
+def zdiv():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = 0
+ while b == 0:
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = div(a, b)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(d, "%i");' % c)
+ print('zdiv(c, a, b);')
+ print('zdiv(a, a, b);')
+ print('assert(zcmp(c, d), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zdiv(b, a, b);')
+ print('assert(zcmp(b, d), == 0);')
+
+def zmod():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = 0
+ while b == 0:
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = mod(a, b)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(d, "%i");' % c)
+ print('zmod(c, a, b);')
+ print('zmod(a, a, b);')
+ print('assert(zcmp(c, d), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zmod(b, a, b);')
+ print('assert(zcmp(b, d), == 0);')
+
+def zdivmod():
+ bits = random.randint(0, LIMIT)
+ ap = random.randint(0, 1 << bits)
+ bits = random.randint(0, LIMIT)
+ bp = 0
+ while bp == 0:
+ bp = random.randint(0, 1 << bits)
+ for (a_sign, b_sign) in ((1, 1), (1, -1), (-1, 1), (-1, -1)):
+ a = ap * a_sign
+ b = bp * b_sign
+ (c, d) = (div(a, b), mod(a, b))
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(c, d, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zdivmod(a, b, a, b);')
+ print('assert(zcmp(a, c), == 0);')
+ print('assert(zcmp(b, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(b, a, a, b);')
+ print('assert(zcmp(b, c), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(b, a, b, b);')
+ print('assert(zcmpu(b, 1), == 0);')
+ print('assert(zcmpu(a, 0), == 0);')
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(a, b, b, b);')
+ print('assert(zcmpu(a, 1), == 0);')
+ print('assert(zcmpu(b, 0), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(a, d, a, b);')
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zdivmod(c, b, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(b, buf), "%i");' % d)
+ a = bp * a_sign
+ b = bp * b_sign
+ (c, d) = (div(a, b), mod(a, b))
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(c, d, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zdivmod(a, b, a, b);')
+ print('assert(zcmp(a, c), == 0);')
+ print('assert(zcmp(b, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(b, a, a, b);')
+ print('assert(zcmp(b, c), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(b, a, b, b);')
+ print('assert(zcmpu(b, 1), == 0);')
+ print('assert(zcmpu(a, 0), == 0);')
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(a, b, b, b);')
+ print('assert(zcmpu(a, 1), == 0);')
+ print('assert(zcmpu(b, 0), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zdivmod(a, d, a, b);')
+ print('assert_s(zstr(a, buf), "%i");' % c)
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zdivmod(c, b, a, b);')
+ print('assert_s(zstr(c, buf), "%i");' % c)
+ print('assert_s(zstr(b, buf), "%i");' % d)
+
+def zmul():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = a * b
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(d, "%i");' % c)
+ print('zmul(c, a, b);')
+ print('assert(zcmp(c, d), == 0);')
+ print('zmul(c, b, a);')
+ print('assert(zcmp(c, d), == 0);')
+ print('zmul(a, a, b);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zmul(b, a, b);')
+ print('assert(zcmp(b, d), == 0);')
+ c = a * a
+ print('zsets(d, "%i");' % c)
+ print('zmul(c, a, a);')
+ print('assert(zcmp(c, d), == 0);')
+ print('zmul(a, a, a);')
+ print('assert(zcmp(a, d), == 0);')
+
+def zsqr():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ c = a * a
+ print('zsets(a, "%i");' % a)
+ print('zsets(d, "%i");' % c)
+ print('zsqr(c, a);')
+ print('assert(zcmp(c, d), == 0);')
+ print('zsqr(a, a);')
+ print('assert(zcmp(a, d), == 0);')
+
+def zmodmul():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ c = 0
+ while c == 0:
+ c = random.randint(-(1 << bits), 1 << bits)
+ d = mod(a * b, c)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(c, "%i");' % c)
+ print('zmodmul(d, a, b, c);')
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zmodmul(a, a, b, c);')
+ print('assert_s(zstr(a, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zmodmul(b, a, b, c);')
+ print('assert_s(zstr(b, buf), "%i");' % d)
+ print('zsets(b, "%i");' % b)
+ print('zmodmul(c, a, b, c);')
+ print('assert_s(zstr(c, buf), "%i");' % d)
+ print('zsets(c, "%i");' % c)
+ print('zmodmul(d, b, a, c);')
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zmodmul(a, b, a, c);')
+ print('assert_s(zstr(a, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zmodmul(b, b, a, c);')
+ print('assert_s(zstr(b, buf), "%i");' % d)
+ print('zsets(b, "%i");' % b)
+ print('zmodmul(c, b, a, c);')
+ print('assert_s(zstr(c, buf), "%i");' % d)
+ print('zsets(c, "%i");' % c)
+ d = mod(a * a, c)
+ print('zmodmul(d, a, a, c);')
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('zmodmul(a, a, a, c);')
+ print('assert_s(zstr(a, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zmodmul(c, a, a, c);')
+ print('assert_s(zstr(c, buf), "%i");' % d)
+ if a != 0:
+ d = mod(a * b, a)
+ print('zsets(d, "%i");' % d)
+ print('zmodmul(c, a, b, a);')
+ print('assert_s(zstr(c, buf), "%i");' % d)
+ print('zmodmul(a, a, b, a);')
+ print('assert_s(zstr(a, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zmodmul(b, a, b, a);')
+ print('assert_s(zstr(b, buf), "%i");' % d)
+ print('zsets(b, "%i");' % b)
+ print('zmodmul(c, b, a, a);')
+ print('assert_s(zstr(c, buf), "%i");' % d)
+ print('zmodmul(a, b, a, a);')
+ print('assert_s(zstr(a, buf), "%i");' % d)
+ print('zsets(a, "%i");' % a)
+ print('zmodmul(b, b, a, a);')
+ print('assert_s(zstr(b, buf), "%i");' % d)
+ print('zmodmul(b, a, a, a);')
+ print('assert(zzero(b), == 1);')
+ print('zmodmul(a, a, a, a);')
+ print('assert(zzero(a), == 1);')
+
+def zmodsqr():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = 0
+ while b == 0:
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = mod(a ** 2, b)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(d, "%i");' % c)
+ print('zmodsqr(c, a, b);')
+ print('assert(zcmp(c, d), == 0);')
+ print('zset(c, a);')
+ print('zmodsqr(a, a, b);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zset(a, c);')
+ print('zset(c, b);')
+ print('zmodsqr(b, a, b);')
+ print('assert(zcmp(b, d), == 0);')
+ if a != 0:
+ c = mod(a ** 2, a)
+ print('zmodsqr(b, a, a);')
+ print('assert(zzero(b), == 1);')
+ print('zmodsqr(a, a, a);')
+ print('assert(zzero(a), == 1);')
+
+def zcmpi():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(-(1 << 63), (1 << 63) - 1)
+ c = -1 if a < b else (1 if a > b else 0)
+ print('zsets(a, "%i");' % a)
+ if b >= 0:
+ print('assert(zcmpi(a, %iLL), == %i);' % (b, c))
+ else:
+ print('assert(zcmpi(a, %iLL - 1LL), == %i);' % (b + 1, c))
+
+def zcmpu():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(0, (1 << 64) - 1)
+ c = -1 if a < b else (1 if a > b else 0)
+ print('zsets(a, "%i");' % a)
+ print('assert(zcmpu(a, %iULL), == %i);' % (b, c))
+
+def zgcd():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ bits = random.randint(0, LIMIT)
+ b = random.randint(-(1 << bits), 1 << bits)
+ c = gcd(a, b)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(d, "%i");' % c)
+ print('zgcd(c, a, b);')
+ print('assert(zcmp(c, d), == 0);')
+
+def zpow():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(1, 16)
+ c = a ** b
+ print('zsets(a, "%i");' % a)
+ print('zsetu(b, %i);' % b)
+ print('zsets(d, "%i");' % c)
+ print('zpow(c, a, b);')
+ print('zpow(a, a, b);')
+ print('assert(zcmp(c, d), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zpow(b, a, b);')
+ print('assert(zcmp(b, d), == 0);')
+
+def zpowu():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(1, 16)
+ c = a ** b
+ print('zsets(a, "%i");' % a)
+ print('zsets(d, "%i");' % c)
+ print('zpowu(c, a, %i);' % b)
+ print('zpowu(a, a, %i);' % b)
+ print('assert(zcmp(c, d), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+
+def zmodpowu():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(1, 16)
+ bits = random.randint(0, LIMIT)
+ c = 0
+ while c == 0:
+ c = random.randint(-(1 << bits), 1 << bits)
+ d = mod(a ** b, c)
+ print('zsets(a, "%i");' % a)
+ print('zsets(c, "%i");' % c)
+ print('zsets(d, "%i");' % d)
+ print('zmodpowu(b, a, %i, c);' % b)
+ print('zmodpowu(a, a, %i, c);' % b)
+ print('assert(zcmp(b, d), == 0);')
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zmodpowu(c, a, %i, c);' % b)
+ print('assert(zcmp(c, d), == 0);')
+
+def zmodpow():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ b = random.randint(1, 16)
+ bits = random.randint(0, LIMIT)
+ c = 0
+ while c == 0:
+ c = random.randint(-(1 << bits), 1 << bits)
+ d = mod(a ** b, c)
+ print('zsets(a, "%i");' % a)
+ print('zsets(b, "%i");' % b)
+ print('zsets(c, "%i");' % c)
+ print('zsets(d, "%i");' % d)
+ print('zmodpow(d, a, b, c);')
+ print('zmodpow(a, a, b, c);')
+ print('assert_s(zstr(d, buf), "%i");' % d)
+ print('assert(zcmp(a, d), == 0);')
+ print('zsets(a, "%i");' % a)
+ print('zmodpow(b, a, b, c);')
+ print('assert(zcmp(b, d), == 0);')
+ print('zsets(b, "%i");' % b)
+ print('zmodpow(c, a, b, c);')
+ print('assert(zcmp(c, d), == 0);')
+
+def znot():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ sign = -(-1 if a < 0 else 1)
+ b = abs(a)
+ bits = 0
+ x = b
+ while x > 0:
+ bits += 1
+ x >>= 1
+ b = ~b
+ b &= (1 << bits) - 1
+ b *= sign
+ print('zsets(a, "%i");' % a)
+ print('zsets(c, "%i");' % b)
+ print('znot(b, a);')
+ print('znot(a, a);')
+ print('assert(zcmp(b, c), == 0);')
+ print('assert(zcmp(a, c), == 0);')
+
+def zsave_zload():
+ bits = random.randint(0, LIMIT)
+ a = random.randint(-(1 << bits), 1 << bits)
+ print('zsets(a, "%i");' % a)
+ print('n = zsave(a, 0);')
+ print('assert_zu(zsave(a, buf), n);')
+ print('assert_zu(zload(b, buf), n);')
+ print('assert(zcmp(a, b), == 0);')
+
+
+
+functions = [zzero, zsignum, zeven_nonzero, zodd_nonzero, zeven, zcmp, zcmpi, zcmpu, zcmpmag,
+ zodd, zabs, zneg, zlsh, zrsh, ztrunc, zsplit, zand, zor, zxor, zbits, zlsb, znot,
+ zbtest, zbset, zadd_unsigned, zsub_unsigned, zadd, zsub, zmul, zsqr, zdivmod,
+ zdiv, zmod, zmodmul, zmodsqr, zsave_zload, zgcd, zpow, zpowu, zmodpow, zmodpowu,
+ zstr_length, zstr] # untested: zptest, zrand
+
+limits = [200]
+
+for LIMIT in limits:
+ for function in functions:
+ print('/* %s */' % function.__qualname__)
+ for i in range(100):
+ function()
+ print()
+ print()
+
diff --git a/test.c b/test.c
@@ -62,7 +62,7 @@ main(void)
/* static because otherwise it would have to be volatile yeilding a lot of stupid
* warnings. auto variables are not guaranteed to be readable after a long jump. */
static z_t a, b, c, d, _0, _1, _2, _3;
- static char buf[1000];
+ static char buf[2000];
static int ret = 0;
static jmp_buf env, env2;
static size_t n;
@@ -309,6 +309,19 @@ main(void)
assert((zadd_unsigned(a, b, _2), zcmp(a, _3)), == 0);
assert((zadd_unsigned(a, _1, c), zcmp(a, _3)), == 0);
+ assert((zadd_unsigned(a, _0, _0), zcmp(a, _0)), == 0);
+ assert((zadd_unsigned(a, _0, _1), zcmp(a, _1)), == 0);
+ assert((zadd_unsigned(a, _1, _1), zcmp(a, _2)), == 0);
+ assert((zadd_unsigned(a, _1, _0), zcmp(a, _1)), == 0);
+ zneg(_1, _1);
+ assert((zadd_unsigned(a, _0, _0), zcmp(a, _0)), == 0);
+ assert((zadd_unsigned(a, _0, _1), zcmp(a, _1)), != 0);
+ assert((zadd_unsigned(a, _0, _1), zcmpmag(a, _1)), == 0);
+ assert((zadd_unsigned(a, _1, _1), zcmp(a, _2)), == 0);
+ assert((zadd_unsigned(a, _1, _0), zcmp(a, _1)), != 0);
+ assert((zadd_unsigned(a, _1, _0), zcmpmag(a, _1)), == 0);
+ zneg(_1, _1);
+
assert((zsub_unsigned(a, _2, _1), zcmp(a, _1)), == 0);
assert((zsub_unsigned(a, _2, b), zcmp(a, _1)), == 0);
assert((zsub_unsigned(a, c, _1), zcmp(a, _1)), == 0);
@@ -992,8 +1005,11 @@ main(void)
zsqr(a, a);
assert_s(zstr(a, buf), "1000000000000000000000000000000");
+#include "test-random.c"
+
done:
zfree(a), zfree(b), zfree(c), zfree(d), zfree(_0), zfree(_1), zfree(_2), zfree(_3);
zunsetup();
return ret;
}
+
diff --git a/zahl.h b/zahl.h
@@ -86,7 +86,7 @@ void zpowu(z_t, z_t, unsigned long long int);
void zmodpowu(z_t, z_t, unsigned long long int, z_t);
/* These are used internally and may be removed in a future version. */
-void zadd_unsigned(z_t, z_t, z_t); /* a := |b| + |c|, b and c must not be the same reference. */
+void zadd_unsigned(z_t, z_t, z_t); /* a := |b| + |c| */
void zsub_unsigned(z_t, z_t, z_t); /* a := |b| - |c| */
