commit 35aad695c4b9b9d3440f68f01d870738aea838c1
Author: Mattias Andrée <[email protected]>
AuthorDate: Thu May 5 14:46:02 2016 +0200
Commit: Mattias Andrée <[email protected]>
CommitDate: Thu May 5 14:46:02 2016 +0200
Rename zahl-{inlines,internals}.h => zahl/{inlines,internals}.h
Signed-off-by: Mattias Andrée <[email protected]>
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 <stddef.h>
#include <stdint.h>
-#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;
+ }
+}
