commit 92be5631d8e319babf5cca49f53ea5e692c54793
parent 1ec80039288073294e3e61b0c680e9c95688e786
Author: Mattias Andrée <maandree@kth.se>
Date: Tue, 15 Mar 2016 00:20:00 +0100
Optimisations
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
13 files changed, 214 insertions(+), 149 deletions(-)
diff --git a/Makefile b/Makefile
@@ -8,11 +8,6 @@ FUN =\
zadd\
zand\
zbset\
- zbtest\
- zcmp\
- zcmpi\
- zcmpmag\
- zcmpu\
zdiv\
zdivmod\
zerror\
@@ -61,7 +56,12 @@ INLINE_FUN =\
zneg\
zlsb\
zbits\
- zseti
+ zseti\
+ zcmp\
+ zcmpi\
+ zcmpmag\
+ zcmpu\
+ zbtest
OBJ = $(FUN:=.o) allocator.o
MAN3 = $(FUN:=.3) $(INLINE_FUN:=.3)
diff --git a/TODO b/TODO
@@ -3,3 +3,8 @@ It uses optimised division algorithm that requires that d|n.
Add zsets_radix
Add zstr_radix
+Add zranddist value based on % for fitness to bound
+
+Test big endian
+Test always having used > 0 for zero
+ Test negative/non-negative instead of sign
diff --git a/src/zadd.c b/src/zadd.c
@@ -21,8 +21,8 @@ zadd_impl(z_t a, z_t b, size_t n)
a->used = i;
}
-inline void
-zadd_unsigned(z_t a, z_t b, z_t c)
+static inline void
+libzahl_zadd_unsigned(z_t a, z_t b, z_t c)
{
size_t size, n;
@@ -66,6 +66,12 @@ zadd_unsigned(z_t a, z_t b, z_t c)
}
void
+zadd_unsigned(z_t a, z_t b, z_t c)
+{
+ libzahl_zadd_unsigned(a, b, c);
+}
+
+void
zadd(z_t a, z_t b, z_t c)
{
if (unlikely(zzero(b))) {
@@ -74,7 +80,7 @@ zadd(z_t a, z_t b, z_t c)
SET(a, b);
} else if (unlikely(znegative(b))) {
if (znegative(c)) {
- zadd_unsigned(a, b, c);
+ libzahl_zadd_unsigned(a, b, c);
SET_SIGNUM(a, -zsignum(a));
} else {
zsub_unsigned(a, c, b);
@@ -82,6 +88,6 @@ zadd(z_t a, z_t b, z_t c)
} else if (unlikely(znegative(c))) {
zsub_unsigned(a, b, c);
} else {
- zadd_unsigned(a, b, c);
+ libzahl_zadd_unsigned(a, b, c);
}
}
diff --git a/src/zbset.c b/src/zbset.c
@@ -2,38 +2,45 @@
#include "internals.h"
-void
-zbset(z_t a, z_t b, size_t bit, int action)
-{
- zahl_char_t mask = 1;
- size_t chars;
-
- chars = FLOOR_BITS_TO_CHARS(bit);
- bit = BITS_IN_LAST_CHAR(bit);
- mask <<= bit;
+#define PROLOGUE(MAY_INCREASE)\
+ zahl_char_t mask = 1;\
+ size_t chars = FLOOR_BITS_TO_CHARS(bit);\
+ if (MAY_INCREASE) {\
+ if (zzero(a)) {\
+ a->used = 0;\
+ SET_SIGNUM(a, 1);\
+ }\
+ if (unlikely(chars >= a->used)) {\
+ ENSURE_SIZE(a, chars + 1);\
+ zmemset(a->chars + a->used, 0, chars + 1 - a->used);\
+ a->used = chars + 1;\
+ }\
+ } else if (unlikely(chars >= a->used)) {\
+ return;\
+ }\
+ bit = BITS_IN_LAST_CHAR(bit);\
+ mask <<= bit
- SET(a, b);
- if (action) {
- if (zzero(a)) {
- a->used = 0;
- SET_SIGNUM(a, 1);
- }
- if (a->used <= chars) {
- ENSURE_SIZE(a, chars + 1);
- zmemset(a->chars + a->used, 0, chars + 1 - a->used);
- a->used = chars + 1;
- }
- }
+void
+zbset_impl_set(z_t a, z_t b, size_t bit)
+{
+ PROLOGUE(1);
+ a->chars[chars] |= mask;
+}
- if (action > 0) {
- a->chars[chars] |= mask;
- return;
- } else if (action < 0) {
- a->chars[chars] ^= mask;
- } else if (chars < a->used) {
- a->chars[chars] &= ~mask;
- }
+void
+zbset_impl_clear(z_t a, z_t b, size_t bit)
+{
+ PROLOGUE(0);
+ a->chars[chars] &= ~mask;
+ TRIM_AND_ZERO(a);
+}
+void
+zbset_impl_flip(z_t a, z_t b, size_t bit)
+{
+ PROLOGUE(1);
+ a->chars[chars] ^= mask;
TRIM_AND_ZERO(a);
}
diff --git a/src/zbtest.c b/src/zbtest.c
@@ -1,18 +0,0 @@
-/* See LICENSE file for copyright and license details. */
-#include "internals.h"
-
-
-int
-zbtest(z_t a, size_t bit)
-{
- size_t chars;
- if (zzero(a))
- return 0;
-
- chars = FLOOR_BITS_TO_CHARS(bit);
- if (chars >= a->used)
- return 0;
-
- bit = BITS_IN_LAST_CHAR(bit);
- return (a->chars[chars] >> bit) & 1;
-}
diff --git a/src/zcmp.c b/src/zcmp.c
@@ -1,11 +0,0 @@
-/* See LICENSE file for copyright and license details. */
-#include "internals.h"
-
-
-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);
-}
diff --git a/src/zcmpi.c b/src/zcmpi.c
@@ -1,14 +0,0 @@
-/* See LICENSE file for copyright and license details. */
-#include "internals.h"
-
-
-int
-zcmpi(z_t a, int64_t b)
-{
- if (unlikely(!b))
- return zsignum(a);
- if (unlikely(zzero(a)))
- return b > 0 ? -1 : b < 0;
- zseti(libzahl_tmp_cmp, b);
- return zcmp(a, libzahl_tmp_cmp);
-}
diff --git a/src/zcmpmag.c b/src/zcmpmag.c
@@ -1,29 +0,0 @@
-/* See LICENSE file for copyright and license details. */
-#include "internals.h"
-
-
-int
-zcmpmag(z_t a, z_t b)
-{
- size_t i, j;
- if (unlikely(zzero(a)))
- return -!zzero(b);
- if (unlikely(zzero(b)))
- return 1;
- i = a->used - 1;
- j = b->used - 1;
- for (; i > j; i--) {
- if (a->chars[i])
- return +1;
- a->used--;
- }
- for (; j > i; j--) {
- if (b->chars[j])
- return -1;
- b->used--;
- }
- for (; i; i--)
- if (a->chars[i] != b->chars[i])
- return (a->chars[i] > b->chars[i]) * 2 - 1;
- return a->chars[0] < b->chars[0] ? -1 : a->chars[0] > b->chars[0];
-}
diff --git a/src/zcmpu.c b/src/zcmpu.c
@@ -1,14 +0,0 @@
-/* See LICENSE file for copyright and license details. */
-#include "internals.h"
-
-
-int
-zcmpu(z_t a, uint64_t b)
-{
- if (unlikely(!b))
- return zsignum(a);
- if (unlikely(zsignum(a) <= 0))
- return -1;
- zsetu(libzahl_tmp_cmp, b);
- return zcmp(a, libzahl_tmp_cmp);
-}
diff --git a/src/zlsh.c b/src/zlsh.c
@@ -6,22 +6,18 @@ void
zlsh(z_t a, z_t b, size_t bits)
{
size_t i, chars, cbits;
- zahl_char_t carry[] = {0, 0};
+ zahl_char_t carry = 0, tcarry;
if (unlikely(zzero(b))) {
SET_SIGNUM(a, 0);
return;
}
- if (unlikely(!bits)) {
- SET(a, b);
- return;
- }
chars = FLOOR_BITS_TO_CHARS(bits);
bits = BITS_IN_LAST_CHAR(bits);
cbits = BITS_PER_CHAR - bits;
- ENSURE_SIZE(a, b->used + chars);
+ ENSURE_SIZE(a, b->used + chars + 1);
if (likely(a == b))
zmemmove(a->chars + chars, b->chars, b->used);
else
@@ -31,15 +27,13 @@ zlsh(z_t a, z_t b, size_t bits)
if (likely(bits)) { /* This if statement is very important in C. */
for (i = chars; i < a->used; i++) {
- carry[~i & 1] = a->chars[i] >> cbits;
+ tcarry = a->chars[i] >> cbits;
a->chars[i] <<= bits;
- a->chars[i] |= carry[i & 1];
- }
- if (carry[i & 1]) {
- ENSURE_SIZE(a, a->used + 1);
- a->chars[i] = carry[i & 1];
- a->used++;
+ a->chars[i] |= carry;
+ carry = tcarry;
}
+ if (carry)
+ a->chars[a->used++] = carry;
}
SET_SIGNUM(a, zsignum(b));
diff --git a/src/zsetup.c b/src/zsetup.c
@@ -31,7 +31,7 @@ zsetup(jmp_buf env)
memset(libzahl_pool_alloc, 0, sizeof(libzahl_pool_alloc));
#define X(x)\
- zinit(x);
+ zinit(x), zsetu(x, 1);
LIST_TEMPS;
#undef X
#define X(x, f, v)\
diff --git a/src/zsub.c b/src/zsub.c
@@ -25,8 +25,8 @@ zsub_impl(z_t a, z_t b, size_t n)
}
}
-inline void
-zsub_unsigned(z_t a, z_t b, z_t c)
+static inline void
+libzahl_zsub_unsigned(z_t a, z_t b, z_t c)
{
int magcmp;
size_t n;
@@ -71,6 +71,12 @@ zsub_unsigned(z_t a, z_t b, z_t c)
}
void
+zsub_unsigned(z_t a, z_t b, z_t c)
+{
+ libzahl_zsub_unsigned(a, b, c);
+}
+
+void
zsub(z_t a, z_t b, z_t c)
{
if (unlikely(zzero(b))) {
@@ -79,7 +85,7 @@ zsub(z_t a, z_t b, z_t c)
SET(a, b);
} else if (unlikely(znegative(b))) {
if (znegative(c)) {
- zsub_unsigned(a, c, b);
+ libzahl_zsub_unsigned(a, c, b);
} else {
zadd_unsigned(a, b, c);
SET_SIGNUM(a, -zsignum(a));
@@ -87,6 +93,6 @@ zsub(z_t a, z_t b, z_t c)
} else if (znegative(c)) {
zadd_unsigned(a, b, c);
} else {
- zsub_unsigned(a, b, c);
+ libzahl_zsub_unsigned(a, b, c);
}
}
diff --git a/zahl.h b/zahl.h
@@ -92,10 +92,10 @@ ZAHL_INLINE void zseti(z_t, int64_t); /* a := b */
/* Comparison functions. */
-int zcmp(z_t, z_t); /* signum (a - b) */
-int zcmpu(z_t, uint64_t); /* signum (a - b) */
-int zcmpi(z_t, int64_t); /* signum (a - b) */
-int zcmpmag(z_t, z_t); /* signum (|a| - |b|) */
+ZAHL_INLINE int zcmp(z_t, z_t); /* signum (a - b) */
+ZAHL_INLINE int zcmpu(z_t, uint64_t); /* signum (a - b) */
+ZAHL_INLINE int zcmpi(z_t, int64_t); /* signum (a - b) */
+ZAHL_INLINE int zcmpmag(z_t, z_t); /* signum (|a| - |b|) */
/* Arithmetic functions. */
@@ -130,13 +130,13 @@ void znot(z_t, z_t); /* a := ~b */
void zlsh(z_t, z_t, size_t); /* a := b << c */
void zrsh(z_t, z_t, size_t); /* a := b >> c */
void ztrunc(z_t, z_t, size_t); /* a := b & ((1 << c) - 1) */
-int zbtest(z_t, size_t); /* (a >> b) & 1 */
void zsplit(z_t, z_t, z_t, size_t); /* a := c >> d, b := c - (a << d) */
+ZAHL_INLINE int zbtest(z_t, size_t); /* (a >> b) & 1 */
ZAHL_INLINE size_t zlsb(z_t); /* Index of first set bit, SIZE_MAX if none are set. */
ZAHL_INLINE size_t zbits(z_t); /* ⌊log₂ |a|⌋ + 1, 1 if a = 0 */
/* If d > 0: a := b | (1 << c), if d = 0: a := b & ~(1 << c), if d < 0: a := b ^ (1 << c) */
-void zbset(z_t, z_t, size_t, int);
+ZAHL_INLINE void zbset(z_t, z_t, size_t, int);
/* Number theory. */
@@ -280,5 +280,138 @@ zbits(z_t a)
}
+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)
+{
+ extern z_t libzahl_tmp_cmp;
+ if (ZAHL_UNLIKELY(!b))
+ return zsignum(a);
+ if (ZAHL_UNLIKELY(zsignum(a) <= 0))
+ return -1;
+ libzahl_tmp_cmp->chars[0] = b;
+ return zcmpmag(a, libzahl_tmp_cmp);
+}
+
+
+ZAHL_INLINE int
+zcmpi(z_t a, int64_t b)
+{
+ extern z_t libzahl_tmp_cmp;
+ 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;
+ libzahl_tmp_cmp->chars[0] = (uint64_t)-b;
+ return -zcmpmag(a, libzahl_tmp_cmp);
+ } else {
+ if (zsignum(a) < 0)
+ return -1;
+ libzahl_tmp_cmp->chars[0] = b;
+ return +zcmpmag(a, libzahl_tmp_cmp);
+ }
+}
+
+
+void zbset_impl_set(z_t a, z_t b, size_t bit);
+void zbset_impl_clear(z_t a, z_t b, size_t bit);
+void zbset_impl_flip(z_t a, z_t b, size_t bit);
+ZAHL_INLINE void
+zbset(z_t a, z_t b, size_t bit, int action)
+{
+ if (ZAHL_UNLIKELY(a != b))
+ zset(a, b);
+
+#if defined(__GNUC__) || defined(__clang__)
+ if (__builtin_constant_p(action) && __builtin_constant_p(bit)) {
+ zahl_char_t mask = 1;
+ if (zzero(a) || bit >> 6 >= a->used) {
+ if (!action)
+ return;
+ goto fallback;
+ }
+ mask <<= bit & 63;
+ if (action > 0) {
+ a->chars[bit >> 6] |= mask;
+ return;
+ } else if (action < 0) {
+ a->chars[bit >> 6] ^= mask;
+ } else {
+ a->chars[bit >> 6] &= ~mask;
+ }
+ for (; a->used && !a->chars[a->used - 1]; a->used--);
+ if (!a->used)
+ a->sign = 0;
+ return;
+ }
+fallback:
+#endif
+
+ if (action > 0) {
+ zbset_impl_set(a, b, bit);
+ } else if (action < 0) {
+ zbset_impl_flip(a, b, bit);
+ } else {
+ zbset_impl_clear(a, b, bit);
+ }
+}
+
+
+ZAHL_INLINE int
+zbtest(z_t a, size_t bit)
+{
+ size_t chars;
+ if (ZAHL_UNLIKELY(zzero(a)))
+ return 0;
+
+ chars = bit >> 6;
+ if (ZAHL_UNLIKELY(chars >= a->used))
+ return 0;
+
+ bit &= 63;
+ return (a->chars[chars] >> bit) & 1;
+}
+
#endif
