aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--BigInt.c138
1 files 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;
}
generated by cgit v1.2.3 (git 2.46.0) at 2026-07-14 22:04:39 +0000