MIRROR: javascript for 馃悳's, a tiny runtime with big ambitions
1#include <stdlib.h>
2#include <string.h>
3
4#include "ant.h"
5#include "internal.h"
6#include "errors.h"
7#include "runtime.h"
8#include "utils.h"
9#include "silver/lexer.h"
10
11#define BIGINT_BASE ((uint64_t)0x100000000ULL)
12#define BIGINT_DEC_GROUP_BASE 1000000000U
13
14typedef struct {
15 uint8_t sign;
16 uint8_t pad[3];
17 uint32_t limb_count;
18 uint32_t limbs[];
19} bigint_payload_t;
20
21static inline bool is_decimal_digit(char c) {
22 return c >= '0' && c <= '9';
23}
24
25static bool checked_add_size(size_t a, size_t b, size_t *out) {
26 if (a > SIZE_MAX - b) return false;
27 *out = a + b;
28 return true;
29}
30
31static bool checked_mul_size(size_t a, size_t b, size_t *out) {
32 if (a != 0 && b > SIZE_MAX / a) return false;
33 *out = a * b;
34 return true;
35}
36
37static uint32_t *limb_alloc(size_t count) {
38 if (count == 0) count = 1;
39 return (uint32_t *)calloc(count, sizeof(uint32_t));
40}
41
42static uint32_t *limb_dup(const uint32_t *limbs, size_t count) {
43 if (count == 0) count = 1;
44 uint32_t *copy = limb_alloc(count);
45 if (!copy) return NULL;
46 if (limbs && count > 0) memcpy(copy, limbs, count * sizeof(uint32_t));
47 return copy;
48}
49
50static bool grow_u32_buffer(uint32_t **buf, size_t *cap) {
51 if (!buf || !*buf || !cap || *cap == 0 || *cap > SIZE_MAX / 2) return false;
52 size_t new_cap = *cap * 2;
53 uint32_t *grown = (uint32_t *)realloc(*buf, new_cap * sizeof(uint32_t));
54 if (!grown) return false;
55 memset(grown + *cap, 0, (new_cap - *cap) * sizeof(uint32_t));
56 *buf = grown;
57 *cap = new_cap;
58 return true;
59}
60
61static bool append_carry_limbs(uint32_t **limbs, size_t *count, size_t *cap, uint64_t carry) {
62 while (carry != 0) {
63 if (*count == *cap && !grow_u32_buffer(limbs, cap)) return false;
64 (*limbs)[(*count)++] = (uint32_t)carry;
65 carry >>= 32;
66 }
67 return true;
68}
69
70static void bigint_normalize_limbs(uint32_t *limbs, size_t *count) {
71 while (*count > 1 && limbs[*count - 1] == 0) (*count)--;
72}
73
74static inline const bigint_payload_t *bigint_payload(ant_value_t v) {
75 return (const bigint_payload_t *)(uintptr_t)vdata(v);
76}
77
78static inline bool limbs_is_zero(const uint32_t *limbs, size_t count) {
79 return count == 1 && limbs[0] == 0;
80}
81
82bool bigint_is_negative(ant_t *js, ant_value_t v) {
83 return bigint_payload(v)->sign == 1;
84}
85
86static const uint32_t *bigint_limbs(ant_t *js, ant_value_t v, size_t *count) {
87 const bigint_payload_t *payload = bigint_payload(v);
88 size_t limb_count = payload->limb_count;
89 if (limb_count == 0) limb_count = 1;
90 if (count) *count = limb_count;
91 return payload->limbs;
92}
93
94double bigint_to_double(ant_t *js, ant_value_t v) {
95 size_t count;
96 const uint32_t *limbs = bigint_limbs(js, v, &count);
97 if (limbs_is_zero(limbs, count)) return 0.0;
98
99 double result = 0.0;
100 double base = 1.0;
101 for (size_t i = 0; i < count; i++) {
102 result += (double)limbs[i] * base;
103 base *= (double)BIGINT_BASE;
104 }
105
106 return bigint_is_negative(js, v) ? -result : result;
107}
108
109static ant_value_t js_mkbigint_limbs(ant_t *js, const uint32_t *limbs, size_t count, bool negative) {
110 uint32_t zero = 0;
111
112 if (!limbs || count == 0) {
113 limbs = &zero;
114 count = 1;
115 }
116
117 while (count > 1 && limbs[count - 1] == 0) count--;
118 if (count == 1 && limbs[0] == 0) negative = false;
119
120 if (count > UINT32_MAX) return js_mkerr(js, "oom");
121
122 size_t limbs_bytes;
123 if (!checked_mul_size(count, sizeof(uint32_t), &limbs_bytes)) return js_mkerr(js, "oom");
124
125 size_t payload_size;
126 if (!checked_add_size(offsetof(bigint_payload_t, limbs), limbs_bytes, &payload_size)) {
127 return js_mkerr(js, "oom");
128 }
129
130 bigint_payload_t *payload = (bigint_payload_t *)js_type_alloc(
131 js, ANT_ALLOC_BIGINT, payload_size, _Alignof(bigint_payload_t)
132 );
133 if (!payload) return js_mkerr(js, "oom");
134
135 payload->sign = negative ? 1 : 0;
136 payload->pad[0] = 0;
137 payload->pad[1] = 0;
138 payload->pad[2] = 0;
139 payload->limb_count = (uint32_t)count;
140 memcpy(payload->limbs, limbs, limbs_bytes);
141
142 return mkval(T_BIGINT, (uintptr_t)payload);
143}
144
145ant_value_t bigint_from_uint64(ant_t *js, uint64_t value) {
146 uint32_t limbs[2] = {
147 (uint32_t)(value & 0xffffffffu),
148 (uint32_t)(value >> 32)
149 };
150
151 size_t count = limbs[1] == 0 ? 1 : 2;
152 return js_mkbigint_limbs(js, limbs, count, false);
153}
154
155ant_value_t bigint_from_int64(ant_t *js, int64_t value) {
156 uint64_t magnitude = value < 0
157 ? (uint64_t)(-(value + 1)) + 1
158 : (uint64_t)value;
159
160 uint32_t limbs[2] = {
161 (uint32_t)(magnitude & 0xffffffffu),
162 (uint32_t)(magnitude >> 32)
163 };
164
165 size_t count = limbs[1] == 0 ? 1 : 2;
166 return js_mkbigint_limbs(js, limbs, count, value < 0);
167}
168
169static uint64_t bigint_low_u64(ant_t *js, ant_value_t value) {
170 size_t count = 0;
171 const uint32_t *limbs = bigint_limbs(js, value, &count);
172 uint64_t out = count > 0 ? (uint64_t)limbs[0] : 0;
173 if (count > 1) out |= ((uint64_t)limbs[1] << 32);
174 return out;
175}
176
177bool bigint_to_uint64_wrapping(ant_t *js, ant_value_t value, uint64_t *out) {
178 if (!out || vtype(value) != T_BIGINT) return false;
179 uint64_t low = bigint_low_u64(js, value);
180 *out = bigint_is_negative(js, value) ? (uint64_t)(0 - low) : low;
181 return true;
182}
183
184bool bigint_to_int64_wrapping(ant_t *js, ant_value_t value, int64_t *out) {
185 if (!out) return false;
186 uint64_t bits = 0;
187 if (!bigint_to_uint64_wrapping(js, value, &bits)) return false;
188 *out = (int64_t)bits;
189 return true;
190}
191
192static bool bigint_parse_abs_u64(ant_t *js, ant_value_t value, uint64_t *out) {
193 size_t count = 0;
194 const uint32_t *limbs = bigint_limbs(js, value, &count);
195
196 if (count > 2) return false;
197
198 uint64_t acc = limbs[0];
199 if (count == 2) acc |= ((uint64_t)limbs[1] << 32);
200
201 *out = acc;
202 return true;
203}
204
205static bool bigint_parse_u64(ant_t *js, ant_value_t value, uint64_t *out) {
206 if (bigint_is_negative(js, value)) return false;
207 return bigint_parse_abs_u64(js, value, out);
208}
209
210static int bigint_cmp_abs_limbs(const uint32_t *a, size_t alen, const uint32_t *b, size_t blen) {
211 while (alen > 1 && a[alen - 1] == 0) alen--;
212 while (blen > 1 && b[blen - 1] == 0) blen--;
213
214 if (alen != blen) return alen > blen ? 1 : -1;
215
216 for (size_t i = alen; i-- > 0;) {
217 if (a[i] != b[i]) return a[i] > b[i] ? 1 : -1;
218 }
219
220 return 0;
221}
222
223static uint32_t *bigint_add_abs_limbs(const uint32_t *a, size_t alen, const uint32_t *b, size_t blen, size_t *rlen) {
224 size_t maxlen = alen > blen ? alen : blen;
225
226 uint32_t *result = limb_alloc(maxlen + 1);
227 if (!result) return NULL;
228
229 uint64_t carry = 0;
230 for (size_t i = 0; i < maxlen; i++) {
231 uint64_t da = i < alen ? a[i] : 0;
232 uint64_t db = i < blen ? b[i] : 0;
233 uint64_t sum = da + db + carry;
234 result[i] = (uint32_t)sum;
235 carry = sum >> 32;
236 }
237
238 result[maxlen] = (uint32_t)carry;
239 *rlen = maxlen + (carry ? 1 : 0);
240 if (*rlen == 0) *rlen = 1;
241 bigint_normalize_limbs(result, rlen);
242 return result;
243}
244
245static uint32_t *bigint_add_u32(const uint32_t *a, size_t alen, uint32_t value, size_t *rlen) {
246 uint32_t *result = limb_dup(a, alen);
247 if (!result) return NULL;
248
249 uint64_t carry = value;
250 size_t i = 0;
251
252 while (carry != 0 && i < alen) {
253 uint64_t sum = (uint64_t)result[i] + carry;
254 result[i] = (uint32_t)sum;
255 carry = sum >> 32;
256 i++;
257 }
258
259 if (carry == 0) {
260 *rlen = alen;
261 bigint_normalize_limbs(result, rlen);
262 return result;
263 }
264
265 uint32_t *grown = (uint32_t *)realloc(result, (alen + 1) * sizeof(uint32_t));
266 if (!grown) {
267 free(result);
268 return NULL;
269 }
270
271 grown[alen] = (uint32_t)carry;
272 *rlen = alen + 1;
273 return grown;
274}
275
276static uint32_t *bigint_sub_abs_limbs(const uint32_t *a, size_t alen, const uint32_t *b, size_t blen, size_t *rlen) {
277 uint32_t *result = limb_alloc(alen);
278 if (!result) return NULL;
279
280 uint64_t borrow = 0;
281
282 for (size_t i = 0; i < alen; i++) {
283 uint64_t da = a[i];
284 uint64_t db = i < blen ? b[i] : 0;
285 uint64_t subtrahend = db + borrow;
286
287 if (da < subtrahend) {
288 result[i] = (uint32_t)(BIGINT_BASE + da - subtrahend);
289 borrow = 1;
290 } else {
291 result[i] = (uint32_t)(da - subtrahend);
292 borrow = 0;
293 }
294 }
295
296 *rlen = alen;
297 bigint_normalize_limbs(result, rlen);
298 return result;
299}
300
301static uint32_t *bigint_mul_abs_limbs(const uint32_t *a, size_t alen, const uint32_t *b, size_t blen, size_t *rlen) {
302 uint32_t *result = limb_alloc(alen + blen + 1);
303 if (!result) return NULL;
304
305 for (size_t i = 0; i < alen; i++) {
306 uint64_t carry = 0;
307
308 for (size_t j = 0; j < blen; j++) {
309 uint64_t prod = (uint64_t)a[i] * (uint64_t)b[j];
310 uint64_t lo = (uint64_t)result[i + j] + (prod & 0xffffffffu) + (carry & 0xffffffffu);
311 result[i + j] = (uint32_t)lo;
312 carry = (prod >> 32) + (carry >> 32) + (lo >> 32);
313 }
314
315 size_t k = i + blen;
316 while (carry != 0) {
317 uint64_t cur = (uint64_t)result[k] + (carry & 0xffffffffu);
318 result[k] = (uint32_t)cur;
319 carry = (carry >> 32) + (cur >> 32);
320 k++;
321 }
322 }
323
324 *rlen = alen + blen + 1;
325 bigint_normalize_limbs(result, rlen);
326 return result;
327}
328
329static uint32_t *bigint_shift_left_abs(const uint32_t *limbs, size_t count, uint64_t shift, size_t *rlen) {
330 size_t limb_shift = (size_t)(shift >> 5);
331 unsigned bit_shift = (unsigned)(shift & 31u);
332
333 size_t out_count = count + limb_shift + 1;
334 uint32_t *out = limb_alloc(out_count);
335 if (!out) return NULL;
336
337 if (bit_shift == 0) {
338 memcpy(out + limb_shift, limbs, count * sizeof(uint32_t));
339 *rlen = count + limb_shift;
340 bigint_normalize_limbs(out, rlen);
341 return out;
342 }
343
344 uint32_t carry = 0;
345 for (size_t i = 0; i < count; i++) {
346 uint64_t cur = ((uint64_t)limbs[i] << bit_shift) | carry;
347 out[i + limb_shift] = (uint32_t)cur;
348 carry = (uint32_t)(cur >> 32);
349 }
350
351 out[count + limb_shift] = carry;
352 *rlen = out_count;
353 bigint_normalize_limbs(out, rlen);
354 return out;
355}
356
357static uint32_t *bigint_shift_right_abs(
358 const uint32_t *limbs,
359 size_t count,
360 uint64_t shift,
361 bool *truncated,
362 size_t *rlen
363) {
364 size_t limb_shift = (size_t)(shift >> 5);
365 unsigned bit_shift = (unsigned)(shift & 31u);
366
367 bool lost = false;
368
369 if (limb_shift >= count) {
370 for (size_t i = 0; i < count; i++) {
371 if (limbs[i] != 0) { lost = true; break; }
372 }
373
374 uint32_t *zero = limb_alloc(1);
375 if (!zero) return NULL;
376 zero[0] = 0;
377 if (truncated) *truncated = lost;
378 *rlen = 1;
379 return zero;
380 }
381
382 for (size_t i = 0; i < limb_shift; i++) {
383 if (limbs[i] != 0) { lost = true; break; }
384 }
385
386 size_t out_count = count - limb_shift;
387 uint32_t *out = limb_alloc(out_count);
388 if (!out) return NULL;
389
390 if (bit_shift == 0) {
391 memcpy(out, limbs + limb_shift, out_count * sizeof(uint32_t));
392 } else {
393 uint32_t carry = 0;
394 uint32_t mask = (1u << bit_shift) - 1u;
395
396 for (size_t src = count; src-- > limb_shift;) {
397 uint32_t cur = limbs[src];
398 size_t dst = src - limb_shift;
399 out[dst] = (cur >> bit_shift) | (carry << (32u - bit_shift));
400 carry = cur & mask;
401 }
402
403 if ((limbs[limb_shift] & mask) != 0) lost = true;
404 }
405
406 *rlen = out_count;
407 bigint_normalize_limbs(out, rlen);
408 if (truncated) *truncated = lost;
409 return out;
410}
411
412static uint32_t bigint_div_small_inplace(uint32_t *limbs, size_t count, uint32_t divisor) {
413 uint64_t rem = 0;
414
415 for (size_t i = count; i-- > 0;) {
416 uint64_t cur = (rem << 32) | limbs[i];
417 limbs[i] = (uint32_t)(cur / divisor);
418 rem = cur % divisor;
419 }
420
421 return (uint32_t)rem;
422}
423
424static size_t bigint_abs_bitlen_limbs(const uint32_t *limbs, size_t count) {
425 while (count > 1 && limbs[count - 1] == 0) count--;
426 if (count == 1 && limbs[0] == 0) return 0;
427
428 uint32_t top = limbs[count - 1];
429#if defined(__GNUC__) || defined(__clang__)
430 unsigned lead = (unsigned)__builtin_clz(top);
431#else
432 unsigned lead = 0;
433 while ((top & 0x80000000u) == 0) {
434 top <<= 1;
435 lead++;
436 }
437#endif
438 return (count - 1) * 32u + (32u - (size_t)lead);
439}
440
441static uint32_t *bigint_to_twos_complement_limbs(
442 const uint32_t *limbs,
443 size_t count,
444 bool negative,
445 size_t width
446) {
447 if (width == 0) width = 1;
448
449 uint32_t *out = limb_alloc(width);
450 if (!out) return NULL;
451
452 size_t copy_count = count < width ? count : width;
453 if (copy_count > 0) memcpy(out, limbs, copy_count * sizeof(uint32_t));
454
455 if (!negative) return out;
456
457 for (size_t i = 0; i < width; i++) out[i] = ~out[i];
458
459 uint64_t carry = 1;
460 for (size_t i = 0; i < width && carry != 0; i++) {
461 uint64_t cur = (uint64_t)out[i] + carry;
462 out[i] = (uint32_t)cur;
463 carry = cur >> 32;
464 }
465
466 return out;
467}
468
469static uint32_t *bigint_from_twos_complement_limbs(
470 const uint32_t *twos,
471 size_t width,
472 bool *negative_out,
473 size_t *count_out
474) {
475 if (width == 0) width = 1;
476
477 bool negative = (twos[width - 1] & 0x80000000u) != 0;
478 uint32_t *mag = limb_dup(twos, width);
479 if (!mag) return NULL;
480
481 if (negative) {
482 for (size_t i = 0; i < width; i++) mag[i] = ~mag[i];
483 uint64_t carry = 1;
484 for (size_t i = 0; i < width && carry != 0; i++) {
485 uint64_t cur = (uint64_t)mag[i] + carry;
486 mag[i] = (uint32_t)cur;
487 carry = cur >> 32;
488 }
489 }
490
491 size_t mcount = width;
492 bigint_normalize_limbs(mag, &mcount);
493 if (mcount == 1 && mag[0] == 0) negative = false;
494
495 if (negative_out) *negative_out = negative;
496 if (count_out) *count_out = mcount;
497 return mag;
498}
499
500typedef enum {
501 BIGINT_BAND = 0,
502 BIGINT_BOR,
503 BIGINT_BXOR
504} bigint_bitop_t;
505
506static ant_value_t bigint_bitwise_binary(ant_t *js, ant_value_t a, ant_value_t b, bigint_bitop_t op) {
507 bool aneg = bigint_is_negative(js, a);
508 bool bneg = bigint_is_negative(js, b);
509
510 size_t alen = 0, blen = 0;
511 const uint32_t *ad = bigint_limbs(js, a, &alen);
512 const uint32_t *bd = bigint_limbs(js, b, &blen);
513
514 size_t abit = bigint_abs_bitlen_limbs(ad, alen);
515 size_t bbit = bigint_abs_bitlen_limbs(bd, blen);
516 size_t width_bits = (abit > bbit ? abit : bbit) + 1;
517 size_t width = (width_bits + 31u) / 32u;
518 if (width == 0) width = 1;
519
520 uint32_t *at = bigint_to_twos_complement_limbs(ad, alen, aneg, width);
521 uint32_t *bt = bigint_to_twos_complement_limbs(bd, blen, bneg, width);
522 if (!at || !bt) {
523 free(at);
524 free(bt);
525 return js_mkerr(js, "oom");
526 }
527
528 for (size_t i = 0; i < width; i++) {
529 switch (op) {
530 case BIGINT_BAND: at[i] &= bt[i]; break;
531 case BIGINT_BOR: at[i] |= bt[i]; break;
532 case BIGINT_BXOR: at[i] ^= bt[i]; break;
533 }
534 }
535
536 bool negative = false;
537 size_t mcount = 0;
538 uint32_t *mag = bigint_from_twos_complement_limbs(at, width, &negative, &mcount);
539 free(at);
540 free(bt);
541 if (!mag) return js_mkerr(js, "oom");
542
543 ant_value_t out = js_mkbigint_limbs(js, mag, mcount, negative);
544 free(mag);
545 return out;
546}
547
548ant_value_t bigint_bitand(ant_t *js, ant_value_t a, ant_value_t b) {
549 return bigint_bitwise_binary(js, a, b, BIGINT_BAND);
550}
551
552ant_value_t bigint_bitor(ant_t *js, ant_value_t a, ant_value_t b) {
553 return bigint_bitwise_binary(js, a, b, BIGINT_BOR);
554}
555
556ant_value_t bigint_bitxor(ant_t *js, ant_value_t a, ant_value_t b) {
557 return bigint_bitwise_binary(js, a, b, BIGINT_BXOR);
558}
559
560ant_value_t bigint_bitnot(ant_t *js, ant_value_t value) {
561 bool neg = bigint_is_negative(js, value);
562 size_t count = 0;
563 const uint32_t *limbs = bigint_limbs(js, value, &count);
564
565 size_t bits = bigint_abs_bitlen_limbs(limbs, count);
566 size_t width_bits = bits + 1;
567 size_t width = (width_bits + 31u) / 32u;
568 if (width == 0) width = 1;
569
570 uint32_t *twos = bigint_to_twos_complement_limbs(limbs, count, neg, width);
571 if (!twos) return js_mkerr(js, "oom");
572 for (size_t i = 0; i < width; i++) twos[i] = ~twos[i];
573
574 bool out_neg = false;
575 size_t out_count = 0;
576
577 uint32_t *mag = bigint_from_twos_complement_limbs(twos, width, &out_neg, &out_count);
578 free(twos); if (!mag) return js_mkerr(js, "oom");
579
580 ant_value_t out = js_mkbigint_limbs(js, mag, out_count, out_neg);
581 free(mag);
582
583 return out;
584}
585
586static inline unsigned clz32_nonzero(uint32_t v) {
587#if defined(__GNUC__) || defined(__clang__)
588 return (unsigned)__builtin_clz(v);
589#else
590 unsigned n = 0;
591 while ((v & 0x80000000u) == 0) {
592 v <<= 1;
593 n++;
594 }
595 return n;
596#endif
597}
598
599static bool bigint_divmod_abs_limbs(
600 const uint32_t *num,
601 size_t num_count,
602 const uint32_t *den,
603 size_t den_count,
604 uint32_t **q_out,
605 size_t *q_count_out,
606 uint32_t **r_out,
607 size_t *r_count_out
608) {
609 if (den_count == 1 && den[0] == 0) return false;
610
611 int cmp = bigint_cmp_abs_limbs(num, num_count, den, den_count);
612 if (cmp < 0) {
613 if (q_out) {
614 uint32_t *q = limb_alloc(1);
615 if (!q) return false;
616 q[0] = 0;
617 *q_out = q;
618 if (q_count_out) *q_count_out = 1;
619 }
620
621 if (r_out) {
622 uint32_t *r = limb_dup(num, num_count);
623 if (!r) {
624 if (q_out && *q_out) {
625 free(*q_out);
626 *q_out = NULL;
627 }
628 return false;
629 }
630 size_t rcount = num_count;
631 bigint_normalize_limbs(r, &rcount);
632 *r_out = r;
633 if (r_count_out) *r_count_out = rcount;
634 }
635
636 return true;
637 }
638
639 if (den_count == 1) {
640 uint32_t divisor = den[0];
641 uint32_t *q = limb_dup(num, num_count);
642 if (!q) return false;
643
644 uint64_t rem = 0;
645 for (size_t i = num_count; i-- > 0;) {
646 uint64_t cur = (rem << 32) | q[i];
647 q[i] = (uint32_t)(cur / divisor);
648 rem = cur % divisor;
649 }
650
651 size_t qcount = num_count;
652 bigint_normalize_limbs(q, &qcount);
653
654 if (q_out) {
655 *q_out = q;
656 if (q_count_out) *q_count_out = qcount;
657 } else free(q);
658
659 if (r_out) {
660 uint32_t *r = limb_alloc(1);
661 if (!r) {
662 if (q_out && *q_out) {
663 free(*q_out);
664 *q_out = NULL;
665 }
666 return false;
667 }
668 r[0] = (uint32_t)rem;
669 *r_out = r;
670 if (r_count_out) *r_count_out = 1;
671 }
672
673 return true;
674 }
675
676 size_t m = num_count - den_count;
677 uint32_t *vn = limb_alloc(den_count);
678 uint32_t *un = limb_alloc(num_count + 1);
679 uint32_t *q = limb_alloc(m + 1);
680
681 if (!vn || !un || !q) {
682 free(vn);
683 free(un);
684 free(q);
685 return false;
686 }
687
688 unsigned shift = clz32_nonzero(den[den_count - 1]);
689
690 if (shift == 0) {
691 memcpy(vn, den, den_count * sizeof(uint32_t));
692 memcpy(un, num, num_count * sizeof(uint32_t));
693 un[num_count] = 0;
694 } else {
695 uint32_t carry = 0;
696 for (size_t i = 0; i < den_count; i++) {
697 uint64_t cur = ((uint64_t)den[i] << shift) | carry;
698 vn[i] = (uint32_t)cur;
699 carry = (uint32_t)(cur >> 32);
700 }
701
702 carry = 0;
703 for (size_t i = 0; i < num_count; i++) {
704 uint64_t cur = ((uint64_t)num[i] << shift) | carry;
705 un[i] = (uint32_t)cur;
706 carry = (uint32_t)(cur >> 32);
707 }
708 un[num_count] = carry;
709 }
710
711 for (size_t j = m + 1; j-- > 0;) {
712 uint64_t numerator = ((uint64_t)un[j + den_count] << 32) | un[j + den_count - 1];
713 uint64_t qhat = numerator / vn[den_count - 1];
714 uint64_t rhat = numerator % vn[den_count - 1];
715
716 if (qhat >= BIGINT_BASE) {
717 qhat = BIGINT_BASE - 1;
718 rhat = numerator - qhat * vn[den_count - 1];
719 }
720
721 if (den_count > 1) {
722 while (qhat * (uint64_t)vn[den_count - 2] > ((rhat << 32) | un[j + den_count - 2])) {
723 qhat--;
724 rhat += vn[den_count - 1];
725 if (rhat >= BIGINT_BASE) break;
726 }
727 }
728
729 uint64_t k = 0;
730 for (size_t i = 0; i < den_count; i++) {
731 uint64_t p = qhat * (uint64_t)vn[i] + k;
732 k = p >> 32;
733 uint32_t plow = (uint32_t)p;
734
735 if (un[j + i] < plow) {
736 un[j + i] = (uint32_t)((uint64_t)un[j + i] + BIGINT_BASE - plow);
737 k += 1;
738 } else {
739 un[j + i] -= plow;
740 }
741 }
742
743 bool borrow = un[j + den_count] < k;
744 un[j + den_count] = (uint32_t)(un[j + den_count] - k);
745
746 if (borrow) {
747 qhat--;
748 uint64_t carry = 0;
749 for (size_t i = 0; i < den_count; i++) {
750 uint64_t sum = (uint64_t)un[j + i] + vn[i] + carry;
751 un[j + i] = (uint32_t)sum;
752 carry = sum >> 32;
753 }
754 un[j + den_count] = (uint32_t)((uint64_t)un[j + den_count] + carry);
755 }
756
757 q[j] = (uint32_t)qhat;
758 }
759
760 size_t qcount = m + 1;
761 bigint_normalize_limbs(q, &qcount);
762
763 if (q_out) {
764 *q_out = q;
765 if (q_count_out) *q_count_out = qcount;
766 } else free(q);
767
768 if (r_out) {
769 uint32_t *r = limb_alloc(den_count);
770 if (!r) {
771 free(vn);
772 free(un);
773 if (q_out && *q_out) {
774 free(*q_out);
775 *q_out = NULL;
776 }
777 return false;
778 }
779
780 if (shift == 0) {
781 memcpy(r, un, den_count * sizeof(uint32_t));
782 } else {
783 uint32_t carry = 0;
784 for (size_t i = den_count; i-- > 0;) {
785 uint32_t cur = un[i];
786 r[i] = (cur >> shift) | (carry << (32u - shift));
787 carry = cur & ((1u << shift) - 1u);
788 }
789 }
790
791 size_t rcount = den_count;
792 bigint_normalize_limbs(r, &rcount);
793 *r_out = r;
794 if (r_count_out) *r_count_out = rcount;
795 }
796
797 free(vn);
798 free(un);
799 return true;
800}
801
802static ant_value_t bigint_from_string_digits(
803 ant_t *js,
804 const char *digits,
805 size_t len,
806 bool negative,
807 bool allow_separators
808) {
809 if (!digits || len == 0) {
810 uint32_t zero = 0;
811 return js_mkbigint_limbs(js, &zero, 1, false);
812 }
813
814 uint32_t base = 10;
815 size_t start = 0;
816
817 if (len >= 2 && digits[0] == '0') {
818 char p = (char)(digits[1] | 0x20);
819 if (p == 'x') {
820 base = 16;
821 start = 2;
822 } else if (p == 'o') {
823 base = 8;
824 start = 2;
825 } else if (p == 'b') {
826 base = 2;
827 start = 2;
828 }
829 }
830
831 if (start >= len) return js_mkerr(js, "Cannot convert string to BigInt");
832
833 size_t cap = len / 8 + 2;
834 if (cap < 4) cap = 4;
835 uint32_t *limbs = limb_alloc(cap);
836 if (!limbs) return js_mkerr(js, "oom");
837
838 size_t count = 1;
839 bool has_digit = false;
840 bool prev_sep = false;
841
842 for (size_t i = start; i < len; i++) {
843 char ch = digits[i];
844
845 if (ch == '_') {
846 if (!allow_separators || !has_digit || prev_sep) {
847 free(limbs);
848 return js_mkerr(js, "Cannot convert string to BigInt");
849 }
850 prev_sep = true;
851 continue;
852 }
853
854 int digit = hex_digit(ch);
855 if (digit < 0 || (uint32_t)digit >= base) {
856 free(limbs);
857 return js_mkerr(js, "Cannot convert string to BigInt");
858 }
859
860 has_digit = true;
861 prev_sep = false;
862
863 uint64_t carry = (uint64_t)digit;
864
865 for (size_t j = 0; j < count; j++) {
866 uint64_t cur = (uint64_t)limbs[j] * base + carry;
867 limbs[j] = (uint32_t)cur;
868 carry = cur >> 32;
869 }
870
871 if (carry != 0 && !append_carry_limbs(&limbs, &count, &cap, carry)) {
872 free(limbs);
873 return js_mkerr(js, "oom");
874 }
875 }
876
877 if (!has_digit || prev_sep) {
878 free(limbs);
879 return js_mkerr(js, "Cannot convert string to BigInt");
880 }
881
882 ant_value_t result = js_mkbigint_limbs(js, limbs, count, negative);
883 free(limbs);
884 return result;
885}
886
887static size_t u32_dec_len(uint32_t v) {
888 if (v >= 1000000000u) return 10;
889 if (v >= 100000000u) return 9;
890 if (v >= 10000000u) return 8;
891 if (v >= 1000000u) return 7;
892 if (v >= 100000u) return 6;
893 if (v >= 10000u) return 5;
894 if (v >= 1000u) return 4;
895 if (v >= 100u) return 3;
896 if (v >= 10u) return 2;
897 return 1;
898}
899
900static char *bigint_abs_to_decimal_string(const uint32_t *limbs, size_t count, size_t *out_len) {
901 if (limbs_is_zero(limbs, count)) {
902 char *z = (char *)malloc(2);
903 if (!z) return NULL;
904 z[0] = '0';
905 z[1] = '\0';
906 if (out_len) *out_len = 1;
907 return z;
908 }
909
910 uint32_t *tmp = limb_dup(limbs, count);
911 if (!tmp) return NULL;
912
913 size_t tmp_count = count;
914 size_t groups_cap = count * 2 + 1;
915 uint32_t *groups = (uint32_t *)malloc(groups_cap * sizeof(uint32_t));
916 if (!groups) {
917 free(tmp);
918 return NULL;
919 }
920
921 size_t groups_len = 0;
922
923 while (!(tmp_count == 1 && tmp[0] == 0)) {
924 if (groups_len == groups_cap && !grow_u32_buffer(&groups, &groups_cap)) {
925 free(tmp);
926 free(groups);
927 return NULL;
928 }
929
930 uint32_t rem = bigint_div_small_inplace(tmp, tmp_count, BIGINT_DEC_GROUP_BASE);
931 groups[groups_len++] = rem;
932 bigint_normalize_limbs(tmp, &tmp_count);
933 }
934
935 free(tmp);
936
937 size_t len = u32_dec_len(groups[groups_len - 1]) + (groups_len - 1) * 9;
938 char *out = (char *)malloc(len + 1);
939 if (!out) {
940 free(groups);
941 return NULL;
942 }
943
944 size_t pos = 0;
945 pos += (size_t)snprintf(out + pos, len + 1 - pos, "%u", groups[groups_len - 1]);
946
947 for (size_t i = groups_len - 1; i-- > 0;) {
948 pos += (size_t)snprintf(out + pos, len + 1 - pos, "%09u", groups[i]);
949 }
950
951 out[len] = '\0';
952 free(groups);
953
954 if (out_len) *out_len = len;
955 return out;
956}
957
958static char *bigint_abs_to_radix_string(const uint32_t *limbs, size_t count, uint32_t radix, size_t *out_len) {
959 static const char digit_map[] = "0123456789abcdefghijklmnopqrstuvwxyz";
960
961 if (limbs_is_zero(limbs, count)) {
962 char *z = (char *)malloc(2);
963 if (!z) return NULL;
964 z[0] = '0';
965 z[1] = '\0';
966 if (out_len) *out_len = 1;
967 return z;
968 }
969
970 uint32_t *tmp = limb_dup(limbs, count);
971 if (!tmp) return NULL;
972
973 size_t tmp_count = count;
974 size_t out_cap = count * 32 + 2;
975 char *out = (char *)malloc(out_cap);
976 if (!out) {
977 free(tmp);
978 return NULL;
979 }
980
981 size_t out_pos = 0;
982
983 while (!(tmp_count == 1 && tmp[0] == 0)) {
984 if (out_pos + 1 >= out_cap) {
985 size_t new_cap = out_cap * 2;
986 char *new_out = (char *)realloc(out, new_cap);
987 if (!new_out) {
988 free(tmp);
989 free(out);
990 return NULL;
991 }
992 out = new_out;
993 out_cap = new_cap;
994 }
995
996 uint32_t rem = bigint_div_small_inplace(tmp, tmp_count, radix);
997 out[out_pos++] = digit_map[rem];
998 bigint_normalize_limbs(tmp, &tmp_count);
999 }
1000
1001 for (size_t i = 0; i < out_pos / 2; i++) {
1002 char t = out[i];
1003 out[i] = out[out_pos - 1 - i];
1004 out[out_pos - 1 - i] = t;
1005 }
1006
1007 out[out_pos] = '\0';
1008 free(tmp);
1009
1010 if (out_len) *out_len = out_pos;
1011 return out;
1012}
1013
1014ant_value_t js_mkbigint(ant_t *js, const char *digits, size_t len, bool negative) {
1015 return bigint_from_string_digits(js, digits, len, negative, true);
1016}
1017
1018ant_value_t bigint_add(ant_t *js, ant_value_t a, ant_value_t b) {
1019 bool aneg = bigint_is_negative(js, a);
1020 bool bneg = bigint_is_negative(js, b);
1021
1022 size_t alen = 0, blen = 0;
1023 const uint32_t *ad = bigint_limbs(js, a, &alen);
1024 const uint32_t *bd = bigint_limbs(js, b, &blen);
1025
1026 uint32_t *result = NULL;
1027 size_t rlen = 0;
1028 bool rneg = false;
1029
1030 if (aneg == bneg) {
1031 result = bigint_add_abs_limbs(ad, alen, bd, blen, &rlen);
1032 rneg = aneg;
1033 } else {
1034 int cmp = bigint_cmp_abs_limbs(ad, alen, bd, blen);
1035 if (cmp >= 0) {
1036 result = bigint_sub_abs_limbs(ad, alen, bd, blen, &rlen);
1037 rneg = aneg;
1038 } else {
1039 result = bigint_sub_abs_limbs(bd, blen, ad, alen, &rlen);
1040 rneg = bneg;
1041 }
1042 }
1043
1044 if (!result) return js_mkerr(js, "oom");
1045
1046 ant_value_t out = js_mkbigint_limbs(js, result, rlen, rneg);
1047 free(result);
1048 return out;
1049}
1050
1051ant_value_t bigint_sub(ant_t *js, ant_value_t a, ant_value_t b) {
1052 bool aneg = bigint_is_negative(js, a);
1053 bool bneg = bigint_is_negative(js, b);
1054
1055 size_t alen = 0, blen = 0;
1056 const uint32_t *ad = bigint_limbs(js, a, &alen);
1057 const uint32_t *bd = bigint_limbs(js, b, &blen);
1058
1059 uint32_t *result = NULL;
1060 size_t rlen = 0;
1061 bool rneg = false;
1062
1063 if (aneg != bneg) {
1064 result = bigint_add_abs_limbs(ad, alen, bd, blen, &rlen);
1065 rneg = aneg;
1066 } else {
1067 int cmp = bigint_cmp_abs_limbs(ad, alen, bd, blen);
1068 if (cmp >= 0) {
1069 result = bigint_sub_abs_limbs(ad, alen, bd, blen, &rlen);
1070 rneg = aneg;
1071 } else {
1072 result = bigint_sub_abs_limbs(bd, blen, ad, alen, &rlen);
1073 rneg = !aneg;
1074 }
1075 }
1076
1077 if (!result) return js_mkerr(js, "oom");
1078
1079 ant_value_t out = js_mkbigint_limbs(js, result, rlen, rneg);
1080 free(result);
1081 return out;
1082}
1083
1084ant_value_t bigint_mul(ant_t *js, ant_value_t a, ant_value_t b) {
1085 bool aneg = bigint_is_negative(js, a);
1086 bool bneg = bigint_is_negative(js, b);
1087
1088 size_t alen = 0, blen = 0;
1089 const uint32_t *ad = bigint_limbs(js, a, &alen);
1090 const uint32_t *bd = bigint_limbs(js, b, &blen);
1091
1092 uint32_t *result = bigint_mul_abs_limbs(ad, alen, bd, blen, &alen);
1093 if (!result) return js_mkerr(js, "oom");
1094
1095 bool rneg = (aneg != bneg) && !(alen == 1 && result[0] == 0);
1096 ant_value_t out = js_mkbigint_limbs(js, result, alen, rneg);
1097 free(result);
1098 return out;
1099}
1100
1101ant_value_t bigint_div(ant_t *js, ant_value_t a, ant_value_t b) {
1102 bool aneg = bigint_is_negative(js, a);
1103 bool bneg = bigint_is_negative(js, b);
1104
1105 size_t alen = 0, blen = 0;
1106 const uint32_t *ad = bigint_limbs(js, a, &alen);
1107 const uint32_t *bd = bigint_limbs(js, b, &blen);
1108
1109 if (blen == 1 && bd[0] == 0) return js_mkerr(js, "Division by zero");
1110
1111 uint32_t *quot = NULL;
1112 size_t qlen = 0;
1113
1114 if (!bigint_divmod_abs_limbs(ad, alen, bd, blen, ", &qlen, NULL, NULL)) {
1115 return js_mkerr(js, "oom");
1116 }
1117
1118 bool qneg = (aneg != bneg) && !(qlen == 1 && quot[0] == 0);
1119 ant_value_t out = js_mkbigint_limbs(js, quot, qlen, qneg);
1120 free(quot);
1121 return out;
1122}
1123
1124ant_value_t bigint_mod(ant_t *js, ant_value_t a, ant_value_t b) {
1125 bool aneg = bigint_is_negative(js, a);
1126
1127 size_t alen = 0, blen = 0;
1128 const uint32_t *ad = bigint_limbs(js, a, &alen);
1129 const uint32_t *bd = bigint_limbs(js, b, &blen);
1130
1131 if (blen == 1 && bd[0] == 0) return js_mkerr(js, "Division by zero");
1132
1133 uint32_t *rem = NULL;
1134 size_t rlen = 0;
1135
1136 if (!bigint_divmod_abs_limbs(ad, alen, bd, blen, NULL, NULL, &rem, &rlen)) {
1137 return js_mkerr(js, "oom");
1138 }
1139
1140 bool rneg = aneg && !(rlen == 1 && rem[0] == 0);
1141 ant_value_t out = js_mkbigint_limbs(js, rem, rlen, rneg);
1142 free(rem);
1143 return out;
1144}
1145
1146ant_value_t bigint_neg(ant_t *js, ant_value_t a) {
1147 size_t len = 0;
1148 const uint32_t *limbs = bigint_limbs(js, a, &len);
1149 bool neg = bigint_is_negative(js, a);
1150
1151 if (limbs_is_zero(limbs, len)) return js_mkbigint_limbs(js, limbs, len, false);
1152 return js_mkbigint_limbs(js, limbs, len, !neg);
1153}
1154
1155static inline bool bigint_is_odd(ant_t *js, ant_value_t v) {
1156 size_t count = 0;
1157 const uint32_t *limbs = bigint_limbs(js, v, &count);
1158 (void)count;
1159 return (limbs[0] & 1u) != 0;
1160}
1161
1162static inline ant_value_t bigint_pow2(ant_t *js, uint64_t bits) {
1163 uint64_t limb_index_u64 = bits >> 5;
1164 if (limb_index_u64 > SIZE_MAX - 1) return js_mkerr(js, "oom");
1165
1166 size_t count = (size_t)limb_index_u64 + 1;
1167 uint32_t *limbs = limb_alloc(count);
1168 if (!limbs) return js_mkerr(js, "oom");
1169
1170 limbs[(size_t)limb_index_u64] = 1u << (bits & 31u);
1171 ant_value_t out = js_mkbigint_limbs(js, limbs, count, false);
1172 free(limbs);
1173 return out;
1174}
1175
1176ant_value_t bigint_shift_left(ant_t *js, ant_value_t value, uint64_t shift) {
1177 if (shift == 0) return value;
1178
1179 size_t count = 0;
1180 const uint32_t *limbs = bigint_limbs(js, value, &count);
1181
1182 if (limbs_is_zero(limbs, count)) return js_mkbigint(js, "0", 1, false);
1183
1184 uint32_t *result = NULL;
1185 size_t rlen = 0;
1186 result = bigint_shift_left_abs(limbs, count, shift, &rlen);
1187 if (!result) return js_mkerr(js, "oom");
1188
1189 ant_value_t out = js_mkbigint_limbs(js, result, rlen, bigint_is_negative(js, value));
1190 free(result);
1191 return out;
1192}
1193
1194ant_value_t bigint_shift_right(ant_t *js, ant_value_t value, uint64_t shift) {
1195 if (shift == 0) return value;
1196
1197 size_t count = 0;
1198 const uint32_t *limbs = bigint_limbs(js, value, &count);
1199
1200 if (limbs_is_zero(limbs, count)) return js_mkbigint(js, "0", 1, false);
1201
1202 bool neg = bigint_is_negative(js, value);
1203 bool truncated = false;
1204
1205 size_t qlen = 0;
1206 uint32_t *q = bigint_shift_right_abs(limbs, count, shift, &truncated, &qlen);
1207 if (!q) return js_mkerr(js, "oom");
1208
1209 if (!neg) {
1210 ant_value_t out = js_mkbigint_limbs(js, q, qlen, false);
1211 free(q);
1212 return out;
1213 }
1214
1215 if (truncated) {
1216 size_t new_len = 0;
1217 uint32_t *adj = bigint_add_u32(q, qlen, 1, &new_len);
1218 free(q);
1219 if (!adj) return js_mkerr(js, "oom");
1220 q = adj;
1221 qlen = new_len;
1222 }
1223
1224 ant_value_t out = js_mkbigint_limbs(js, q, qlen, !limbs_is_zero(q, qlen));
1225 free(q);
1226 return out;
1227}
1228
1229ant_value_t bigint_shift_right_logical(ant_t *js, ant_value_t value, uint64_t shift) {
1230 (void)value;
1231 (void)shift;
1232 return js_mkerr_typed(js, JS_ERR_TYPE, "BigInts have no unsigned right shift, use >> instead");
1233}
1234
1235int bigint_compare(ant_t *js, ant_value_t a, ant_value_t b) {
1236 bool aneg = bigint_is_negative(js, a);
1237 bool bneg = bigint_is_negative(js, b);
1238
1239 if (aneg && !bneg) return -1;
1240 if (!aneg && bneg) return 1;
1241
1242 size_t alen = 0, blen = 0;
1243 const uint32_t *ad = bigint_limbs(js, a, &alen);
1244 const uint32_t *bd = bigint_limbs(js, b, &blen);
1245
1246 int cmp = bigint_cmp_abs_limbs(ad, alen, bd, blen);
1247 return aneg ? -cmp : cmp;
1248}
1249
1250bool bigint_is_zero(ant_t *js, ant_value_t v) {
1251 size_t count = 0;
1252 const uint32_t *limbs = bigint_limbs(js, v, &count);
1253 return limbs_is_zero(limbs, count);
1254}
1255
1256size_t bigint_digits_len(ant_t *js, ant_value_t v) {
1257 size_t count = 0;
1258 const uint32_t *limbs = bigint_limbs(js, v, &count);
1259
1260 size_t len = 0;
1261 char *digits = bigint_abs_to_decimal_string(limbs, count, &len);
1262 if (!digits) return 0;
1263
1264 free(digits);
1265 return len;
1266}
1267
1268ant_value_t bigint_exp(ant_t *js, ant_value_t base, ant_value_t exp) {
1269 if (bigint_is_negative(js, exp)) return js_mkerr(js, "Exponent must be positive");
1270 if (bigint_is_zero(js, exp)) return js_mkbigint(js, "1", 1, false);
1271
1272 ant_value_t result = js_mkbigint(js, "1", 1, false);
1273 ant_value_t b = base;
1274 ant_value_t e = exp;
1275
1276 while (!bigint_is_zero(js, e)) {
1277 if (bigint_is_odd(js, e)) {
1278 result = bigint_mul(js, result, b);
1279 if (is_err(result)) return result;
1280 }
1281
1282 b = bigint_mul(js, b, b);
1283 if (is_err(b)) return b;
1284
1285 e = bigint_shift_right(js, e, 1);
1286 if (is_err(e)) return e;
1287 }
1288
1289 return result;
1290}
1291
1292size_t strbigint(ant_t *js, ant_value_t value, char *buf, size_t len) {
1293 bool neg = bigint_is_negative(js, value);
1294
1295 size_t count = 0;
1296 const uint32_t *limbs = bigint_limbs(js, value, &count);
1297
1298 size_t dlen = 0;
1299 char *digits = bigint_abs_to_decimal_string(limbs, count, &dlen);
1300 if (!digits) return 0;
1301
1302 size_t total = dlen + (neg ? 1 : 0);
1303 if (len == 0) {
1304 free(digits);
1305 return total;
1306 }
1307
1308 size_t n = 0;
1309
1310 if (neg && n < len - 1) buf[n] = '-';
1311 if (neg) n++;
1312
1313 size_t avail = n < len ? len - n - 1 : 0;
1314 size_t copy_len = dlen < avail ? dlen : avail;
1315 if (copy_len > 0) memcpy(buf + n, digits, copy_len);
1316
1317 size_t term = n + copy_len;
1318 if (term >= len) term = len - 1;
1319 buf[term] = '\0';
1320
1321 free(digits);
1322 return total;
1323}
1324
1325static ant_value_t builtin_BigInt(ant_t *js, ant_value_t *args, int nargs) {
1326 if (vtype(js->new_target) != T_UNDEF) return js_mkerr_typed(js, JS_ERR_TYPE, "BigInt is not a constructor");
1327 if (nargs < 1) return js_mkbigint(js, "0", 1, false);
1328
1329 ant_value_t arg = args[0];
1330 if (vtype(arg) == T_BIGINT) return arg;
1331
1332 if (vtype(arg) == T_NUM) {
1333 double d = tod(arg);
1334 if (!isfinite(d)) return js_mkerr(js, "Cannot convert Infinity or NaN to BigInt");
1335 if (d != trunc(d)) return js_mkerr(js, "Cannot convert non-integer to BigInt");
1336
1337 bool neg = d < 0;
1338 if (neg) d = -d;
1339
1340 int need = snprintf(NULL, 0, "%.0f", d);
1341 if (need < 0) return js_mkerr(js, "Cannot convert to BigInt");
1342
1343 char *buf = (char *)malloc((size_t)need + 1);
1344 if (!buf) return js_mkerr(js, "oom");
1345
1346 snprintf(buf, (size_t)need + 1, "%.0f", d);
1347 ant_value_t out = js_mkbigint(js, buf, (size_t)need, neg);
1348 free(buf);
1349 return out;
1350 }
1351
1352 if (vtype(arg) == T_STR) {
1353 ant_offset_t slen;
1354 ant_offset_t off = vstr(js, arg, &slen);
1355 const char *str = (const char *)(uintptr_t)(off);
1356
1357 size_t start = 0;
1358 size_t end = slen;
1359
1360 while (start < end && is_space((unsigned char)str[start])) start++;
1361 while (end > start && is_space((unsigned char)str[end - 1])) end--;
1362 if (start >= end) return js_mkbigint(js, "0", 1, false);
1363
1364 bool neg = false;
1365 if (str[start] == '-') {
1366 neg = true;
1367 start++;
1368 } else if (str[start] == '+') start++;
1369
1370 if (start >= end) return js_mkerr(js, "Cannot convert string to BigInt");
1371 return bigint_from_string_digits(js, str + start, end - start, neg, false);
1372 }
1373
1374 if (vtype(arg) == T_BOOL) return js_mkbigint(js, vdata(arg) ? "1" : "0", 1, false);
1375
1376 return js_mkerr(js, "Cannot convert to BigInt");
1377}
1378
1379static ant_value_t bigint_to_u64(ant_t *js, ant_value_t value, uint64_t *out) {
1380 if (!bigint_parse_u64(js, value, out)) {
1381 return js_mkerr_typed(js, JS_ERR_RANGE, "Invalid bits");
1382 }
1383 return js_mkundef();
1384}
1385
1386ant_value_t bigint_asint_bits(ant_t *js, ant_value_t arg, uint64_t *bits_out) {
1387 if (vtype(arg) == T_BIGINT) return bigint_to_u64(js, arg, bits_out);
1388
1389 double bits = js_to_number(js, arg);
1390 if (!isfinite(bits) || bits < 0 || bits != floor(bits)) {
1391 return js_mkerr_typed(js, JS_ERR_RANGE, "Invalid bits");
1392 }
1393
1394 if (bits > 18446744073709551615.0) {
1395 return js_mkerr_typed(js, JS_ERR_RANGE, "Invalid bits");
1396 }
1397
1398 *bits_out = (uint64_t)bits;
1399 return js_mkundef();
1400}
1401
1402static ant_value_t builtin_BigInt_asIntN(ant_t *js, ant_value_t *args, int nargs) {
1403 if (nargs < 2) return js_mkerr(js, "BigInt.asIntN requires 2 arguments");
1404
1405 uint64_t bits = 0;
1406 ant_value_t err = bigint_asint_bits(js, args[0], &bits);
1407 if (is_err(err)) return err;
1408
1409 if (vtype(args[1]) != T_BIGINT) return js_mkerr_typed(js, JS_ERR_TYPE, "Cannot convert to BigInt");
1410 if (bits == 0) return js_mkbigint(js, "0", 1, false);
1411
1412 ant_value_t mod = bigint_pow2(js, bits);
1413 if (is_err(mod)) return mod;
1414
1415 ant_value_t res = bigint_mod(js, args[1], mod);
1416 if (is_err(res)) return res;
1417
1418 if (bigint_is_negative(js, res)) {
1419 ant_value_t adj = bigint_add(js, res, mod);
1420 if (is_err(adj)) return adj;
1421 res = adj;
1422 }
1423
1424 ant_value_t threshold = bigint_pow2(js, bits - 1);
1425 if (is_err(threshold)) return threshold;
1426
1427 if (bigint_compare(js, res, threshold) >= 0) {
1428 ant_value_t adj = bigint_sub(js, res, mod);
1429 if (is_err(adj)) return adj;
1430 res = adj;
1431 }
1432
1433 return res;
1434}
1435
1436static ant_value_t builtin_BigInt_asUintN(ant_t *js, ant_value_t *args, int nargs) {
1437 if (nargs < 2) return js_mkerr(js, "BigInt.asUintN requires 2 arguments");
1438
1439 uint64_t bits = 0;
1440 ant_value_t err = bigint_asint_bits(js, args[0], &bits);
1441 if (is_err(err)) return err;
1442
1443 if (vtype(args[1]) != T_BIGINT) return js_mkerr_typed(js, JS_ERR_TYPE, "Cannot convert to BigInt");
1444 if (bits == 0) return js_mkbigint(js, "0", 1, false);
1445
1446 ant_value_t mod = bigint_pow2(js, bits);
1447 if (is_err(mod)) return mod;
1448
1449 ant_value_t res = bigint_mod(js, args[1], mod);
1450 if (is_err(res)) return res;
1451
1452 if (bigint_is_negative(js, res)) {
1453 ant_value_t adj = bigint_add(js, res, mod);
1454 if (is_err(adj)) return adj;
1455 res = adj;
1456 }
1457
1458 return res;
1459}
1460
1461static ant_value_t builtin_bigint_toString(ant_t *js, ant_value_t *args, int nargs) {
1462 ant_value_t val = js->this_val;
1463 if (vtype(val) != T_BIGINT) return js_mkerr(js, "toString called on non-BigInt");
1464
1465 int radix = 10;
1466 if (nargs >= 1 && vtype(args[0]) == T_NUM) {
1467 radix = (int)tod(args[0]);
1468 if (radix < 2 || radix > 36) return js_mkerr(js, "radix must be between 2 and 36");
1469 }
1470
1471 bool neg = bigint_is_negative(js, val);
1472 size_t count = 0;
1473 const uint32_t *limbs = bigint_limbs(js, val, &count);
1474
1475 size_t dlen = 0;
1476 char *digits = NULL;
1477
1478 if (radix == 10) digits = bigint_abs_to_decimal_string(limbs, count, &dlen);
1479 else digits = bigint_abs_to_radix_string(limbs, count, (uint32_t)radix, &dlen);
1480
1481 if (!digits) return js_mkerr(js, "oom");
1482
1483 if (!neg) {
1484 ant_value_t out = js_mkstr(js, digits, dlen);
1485 free(digits);
1486 return out;
1487 }
1488
1489 char *full = (char *)malloc(dlen + 2);
1490 if (!full) {
1491 free(digits);
1492 return js_mkerr(js, "oom");
1493 }
1494
1495 full[0] = '-';
1496 memcpy(full + 1, digits, dlen);
1497 full[dlen + 1] = '\0';
1498
1499 ant_value_t out = js_mkstr(js, full, dlen + 1);
1500 free(digits);
1501 free(full);
1502 return out;
1503}
1504
1505void init_bigint_module(void) {
1506 ant_t *js = rt->js;
1507
1508 ant_value_t glob = js_glob(js);
1509 ant_value_t object_proto = js->sym.object_proto;
1510 ant_value_t function_proto = js_get_slot(glob, SLOT_FUNC_PROTO);
1511 if (vtype(function_proto) == T_UNDEF) function_proto = js_get_ctor_proto(js, "Function", 8);
1512
1513 ant_value_t bigint_proto = js_mkobj(js);
1514 js_set_proto_init(bigint_proto, object_proto);
1515 defmethod(js, bigint_proto, "toString", 8, js_mkfun(builtin_bigint_toString));
1516
1517 ant_value_t bigint_ctor_obj = mkobj(js, 0);
1518 js_set_proto_init(bigint_ctor_obj, function_proto);
1519 js_set_slot(bigint_ctor_obj, SLOT_CFUNC, js_mkfun(builtin_BigInt));
1520 js_setprop(js, bigint_ctor_obj, js_mkstr(js, "asIntN", 6), js_mkfun(builtin_BigInt_asIntN));
1521 js_setprop(js, bigint_ctor_obj, js_mkstr(js, "asUintN", 7), js_mkfun(builtin_BigInt_asUintN));
1522 js_setprop_nonconfigurable(js, bigint_ctor_obj, "prototype", 9, bigint_proto);
1523 js_setprop(js, bigint_ctor_obj, ANT_STRING("name"), ANT_STRING("BigInt"));
1524 js_setprop(js, glob, js_mkstr(js, "BigInt", 6), js_obj_to_func(bigint_ctor_obj));
1525}