libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

commit d6987458f21cf1890045f2606d0f8ec4d2225b44
parent d2998cadfbdf13a427966a44a17767c316d6d410
Author: Mattias Andrée <maandree@kth.se>
Date:   Thu,  3 Mar 2016 23:02:59 +0100

Cleanup and fix bug in ztrunc

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

Diffstat:
Msrc/internals.h | 24++++++++++++++++++++++--
Msrc/zabs.c | 3+--
Msrc/zadd.c | 25+++++++++----------------
Msrc/zand.c | 13++++---------
Msrc/zbset.c | 14++++----------
Msrc/zdivmod.c | 10+++++-----
Msrc/zfree.c | 4----
Msrc/zgcd.c | 11++++-------
Msrc/zload.c | 15+++++----------
Msrc/zlsh.c | 25++++++++++---------------
Msrc/zmul.c | 2+-
Msrc/zneg.c | 3+--
Msrc/znot.c | 3+--
Msrc/zor.c | 30+++++++++++-------------------
Msrc/zrsh.c | 16+++++-----------
Msrc/zsave.c | 7++-----
Msrc/zset.c | 11+++--------
Msrc/zsets.c | 8+++-----
Msrc/zsetu.c | 8++------
Msrc/zstr.c | 1-
Msrc/zsub.c | 18++++++------------
Msrc/ztrunc.c | 44+++++++++++++++++++++++---------------------
Msrc/zxor.c | 32++++++++++++--------------------
23 files changed, 134 insertions(+), 193 deletions(-)

