1#include "prism/internal/integer.h"
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"
30#define PM_INTEGER_DIVIDE_THRESHOLD 224
39#define PM_INTEGER_STRING_THRESHOLD 48
47#define PM_INTEGER_STRING_LEAF 8
52static const int8_t pm_integer_parse_digit_values[256] = {
54 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
55 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
56 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
57 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,
58 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
59 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
60 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,
61 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
62 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
63 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
64 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
65 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
66 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
67 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
68 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
69 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
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");
80 return (uint8_t) value;
89pm_integer_separator(uint8_t character) {
90 return character ==
'_' || character ==
'.';
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);
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));
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)];
121 uint32_t bit = (uint32_t) pm_ctzll(base);
122 PRISM_ASSERT(bit >= 1 && bit <= 4);
124 uint32_t length = (uint32_t) (((uint64_t) (digits - 1) * bit + leading_bits + 31) / 32);
125 PRISM_ASSERT(length > 2);
127 uint32_t *words = pm_arena_zalloc(arena,
sizeof(uint32_t) * length,
PRISM_ALIGNOF(uint32_t));
128 uint64_t bit_position = 0;
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);
134 uint32_t index = (uint32_t) (bit_position / 32);
135 uint32_t shift = (uint32_t) (bit_position % 32);
137 words[index] |= value << shift;
138 if (32 - shift < bit && index + 1 < length) words[index + 1] |= value >> (32 - shift);
157pm_integer_decimal_words(uint64_t digits) {
158 return (uint32_t) ((digits * 3402 / 1024) / 32 + 1);
170pm_integer_chunks_words(uint32_t nchunks) {
171 return pm_integer_decimal_words((uint64_t) nchunks * 9) + 1;
181 if (nchunks <= PM_INTEGER_DIVIDE_THRESHOLD) {
183 for (uint32_t index = nchunks; index > 0; index--) pm_bignum_mul_add(result, PM_BIGNUM_DECIMAL_BASE, chunks[index - 1]);
185 uint32_t level = pm_bsrll((uint64_t) nchunks - 1);
186 uint32_t split = (uint32_t) 1 << level;
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);
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;
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;
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);
220 .words = (uint32_t *) pm_arena_alloc(arena,
sizeof(uint32_t) * capacity,
PRISM_ALIGNOF(uint32_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();
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 };
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;
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);
246 if (++chunk_digits == chunk_size) {
247 chunks[--chunk_index] = chunk;
253 PRISM_ASSERT(chunk_index == 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;
262 for (uint32_t split = 2; split < nchunks; split *= 2) {
264 powers[level].words = pm_bignum_scratch_take(&scratch, 2 * previous->length);
265 pm_bignum_multiply(&powers[level], previous, previous, &scratch);
268 pm_integer_parse_decimal_divide_chunks(&result, nchunks, chunks, powers, &scratch);
269 xfree_sized(allocation,
sizeof(uint32_t) * (
size_t) scratch_size);
271 PRISM_ASSERT(result.length > 2 && result.length <= capacity);
272 pm_integer_from_bignum(arena, integer, &result, capacity);
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 };
288 uint32_t capacity = pm_integer_decimal_words(digits);
291 .words = (uint32_t *) pm_arena_alloc(arena,
sizeof(uint32_t) * capacity,
PRISM_ALIGNOF(uint32_t))
294 uint32_t chunk_size = digits % 9 == 0 ? 9 : digits % 9;
295 uint32_t chunk_digits = 0;
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);
302 if (++chunk_digits == chunk_size) {
303 pm_bignum_mul_add(&bignum, powof10[chunk_size], chunk);
311 PRISM_ASSERT(bignum.length > 2 && bignum.length <= capacity);
312 pm_integer_from_bignum(arena, integer, &bignum, capacity);
319pm_integer_parse_digits(
pm_arena_t *arena,
pm_integer_t *integer, uint32_t base,
const uint8_t *start,
const uint8_t *end) {
322 while (start < end && (*start ==
'0' || pm_integer_separator(*start))) start++;
334 const uint64_t limit = UINT64_MAX / base;
335 const uint64_t limit_digit = UINT64_MAX % base;
337 const uint8_t *cursor = start;
338 uint64_t value = (uint64_t) pm_integer_parse_digit(*cursor++);
340 for (; cursor < end; cursor++) {
341 if (pm_integer_separator(*cursor))
continue;
342 uint64_t digit = (uint64_t) pm_integer_parse_digit(*cursor);
344 if (value > limit || (value == limit && digit > limit_digit)) {
346 for (
const uint8_t *scan = start; scan < end; scan++) {
347 if (!pm_integer_separator(*scan)) digits++;
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);
355 pm_integer_parse_decimal_schoolbook(arena, integer, digits, start, end);
361 value = value * base + digit;
364 *integer = pm_integer_uint64(value);
373pm_integer_parse(
pm_arena_t *arena,
pm_integer_t *integer, pm_integer_base_t base,
const uint8_t *start,
const uint8_t *end) {
376 if (*start ==
'+') start++;
380 case PM_INTEGER_BASE_BINARY:
383 case PM_INTEGER_BASE_OCTAL:
385 if (*start ==
'_' || *start ==
'o' || *start ==
'O') start++;
387 case PM_INTEGER_BASE_DECIMAL:
388 if (*start ==
'0' && (end - start) > 1) start += 2;
390 case PM_INTEGER_BASE_HEXADECIMAL:
395 pm_integer_parse_digits(arena, integer, (uint32_t) base, start, end);
409 static const uint32_t powof5[14] = { 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125 };
411 if (*start ==
'+') start++;
413 const uint8_t *point = memchr(start,
'.', (
size_t) (end - start));
414 PRISM_ASSERT(point != NULL);
418 while (end > point + 1 && (end[-1] ==
'0' || end[-1] ==
'_')) end--;
420 uint32_t exponent = 0;
421 for (
const uint8_t *cursor = point + 1; cursor < end; cursor++) {
422 if (*cursor !=
'_') exponent++;
425 pm_integer_parse_digits(arena, numerator, 10, start, end);
429 if (numerator->
length > 0 && exponent > 0) {
430 uint32_t length = numerator->
length;
436 uint64_t trailing = pm_bignum_trailing_zeros(&bignum);
437 twos = trailing > exponent ? exponent : (uint32_t) trailing;
438 pm_bignum_shift_right(&bignum, twos);
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++;
446 *numerator = pm_integer_uint64(pm_bignum_uint64(&bignum));
448 pm_integer_from_bignum(arena, numerator, &bignum, length);
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);
460 .words = (uint32_t *) pm_arena_alloc(arena,
sizeof(uint32_t) * capacity,
PRISM_ALIGNOF(uint32_t))
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);
468 PRISM_ASSERT(bignum.length <= capacity);
469 pm_integer_from_bignum(arena, denominator, &bignum, capacity);
480 return (
pm_bignum_t) { .length = length, .words = (uint32_t *) words };
491 int negative = left->
negative ? -1 : 1;
494 pm_bignum_t right_bignum = pm_integer_bignum(right);
495 return pm_bignum_compare(&left_bignum, &right_bignum) * negative;
512pm_integer_string_words(uint32_t length) {
513 return (uint32_t) ((uint64_t) length * 1097 / 1024 + 2);
529 while (length > 0 && words[length - 1] == 0) length--;
530 uint32_t *saved = scratch->cursor;
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);
537 while (bignum.length > 0) result->words[result->length++] = pm_bignum_div(&bignum, PM_BIGNUM_DECIMAL_BASE);
539 uint32_t level = pm_bsrll((uint64_t) length - 1);
540 uint32_t split = (uint32_t) 1 << level;
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);
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;
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);
554 scratch->cursor = saved;
568pm_integer_string_divide(
pm_buffer_t *buffer,
const uint32_t *words, uint32_t length) {
569 uint32_t capacity = pm_integer_string_words(length);
574 uint64_t scratch_size = 12 * (uint64_t) capacity + 1024;
575 if (scratch_size > SIZE_MAX /
sizeof(uint32_t)) PRISM_OOM();
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 };
581 pm_bignum_t result = { .length = 0, .words = pm_bignum_scratch_take(&scratch, capacity) };
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;
592 for (uint32_t split = 2; split < length; split *= 2) {
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);
598 pm_integer_string_convert(&result, words, length, powers, &scratch);
599 PRISM_ASSERT(result.length > 0 && result.length < capacity);
603 pm_buffer_append_format(buffer,
"%" PRIu32, result.words[result.length - 1]);
605 for (uint32_t index = result.length - 1; index > 0; index--) {
606 uint32_t word = result.words[index - 1];
609 for (
size_t digit = 9; digit > 0; digit--) {
610 digits[digit - 1] = (char) (
'0' + word % 10);
614 pm_buffer_append_string(buffer, digits, 9);
617 xfree_sized(allocation,
sizeof(uint32_t) * (
size_t) scratch_size);
626 pm_buffer_append_byte(buffer,
'-');
631 if (integer->
length <= 2) {
636 if (integer->
length > PM_INTEGER_STRING_THRESHOLD) {
644 const size_t words_size =
sizeof(uint32_t) * integer->
length;
648 const size_t capacity = (size_t) integer->
length * 10;
652 void *allocation =
xmalloc(words_size + capacity);
653 if (allocation == NULL) PRISM_OOM();
655 pm_bignum_t bignum = { .length = integer->
length, .words = (uint32_t *) allocation };
656 memcpy(bignum.words, integer->
words.
values, words_size);
658 char *digits = (
char *) allocation + words_size;
659 size_t offset = capacity;
661 while (bignum.length > 0) {
662 uint32_t remainder = pm_bignum_div(&bignum, PM_BIGNUM_DECIMAL_BASE);
667 for (
size_t index = 0; index < 9 && (bignum.length > 0 || remainder > 0); index++) {
668 digits[--offset] = (char) (
'0' + remainder % 10);
673 pm_buffer_append_string(buffer, digits + offset, capacity - offset);
674 xfree_sized(allocation, words_size + capacity);
#define PRISM_ALIGNOF
Get the alignment requirement of a type.
#define xmalloc
Old name of ruby_xmalloc.
#define PRISM_INLINE
Old Visual Studio versions do not support the inline keyword, so we need to define it to be __inline.
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.
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.
A structure represents an arbitrary-sized integer.
uint32_t length
The number of words in the magnitude, with no leading zero words.
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.
bool negative
Whether or not the integer is negative.
uint32_t value[2]
The words of an integer whose length is at most 2.