From 35aad695c4b9b9d3440f68f01d870738aea838c1 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Thu, 5 May 2016 14:46:02 +0200 Subject: Rename zahl-{inlines,internals}.h => zahl/{inlines,internals}.h MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- Makefile | 22 ++--- zahl-inlines.h | 268 ------------------------------------------------------- zahl-internals.h | 170 ----------------------------------- zahl.h | 4 +- zahl/inlines.h | 268 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ zahl/internals.h | 170 +++++++++++++++++++++++++++++++++++ 6 files changed, 452 insertions(+), 450 deletions(-) delete mode 100644 zahl-inlines.h delete mode 100644 zahl-internals.h create mode 100644 zahl/inlines.h create mode 100644 zahl/internals.h diff --git a/Makefile b/Makefile index 19b01b4..7233b87 100644 --- a/Makefile +++ b/Makefile @@ -1,9 +1,8 @@ include config.mk -HDR_PUBLIC =\ - zahl.h\ - zahl-inlines.h\ - zahl-internals.h +HDR_SEMIPUBLIC =\ + zahl/inlines.h\ + zahl/internals.h HDR_PRIVATE =\ src/internals.h @@ -70,10 +69,11 @@ INLINE_FUN =\ DOC =\ refsheet.pdf -HDR = $(HDR_PUBLIC) $(HDR_PRIVATE) -OBJ = $(FUN:=.o) allocator.o -MAN3 = $(FUN:=.3) $(INLINE_FUN:=.3) -MAN7 = libzahl.7 +HDR_PUBLIC = zahl.h $(HDR_SEMIPUBLIC) +HDR = $(HDR_PUBLIC) $(HDR_PRIVATE) +OBJ = $(FUN:=.o) allocator.o +MAN3 = $(FUN:=.3) $(INLINE_FUN:=.3) +MAN7 = libzahl.7 VPATH = src @@ -153,7 +153,7 @@ check: test install: libzahl.a mkdir -p -- "$(DESTDIR)$(EXECPREFIX)/lib" - mkdir -p -- "$(DESTDIR)$(PREFIX)/include" + mkdir -p -- "$(DESTDIR)$(PREFIX)/include/zahl" mkdir -p -- "$(DESTDIR)$(MANPREFIX)/man3" mkdir -p -- "$(DESTDIR)$(MANPREFIX)/man7" mkdir -p -- "$(DESTDIR)$(DOCPREFIX)/libzahl" @@ -162,7 +162,8 @@ install: libzahl.a (printf '\n\n!! DESTDIR must be an absolute path. !!\n\n\n' ; exit 1) \ fi cp -- libzahl.a "$(DESTDIR)$(EXECPREFIX)/lib" - cp -- $(HDR_PUBLIC) "$(DESTDIR)$(PREFIX)/include" + cp -- zahl.h "$(DESTDIR)$(PREFIX)/include" + cp -- $(HDR_SEMIPUBLIC) "$(DESTDIR)$(PREFIX)/include/zahl" cd man && cp -- $(MAN3) "$(DESTDIR)$(MANPREFIX)/man3" cd man && cp -- $(MAN7) "$(DESTDIR)$(MANPREFIX)/man7" cp -- $(DOC) "$(DESTDIR)$(DOCPREFIX)/libzahl" @@ -170,6 +171,7 @@ install: libzahl.a uninstall: -rm -- "$(DESTDIR)$(EXECPREFIX)/lib/libzahl.a" -cd -- "$(DESTDIR)$(PREFIX)/include" && rm $(HDR_PUBLIC) + -rmdir -- "$(DESTDIR)$(PREFIX)/include/zahl" -cd -- "$(DESTDIR)$(MANPREFIX)/man3" && rm $(MAN3) -cd -- "$(DESTDIR)$(MANPREFIX)/man7" && rm $(MAN7) -cd -- "$(DESTDIR)$(DOCPREFIX)/libzahl" && rm $(DOC) diff --git a/zahl-inlines.h b/zahl-inlines.h deleted file mode 100644 index 761309c..0000000 --- a/zahl-inlines.h +++ /dev/null @@ -1,268 +0,0 @@ -/* See LICENSE file for copyright and license details. */ - -ZAHL_INLINE void zinit(z_t a) { a->alloced = 0; a->chars = 0; } -ZAHL_INLINE int zeven(z_t a) { return !a->sign || (~a->chars[0] & 1); } -ZAHL_INLINE int zodd(z_t a) { return a->sign && (a->chars[0] & 1); } -ZAHL_INLINE int zeven_nonzero(z_t a) { return ~a->chars[0] & 1; } -ZAHL_INLINE int zodd_nonzero(z_t a) { return a->chars[0] & 1; } -ZAHL_INLINE int zzero(z_t a) { return !a->sign; } -ZAHL_INLINE int zsignum(z_t a) { return a->sign; } -ZAHL_INLINE void zneg(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = -a->sign; } - -#if 1 && (-1 & 1) /* In the future, tuning will select the fastest implementation. */ -ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign &= 1; } -#elif 1 -ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); if (ZAHL_LIKELY(a->sign < 0)) a->sign = 1; } -#else -ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = !!a->sign; } -#endif - - -#if ULONG_MAX != SIZE_MAX /* This variant should be equivalent to the second one if .sign was long. */ -ZAHL_INLINE void -zswap(z_t a, z_t b) -{ - z_t t; - ZAHL_SWAP(a, b, t, sign); - ZAHL_SWAP(b, a, t, used); - ZAHL_SWAP(a, b, t, alloced); - ZAHL_SWAP(b, a, t, chars); -} -#else -ZAHL_INLINE void -zswap(z_t a_, z_t b_) -{ - register long t; - long *a = (long *)a_; - long *b = (long *)b_; - t = a[0], a[0] = b[0], b[0] = t; - t = b[1], b[1] = a[1], a[1] = t; - t = a[2], a[2] = b[2], b[2] = t; - t = b[3], b[3] = a[3], a[3] = t; -} -#endif - - -ZAHL_INLINE void -zset(z_t a, z_t b) -{ - if (ZAHL_UNLIKELY(b->sign == 0)) { - a->sign = 0; - } else { - a->sign = b->sign; - a->used = b->used; - ZAHL_ENSURE_SIZE(a, b->used); - libzahl_memcpy(a->chars, b->chars, b->used); - } -} - - -ZAHL_INLINE void -zseti(z_t a, int64_t b) -{ - if (ZAHL_UNLIKELY(b >= 0)) { - zsetu(a, (uint64_t)b); - return; - } - ZAHL_ENSURE_SIZE(a, 1); - ZAHL_SET_SIGNUM(a, -1); - a->chars[0] = (zahl_char_t)-b; - a->used = 1; -} - - -ZAHL_INLINE void -zsetu(z_t a, uint64_t b) -{ - if (ZAHL_UNLIKELY(!b)) { - ZAHL_SET_SIGNUM(a, 0); - return; - } - ZAHL_ENSURE_SIZE(a, 1); - ZAHL_SET_SIGNUM(a, 1); - a->chars[0] = (zahl_char_t)b; - a->used = 1; -} - - -ZAHL_INLINE size_t -zlsb(z_t a) -{ - size_t i = 0; - if (ZAHL_UNLIKELY(zzero(a))) - return SIZE_MAX; - for (; !a->chars[i]; i++); - i *= 8 * sizeof(zahl_char_t); - ZAHL_ADD_CTZ(i, a->chars[i]); - return i; -} - - -ZAHL_INLINE size_t -zbits(z_t a) -{ - size_t rc; - if (ZAHL_UNLIKELY(zzero(a))) - return 1; - while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ - rc = a->used * 8 * sizeof(zahl_char_t); - ZAHL_SUB_CLZ(rc, a->chars[a->used - 1]); - return rc; -} - - -ZAHL_INLINE int -zcmpmag(z_t a, z_t b) -{ - size_t i, j; - if (ZAHL_UNLIKELY(zzero(a))) return -!zzero(b); - if (ZAHL_UNLIKELY(zzero(b))) return 1; - i = a->used - 1; - j = b->used - 1; -#if 0 /* TODO this should be sufficient. */ - if (i != j) - return (i > j) * 2 - 1; -#else - for (; i > j; i--) { - if (a->chars[i]) - return +1; - a->used--; - } - for (; j > i; j--) { - if (b->chars[j]) - return -1; - b->used--; - } -#endif - for (; i && a->chars[i] == b->chars[i]; i--); - return a->chars[i] < b->chars[i] ? -1 : a->chars[i] > b->chars[i]; -} - - -ZAHL_INLINE int -zcmp(z_t a, z_t b) -{ - if (zsignum(a) != zsignum(b)) - return zsignum(a) < zsignum(b) ? -1 : zsignum(a) > zsignum(b); - return zsignum(a) * zcmpmag(a, b); -} - - -ZAHL_INLINE int -zcmpu(z_t a, uint64_t b) -{ - if (ZAHL_UNLIKELY(!b)) - return zsignum(a); - if (ZAHL_UNLIKELY(zsignum(a) <= 0)) - return -1; - while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ - if (a->used > 1) - return +1; - return a->chars[0] < b ? -1 : a->chars[0] > b; -} - - -ZAHL_INLINE int -zcmpi(z_t a, int64_t b) -{ - if (ZAHL_UNLIKELY(!b)) - return zsignum(a); - if (ZAHL_UNLIKELY(zzero(a))) - return ZAHL_LIKELY(b < 0) ? 1 : -1; - if (ZAHL_LIKELY(b < 0)) { - if (zsignum(a) > 0) - return +1; - while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ - if (a->used > 1) - return -1; - return a->chars[0] > (zahl_char_t)-b ? -1 : a->chars[0] < (zahl_char_t)-b; - } else { - if (zsignum(a) < 0) - return -1; - while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ - if (a->used > 1) - return +1; - return a->chars[0] < (zahl_char_t)b ? -1 : a->chars[0] > (zahl_char_t)b; - } -} - - -ZAHL_INLINE void -zbset(z_t a, z_t b, size_t bit, int action) -{ - if (ZAHL_UNLIKELY(a != b)) - zset(a, b); - -#ifdef ZAHL_CONST_P - if (ZAHL_CONST_P(action) && ZAHL_CONST_P(bit)) { - zahl_char_t mask = 1; - if (zzero(a) || ZAHL_FLOOR_BITS_TO_CHARS(bit) >= a->used) { - if (!action) - return; - goto fallback; - } - mask <<= ZAHL_BITS_IN_LAST_CHAR(bit); - if (action > 0) { - a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] |= mask; - return; - } else if (action < 0) { - a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] ^= mask; - } else { - a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] &= ~mask; - } - ZAHL_TRIM_AND_ZERO(a); - return; - } -fallback: -#endif - - if (action > 0) - zbset_ll_set(a, bit); - else if (action < 0) - zbset_ll_flip(a, bit); - else - zbset_ll_clear(a, bit); -} - - -ZAHL_O3 ZAHL_INLINE int -zbtest(z_t a, size_t bit) -{ - size_t chars; - if (ZAHL_UNLIKELY(zzero(a))) - return 0; - - chars = ZAHL_FLOOR_BITS_TO_CHARS(bit); - if (ZAHL_UNLIKELY(chars >= a->used)) - return 0; - - bit &= ZAHL_BITS_IN_LAST_CHAR(bit); - return (a->chars[chars] >> bit) & 1; -} - - -ZAHL_O3 ZAHL_INLINE void -zsplit(z_t high, z_t low, z_t a, size_t delim) -{ - if (ZAHL_UNLIKELY(high == a)) { - ztrunc(low, a, delim); - zrsh(high, a, delim); - } else { - zrsh(high, a, delim); - ztrunc(low, a, delim); - } -} - - -ZAHL_O2 ZAHL_INLINE size_t -zsave(z_t a, void *buffer) -{ - if (ZAHL_LIKELY(buffer)) { - char *buf = buffer; - *((int *)buf) = a->sign, buf += sizeof(int); - *((size_t *)buf) = a->used, buf += sizeof(size_t); - if (ZAHL_LIKELY(!zzero(a))) - libzahl_memcpy((zahl_char_t *)buf, a->chars, a->used); - } - return sizeof(int) + sizeof(size_t) + (zzero(a) ? 0 : a->used * sizeof(zahl_char_t)); -} diff --git a/zahl-internals.h b/zahl-internals.h deleted file mode 100644 index 5c9cc5e..0000000 --- a/zahl-internals.h +++ /dev/null @@ -1,170 +0,0 @@ -/* See LICENSE file for copyright and license details. */ - -#ifndef ZAHL_INLINE -# if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L -# define ZAHL_INLINE static inline -# else -# define ZAHL_INLINE static -# endif -#endif - - -#if defined(__GNUC__) || defined(__clang__) -# define ZAHL_LIKELY(expr) __builtin_expect(!!(expr), 1) -# define ZAHL_UNLIKELY(expr) __builtin_expect(!!(expr), 0) -# define ZAHL_CONST_P(value) __builtin_constant_p(value) -#else -# define ZAHL_LIKELY(expr) (expr) -# define ZAHL_UNLIKELY(expr) (expr) -#endif - - -#if defined(__GNUC__) && !defined(__clang__) -# define ZAHL_O0 __attribute__((optimize("O0"))) -# define ZAHL_O1 __attribute__((optimize("O1"))) -# define ZAHL_O2 __attribute__((optimize("O2"))) -# define ZAHL_O3 __attribute__((optimize("O3"))) -# define ZAHL_Ofast __attribute__((optimize("Ofast"))) -# define ZAHL_Os __attribute__((optimize("Os"))) -# define ZAHL_Oz __attribute__((optimize("Os"))) -#elif defined(__clang__) -# define ZAHL_O0 __attribute__((optnone)) -# define ZAHL_O1 /* Don't know how. */ -# define ZAHL_O2 /* Don't know how. */ -# define ZAHL_O3 /* Don't know how. */ -# define ZAHL_Ofast /* Don't know how. */ -# define ZAHL_Os /* Don't know how. */ -# define ZAHL_Oz /* Don't know how. */ -#else -# define ZAHL_O0 /* Don't know how. */ -# define ZAHL_O1 /* Don't know how. */ -# define ZAHL_O2 /* Don't know how. */ -# define ZAHL_O3 /* Don't know how. */ -# define ZAHL_Ofast /* Don't know how. */ -# define ZAHL_Os /* Don't know how. */ -# define ZAHL_Oz /* Don't know how. */ -#endif -/* Mostly ZAHL_O2, but sometimes ZAHL_O3, are useful. - * But note, often it optimal to not use any of them. */ - - -#define ZAHL_BITS_PER_CHAR 64 -#define ZAHL_LB_BITS_PER_CHAR 6 -#define ZAHL_CHAR_MAX UINT64_MAX -/* Note: These cannot be changed willy-nilly, some code depends - * on them, be cause being flexible would just be too painful. */ - - -#define ZAHL_FLOOR_BITS_TO_CHARS(bits) ((bits) >> ZAHL_LB_BITS_PER_CHAR) -#define ZAHL_CEILING_BITS_TO_CHARS(bits) (((bits) + (ZAHL_BITS_PER_CHAR - 1)) >> ZAHL_LB_BITS_PER_CHAR) -#define ZAHL_BITS_IN_LAST_CHAR(bits) ((bits) & (ZAHL_BITS_PER_CHAR - 1)) -#define ZAHL_TRUNCATE_TO_CHAR(bits) ((bits) & ~(size_t)(ZAHL_BITS_PER_CHAR - 1)) - - -#define ZAHL_SET_SIGNUM(a, signum) ((a)->sign = (signum)) -#define ZAHL_SET(a, b) do { if ((a) != (b)) zset(a, b); } while (0) -#define ZAHL_ENSURE_SIZE(a, n) do { if ((a)->alloced < (n)) libzahl_realloc(a, (n)); } while (0) -#define ZAHL_TRIM(a) for (; (a)->used && !(a)->chars[(a)->used - 1]; (a)->used--) -#define ZAHL_TRIM_NONZERO(a) for (; !(a)->chars[(a)->used - 1]; (a)->used--) -#define ZAHL_TRIM_AND_ZERO(a) do { ZAHL_TRIM(a); if (!(a)->used) ZAHL_SET_SIGNUM(a, 0); } while (0) -#define ZAHL_TRIM_AND_SIGN(a, s) do { ZAHL_TRIM(a); ZAHL_SET_SIGNUM(a, (a)->used ? (s) : 0); } while (0) -#define ZAHL_SWAP(a, b, t, m) ((t)->m = (a)->m, (a)->m = (b)->m, (b)->m = (t)->m) - - -#if defined(__GNUC__) || defined(__clang__) -# if ZAHL_CHAR_MAX == LONG_MAX -# define ZAHL_ADD_CTZ(r, x) ((r) += (size_t)__builtin_ctzl(x)) -# define ZAHL_SUB_CLZ(r, x) ((r) -= (size_t)__builtin_clzl(x)) -# else -# define ZAHL_ADD_CTZ(r, x) ((r) += (size_t)__builtin_ctzll(x)) -# define ZAHL_SUB_CLZ(r, x) ((r) -= (size_t)__builtin_clzll(x)) -# endif -#else -# define ZAHL_ADD_CTZ(r, x) \ - do { \ - zahl_char_t zahl_x__ = (x); \ - for (; zahl_x__ & 1; zahl_x__ >>= 1, (r)++); \ - } while (0) -# define ZAHL_SUB_CLZ(r, x) \ - do { \ - zahl_char_t zahl_x__ = (x); \ - (r) -= 8 * sizeof(zahl_char_t); \ - for (; zahl_x__; zahl_x__ >>= 1, (r)++); \ - } while (0) -#endif - - -typedef uint64_t zahl_char_t; - -struct zahl { - int sign; -#if INT_MAX != LONG_MAX - int padding__; -#endif - size_t used; - size_t alloced; - zahl_char_t *chars; -}; - - -void libzahl_realloc(struct zahl *, size_t); - -ZAHL_INLINE void -libzahl_memcpy(register zahl_char_t *d, register const zahl_char_t *s, size_t n) -{ - size_t i; - if (n <= 4) { - if (n >= 1) - d[0] = s[0]; - if (n >= 2) - d[1] = s[1]; - if (n >= 3) - d[2] = s[2]; - if (n >= 4) - d[3] = s[3]; - } else { - for (i = 0; (i += 4) <= n;) { - d[i - 4] = s[i - 4]; - d[i - 3] = s[i - 3]; - d[i - 2] = s[i - 2]; - d[i - 1] = s[i - 1]; - } - if (i > n) { - i -= 4; - if (i < n) - d[i] = s[i], i++; - if (i < n) - d[i] = s[i], i++; - if (i < n) - d[i] = s[i], i++; - if (i < n) - d[i] = s[i]; - } - } -} - -ZAHL_INLINE void -libzahl_memset(register zahl_char_t *a, register zahl_char_t v, size_t n) -{ - size_t i; - if (n <= 4) { - if (n >= 1) - a[0] = v; - if (n >= 2) - a[1] = v; - if (n >= 3) - a[2] = v; - if (n >= 4) - a[3] = v; - } else { - for (i = 0; (i += 4) <= n;) { - a[i - 1] = v; - a[i - 2] = v; - a[i - 3] = v; - a[i - 4] = v; - } - if (i > n) - for (i -= 4; i < n; i++) - a[i] = v; - } -} diff --git a/zahl.h b/zahl.h index 45404af..93f3705 100644 --- a/zahl.h +++ b/zahl.h @@ -12,7 +12,7 @@ #include #include -#include "zahl-internals.h" +#include "zahl/internals.h" @@ -175,6 +175,6 @@ void zbset_ll_flip(z_t, size_t); /* zbset(a, a, b, -1) */ -#include "zahl-inlines.h" +#include "zahl/inlines.h" #endif diff --git a/zahl/inlines.h b/zahl/inlines.h new file mode 100644 index 0000000..761309c --- /dev/null +++ b/zahl/inlines.h @@ -0,0 +1,268 @@ +/* See LICENSE file for copyright and license details. */ + +ZAHL_INLINE void zinit(z_t a) { a->alloced = 0; a->chars = 0; } +ZAHL_INLINE int zeven(z_t a) { return !a->sign || (~a->chars[0] & 1); } +ZAHL_INLINE int zodd(z_t a) { return a->sign && (a->chars[0] & 1); } +ZAHL_INLINE int zeven_nonzero(z_t a) { return ~a->chars[0] & 1; } +ZAHL_INLINE int zodd_nonzero(z_t a) { return a->chars[0] & 1; } +ZAHL_INLINE int zzero(z_t a) { return !a->sign; } +ZAHL_INLINE int zsignum(z_t a) { return a->sign; } +ZAHL_INLINE void zneg(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = -a->sign; } + +#if 1 && (-1 & 1) /* In the future, tuning will select the fastest implementation. */ +ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign &= 1; } +#elif 1 +ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); if (ZAHL_LIKELY(a->sign < 0)) a->sign = 1; } +#else +ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = !!a->sign; } +#endif + + +#if ULONG_MAX != SIZE_MAX /* This variant should be equivalent to the second one if .sign was long. */ +ZAHL_INLINE void +zswap(z_t a, z_t b) +{ + z_t t; + ZAHL_SWAP(a, b, t, sign); + ZAHL_SWAP(b, a, t, used); + ZAHL_SWAP(a, b, t, alloced); + ZAHL_SWAP(b, a, t, chars); +} +#else +ZAHL_INLINE void +zswap(z_t a_, z_t b_) +{ + register long t; + long *a = (long *)a_; + long *b = (long *)b_; + t = a[0], a[0] = b[0], b[0] = t; + t = b[1], b[1] = a[1], a[1] = t; + t = a[2], a[2] = b[2], b[2] = t; + t = b[3], b[3] = a[3], a[3] = t; +} +#endif + + +ZAHL_INLINE void +zset(z_t a, z_t b) +{ + if (ZAHL_UNLIKELY(b->sign == 0)) { + a->sign = 0; + } else { + a->sign = b->sign; + a->used = b->used; + ZAHL_ENSURE_SIZE(a, b->used); + libzahl_memcpy(a->chars, b->chars, b->used); + } +} + + +ZAHL_INLINE void +zseti(z_t a, int64_t b) +{ + if (ZAHL_UNLIKELY(b >= 0)) { + zsetu(a, (uint64_t)b); + return; + } + ZAHL_ENSURE_SIZE(a, 1); + ZAHL_SET_SIGNUM(a, -1); + a->chars[0] = (zahl_char_t)-b; + a->used = 1; +} + + +ZAHL_INLINE void +zsetu(z_t a, uint64_t b) +{ + if (ZAHL_UNLIKELY(!b)) { + ZAHL_SET_SIGNUM(a, 0); + return; + } + ZAHL_ENSURE_SIZE(a, 1); + ZAHL_SET_SIGNUM(a, 1); + a->chars[0] = (zahl_char_t)b; + a->used = 1; +} + + +ZAHL_INLINE size_t +zlsb(z_t a) +{ + size_t i = 0; + if (ZAHL_UNLIKELY(zzero(a))) + return SIZE_MAX; + for (; !a->chars[i]; i++); + i *= 8 * sizeof(zahl_char_t); + ZAHL_ADD_CTZ(i, a->chars[i]); + return i; +} + + +ZAHL_INLINE size_t +zbits(z_t a) +{ + size_t rc; + if (ZAHL_UNLIKELY(zzero(a))) + return 1; + while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ + rc = a->used * 8 * sizeof(zahl_char_t); + ZAHL_SUB_CLZ(rc, a->chars[a->used - 1]); + return rc; +} + + +ZAHL_INLINE int +zcmpmag(z_t a, z_t b) +{ + size_t i, j; + if (ZAHL_UNLIKELY(zzero(a))) return -!zzero(b); + if (ZAHL_UNLIKELY(zzero(b))) return 1; + i = a->used - 1; + j = b->used - 1; +#if 0 /* TODO this should be sufficient. */ + if (i != j) + return (i > j) * 2 - 1; +#else + for (; i > j; i--) { + if (a->chars[i]) + return +1; + a->used--; + } + for (; j > i; j--) { + if (b->chars[j]) + return -1; + b->used--; + } +#endif + for (; i && a->chars[i] == b->chars[i]; i--); + return a->chars[i] < b->chars[i] ? -1 : a->chars[i] > b->chars[i]; +} + + +ZAHL_INLINE int +zcmp(z_t a, z_t b) +{ + if (zsignum(a) != zsignum(b)) + return zsignum(a) < zsignum(b) ? -1 : zsignum(a) > zsignum(b); + return zsignum(a) * zcmpmag(a, b); +} + + +ZAHL_INLINE int +zcmpu(z_t a, uint64_t b) +{ + if (ZAHL_UNLIKELY(!b)) + return zsignum(a); + if (ZAHL_UNLIKELY(zsignum(a) <= 0)) + return -1; + while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ + if (a->used > 1) + return +1; + return a->chars[0] < b ? -1 : a->chars[0] > b; +} + + +ZAHL_INLINE int +zcmpi(z_t a, int64_t b) +{ + if (ZAHL_UNLIKELY(!b)) + return zsignum(a); + if (ZAHL_UNLIKELY(zzero(a))) + return ZAHL_LIKELY(b < 0) ? 1 : -1; + if (ZAHL_LIKELY(b < 0)) { + if (zsignum(a) > 0) + return +1; + while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ + if (a->used > 1) + return -1; + return a->chars[0] > (zahl_char_t)-b ? -1 : a->chars[0] < (zahl_char_t)-b; + } else { + if (zsignum(a) < 0) + return -1; + while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ + if (a->used > 1) + return +1; + return a->chars[0] < (zahl_char_t)b ? -1 : a->chars[0] > (zahl_char_t)b; + } +} + + +ZAHL_INLINE void +zbset(z_t a, z_t b, size_t bit, int action) +{ + if (ZAHL_UNLIKELY(a != b)) + zset(a, b); + +#ifdef ZAHL_CONST_P + if (ZAHL_CONST_P(action) && ZAHL_CONST_P(bit)) { + zahl_char_t mask = 1; + if (zzero(a) || ZAHL_FLOOR_BITS_TO_CHARS(bit) >= a->used) { + if (!action) + return; + goto fallback; + } + mask <<= ZAHL_BITS_IN_LAST_CHAR(bit); + if (action > 0) { + a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] |= mask; + return; + } else if (action < 0) { + a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] ^= mask; + } else { + a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] &= ~mask; + } + ZAHL_TRIM_AND_ZERO(a); + return; + } +fallback: +#endif + + if (action > 0) + zbset_ll_set(a, bit); + else if (action < 0) + zbset_ll_flip(a, bit); + else + zbset_ll_clear(a, bit); +} + + +ZAHL_O3 ZAHL_INLINE int +zbtest(z_t a, size_t bit) +{ + size_t chars; + if (ZAHL_UNLIKELY(zzero(a))) + return 0; + + chars = ZAHL_FLOOR_BITS_TO_CHARS(bit); + if (ZAHL_UNLIKELY(chars >= a->used)) + return 0; + + bit &= ZAHL_BITS_IN_LAST_CHAR(bit); + return (a->chars[chars] >> bit) & 1; +} + + +ZAHL_O3 ZAHL_INLINE void +zsplit(z_t high, z_t low, z_t a, size_t delim) +{ + if (ZAHL_UNLIKELY(high == a)) { + ztrunc(low, a, delim); + zrsh(high, a, delim); + } else { + zrsh(high, a, delim); + ztrunc(low, a, delim); + } +} + + +ZAHL_O2 ZAHL_INLINE size_t +zsave(z_t a, void *buffer) +{ + if (ZAHL_LIKELY(buffer)) { + char *buf = buffer; + *((int *)buf) = a->sign, buf += sizeof(int); + *((size_t *)buf) = a->used, buf += sizeof(size_t); + if (ZAHL_LIKELY(!zzero(a))) + libzahl_memcpy((zahl_char_t *)buf, a->chars, a->used); + } + return sizeof(int) + sizeof(size_t) + (zzero(a) ? 0 : a->used * sizeof(zahl_char_t)); +} diff --git a/zahl/internals.h b/zahl/internals.h new file mode 100644 index 0000000..5c9cc5e --- /dev/null +++ b/zahl/internals.h @@ -0,0 +1,170 @@ +/* See LICENSE file for copyright and license details. */ + +#ifndef ZAHL_INLINE +# if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L +# define ZAHL_INLINE static inline +# else +# define ZAHL_INLINE static +# endif +#endif + + +#if defined(__GNUC__) || defined(__clang__) +# define ZAHL_LIKELY(expr) __builtin_expect(!!(expr), 1) +# define ZAHL_UNLIKELY(expr) __builtin_expect(!!(expr), 0) +# define ZAHL_CONST_P(value) __builtin_constant_p(value) +#else +# define ZAHL_LIKELY(expr) (expr) +# define ZAHL_UNLIKELY(expr) (expr) +#endif + + +#if defined(__GNUC__) && !defined(__clang__) +# define ZAHL_O0 __attribute__((optimize("O0"))) +# define ZAHL_O1 __attribute__((optimize("O1"))) +# define ZAHL_O2 __attribute__((optimize("O2"))) +# define ZAHL_O3 __attribute__((optimize("O3"))) +# define ZAHL_Ofast __attribute__((optimize("Ofast"))) +# define ZAHL_Os __attribute__((optimize("Os"))) +# define ZAHL_Oz __attribute__((optimize("Os"))) +#elif defined(__clang__) +# define ZAHL_O0 __attribute__((optnone)) +# define ZAHL_O1 /* Don't know how. */ +# define ZAHL_O2 /* Don't know how. */ +# define ZAHL_O3 /* Don't know how. */ +# define ZAHL_Ofast /* Don't know how. */ +# define ZAHL_Os /* Don't know how. */ +# define ZAHL_Oz /* Don't know how. */ +#else +# define ZAHL_O0 /* Don't know how. */ +# define ZAHL_O1 /* Don't know how. */ +# define ZAHL_O2 /* Don't know how. */ +# define ZAHL_O3 /* Don't know how. */ +# define ZAHL_Ofast /* Don't know how. */ +# define ZAHL_Os /* Don't know how. */ +# define ZAHL_Oz /* Don't know how. */ +#endif +/* Mostly ZAHL_O2, but sometimes ZAHL_O3, are useful. + * But note, often it optimal to not use any of them. */ + + +#define ZAHL_BITS_PER_CHAR 64 +#define ZAHL_LB_BITS_PER_CHAR 6 +#define ZAHL_CHAR_MAX UINT64_MAX +/* Note: These cannot be changed willy-nilly, some code depends + * on them, be cause being flexible would just be too painful. */ + + +#define ZAHL_FLOOR_BITS_TO_CHARS(bits) ((bits) >> ZAHL_LB_BITS_PER_CHAR) +#define ZAHL_CEILING_BITS_TO_CHARS(bits) (((bits) + (ZAHL_BITS_PER_CHAR - 1)) >> ZAHL_LB_BITS_PER_CHAR) +#define ZAHL_BITS_IN_LAST_CHAR(bits) ((bits) & (ZAHL_BITS_PER_CHAR - 1)) +#define ZAHL_TRUNCATE_TO_CHAR(bits) ((bits) & ~(size_t)(ZAHL_BITS_PER_CHAR - 1)) + + +#define ZAHL_SET_SIGNUM(a, signum) ((a)->sign = (signum)) +#define ZAHL_SET(a, b) do { if ((a) != (b)) zset(a, b); } while (0) +#define ZAHL_ENSURE_SIZE(a, n) do { if ((a)->alloced < (n)) libzahl_realloc(a, (n)); } while (0) +#define ZAHL_TRIM(a) for (; (a)->used && !(a)->chars[(a)->used - 1]; (a)->used--) +#define ZAHL_TRIM_NONZERO(a) for (; !(a)->chars[(a)->used - 1]; (a)->used--) +#define ZAHL_TRIM_AND_ZERO(a) do { ZAHL_TRIM(a); if (!(a)->used) ZAHL_SET_SIGNUM(a, 0); } while (0) +#define ZAHL_TRIM_AND_SIGN(a, s) do { ZAHL_TRIM(a); ZAHL_SET_SIGNUM(a, (a)->used ? (s) : 0); } while (0) +#define ZAHL_SWAP(a, b, t, m) ((t)->m = (a)->m, (a)->m = (b)->m, (b)->m = (t)->m) + + +#if defined(__GNUC__) || defined(__clang__) +# if ZAHL_CHAR_MAX == LONG_MAX +# define ZAHL_ADD_CTZ(r, x) ((r) += (size_t)__builtin_ctzl(x)) +# define ZAHL_SUB_CLZ(r, x) ((r) -= (size_t)__builtin_clzl(x)) +# else +# define ZAHL_ADD_CTZ(r, x) ((r) += (size_t)__builtin_ctzll(x)) +# define ZAHL_SUB_CLZ(r, x) ((r) -= (size_t)__builtin_clzll(x)) +# endif +#else +# define ZAHL_ADD_CTZ(r, x) \ + do { \ + zahl_char_t zahl_x__ = (x); \ + for (; zahl_x__ & 1; zahl_x__ >>= 1, (r)++); \ + } while (0) +# define ZAHL_SUB_CLZ(r, x) \ + do { \ + zahl_char_t zahl_x__ = (x); \ + (r) -= 8 * sizeof(zahl_char_t); \ + for (; zahl_x__; zahl_x__ >>= 1, (r)++); \ + } while (0) +#endif + + +typedef uint64_t zahl_char_t; + +struct zahl { + int sign; +#if INT_MAX != LONG_MAX + int padding__; +#endif + size_t used; + size_t alloced; + zahl_char_t *chars; +}; + + +void libzahl_realloc(struct zahl *, size_t); + +ZAHL_INLINE void +libzahl_memcpy(register zahl_char_t *d, register const zahl_char_t *s, size_t n) +{ + size_t i; + if (n <= 4) { + if (n >= 1) + d[0] = s[0]; + if (n >= 2) + d[1] = s[1]; + if (n >= 3) + d[2] = s[2]; + if (n >= 4) + d[3] = s[3]; + } else { + for (i = 0; (i += 4) <= n;) { + d[i - 4] = s[i - 4]; + d[i - 3] = s[i - 3]; + d[i - 2] = s[i - 2]; + d[i - 1] = s[i - 1]; + } + if (i > n) { + i -= 4; + if (i < n) + d[i] = s[i], i++; + if (i < n) + d[i] = s[i], i++; + if (i < n) + d[i] = s[i], i++; + if (i < n) + d[i] = s[i]; + } + } +} + +ZAHL_INLINE void +libzahl_memset(register zahl_char_t *a, register zahl_char_t v, size_t n) +{ + size_t i; + if (n <= 4) { + if (n >= 1) + a[0] = v; + if (n >= 2) + a[1] = v; + if (n >= 3) + a[2] = v; + if (n >= 4) + a[3] = v; + } else { + for (i = 0; (i += 4) <= n;) { + a[i - 1] = v; + a[i - 2] = v; + a[i - 3] = v; + a[i - 4] = v; + } + if (i > n) + for (i -= 4; i < n; i++) + a[i] = v; + } +} -- cgit v1.2.3-70-g09d2