inlines.h - libzahl - big integer library | |
git clone git://git.suckless.org/libzahl | |
Log | |
Files | |
Refs | |
README | |
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]… | |
5 ZAHL_INLINE int zodd(z_t a) { return a->sign && (a->chars[0] &… | |
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->si… | |
11 | |
12 #if 1 && (-1 & 1) /* In the future, tuning will select the fastest imple… | |
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(… | |
16 #else | |
17 ZAHL_INLINE void zabs(z_t a, z_t b) { ZAHL_SET(a, b); a->sign = !!a->s… | |
18 #endif | |
19 | |
20 | |
21 #if ULONG_MAX != SIZE_MAX /* This variant should be equivalent to the se… | |
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… | |
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) > zsign… | |
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… | |
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 shoul… | |
176 if (a->used > 1) | |
177 return -1; | |
178 return a->chars[0] > (zahl_char_t)-b ? -1 : a->chars[0] … | |
179 } else { | |
180 if (zsignum(a) < 0) | |
181 return -1; | |
182 while (!a->chars[a->used - 1]) a->used--; /* TODO shoul… | |
183 if (a->used > 1) | |
184 return +1; | |
185 return a->chars[0] < (zahl_char_t)b ? -1 : a->chars[0] >… | |
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 … | |
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->… | |
269 } | |
270 } | |
271 return sizeof(long) + sizeof(size_t) + | |
272 (zzero(a) ? 0 :((a->used + 3) & (size_t)~3) * sizeof(zah… | |
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 } |