zahl.h - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
zahl.h (7741B)
---
1 /* See LICENSE file for copyright and license details. */
2
3 /* Warning: libzahl is not thread-safe. */
4 /* Caution: Do not use libzahl for cryptographic applications, use a specialised library. */
5
6 #ifndef ZAHL_H
7 #define ZAHL_H 1
8
9
10 #include <limits.h>
11 #include <setjmp.h>
12 #include <stddef.h>
13 #include <stdint.h>
14 #include <unistd.h>
15
16
17
18 /* TODO these should be documented*/
19 #define ZAHL_VERSION_MAJOR 1L
20 #define ZAHL_VERSION_MINOR 1L
21 #define ZAHL_VERSION_PATCHLEVEL 0L
22 #define ZAHL_VERSION (ZAHL_VERSION_MAJOR * 1000000L + \
23 ZAHL_VERSION_MINOR * 1000L + \
24 ZAHL_VERSION_PATCHLEVEL)
25 #define ZAHL_VERSION_STRING "1.1"
26 #define ZAHL_INTERNALS_VERSION 1
27 #define ZAHL_ZRANDDEV_COUNT 7
28 #define ZAHL_ZRANDDIST_COUNT 3
29 #define ZAHL_ZERROR_COUNT 6
30
31
32
33 #include "zahl/internals.h"
34
35
36
37 typedef struct zahl z_t[1];
38
39
40
41 enum zprimality {
42 NONPRIME = 0, /* The number is definitely composite. */
43 PROBABLY_PRIME, /* The number is probably prime. */
44 PRIME /* The number is definitely prime. */
45 };
46
47 enum zranddev {
48 FAST_RANDOM = 0, /* Random numbers are generated directly from /dev/urandom. */
49 SECURE_RANDOM, /* Random numbers are generated directly from /dev/random. */
50 DEFAULT_RANDOM, /* Select the default random number generator. */
51 FASTEST_RANDOM, /* Select the fastest random number generator. */
52 LIBC_RAND_RANDOM, /* Use rand(3). */
53 LIBC_RANDOM_RANDOM, /* Use random(3). */
54 LIBC_RAND48_RANDOM /* Use lrand48(3). */
55 };
56
57 enum zranddist {
58 QUASIUNIFORM = 0, /* Almost uniformly random, per the usual recommendation. */
59 UNIFORM, /* Actually uniformly random. */
60 MODUNIFORM /* Almost uniformly random, using the naïve approach of modulation. */
61 };
62
63 enum zerror {
64 ZERROR_ERRNO_SET = 0, /* Please refer to errno. */
65 ZERROR_0_POW_0, /* Indeterminate form: 0:th power of 0. (Translatable to EDOM.) */
66 ZERROR_0_DIV_0, /* Indeterminate form: 0 divided by 0. (Translatable to EDOM.) */
67 ZERROR_DIV_0, /* Undefined result: Division by 0. (Translatable to EDOM.) */
68 ZERROR_NEGATIVE, /* Argument must be non-negative. (Translatable to EDOM or EINVAL.) */
69 ZERROR_INVALID_RADIX /* Radix must be at least 2. (Translatable to EINVAL.) */
70 };
71
72
73
74 /* The parameters in the functions below are numbers a, b, c, ... */
75
76
77 /* Library initialisation and destruction. */
78
79 void zsetup(jmp_buf); /* Prepare libzahl for use. */
80 void zunsetup(void); /* Free resources used by libzahl */
81
82
83 /* Memory functions. */
84
85 ZAHL_INLINE void zinit(z_t); /* Prepare a for use. */
86 ZAHL_INLINE void zswap(z_t, z_t); /* (a, b) := (b, a) */
87 void zfree(z_t); /* Free resources in a. */
88 ZAHL_INLINE size_t zsave(z_t, void *); /* Store a into b (if !!b), and return number of written bytes. */
89 size_t zload(z_t, const void *); /* Restore a from b, and return number of read bytes. */
90
91
92 /* Assignment functions. */
93
94 ZAHL_INLINE void zset(z_t, z_t); /* a := b */
95 ZAHL_INLINE void zsetu(z_t, uint64_t); /* a := b */
96 ZAHL_INLINE void zseti(z_t, int64_t); /* a := b */
97
98
99 /* Comparison functions. */
100
101 ZAHL_INLINE int zcmp(z_t, z_t); /* signum (a - b) */
102 ZAHL_INLINE int zcmpu(z_t, uint64_t); /* signum (a - b) */
103 ZAHL_INLINE int zcmpi(z_t, int64_t); /* signum (a - b) */
104 ZAHL_INLINE int zcmpmag(z_t, z_t); /* signum (|a| - |b|) */
105
106
107 /* Arithmetic functions. */
108
109 ZAHL_INLINE void zabs(z_t, z_t); /* a := |b| */
110 ZAHL_INLINE void zneg(z_t, z_t); /* a := -b */
111 void zadd(z_t, z_t, z_t); /* a := b + c */
112 void zsub(z_t, z_t, z_t); /* a := b - c */
113 ZAHL_INLINE void zmul(z_t, z_t, z_t); /* a := b * c */
114 void zmodmul(z_t, z_t, z_t, z_t); /* a := (b * c) % d */
115 ZAHL_INLINE void zdiv(z_t, z_t, z_t); /* a := b / c */
116 void zdivmod(z_t, z_t, z_t, z_t); /* a := c / d, b = c % d */
117 ZAHL_INLINE void zmod(z_t, z_t, z_t); /* a := b % c */
118 ZAHL_INLINE void zsqr(z_t, z_t); /* a := b² */
119 void zmodsqr(z_t, z_t, z_t); /* a := b² % c */
120 void zpow(z_t, z_t, z_t); /* a := b ↑ c */
121 void zmodpow(z_t, z_t, z_t, z_t); /* a := (b ↑ c) % d */
122 void zpowu(z_t, z_t, unsigned long long int);
123 void zmodpowu(z_t, z_t, unsigned long long int, z_t);
124
125 /* These are used internally and may be removed in a future version. */
126 void zadd_unsigned(z_t, z_t, z_t); /* a := |b| + |c| */
127 void zsub_unsigned(z_t, z_t, z_t); /* a := |b| - |c| */
128 void zadd_unsigned_assign(z_t, z_t); /* a := |a| + |b| */
129 void zsub_nonnegative_assign(z_t, z_t); /* a := a - b, assuming a ≥ b ≥ 0 */
130 void zsub_positive_assign(z_t, z_t); /* a := a - b, assuming a > b > 0 */
131
132
133 /* Bitwise operations. */
134
135 void zand(z_t, z_t, z_t); /* a := b & c */
136 void zor(z_t, z_t, z_t); /* a := b | c */
137 void zxor(z_t, z_t, z_t); /* a := b ^ c */
138 void znot(z_t, z_t); /* a := ~b */
139 void zlsh(z_t, z_t, size_t); /* a := b << c */
140 void zrsh(z_t, z_t, size_t); /* a := b >> c */
141 void ztrunc(z_t, z_t, size_t); /* a := b & ((1 << c) - 1) */
142 ZAHL_INLINE void zsplit(z_t, z_t, z_t, size_t);
143 /* a := c >> d, b := c - (a << d) */
144 ZAHL_INLINE int zbtest(z_t, size_t); /* (a >> b) & 1 */
145 ZAHL_INLINE size_t zlsb(z_t); /* Index of first set bit, SIZE_MAX if none are set. */
146 ZAHL_INLINE size_t zbits(z_t); /* ⌊log₂ |a|⌋ + 1, 1 if a = 0 */
147
148 /* If d > 0: a := b | (1 << c), if d = 0: a := b & ~(1 << c), if d < 0: a := b ^ (1 << c) */
149 ZAHL_INLINE void zbset(z_t, z_t, size_t, int);
150
151
152 /* Number theory. */
153
154 ZAHL_INLINE int zeven(z_t); /* Is a even? */
155 ZAHL_INLINE int zodd(z_t); /* Is a odd? */
156 ZAHL_INLINE int zeven_nonzero(z_t); /* Is a even? Assumes a ≠ 0. */
157 ZAHL_INLINE int zodd_nonzero(z_t); /* Is a odd? Assumes a ≠ 0. */
158 ZAHL_INLINE int zzero(z_t); /* Is a zero? */
159 ZAHL_INLINE int zsignum(z_t); /* a/|a|, 0 if a is zero. */
160 void zgcd(z_t, z_t, z_t); /* a := gcd(b, c) */
161
162 /* NONPRIME if b ∉ ℙ, PROBABLY_PRIME, if b ∈ ℙ with (1 − 4↑−c) certainty, 2 if PRIME ∈ ℙ.
163 * If NONPRIME is returned the witness of b's compositeness is stored in a. */
164 enum zprimality zptest(z_t, z_t, int);
165
166
167 /* Random number generation. */
168
169 /* Pick a randomly from [0, d] ∩ ℤ. */
170 void zrand(z_t, enum zranddev, enum zranddist, z_t);
171
172
173 /* String conversion. */
174
175 char *zstr(z_t, char *, size_t); /* Write a in decimal onto b. c is the output size or 0. */
176 int zsets(z_t, const char *); /* a := b */
177
178 /* Length of a in radix b. */
179 size_t zstr_length(z_t, unsigned long long int);
180
181
182 /* Error handling functions. */
183
184 enum zerror zerror(const char **); /* Return the current error code, and unless !a, a description in *a. */
185 void zperror(const char *); /* Identical to perror(3p) except it supports libzahl errors. */
186
187
188
189 /* Low-level functions. [Do not count on these to be retained between different versions of libzahl.] */
190
191 void zbset_ll_set(z_t, size_t); /* zbset(a, a, b, 1) */
192 void zbset_ll_clear(z_t, size_t); /* zbset(a, a, b, 0) */
193 void zbset_ll_flip(z_t, size_t); /* zbset(a, a, b, -1) */
194 void zmul_ll(z_t, z_t, z_t); /* zmul for non-negative operands */
195 void zsqr_ll(z_t, z_t); /* zsqr for non-negative operand */
196
197
198
199 #include "zahl/inlines.h"
200
201
202 #endif