inlines.h - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
inlines.h (6645B)
---
1 /* See LICENSE file for copyright and license details. */
2
3 ZAHL_INLINE void zinit(z_t a) { a->alloced = 0; a->chars = 0; }
4 ZAHL_INLINE int zeven(z_t a) { return !a->sign || (~a->chars[0] & 1); }
5 ZAHL_INLINE int zodd(z_t a) { return a->sign && (a->chars[0] & 1); }
6 ZAHL_INLINE int zeven_nonzero(z_t a) { return ~a->chars[0] & 1; }
7 ZAHL_INLINE int zodd_nonzero(z_t a) { return a->chars[0] & 1; }
8 ZAHL_INLINE int zzero(z_t a) { return !a->sign; }
9 ZAHL_INLINE int zsignum(z_t a) { return a->sign; }
10 ZAHL_INLINE void zneg(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = -a->sign; }
11
12 #if 1 && (-1 & 1) /* In the future, tuning will select the fastest implementation. */
13 ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign &= 1; }
14 #elif 1
15 ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); if (ZAHL_LIKELY(a->sign < 0)) a->sign = 1; }
16 #else
17 ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = !!a->sign; }
18 #endif
19
20
21 #if ULONG_MAX != SIZE_MAX /* This variant should be equivalent to the second one if .sign was long. */
22 ZAHL_INLINE void
23 zswap(z_t a, z_t b)
24 {
25 z_t t;
26 ZAHL_SWAP(a, b, t, sign);
27 ZAHL_SWAP(b, a, t, used);
28 ZAHL_SWAP(a, b, t, alloced);
29 ZAHL_SWAP(b, a, t, chars);
30 }
31 #else
32 ZAHL_INLINE void
33 zswap(z_t a_, z_t b_)
34 {
35 register long t;
36 long *a = (long *)a_;
37 long *b = (long *)b_;
38 t = a[0], a[0] = b[0], b[0] = t;
39 t = b[1], b[1] = a[1], a[1] = t;
40 t = a[2], a[2] = b[2], b[2] = t;
41 t = b[3], b[3] = a[3], a[3] = t;
42 }
43 #endif
44
45
46 ZAHL_INLINE void
47 zset(z_t a, z_t b)
48 {
49 if (ZAHL_UNLIKELY(b->sign == 0)) {
50 a->sign = 0;
51 } else {
52 a->sign = b->sign;
53 a->used = b->used;
54 ZAHL_ENSURE_SIZE(a, b->used);
55 libzahl_memcpy(a->chars, b->chars, b->used);
56 }
57 }
58
59
60 ZAHL_INLINE void
61 zseti(z_t a, int64_t b)
62 {
63 if (ZAHL_UNLIKELY(b >= 0)) {
64 zsetu(a, (uint64_t)b);
65 return;
66 }
67 ZAHL_ENSURE_SIZE(a, 1);
68 ZAHL_SET_SIGNUM(a, -1);
69 a->chars[0] = (zahl_char_t)-b;
70 a->used = 1;
71 }
72
73
74 ZAHL_INLINE void
75 zsetu(z_t a, uint64_t b)
76 {
77 if (ZAHL_UNLIKELY(!b)) {
78 ZAHL_SET_SIGNUM(a, 0);
79 return;
80 }
81 ZAHL_ENSURE_SIZE(a, 1);
82 ZAHL_SET_SIGNUM(a, 1);
83 a->chars[0] = (zahl_char_t)b;
84 a->used = 1;
85 }
86
87
88 ZAHL_INLINE size_t
89 zlsb(z_t a)
90 {
91 size_t i = 0;
92 if (ZAHL_UNLIKELY(zzero(a)))
93 return SIZE_MAX;
94 for (; !a->chars[i]; i++);
95 i *= 8 * sizeof(zahl_char_t);
96 ZAHL_ADD_CTZ(i, a->chars[i]);
97 return i;
98 }
99
100
101 ZAHL_INLINE size_t
102 zbits(z_t a)
103 {
104 size_t rc;
105 if (ZAHL_UNLIKELY(zzero(a)))
106 return 1;
107 while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */
108 rc = a->used * 8 * sizeof(zahl_char_t);
109 ZAHL_SUB_CLZ(rc, a->chars[a->used - 1]);
110 return rc;
111 }
112
113
114 ZAHL_INLINE int
115 zcmpmag(z_t a, z_t b)
116 {
117 size_t i, j;
118 if (ZAHL_UNLIKELY(zzero(a))) return -!zzero(b);
119 if (ZAHL_UNLIKELY(zzero(b))) return 1;
120 i = a->used - 1;
121 j = b->used - 1;
122 #if 0 /* TODO this should be sufficient. */
123 if (i != j)
124 return (i > j) * 2 - 1;
125 #else
126 for (; i > j; i--) {
127 if (a->chars[i])
128 return +1;
129 a->used--;
130 }
131 for (; j > i; j--) {
132 if (b->chars[j])
133 return -1;
134 b->used--;
135 }
136 #endif
137 for (; i && a->chars[i] == b->chars[i]; i--);
138 return a->chars[i] < b->chars[i] ? -1 : a->chars[i] > b->chars[i];
139 }
140
141
142 ZAHL_INLINE int
143 zcmp(z_t a, z_t b)
144 {
145 if (zsignum(a) != zsignum(b))
146 return zsignum(a) < zsignum(b) ? -1 : zsignum(a) > zsignum(b);
147 return zsignum(a) * zcmpmag(a, b);
148 }
149
150
151 ZAHL_INLINE int
152 zcmpu(z_t a, uint64_t b)
153 {
154 if (ZAHL_UNLIKELY(!b))
155 return zsignum(a);
156 if (ZAHL_UNLIKELY(zsignum(a) <= 0))
157 return -1;
158 while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */
159 if (a->used > 1)
160 return +1;
161 return a->chars[0] < b ? -1 : a->chars[0] > b;
162 }
163
164
165 ZAHL_INLINE int
166 zcmpi(z_t a, int64_t b)
167 {
168 if (ZAHL_UNLIKELY(!b))
169 return zsignum(a);
170 if (ZAHL_UNLIKELY(zzero(a)))
171 return ZAHL_LIKELY(b < 0) ? 1 : -1;
172 if (ZAHL_LIKELY(b < 0)) {
173 if (zsignum(a) > 0)
174 return +1;
175 while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */
176 if (a->used > 1)
177 return -1;
178 return a->chars[0] > (zahl_char_t)-b ? -1 : a->chars[0] < (zahl_char_t)-b;
179 } else {
180 if (zsignum(a) < 0)
181 return -1;
182 while (!a->chars[a->used - 1]) a->used--; /* TODO should not be necessary */
183 if (a->used > 1)
184 return +1;
185 return a->chars[0] < (zahl_char_t)b ? -1 : a->chars[0] > (zahl_char_t)b;
186 }
187 }
188
189
190 ZAHL_INLINE void
191 zbset(z_t a, z_t b, size_t bit, int action)
192 {
193 if (ZAHL_UNLIKELY(a != b))
194 zset(a, b);
195
196 #ifdef ZAHL_CONST_P
197 if (ZAHL_CONST_P(action) && ZAHL_CONST_P(bit)) {
198 zahl_char_t mask = 1;
199 if (zzero(a) || ZAHL_FLOOR_BITS_TO_CHARS(bit) >= a->used) {
200 if (!action)
201 return;
202 goto fallback;
203 }
204 mask <<= ZAHL_BITS_IN_LAST_CHAR(bit);
205 if (action > 0) {
206 a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] |= mask;
207 return;
208 } else if (action < 0) {
209 a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] ^= mask;
210 } else {
211 a->chars[ZAHL_FLOOR_BITS_TO_CHARS(bit)] &= ~mask;
212 }
213 ZAHL_TRIM_AND_ZERO(a);
214 return;
215 }
216 fallback:
217 #endif
218
219 if (action > 0)
220 zbset_ll_set(a, bit);
221 else if (action < 0)
222 zbset_ll_flip(a, bit);
223 else
224 zbset_ll_clear(a, bit);
225 }
226
227
228 ZAHL_O3 ZAHL_INLINE int
229 zbtest(z_t a, size_t bit)
230 {
231 size_t chars;
232 if (ZAHL_UNLIKELY(zzero(a)))
233 return 0;
234
235 chars = ZAHL_FLOOR_BITS_TO_CHARS(bit);
236 if (ZAHL_UNLIKELY(chars >= a->used))
237 return 0;
238
239 bit &= ZAHL_BITS_IN_LAST_CHAR(bit);
240 return (a->chars[chars] >> bit) & 1;
241 }
242
243
244 ZAHL_O3 ZAHL_INLINE void
245 zsplit(z_t high, z_t low, z_t a, size_t delim)
246 {
247 if (ZAHL_UNLIKELY(high == a)) {
248 ztrunc(low, a, delim);
249 zrsh(high, a, delim);
250 } else {
251 zrsh(high, a, delim);
252 ztrunc(low, a, delim);
253 }
254 }
255
256
257 ZAHL_INLINE size_t
258 zsave(z_t a, void *buffer)
259 {
260 if (ZAHL_LIKELY(buffer)) {
261 char *buf = buffer;
262 *((long *)buf) = a->sign, buf += sizeof(long); /* Use `long` for alignment. */
263 *((size_t *)buf) = a->used, buf += sizeof(size_t);
264 if (ZAHL_LIKELY(!zzero(a))) {
265 a->chars[a->used + 2] = 0;
266 a->chars[a->used + 1] = 0;
267 a->chars[a->used + 0] = 0;
268 libzahl_memcpy((zahl_char_t *)buf, a->chars, a->used);
269 }
270 }
271 return sizeof(long) + sizeof(size_t) +
272 (zzero(a) ? 0 :((a->used + 3) & (size_t)~3) * sizeof(zahl_char_t));
273 }
274
275
276 ZAHL_INLINE void
277 zmul(z_t a, z_t b, z_t c)
278 {
279 int b_sign, c_sign;
280 b_sign = b->sign, b->sign *= b_sign;
281 c_sign = c->sign, c->sign *= c_sign;
282 zmul_ll(a, b, c);
283 c->sign = c_sign;
284 b->sign = b_sign;
285 ZAHL_SET_SIGNUM(a, zsignum(b) * zsignum(c));
286 }
287
288
289 ZAHL_INLINE void
290 zsqr(z_t a, z_t b)
291 {
292 if (ZAHL_UNLIKELY(zzero(b))) {
293 ZAHL_SET_SIGNUM(a, 0);
294 } else {
295 zsqr_ll(a, b);
296 ZAHL_SET_SIGNUM(a, 1);
297 }
298 }
299
300
301 ZAHL_INLINE void
302 zdiv(z_t a, z_t b, z_t c)
303 {
304 zdivmod(a, libzahl_tmp_div, b, c);
305 }
306
307
308 ZAHL_INLINE void
309 zmod(z_t a, z_t b, z_t c)
310 {
311 zdivmod(libzahl_tmp_mod, a, b, c);
312 }