diff --git a/src/internals.h b/src/internals.h @@ -1,6 +1,9 @@ /* See LICENSE file for copyright and license details. */ #include "../zahl.h" +#include <string.h> +#include <stdlib.h> + #define BITS_PER_CHAR 32 #define LB_BITS_PER_CHAR 5 #define ZAHL_CHAR_MAX UINT32_MAX @@ -43,6 +46,23 @@ extern z_t libzahl_tmp_divmod_ds[BITS_PER_CHAR]; extern jmp_buf libzahl_jmp_buf; extern int libzahl_set_up; -#define FAILURE_JUMP() (longjmp(libzahl_jmp_buf, 1)) +#define FAILURE_JUMP() longjmp(libzahl_jmp_buf, 1) +#define zmemcpy(d, s, n) memcpy(d, s, (n) * sizeof(zahl_char_t)) +#define zmemmove(d, s, n) memmove(d, s, (n) * sizeof(zahl_char_t)) +#define zmemset(a, v, n) memset(a, v, (n) * sizeof(zahl_char_t)) +#define zmemcmp(a, b, n) memcmp(a, b, (n) * sizeof(zahl_char_t)) + +#define SET_SIGNUM(a, signum) ((a)->sign = (signum)) +#define SET(a, b) do { if (a != b) zset(a, b)} while (0) + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) +#define MAX(a, b) ((a) > (b) ? (a) : (b)) -#define SET_SIGNUM(a, signum) ((a)->sign = (signum)) +static inline void +zahl_realloc(z_t *p, size_t n) +{ + p->chars = realloc(p->chars, n * sizeof(zahl_char_t)); + if (!p->chars) + FAILURE_JUMP(); + p->alloced = n; +} diff --git a/src/zabs.c b/src/zabs.c @@ -5,7 +5,6 @@ void zabs(z_t a, z_t b) { - if (a != b) - zset(a, b); + SET(a, b); SET_SIGNUM(a, !zzero(a)); } diff --git a/src/zadd.c b/src/zadd.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zadd_unsigned(z_t a, z_t b, z_t c) @@ -17,32 +14,30 @@ zadd_unsigned(z_t a, z_t b, z_t c) return; } - size = b->used > c->used ? b->used : c->used; - if (a->alloced < size + 1) { - a->alloced = size + 1; - a->chars = realloc(a->chars, a->alloced * sizeof(*(a->chars))); - } + size = MAX(b->used, c->used); + if (a->alloced < size + 1) + zahl_realloc(a, size + 1); a->chars[size] = 0; n = b->used + c->used - size; if (a == b) { if (a->used < c->used) { n = c->used; - memset(a->chars + a->used, 0, (n - a->used) * sizeof(*(a->chars))); + zmemset(a->chars + a->used, 0, n - a->used); } addend = c->chars; } else if (a == c) { if (a->used < b->used) { n = b->used; - memset(a->chars + a->used, 0, (n - a->used) * sizeof(*(a->chars))); + zmemset(a->chars + a->used, 0, n - a->used); } addend = b->chars; } else if (b->used > c->used) { - memcpy(a->chars, b->chars, b->used * sizeof(*(a->chars))); + zmemcpy(a->chars, b->chars, b->used); a->used = b->used; addend = c->chars; } else { - memcpy(a->chars, c->chars, c->used * sizeof(*(a->chars))); + zmemcpy(a->chars, c->chars, c->used)); a->used = c->used; addend = b->chars; } @@ -70,11 +65,9 @@ void zadd(z_t a, z_t b, z_t c) { if (zzero(b)) { - if (a != b) - zset(a, c); + SET(a, c); } else if (zzero(c)) { - if (a != b) - zset(a, b); + SET(a, b); } else if (b == c) { zlsh(a, b, 1); } else if ((zsignum(b) | zsignum(c)) < 0) { diff --git a/src/zand.c b/src/zand.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zand(z_t a, z_t b, z_t c) @@ -15,7 +12,7 @@ zand(z_t a, z_t b, z_t c) return; } - n = b->used < c->used ? b->used : c->used; + n = MIN(b->used, c->used); while (n--) if (b->chars[n] & c->chars[n]) goto found_highest; @@ -31,11 +28,9 @@ found_highest: 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))); + if (a->alloced < a->used) + zahl_realloc(a, a->used); + zmemcpy(a->chars, c->chars, a->used); while (n--) a->chars[n] &= b->chars[n]; } diff --git a/src/zbset.c b/src/zbset.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zbset(z_t a, z_t b, size_t bit, int action) @@ -15,8 +12,7 @@ zbset(z_t a, z_t b, size_t bit, int action) bit = BITS_IN_LAST_CHAR(bit); x <<= bit; - if (a != b) - zset(a, b); + SET(a, b); if (action) { if (zzero(a)) { @@ -24,11 +20,9 @@ zbset(z_t a, z_t b, size_t bit, int action) SET_SIGNUM(a, 1); } if (a->used <= chars) { - if (a->alloced <= chars) { - a->alloced = chars + 1; - a->chars = realloc(a->chars, a->alloced * sizeof(*(a->chars))); - } - memset(a->chars + a->used, 0, (chars - a->used + 1) * sizeof(*(a->chars))); + if (a->alloced <= chars) + zahl_realloc(a, chars + 1); + zmemset(a->chars + a->used, 0, chars - a->used + 1); } } diff --git a/src/zdivmod.c b/src/zdivmod.c @@ -36,8 +36,8 @@ zdivmod(z_t a, z_t b, z_t c, z_t d) return; } else if (sign < 0) { zsub_unsigned(b, d, c); - } else if (b != c) { - zset(b, c); + } else { + SET(b, c); } SET_SIGNUM(b, 1); SET_SIGNUM(a, 0); @@ -82,13 +82,13 @@ zdivmod(z_t a, z_t b, z_t c, z_t d) goto done; zrsh(td[i], td[i], 1); } - for (i = bit < BITS_PER_CHAR ? bit : BITS_PER_CHAR; i--;) + for (i = MIN(bit, BITS_PER_CHAR); i--;) zrsh(tds[i], tds[i], BITS_PER_CHAR); } } done: - zset(a, ta); - zset(b, tb); + zswap(a, ta); + zswap(b, tb); SET_SIGNUM(a, sign); } diff --git a/src/zfree.c b/src/zfree.c @@ -1,13 +1,9 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> - void zfree(z_t a) { free(a->chars); - a->alloced = 0; - a->chars = 0; } diff --git a/src/zgcd.c b/src/zgcd.c @@ -17,18 +17,15 @@ zgcd(z_t a, z_t b, z_t c) int neg; if (!zcmp(b, c)) { - if (a != b) - zset(a, b); + SET(a, b); return; } if (zzero(b)) { - if (a != c) - zset(a, c); + SET(a, c); return; } if (zzero(c)) { - if (a != b) - zset(a, b); + SET(a, b); return; } @@ -36,7 +33,7 @@ zgcd(z_t a, z_t b, z_t c) zabs(v, c); neg = zsignum(b) < 0 && zsignum(c) < 0; - min = u->used < v->used ? u->used : v->used; + min = MIN(u->used, v->used); for (; i < min; i++) { uv = u->chars[i] | v->used[i]; for (bit = 1; bit; bit <<= 1, shifts++) diff --git a/src/zload.c b/src/zload.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - size_t zload(z_t a, const void *buffer) @@ -12,13 +9,11 @@ zload(z_t a, const void *buffer) a->sign = *((int *)buf), buf += sizeof(int); a->used = *((size_t *)buf), buf += sizeof(size_t); a->alloced = *((size_t *)buf), buf += sizeof(size_t); - if (a->alloced) { - a->chars = realloc(a->chars, a->alloced * sizeof(*(a->chars))); - } else { + if (a->alloced) + zahl_realloc(a, a->alloced); + else a->chars = 0; - } - if (!zzero(a)) { - memcpy(a->chars, buf, a->used * sizeof(*(a->chars))); - } + if (!zzero(a)) + zmemcpy(a->chars, buf, a->used); return sizeof(z_t) - sizeof(a->chars) + (zzero(a) ? 0 : a->used * sizeof(*(a->chars))); } diff --git a/src/zlsh.c b/src/zlsh.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zlsh(z_t a, z_t b, size_t bits) @@ -16,8 +13,7 @@ zlsh(z_t a, z_t b, size_t bits) return; } if (!bits) { - if (a != b) - zset(a, b); + SET(a, b); return; } @@ -26,12 +22,13 @@ zlsh(z_t a, z_t b, size_t bits) cbits = BITS_PER_CHAR - 1 - bits; a->used = b->used + chars; - if (a->alloced < a->used) { - a->alloced = a->used; - a->chars = realloc(a->chars, a->used * sizeof(*(a->chars))); - } - (a == b ? memmove : memcpy)(a->chars + chars, b->chars, a->used * sizeof(*(a->chars))); - memset(a->chars, 0, chars * sizeof(*(a->chars))); + if (a->alloced < a->used) + zahl_realloc(a, a->used); + if (a == b) + zmemmove(a->chars + chars, b->chars, a->used); + else + zmemcpy(a->chars + chars, b->chars, a->used); + zmemset(a->chars, 0, chars); for (i = chars; i < a->used; i++) { carry[~i & 1] = a->chars[i] >> cbits; @@ -39,10 +36,8 @@ zlsh(z_t a, z_t b, size_t bits) a->chars[i] |= carry[i & 1]; } if (carry[i & 1]) { - if (a->alloced == a->used) { - a->alloced <<= 1; - a->chars = realloc(a->chars, a->alloced * sizeof(*(a->chars))); - } + if (a->alloced == a->used) + zahl_realloc(a, a->alloced << 1); a->chars[i] = carry[i & 1]; a->used++; } diff --git a/src/zmul.c b/src/zmul.c @@ -33,7 +33,7 @@ zmul(z_t a, z_t b, z_t c) SET_SIGNUM(b, 1); SET_SIGNUM(c, 1); - m = m > m2 ? m : m2; + m = MAX(m, m2); m2 = m >> 1; zinit(z0); diff --git a/src/zneg.c b/src/zneg.c @@ -5,7 +5,6 @@ void zneg(z_t a, z_t b) { - if (a != b) - zset(a, b); + SET(a, b); SET_SIGNUM(a, -zsignum(a)); } diff --git a/src/znot.c b/src/znot.c @@ -13,8 +13,7 @@ znot(z_t a, z_t b) } bits = zbits(b); - if (a != b) - zset(a, b); + SET(a, b); SET_SIGNUM(a, -zsignum(a)); for (n = a->used; n--;) diff --git a/src/zor.c b/src/zor.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zor(z_t a, z_t b, z_t c) @@ -11,41 +8,36 @@ zor(z_t a, z_t b, z_t c) size_t n, m; if (zzero(b)) { - if (zzero(c)) { + if (zzero(c)) SET_SIGNUM(a, 0); - } else { - if (a != c) - zset(a, c); - } + else + SET(a, c); return; } else if (zzero(c)) { - if (a != b) - zset(a, b); + SET(a, b); return; } - m = b->used > c->used ? b->used : c->used; + m = MAX(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->alloced < m) + zahl_realloc(a, m); if (a == b) { - memcpy(a->chars + n, m == b->used ? b->chars : c->chars, (m - n) * sizeof(*(a->chars))); + zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n); 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))); + zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n); while (n--) a->chars[n] |= b->chars[n]; } else if (m == b->used) { - memcpy(a->chars, b->chars, m * sizeof(*(a->chars))); + zmemcpy(a->chars, b->chars, m); while (n--) a->chars[n] |= c->chars[n]; } else { - memcpy(a->chars, c->chars, m * sizeof(*(a->chars))); + zmemcpy(a->chars, c->chars, m); while (n--) a->chars[n] |= b->chars[n]; } diff --git a/src/zrsh.c b/src/zrsh.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zrsh(z_t a, z_t b, size_t bits) @@ -11,8 +8,7 @@ zrsh(z_t a, z_t b, size_t bits) size_t i, chars, cbits; if (!bits) { - if (a != b) - zset(a, b); + SET(a, b); return; } @@ -28,14 +24,12 @@ zrsh(z_t a, z_t b, size_t bits) if (chars && a == b) { a->used -= chars; - memmove(a->chars, a->chars + chars, a->used * sizeof(*(a->chars))); + zmemmove(a->chars, a->chars + chars, a->used); } else if (a != b) { a->used = b->used - chars; - if (a->alloced < a->used) { - a->alloced = a->used; - a->chars = realloc(a->chars, a->used * sizeof(*(a->chars))); - } - memcpy(a->chars, b->chars + chars, a->used * sizeof(*(a->chars))); + if (a->alloced < a->used) + zahl_realloc(a->chars, a->used); + zmemcpy(a->chars, b->chars + chars, a->used); } a->chars[0] >>= bits; diff --git a/src/zsave.c b/src/zsave.c @@ -1,8 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <string.h> - size_t zsave(z_t a, void *buffer) @@ -12,9 +10,8 @@ zsave(z_t a, void *buffer) *((int *)buf) = a->sign, buf += sizeof(int); *((size_t *)buf) = a->used, buf += sizeof(size_t); *((size_t *)buf) = a->alloced, buf += sizeof(size_t); - if (!zzero(a)) { - memcpy(buf, a->chars, a->used * sizeof(*(a->chars))); - } + if (!zzero(a)) + zmemcpy(buf, a->chars, a->used); } return sizeof(z_t) - sizeof(a->chars) + (zzero(a) ? 0 : a->used * sizeof(*(a->chars))); } diff --git a/src/zset.c b/src/zset.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zset(z_t a, z_t b) @@ -11,12 +8,10 @@ zset(z_t a, z_t b) if (zzero(b)) { SET_SIGNUM(a, 0); } else { - if (a->alloced < b->alloced) { - a->alloced = b->alloced; - a->chars = realloc(a->chars, b->alloced * sizeof(*(a->chars))); - } + if (a->alloced < b->alloced) + zahl_realloc(a, b->alloced); a->sign = b->sign; a->used = b->used; - memcpy(a->chars, b->chars, b->used * sizeof(*(a->chars))); + zmemcpy(a->chars, b->chars, b->used); } } diff --git a/src/zsets.c b/src/zsets.c @@ -27,15 +27,13 @@ zsets(z_t a, const char *str) SET_SIGNUM(a, 0); switch ((str_end - str) % 19) { - case 0: while (*str) { #define X(n)\ + case n:\ temp *= 10, temp += *str++ & 15;\ - case n: - X(18) X(17) X(16) X(15) X(14) X(13) X(12) X(11) X(10) - X(9) X(8) X(7) X(6) X(5) X(4) X(3) X(2) X(1) + X(0) X(18) X(17) X(16) X(15) X(14) X(13) X(12) X(11) + X(10) X(9) X(8) X(7) X(6) X(5) X(4) X(3) X(2) X(1) #undef X - temp *= 10, temp += *str++ & 15; zmul(a, a, libzahl_const_1e19); zsetu(libzahl_tmp_str_num, temp); diff --git a/src/zsetu.c b/src/zsetu.c @@ -1,8 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> - #define SIZE_MULTIPLE(fit, in) ((sizeof(fit) + sizeof(in) - 1) / sizeof(in)) @@ -13,10 +11,8 @@ zsetu(z_t a, unsigned long long int b) SET_SIGNUM(a, 0); return; } - if (a->alloced < SIZE_MULTIPLE(b, *(a->chars))) { - a->alloced = SIZE_MULTIPLE(b, *(a->chars)); - a->chars = realloc(a->chars, SIZE_MULTIPLE(b, *(a->chars)) * sizeof(*(a->chars))) - } + if (a->alloced < SIZE_MULTIPLE(b, *(a->chars))) + zahl_realloc(a, SIZE_MULTIPLE(b, *(a->chars))) SET_SIGNUM(a, 1); a->used = 0; while (b) { diff --git a/src/zstr.c b/src/zstr.c @@ -1,7 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> #include <stdio.h> #define num libzahl_tmp_str_num diff --git a/src/zsub.c b/src/zsub.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <stdlib.h> -#include <string.h> - void zsub_unsigned(z_t a, z_t b, z_t c) @@ -18,16 +15,14 @@ zsub_unsigned(z_t a, z_t b, z_t c) SET_SIGNUM(a, 0); return; } - if (a != c) - zset(a, c); - *subtrahend = *b; + SET(a, c); + *s = *b; } else { - if (a != b) - zset(a, b); - *subtrahend = *c; + SET(a, b); + *s = *c; } - n = a->used < s->used ? a->used : s->used; + 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]); @@ -51,8 +46,7 @@ zsub(z_t a, z_t b, z_t c) } else if (zzero(b)) { zneg(a, c); } else if (zzero(c)) { - if (a != b) - zset(a, b); + SET(a, b); } else if ((zsignum(b) | zsignum(c)) < 0) { if (zsignum(b) < 0) { if (zsignum(c) < 0) { diff --git a/src/ztrunc.c b/src/ztrunc.c @@ -1,33 +1,35 @@ /* 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; + size_t chars, i; + 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->used < chars) - bits = 0; - 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; - } + return; } + + chars = CEILING_BITS_TO_CHARS(bits); + a->sign = b->sign; + a->used = MIN(chars, b->used); + if (a->used < chars) + bits = 0; + if (a->alloced < b->alloced) + zahl_realloc(a, b->alloced); + zmemcpy(a->chars, b->chars, a->used); + bits = BITS_IN_LAST_CHAR(bits); + if (bits) { + mask <<= bits; + mask -= 1; + a->chars[a->used - 1] &= mask; + } + + for (i = a->used; i--;) + if (a->chars[i]) + return; + SET_SIGNUM(a, 0); } diff --git a/src/zxor.c b/src/zxor.c @@ -1,9 +1,6 @@ /* See LICENSE file for copyright and license details. */ #include "internals" -#include <string.h> -#include <stdlib.h> - void zxor(z_t a, z_t b, z_t c) @@ -11,46 +8,41 @@ zxor(z_t a, z_t b, z_t c) size_t n, m; if (zzero(b)) { - if (zzero(c)) { + if (zzero(c)) SET_SIGNUM(a, 0); - } else { - if (a != c) - zset(a, c); - } + else + SET(a, c); return; } else if (zzero(c)) { - if (a != b) - zset(a, b); + SET(a, b); return; } - m = b->used > c->used ? b->used : c->used; + m = MAX(b->used, c->used); n = b->used + c->used - m; - if (n == m && !memcmp(b->chars, c->chars, m * sizeof(*(b->chars)))) { + if (n == m && !zmemcmp(b->chars, c->chars, m)) { SET_SIGNUM(a, 0); return; } - if (a->alloced < m) { - a->alloced = m; - a->chars = realloc(a->chars, m * sizeof(*(a->chars))); - } + if (a->alloced < m) + zahl_realloc(a, m); if (a == b) { - memcpy(a->chars + n, m == b->used ? b->chars : c->chars, (m - n) * sizeof(*(a->chars))); + zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n); 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))); + zmemcpy(a->chars + n, m == b->used ? b->chars : c->chars, m - n); while (n--) a->chars[n] ^= b->chars[n]; } else if (m == b->used) { - memcpy(a->chars, b->chars, m * sizeof(*(a->chars))); + zmemcpy(a->chars, b->chars, m); while (n--) a->chars[n] ^= c->chars[n]; } else { - memcpy(a->chars, c->chars, m * sizeof(*(a->chars))); + zmemcpy(a->chars, c->chars, m); while (n--) a->chars[n] ^= b->chars[n]; }