Ruby 4.1.0dev (2026-11-16 revision 9c7bc705b8bd4542beac71542a8ea79f9bb7622b)
integer.c
1#include "prism/internal/integer.h"
2
5
6#include "prism/internal/allocator.h"
7#include "prism/internal/arena.h"
8#include "prism/internal/assert.h"
9#include "prism/internal/bignum.h"
10#include "prism/internal/bit.h"
11#include "prism/internal/buffer.h"
12#include "prism/internal/oom.h"
13
14/* Include sys/types.h before inttypes.h to work around an issue with certain
15 * versions of GCC and newlib which causes omission of PRIu64 and the other
16 * 64-bit macros. */
17#include <sys/types.h>
18#include <inttypes.h>
19
20#include <stdbool.h>
21#include <stddef.h>
22#include <stdlib.h>
23#include <string.h>
24
30#define PM_INTEGER_DIVIDE_THRESHOLD 224
31
39#define PM_INTEGER_STRING_THRESHOLD 48
40
47#define PM_INTEGER_STRING_LEAF 8
48
52static const int8_t pm_integer_parse_digit_values[256] = {
53/* 0 1 2 3 4 5 6 7 8 9 A B C D E F */
54 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 0x */
55 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 1x */
56 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 2x */
57 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, /* 3x */
58 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 4x */
59 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 5x */
60 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 6x */
61 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 7x */
62 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 8x */
63 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 9x */
64 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* Ax */
65 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* Bx */
66 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* Cx */
67 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* Dx */
68 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* Ex */
69 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* Fx */
70};
71
75static uint8_t
76pm_integer_parse_digit(const uint8_t character) {
77 int8_t value = pm_integer_parse_digit_values[character];
78 PRISM_ASSERT(value != -1 && "invalid digit");
79
80 return (uint8_t) value;
81}
82
88static PRISM_INLINE bool
89pm_integer_separator(uint8_t character) {
90 return character == '_' || character == '.';
91}
92
98static void
99pm_integer_from_bignum(pm_arena_t *arena, pm_integer_t *integer, const pm_bignum_t *bignum, uint32_t capacity) {
100 if (bignum->length <= 2) {
101 uint64_t value = pm_bignum_uint64(bignum);
102 pm_arena_realloc(arena, bignum->words, 0, sizeof(uint32_t) * capacity, PRISM_ALIGNOF(uint32_t));
103 *integer = pm_integer_uint64(value);
104 } else {
105 uint32_t *words = (uint32_t *) pm_arena_realloc(arena, bignum->words, sizeof(uint32_t) * bignum->length, sizeof(uint32_t) * capacity, PRISM_ALIGNOF(uint32_t));
106 *integer = (pm_integer_t) { .length = bignum->length, .words = { .values = words } };
107 }
108}
109
116static void
117pm_integer_parse_powof2(pm_arena_t *arena, pm_integer_t *integer, uint32_t base, uint32_t digits, const uint8_t *start, const uint8_t *end) {
118 static const uint8_t digit_bits[16] = { 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 };
119 uint32_t leading_bits = digit_bits[pm_integer_parse_digit(*start)];
120
121 uint32_t bit = (uint32_t) pm_ctzll(base);
122 PRISM_ASSERT(bit >= 1 && bit <= 4);
123
124 uint32_t length = (uint32_t) (((uint64_t) (digits - 1) * bit + leading_bits + 31) / 32);
125 PRISM_ASSERT(length > 2);
126
127 uint32_t *words = pm_arena_zalloc(arena, sizeof(uint32_t) * length, PRISM_ALIGNOF(uint32_t));
128 uint64_t bit_position = 0;
129
130 for (const uint8_t *cursor = end; cursor > start;) {
131 if (pm_integer_separator(*--cursor)) continue;
132 uint32_t value = pm_integer_parse_digit(*cursor);
133
134 uint32_t index = (uint32_t) (bit_position / 32);
135 uint32_t shift = (uint32_t) (bit_position % 32);
136
137 words[index] |= value << shift;
138 if (32 - shift < bit && index + 1 < length) words[index + 1] |= value >> (32 - shift);
139
140 bit_position += bit;
141 }
142
143 *integer = (pm_integer_t) { .length = length, .words = { .values = words } };
144}
145
156static PRISM_INLINE uint32_t
157pm_integer_decimal_words(uint64_t digits) {
158 return (uint32_t) ((digits * 3402 / 1024) / 32 + 1);
159}
160
169static PRISM_INLINE uint32_t
170pm_integer_chunks_words(uint32_t nchunks) {
171 return pm_integer_decimal_words((uint64_t) nchunks * 9) + 1;
172}
173
179static void
180pm_integer_parse_decimal_divide_chunks(pm_bignum_t *result, uint32_t nchunks, const uint32_t *chunks, const pm_bignum_t *powers, pm_bignum_scratch_t *scratch) {
181 if (nchunks <= PM_INTEGER_DIVIDE_THRESHOLD) {
182 result->length = 0;
183 for (uint32_t index = nchunks; index > 0; index--) pm_bignum_mul_add(result, PM_BIGNUM_DECIMAL_BASE, chunks[index - 1]);
184 } else {
185 uint32_t level = pm_bsrll((uint64_t) nchunks - 1);
186 uint32_t split = (uint32_t) 1 << level;
187
188 uint32_t *saved = scratch->cursor;
189 pm_bignum_t high = { .length = 0, .words = pm_bignum_scratch_take(scratch, pm_integer_chunks_words(nchunks - split)) };
190 pm_integer_parse_decimal_divide_chunks(&high, nchunks - split, chunks + split, powers, scratch);
191
192 PRISM_ASSERT(high.length + powers[level].length <= pm_integer_chunks_words(nchunks));
193 pm_bignum_multiply(result, &high, &powers[level], scratch);
194 scratch->cursor = saved;
195
196 pm_bignum_t low = { .length = 0, .words = pm_bignum_scratch_take(scratch, pm_integer_chunks_words(split)) };
197 pm_integer_parse_decimal_divide_chunks(&low, split, chunks, powers, scratch);
198 pm_bignum_add(result, &low);
199 scratch->cursor = saved;
200 }
201}
202
213static void
214pm_integer_parse_decimal_divide(pm_arena_t *arena, pm_integer_t *integer, uint32_t digits, const uint8_t *start, const uint8_t *end) {
215 uint32_t nchunks = (uint32_t) (((uint64_t) digits + 8) / 9);
216 uint32_t capacity = pm_integer_chunks_words(nchunks);
217
218 pm_bignum_t result = {
219 .length = 0,
220 .words = (uint32_t *) pm_arena_alloc(arena, sizeof(uint32_t) * capacity, PRISM_ALIGNOF(uint32_t))
221 };
222
223 /* The scratch space is about 12 times the number of chunks, which can
224 * exceed 32 bits, and on a 32-bit platform its size in bytes can exceed
225 * size_t. */
226 uint64_t scratch_size = (uint64_t) nchunks + 12 * (uint64_t) capacity + 1024;
227 if (scratch_size > SIZE_MAX / sizeof(uint32_t)) PRISM_OOM();
228
229 uint32_t *allocation = (uint32_t *) xmalloc(sizeof(uint32_t) * (size_t) scratch_size);
230 if (allocation == NULL) PRISM_OOM();
231 pm_bignum_scratch_t scratch = { .cursor = allocation, .end = allocation + (size_t) scratch_size };
232
233 /* Pack the digits into chunks of nine, least significant first. The most
234 * significant chunk takes the leftover digits so the rest are exactly
235 * nine. */
236 uint32_t *chunks = pm_bignum_scratch_take(&scratch, nchunks);
237 uint32_t chunk_size = digits % 9 == 0 ? 9 : digits % 9;
238 uint32_t chunk_digits = 0;
239 uint32_t chunk_index = nchunks;
240 uint32_t chunk = 0;
241
242 for (const uint8_t *cursor = start; cursor < end; cursor++) {
243 if (pm_integer_separator(*cursor)) continue;
244 chunk = chunk * 10 + pm_integer_parse_digit(*cursor);
245
246 if (++chunk_digits == chunk_size) {
247 chunks[--chunk_index] = chunk;
248 chunk_size = 9;
249 chunk_digits = 0;
250 chunk = 0;
251 }
252 }
253 PRISM_ASSERT(chunk_index == 0);
254
255 /* powers[level] is 10**(9 * 2**level), for every level a split uses. */
256 pm_bignum_t powers[64];
257 uint32_t level = 0;
258 powers[level].words = pm_bignum_scratch_take(&scratch, 1);
259 powers[level].words[0] = PM_BIGNUM_DECIMAL_BASE;
260 powers[level].length = 1;
261
262 for (uint32_t split = 2; split < nchunks; split *= 2) {
263 const pm_bignum_t *previous = &powers[level++];
264 powers[level].words = pm_bignum_scratch_take(&scratch, 2 * previous->length);
265 pm_bignum_multiply(&powers[level], previous, previous, &scratch);
266 }
267
268 pm_integer_parse_decimal_divide_chunks(&result, nchunks, chunks, powers, &scratch);
269 xfree_sized(allocation, sizeof(uint32_t) * (size_t) scratch_size);
270
271 PRISM_ASSERT(result.length > 2 && result.length <= capacity);
272 pm_integer_from_bignum(arena, integer, &result, capacity);
273}
274
282static void
283pm_integer_parse_decimal_schoolbook(pm_arena_t *arena, pm_integer_t *integer, uint32_t digits, const uint8_t *start, const uint8_t *end) {
284 static const uint32_t powof10[10] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
285
286 /* The words that turn out to be unneeded are given back to the arena
287 * below. */
288 uint32_t capacity = pm_integer_decimal_words(digits);
289 pm_bignum_t bignum = {
290 .length = 0,
291 .words = (uint32_t *) pm_arena_alloc(arena, sizeof(uint32_t) * capacity, PRISM_ALIGNOF(uint32_t))
292 };
293
294 uint32_t chunk_size = digits % 9 == 0 ? 9 : digits % 9;
295 uint32_t chunk_digits = 0;
296 uint32_t chunk = 0;
297
298 for (const uint8_t *cursor = start; cursor < end; cursor++) {
299 if (pm_integer_separator(*cursor)) continue;
300 chunk = chunk * 10 + pm_integer_parse_digit(*cursor);
301
302 if (++chunk_digits == chunk_size) {
303 pm_bignum_mul_add(&bignum, powof10[chunk_size], chunk);
304
305 chunk_size = 9;
306 chunk_digits = 0;
307 chunk = 0;
308 }
309 }
310
311 PRISM_ASSERT(bignum.length > 2 && bignum.length <= capacity);
312 pm_integer_from_bignum(arena, integer, &bignum, capacity);
313}
314
318static void
319pm_integer_parse_digits(pm_arena_t *arena, pm_integer_t *integer, uint32_t base, const uint8_t *start, const uint8_t *end) {
320 /* Leading zeros do not change the value, so skip them here and the paths
321 * below always start at a nonzero digit. */
322 while (start < end && (*start == '0' || pm_integer_separator(*start))) start++;
323
324 /* Everything has been consumed if the integer is zero, or if it is invalid
325 * and has no digits. Either way the result is zero. */
326 if (start >= end) {
327 *integer = (pm_integer_t) { 0 };
328 return;
329 }
330
331 /* Accumulate into a uint64_t, which covers every integer whose words are
332 * stored inline. value * base + digit overflows exactly when value
333 * is past limit, or equal to it with digit past limit_digit. */
334 const uint64_t limit = UINT64_MAX / base;
335 const uint64_t limit_digit = UINT64_MAX % base;
336
337 const uint8_t *cursor = start;
338 uint64_t value = (uint64_t) pm_integer_parse_digit(*cursor++);
339
340 for (; cursor < end; cursor++) {
341 if (pm_integer_separator(*cursor)) continue;
342 uint64_t digit = (uint64_t) pm_integer_parse_digit(*cursor);
343
344 if (value > limit || (value == limit && digit > limit_digit)) {
345 uint32_t digits = 0;
346 for (const uint8_t *scan = start; scan < end; scan++) {
347 if (!pm_integer_separator(*scan)) digits++;
348 }
349
350 if (base != 10) {
351 pm_integer_parse_powof2(arena, integer, base, digits, start, end);
352 } else if (((uint64_t) digits + 8) / 9 > PM_INTEGER_DIVIDE_THRESHOLD) {
353 pm_integer_parse_decimal_divide(arena, integer, digits, start, end);
354 } else {
355 pm_integer_parse_decimal_schoolbook(arena, integer, digits, start, end);
356 }
357
358 return;
359 }
360
361 value = value * base + digit;
362 }
363
364 *integer = pm_integer_uint64(value);
365}
366
372void
373pm_integer_parse(pm_arena_t *arena, pm_integer_t *integer, pm_integer_base_t base, const uint8_t *start, const uint8_t *end) {
374 /* Ignore unary +. Unary - is parsed differently and will not end up here.
375 * Instead, it will modify the parsed integer later. */
376 if (*start == '+') start++;
377
378 /* Skip past any prefixes. */
379 switch (base) {
380 case PM_INTEGER_BASE_BINARY:
381 start += 2; /* 0b */
382 break;
383 case PM_INTEGER_BASE_OCTAL:
384 start++; /* 0 */
385 if (*start == '_' || *start == 'o' || *start == 'O') start++; /* o */
386 break;
387 case PM_INTEGER_BASE_DECIMAL:
388 if (*start == '0' && (end - start) > 1) start += 2; /* 0d */
389 break;
390 case PM_INTEGER_BASE_HEXADECIMAL:
391 start += 2; /* 0x */
392 break;
393 }
394
395 pm_integer_parse_digits(arena, integer, (uint32_t) base, start, end);
396}
397
407void
408pm_integer_parse_rational(pm_arena_t *arena, pm_integer_t *numerator, pm_integer_t *denominator, const uint8_t *start, const uint8_t *end) {
409 static const uint32_t powof5[14] = { 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125 };
410
411 if (*start == '+') start++;
412
413 const uint8_t *point = memchr(start, '.', (size_t) (end - start));
414 PRISM_ASSERT(point != NULL);
415
416 /* Each trailing zero after the decimal point divides both sides by 10, so
417 * drop them before parsing. */
418 while (end > point + 1 && (end[-1] == '0' || end[-1] == '_')) end--;
419
420 uint32_t exponent = 0;
421 for (const uint8_t *cursor = point + 1; cursor < end; cursor++) {
422 if (*cursor != '_') exponent++;
423 }
424
425 pm_integer_parse_digits(arena, numerator, 10, start, end);
426 uint32_t twos = 0;
427 uint32_t fives = 0;
428
429 if (numerator->length > 0 && exponent > 0) {
430 uint32_t length = numerator->length;
431 pm_bignum_t bignum = {
432 .length = length,
433 .words = length <= 2 ? numerator->words.value : numerator->words.values
434 };
435
436 uint64_t trailing = pm_bignum_trailing_zeros(&bignum);
437 twos = trailing > exponent ? exponent : (uint32_t) trailing;
438 pm_bignum_shift_right(&bignum, twos);
439
440 /* 5**13 is the largest power of five that fits in a word, so divide by
441 * it while it divides evenly before dividing by five alone. */
442 while (exponent - fives >= 13 && pm_bignum_div_exact(&bignum, powof5[13])) fives += 13;
443 while (fives < exponent && pm_bignum_div_exact(&bignum, 5)) fives++;
444
445 if (length <= 2) {
446 *numerator = pm_integer_uint64(pm_bignum_uint64(&bignum));
447 } else {
448 pm_integer_from_bignum(arena, numerator, &bignum, length);
449 }
450 }
451
452 /* The denominator is what is left of 10**exponent. 2378/1024 is just above
453 * log2(5), so this capacity never undercounts. */
454 uint32_t remaining_fives = exponent - fives;
455 uint32_t remaining_twos = exponent - twos;
456 uint32_t capacity = (uint32_t) (((uint64_t) remaining_fives * 2378 / 1024 + remaining_twos + 32) / 32);
457
458 pm_bignum_t bignum = {
459 .length = 1,
460 .words = (uint32_t *) pm_arena_alloc(arena, sizeof(uint32_t) * capacity, PRISM_ALIGNOF(uint32_t))
461 };
462 bignum.words[0] = 1;
463
464 for (; remaining_fives >= 13; remaining_fives -= 13) pm_bignum_mul_add(&bignum, powof5[13], 0);
465 if (remaining_fives > 0) pm_bignum_mul_add(&bignum, powof5[remaining_fives], 0);
466 pm_bignum_shift_left(&bignum, remaining_twos);
467
468 PRISM_ASSERT(bignum.length <= capacity);
469 pm_integer_from_bignum(arena, denominator, &bignum, capacity);
470}
471
476static pm_bignum_t
477pm_integer_bignum(const pm_integer_t *integer) {
478 uint32_t length;
479 const uint32_t *words = pm_integer_words(integer, &length);
480 return (pm_bignum_t) { .length = length, .words = (uint32_t *) words };
481}
482
488int
489pm_integer_compare(const pm_integer_t *left, const pm_integer_t *right) {
490 if (left->negative != right->negative) return left->negative ? -1 : 1;
491 int negative = left->negative ? -1 : 1;
492
493 pm_bignum_t left_bignum = pm_integer_bignum(left);
494 pm_bignum_t right_bignum = pm_integer_bignum(right);
495 return pm_bignum_compare(&left_bignum, &right_bignum) * negative;
496}
497
511static PRISM_INLINE uint32_t
512pm_integer_string_words(uint32_t length) {
513 return (uint32_t) ((uint64_t) length * 1097 / 1024 + 2);
514}
515
526static void
527pm_integer_string_convert(pm_bignum_t *result, const uint32_t *words, uint32_t length, const pm_bignum_t *powers, pm_bignum_scratch_t *scratch) {
528 /* The low half of a split can have leading zero words. */
529 while (length > 0 && words[length - 1] == 0) length--;
530 uint32_t *saved = scratch->cursor;
531
532 if (length <= PM_INTEGER_STRING_LEAF) {
533 pm_bignum_t bignum = { .length = length, .words = pm_bignum_scratch_take(scratch, length) };
534 memcpy(bignum.words, words, sizeof(uint32_t) * length);
535
536 result->length = 0;
537 while (bignum.length > 0) result->words[result->length++] = pm_bignum_div(&bignum, PM_BIGNUM_DECIMAL_BASE);
538 } else {
539 uint32_t level = pm_bsrll((uint64_t) length - 1);
540 uint32_t split = (uint32_t) 1 << level;
541
542 pm_bignum_t high = { .length = 0, .words = pm_bignum_scratch_take(scratch, pm_integer_string_words(length - split)) };
543 pm_integer_string_convert(&high, words + split, length - split, powers, scratch);
544
545 PRISM_ASSERT(high.length + powers[level].length <= pm_integer_string_words(length));
546 pm_bignum_decimal_multiply(result, &high, &powers[level], scratch);
547 scratch->cursor = saved;
548
549 pm_bignum_t low = { .length = 0, .words = pm_bignum_scratch_take(scratch, pm_integer_string_words(split)) };
550 pm_integer_string_convert(&low, words, split, powers, scratch);
551 pm_bignum_decimal_add(result, &low);
552 }
553
554 scratch->cursor = saved;
555}
556
567static void
568pm_integer_string_divide(pm_buffer_t *buffer, const uint32_t *words, uint32_t length) {
569 uint32_t capacity = pm_integer_string_words(length);
570
571 /* The scratch space is about 13 times the number of words, which can
572 * exceed 32 bits, and on a 32-bit platform its size in bytes can exceed
573 * size_t. */
574 uint64_t scratch_size = 12 * (uint64_t) capacity + 1024;
575 if (scratch_size > SIZE_MAX / sizeof(uint32_t)) PRISM_OOM();
576
577 uint32_t *allocation = (uint32_t *) xmalloc(sizeof(uint32_t) * (size_t) scratch_size);
578 if (allocation == NULL) PRISM_OOM();
579 pm_bignum_scratch_t scratch = { .cursor = allocation, .end = allocation + (size_t) scratch_size };
580
581 pm_bignum_t result = { .length = 0, .words = pm_bignum_scratch_take(&scratch, capacity) };
582
583 /* powers[level] is 2**(32 * 2**level) in base 10**9, for every level a
584 * split uses. */
585 pm_bignum_t powers[64];
586 uint32_t level = 0;
587 powers[level].words = pm_bignum_scratch_take(&scratch, 2);
588 powers[level].words[0] = (uint32_t) (PM_BIGNUM_BINARY_BASE % PM_BIGNUM_DECIMAL_BASE);
589 powers[level].words[1] = (uint32_t) (PM_BIGNUM_BINARY_BASE / PM_BIGNUM_DECIMAL_BASE);
590 powers[level].length = 2;
591
592 for (uint32_t split = 2; split < length; split *= 2) {
593 const pm_bignum_t *previous = &powers[level++];
594 powers[level] = (pm_bignum_t) { .length = 0, .words = pm_bignum_scratch_take(&scratch, 2 * previous->length) };
595 pm_bignum_decimal_multiply(&powers[level], previous, previous, &scratch);
596 }
597
598 pm_integer_string_convert(&result, words, length, powers, &scratch);
599 PRISM_ASSERT(result.length > 0 && result.length < capacity);
600
601 /* Every word but the most significant is exactly nine digits, padded with
602 * zeros. */
603 pm_buffer_append_format(buffer, "%" PRIu32, result.words[result.length - 1]);
604
605 for (uint32_t index = result.length - 1; index > 0; index--) {
606 uint32_t word = result.words[index - 1];
607 char digits[9];
608
609 for (size_t digit = 9; digit > 0; digit--) {
610 digits[digit - 1] = (char) ('0' + word % 10);
611 word /= 10;
612 }
613
614 pm_buffer_append_string(buffer, digits, 9);
615 }
616
617 xfree_sized(allocation, sizeof(uint32_t) * (size_t) scratch_size);
618}
619
623void
624pm_integer_string(pm_buffer_t *buffer, const pm_integer_t *integer) {
625 if (integer->negative) {
626 pm_buffer_append_byte(buffer, '-');
627 }
628
629 /* An integer whose words are inline fits in a uint64_t, so it can be
630 * appended directly. */
631 if (integer->length <= 2) {
632 pm_buffer_append_format(buffer, "%" PRIu64, pm_integer_uint64_value(integer));
633 return;
634 }
635
636 if (integer->length > PM_INTEGER_STRING_THRESHOLD) {
637 pm_integer_string_divide(buffer, integer->words.values, integer->length);
638 return;
639 }
640
641 /* Dividing by 10**9 yields the next nine digits from the remainder, least
642 * significant first, so the digits are written from the end of the buffer
643 * toward the front. The division is destructive, so it works on a copy. */
644 const size_t words_size = sizeof(uint32_t) * integer->length;
645
646 /* A number of n words has at most n * 32 * log10(2) + 1 decimal digits,
647 * which is at most n * 10 for the three or more words that reach here. */
648 const size_t capacity = (size_t) integer->length * 10;
649
650 /* The copy of the words and the digits share one allocation, with the
651 * words first so that they are aligned. */
652 void *allocation = xmalloc(words_size + capacity);
653 if (allocation == NULL) PRISM_OOM();
654
655 pm_bignum_t bignum = { .length = integer->length, .words = (uint32_t *) allocation };
656 memcpy(bignum.words, integer->words.values, words_size);
657
658 char *digits = (char *) allocation + words_size;
659 size_t offset = capacity;
660
661 while (bignum.length > 0) {
662 uint32_t remainder = pm_bignum_div(&bignum, PM_BIGNUM_DECIMAL_BASE);
663
664 /* Every chunk but the most significant is exactly nine digits, padded
665 * with zeros. The most significant chunk is nonzero and stops at its
666 * leading digit. */
667 for (size_t index = 0; index < 9 && (bignum.length > 0 || remainder > 0); index++) {
668 digits[--offset] = (char) ('0' + remainder % 10);
669 remainder /= 10;
670 }
671 }
672
673 pm_buffer_append_string(buffer, digits + offset, capacity - offset);
674 xfree_sized(allocation, words_size + capacity);
675}
#define PRISM_ALIGNOF
Get the alignment requirement of a type.
Definition align.h:15
#define xmalloc
Old name of ruby_xmalloc.
Definition xmalloc.h:53
#define PRISM_INLINE
Old Visual Studio versions do not support the inline keyword, so we need to define it to be __inline.
Definition inline.h:12
static PRISM_INLINE uint64_t pm_integer_uint64_value(const pm_integer_t *integer)
Return the magnitude of an integer whose length is at most 2, which always fits in a uint64_t.
Definition integer.h:75
static PRISM_INLINE const uint32_t * pm_integer_words(const pm_integer_t *integer, uint32_t *length)
Return the words of an integer, least significant first.
Definition integer.h:57
C99 shim for <stdbool.h>
A structure represents an arbitrary-sized integer.
Definition integer.h:19
uint32_t length
The number of words in the magnitude, with no leading zero words.
Definition integer.h:24
union pm_integer_t::@107 words
The words of the magnitude.
uint32_t * values
The words of an integer whose length is greater than 2.
Definition integer.h:45
bool negative
Whether or not the integer is negative.
Definition integer.h:29
uint32_t value[2]
The words of an integer whose length is at most 2.
Definition integer.h:40