aboutsummaryrefslogtreecommitdiff
path: root/core/math/big/internal.odin
diff options
context:
space:
mode:
authorgingerBill <bill@gingerbill.org>2021-08-31 22:21:13 +0100
committergingerBill <bill@gingerbill.org>2021-08-31 22:21:13 +0100
commit251da264ed6e0f039931683c7b0d4b97e88c8d99 (patch)
treec7a9a088477d2452c2cf850458c62d994a211df6 /core/math/big/internal.odin
parentb176af27427a6c39448a71a8023e4a9877f0a51c (diff)
Remove unneeded semicolons from the core library
Diffstat (limited to 'core/math/big/internal.odin')
-rw-r--r--core/math/big/internal.odin1438
1 files changed, 719 insertions, 719 deletions
diff --git a/core/math/big/internal.odin b/core/math/big/internal.odin
index 9422067ae..033bc11a2 100644
--- a/core/math/big/internal.odin
+++ b/core/math/big/internal.odin
@@ -43,43 +43,43 @@ import rnd "core:math/rand"
`dest`, `a` and `b` != `nil` and have been initalized.
*/
internal_int_add_unsigned :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
- dest := dest; x := a; y := b;
- context.allocator = allocator;
+ dest := dest; x := a; y := b
+ context.allocator = allocator
- old_used, min_used, max_used, i: int;
+ old_used, min_used, max_used, i: int
if x.used < y.used {
- x, y = y, x;
+ x, y = y, x
}
- min_used = y.used;
- max_used = x.used;
- old_used = dest.used;
+ min_used = y.used
+ max_used = x.used
+ old_used = dest.used
- internal_grow(dest, max(max_used + 1, _DEFAULT_DIGIT_COUNT)) or_return;
- dest.used = max_used + 1;
+ internal_grow(dest, max(max_used + 1, _DEFAULT_DIGIT_COUNT)) or_return
+ dest.used = max_used + 1
/*
All parameters have been initialized.
*/
/* Zero the carry */
- carry := DIGIT(0);
+ carry := DIGIT(0)
#no_bounds_check for i = 0; i < min_used; i += 1 {
/*
Compute the sum one _DIGIT at a time.
dest[i] = a[i] + b[i] + carry;
*/
- dest.digit[i] = x.digit[i] + y.digit[i] + carry;
+ dest.digit[i] = x.digit[i] + y.digit[i] + carry
/*
Compute carry
*/
- carry = dest.digit[i] >> _DIGIT_BITS;
+ carry = dest.digit[i] >> _DIGIT_BITS
/*
Mask away carry from result digit.
*/
- dest.digit[i] &= _MASK;
+ dest.digit[i] &= _MASK
}
if min_used != max_used {
@@ -88,32 +88,32 @@ internal_int_add_unsigned :: proc(dest, a, b: ^Int, allocator := context.allocat
If A or B has more digits, add those in.
*/
#no_bounds_check for ; i < max_used; i += 1 {
- dest.digit[i] = x.digit[i] + carry;
+ dest.digit[i] = x.digit[i] + carry
/*
Compute carry
*/
- carry = dest.digit[i] >> _DIGIT_BITS;
+ carry = dest.digit[i] >> _DIGIT_BITS
/*
Mask away carry from result digit.
*/
- dest.digit[i] &= _MASK;
+ dest.digit[i] &= _MASK
}
}
/*
Add remaining carry.
*/
- dest.digit[i] = carry;
+ dest.digit[i] = carry
/*
Zero remainder.
*/
- internal_zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used)
/*
Adjust dest.used based on leading zeroes.
*/
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
-internal_add_unsigned :: proc { internal_int_add_unsigned, };
+internal_add_unsigned :: proc { internal_int_add_unsigned, }
/*
Low-level addition, signed. Handbook of Applied Cryptography, algorithm 14.7.
@@ -122,14 +122,14 @@ internal_add_unsigned :: proc { internal_int_add_unsigned, };
`dest`, `a` and `b` != `nil` and have been initalized.
*/
internal_int_add_signed :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
- x := a; y := b;
- context.allocator = allocator;
+ x := a; y := b
+ context.allocator = allocator
/*
Handle both negative or both positive.
*/
if x.sign == y.sign {
- dest.sign = x.sign;
- return #force_inline internal_int_add_unsigned(dest, x, y);
+ dest.sign = x.sign
+ return #force_inline internal_int_add_unsigned(dest, x, y)
}
/*
@@ -138,13 +138,13 @@ internal_int_add_signed :: proc(dest, a, b: ^Int, allocator := context.allocator
The result gets the sign of the one with the greater magnitude.
*/
if #force_inline internal_cmp_mag(a, b) == -1 {
- x, y = y, x;
+ x, y = y, x
}
- dest.sign = x.sign;
- return #force_inline internal_int_sub_unsigned(dest, x, y);
+ dest.sign = x.sign
+ return #force_inline internal_int_sub_unsigned(dest, x, y)
}
-internal_add_signed :: proc { internal_int_add_signed, };
+internal_add_signed :: proc { internal_int_add_signed, }
/*
Low-level addition Int+DIGIT, signed. Handbook of Applied Cryptography, algorithm 14.7.
@@ -154,9 +154,9 @@ internal_add_signed :: proc { internal_int_add_signed, };
`dest` is large enough (a.used + 1) to fit result.
*/
internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- internal_grow(dest, a.used + 1) or_return;
+ internal_grow(dest, a.used + 1) or_return
/*
Fast paths for destination and input Int being the same.
*/
@@ -165,17 +165,17 @@ internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context
Fast path for dest.digit[0] + digit fits in dest.digit[0] without overflow.
*/
if dest.sign == .Zero_or_Positive && (dest.digit[0] + digit < _DIGIT_MAX) {
- dest.digit[0] += digit;
- dest.used += 1;
- return internal_clamp(dest);
+ dest.digit[0] += digit
+ dest.used += 1
+ return internal_clamp(dest)
}
/*
Can be subtracted from dest.digit[0] without underflow.
*/
if a.sign == .Negative && (dest.digit[0] > digit) {
- dest.digit[0] -= digit;
- dest.used += 1;
- return internal_clamp(dest);
+ dest.digit[0] -= digit
+ dest.used += 1
+ return internal_clamp(dest)
}
}
@@ -186,7 +186,7 @@ internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context
/*
Temporarily fix `a`'s sign.
*/
- a.sign = .Zero_or_Positive;
+ a.sign = .Zero_or_Positive
/*
dest = |a| - digit
*/
@@ -194,22 +194,22 @@ internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context
/*
Restore a's sign.
*/
- a.sign = .Negative;
- return err;
+ a.sign = .Negative
+ return err
}
/*
Restore sign and set `dest` sign.
*/
- a.sign = .Negative;
- dest.sign = .Negative;
+ a.sign = .Negative
+ dest.sign = .Negative
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
/*
Remember the currently used number of digits in `dest`.
*/
- old_used := dest.used;
+ old_used := dest.used
/*
If `a` is positive
@@ -218,53 +218,53 @@ internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context
/*
Add digits, use `carry`.
*/
- i: int;
- carry := digit;
+ i: int
+ carry := digit
#no_bounds_check for i = 0; i < a.used; i += 1 {
- dest.digit[i] = a.digit[i] + carry;
- carry = dest.digit[i] >> _DIGIT_BITS;
- dest.digit[i] &= _MASK;
+ dest.digit[i] = a.digit[i] + carry
+ carry = dest.digit[i] >> _DIGIT_BITS
+ dest.digit[i] &= _MASK
}
/*
Set final carry.
*/
- dest.digit[i] = carry;
+ dest.digit[i] = carry
/*
Set `dest` size.
*/
- dest.used = a.used + 1;
+ dest.used = a.used + 1
} else {
/*
`a` was negative and |a| < digit.
*/
- dest.used = 1;
+ dest.used = 1
/*
The result is a single DIGIT.
*/
- dest.digit[0] = digit - a.digit[0] if a.used == 1 else digit;
+ dest.digit[0] = digit - a.digit[0] if a.used == 1 else digit
}
/*
Sign is always positive.
*/
- dest.sign = .Zero_or_Positive;
+ dest.sign = .Zero_or_Positive
/*
Zero remainder.
*/
- internal_zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used)
/*
Adjust dest.used based on leading zeroes.
*/
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
-internal_add :: proc { internal_int_add_signed, internal_int_add_digit, };
+internal_add :: proc { internal_int_add_signed, internal_int_add_digit, }
internal_int_incr :: proc(dest: ^Int, allocator := context.allocator) -> (err: Error) {
- return #force_inline internal_add(dest, dest, 1);
+ return #force_inline internal_add(dest, dest, 1)
}
-internal_incr :: proc { internal_int_incr, };
+internal_incr :: proc { internal_int_incr, }
/*
Low-level subtraction, dest = number - decrease. Assumes |number| > |decrease|.
@@ -274,66 +274,66 @@ internal_incr :: proc { internal_int_incr, };
`dest`, `number` and `decrease` != `nil` and have been initalized.
*/
internal_int_sub_unsigned :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- dest := dest; x := number; y := decrease;
- old_used := dest.used;
- min_used := y.used;
- max_used := x.used;
- i: int;
+ dest := dest; x := number; y := decrease
+ old_used := dest.used
+ min_used := y.used
+ max_used := x.used
+ i: int
- grow(dest, max(max_used, _DEFAULT_DIGIT_COUNT)) or_return;
- dest.used = max_used;
+ grow(dest, max(max_used, _DEFAULT_DIGIT_COUNT)) or_return
+ dest.used = max_used
/*
All parameters have been initialized.
*/
- borrow := DIGIT(0);
+ borrow := DIGIT(0)
#no_bounds_check for i = 0; i < min_used; i += 1 {
- dest.digit[i] = (x.digit[i] - y.digit[i] - borrow);
+ dest.digit[i] = (x.digit[i] - y.digit[i] - borrow)
/*
borrow = carry bit of dest[i]
Note this saves performing an AND operation since if a carry does occur,
it will propagate all the way to the MSB.
As a result a single shift is enough to get the carry.
*/
- borrow = dest.digit[i] >> ((size_of(DIGIT) * 8) - 1);
+ borrow = dest.digit[i] >> ((size_of(DIGIT) * 8) - 1)
/*
Clear borrow from dest[i].
*/
- dest.digit[i] &= _MASK;
+ dest.digit[i] &= _MASK
}
/*
Now copy higher words if any, e.g. if A has more digits than B
*/
#no_bounds_check for ; i < max_used; i += 1 {
- dest.digit[i] = x.digit[i] - borrow;
+ dest.digit[i] = x.digit[i] - borrow
/*
borrow = carry bit of dest[i]
Note this saves performing an AND operation since if a carry does occur,
it will propagate all the way to the MSB.
As a result a single shift is enough to get the carry.
*/
- borrow = dest.digit[i] >> ((size_of(DIGIT) * 8) - 1);
+ borrow = dest.digit[i] >> ((size_of(DIGIT) * 8) - 1)
/*
Clear borrow from dest[i].
*/
- dest.digit[i] &= _MASK;
+ dest.digit[i] &= _MASK
}
/*
Zero remainder.
*/
- internal_zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used)
/*
Adjust dest.used based on leading zeroes.
*/
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
-internal_sub_unsigned :: proc { internal_int_sub_unsigned, };
+internal_sub_unsigned :: proc { internal_int_sub_unsigned, }
/*
Low-level subtraction, signed. Handbook of Applied Cryptography, algorithm 14.9.
@@ -343,16 +343,16 @@ internal_sub_unsigned :: proc { internal_int_sub_unsigned, };
`dest`, `number` and `decrease` != `nil` and have been initalized.
*/
internal_int_sub_signed :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- number := number; decrease := decrease;
+ number := number; decrease := decrease
if number.sign != decrease.sign {
/*
Subtract a negative from a positive, OR subtract a positive from a negative.
In either case, ADD their magnitudes and use the sign of the first number.
*/
- dest.sign = number.sign;
- return #force_inline internal_int_add_unsigned(dest, number, decrease);
+ dest.sign = number.sign
+ return #force_inline internal_int_add_unsigned(dest, number, decrease)
}
/*
@@ -364,16 +364,16 @@ internal_int_sub_signed :: proc(dest, number, decrease: ^Int, allocator := conte
The second has a larger magnitude.
The result has the *opposite* sign from the first number.
*/
- dest.sign = .Negative if number.sign == .Zero_or_Positive else .Zero_or_Positive;
- number, decrease = decrease, number;
+ dest.sign = .Negative if number.sign == .Zero_or_Positive else .Zero_or_Positive
+ number, decrease = decrease, number
} else {
/*
The first has a larger or equal magnitude.
Copy the sign from the first.
*/
- dest.sign = number.sign;
+ dest.sign = number.sign
}
- return #force_inline internal_int_sub_unsigned(dest, number, decrease);
+ return #force_inline internal_int_sub_unsigned(dest, number, decrease)
}
/*
@@ -385,11 +385,11 @@ internal_int_sub_signed :: proc(dest, number, decrease: ^Int, allocator := conte
`dest` is large enough (number.used + 1) to fit result.
*/
internal_int_sub_digit :: proc(dest, number: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- internal_grow(dest, number.used + 1) or_return;
+ internal_grow(dest, number.used + 1) or_return
- dest := dest; digit := digit;
+ dest := dest; digit := digit
/*
All parameters have been initialized.
@@ -400,15 +400,15 @@ internal_int_sub_digit :: proc(dest, number: ^Int, digit: DIGIT, allocator := co
Fast path for `dest` is negative and unsigned addition doesn't overflow the lowest digit.
*/
if dest.sign == .Negative && (dest.digit[0] + digit < _DIGIT_MAX) {
- dest.digit[0] += digit;
- return nil;
+ dest.digit[0] += digit
+ return nil
}
/*
Can be subtracted from dest.digit[0] without underflow.
*/
if number.sign == .Zero_or_Positive && (dest.digit[0] > digit) {
- dest.digit[0] -= digit;
- return nil;
+ dest.digit[0] -= digit
+ return nil
}
}
@@ -416,58 +416,58 @@ internal_int_sub_digit :: proc(dest, number: ^Int, digit: DIGIT, allocator := co
If `a` is negative, just do an unsigned addition (with fudged signs).
*/
if number.sign == .Negative {
- t := number;
- t.sign = .Zero_or_Positive;
+ t := number
+ t.sign = .Zero_or_Positive
- err = #force_inline internal_int_add_digit(dest, t, digit);
- dest.sign = .Negative;
+ err = #force_inline internal_int_add_digit(dest, t, digit)
+ dest.sign = .Negative
- internal_clamp(dest);
- return err;
+ internal_clamp(dest)
+ return err
}
- old_used := dest.used;
+ old_used := dest.used
/*
if `a`<= digit, simply fix the single digit.
*/
if number.used == 1 && (number.digit[0] <= digit) || number.used == 0 {
- dest.digit[0] = digit - number.digit[0] if number.used == 1 else digit;
- dest.sign = .Negative;
- dest.used = 1;
+ dest.digit[0] = digit - number.digit[0] if number.used == 1 else digit
+ dest.sign = .Negative
+ dest.used = 1
} else {
- dest.sign = .Zero_or_Positive;
- dest.used = number.used;
+ dest.sign = .Zero_or_Positive
+ dest.used = number.used
/*
Subtract with carry.
*/
- carry := digit;
+ carry := digit
#no_bounds_check for i := 0; i < number.used; i += 1 {
- dest.digit[i] = number.digit[i] - carry;
- carry = dest.digit[i] >> (_DIGIT_TYPE_BITS - 1);
- dest.digit[i] &= _MASK;
+ dest.digit[i] = number.digit[i] - carry
+ carry = dest.digit[i] >> (_DIGIT_TYPE_BITS - 1)
+ dest.digit[i] &= _MASK
}
}
/*
Zero remainder.
*/
- internal_zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used)
/*
Adjust dest.used based on leading zeroes.
*/
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
-internal_sub :: proc { internal_int_sub_signed, internal_int_sub_digit, };
+internal_sub :: proc { internal_int_sub_signed, internal_int_sub_digit, }
internal_int_decr :: proc(dest: ^Int, allocator := context.allocator) -> (err: Error) {
- return #force_inline internal_sub(dest, dest, 1);
+ return #force_inline internal_sub(dest, dest, 1)
}
-internal_decr :: proc { internal_int_decr, };
+internal_decr :: proc { internal_int_decr, }
/*
dest = src / 2
@@ -477,38 +477,38 @@ internal_decr :: proc { internal_int_decr, };
We make no allocations here.
*/
internal_int_shr1 :: proc(dest, src: ^Int) -> (err: Error) {
- old_used := dest.used; dest.used = src.used;
+ old_used := dest.used; dest.used = src.used
/*
Carry
*/
- fwd_carry := DIGIT(0);
+ fwd_carry := DIGIT(0)
#no_bounds_check for x := dest.used - 1; x >= 0; x -= 1 {
/*
Get the carry for the next iteration.
*/
- src_digit := src.digit[x];
- carry := src_digit & 1;
+ src_digit := src.digit[x]
+ carry := src_digit & 1
/*
Shift the current digit, add in carry and store.
*/
- dest.digit[x] = (src_digit >> 1) | (fwd_carry << (_DIGIT_BITS - 1));
+ dest.digit[x] = (src_digit >> 1) | (fwd_carry << (_DIGIT_BITS - 1))
/*
Forward carry to next iteration.
*/
- fwd_carry = carry;
+ fwd_carry = carry
}
/*
Zero remainder.
*/
- internal_zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used)
/*
Adjust dest.used based on leading zeroes.
*/
- dest.sign = src.sign;
- return internal_clamp(dest);
+ dest.sign = src.sign
+ return internal_clamp(dest)
}
/*
@@ -516,121 +516,121 @@ internal_int_shr1 :: proc(dest, src: ^Int) -> (err: Error) {
dest = src << 1
*/
internal_int_shl1 :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- internal_copy(dest, src) or_return;
+ internal_copy(dest, src) or_return
/*
Grow `dest` to accommodate the additional bits.
*/
- digits_needed := dest.used + 1;
- internal_grow(dest, digits_needed) or_return;
- dest.used = digits_needed;
+ digits_needed := dest.used + 1
+ internal_grow(dest, digits_needed) or_return
+ dest.used = digits_needed
- mask := (DIGIT(1) << uint(1)) - DIGIT(1);
- shift := DIGIT(_DIGIT_BITS - 1);
- carry := DIGIT(0);
+ mask := (DIGIT(1) << uint(1)) - DIGIT(1)
+ shift := DIGIT(_DIGIT_BITS - 1)
+ carry := DIGIT(0)
#no_bounds_check for x:= 0; x < dest.used; x+= 1 {
- fwd_carry := (dest.digit[x] >> shift) & mask;
- dest.digit[x] = (dest.digit[x] << uint(1) | carry) & _MASK;
- carry = fwd_carry;
+ fwd_carry := (dest.digit[x] >> shift) & mask
+ dest.digit[x] = (dest.digit[x] << uint(1) | carry) & _MASK
+ carry = fwd_carry
}
/*
Use final carry.
*/
if carry != 0 {
- dest.digit[dest.used] = carry;
- dest.used += 1;
+ dest.digit[dest.used] = carry
+ dest.used += 1
}
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
/*
Multiply by a DIGIT.
*/
internal_int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
- assert_if_nil(dest, src);
+ context.allocator = allocator
+ assert_if_nil(dest, src)
if multiplier == 0 {
- return internal_zero(dest);
+ return internal_zero(dest)
}
if multiplier == 1 {
- return internal_copy(dest, src);
+ return internal_copy(dest, src)
}
/*
Power of two?
*/
if multiplier == 2 {
- return #force_inline internal_int_shl1(dest, src);
+ return #force_inline internal_int_shl1(dest, src)
}
if #force_inline platform_int_is_power_of_two(int(multiplier)) {
- ix := internal_log(multiplier, 2) or_return;
- return internal_shl(dest, src, ix);
+ ix := internal_log(multiplier, 2) or_return
+ return internal_shl(dest, src, ix)
}
/*
Ensure `dest` is big enough to hold `src` * `multiplier`.
*/
- grow(dest, max(src.used + 1, _DEFAULT_DIGIT_COUNT)) or_return;
+ grow(dest, max(src.used + 1, _DEFAULT_DIGIT_COUNT)) or_return
/*
Save the original used count.
*/
- old_used := dest.used;
+ old_used := dest.used
/*
Set the sign.
*/
- dest.sign = src.sign;
+ dest.sign = src.sign
/*
Set up carry.
*/
- carry := _WORD(0);
+ carry := _WORD(0)
/*
Compute columns.
*/
- ix := 0;
+ ix := 0
#no_bounds_check for ; ix < src.used; ix += 1 {
/*
Compute product and carry sum for this term
*/
- product := carry + _WORD(src.digit[ix]) * _WORD(multiplier);
+ product := carry + _WORD(src.digit[ix]) * _WORD(multiplier)
/*
Mask off higher bits to get a single DIGIT.
*/
- dest.digit[ix] = DIGIT(product & _WORD(_MASK));
+ dest.digit[ix] = DIGIT(product & _WORD(_MASK))
/*
Send carry into next iteration
*/
- carry = product >> _DIGIT_BITS;
+ carry = product >> _DIGIT_BITS
}
/*
Store final carry [if any] and increment used.
*/
- dest.digit[ix] = DIGIT(carry);
- dest.used = src.used + 1;
+ dest.digit[ix] = DIGIT(carry)
+ dest.used = src.used + 1
/*
Zero remainder.
*/
- internal_zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used)
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
/*
High level multiplication (handles sign).
*/
internal_int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
Early out for `multiplier` is zero; Set `dest` to zero.
*/
if multiplier.used == 0 || src.used == 0 { return internal_zero(dest); }
- neg := src.sign != multiplier.sign;
+ neg := src.sign != multiplier.sign
if src == multiplier {
/*
@@ -640,19 +640,19 @@ internal_int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.alloc
/*
Use Toom-Cook?
*/
- err = #force_inline _private_int_sqr_toom(dest, src);
+ err = #force_inline _private_int_sqr_toom(dest, src)
} else if src.used >= SQR_KARATSUBA_CUTOFF {
/*
Karatsuba?
*/
- err = #force_inline _private_int_sqr_karatsuba(dest, src);
+ err = #force_inline _private_int_sqr_karatsuba(dest, src)
} else if ((src.used * 2) + 1) < _WARRAY && src.used < (_MAX_COMBA / 2) {
/*
Fast comba?
*/
- err = #force_inline _private_int_sqr_comba(dest, src);
+ err = #force_inline _private_int_sqr_comba(dest, src)
} else {
- err = #force_inline _private_int_sqr(dest, src);
+ err = #force_inline _private_int_sqr(dest, src)
}
} else {
/*
@@ -664,23 +664,23 @@ internal_int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.alloc
* was actually slower on the author's machine, but YMMV.
*/
- min_used := min(src.used, multiplier.used);
- max_used := max(src.used, multiplier.used);
- digits := src.used + multiplier.used + 1;
+ min_used := min(src.used, multiplier.used)
+ max_used := max(src.used, multiplier.used)
+ digits := src.used + multiplier.used + 1
if min_used >= MUL_KARATSUBA_CUTOFF && (max_used / 2) >= MUL_KARATSUBA_CUTOFF && max_used >= (2 * min_used) {
/*
Not much effect was observed below a ratio of 1:2, but again: YMMV.
*/
- err = _private_int_mul_balance(dest, src, multiplier);
+ err = _private_int_mul_balance(dest, src, multiplier)
} else if min_used >= MUL_TOOM_CUTOFF {
/*
Toom path commented out until it no longer fails Factorial 10k or 100k,
as reveaved in the long test.
*/
- err = #force_inline _private_int_mul_toom(dest, src, multiplier);
+ err = #force_inline _private_int_mul_toom(dest, src, multiplier)
} else if min_used >= MUL_KARATSUBA_CUTOFF {
- err = #force_inline _private_int_mul_karatsuba(dest, src, multiplier);
+ err = #force_inline _private_int_mul_karatsuba(dest, src, multiplier)
} else if digits < _WARRAY && min_used <= _MAX_COMBA {
/*
Can we use the fast multiplier?
@@ -688,24 +688,24 @@ internal_int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.alloc
* have less than MP_WARRAY digits and the number of
* digits won't affect carry propagation
*/
- err = #force_inline _private_int_mul_comba(dest, src, multiplier, digits);
+ err = #force_inline _private_int_mul_comba(dest, src, multiplier, digits)
} else {
- err = #force_inline _private_int_mul(dest, src, multiplier, digits);
+ err = #force_inline _private_int_mul(dest, src, multiplier, digits)
}
}
- dest.sign = .Negative if dest.used > 0 && neg else .Zero_or_Positive;
- return err;
+ dest.sign = .Negative if dest.used > 0 && neg else .Zero_or_Positive
+ return err
}
-internal_mul :: proc { internal_int_mul, internal_int_mul_digit, };
+internal_mul :: proc { internal_int_mul, internal_int_mul_digit, }
internal_sqr :: proc (dest, src: ^Int, allocator := context.allocator) -> (res: Error) {
/*
We call `internal_mul` and not e.g. `_private_int_sqr` because the former
will dispatch to the optimal implementation depending on the source.
*/
- return #force_inline internal_mul(dest, src, src, allocator);
+ return #force_inline internal_mul(dest, src, src, allocator)
}
/*
@@ -714,37 +714,37 @@ internal_sqr :: proc (dest, src: ^Int, allocator := context.allocator) -> (res:
`numerator` and `denominator` are expected not to be `nil` and have been initialized.
*/
internal_int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if denominator.used == 0 { return .Division_by_Zero; }
/*
If numerator < denominator then quotient = 0, remainder = numerator.
*/
if #force_inline internal_cmp_mag(numerator, denominator) == -1 {
if remainder != nil {
- internal_copy(remainder, numerator) or_return;
+ internal_copy(remainder, numerator) or_return
}
if quotient != nil {
- internal_zero(quotient);
+ internal_zero(quotient)
}
- return nil;
+ return nil
}
if (denominator.used > 2 * MUL_KARATSUBA_CUTOFF) && (denominator.used <= (numerator.used / 3) * 2) {
- assert(denominator.used >= 160 && numerator.used >= 240, "MUL_KARATSUBA_CUTOFF global not properly set.");
- err = _private_int_div_recursive(quotient, remainder, numerator, denominator);
+ assert(denominator.used >= 160 && numerator.used >= 240, "MUL_KARATSUBA_CUTOFF global not properly set.")
+ err = _private_int_div_recursive(quotient, remainder, numerator, denominator)
// err = #force_inline _private_int_div_school(quotient, remainder, numerator, denominator);
} else {
when true {
- err = #force_inline _private_int_div_school(quotient, remainder, numerator, denominator);
+ err = #force_inline _private_int_div_school(quotient, remainder, numerator, denominator)
} else {
/*
NOTE(Jeroen): We no longer need or use `_private_int_div_small`.
We'll keep it around for a bit until we're reasonably certain div_school is bug free.
*/
- err = _private_int_div_small(quotient, remainder, numerator, denominator);
+ err = _private_int_div_small(quotient, remainder, numerator, denominator)
}
}
- return;
+ return
}
/*
@@ -752,7 +752,7 @@ internal_int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, a
The quotient is optional and may be passed a nil.
*/
internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
Cannot divide by zero.
@@ -764,9 +764,9 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT,
*/
if denominator == 1 || numerator.used == 0 {
if quotient != nil {
- return 0, internal_copy(quotient, numerator);
+ return 0, internal_copy(quotient, numerator)
}
- return 0, err;
+ return 0, err
}
/*
Power of two?
@@ -774,75 +774,75 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT,
if denominator == 2 {
if numerator.used > 0 && numerator.digit[0] & 1 != 0 {
// Remainder is 1 if numerator is odd.
- remainder = 1;
+ remainder = 1
}
if quotient == nil {
- return remainder, nil;
+ return remainder, nil
}
- return remainder, internal_shr(quotient, numerator, 1);
+ return remainder, internal_shr(quotient, numerator, 1)
}
- ix: int;
+ ix: int
if platform_int_is_power_of_two(int(denominator)) {
- ix = 1;
+ ix = 1
for ix < _DIGIT_BITS && denominator != (1 << uint(ix)) {
- ix += 1;
+ ix += 1
}
- remainder = numerator.digit[0] & ((1 << uint(ix)) - 1);
+ remainder = numerator.digit[0] & ((1 << uint(ix)) - 1)
if quotient == nil {
- return remainder, nil;
+ return remainder, nil
}
- return remainder, internal_shr(quotient, numerator, int(ix));
+ return remainder, internal_shr(quotient, numerator, int(ix))
}
/*
Three?
*/
if denominator == 3 {
- return _private_int_div_3(quotient, numerator);
+ return _private_int_div_3(quotient, numerator)
}
/*
No easy answer [c'est la vie]. Just division.
*/
- q := &Int{};
+ q := &Int{}
- internal_grow(q, numerator.used) or_return;
+ internal_grow(q, numerator.used) or_return
- q.used = numerator.used;
- q.sign = numerator.sign;
+ q.used = numerator.used
+ q.sign = numerator.sign
- w := _WORD(0);
+ w := _WORD(0)
for ix = numerator.used - 1; ix >= 0; ix -= 1 {
- t := DIGIT(0);
- w = (w << _WORD(_DIGIT_BITS) | _WORD(numerator.digit[ix]));
+ t := DIGIT(0)
+ w = (w << _WORD(_DIGIT_BITS) | _WORD(numerator.digit[ix]))
if w >= _WORD(denominator) {
- t = DIGIT(w / _WORD(denominator));
- w -= _WORD(t) * _WORD(denominator);
+ t = DIGIT(w / _WORD(denominator))
+ w -= _WORD(t) * _WORD(denominator)
}
- q.digit[ix] = t;
+ q.digit[ix] = t
}
- remainder = DIGIT(w);
+ remainder = DIGIT(w)
if quotient != nil {
- internal_clamp(q);
- internal_swap(q, quotient);
+ internal_clamp(q)
+ internal_swap(q, quotient)
}
- internal_destroy(q);
- return remainder, nil;
+ internal_destroy(q)
+ return remainder, nil
}
-internal_divmod :: proc { internal_int_divmod, internal_int_divmod_digit, };
+internal_divmod :: proc { internal_int_divmod, internal_int_divmod_digit, }
/*
Asssumes quotient, numerator and denominator to have been initialized and not to be nil.
*/
internal_int_div :: proc(quotient, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {
- return #force_inline internal_int_divmod(quotient, nil, numerator, denominator, allocator);
+ return #force_inline internal_int_divmod(quotient, nil, numerator, denominator, allocator)
}
-internal_div :: proc { internal_int_div, };
+internal_div :: proc { internal_int_div, }
/*
remainder = numerator % denominator.
@@ -856,50 +856,50 @@ internal_int_mod :: proc(remainder, numerator, denominator: ^Int, allocator := c
if remainder.used == 0 || denominator.sign == remainder.sign { return nil; }
- return #force_inline internal_add(remainder, remainder, numerator, allocator);
+ return #force_inline internal_add(remainder, remainder, numerator, allocator)
}
internal_int_mod_digit :: proc(numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {
- return internal_int_divmod_digit(nil, numerator, denominator, allocator);
+ return internal_int_divmod_digit(nil, numerator, denominator, allocator)
}
-internal_mod :: proc{ internal_int_mod, internal_int_mod_digit};
+internal_mod :: proc{ internal_int_mod, internal_int_mod_digit}
/*
remainder = (number + addend) % modulus.
*/
internal_int_addmod :: proc(remainder, number, addend, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
#force_inline internal_add(remainder, number, addend, allocator) or_return;
- return #force_inline internal_mod(remainder, remainder, modulus, allocator);
+ return #force_inline internal_mod(remainder, remainder, modulus, allocator)
}
-internal_addmod :: proc { internal_int_addmod, };
+internal_addmod :: proc { internal_int_addmod, }
/*
remainder = (number - decrease) % modulus.
*/
internal_int_submod :: proc(remainder, number, decrease, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
#force_inline internal_sub(remainder, number, decrease, allocator) or_return;
- return #force_inline internal_mod(remainder, remainder, modulus, allocator);
+ return #force_inline internal_mod(remainder, remainder, modulus, allocator)
}
-internal_submod :: proc { internal_int_submod, };
+internal_submod :: proc { internal_int_submod, }
/*
remainder = (number * multiplicand) % modulus.
*/
internal_int_mulmod :: proc(remainder, number, multiplicand, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
#force_inline internal_mul(remainder, number, multiplicand, allocator) or_return;
- return #force_inline internal_mod(remainder, remainder, modulus, allocator);
+ return #force_inline internal_mod(remainder, remainder, modulus, allocator)
}
-internal_mulmod :: proc { internal_int_mulmod, };
+internal_mulmod :: proc { internal_int_mulmod, }
/*
remainder = (number * number) % modulus.
*/
internal_int_sqrmod :: proc(remainder, number, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
#force_inline internal_sqr(remainder, number, allocator) or_return;
- return #force_inline internal_mod(remainder, remainder, modulus, allocator);
+ return #force_inline internal_mod(remainder, remainder, modulus, allocator)
}
-internal_sqrmod :: proc { internal_int_sqrmod, };
+internal_sqrmod :: proc { internal_int_sqrmod, }
@@ -908,26 +908,26 @@ internal_sqrmod :: proc { internal_int_sqrmod, };
This way we'll have to reallocate less, possibly not at all.
*/
internal_int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if n >= FACTORIAL_BINARY_SPLIT_CUTOFF {
- return _private_int_factorial_binary_split(res, n);
+ return _private_int_factorial_binary_split(res, n)
}
- i := len(_factorial_table);
+ i := len(_factorial_table)
if n < i {
- return #force_inline internal_set(res, _factorial_table[n]);
+ return #force_inline internal_set(res, _factorial_table[n])
}
#force_inline internal_set(res, _factorial_table[i - 1]) or_return;
for {
if err = #force_inline internal_mul(res, res, DIGIT(i)); err != nil || i == n {
- return err;
+ return err
}
- i += 1;
+ i += 1
}
- return nil;
+ return nil
}
/*
@@ -939,7 +939,7 @@ internal_int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator
internal_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
if res_gcd == nil && res_lcm == nil { return nil; }
- return #force_inline _private_int_gcd_lcm(res_gcd, res_lcm, a, b, allocator);
+ return #force_inline _private_int_gcd_lcm(res_gcd, res_lcm, a, b, allocator)
}
/*
@@ -956,29 +956,29 @@ internal_int_mod_bits :: proc(remainder, numerator: ^Int, bits: int, allocator :
/*
If the modulus is larger than the value, return the value.
*/
- internal_copy(remainder, numerator) or_return;
+ internal_copy(remainder, numerator) or_return
if bits >= (numerator.used * _DIGIT_BITS) {
- return;
+ return
}
/*
Zero digits above the last digit of the modulus.
*/
- zero_count := (bits / _DIGIT_BITS);
- zero_count += 0 if (bits % _DIGIT_BITS == 0) else 1;
+ zero_count := (bits / _DIGIT_BITS)
+ zero_count += 0 if (bits % _DIGIT_BITS == 0) else 1
/*
Zero remainder. Special case, can't use `internal_zero_unused`.
*/
if zero_count > 0 {
- mem.zero_slice(remainder.digit[zero_count:]);
+ mem.zero_slice(remainder.digit[zero_count:])
}
/*
Clear the digit that is not completely outside/inside the modulus.
*/
- remainder.digit[bits / _DIGIT_BITS] &= DIGIT(1 << DIGIT(bits % _DIGIT_BITS)) - DIGIT(1);
- return internal_clamp(remainder);
+ remainder.digit[bits / _DIGIT_BITS] &= DIGIT(1 << DIGIT(bits % _DIGIT_BITS)) - DIGIT(1)
+ return internal_clamp(remainder)
}
/*
@@ -997,37 +997,37 @@ internal_int_mod_bits :: proc(remainder, numerator: ^Int, bits: int, allocator :
Assumes `a` not to be `nil`.
*/
internal_int_is_initialized :: #force_inline proc(a: ^Int) -> (initialized: bool) {
- raw := transmute(mem.Raw_Dynamic_Array)a.digit;
- return raw.cap >= _MIN_DIGIT_COUNT;
+ raw := transmute(mem.Raw_Dynamic_Array)a.digit
+ return raw.cap >= _MIN_DIGIT_COUNT
}
-internal_is_initialized :: proc { internal_int_is_initialized, };
+internal_is_initialized :: proc { internal_int_is_initialized, }
/*
This procedure will return `true` if the `Int` is zero, `false` if not.
Assumes `a` not to be `nil`.
*/
internal_int_is_zero :: #force_inline proc(a: ^Int) -> (zero: bool) {
- return a.used == 0;
+ return a.used == 0
}
-internal_is_zero :: proc { internal_int_is_zero, };
+internal_is_zero :: proc { internal_int_is_zero, }
/*
This procedure will return `true` if the `Int` is positive, `false` if not.
Assumes `a` not to be `nil`.
*/
internal_int_is_positive :: #force_inline proc(a: ^Int) -> (positive: bool) {
- return a.sign == .Zero_or_Positive;
+ return a.sign == .Zero_or_Positive
}
-internal_is_positive :: proc { internal_int_is_positive, };
+internal_is_positive :: proc { internal_int_is_positive, }
/*
This procedure will return `true` if the `Int` is negative, `false` if not.
Assumes `a` not to be `nil`.
*/
internal_int_is_negative :: #force_inline proc(a: ^Int) -> (negative: bool) {
- return a.sign == .Negative;
+ return a.sign == .Negative
}
-internal_is_negative :: proc { internal_int_is_negative, };
+internal_is_negative :: proc { internal_int_is_negative, }
/*
This procedure will return `true` if the `Int` is even, `false` if not.
@@ -1040,18 +1040,18 @@ internal_int_is_even :: #force_inline proc(a: ^Int) -> (even: bool) {
`a.used` > 0 here, because the above handled `is_zero`.
We don't need to explicitly test it.
*/
- return a.digit[0] & 1 == 0;
+ return a.digit[0] & 1 == 0
}
-internal_is_even :: proc { internal_int_is_even, };
+internal_is_even :: proc { internal_int_is_even, }
/*
This procedure will return `true` if the `Int` is even, `false` if not.
Assumes `a` not to be `nil`.
*/
internal_int_is_odd :: #force_inline proc(a: ^Int) -> (odd: bool) {
- return !internal_int_is_even(a);
+ return !internal_int_is_even(a)
}
-internal_is_odd :: proc { internal_int_is_odd, };
+internal_is_odd :: proc { internal_int_is_odd, }
/*
@@ -1080,9 +1080,9 @@ internal_int_is_power_of_two :: #force_inline proc(a: ^Int) -> (power_of_two: bo
*/
for i := 1; i < a.used && a.digit[i - 1] != 0; i += 1 { return false; }
- return true;
+ return true
}
-internal_is_power_of_two :: proc { internal_int_is_power_of_two, };
+internal_is_power_of_two :: proc { internal_int_is_power_of_two, }
/*
Compare two `Int`s, signed.
@@ -1091,7 +1091,7 @@ internal_is_power_of_two :: proc { internal_int_is_power_of_two, };
Expects `a` and `b` both to be valid `Int`s, i.e. initialized and not `nil`.
*/
internal_int_compare :: #force_inline proc(a, b: ^Int) -> (comparison: int) {
- a_is_negative := #force_inline internal_is_negative(a);
+ a_is_negative := #force_inline internal_is_negative(a)
/*
Compare based on sign.
@@ -1102,10 +1102,10 @@ internal_int_compare :: #force_inline proc(a, b: ^Int) -> (comparison: int) {
If `a` is negative, compare in the opposite direction */
if a_is_negative { return #force_inline internal_compare_magnitude(b, a); }
- return #force_inline internal_compare_magnitude(a, b);
+ return #force_inline internal_compare_magnitude(a, b)
}
-internal_compare :: proc { internal_int_compare, internal_int_compare_digit, };
-internal_cmp :: internal_compare;
+internal_compare :: proc { internal_int_compare, internal_int_compare_digit, }
+internal_cmp :: internal_compare
/*
Compare an `Int` to an unsigned number upto `DIGIT & _MASK`.
@@ -1114,32 +1114,32 @@ internal_cmp :: internal_compare;
Expects: `a` and `b` both to be valid `Int`s, i.e. initialized and not `nil`.
*/
internal_int_compare_digit :: #force_inline proc(a: ^Int, b: DIGIT) -> (comparison: int) {
- a_is_negative := #force_inline internal_is_negative(a);
+ a_is_negative := #force_inline internal_is_negative(a)
switch {
/*
Compare based on sign first.
*/
- case a_is_negative: return -1;
+ case a_is_negative: return -1
/*
Then compare on magnitude.
*/
- case a.used > 1: return +1;
+ case a.used > 1: return +1
/*
We have only one digit. Compare it against `b`.
*/
- case a.digit[0] < b: return -1;
- case a.digit[0] == b: return 0;
- case a.digit[0] > b: return +1;
+ case a.digit[0] < b: return -1
+ case a.digit[0] == b: return 0
+ case a.digit[0] > b: return +1
/*
Unreachable.
Just here because Odin complains about a missing return value at the bottom of the proc otherwise.
*/
- case: return;
+ case: return
}
}
-internal_compare_digit :: proc { internal_int_compare_digit, };
-internal_cmp_digit :: internal_compare_digit;
+internal_compare_digit :: proc { internal_int_compare_digit, }
+internal_cmp_digit :: internal_compare_digit
/*
Compare the magnitude of two `Int`s, unsigned.
@@ -1150,9 +1150,9 @@ internal_int_compare_magnitude :: #force_inline proc(a, b: ^Int) -> (comparison:
*/
if a.used != b.used {
if a.used > b.used {
- return +1;
+ return +1
}
- return -1;
+ return -1
}
/*
@@ -1161,16 +1161,16 @@ internal_int_compare_magnitude :: #force_inline proc(a, b: ^Int) -> (comparison:
#no_bounds_check for n := a.used - 1; n >= 0; n -= 1 {
if a.digit[n] != b.digit[n] {
if a.digit[n] > b.digit[n] {
- return +1;
+ return +1
}
- return -1;
+ return -1
}
}
- return 0;
+ return 0
}
-internal_compare_magnitude :: proc { internal_int_compare_magnitude, };
-internal_cmp_mag :: internal_compare_magnitude;
+internal_compare_magnitude :: proc { internal_int_compare_magnitude, }
+internal_cmp_mag :: internal_compare_magnitude
/*
Check if remainders are possible squares - fast exclude non-squares.
@@ -1179,12 +1179,12 @@ internal_cmp_mag :: internal_compare_magnitude;
Assumes `a` not to be `nil` and to have been initialized.
*/
internal_int_is_square :: proc(a: ^Int, allocator := context.allocator) -> (square: bool, err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
Default to Non-square :)
*/
- square = false;
+ square = false
if internal_is_negative(a) { return; }
if internal_is_zero(a) { return; }
@@ -1197,18 +1197,18 @@ internal_int_is_square :: proc(a: ^Int, allocator := context.allocator) -> (squa
/*
Next check mod 105 (3*5*7).
*/
- c: DIGIT;
- c, err = internal_mod(a, 105);
+ c: DIGIT
+ c, err = internal_mod(a, 105)
if _private_int_rem_105[c] == 1 { return; }
- t := &Int{};
- defer destroy(t);
+ t := &Int{}
+ defer destroy(t)
- set(t, 11 * 13 * 17 * 19 * 23 * 29 * 31) or_return;
- internal_mod(t, a, t) or_return;
+ set(t, 11 * 13 * 17 * 19 * 23 * 29 * 31) or_return
+ internal_mod(t, a, t) or_return
- r: u64;
- r, err = internal_int_get(t, u64);
+ r: u64
+ r, err = internal_int_get(t, u64)
/*
Check for other prime modules, note it's not an ERROR but we must
@@ -1226,12 +1226,12 @@ internal_int_is_square :: proc(a: ^Int, allocator := context.allocator) -> (squa
/*
Final check - is sqr(sqrt(arg)) == arg?
*/
- sqrt(t, a) or_return;
- sqr(t, t) or_return;
+ sqrt(t, a) or_return
+ sqr(t, t) or_return
- square = internal_cmp_mag(t, a) == 0;
+ square = internal_cmp_mag(t, a) == 0
- return;
+ return
}
/*
@@ -1258,7 +1258,7 @@ internal_int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) {
*/
if a.used == 1 { return internal_log(a.digit[0], DIGIT(base)); }
- return _private_int_log(a, base);
+ return _private_int_log(a, base)
}
@@ -1277,52 +1277,52 @@ internal_digit_log :: proc(a: DIGIT, base: DIGIT) -> (log: int, err: Error) {
*/
if a == base { return 1, nil; }
- N := _WORD(a);
- bracket_low := _WORD(1);
- bracket_high := _WORD(base);
- high := 1;
- low := 0;
+ N := _WORD(a)
+ bracket_low := _WORD(1)
+ bracket_high := _WORD(base)
+ high := 1
+ low := 0
for bracket_high < N {
- low = high;
- bracket_low = bracket_high;
- high <<= 1;
- bracket_high *= bracket_high;
+ low = high
+ bracket_low = bracket_high
+ high <<= 1
+ bracket_high *= bracket_high
}
for high - low > 1 {
- mid := (low + high) >> 1;
- bracket_mid := bracket_low * #force_inline internal_small_pow(_WORD(base), _WORD(mid - low));
+ mid := (low + high) >> 1
+ bracket_mid := bracket_low * #force_inline internal_small_pow(_WORD(base), _WORD(mid - low))
if N < bracket_mid {
- high = mid;
- bracket_high = bracket_mid;
+ high = mid
+ bracket_high = bracket_mid
}
if N > bracket_mid {
- low = mid;
- bracket_low = bracket_mid;
+ low = mid
+ bracket_low = bracket_mid
}
if N == bracket_mid {
- return mid, nil;
+ return mid, nil
}
}
if bracket_high == N {
- return high, nil;
+ return high, nil
} else {
- return low, nil;
+ return low, nil
}
}
-internal_log :: proc { internal_int_log, internal_digit_log, };
+internal_log :: proc { internal_int_log, internal_digit_log, }
/*
Calculate dest = base^power using a square-multiply algorithm.
Assumes `dest` and `base` not to be `nil` and to have been initialized.
*/
internal_int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- power := power;
+ power := power
/*
Early outs.
*/
@@ -1331,8 +1331,8 @@ internal_int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allo
A zero base is a special case.
*/
if power < 0 {
- internal_zero(dest) or_return;
- return .Math_Domain_Error;
+ internal_zero(dest) or_return
+ return .Math_Domain_Error
}
if power == 0 { return internal_one(dest); }
if power > 0 { return internal_zero(dest); }
@@ -1342,52 +1342,52 @@ internal_int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allo
/*
Fraction, so we'll return zero.
*/
- return internal_zero(dest);
+ return internal_zero(dest)
}
switch(power) {
case 0:
/*
Any base to the power zero is one.
*/
- return #force_inline internal_one(dest);
+ return #force_inline internal_one(dest)
case 1:
/*
Any base to the power one is itself.
*/
- return copy(dest, base);
+ return copy(dest, base)
case 2:
- return #force_inline internal_sqr(dest, base);
+ return #force_inline internal_sqr(dest, base)
}
- g := &Int{};
- internal_copy(g, base) or_return;
+ g := &Int{}
+ internal_copy(g, base) or_return
/*
Set initial result.
*/
- internal_one(dest) or_return;
+ internal_one(dest) or_return
- defer internal_destroy(g);
+ defer internal_destroy(g)
for power > 0 {
/*
If the bit is set, multiply.
*/
if power & 1 != 0 {
- internal_mul(dest, g, dest) or_return;
+ internal_mul(dest, g, dest) or_return
}
/*
Square.
*/
if power > 1 {
- internal_sqr(g, g) or_return;
+ internal_sqr(g, g) or_return
}
/* shift to next bit */
- power >>= 1;
+ power >>= 1
}
- return;
+ return
}
/*
@@ -1395,34 +1395,34 @@ internal_int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allo
Assumes `dest` not to be `nil` and to have been initialized.
*/
internal_int_pow_int :: proc(dest: ^Int, base, power: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- base_t := &Int{};
- defer internal_destroy(base_t);
+ base_t := &Int{}
+ defer internal_destroy(base_t)
- internal_set(base_t, base) or_return;
+ internal_set(base_t, base) or_return
- return #force_inline internal_int_pow(dest, base_t, power);
+ return #force_inline internal_int_pow(dest, base_t, power)
}
-internal_pow :: proc { internal_int_pow, internal_int_pow_int, };
-internal_exp :: pow;
+internal_pow :: proc { internal_int_pow, internal_int_pow_int, }
+internal_exp :: pow
/*
*/
internal_small_pow :: proc(base: _WORD, exponent: _WORD) -> (result: _WORD) {
- exponent := exponent; base := base;
- result = _WORD(1);
+ exponent := exponent; base := base
+ result = _WORD(1)
for exponent != 0 {
if exponent & 1 == 1 {
- result *= base;
+ result *= base
}
- exponent >>= 1;
- base *= base;
+ exponent >>= 1
+ base *= base
}
- return result;
+ return result
}
/*
@@ -1430,7 +1430,7 @@ internal_small_pow :: proc(base: _WORD, exponent: _WORD) -> (result: _WORD) {
Assumes `dest` and `src` not to be `nil` and to have been initialized.
*/
internal_int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
Must be positive.
@@ -1445,33 +1445,33 @@ internal_int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (e
/*
Set up temporaries.
*/
- x, y, t1, t2 := &Int{}, &Int{}, &Int{}, &Int{};
- defer internal_destroy(x, y, t1, t2);
+ x, y, t1, t2 := &Int{}, &Int{}, &Int{}, &Int{}
+ defer internal_destroy(x, y, t1, t2)
- count := #force_inline internal_count_bits(src);
+ count := #force_inline internal_count_bits(src)
- a, b := count >> 1, count & 1;
- internal_int_power_of_two(x, a+b, allocator) or_return;
+ a, b := count >> 1, count & 1
+ internal_int_power_of_two(x, a+b, allocator) or_return
for {
/*
y = (x + n // x) // 2
*/
- internal_div(t1, src, x) or_return;
- internal_add(t2, t1, x) or_return;
- internal_shr(y, t2, 1) or_return;
+ internal_div(t1, src, x) or_return
+ internal_add(t2, t1, x) or_return
+ internal_shr(y, t2, 1) or_return
if c := internal_cmp(y, x); c == 0 || c == 1 {
- internal_swap(dest, x);
- return nil;
+ internal_swap(dest, x)
+ return nil
}
- internal_swap(x, y);
+ internal_swap(x, y)
}
- internal_swap(dest, x);
- return err;
+ internal_swap(dest, x)
+ return err
}
-internal_sqrt :: proc { internal_int_sqrt, };
+internal_sqrt :: proc { internal_int_sqrt, }
/*
@@ -1484,7 +1484,7 @@ internal_sqrt :: proc { internal_int_sqrt, };
Assumes `dest` and `src` not to be `nil` and have been initialized.
*/
internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
Fast path for n == 2
@@ -1498,15 +1498,15 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca
/*
Set up temporaries.
*/
- t1, t2, t3, a := &Int{}, &Int{}, &Int{}, &Int{};
- defer internal_destroy(t1, t2, t3);
+ t1, t2, t3, a := &Int{}, &Int{}, &Int{}, &Int{}
+ defer internal_destroy(t1, t2, t3)
/*
If `src` is negative fudge the sign but keep track.
*/
- a.sign = .Zero_or_Positive;
- a.used = src.used;
- a.digit = src.digit;
+ a.sign = .Zero_or_Positive
+ a.used = src.used
+ a.digit = src.digit
/*
If "n" is larger than INT_MAX it is also larger than
@@ -1514,63 +1514,63 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca
with an int and hence the root is always < 2 (two).
*/
if n > max(int) / 2 {
- err = set(dest, 1);
- dest.sign = a.sign;
- return err;
+ err = set(dest, 1)
+ dest.sign = a.sign
+ return err
}
/*
Compute seed: 2^(log_2(src)/n + 2)
*/
- ilog2 := internal_count_bits(src);
+ ilog2 := internal_count_bits(src)
/*
"src" is smaller than max(int), we can cast safely.
*/
if ilog2 < n {
- err = internal_one(dest);
- dest.sign = a.sign;
- return err;
+ err = internal_one(dest)
+ dest.sign = a.sign
+ return err
}
- ilog2 /= n;
+ ilog2 /= n
if ilog2 == 0 {
- err = internal_one(dest);
- dest.sign = a.sign;
- return err;
+ err = internal_one(dest)
+ dest.sign = a.sign
+ return err
}
/*
Start value must be larger than root.
*/
- ilog2 += 2;
- internal_int_power_of_two(t2, ilog2) or_return;
+ ilog2 += 2
+ internal_int_power_of_two(t2, ilog2) or_return
- c: int;
- iterations := 0;
+ c: int
+ iterations := 0
for {
/* t1 = t2 */
- internal_copy(t1, t2) or_return;
+ internal_copy(t1, t2) or_return
/* t2 = t1 - ((t1**b - a) / (b * t1**(b-1))) */
/* t3 = t1**(b-1) */
- internal_pow(t3, t1, n-1) or_return;
+ internal_pow(t3, t1, n-1) or_return
/* numerator */
/* t2 = t1**b */
- internal_mul(t2, t1, t3) or_return;
+ internal_mul(t2, t1, t3) or_return
/* t2 = t1**b - a */
- internal_sub(t2, t2, a) or_return;
+ internal_sub(t2, t2, a) or_return
/* denominator */
/* t3 = t1**(b-1) * b */
- internal_mul(t3, t3, DIGIT(n)) or_return;
+ internal_mul(t3, t3, DIGIT(n)) or_return
/* t3 = (t1**b - a)/(b * t1**(b-1)) */
- internal_div(t3, t2, t3) or_return;
- internal_sub(t2, t1, t3) or_return;
+ internal_div(t3, t2, t3) or_return
+ internal_sub(t2, t1, t3) or_return
/*
Number of rounds is at most log_2(root). If it is more it
@@ -1579,65 +1579,65 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca
if ilog2 -= 1; ilog2 == 0 { break; }
if internal_cmp(t1, t2) == 0 { break; }
- iterations += 1;
+ iterations += 1
if iterations == MAX_ITERATIONS_ROOT_N {
- return .Max_Iterations_Reached;
+ return .Max_Iterations_Reached
}
}
/* Result can be off by a few so check. */
/* Loop beneath can overshoot by one if found root is smaller than actual root. */
- iterations = 0;
+ iterations = 0
for {
- internal_pow(t2, t1, n) or_return;
+ internal_pow(t2, t1, n) or_return
- c = internal_cmp(t2, a);
+ c = internal_cmp(t2, a)
if c == 0 {
- swap(dest, t1);
- return nil;
+ swap(dest, t1)
+ return nil
} else if c == -1 {
- internal_add(t1, t1, DIGIT(1)) or_return;
+ internal_add(t1, t1, DIGIT(1)) or_return
} else {
- break;
+ break
}
- iterations += 1;
+ iterations += 1
if iterations == MAX_ITERATIONS_ROOT_N {
- return .Max_Iterations_Reached;
+ return .Max_Iterations_Reached
}
}
- iterations = 0;
+ iterations = 0
/*
Correct overshoot from above or from recurrence.
*/
for {
- internal_pow(t2, t1, n) or_return;
+ internal_pow(t2, t1, n) or_return
if internal_cmp(t2, a) != 1 { break; }
- internal_sub(t1, t1, DIGIT(1)) or_return;
+ internal_sub(t1, t1, DIGIT(1)) or_return
- iterations += 1;
+ iterations += 1
if iterations == MAX_ITERATIONS_ROOT_N {
- return .Max_Iterations_Reached;
+ return .Max_Iterations_Reached
}
}
/*
Set the result.
*/
- internal_swap(dest, t1);
+ internal_swap(dest, t1)
/*
Set the sign of the result.
*/
- dest.sign = src.sign;
+ dest.sign = src.sign
- return err;
+ return err
}
-internal_root_n :: proc { internal_int_root_n, };
+internal_root_n :: proc { internal_int_root_n, }
/*
Other internal helpers
@@ -1648,51 +1648,51 @@ internal_root_n :: proc { internal_int_root_n, };
Asssumes none of the `integers` to be a `nil`.
*/
internal_int_destroy :: proc(integers: ..^Int) {
- integers := integers;
+ integers := integers
for a in &integers {
- raw := transmute(mem.Raw_Dynamic_Array)a.digit;
+ raw := transmute(mem.Raw_Dynamic_Array)a.digit
if raw.cap > 0 {
- mem.zero_slice(a.digit[:]);
- free(&a.digit[0]);
+ mem.zero_slice(a.digit[:])
+ free(&a.digit[0])
}
- a = &Int{};
+ a = &Int{}
}
}
-internal_destroy :: proc{ internal_int_destroy, };
+internal_destroy :: proc{ internal_int_destroy, }
/*
Helpers to set an `Int` to a specific value.
*/
internal_int_set_from_integer :: proc(dest: ^Int, src: $T, minimize := false, allocator := context.allocator) -> (err: Error)
where intrinsics.type_is_integer(T) {
- context.allocator = allocator;
+ context.allocator = allocator
- src := src;
+ src := src
- internal_error_if_immutable(dest) or_return;
+ internal_error_if_immutable(dest) or_return
/*
Most internal procs asssume an Int to have already been initialize,
but as this is one of the procs that initializes, we have to check the following.
*/
- internal_clear_if_uninitialized_single(dest) or_return;
+ internal_clear_if_uninitialized_single(dest) or_return
- dest.flags = {}; // We're not -Inf, Inf, NaN or Immutable.
+ dest.flags = {} // We're not -Inf, Inf, NaN or Immutable.
- dest.used = 0;
- dest.sign = .Zero_or_Positive if src >= 0 else .Negative;
- src = internal_abs(src);
+ dest.used = 0
+ dest.sign = .Zero_or_Positive if src >= 0 else .Negative
+ src = internal_abs(src)
#no_bounds_check for src != 0 {
- dest.digit[dest.used] = DIGIT(src) & _MASK;
- dest.used += 1;
- src >>= _DIGIT_BITS;
+ dest.digit[dest.used] = DIGIT(src) & _MASK
+ dest.used += 1
+ src >>= _DIGIT_BITS
}
- internal_zero_unused(dest);
- return nil;
+ internal_zero_unused(dest)
+ return nil
}
-internal_set :: proc { internal_int_set_from_integer, internal_int_copy };
+internal_set :: proc { internal_int_set_from_integer, internal_int_copy }
internal_copy_digits :: #force_inline proc(dest, src: ^Int, digits: int, offset := int(0)) -> (err: Error) {
#force_inline internal_error_if_immutable(dest) or_return;
@@ -1700,43 +1700,43 @@ internal_copy_digits :: #force_inline proc(dest, src: ^Int, digits: int, offset
/*
If dest == src, do nothing
*/
- return #force_inline _private_copy_digits(dest, src, digits, offset);
+ return #force_inline _private_copy_digits(dest, src, digits, offset)
}
/*
Copy one `Int` to another.
*/
internal_int_copy :: proc(dest, src: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
If dest == src, do nothing
*/
if (dest == src) { return nil; }
- internal_error_if_immutable(dest) or_return;
+ internal_error_if_immutable(dest) or_return
/*
Grow `dest` to fit `src`.
If `dest` is not yet initialized, it will be using `allocator`.
*/
- needed := src.used if minimize else max(src.used, _DEFAULT_DIGIT_COUNT);
+ needed := src.used if minimize else max(src.used, _DEFAULT_DIGIT_COUNT)
- internal_grow(dest, needed, minimize) or_return;
+ internal_grow(dest, needed, minimize) or_return
/*
Copy everything over and zero high digits.
*/
- internal_copy_digits(dest, src, src.used);
+ internal_copy_digits(dest, src, src.used)
- dest.used = src.used;
- dest.sign = src.sign;
- dest.flags = src.flags &~ {.Immutable};
+ dest.used = src.used
+ dest.sign = src.sign
+ dest.flags = src.flags &~ {.Immutable}
- internal_zero_unused(dest);
- return nil;
+ internal_zero_unused(dest)
+ return nil
}
-internal_copy :: proc { internal_int_copy, };
+internal_copy :: proc { internal_int_copy, }
/*
In normal code, you can also write `a, b = b, a`.
@@ -1744,80 +1744,80 @@ internal_copy :: proc { internal_int_copy, };
This helper swaps completely.
*/
internal_int_swap :: #force_inline proc(a, b: ^Int) {
- a := a; b := b;
+ a := a; b := b
- a.used, b.used = b.used, a.used;
- a.sign, b.sign = b.sign, a.sign;
- a.digit, b.digit = b.digit, a.digit;
+ a.used, b.used = b.used, a.used
+ a.sign, b.sign = b.sign, a.sign
+ a.digit, b.digit = b.digit, a.digit
}
-internal_swap :: proc { internal_int_swap, };
+internal_swap :: proc { internal_int_swap, }
/*
Set `dest` to |`src`|.
*/
internal_int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
If `dest == src`, just fix `dest`'s sign.
*/
if (dest == src) {
- dest.sign = .Zero_or_Positive;
- return nil;
+ dest.sign = .Zero_or_Positive
+ return nil
}
/*
Copy `src` to `dest`
*/
- internal_copy(dest, src) or_return;
+ internal_copy(dest, src) or_return
/*
Fix sign.
*/
- dest.sign = .Zero_or_Positive;
- return nil;
+ dest.sign = .Zero_or_Positive
+ return nil
}
internal_platform_abs :: proc(n: $T) -> T where intrinsics.type_is_integer(T) {
- return n if n >= 0 else -n;
+ return n if n >= 0 else -n
}
-internal_abs :: proc{ internal_int_abs, internal_platform_abs, };
+internal_abs :: proc{ internal_int_abs, internal_platform_abs, }
/*
Set `dest` to `-src`.
*/
internal_int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
If `dest == src`, just fix `dest`'s sign.
*/
- sign := Sign.Negative;
+ sign := Sign.Negative
if #force_inline internal_is_zero(src) || #force_inline internal_is_negative(src) {
- sign = .Zero_or_Positive;
+ sign = .Zero_or_Positive
}
if dest == src {
- dest.sign = sign;
- return nil;
+ dest.sign = sign
+ return nil
}
/*
Copy `src` to `dest`
*/
- internal_copy(dest, src) or_return;
+ internal_copy(dest, src) or_return
/*
Fix sign.
*/
- dest.sign = sign;
- return nil;
+ dest.sign = sign
+ return nil
}
-internal_neg :: proc { internal_int_neg, };
+internal_neg :: proc { internal_int_neg, }
/*
hac 14.61, pp608.
*/
internal_int_inverse_modulo :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
For all n in N and n > 0, n = 0 mod 1.
*/
@@ -1833,15 +1833,15 @@ internal_int_inverse_modulo :: proc(dest, a, b: ^Int, allocator := context.alloc
*/
if internal_is_odd(b) { return _private_inverse_modulo_odd(dest, a, b); }
- return _private_inverse_modulo(dest, a, b);
+ return _private_inverse_modulo(dest, a, b)
}
-internal_invmod :: proc{ internal_int_inverse_modulo, };
+internal_invmod :: proc{ internal_int_inverse_modulo, }
/*
Helpers to extract values from the `Int`.
*/
internal_int_bitfield_extract_single :: proc(a: ^Int, offset: int) -> (bit: _WORD, err: Error) {
- return #force_inline int_bitfield_extract(a, offset, 1);
+ return #force_inline int_bitfield_extract(a, offset, 1)
}
internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WORD, err: Error) #no_bounds_check {
@@ -1849,10 +1849,10 @@ internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WOR
Early out for single bit.
*/
if count == 1 {
- limb := offset / _DIGIT_BITS;
+ limb := offset / _DIGIT_BITS
if limb < 0 || limb >= a.used { return 0, .Invalid_Argument; }
- i := _WORD(1 << _WORD((offset % _DIGIT_BITS)));
- return 1 if ((_WORD(a.digit[limb]) & i) != 0) else 0, nil;
+ i := _WORD(1 << _WORD((offset % _DIGIT_BITS)))
+ return 1 if ((_WORD(a.digit[limb]) & i) != 0) else 0, nil
}
if count > _WORD_BITS || count < 1 { return 0, .Invalid_Argument; }
@@ -1869,34 +1869,34 @@ internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WOR
e.g. offset: 40, count: 120 = bits 40..59, 0..59, 0..39
*/
- limb := offset / _DIGIT_BITS;
- bits_left := count;
- bits_offset := offset % _DIGIT_BITS;
+ limb := offset / _DIGIT_BITS
+ bits_left := count
+ bits_offset := offset % _DIGIT_BITS
- num_bits := min(bits_left, _DIGIT_BITS - bits_offset);
+ num_bits := min(bits_left, _DIGIT_BITS - bits_offset)
- shift := offset % _DIGIT_BITS;
- mask := (_WORD(1) << uint(num_bits)) - 1;
- res = (_WORD(a.digit[limb]) >> uint(shift)) & mask;
+ shift := offset % _DIGIT_BITS
+ mask := (_WORD(1) << uint(num_bits)) - 1
+ res = (_WORD(a.digit[limb]) >> uint(shift)) & mask
- bits_left -= num_bits;
+ bits_left -= num_bits
if bits_left == 0 { return res, nil; }
- res_shift := num_bits;
- num_bits = min(bits_left, _DIGIT_BITS);
- mask = (1 << uint(num_bits)) - 1;
+ res_shift := num_bits
+ num_bits = min(bits_left, _DIGIT_BITS)
+ mask = (1 << uint(num_bits)) - 1
- res |= (_WORD(a.digit[limb + 1]) & mask) << uint(res_shift);
+ res |= (_WORD(a.digit[limb + 1]) & mask) << uint(res_shift)
- bits_left -= num_bits;
+ bits_left -= num_bits
if bits_left == 0 { return res, nil; }
- mask = (1 << uint(bits_left)) - 1;
- res_shift += _DIGIT_BITS;
+ mask = (1 << uint(bits_left)) - 1
+ res_shift += _DIGIT_BITS
- res |= (_WORD(a.digit[limb + 2]) & mask) << uint(res_shift);
+ res |= (_WORD(a.digit[limb + 2]) & mask) << uint(res_shift)
- return res, nil;
+ return res, nil
}
/*
@@ -1906,169 +1906,169 @@ internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WOR
Assumes `a` not to be `nil`, and to have already been initialized.
*/
internal_int_shrink :: proc(a: ^Int) -> (err: Error) {
- needed := max(_MIN_DIGIT_COUNT, a.used);
+ needed := max(_MIN_DIGIT_COUNT, a.used)
if a.used != needed { return internal_grow(a, needed, true); }
- return nil;
+ return nil
}
-internal_shrink :: proc { internal_int_shrink, };
+internal_shrink :: proc { internal_int_shrink, }
internal_int_grow :: proc(a: ^Int, digits: int, allow_shrink := false, allocator := context.allocator) -> (err: Error) {
- raw := transmute(mem.Raw_Dynamic_Array)a.digit;
+ raw := transmute(mem.Raw_Dynamic_Array)a.digit
/*
We need at least _MIN_DIGIT_COUNT or a.used digits, whichever is bigger.
The caller is asking for `digits`. Let's be accomodating.
*/
- needed := max(_MIN_DIGIT_COUNT, a.used, digits);
+ needed := max(_MIN_DIGIT_COUNT, a.used, digits)
if !allow_shrink {
- needed = max(needed, raw.cap);
+ needed = max(needed, raw.cap)
}
/*
If not yet iniialized, initialize the `digit` backing with the allocator we were passed.
*/
if raw.cap == 0 {
- a.digit = make([dynamic]DIGIT, needed, allocator);
+ a.digit = make([dynamic]DIGIT, needed, allocator)
} else if raw.cap != needed {
/*
`[dynamic]DIGIT` already knows what allocator was used for it, so resize will do the right thing.
*/
- resize(&a.digit, needed);
+ resize(&a.digit, needed)
}
/*
Let's see if the allocation/resize worked as expected.
*/
if len(a.digit) != needed {
- return .Out_Of_Memory;
+ return .Out_Of_Memory
}
- return nil;
+ return nil
}
-internal_grow :: proc { internal_int_grow, };
+internal_grow :: proc { internal_int_grow, }
/*
Clear `Int` and resize it to the default size.
Assumes `a` not to be `nil`.
*/
internal_int_clear :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- raw := transmute(mem.Raw_Dynamic_Array)a.digit;
+ raw := transmute(mem.Raw_Dynamic_Array)a.digit
if raw.cap != 0 {
- mem.zero_slice(a.digit[:a.used]);
+ mem.zero_slice(a.digit[:a.used])
}
- a.sign = .Zero_or_Positive;
- a.used = 0;
+ a.sign = .Zero_or_Positive
+ a.used = 0
- return #force_inline internal_grow(a, a.used, minimize, allocator);
+ return #force_inline internal_grow(a, a.used, minimize, allocator)
}
-internal_clear :: proc { internal_int_clear, };
-internal_zero :: internal_clear;
+internal_clear :: proc { internal_int_clear, }
+internal_zero :: internal_clear
/*
Set the `Int` to 1 and optionally shrink it to the minimum backing size.
*/
internal_int_one :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- return internal_copy(a, INT_ONE, minimize, allocator);
+ return internal_copy(a, INT_ONE, minimize, allocator)
}
-internal_one :: proc { internal_int_one, };
+internal_one :: proc { internal_int_one, }
/*
Set the `Int` to -1 and optionally shrink it to the minimum backing size.
*/
internal_int_minus_one :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- return internal_copy(a, INT_MINUS_ONE, minimize, allocator);
+ return internal_copy(a, INT_MINUS_ONE, minimize, allocator)
}
-internal_minus_one :: proc { internal_int_minus_one, };
+internal_minus_one :: proc { internal_int_minus_one, }
/*
Set the `Int` to Inf and optionally shrink it to the minimum backing size.
*/
internal_int_inf :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- return internal_copy(a, INT_INF, minimize, allocator);
+ return internal_copy(a, INT_INF, minimize, allocator)
}
-internal_inf :: proc { internal_int_inf, };
+internal_inf :: proc { internal_int_inf, }
/*
Set the `Int` to -Inf and optionally shrink it to the minimum backing size.
*/
internal_int_minus_inf :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- return internal_copy(a, INT_MINUS_INF, minimize, allocator);
+ return internal_copy(a, INT_MINUS_INF, minimize, allocator)
}
-internal_minus_inf :: proc { internal_int_inf, };
+internal_minus_inf :: proc { internal_int_inf, }
/*
Set the `Int` to NaN and optionally shrink it to the minimum backing size.
*/
internal_int_nan :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) {
- return internal_copy(a, INT_NAN, minimize, allocator);
+ return internal_copy(a, INT_NAN, minimize, allocator)
}
-internal_nan :: proc { internal_int_nan, };
+internal_nan :: proc { internal_int_nan, }
internal_int_power_of_two :: proc(a: ^Int, power: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if power < 0 || power > _MAX_BIT_COUNT { return .Invalid_Argument; }
/*
Grow to accomodate the single bit.
*/
- a.used = (power / _DIGIT_BITS) + 1;
- internal_grow(a, a.used) or_return;
+ a.used = (power / _DIGIT_BITS) + 1
+ internal_grow(a, a.used) or_return
/*
Zero the entirety.
*/
- mem.zero_slice(a.digit[:]);
+ mem.zero_slice(a.digit[:])
/*
Set the bit.
*/
- a.digit[power / _DIGIT_BITS] = 1 << uint((power % _DIGIT_BITS));
- return nil;
+ a.digit[power / _DIGIT_BITS] = 1 << uint((power % _DIGIT_BITS))
+ return nil
}
internal_int_get_u128 :: proc(a: ^Int) -> (res: u128, err: Error) {
- return internal_int_get(a, u128);
+ return internal_int_get(a, u128)
}
-internal_get_u128 :: proc { internal_int_get_u128, };
+internal_get_u128 :: proc { internal_int_get_u128, }
internal_int_get_i128 :: proc(a: ^Int) -> (res: i128, err: Error) {
- return internal_int_get(a, i128);
+ return internal_int_get(a, i128)
}
-internal_get_i128 :: proc { internal_int_get_i128, };
+internal_get_i128 :: proc { internal_int_get_i128, }
internal_int_get_u64 :: proc(a: ^Int) -> (res: u64, err: Error) {
- return internal_int_get(a, u64);
+ return internal_int_get(a, u64)
}
-internal_get_u64 :: proc { internal_int_get_u64, };
+internal_get_u64 :: proc { internal_int_get_u64, }
internal_int_get_i64 :: proc(a: ^Int) -> (res: i64, err: Error) {
- return internal_int_get(a, i64);
+ return internal_int_get(a, i64)
}
-internal_get_i64 :: proc { internal_int_get_i64, };
+internal_get_i64 :: proc { internal_int_get_i64, }
internal_int_get_u32 :: proc(a: ^Int) -> (res: u32, err: Error) {
- return internal_int_get(a, u32);
+ return internal_int_get(a, u32)
}
-internal_get_u32 :: proc { internal_int_get_u32, };
+internal_get_u32 :: proc { internal_int_get_u32, }
internal_int_get_i32 :: proc(a: ^Int) -> (res: i32, err: Error) {
- return internal_int_get(a, i32);
+ return internal_int_get(a, i32)
}
-internal_get_i32 :: proc { internal_int_get_i32, };
+internal_get_i32 :: proc { internal_int_get_i32, }
/*
TODO: Think about using `count_bits` to check if the value could be returned completely,
and maybe return max(T), .Integer_Overflow if not?
*/
internal_int_get :: proc(a: ^Int, $T: typeid) -> (res: T, err: Error) where intrinsics.type_is_integer(T) {
- size_in_bits := int(size_of(T) * 8);
- i := int((size_in_bits + _DIGIT_BITS - 1) / _DIGIT_BITS);
- i = min(int(a.used), i);
+ size_in_bits := int(size_of(T) * 8)
+ i := int((size_in_bits + _DIGIT_BITS - 1) / _DIGIT_BITS)
+ i = min(int(a.used), i)
#no_bounds_check for ; i >= 0; i -= 1 {
- res <<= uint(0) if size_in_bits <= _DIGIT_BITS else _DIGIT_BITS;
- res |= T(a.digit[i]);
+ res <<= uint(0) if size_in_bits <= _DIGIT_BITS else _DIGIT_BITS
+ res |= T(a.digit[i])
if size_in_bits <= _DIGIT_BITS {
- break;
+ break
};
}
@@ -2076,31 +2076,31 @@ internal_int_get :: proc(a: ^Int, $T: typeid) -> (res: T, err: Error) where intr
/*
Mask off sign bit.
*/
- res ~= 1 << uint(size_in_bits - 1);
+ res ~= 1 << uint(size_in_bits - 1)
/*
Set the sign.
*/
if a.sign == .Negative { res = -res; }
}
- return;
+ return
}
-internal_get :: proc { internal_int_get, };
+internal_get :: proc { internal_int_get, }
internal_int_get_float :: proc(a: ^Int) -> (res: f64, err: Error) {
/*
log2(max(f64)) is approximately 1020, or 17 legs with the 64-bit storage.
*/
- legs :: 1020 / _DIGIT_BITS;
- l := min(a.used, legs);
- fac := f64(1 << _DIGIT_BITS);
- d := 0.0;
+ legs :: 1020 / _DIGIT_BITS
+ l := min(a.used, legs)
+ fac := f64(1 << _DIGIT_BITS)
+ d := 0.0
#no_bounds_check for i := l; i >= 0; i -= 1 {
- d = (d * fac) + f64(a.digit[i]);
+ d = (d * fac) + f64(a.digit[i])
}
- res = -d if a.sign == .Negative else d;
- return;
+ res = -d if a.sign == .Negative else d
+ return
}
/*
@@ -2114,278 +2114,278 @@ internal_int_get_float :: proc(a: ^Int) -> (res: f64, err: Error) {
2's complement `and`, returns `dest = a & b;`
*/
internal_int_and :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- used := max(a.used, b.used) + 1;
+ used := max(a.used, b.used) + 1
/*
Grow the destination to accomodate the result.
*/
- internal_grow(dest, used) or_return;
+ internal_grow(dest, used) or_return
- neg_a := #force_inline internal_is_negative(a);
- neg_b := #force_inline internal_is_negative(b);
- neg := neg_a && neg_b;
+ neg_a := #force_inline internal_is_negative(a)
+ neg_b := #force_inline internal_is_negative(b)
+ neg := neg_a && neg_b
- ac, bc, cc := DIGIT(1), DIGIT(1), DIGIT(1);
+ ac, bc, cc := DIGIT(1), DIGIT(1), DIGIT(1)
#no_bounds_check for i := 0; i < used; i += 1 {
- x, y: DIGIT;
+ x, y: DIGIT
/*
Convert to 2's complement if negative.
*/
if neg_a {
- ac += _MASK if i >= a.used else (~a.digit[i] & _MASK);
- x = ac & _MASK;
- ac >>= _DIGIT_BITS;
+ ac += _MASK if i >= a.used else (~a.digit[i] & _MASK)
+ x = ac & _MASK
+ ac >>= _DIGIT_BITS
} else {
- x = 0 if i >= a.used else a.digit[i];
+ x = 0 if i >= a.used else a.digit[i]
}
/*
Convert to 2's complement if negative.
*/
if neg_b {
- bc += _MASK if i >= b.used else (~b.digit[i] & _MASK);
- y = bc & _MASK;
- bc >>= _DIGIT_BITS;
+ bc += _MASK if i >= b.used else (~b.digit[i] & _MASK)
+ y = bc & _MASK
+ bc >>= _DIGIT_BITS
} else {
- y = 0 if i >= b.used else b.digit[i];
+ y = 0 if i >= b.used else b.digit[i]
}
- dest.digit[i] = x & y;
+ dest.digit[i] = x & y
/*
Convert to to sign-magnitude if negative.
*/
if neg {
- cc += ~dest.digit[i] & _MASK;
- dest.digit[i] = cc & _MASK;
- cc >>= _DIGIT_BITS;
+ cc += ~dest.digit[i] & _MASK
+ dest.digit[i] = cc & _MASK
+ cc >>= _DIGIT_BITS
}
}
- dest.used = used;
- dest.sign = .Negative if neg else .Zero_or_Positive;
- return internal_clamp(dest);
+ dest.used = used
+ dest.sign = .Negative if neg else .Zero_or_Positive
+ return internal_clamp(dest)
}
-internal_and :: proc { internal_int_and, };
+internal_and :: proc { internal_int_and, }
/*
2's complement `or`, returns `dest = a | b;`
*/
internal_int_or :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- used := max(a.used, b.used) + 1;
+ used := max(a.used, b.used) + 1
/*
Grow the destination to accomodate the result.
*/
- internal_grow(dest, used) or_return;
+ internal_grow(dest, used) or_return
- neg_a := #force_inline internal_is_negative(a);
- neg_b := #force_inline internal_is_negative(b);
- neg := neg_a || neg_b;
+ neg_a := #force_inline internal_is_negative(a)
+ neg_b := #force_inline internal_is_negative(b)
+ neg := neg_a || neg_b
- ac, bc, cc := DIGIT(1), DIGIT(1), DIGIT(1);
+ ac, bc, cc := DIGIT(1), DIGIT(1), DIGIT(1)
#no_bounds_check for i := 0; i < used; i += 1 {
- x, y: DIGIT;
+ x, y: DIGIT
/*
Convert to 2's complement if negative.
*/
if neg_a {
- ac += _MASK if i >= a.used else (~a.digit[i] & _MASK);
- x = ac & _MASK;
- ac >>= _DIGIT_BITS;
+ ac += _MASK if i >= a.used else (~a.digit[i] & _MASK)
+ x = ac & _MASK
+ ac >>= _DIGIT_BITS
} else {
- x = 0 if i >= a.used else a.digit[i];
+ x = 0 if i >= a.used else a.digit[i]
}
/*
Convert to 2's complement if negative.
*/
if neg_b {
- bc += _MASK if i >= b.used else (~b.digit[i] & _MASK);
- y = bc & _MASK;
- bc >>= _DIGIT_BITS;
+ bc += _MASK if i >= b.used else (~b.digit[i] & _MASK)
+ y = bc & _MASK
+ bc >>= _DIGIT_BITS
} else {
- y = 0 if i >= b.used else b.digit[i];
+ y = 0 if i >= b.used else b.digit[i]
}
- dest.digit[i] = x | y;
+ dest.digit[i] = x | y
/*
Convert to to sign-magnitude if negative.
*/
if neg {
- cc += ~dest.digit[i] & _MASK;
- dest.digit[i] = cc & _MASK;
- cc >>= _DIGIT_BITS;
+ cc += ~dest.digit[i] & _MASK
+ dest.digit[i] = cc & _MASK
+ cc >>= _DIGIT_BITS
}
}
- dest.used = used;
- dest.sign = .Negative if neg else .Zero_or_Positive;
- return internal_clamp(dest);
+ dest.used = used
+ dest.sign = .Negative if neg else .Zero_or_Positive
+ return internal_clamp(dest)
}
-internal_or :: proc { internal_int_or, };
+internal_or :: proc { internal_int_or, }
/*
2's complement `xor`, returns `dest = a ~ b;`
*/
internal_int_xor :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- used := max(a.used, b.used) + 1;
+ used := max(a.used, b.used) + 1
/*
Grow the destination to accomodate the result.
*/
- internal_grow(dest, used) or_return;
+ internal_grow(dest, used) or_return
- neg_a := #force_inline internal_is_negative(a);
- neg_b := #force_inline internal_is_negative(b);
- neg := neg_a != neg_b;
+ neg_a := #force_inline internal_is_negative(a)
+ neg_b := #force_inline internal_is_negative(b)
+ neg := neg_a != neg_b
- ac, bc, cc := DIGIT(1), DIGIT(1), DIGIT(1);
+ ac, bc, cc := DIGIT(1), DIGIT(1), DIGIT(1)
#no_bounds_check for i := 0; i < used; i += 1 {
- x, y: DIGIT;
+ x, y: DIGIT
/*
Convert to 2's complement if negative.
*/
if neg_a {
- ac += _MASK if i >= a.used else (~a.digit[i] & _MASK);
- x = ac & _MASK;
- ac >>= _DIGIT_BITS;
+ ac += _MASK if i >= a.used else (~a.digit[i] & _MASK)
+ x = ac & _MASK
+ ac >>= _DIGIT_BITS
} else {
- x = 0 if i >= a.used else a.digit[i];
+ x = 0 if i >= a.used else a.digit[i]
}
/*
Convert to 2's complement if negative.
*/
if neg_b {
- bc += _MASK if i >= b.used else (~b.digit[i] & _MASK);
- y = bc & _MASK;
- bc >>= _DIGIT_BITS;
+ bc += _MASK if i >= b.used else (~b.digit[i] & _MASK)
+ y = bc & _MASK
+ bc >>= _DIGIT_BITS
} else {
- y = 0 if i >= b.used else b.digit[i];
+ y = 0 if i >= b.used else b.digit[i]
}
- dest.digit[i] = x ~ y;
+ dest.digit[i] = x ~ y
/*
Convert to to sign-magnitude if negative.
*/
if neg {
- cc += ~dest.digit[i] & _MASK;
- dest.digit[i] = cc & _MASK;
- cc >>= _DIGIT_BITS;
+ cc += ~dest.digit[i] & _MASK
+ dest.digit[i] = cc & _MASK
+ cc >>= _DIGIT_BITS
}
}
- dest.used = used;
- dest.sign = .Negative if neg else .Zero_or_Positive;
- return internal_clamp(dest);
+ dest.used = used
+ dest.sign = .Negative if neg else .Zero_or_Positive
+ return internal_clamp(dest)
}
-internal_xor :: proc { internal_int_xor, };
+internal_xor :: proc { internal_int_xor, }
/*
dest = ~src
*/
internal_int_complement :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
/*
Temporarily fix sign.
*/
- old_sign := src.sign;
+ old_sign := src.sign
- neg := #force_inline internal_is_zero(src) || #force_inline internal_is_positive(src);
+ neg := #force_inline internal_is_zero(src) || #force_inline internal_is_positive(src)
- src.sign = .Negative if neg else .Zero_or_Positive;
+ src.sign = .Negative if neg else .Zero_or_Positive
- err = #force_inline internal_sub(dest, src, 1);
+ err = #force_inline internal_sub(dest, src, 1)
/*
Restore sign.
*/
- src.sign = old_sign;
+ src.sign = old_sign
- return err;
+ return err
}
-internal_complement :: proc { internal_int_complement, };
+internal_complement :: proc { internal_int_complement, }
/*
quotient, remainder := numerator >> bits;
`remainder` is allowed to be passed a `nil`, in which case `mod` won't be computed.
*/
internal_int_shrmod :: proc(quotient, remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- bits := bits;
+ bits := bits
if bits < 0 { return .Invalid_Argument; }
- internal_copy(quotient, numerator) or_return;
+ internal_copy(quotient, numerator) or_return
/*
Shift right by a certain bit count (store quotient and optional remainder.)
`numerator` should not be used after this.
*/
if remainder != nil {
- internal_int_mod_bits(remainder, numerator, bits) or_return;
+ internal_int_mod_bits(remainder, numerator, bits) or_return
}
/*
Shift by as many digits in the bit count.
*/
if bits >= _DIGIT_BITS {
- internal_shr_digit(quotient, bits / _DIGIT_BITS) or_return;
+ internal_shr_digit(quotient, bits / _DIGIT_BITS) or_return
}
/*
Shift any bit count < _DIGIT_BITS.
*/
- bits %= _DIGIT_BITS;
+ bits %= _DIGIT_BITS
if bits != 0 {
- mask := DIGIT(1 << uint(bits)) - 1;
- shift := DIGIT(_DIGIT_BITS - bits);
- carry := DIGIT(0);
+ mask := DIGIT(1 << uint(bits)) - 1
+ shift := DIGIT(_DIGIT_BITS - bits)
+ carry := DIGIT(0)
#no_bounds_check for x := quotient.used - 1; x >= 0; x -= 1 {
/*
Get the lower bits of this word in a temp.
*/
- fwd_carry := quotient.digit[x] & mask;
+ fwd_carry := quotient.digit[x] & mask
/*
Shift the current word and mix in the carry bits from the previous word.
*/
- quotient.digit[x] = (quotient.digit[x] >> uint(bits)) | (carry << shift);
+ quotient.digit[x] = (quotient.digit[x] >> uint(bits)) | (carry << shift)
/*
Update carry from forward carry.
*/
- carry = fwd_carry;
+ carry = fwd_carry
}
}
- return internal_clamp(numerator);
+ return internal_clamp(numerator)
}
-internal_shrmod :: proc { internal_int_shrmod, };
+internal_shrmod :: proc { internal_int_shrmod, }
internal_int_shr :: proc(dest, source: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {
- return #force_inline internal_shrmod(dest, nil, source, bits, allocator);
+ return #force_inline internal_shrmod(dest, nil, source, bits, allocator)
}
-internal_shr :: proc { internal_int_shr, };
+internal_shr :: proc { internal_int_shr, }
/*
Shift right by `digits` * _DIGIT_BITS bits.
*/
internal_int_shr_digit :: proc(quotient: ^Int, digits: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if digits <= 0 { return nil; }
@@ -2404,88 +2404,88 @@ internal_int_shr_digit :: proc(quotient: ^Int, digits: int, allocator := context
*/
#no_bounds_check for x := 0; x < (quotient.used - digits); x += 1 {
- quotient.digit[x] = quotient.digit[x + digits];
+ quotient.digit[x] = quotient.digit[x + digits]
}
- quotient.used -= digits;
- internal_zero_unused(quotient);
- return internal_clamp(quotient);
+ quotient.used -= digits
+ internal_zero_unused(quotient)
+ return internal_clamp(quotient)
}
-internal_shr_digit :: proc { internal_int_shr_digit, };
+internal_shr_digit :: proc { internal_int_shr_digit, }
/*
Shift right by a certain bit count with sign extension.
*/
internal_int_shr_signed :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if src.sign == .Zero_or_Positive {
- return internal_shr(dest, src, bits);
+ return internal_shr(dest, src, bits)
}
- internal_int_add_digit(dest, src, DIGIT(1)) or_return;
- internal_shr(dest, dest, bits) or_return;
- return internal_sub(dest, src, DIGIT(1));
+ internal_int_add_digit(dest, src, DIGIT(1)) or_return
+ internal_shr(dest, dest, bits) or_return
+ return internal_sub(dest, src, DIGIT(1))
}
-internal_shr_signed :: proc { internal_int_shr_signed, };
+internal_shr_signed :: proc { internal_int_shr_signed, }
/*
Shift left by a certain bit count.
*/
internal_int_shl :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- bits := bits;
+ bits := bits
if bits < 0 { return .Invalid_Argument; }
- internal_copy(dest, src) or_return;
+ internal_copy(dest, src) or_return
/*
Grow `dest` to accommodate the additional bits.
*/
- digits_needed := dest.used + (bits / _DIGIT_BITS) + 1;
- internal_grow(dest, digits_needed) or_return;
- dest.used = digits_needed;
+ digits_needed := dest.used + (bits / _DIGIT_BITS) + 1
+ internal_grow(dest, digits_needed) or_return
+ dest.used = digits_needed
/*
Shift by as many digits in the bit count as we have.
*/
if bits >= _DIGIT_BITS {
- internal_shl_digit(dest, bits / _DIGIT_BITS) or_return;
+ internal_shl_digit(dest, bits / _DIGIT_BITS) or_return
}
/*
Shift any remaining bit count < _DIGIT_BITS
*/
- bits %= _DIGIT_BITS;
+ bits %= _DIGIT_BITS
if bits != 0 {
- mask := (DIGIT(1) << uint(bits)) - DIGIT(1);
- shift := DIGIT(_DIGIT_BITS - bits);
- carry := DIGIT(0);
+ mask := (DIGIT(1) << uint(bits)) - DIGIT(1)
+ shift := DIGIT(_DIGIT_BITS - bits)
+ carry := DIGIT(0)
#no_bounds_check for x:= 0; x < dest.used; x+= 1 {
- fwd_carry := (dest.digit[x] >> shift) & mask;
- dest.digit[x] = (dest.digit[x] << uint(bits) | carry) & _MASK;
- carry = fwd_carry;
+ fwd_carry := (dest.digit[x] >> shift) & mask
+ dest.digit[x] = (dest.digit[x] << uint(bits) | carry) & _MASK
+ carry = fwd_carry
}
/*
Use final carry.
*/
if carry != 0 {
- dest.digit[dest.used] = carry;
- dest.used += 1;
+ dest.digit[dest.used] = carry
+ dest.used += 1
}
}
- return internal_clamp(dest);
+ return internal_clamp(dest)
}
-internal_shl :: proc { internal_int_shl, };
+internal_shl :: proc { internal_int_shl, }
/*
Shift left by `digits` * _DIGIT_BITS bits.
*/
internal_int_shl_digit :: proc(quotient: ^Int, digits: int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if digits <= 0 { return nil; }
@@ -2493,7 +2493,7 @@ internal_int_shl_digit :: proc(quotient: ^Int, digits: int, allocator := context
No need to shift a zero.
*/
if #force_inline internal_is_zero(quotient) {
- return nil;
+ return nil
}
/*
@@ -2510,14 +2510,14 @@ internal_int_shl_digit :: proc(quotient: ^Int, digits: int, allocator := context
except the window goes the other way around.
*/
#no_bounds_check for x := quotient.used; x > 0; x -= 1 {
- quotient.digit[x+digits-1] = quotient.digit[x-1];
+ quotient.digit[x+digits-1] = quotient.digit[x-1]
}
- quotient.used += digits;
- mem.zero_slice(quotient.digit[:digits]);
- return nil;
+ quotient.used += digits
+ mem.zero_slice(quotient.digit[:digits])
+ return nil
}
-internal_shl_digit :: proc { internal_int_shl_digit, };
+internal_shl_digit :: proc { internal_int_shl_digit, }
/*
Count bits in an `Int`.
@@ -2531,13 +2531,13 @@ internal_count_bits :: proc(a: ^Int) -> (count: int) {
/*
Get the number of DIGITs and use it.
*/
- count = (a.used - 1) * _DIGIT_BITS;
+ count = (a.used - 1) * _DIGIT_BITS
/*
Take the last DIGIT and count the bits in it.
*/
- clz := int(intrinsics.count_leading_zeros(a.digit[a.used - 1]));
- count += (_DIGIT_TYPE_BITS - clz);
- return;
+ clz := int(intrinsics.count_leading_zeros(a.digit[a.used - 1]))
+ count += (_DIGIT_TYPE_BITS - clz)
+ return
}
/*
@@ -2555,117 +2555,117 @@ internal_int_count_lsb :: proc(a: ^Int) -> (count: int, err: Error) {
/*
Scan lower digits until non-zero.
*/
- x: int;
+ x: int
#no_bounds_check for x = 0; x < a.used && a.digit[x] == 0; x += 1 {}
- q := a.digit[x];
- x *= _DIGIT_BITS;
- x += internal_count_lsb(q);
- return x, nil;
+ q := a.digit[x]
+ x *= _DIGIT_BITS
+ x += internal_count_lsb(q)
+ return x, nil
}
internal_platform_count_lsb :: #force_inline proc(a: $T) -> (count: int)
where intrinsics.type_is_integer(T) && intrinsics.type_is_unsigned(T) {
- return int(intrinsics.count_trailing_zeros(a)) if a > 0 else 0;
+ return int(intrinsics.count_trailing_zeros(a)) if a > 0 else 0
}
-internal_count_lsb :: proc { internal_int_count_lsb, internal_platform_count_lsb, };
+internal_count_lsb :: proc { internal_int_count_lsb, internal_platform_count_lsb, }
internal_int_random_digit :: proc(r: ^rnd.Rand = nil) -> (res: DIGIT) {
when _DIGIT_BITS == 60 { // DIGIT = u64
- return DIGIT(rnd.uint64(r)) & _MASK;
+ return DIGIT(rnd.uint64(r)) & _MASK
} else when _DIGIT_BITS == 28 { // DIGIT = u32
- return DIGIT(rnd.uint32(r)) & _MASK;
+ return DIGIT(rnd.uint32(r)) & _MASK
} else {
- panic("Unsupported DIGIT size.");
+ panic("Unsupported DIGIT size.")
}
- return 0; // We shouldn't get here.
+ return 0 // We shouldn't get here.
}
internal_int_rand :: proc(dest: ^Int, bits: int, r: ^rnd.Rand = nil, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- bits := bits;
+ bits := bits
if bits <= 0 { return .Invalid_Argument; }
- digits := bits / _DIGIT_BITS;
- bits %= _DIGIT_BITS;
+ digits := bits / _DIGIT_BITS
+ bits %= _DIGIT_BITS
if bits > 0 {
- digits += 1;
+ digits += 1
}
#force_inline internal_grow(dest, digits) or_return;
for i := 0; i < digits; i += 1 {
- dest.digit[i] = int_random_digit(r) & _MASK;
+ dest.digit[i] = int_random_digit(r) & _MASK
}
if bits > 0 {
- dest.digit[digits - 1] &= ((1 << uint(bits)) - 1);
+ dest.digit[digits - 1] &= ((1 << uint(bits)) - 1)
}
- dest.used = digits;
- return nil;
+ dest.used = digits
+ return nil
}
-internal_rand :: proc { internal_int_rand, };
+internal_rand :: proc { internal_int_rand, }
/*
Internal helpers.
*/
internal_assert_initialized :: proc(a: ^Int, loc := #caller_location) {
- assert(internal_is_initialized(a), "`Int` was not properly initialized.", loc);
+ assert(internal_is_initialized(a), "`Int` was not properly initialized.", loc)
}
internal_clear_if_uninitialized_single :: proc(arg: ^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
if ! #force_inline internal_is_initialized(arg) {
- return #force_inline internal_grow(arg, _DEFAULT_DIGIT_COUNT);
+ return #force_inline internal_grow(arg, _DEFAULT_DIGIT_COUNT)
}
- return err;
+ return err
}
internal_clear_if_uninitialized_multi :: proc(args: ..^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
for i in args {
if ! #force_inline internal_is_initialized(i) {
- e := #force_inline internal_grow(i, _DEFAULT_DIGIT_COUNT);
+ e := #force_inline internal_grow(i, _DEFAULT_DIGIT_COUNT)
if e != nil { err = e; }
}
}
- return err;
+ return err
}
-internal_clear_if_uninitialized :: proc {internal_clear_if_uninitialized_single, internal_clear_if_uninitialized_multi, };
+internal_clear_if_uninitialized :: proc {internal_clear_if_uninitialized_single, internal_clear_if_uninitialized_multi, }
internal_error_if_immutable_single :: proc(arg: ^Int) -> (err: Error) {
if arg != nil && .Immutable in arg.flags { return .Assignment_To_Immutable; }
- return nil;
+ return nil
}
internal_error_if_immutable_multi :: proc(args: ..^Int) -> (err: Error) {
for i in args {
if i != nil && .Immutable in i.flags { return .Assignment_To_Immutable; }
}
- return nil;
+ return nil
}
-internal_error_if_immutable :: proc {internal_error_if_immutable_single, internal_error_if_immutable_multi, };
+internal_error_if_immutable :: proc {internal_error_if_immutable_single, internal_error_if_immutable_multi, }
/*
Allocates several `Int`s at once.
*/
internal_int_init_multi :: proc(integers: ..^Int, allocator := context.allocator) -> (err: Error) {
- context.allocator = allocator;
+ context.allocator = allocator
- integers := integers;
+ integers := integers
for a in &integers {
- internal_clear(a) or_return;
+ internal_clear(a) or_return
}
- return nil;
+ return nil
}
-internal_init_multi :: proc { internal_int_init_multi, };
+internal_init_multi :: proc { internal_int_init_multi, }
/*
Trim unused digits.
@@ -2678,7 +2678,7 @@ internal_clamp :: proc(a: ^Int) -> (err: Error) {
if #force_inline internal_is_zero(a) { a.sign = .Zero_or_Positive; }
- return nil;
+ return nil
}
@@ -2686,21 +2686,21 @@ internal_int_zero_unused :: #force_inline proc(dest: ^Int, old_used := -1) {
/*
If we don't pass the number of previously used DIGITs, we zero all remaining ones.
*/
- zero_count: int;
+ zero_count: int
if old_used == -1 {
- zero_count = len(dest.digit) - dest.used;
+ zero_count = len(dest.digit) - dest.used
} else {
- zero_count = old_used - dest.used;
+ zero_count = old_used - dest.used
}
/*
Zero remainder.
*/
if zero_count > 0 && dest.used < len(dest.digit) {
- mem.zero_slice(dest.digit[dest.used:][:zero_count]);
+ mem.zero_slice(dest.digit[dest.used:][:zero_count])
}
}
-internal_zero_unused :: proc { internal_int_zero_unused, };
+internal_zero_unused :: proc { internal_int_zero_unused, }
/*
========================== End of low-level routines ==========================