From be67821d6fddfa97abb91188c6ef8799bff15c74 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 28 May 2026 14:03:16 +0300 Subject: feat: Correct resize logic --- BigInt.c | 138 +++++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 95 insertions(+), 43 deletions(-) diff --git a/BigInt.c b/BigInt.c index a1a617c..21c22d3 100644 --- a/BigInt.c +++ b/BigInt.c @@ -14,6 +14,7 @@ typedef uint_fast32_t UWord; struct BigIntMeta { MemoryManager *mm; usize words; + int resizeable; }; static inline struct BigIntMeta* @@ -31,6 +32,7 @@ B_start(MemoryManager *mm, usize words) { struct BigIntMeta bim = { .mm = mm, .words = words, + .resizeable = 1, }; void* start = NULL; @@ -45,16 +47,16 @@ B_start(MemoryManager *mm, usize words) { } static inline Result -B_resize(BigInt *x) { +B_resize(BigInt *x, usize words) { 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->mm->realloc(*bim->mm, &start, sizeof(*bim) + words * sizeof(UWord))); bim = start; *x = start + sizeof(struct BigIntMeta); - bim->words <<= 1; + bim->words = words; return R_Ok; } @@ -185,15 +187,19 @@ B_sum(BigInt *inta, BigInt intb) { return R_NullArgument; struct BigIntMeta *am = B_metadata(*inta), *bm = B_metadata(intb); + + if (am->resizeable && am->words < bm->words) { + RETURN_NOTOK(B_resize(inta, bm->words)); + am = B_metadata(*inta); + } + UWord *a = *inta, *b = intb; int overflow = 0; - usize w; - for (w = 0; w < bm->words; ++w) { - if (w >= am->words) - B_resize(inta); + usize words = am->words < bm->words ? am->words : bm->words; - if (!(overflow && a[w] > UWORD_MAX - 1)) { + for (usize w = 0; w < words; ++w) { + if (!(overflow && a[w] == UWORD_MAX)) { if (overflow) ++a[w]; overflow = a[w] > UWORD_MAX - b[w]; @@ -203,11 +209,17 @@ B_sum(BigInt *inta, BigInt intb) { } if (overflow) { - if (w >= am->words) { - RETURN_NOTOK(B_resize(inta)); + if (am->words > words) { + for (usize w = words; w < am->words && overflow; ++w) { + overflow = a[w] == UWORD_MAX; + ++a[w]; + } + } + else if (am->resizeable) { + RETURN_NOTOK(B_resize(inta, am->words << 1)); a = *inta; + ++a[words]; } - ++a[w]; } return R_Ok; @@ -219,29 +231,39 @@ B_sub(BigInt *inta, BigInt intb) { return R_NullArgument; struct BigIntMeta *am = B_metadata(*inta), *bm = B_metadata(intb); + + if (am->resizeable && am->words < bm->words) { + RETURN_NOTOK(B_resize(inta, bm->words)); + am = B_metadata(*inta); + } + UWord *a = *inta, *b = intb; int underflow = 0; - usize w; - for (w = 0; w < bm->words; ++w) { - if (w >= am->words) - B_resize(inta); + usize words = am->words < bm->words ? am->words : bm->words; - if (!(underflow && a[w] < 0 + 1)) { + for (usize w = 0; w < words; ++w) { + if (!(underflow && a[w] == 0)) { if (underflow) --a[w]; - underflow = a[w] < 0 + b[w]; + underflow = a[w] < b[w]; } a[w] -= b[w]; } if (underflow) { - if (w >= am->words) { - RETURN_NOTOK(B_resize(inta)); + if (am->words > words) { + for (usize w = words; w < am->words && underflow; ++w) { + underflow = a[w] == 0; + --a[w]; + } + } + else if (am->resizeable) { + RETURN_NOTOK(B_resize(inta, am->words << 1)); a = *inta; + --a[words]; } - --a[w]; } return R_Ok; @@ -255,8 +277,8 @@ B_compl(BigInt *intx) { struct BigIntMeta *xm = B_metadata(intx); UWord *x = (void*)intx; - for (usize i = 0; i < xm->words; ++i) - x[i] = ~x[i]; + for (usize w = 0; w < xm->words; ++w) + x[w] = ~x[w]; return R_Ok; } @@ -267,11 +289,18 @@ B_bitand(BigInt *intx, BigInt *inty) { return R_NullArgument; struct BigIntMeta *xm = B_metadata(intx), *ym = B_metadata(inty); + + if (xm->resizeable && xm->words < ym->words) { + RETURN_NOTOK(B_resize(intx, ym->words)); + xm = B_metadata(intx); + } + UWord *x = (void*)intx, *y = (void*)inty; - usize size = xm->words < ym->words ? xm->words : ym->words; - for (usize i = 0; i < size; ++i) - x[i] &= y[i]; + usize words = xm->words < ym->words ? xm->words : ym->words; + + for (usize w = 0; w < words; ++w) + x[w] &= y[w]; return R_Ok; } @@ -282,11 +311,18 @@ B_bitor(BigInt *intx, BigInt *inty) { return R_NullArgument; struct BigIntMeta *xm = B_metadata(intx), *ym = B_metadata(inty); + + if (xm->resizeable && xm->words < ym->words) { + RETURN_NOTOK(B_resize(intx, ym->words)); + xm = B_metadata(intx); + } + UWord *x = (void*)intx, *y = (void*)inty; - usize size = xm->words < ym->words ? xm->words : ym->words; - for (usize i = 0; i < size; ++i) - x[i] |= y[i]; + usize words = xm->words < ym->words ? xm->words : ym->words; + + for (usize w = 0; w < words; ++w) + x[w] |= y[w]; return R_Ok; } @@ -297,11 +333,18 @@ B_bitxor(BigInt *intx, BigInt *inty) { return R_NullArgument; struct BigIntMeta *xm = B_metadata(intx), *ym = B_metadata(inty); + + if (xm->resizeable && xm->words < ym->words) { + RETURN_NOTOK(B_resize(intx, ym->words)); + xm = B_metadata(intx); + } + UWord *x = (void*)intx, *y = (void*)inty; - usize size = xm->words < ym->words ? xm->words : ym->words; - for (usize i = 0; i < size; ++i) - x[i] ^= y[i]; + usize words = xm->words < ym->words ? xm->words : ym->words; + + for (usize w = 0; w < words; ++w) + x[w] ^= y[w]; return R_Ok; } @@ -314,22 +357,22 @@ B_rshift(BigInt *intx, usize shift) { if (shift == 0) return R_Ok; - struct BigIntMeta *bim = B_metadata(*intx); + struct BigIntMeta *xm = B_metadata(*intx); UWord *x = *intx; usize word_moves = shift / UWORD_BIT; if (word_moves) { usize w = 0; - for (; w < bim->words - word_moves; ++w) + for (; w < xm->words - word_moves; ++w) x[w] = x[w + word_moves]; - for (; w < bim->words; ++w) + for (; w < xm->words; ++w) x[w] = 0; } usize bit_moves = shift % UWORD_BIT; if (bit_moves == 1) { x[0] >>= 1; - for (usize w = 1; w < bim->words; ++w) { + for (usize w = 1; w < xm->words; ++w) { x[w - 1] |= (x[w] & 1) << (UWORD_BIT - 1); x[w] >>= 1; } @@ -338,7 +381,7 @@ B_rshift(BigInt *intx, usize shift) { UWord mask = ((UWord)1 << bit_moves) - 1; x[0] >>= bit_moves; - for (usize w = 1; w < bim->words; ++w) { + for (usize w = 1; w < xm->words; ++w) { x[w - 1] |= (x[w] & mask) << (UWORD_BIT - bit_moves); x[w] >>= bit_moves; } @@ -355,15 +398,24 @@ B_lshift(BigInt *intx, usize shift) { if (shift == 0) return R_Ok; - struct BigIntMeta *bim = B_metadata(*intx); + struct BigIntMeta *xm = B_metadata(*intx); + + if (xm->resizeable) { + UWord width = B_bitwidth(*intx); + if (width + shift > xm->words * UWORD_BIT) { + RETURN_NOTOK(B_resize(intx, (width + shift - 1) / UWORD_BIT + 1)); + xm = B_metadata(*intx); + } + } + UWord *x = *intx; usize word_moves = shift / UWORD_BIT; if (word_moves) { - usize w = bim->words - 1; + usize w = xm->words - 1; for (; w >= word_moves; --w) x[w] = x[w - word_moves]; - for (; w < bim->words; --w) + for (; w < xm->words; --w) x[w] = 0; } @@ -371,8 +423,8 @@ B_lshift(BigInt *intx, usize shift) { if (bit_moves == 1) { UWord mask = (UWord)1 << (UWORD_BIT - 1); - x[bim->words - 1] <<= 1; - for (usize w = bim->words - 2; w < bim->words; --w) { + x[xm->words - 1] <<= 1; + for (usize w = xm->words - 2; w < xm->words; --w) { x[w + 1] |= (x[w] & mask) >> (UWORD_BIT - 1); x[w] <<= 1; } @@ -380,8 +432,8 @@ B_lshift(BigInt *intx, usize shift) { else if (bit_moves > 1) { UWord mask = (((UWord)1 << bit_moves) - 1) << (UWORD_BIT - bit_moves); - x[bim->words - 1] <<= bit_moves; - for (usize w = bim->words - 2; w < bim->words; --w) { + x[xm->words - 1] <<= bit_moves; + for (usize w = xm->words - 2; w < xm->words; --w) { x[w + 1] |= (x[w] & mask) >> (UWORD_BIT - bit_moves); x[w] <<= bit_moves; } -- cgit v1.2.3