diff options
Diffstat (limited to 'zahl.h')
| -rw-r--r-- | zahl.h | 216 |
1 files changed, 131 insertions, 85 deletions
@@ -4,12 +4,23 @@ /* Caution: Do not use libzahl for cryptographic applications, use a specialised library. */ #ifndef ZAHL_H -#define ZAHL_H +#define ZAHL_H 1 #include <stddef.h> #include <setjmp.h> #include <stdint.h> +#include <limits.h> + + + +#ifndef ZAHL_INLINE +# if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L +# define ZAHL_INLINE static inline +# else +# define ZAHL_INLINE static +# endif +#endif @@ -19,22 +30,38 @@ typedef uint64_t zahl_char_t; /* This structure should be considered opaque. */ typedef struct { int sign; +#if INT_MAX != LONG_MAX + int padding__; +#endif size_t used; size_t alloced; zahl_char_t *chars; } z_t[1]; -enum zprimality { NONPRIME = 0, PROBABLY_PRIME, PRIME }; -enum zranddev { FAST_RANDOM = 0, SECURE_RANDOM }; -enum zranddist { QUASIUNIFORM = 0, UNIFORM }; + +enum zprimality { + NONPRIME = 0, /* The number is definitely composite. */ + PROBABLY_PRIME, /* The number is probably prime. */ + PRIME /* The number is definitely prime. */ +}; + +enum zranddev { + FAST_RANDOM = 0, /* Random numbers are generated directly from /dev/urandom. */ + SECURE_RANDOM /* Random numbers are generated directly from /dev/random. */ +}; + +enum zranddist { + QUASIUNIFORM = 0, /* Almost uniformly random, per the usual recommendation. */ + UNIFORM /* Actually uniformly random. */ +}; enum zerror { - ZERROR_ERRNO_SET = 0, /* Please refer to errno. */ - ZERROR_0_POW_0, /* Indeterminate form: 0:th power of 0. (Translatable to EDOM.) */ - ZERROR_0_DIV_0, /* Indeterminate form: 0 divided by 0. (Translatable to EDOM.) */ - ZERROR_DIV_0, /* Undefined result: Division by 0. (Translatable to EDOM.) */ - ZERROR_NEGATIVE /* Argument must be non-negative. (Translatable to EDOM or EINVAL.) */ + ZERROR_ERRNO_SET = 0, /* Please refer to errno. */ + ZERROR_0_POW_0, /* Indeterminate form: 0:th power of 0. (Translatable to EDOM.) */ + ZERROR_0_DIV_0, /* Indeterminate form: 0 divided by 0. (Translatable to EDOM.) */ + ZERROR_DIV_0, /* Undefined result: Division by 0. (Translatable to EDOM.) */ + ZERROR_NEGATIVE /* Argument must be non-negative. (Translatable to EDOM or EINVAL.) */ }; @@ -44,75 +71,83 @@ enum zerror { /* Library initialisation and destruction. */ -void zsetup(jmp_buf); /* Prepare libzahl for use. */ -void zunsetup(void); /* Free resources used by libzahl */ +void zsetup(jmp_buf); /* Prepare libzahl for use. */ +void zunsetup(void); /* Free resources used by libzahl */ /* Memory functions. */ -void zfree(z_t); /* Free resources in a. */ -size_t zsave(z_t, void *); /* Store a into b (if !!b), and return number of written bytes. */ -size_t zload(z_t, const void *); /* Restore a from b, and return number of read bytes. */ +ZAHL_INLINE void zinit(z_t); /* Prepare a for use. */ +ZAHL_INLINE void zswap(z_t, z_t); /* (a, b) := (b, a) */ +void zfree(z_t); /* Free resources in a. */ +size_t zsave(z_t, void *); /* Store a into b (if !!b), and return number of written bytes. */ +size_t zload(z_t, const void *); /* Restore a from b, and return number of read bytes. */ /* Assignment functions. */ -/* a := b */ -void zset(z_t, z_t); -void zseti(z_t, long long int); -void zsetu(z_t, unsigned long long int); - +void zset(z_t, z_t); /* a := b */ +void zsetu(z_t, uint64_t); /* a := b */ +ZAHL_INLINE void zseti(z_t, int64_t); /* a := b */ /* Comparison functions. */ -/* signum (a - b) */ -int zcmp(z_t, z_t); -int zcmpi(z_t, long long int); -int zcmpu(z_t, unsigned long long int); - -int zcmpmag(z_t, z_t); /* signum (|a| - |b|) */ +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|) */ /* Arithmetic functions. */ -void zadd(z_t, z_t, z_t); /* a := b + c */ -void zsub(z_t, z_t, z_t); /* a := b - c */ -void zmul(z_t, z_t, z_t); /* a := b * c */ -void zmodmul(z_t, z_t, z_t, z_t); /* a := (b * c) % d */ -void zdiv(z_t, z_t, z_t); /* a := b / c */ -void zdivmod(z_t, z_t, z_t, z_t); /* a := c / d, b = c % d */ -void zmod(z_t, z_t, z_t); /* a := b % c */ -void zsqr(z_t, z_t); /* a := b² */ -void zmodsqr(z_t, z_t, z_t); /* a := b² % c */ -void zpow(z_t, z_t, z_t); /* a := b ↑ c */ -void zmodpow(z_t, z_t, z_t, z_t); /* a := (b ↑ c) % d */ +ZAHL_INLINE void zabs(z_t, z_t); /* a := |b| */ +ZAHL_INLINE void zneg(z_t, z_t); /* a := -b */ +void zadd(z_t, z_t, z_t); /* a := b + c */ +void zsub(z_t, z_t, z_t); /* a := b - c */ +void zmul(z_t, z_t, z_t); /* a := b * c */ +void zmodmul(z_t, z_t, z_t, z_t); /* a := (b * c) % d */ +void zdiv(z_t, z_t, z_t); /* a := b / c */ +void zdivmod(z_t, z_t, z_t, z_t); /* a := c / d, b = c % d */ +void zmod(z_t, z_t, z_t); /* a := b % c */ +void zsqr(z_t, z_t); /* a := b² */ +void zmodsqr(z_t, z_t, z_t); /* a := b² % c */ +void zpow(z_t, z_t, z_t); /* a := b ↑ c */ +void zmodpow(z_t, z_t, z_t, z_t); /* a := (b ↑ c) % d */ 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| */ -void zsub_unsigned(z_t, z_t, z_t); /* a := |b| - |c| */ +void zadd_unsigned(z_t, z_t, z_t); /* a := |b| + |c| */ +void zsub_unsigned(z_t, z_t, z_t); /* a := |b| - |c| */ /* Bitwise operations. */ -void zand(z_t, z_t, z_t); /* a := b & c */ -void zor(z_t, z_t, z_t); /* a := b | c */ -void zxor(z_t, z_t, z_t); /* a := b ^ c */ -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) */ +void zand(z_t, z_t, z_t); /* a := b & c */ +void zor(z_t, z_t, z_t); /* a := b | c */ +void zxor(z_t, z_t, z_t); /* a := b ^ c */ +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 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), f d = 0: a := b & ~(1 << c), if d < 0: a := b ^ (1 << c) */ +/* 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); /* Number theory. */ -void zgcd(z_t, z_t, z_t); /* a := gcd(b, c) */ +ZAHL_INLINE int zeven(z_t); /* Is a even? */ +ZAHL_INLINE int zodd(z_t); /* Is a odd? */ +ZAHL_INLINE int zeven_nonzero(z_t); /* Is a even? Assumes a ≠ 0. */ +ZAHL_INLINE int zodd_nonzero(z_t); /* Is a odd? Assumes a ≠ 0. */ +ZAHL_INLINE int zzero(z_t); /* Is a zero? */ +ZAHL_INLINE int zsignum(z_t); /* a/|a|, 0 if a is zero. */ +void zgcd(z_t, z_t, z_t); /* a := gcd(b, c) */ /* NONPRIME if b ∉ ℙ, PROBABLY_PRIME, if b ∈ ℙ with (1 − 4↑−c) certainty, 2 if PRIME ∈ ℙ. * If NONPRIME is returned the witness of b's compositeness is stored in a. */ @@ -127,8 +162,8 @@ void zrand(z_t, enum zranddev, enum zranddist, z_t); /* String conversion. */ -char *zstr(z_t, char *); /* Write a in decimal onto b. */ -int zsets(z_t, const char *); /* a := b */ +char *zstr(z_t, char *); /* Write a in decimal onto b. */ +int zsets(z_t, const char *); /* a := b */ /* Length of a in radix b. */ size_t zstr_length(z_t, unsigned long long int); @@ -136,85 +171,96 @@ size_t zstr_length(z_t, unsigned long long int); /* Error handling functions. */ -enum zerror zerror(const char **); /* Return the current error code, and unless a is 0, a description in *a. */ -void zperror(const char *); /* Identical to perror(3p) except it supports libzahl errors. */ +enum zerror zerror(const char **); /* Return the current error code, and unless !a, a description in *a. */ +void zperror(const char *); /* Identical to perror(3p) except it supports libzahl errors. */ -/* Inline functions. */ -static inline void zinit(z_t a) { a->alloced = 0; a->chars = 0; } /* Prepare a for use. */ -static inline void zswap(z_t a, z_t b) { z_t t; *t = *a; *a = *b; *b = *t; } /* (a, b) := (b, a) */ -static inline int zeven(z_t a) { return !a->sign || !(a->chars[0] & 1); } /* Is a even? */ -static inline int zodd(z_t a) { return a->sign && (a->chars[0] & 1); } /* Is a odd? */ -static inline int zeven_nonzero(z_t a) { return !(a->chars[0] & 1); } /* Is a even? Assumes a ≠ 0. */ -static inline int zodd_nonzero(z_t a) { return (a->chars[0] & 1); } /* Is a odd? Assumes a ≠ 0. */ -static inline int zzero(z_t a) { return !a->sign; } /* Is a zero? */ -static inline int zsignum(z_t a) { return a->sign; } /* a/|a|, 0 if a is zero. */ -static inline void zabs(z_t a, z_t b) { if (a != b) zset(a, b); a->sign = !!a->sign; } /* a := |b| */ -static inline void zneg(z_t a, z_t b) { if (a != b) zset(a, b); a->sign = -a->sign; } /* a := -b */ +/* ------------------------------- Implementations of inline functions. ------------------------------- */ -/* Bitwise inline functions. */ +#if defined(__GNUC__) || defined(__clang__) +# define ZAHL_UNLIKELY(expr) __builtin_expect(!!(expr), 0) +# define ZAHL_LIKELY(expr) __builtin_expect(!!(expr), 1) +#else +# define ZAHL_UNLIKELY(expr) (expr) +# define ZAHL_LIKELY(expr) (expr) +#endif -/* Index of first set bit, SIZE_MAX if none are set. */ -#if defined(__GNUC__) || defined(__clang__) -static inline size_t +ZAHL_INLINE void zinit(z_t a) { a->alloced = 0; a->chars = 0; } +ZAHL_INLINE void zswap(z_t a, z_t b) { z_t t; *t = *a; *a = *b; *b = *t; } +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 zabs(z_t a, z_t b) { if (a != b) zset(a, b); a->sign = !!a->sign; } +ZAHL_INLINE void zneg(z_t a, z_t b) { if (a != b) zset(a, b); a->sign = -a->sign; } + + +ZAHL_INLINE void +zseti(z_t a, int64_t b) +{ + if (ZAHL_UNLIKELY(b >= 0)) { + zsetu(a, (uint64_t)b); + } else { + zsetu(a, (uint64_t)-b); + a->sign = -1; + } +} + + +ZAHL_INLINE size_t zlsb(z_t a) { +#if defined(__GNUC__) || defined(__clang__) size_t i = 0; - if (__builtin_expect(zzero(a), 0)) + if (ZAHL_UNLIKELY(zzero(a))) return SIZE_MAX; for (; !a->chars[i]; i++); i *= 8 * sizeof(zahl_char_t); i += (size_t)__builtin_ctzll(a->chars[i]); return i; -} #else -static inline size_t -zlsb(z_t a) -{ size_t i = 0; zahl_char_t x; - if (zzero(a)) + if (ZAHL_UNLIKELY(zzero(a))) return SIZE_MAX; for (; !a->chars[i]; i++); i *= 8 * sizeof(zahl_char_t); x = ~(a->chars[i]); for (; x & 1; x >>= 1, i++); return i; -} #endif +} -/* ⌊log₂ |a|⌋ + 1, 1 if a = 0 */ -#if defined(__GNUC__) || defined(__clang__) -static inline size_t +ZAHL_INLINE size_t zbits(z_t a) { +#if defined(__GNUC__) || defined(__clang__) size_t rc; - if (__builtin_expect(zzero(a), 0)) + 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); rc -= (size_t)__builtin_clzll(a->chars[a->used - 1]); return rc; -} #else -static inline size_t -zbits(z_t a) -{ size_t rc; zahl_char_t x; - if (zzero(a)) + if (ZAHL_UNLIKELY(zzero(a))) return 1; while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */ x = a->chars[a->used - 1]; rc = (a->used - 1) * 8 * sizeof(zahl_char_t); for (; x; x >>= 1, rc++); return rc; -} #endif +} + #endif |