From 72f791227cf3f0e835e62ff22953c005a40882c6 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Sun, 17 May 2026 17:57:57 +0300 Subject: feat(BigInt): Implement create/free and summation, subtraction --- BigInt.c | 313 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ BigInt.h | 32 +++++++ 2 files changed, 345 insertions(+) create mode 100644 BigInt.c create mode 100644 BigInt.h diff --git a/BigInt.c b/BigInt.c new file mode 100644 index 0000000..b9239d7 --- /dev/null +++ b/BigInt.c @@ -0,0 +1,313 @@ +#include "BigInt.h" +#include "MemoryManager.h" +#include "Types.h" +#include + +typedef uint_fast32_t UWord; +#define UWORD_MAX UINT_FAST32_MAX + +/** Metadata **/ + +struct BigIntMeta { + MemoryManager *mm; + usize words; +}; + +static inline struct BigIntMeta* +B_metadata(BigInt s) { +return (struct BigIntMeta*)(s - sizeof(struct BigIntMeta)); +} + +/** Helpers **/ + +static inline void* +B_start(MemoryManager *mm, usize words) { + if (NULL == mm) + return NULL; + + struct BigIntMeta bim = { + .mm = mm, + .words = words, + }; + + void* start = NULL; + if (R_Ok != mm->alloc(*mm, &start, sizeof(bim) + bim.words * sizeof(UWord)) || + NULL == start) + { + return NULL; + } + + memcpy(start, &bim, sizeof(bim)); + return start + sizeof(bim); +} + +static inline Result +B_resize(BigInt *x) { + struct BigIntMeta *bim = B_metadata(*x); + + void *start = bim; + RETURN_NOTOK( + bim->mm->realloc(*bim->mm, &start, sizeof(*bim) + (bim->words << 1) * sizeof(UWord))); + + bim = start; + *x = start + sizeof(struct BigIntMeta); + bim->words <<= 1; + + return R_Ok; +} + +/** Create **/ + +BigInt +B_new(MemoryManager *mm, int value) { + UWord *start = B_start(mm, 1); + + if (NULL != start) + memcpy(start, &value, sizeof(value)); + + return start; +} + +BigInt +B_newstr(MemoryManager *mm, const char* str) { + return NULL; +} + +BigInt +B_dup(MemoryManager *mm, BigInt bigint) { + if (NULL == bigint) + return NULL; + + struct BigIntMeta *bim = B_metadata(bigint); + + void *start = B_start(mm, bim->words); + + if (NULL != start) + memcpy(start, bigint, bim->words * sizeof(UWord)); + + return start; +} + +BigInt +B_newsum(MemoryManager *mm, BigInt a, BigInt b) { + BigInt total = B_dup(mm, a); + + if (NULL == total || + R_Ok != B_sum(&total, b)) + { + return NULL; + } + + return total; +} + +BigInt +B_newsub(MemoryManager *mm, BigInt a, BigInt b) { + BigInt total = B_dup(mm, a); + + if (NULL == total || + R_Ok != B_sub(&total, b)) + { + return NULL; + } + + return total; +} + +/* Free */ + +Result +B_free(BigInt *bigint) { + if (NULL == bigint || NULL == *bigint) + return R_NullArgument; + + struct BigIntMeta *start = B_metadata(*bigint); + *bigint = (BigInt*)start; + return start->mm->free(*start->mm, (void*)bigint); +} + +/* Modify */ + +Result +B_sum(BigInt *inta, BigInt intb) { + if (NULL == inta || NULL == intb || NULL == *inta) + return R_NullArgument; + + struct BigIntMeta *am = B_metadata(*inta), *bm = B_metadata(intb); + UWord *a = *inta, *b = intb; + + int overflow = 0; + usize w; + for (w = 0; w < bm->words; ++w) { + if (w >= am->words) + B_resize(inta); + + if (!(overflow && a[w] > UWORD_MAX - 1)) { + if (overflow) + ++a[w]; + overflow = a[w] > UWORD_MAX - b[w]; + } + + a[w] += b[w]; + } + + if (overflow) { + if (w >= am->words) { + RETURN_NOTOK(B_resize(inta)); + a = *inta; + } + ++a[w]; + } + + return R_Ok; +} + +Result +B_sub(BigInt *inta, BigInt intb) { + if (NULL == inta || NULL == intb || NULL == *inta) + return R_NullArgument; + + struct BigIntMeta *am = B_metadata(*inta), *bm = B_metadata(intb); + UWord *a = *inta, *b = intb; + + int underflow = 0; + usize w; + for (w = 0; w < bm->words; ++w) { + if (w >= am->words) + B_resize(inta); + + if (!(underflow && a[w] < 0 + 1)) { + if (underflow) + --a[w]; + underflow = a[w] < 0 + b[w]; + } + + a[w] -= b[w]; + } + + if (underflow) { + if (w >= am->words) { + RETURN_NOTOK(B_resize(inta)); + a = *inta; + } + --a[w]; + } + + return R_Ok; +} + +/* Get */ + +usize +B_bytes(BigInt x) { + if (NULL == x) + return 0; + return B_metadata(x)->words * sizeof(UWord); +} + +usize +B_bitwidth(BigInt intx) { + if (NULL == intx) + return 0; + + struct BigIntMeta *bim = B_metadata(intx); + UWord *x = intx; + + for (usize w = bim->words - 1; w < bim->words; --w) { + if (x[w] == 0) continue; + + // TODO: use faster search than linear + usize width = sizeof(UWord) * 8 * (w + 1); + for (UWord mask = (UWord)1 << (sizeof(UWord) * 8 - 1); mask > 0; mask >>= 1, --width) { + if (x[w] & mask) + return width; + } + } + + return 0; +} + +char* +B_tostr(MemoryManager *mm, BigInt intx) { + if (NULL == intx) + return NULL; + + struct BigIntMeta *bim = B_metadata(intx); + UWord *x = intx; + + usize n = B_bitwidth(intx); + + if (0 == n) { + char *str = NULL; + if (R_Ok != mm->alloc(*mm, (void**)&str, sizeof(char) * 2)) + return NULL; + + str[0] = '0'; + str[1] = '\0'; + return str; + } + + // TODO: these calculations are based on Wikipedia's statement that + // "4 x ceil(n / 3)" is enough bits of memory. + // This is true, but it grows faster than needed, so from 31 bits onward, + // we use too much memory (adding unnecessary leading 0s). + // The exact value is "ceil(log10(2^x - 1))" + usize bcd_bytes = 1 + (n - 1) / 6; + int odd_nibbles = (1 + (n - 1) / 3) % 2; + + char *str; + if (R_Ok != mm->alloc(*mm, (void**)&str, sizeof(char) * (bcd_bytes * 2 - odd_nibbles + 1))) + return NULL; + + u8 *bcd; + if (R_Ok != mm->alloc(*mm, (void**)&bcd, sizeof(u8) * bcd_bytes)) { + mm->free(*mm, (void**)&str); + return NULL; + } + memset(bcd, 0, sizeof(u8) * bcd_bytes); + + UWord mask = (UWord)1 << (sizeof(UWord) * 8 - 1); + + // Double-dable, binary to binary-coded decimal + for (usize w = bim->words - 1; w < bim->words; --w) { + for (UWord m = mask; m != 0; m >>= 1) { + // Incrementing values >=5 by 3 + for (usize b = 0; b < bcd_bytes; ++b) { + // Upper nibble + if ((bcd[b] & 0b11110000) >= 0b01010000) + bcd[b] += 0b00110000; + // Lower nibble + if ((bcd[b] & 0b00001111) >= 5) + bcd[b] += 3; + } + + // Left shift all bits in bcd + u8 carry = 0, next_carry = 0; + for (usize b = 0; b < bcd_bytes; ++b) { + next_carry = !!(bcd[b] & 0b10000000); + bcd[b] <<= 1; + bcd[b] |= carry; + carry = next_carry; + } + + // Place leading bit in x into bcd + bcd[0] |= !!(x[w] & m); + } + } + + // BCD to char string + char *s = str; + + if (!odd_nibbles) + *(s++) = ((bcd[bcd_bytes - 1] & 0b11110000) >> 4) + '0'; + *(s++) = (bcd[bcd_bytes - 1] & 0b00001111) + '0'; + + for (usize b = bcd_bytes - 2; b < bcd_bytes; --b) { + *(s++) = ((bcd[b] & 0b11110000) >> 4) + '0'; + *(s++) = (bcd[b] & 0b00001111) + '0'; + } + *s = '\0'; + + mm->free(*mm, (void**)&bcd); + return str; +} diff --git a/BigInt.h b/BigInt.h new file mode 100644 index 0000000..2324143 --- /dev/null +++ b/BigInt.h @@ -0,0 +1,32 @@ +#ifndef _BIGINT +#define _BIGINT + +#include "MemoryManager.h" + +typedef void* BigInt; + +/* Create */ + +BigInt B_new(MemoryManager *mm, int value); +BigInt B_newstr(MemoryManager *mm, const char* str); +BigInt B_dup(MemoryManager *mm, BigInt bigint); + +BigInt B_newsum(MemoryManager *mm, BigInt a, BigInt b); +BigInt B_newsub(MemoryManager *mm, BigInt a, BigInt b); + +/* Free */ + +Result B_free(BigInt *bigint); + +/* Modify */ + +Result B_sum(BigInt *a, BigInt b); +Result B_sub(BigInt *a, BigInt b); + +/* Get */ + +usize B_bytes(BigInt x); +usize B_bitwidth(BigInt x); +char* B_tostr(MemoryManager *mm, BigInt x); + +#endif /* _BIGINT */ -- cgit v1.2.3