diff options
| author | Jeroen van Rijn <Kelimion@users.noreply.github.com> | 2021-08-10 17:17:22 +0200 |
|---|---|---|
| committer | Jeroen van Rijn <Kelimion@users.noreply.github.com> | 2021-08-11 20:59:54 +0200 |
| commit | 1f91a2fe653137337411aaab4959f51a2dd710e1 (patch) | |
| tree | c40d5be56757f1f25cb925bb87465866ba43246f /core/math/big | |
| parent | 19ff27788c329e6d05659edb0dcee5c1550263d0 (diff) | |
big: Finish refactor.
Diffstat (limited to 'core/math/big')
| -rw-r--r-- | core/math/big/helpers.odin | 108 | ||||
| -rw-r--r-- | core/math/big/internal.odin | 370 | ||||
| -rw-r--r-- | core/math/big/logical.odin | 47 | ||||
| -rw-r--r-- | core/math/big/prime.odin | 4 | ||||
| -rw-r--r-- | core/math/big/private.odin | 252 | ||||
| -rw-r--r-- | core/math/big/public.odin | 156 | ||||
| -rw-r--r-- | core/math/big/radix.odin | 62 | ||||
| -rw-r--r-- | core/math/big/test.odin | 38 | ||||
| -rw-r--r-- | core/math/big/test.py | 10 |
9 files changed, 602 insertions, 445 deletions
diff --git a/core/math/big/helpers.odin b/core/math/big/helpers.odin index e6b73430e..c0aa0c8bb 100644 --- a/core/math/big/helpers.odin +++ b/core/math/big/helpers.odin @@ -35,6 +35,7 @@ int_destroy :: proc(integers: ..^Int) { */ 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; src := src; /* @@ -43,7 +44,7 @@ int_set_from_integer :: proc(dest: ^Int, src: $T, minimize := false, allocator : assert_if_nil(dest); if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } - return #force_inline internal_int_set_from_integer(dest, src, minimize, allocator); + return #force_inline internal_int_set_from_integer(dest, src, minimize); } set :: proc { int_set_from_integer, int_copy }; @@ -61,10 +62,12 @@ int_copy :: proc(dest, src: ^Int, minimize := false, allocator := context.alloca Check that `src` is usable and `dest` isn't immutable. */ assert_if_nil(dest, src); - if err = #force_inline internal_clear_if_uninitialized(src, allocator); err != nil { return err; } - if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_copy(dest, src, minimize, allocator); + if err = #force_inline internal_clear_if_uninitialized(src); err != nil { return err; } + if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + + return #force_inline internal_int_copy(dest, src, minimize); } copy :: proc { int_copy, }; @@ -87,10 +90,12 @@ int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) Check that `src` is usable and `dest` isn't immutable. */ assert_if_nil(dest, src); - if err = #force_inline internal_clear_if_uninitialized(src, allocator); err != nil { return err; } - if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_abs(dest, src, allocator); + if err = #force_inline internal_clear_if_uninitialized(src); err != nil { return err; } + if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + + return #force_inline internal_int_abs(dest, src); } platform_abs :: proc(n: $T) -> T where intrinsics.type_is_integer(T) { @@ -106,10 +111,12 @@ int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) Check that `src` is usable and `dest` isn't immutable. */ assert_if_nil(dest, src); - if err = #force_inline internal_clear_if_uninitialized(src, allocator); err != nil { return err; } - if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_neg(dest, src, allocator); + if err = #force_inline internal_clear_if_uninitialized(src); err != nil { return err; } + if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + + return #force_inline internal_int_neg(dest, src); } neg :: proc { int_neg, }; @@ -125,22 +132,24 @@ int_bitfield_extract :: proc(a: ^Int, offset, count: int, allocator := context.a Check that `a` is usable. */ assert_if_nil(a); - if err = #force_inline internal_clear_if_uninitialized(a, allocator); err != nil { return {}, err; } + context.allocator = allocator; - return #force_inline internal_int_bitfield_extract(a, offset, count); + if err = #force_inline internal_clear_if_uninitialized(a); err != nil { return {}, err; } + return #force_inline internal_int_bitfield_extract(a, offset, count); } /* Resize backing store. */ -shrink :: proc(a: ^Int) -> (err: Error) { +shrink :: proc(a: ^Int, allocator := context.allocator) -> (err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - if err = #force_inline internal_clear_if_uninitialized(a); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_shrink(a); + if err = #force_inline internal_clear_if_uninitialized(a); err != nil { return err; } + return #force_inline internal_shrink(a); } int_grow :: proc(a: ^Int, digits: int, allow_shrink := false, allocator := context.allocator) -> (err: Error) { @@ -148,7 +157,6 @@ int_grow :: proc(a: ^Int, digits: int, allow_shrink := false, allocator := conte Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_int_grow(a, digits, allow_shrink, allocator); } grow :: proc { int_grow, }; @@ -161,7 +169,6 @@ int_clear :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_int_clear(a, minimize, allocator); } clear :: proc { int_clear, }; @@ -175,7 +182,6 @@ int_one :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> ( Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_one(a, minimize, allocator); } one :: proc { int_one, }; @@ -188,7 +194,6 @@ int_minus_one :: proc(a: ^Int, minimize := false, allocator := context.allocator Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_minus_one(a, minimize, allocator); } minus_one :: proc { int_minus_one, }; @@ -201,7 +206,6 @@ int_inf :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> ( Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_inf(a, minimize, allocator); } inf :: proc { int_inf, }; @@ -214,7 +218,6 @@ int_minus_inf :: proc(a: ^Int, minimize := false, allocator := context.allocator Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_minus_inf(a, minimize, allocator); } minus_inf :: proc { int_inf, }; @@ -227,7 +230,6 @@ int_nan :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> ( Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_nan(a, minimize, allocator); } nan :: proc { int_nan, }; @@ -237,67 +239,60 @@ power_of_two :: proc(a: ^Int, power: int, allocator := context.allocator) -> (er Check that `a` is usable. */ assert_if_nil(a); - return #force_inline internal_int_power_of_two(a, power, allocator); } -int_get_u128 :: proc(a: ^Int) -> (res: u128, err: Error) { +int_get_u128 :: proc(a: ^Int, allocator := context.allocator) -> (res: u128, err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - - return int_get(a, u128); + return int_get(a, u128, allocator); } get_u128 :: proc { int_get_u128, }; -int_get_i128 :: proc(a: ^Int) -> (res: i128, err: Error) { +int_get_i128 :: proc(a: ^Int, allocator := context.allocator) -> (res: i128, err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - - return int_get(a, i128); + return int_get(a, i128, allocator); } get_i128 :: proc { int_get_i128, }; -int_get_u64 :: proc(a: ^Int) -> (res: u64, err: Error) { +int_get_u64 :: proc(a: ^Int, allocator := context.allocator) -> (res: u64, err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - - return int_get(a, u64); + return int_get(a, u64, allocator); } get_u64 :: proc { int_get_u64, }; -int_get_i64 :: proc(a: ^Int) -> (res: i64, err: Error) { +int_get_i64 :: proc(a: ^Int, allocator := context.allocator) -> (res: i64, err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - - return int_get(a, i64); + return int_get(a, i64, allocator); } get_i64 :: proc { int_get_i64, }; -int_get_u32 :: proc(a: ^Int) -> (res: u32, err: Error) { +int_get_u32 :: proc(a: ^Int, allocator := context.allocator) -> (res: u32, err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - - return int_get(a, u32); + return int_get(a, u32, allocator); } get_u32 :: proc { int_get_u32, }; -int_get_i32 :: proc(a: ^Int) -> (res: i32, err: Error) { +int_get_i32 :: proc(a: ^Int, allocator := context.allocator) -> (res: i32, err: Error) { /* Check that `a` is usable. */ assert_if_nil(a); - - return int_get(a, i32); + return int_get(a, i32, allocator); } get_i32 :: proc { int_get_i32, }; @@ -311,8 +306,7 @@ int_get :: proc(a: ^Int, $T: typeid, allocator := context.allocator) -> (res: T, */ assert_if_nil(a); if err = #force_inline internal_clear_if_uninitialized(a, allocator); err != nil { return T{}, err; } - - return #force_inline internal_int_get(a, T); + return #force_inline internal_int_get(a, T); } get :: proc { int_get, }; @@ -322,8 +316,7 @@ int_get_float :: proc(a: ^Int, allocator := context.allocator) -> (res: f64, err */ assert_if_nil(a); if err = #force_inline internal_clear_if_uninitialized(a, allocator); err != nil { return 0, err; } - - return #force_inline internal_int_get_float(a); + return #force_inline internal_int_get_float(a); } /* @@ -335,8 +328,7 @@ count_bits :: proc(a: ^Int, allocator := context.allocator) -> (count: int, err: */ assert_if_nil(a); if err = #force_inline internal_clear_if_uninitialized(a, allocator); err != nil { return 0, err; } - - return #force_inline internal_count_bits(a), nil; + return #force_inline internal_count_bits(a), nil; } /* @@ -349,8 +341,7 @@ int_count_lsb :: proc(a: ^Int, allocator := context.allocator) -> (count: int, e */ assert_if_nil(a); if err = #force_inline internal_clear_if_uninitialized(a, allocator); err != nil { return 0, err; } - - return #force_inline internal_int_count_lsb(a); + return #force_inline internal_int_count_lsb(a); } platform_count_lsb :: #force_inline proc(a: $T) -> (count: int) @@ -429,35 +420,30 @@ error_if_immutable :: proc {error_if_immutable_single, error_if_immutable_multi, /* Allocates several `Int`s at once. */ -int_init_multi :: proc(integers: ..^Int) -> (err: Error) { +int_init_multi :: proc(integers: ..^Int, allocator := context.allocator) -> (err: Error) { assert_if_nil(..integers); integers := integers; for a in &integers { - if err = #force_inline internal_clear(a); err != nil { return err; } + if err = #force_inline internal_clear(a, true, allocator); err != nil { return err; } } return nil; } init_multi :: proc { int_init_multi, }; -_copy_digits :: proc(dest, src: ^Int, digits: int, allocator := context.allocator) -> (err: Error) { +copy_digits :: proc(dest, src: ^Int, digits: int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + digits := digits; /* Check that `src` is usable and `dest` isn't immutable. */ assert_if_nil(dest, src); - if err = #force_inline internal_clear_if_uninitialized(src, allocator); err != nil { return err; } - if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } - - /* - If dest == src, do nothing - */ - if (dest == src) { return nil; } + if err = #force_inline internal_clear_if_uninitialized(src); err != nil { return err; } digits = min(digits, len(src.digit), len(dest.digit)); - #force_inline mem.copy_non_overlapping(&dest.digit[0], &src.digit[0], size_of(DIGIT) * digits); - return nil; + return #force_inline internal_copy_digits(dest, src, digits); } /* diff --git a/core/math/big/internal.odin b/core/math/big/internal.odin index e916f9115..b05aeaf2e 100644 --- a/core/math/big/internal.odin +++ b/core/math/big/internal.odin @@ -26,6 +26,9 @@ package big Check the comments above each `internal_*` implementation to see what constraints it expects to have met. + We pass the custom allocator to procedures by default using the pattern `context.allocator = allocator`. + This way we don't have to add `, allocator` at the end of each call. + TODO: Handle +/- Infinity and NaN. */ @@ -41,6 +44,7 @@ import rnd "core:math/rand" */ internal_int_add_unsigned :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) { dest := dest; x := a; y := b; + context.allocator = allocator; old_used, min_used, max_used, i: int; @@ -52,7 +56,7 @@ internal_int_add_unsigned :: proc(dest, a, b: ^Int, allocator := context.allocat max_used = x.used; old_used = dest.used; - if err = internal_grow(dest, max(max_used + 1, _DEFAULT_DIGIT_COUNT), false, allocator); err != nil { return err; } + if err = internal_grow(dest, max(max_used + 1, _DEFAULT_DIGIT_COUNT)); err != nil { return err; } dest.used = max_used + 1; /* All parameters have been initialized. @@ -119,12 +123,13 @@ internal_add_unsigned :: proc { internal_int_add_unsigned, }; */ internal_int_add_signed :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) { 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, allocator); + return #force_inline internal_int_add_unsigned(dest, x, y); } /* @@ -137,7 +142,7 @@ internal_int_add_signed :: proc(dest, a, b: ^Int, allocator := context.allocator } dest.sign = x.sign; - return #force_inline internal_int_sub_unsigned(dest, x, y, allocator); + return #force_inline internal_int_sub_unsigned(dest, x, y); } internal_add_signed :: proc { internal_int_add_signed, }; @@ -149,7 +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) { - if err = internal_grow(dest, a.used + 1, false, allocator); err != nil { return err; } + context.allocator = allocator; + + if err = internal_grow(dest, a.used + 1); err != nil { return err; } /* Fast paths for destination and input Int being the same. */ @@ -183,7 +190,7 @@ internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context /* dest = |a| - digit */ - if err = #force_inline internal_int_add_digit(dest, a, digit, allocator); err != nil { + if err = #force_inline internal_int_add_digit(dest, a, digit); err != nil { /* Restore a's sign. */ @@ -261,13 +268,15 @@ internal_add :: proc { internal_int_add_signed, internal_int_add_digit, }; `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; + dest := dest; x := number; y := decrease; old_used := dest.used; min_used := y.used; max_used := x.used; i: int; - if err = grow(dest, max(max_used, _DEFAULT_DIGIT_COUNT), false, allocator); err != nil { return err; } + if err = grow(dest, max(max_used, _DEFAULT_DIGIT_COUNT)); err != nil { return err; } dest.used = max_used; /* All parameters have been initialized. @@ -328,6 +337,8 @@ 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; + number := number; decrease := decrease; if number.sign != decrease.sign { /* @@ -335,14 +346,14 @@ internal_int_sub_signed :: proc(dest, number, decrease: ^Int, allocator := conte 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, allocator); + return #force_inline internal_int_add_unsigned(dest, number, decrease); } /* Subtract a positive from a positive, OR negative from a negative. First, take the difference between their magnitudes, then... */ - if c, _ := #force_inline cmp_mag(number, decrease); c == -1 { + if #force_inline internal_cmp_mag(number, decrease) == -1 { /* The second has a larger magnitude. The result has the *opposite* sign from the first number. @@ -356,7 +367,7 @@ internal_int_sub_signed :: proc(dest, number, decrease: ^Int, allocator := conte */ dest.sign = number.sign; } - return #force_inline internal_int_sub_unsigned(dest, number, decrease, allocator); + return #force_inline internal_int_sub_unsigned(dest, number, decrease); } /* @@ -368,7 +379,9 @@ 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) { - if err = internal_grow(dest, number.used + 1, false, allocator); err != nil { return err; } + context.allocator = allocator; + + if err = internal_grow(dest, number.used + 1); err != nil { return err; } dest := dest; digit := digit; /* @@ -403,7 +416,7 @@ internal_int_sub_digit :: proc(dest, number: ^Int, digit: DIGIT, allocator := co err = #force_inline internal_int_add_digit(dest, t, digit); dest.sign = .Negative; - clamp(dest); + internal_clamp(dest); return err; } @@ -448,6 +461,9 @@ internal_sub :: proc { internal_int_sub_signed, internal_int_sub_digit, }; /* dest = src / 2 dest = src >> 1 + + Assumes `dest` and `src` not to be `nil` and have been initialized. + We make no allocations here. */ internal_int_shr1 :: proc(dest, src: ^Int) -> (err: Error) { old_used := dest.used; dest.used = src.used; @@ -488,13 +504,15 @@ internal_int_shr1 :: proc(dest, src: ^Int) -> (err: Error) { dest = src * 2 dest = src << 1 */ -internal_int_shl1 :: proc(dest, src: ^Int) -> (err: Error) { - if err = copy(dest, src); err != nil { return err; } +internal_int_shl1 :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + + if err = internal_copy(dest, src); err != nil { return err; } /* Grow `dest` to accommodate the additional bits. */ digits_needed := dest.used + 1; - if err = grow(dest, digits_needed); err != nil { return err; } + if err = internal_grow(dest, digits_needed); err != nil { return err; } dest.used = digits_needed; mask := (DIGIT(1) << uint(1)) - DIGIT(1); @@ -520,13 +538,14 @@ internal_int_shl1 :: proc(dest, src: ^Int) -> (err: Error) { Multiply by a DIGIT. */ internal_int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator) -> (err: Error) { - assert(dest != nil && src != nil); + context.allocator = allocator; + assert_if_nil(dest, src); if multiplier == 0 { - return zero(dest); + return internal_zero(dest); } if multiplier == 1 { - return copy(dest, src); + return internal_copy(dest, src); } /* @@ -535,16 +554,16 @@ internal_int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := if multiplier == 2 { return #force_inline internal_int_shl1(dest, src); } - if is_power_of_two(int(multiplier)) { + if #force_inline platform_int_is_power_of_two(int(multiplier)) { ix: int; - if ix, err = log(multiplier, 2); err != nil { return err; } - return shl(dest, src, ix); + if ix, err = internal_log(multiplier, 2); err != nil { return err; } + return internal_shl(dest, src, ix); } /* Ensure `dest` is big enough to hold `src` * `multiplier`. */ - if err = grow(dest, max(src.used + 1, _DEFAULT_DIGIT_COUNT), false, allocator); err != nil { return err; } + if err = grow(dest, max(src.used + 1, _DEFAULT_DIGIT_COUNT)); err != nil { return err; } /* Save the original used count. @@ -562,7 +581,7 @@ internal_int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := Compute columns. */ ix := 0; - for ; ix < src.used; ix += 1 { + #no_bounds_check for ; ix < src.used; ix += 1 { /* Compute product and carry sum for this term */ @@ -595,10 +614,11 @@ internal_int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := High level multiplication (handles sign). */ internal_int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; /* Early out for `multiplier` is zero; Set `dest` to zero. */ - if multiplier.used == 0 || src.used == 0 { return zero(dest); } + if multiplier.used == 0 || src.used == 0 { return internal_zero(dest); } if src == multiplier { /* @@ -676,6 +696,7 @@ 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; if denominator.used == 0 { return .Division_by_Zero; } /* @@ -683,7 +704,7 @@ internal_int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, a */ if #force_inline internal_cmp_mag(numerator, denominator) == -1 { if remainder != nil { - if err = internal_copy(remainder, numerator, false, allocator); err != nil { return err; } + if err = internal_copy(remainder, numerator); err != nil { return err; } } if quotient != nil { internal_zero(quotient); @@ -711,7 +732,9 @@ internal_int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, a Single digit division (based on routine from MPI). The quotient is optional and may be passed a nil. */ -internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) -> (remainder: DIGIT, err: Error) { +internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) { + context.allocator = allocator; + /* Cannot divide by zero. */ @@ -722,7 +745,7 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) */ if denominator == 1 || numerator.used == 0 { if quotient != nil { - return 0, copy(quotient, numerator); + return 0, internal_copy(quotient, numerator); } return 0, err; } @@ -737,11 +760,11 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) if quotient == nil { return remainder, nil; } - return remainder, shr(quotient, numerator, 1); + return remainder, internal_shr(quotient, numerator, 1); } ix: int; - if is_power_of_two(int(denominator)) { + if platform_int_is_power_of_two(int(denominator)) { ix = 1; for ix < _DIGIT_BITS && denominator != (1 << uint(ix)) { ix += 1; @@ -751,7 +774,7 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) return remainder, nil; } - return remainder, shr(quotient, numerator, int(ix)); + return remainder, internal_shr(quotient, numerator, int(ix)); } /* @@ -766,7 +789,7 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) */ q := &Int{}; - if err = grow(q, numerator.used); err != nil { return 0, err; } + if err = internal_grow(q, numerator.used); err != nil { return 0, err; } q.used = numerator.used; q.sign = numerator.sign; @@ -785,10 +808,10 @@ internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) remainder = DIGIT(w); if quotient != nil { - clamp(q); - swap(q, quotient); + internal_clamp(q); + internal_swap(q, quotient); } - destroy(q); + internal_destroy(q); return remainder, nil; } @@ -861,18 +884,20 @@ 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; + if n >= FACTORIAL_BINARY_SPLIT_CUTOFF { - return #force_inline _private_int_factorial_binary_split(res, n, allocator); + return #force_inline _private_int_factorial_binary_split(res, n); } i := len(_factorial_table); if n < i { - return #force_inline internal_set(res, _factorial_table[n], true, allocator); + return #force_inline internal_set(res, _factorial_table[n]); } - if err = #force_inline internal_set(res, _factorial_table[i - 1], true, allocator); err != nil { return err; } + if err = #force_inline internal_set(res, _factorial_table[i - 1]); err != nil { return err; } for { - if err = #force_inline internal_mul(res, res, DIGIT(i), allocator); err != nil || i == n { return err; } + if err = #force_inline internal_mul(res, res, DIGIT(i)); err != nil || i == n { return err; } i += 1; } @@ -885,10 +910,10 @@ internal_int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator Assumes `a` and `b` to have been initialized. `res_gcd` and `res_lcm` can be nil or ^Int depending on which results are desired. */ -internal_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { +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); + return #force_inline _private_int_gcd_lcm(res_gcd, res_lcm, a, b, allocator); } /* @@ -896,7 +921,7 @@ internal_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { Assumes `remainder` and `numerator` both not to be `nil` and `bits` to be >= 0. */ -internal_int_mod_bits :: proc(remainder, numerator: ^Int, bits: int) -> (err: Error) { +internal_int_mod_bits :: proc(remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) { /* Everything is divisible by 1 << 0 == 1, so this returns 0. */ @@ -1139,14 +1164,14 @@ internal_int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) { /* Fast path for bases that are a power of two. */ - if platform_int_is_power_of_two(int(base)) { return private_log_power_of_two(a, base); } + if platform_int_is_power_of_two(int(base)) { return _private_log_power_of_two(a, base); } /* Fast path for `Int`s that fit within a single `DIGIT`. */ if a.used == 1 { return internal_log(a.digit[0], DIGIT(base)); } - return private_int_log(a, base); + return _private_int_log(a, base); } @@ -1207,7 +1232,9 @@ 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) -> (err: Error) { +internal_int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + power := power; /* Early outs. @@ -1217,18 +1244,18 @@ internal_int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) { A zero base is a special case. */ if power < 0 { - if err = zero(dest); err != nil { return err; } + if err = internal_zero(dest); err != nil { return err; } return .Math_Domain_Error; } - if power == 0 { return set(dest, 1); } - if power > 0 { return zero(dest); } + if power == 0 { return internal_one(dest); } + if power > 0 { return internal_zero(dest); } } if power < 0 { /* Fraction, so we'll return zero. */ - return zero(dest); + return internal_zero(dest); } switch(power) { case 0: @@ -1246,19 +1273,19 @@ internal_int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) { } g := &Int{}; - if err = copy(g, base); err != nil { return err; } + if err = internal_copy(g, base); err != nil { return err; } /* Set initial result. */ - if err = set(dest, 1); err != nil { return err; } + if err = internal_one(dest); err != nil { return err; } loop: for power > 0 { /* If the bit is set, multiply. */ if power & 1 != 0 { - if err = mul(dest, g, dest); err != nil { + if err = internal_mul(dest, g, dest); err != nil { break loop; } } @@ -1275,7 +1302,7 @@ internal_int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) { power >>= 1; } - destroy(g); + internal_destroy(g); return err; } @@ -1283,11 +1310,13 @@ internal_int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) { Calculate `dest = base^power`. Assumes `dest` not to be `nil` and to have been initialized. */ -internal_int_pow_int :: proc(dest: ^Int, base, power: int) -> (err: Error) { +internal_int_pow_int :: proc(dest: ^Int, base, power: int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + base_t := &Int{}; - defer destroy(base_t); + defer internal_destroy(base_t); - if err = set(base_t, base); err != nil { return err; } + if err = internal_set(base_t, base); err != nil { return err; } return #force_inline internal_int_pow(dest, base_t, power); } @@ -1296,22 +1325,6 @@ internal_pow :: proc { internal_int_pow, internal_int_pow_int, }; internal_exp :: pow; /* - Returns the log2 of an `Int`. - Assumes `a` not to be `nil` and to have been initialized. - Also assumes `base` is a power of two. -*/ -private_log_power_of_two :: proc(a: ^Int, base: DIGIT) -> (log: int, err: Error) { - base := base; - y: int; - for y = 0; base & 1 == 0; { - y += 1; - base >>= 1; - } - log, err = count_bits(a); - return (log - 1) / y, err; -} - -/* */ internal_small_pow :: proc(base: _WORD, exponent: _WORD) -> (result: _WORD) { @@ -1333,6 +1346,8 @@ 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; + /* Must be positive. */ @@ -1341,7 +1356,7 @@ internal_int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (e /* Easy out. If src is zero, so is dest. */ - if #force_inline internal_is_zero(src) { return zero(dest); } + if #force_inline internal_is_zero(src) { return internal_zero(dest); } /* Set up temporaries. @@ -1358,9 +1373,9 @@ internal_int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (e /* y = (x + n // x) // 2 */ - internal_div(t1, src, x); - internal_add(t2, t1, x); - internal_shr(y, t2, 1); + if err = internal_div(t1, src, x); err != nil { return err; } + if err = internal_add(t2, t1, x); err != nil { return err; } + if err = internal_shr(y, t2, 1); err != nil { return err; } if c := internal_cmp(y, x); c == 0 || c == 1 { internal_swap(dest, x); @@ -1385,10 +1400,12 @@ 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; + /* Fast path for n == 2 */ - if n == 2 { return #force_inline internal_sqrt(dest, src, allocator); } + if n == 2 { return #force_inline internal_sqrt(dest, src); } if n < 0 || n > int(_DIGIT_MAX) { return .Invalid_Argument; } @@ -1427,14 +1444,14 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca "src" is smaller than max(int), we can cast safely. */ if ilog2 < n { - err = internal_one(dest, true, allocator); + err = internal_one(dest); dest.sign = a.sign; return err; } ilog2 /= n; if ilog2 == 0 { - err = internal_one(dest, true, allocator); + err = internal_one(dest); dest.sign = a.sign; return err; } @@ -1443,13 +1460,13 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca Start value must be larger than root. */ ilog2 += 2; - if err = power_of_two(t2, ilog2, allocator); err != nil { return err; } + if err = internal_int_power_of_two(t2, ilog2); err != nil { return err; } c: int; iterations := 0; for { /* t1 = t2 */ - if err = copy(t1, t2, false, allocator); err != nil { return err; } + if err = internal_copy(t1, t2); err != nil { return err; } /* t2 = t1 - ((t1**b - a) / (b * t1**(b-1))) */ @@ -1458,24 +1475,24 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca /* numerator */ /* t2 = t1**b */ - if err = internal_mul(t2, t1, t3, allocator); err != nil { return err; } + if err = internal_mul(t2, t1, t3); err != nil { return err; } /* t2 = t1**b - a */ - if err = internal_sub(t2, t2, a, allocator); err != nil { return err; } + if err = internal_sub(t2, t2, a); err != nil { return err; } /* denominator */ /* t3 = t1**(b-1) * b */ - if err = internal_mul(t3, t3, DIGIT(n), allocator); err != nil { return err; } + if err = internal_mul(t3, t3, DIGIT(n)); err != nil { return err; } /* t3 = (t1**b - a)/(b * t1**(b-1)) */ - if err = internal_div(t3, t2, t3, allocator); err != nil { return err; } - if err = internal_sub(t2, t1, t3, allocator); err != nil { return err; } + if err = internal_div(t3, t2, t3); err != nil { return err; } + if err = internal_sub(t2, t1, t3); err != nil { return err; } /* Number of rounds is at most log_2(root). If it is more it got stuck, so break out of the loop and do the rest manually. */ - if ilog2 -= 1; ilog2 == 0 { break; } + if ilog2 -= 1; ilog2 == 0 { break; } if internal_cmp(t1, t2) == 0 { break; } iterations += 1; @@ -1539,72 +1556,6 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.alloca internal_root_n :: proc { internal_int_root_n, }; /* - Internal implementation of log. - Assumes `a` not to be `nil` and to have been initialized. -*/ -private_int_log :: proc(a: ^Int, base: DIGIT, allocator := context.allocator) -> (res: int, err: Error) { - bracket_low, bracket_high, bracket_mid, t, bi_base := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}; - defer destroy(bracket_low, bracket_high, bracket_mid, t, bi_base); - - ic := #force_inline internal_cmp(a, base); - if ic == -1 || ic == 0 { - return 1 if ic == 0 else 0, nil; - } - - if err = internal_set(bi_base, base, true, allocator); err != nil { return -1, err; } - if err = internal_clear(bracket_mid, false, allocator); err != nil { return -1, err; } - if err = internal_clear(t, false, allocator); err != nil { return -1, err; } - if err = internal_one(bracket_low, false, allocator); err != nil { return -1, err; } - if err = internal_set(bracket_high, base, false, allocator); err != nil { return -1, err; } - - low := 0; high := 1; - - /* - A kind of Giant-step/baby-step algorithm. - Idea shamelessly stolen from https://programmingpraxis.com/2010/05/07/integer-logarithms/2/ - The effect is asymptotic, hence needs benchmarks to test if the Giant-step should be skipped - for small n. - */ - - for { - /* - Iterate until `a` is bracketed between low + high. - */ - if #force_inline internal_cmp(bracket_high, a) != -1 { break; } - - low = high; - if err = #force_inline internal_copy(bracket_low, bracket_high); err != nil { return -1, err; } - high <<= 1; - if err = #force_inline internal_sqr(bracket_high, bracket_high); err != nil { return -1, err; } - } - - for (high - low) > 1 { - mid := (high + low) >> 1; - - if err = #force_inline internal_pow(t, bi_base, mid - low); err != nil { return -1, err; } - - if err = #force_inline internal_mul(bracket_mid, bracket_low, t); err != nil { return -1, err; } - - mc := #force_inline internal_cmp(a, bracket_mid); - switch mc { - case -1: - high = mid; - internal_swap(bracket_mid, bracket_high); - case 0: - return mid, nil; - case 1: - low = mid; - internal_swap(bracket_mid, bracket_low); - } - } - - fc := #force_inline internal_cmp(bracket_high, a); - res = high if fc == 0 else low; - - return; -} - -/* Other internal helpers */ @@ -1616,9 +1567,9 @@ internal_int_destroy :: proc(integers: ..^Int) { integers := integers; for a in &integers { - mem.zero_slice(a.digit[:]); raw := transmute(mem.Raw_Dynamic_Array)a.digit; if raw.cap > 0 { + mem.zero_slice(a.digit[:]); free(&a.digit[0]); } a = &Int{}; @@ -1631,6 +1582,8 @@ internal_destroy :: proc{ internal_int_destroy, }; */ 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; + src := src; if err = internal_error_if_immutable(dest); err != nil { return err; } @@ -1638,7 +1591,7 @@ internal_int_set_from_integer :: proc(dest: ^Int, src: $T, minimize := false, al 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. */ - if err = internal_clear_if_uninitialized_single(dest, allocator); err != nil { return err; } + if err = internal_clear_if_uninitialized_single(dest); err != nil { return err; } dest.flags = {}; // We're not -Inf, Inf, NaN or Immutable. @@ -1657,10 +1610,24 @@ internal_int_set_from_integer :: proc(dest: ^Int, src: $T, minimize := false, al internal_set :: proc { internal_int_set_from_integer, internal_int_copy }; +internal_copy_digits :: #force_inline proc(dest, src: ^Int, digits: int) -> (err: Error) { + if err = #force_inline internal_error_if_immutable(dest); err != nil { return err; } + + /* + If dest == src, do nothing + */ + if (dest == src) { return nil; } + + #force_inline mem.copy_non_overlapping(&dest.digit[0], &src.digit[0], size_of(DIGIT) * digits); + return nil; +} + /* Copy one `Int` to another. */ internal_int_copy :: proc(dest, src: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + /* If dest == src, do nothing */ @@ -1674,14 +1641,13 @@ internal_int_copy :: proc(dest, src: ^Int, minimize := false, allocator := conte */ needed := src.used if minimize else max(src.used, _DEFAULT_DIGIT_COUNT); - if err = internal_grow(dest, needed, minimize, allocator); err != nil { return err; } + if err = internal_grow(dest, needed, minimize); err != nil { return err; } /* Copy everything over and zero high digits. */ - #no_bounds_check for v, i in src.digit[:src.used] { - dest.digit[i] = v; - } + internal_copy_digits(dest, src, src.used); + dest.used = src.used; dest.sign = src.sign; dest.flags = src.flags &~ {.Immutable}; @@ -1709,6 +1675,8 @@ 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; + /* If `dest == src`, just fix `dest`'s sign. */ @@ -1720,7 +1688,7 @@ internal_int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (er /* Copy `src` to `dest` */ - if err = internal_copy(dest, src, false, allocator); err != nil { + if err = internal_copy(dest, src); err != nil { return err; } @@ -1740,6 +1708,8 @@ 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; + /* If `dest == src`, just fix `dest`'s sign. */ @@ -1754,7 +1724,7 @@ internal_int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (er /* Copy `src` to `dest` */ - if err = internal_copy(dest, src, false, allocator); err != nil { return err; } + if err = internal_copy(dest, src); err != nil { return err; } /* Fix sign. @@ -1836,7 +1806,7 @@ internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WOR internal_int_shrink :: proc(a: ^Int) -> (err: Error) { needed := max(_MIN_DIGIT_COUNT, a.used); - if a.used != needed { return internal_grow(a, needed); } + if a.used != needed { return internal_grow(a, needed, true); } return nil; } internal_shrink :: proc { internal_int_shrink, }; @@ -1932,13 +1902,15 @@ internal_int_nan :: proc(a: ^Int, minimize := false, allocator := context.alloca internal_nan :: proc { internal_int_nan, }; internal_int_power_of_two :: proc(a: ^Int, power: int, allocator := context.allocator) -> (err: Error) { + 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; - if err = internal_grow(a, a.used, false, allocator); err != nil { return err; } + if err = internal_grow(a, a.used); err != nil { return err; } /* Zero the entirety. */ @@ -2036,11 +2008,13 @@ 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; + used := max(a.used, b.used) + 1; /* Grow the destination to accomodate the result. */ - if err = internal_grow(dest, used, false, allocator); err != nil { return err; } + if err = internal_grow(dest, used); err != nil { return err; } neg_a := #force_inline internal_is_negative(a); neg_b := #force_inline internal_is_negative(b); @@ -2095,11 +2069,13 @@ 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; + used := max(a.used, b.used) + 1; /* Grow the destination to accomodate the result. */ - if err = internal_grow(dest, used, false, allocator); err != nil { return err; } + if err = internal_grow(dest, used); err != nil { return err; } neg_a := #force_inline internal_is_negative(a); neg_b := #force_inline internal_is_negative(b); @@ -2154,11 +2130,13 @@ 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; + used := max(a.used, b.used) + 1; /* Grow the destination to accomodate the result. */ - if err = internal_grow(dest, used, false, allocator); err != nil { return err; } + if err = internal_grow(dest, used); err != nil { return err; } neg_a := #force_inline internal_is_negative(a); neg_b := #force_inline internal_is_negative(b); @@ -2213,6 +2191,8 @@ internal_xor :: proc { internal_int_xor, }; dest = ~src */ internal_int_complement :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + /* Temporarily fix sign. */ @@ -2237,10 +2217,12 @@ internal_complement :: proc { internal_int_complement, }; `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; + bits := bits; if bits < 0 { return .Invalid_Argument; } - if err = internal_copy(quotient, numerator, true, allocator); err != nil { return err; } + if err = internal_copy(quotient, numerator); err != nil { return err; } /* Shift right by a certain bit count (store quotient and optional remainder.) @@ -2297,12 +2279,14 @@ 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; + if digits <= 0 { return nil; } /* If digits > used simply zero and return. */ - if digits > quotient.used { return internal_zero(quotient, true, allocator); } + if digits > quotient.used { return internal_zero(quotient); } /* Much like `int_shl_digit`, this is implemented using a sliding window, @@ -2326,13 +2310,15 @@ 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; + if src.sign == .Zero_or_Positive { - return internal_shr(dest, src, bits, allocator); + return internal_shr(dest, src, bits); } - if err = internal_int_add_digit(dest, src, DIGIT(1), allocator); err != nil { return err; } + if err = internal_int_add_digit(dest, src, DIGIT(1)); err != nil { return err; } - if err = internal_shr(dest, dest, bits, allocator); err != nil { return err; } - return internal_sub(dest, src, DIGIT(1), allocator); + if err = internal_shr(dest, dest, bits); err != nil { return err; } + return internal_sub(dest, src, DIGIT(1)); } internal_shr_signed :: proc { internal_int_shr_signed, }; @@ -2341,11 +2327,13 @@ 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; + bits := bits; if bits < 0 { return .Invalid_Argument; } - if err = internal_copy(dest, src, false, allocator); err != nil { return err; } + if err = internal_copy(dest, src); err != nil { return err; } /* Grow `dest` to accommodate the additional bits. @@ -2391,7 +2379,9 @@ internal_shl :: proc { internal_int_shl, }; /* Shift left by `digits` * _DIGIT_BITS bits. */ -internal_int_shl_digit :: proc(quotient: ^Int, digits: int) -> (err: Error) { +internal_int_shl_digit :: proc(quotient: ^Int, digits: int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + if digits <= 0 { return nil; } /* @@ -2446,10 +2436,10 @@ internal_count_bits :: proc(a: ^Int) -> (count: int) { /* Returns the number of trailing zeroes before the first one. Differs from regular `ctz` in that 0 returns 0. + + Assumes `a` not to be `nil` and have been initialized. */ internal_int_count_lsb :: proc(a: ^Int) -> (count: int, err: Error) { - if err = internal_clear_if_uninitialized_single(a); err != nil { return -1, err; } - /* Easy out. */ @@ -2487,6 +2477,8 @@ internal_int_random_digit :: proc(r: ^rnd.Rand = nil) -> (res: DIGIT) { } internal_int_rand :: proc(dest: ^Int, bits: int, r: ^rnd.Rand = nil, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + bits := bits; if bits <= 0 { return .Invalid_Argument; } @@ -2498,7 +2490,7 @@ internal_int_rand :: proc(dest: ^Int, bits: int, r: ^rnd.Rand = nil, allocator : digits += 1; } - if err = #force_inline internal_grow(dest, digits, true, allocator); err != nil { return err; } + if err = #force_inline internal_grow(dest, digits); err != nil { return err; } for i := 0; i < digits; i += 1 { dest.digit[i] = int_random_digit(r) & _MASK; @@ -2519,16 +2511,20 @@ internal_assert_initialized :: proc(a: ^Int, loc := #caller_location) { } internal_clear_if_uninitialized_single :: proc(arg: ^Int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + if ! #force_inline internal_is_initialized(arg) { - return #force_inline internal_grow(arg, _DEFAULT_DIGIT_COUNT, true, allocator); + return #force_inline internal_grow(arg, _DEFAULT_DIGIT_COUNT); } return err; } internal_clear_if_uninitialized_multi :: proc(args: ..^Int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + for i in args { if ! #force_inline internal_is_initialized(i) { - e := #force_inline internal_grow(i, _DEFAULT_DIGIT_COUNT, true, allocator); + e := #force_inline internal_grow(i, _DEFAULT_DIGIT_COUNT); if e != nil { err = e; } } } @@ -2553,9 +2549,11 @@ internal_error_if_immutable :: proc {internal_error_if_immutable_single, interna Allocates several `Int`s at once. */ internal_int_init_multi :: proc(integers: ..^Int, allocator := context.allocator) -> (err: Error) { + context.allocator = allocator; + integers := integers; for a in &integers { - if err = internal_clear(a, false, allocator); err != nil { return err; } + if err = internal_clear(a); err != nil { return err; } } return nil; } @@ -2563,22 +2561,6 @@ internal_int_init_multi :: proc(integers: ..^Int, allocator := context.allocator internal_init_multi :: proc { internal_int_init_multi, }; /* - Copies DIGITs from `src` to `dest`. - Assumes `src` and `dest` to not be `nil` and have been initialized. -*/ -_private_copy_digits :: proc(dest, src: ^Int, digits: int) -> (err: Error) { - digits := digits; - /* - If dest == src, do nothing - */ - if dest == src { return nil; } - - digits = min(digits, len(src.digit), len(dest.digit)); - mem.copy_non_overlapping(&dest.digit[0], &src.digit[0], size_of(DIGIT) * digits); - return nil; -} - -/* Trim unused digits. This is used to ensure that leading zero digits are trimmed and the leading "used" digit will be non-zero. diff --git a/core/math/big/logical.odin b/core/math/big/logical.odin index 57adf6f1e..1050de0c4 100644 --- a/core/math/big/logical.odin +++ b/core/math/big/logical.odin @@ -25,9 +25,10 @@ import "core:mem" */ int_and :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) { assert_if_nil(dest, a, b); - if err = internal_clear_if_uninitialized(a, b); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_and(dest, a, b, allocator); + if err = internal_clear_if_uninitialized(a, b); err != nil { return err; } + return #force_inline internal_int_and(dest, a, b); } and :: proc { int_and, }; @@ -36,9 +37,10 @@ and :: proc { int_and, }; */ int_or :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) { assert_if_nil(dest, a, b); - if err = internal_clear_if_uninitialized(a, b); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_or(dest, a, b, allocator); + if err = internal_clear_if_uninitialized(a, b); err != nil { return err; } + return #force_inline internal_int_or(dest, a, b); } or :: proc { int_or, }; @@ -47,9 +49,10 @@ or :: proc { int_or, }; */ int_xor :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) { assert_if_nil(dest, a, b); - if err = internal_clear_if_uninitialized(a, b); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_xor(dest, a, b, allocator); + if err = internal_clear_if_uninitialized(a, b); err != nil { return err; } + return #force_inline internal_int_xor(dest, a, b); } xor :: proc { int_xor, }; @@ -61,9 +64,9 @@ int_complement :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Check that `src` and `dest` are usable. */ assert_if_nil(dest, src); - if err = internal_clear_if_uninitialized(dest, allocator); err != nil { return err; } - if err = internal_clear_if_uninitialized(src, allocator); err != nil { return err; } + context.allocator = allocator; + if err = internal_clear_if_uninitialized(dest, src); err != nil { return err; } return #force_inline internal_int_complement(dest, src); } complement :: proc { int_complement, }; @@ -74,15 +77,15 @@ complement :: proc { int_complement, }; */ int_shrmod :: proc(quotient, remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) { assert_if_nil(quotient, numerator); - if err = internal_clear_if_uninitialized(quotient, allocator); err != nil { return err; } - if err = internal_clear_if_uninitialized(numerator, allocator); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_shrmod(quotient, remainder, numerator, bits, allocator); + if err = internal_clear_if_uninitialized(quotient, numerator); err != nil { return err; } + return #force_inline internal_int_shrmod(quotient, remainder, numerator, bits); } shrmod :: proc { int_shrmod, }; -int_shr :: proc(dest, source: ^Int, bits: int) -> (err: Error) { - return #force_inline shrmod(dest, nil, source, bits); +int_shr :: proc(dest, source: ^Int, bits: int, allocator := context.allocator) -> (err: Error) { + return #force_inline shrmod(dest, nil, source, bits, allocator); } shr :: proc { int_shr, }; @@ -94,9 +97,10 @@ int_shr_digit :: proc(quotient: ^Int, digits: int, allocator := context.allocato Check that `quotient` is usable. */ assert_if_nil(quotient); - if err = internal_clear_if_uninitialized(quotient, allocator); err != nil { return err; } + context.allocator = allocator; - return #force_inline internal_int_shr_digit(quotient, digits, allocator); + if err = internal_clear_if_uninitialized(quotient); err != nil { return err; } + return #force_inline internal_int_shr_digit(quotient, digits); } shr_digit :: proc { int_shr_digit, }; @@ -105,9 +109,9 @@ shr_digit :: proc { int_shr_digit, }; */ int_shr_signed :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) { assert_if_nil(dest, src); - if err = internal_clear_if_uninitialized(dest, allocator); err != nil { return err; } - if err = internal_clear_if_uninitialized(src, allocator); err != nil { return err; } + context.allocator = allocator; + if err = internal_clear_if_uninitialized(dest, src); err != nil { return err; } return #force_inline internal_int_shr_signed(dest, src, bits); } @@ -118,9 +122,9 @@ shr_signed :: proc { int_shr_signed, }; */ int_shl :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) { assert_if_nil(dest, src); - if err = internal_clear_if_uninitialized(dest, allocator); err != nil { return err; } - if err = internal_clear_if_uninitialized(src, allocator); err != nil { return err; } + context.allocator = allocator; + if err = internal_clear_if_uninitialized(dest, src); err != nil { return err; } return #force_inline internal_int_shl(dest, src, bits); } shl :: proc { int_shl, }; @@ -129,13 +133,14 @@ shl :: proc { int_shl, }; /* Shift left by `digits` * _DIGIT_BITS bits. */ -int_shl_digit :: proc(quotient: ^Int, digits: int) -> (err: Error) { +int_shl_digit :: proc(quotient: ^Int, digits: int, allocator := context.allocator) -> (err: Error) { /* Check that `quotient` is usable. */ assert_if_nil(quotient); - if err = internal_clear_if_uninitialized(quotient); err != nil { return err; } + context.allocator = allocator; + if err = internal_clear_if_uninitialized(quotient); err != nil { return err; } return #force_inline internal_int_shl_digit(quotient, digits); } shl_digit :: proc { int_shl_digit, };
\ No newline at end of file diff --git a/core/math/big/prime.odin b/core/math/big/prime.odin index 7041b8c39..25d5ddda3 100644 --- a/core/math/big/prime.odin +++ b/core/math/big/prime.odin @@ -17,7 +17,9 @@ package big */ int_prime_is_divisible :: proc(a: ^Int, allocator := context.allocator) -> (res: bool, err: Error) { assert_if_nil(a); - if err = internal_clear_if_uninitialized(a, allocator); err != nil { return {}, err; } + context.allocator = allocator; + + if err = internal_clear_if_uninitialized(a); err != nil { return {}, err; } rem: DIGIT; for prime in _private_prime_table { diff --git a/core/math/big/private.odin b/core/math/big/private.odin index 111439e25..fab63977c 100644 --- a/core/math/big/private.odin +++ b/core/math/big/private.odin @@ -19,13 +19,16 @@ package big */
import "core:intrinsics"
+import "core:mem"
/*
Multiplies |a| * |b| and only computes upto digs digits of result.
HAC pp. 595, Algorithm 14.12 Modified so you can control how
many digits of output are created.
*/
-_private_int_mul :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) {
+_private_int_mul :: proc(dest, a, b: ^Int, digits: int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
+
/*
Can we use the fast multiplier?
*/
@@ -39,7 +42,7 @@ _private_int_mul :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) { t := &Int{};
- if err = grow(t, max(digits, _DEFAULT_DIGIT_COUNT)); err != nil { return err; }
+ if err = internal_grow(t, max(digits, _DEFAULT_DIGIT_COUNT)); err != nil { return err; }
t.used = digits;
/*
@@ -81,9 +84,9 @@ _private_int_mul :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) { }
}
- swap(dest, t);
- destroy(t);
- return clamp(dest);
+ internal_swap(dest, t);
+ internal_destroy(t);
+ return internal_clamp(dest);
}
/*
@@ -102,7 +105,9 @@ _private_int_mul :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) { Based on Algorithm 14.12 on pp.595 of HAC.
*/
-_private_int_mul_comba :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) {
+_private_int_mul_comba :: proc(dest, a, b: ^Int, digits: int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
+
/*
Set up array.
*/
@@ -111,7 +116,7 @@ _private_int_mul_comba :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) { /*
Grow the destination as required.
*/
- if err = grow(dest, digits); err != nil { return err; }
+ if err = internal_grow(dest, digits); err != nil { return err; }
/*
Number of output digits to produce.
@@ -172,27 +177,28 @@ _private_int_mul_comba :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) { /*
Clear unused digits [that existed in the old copy of dest].
*/
- zero_unused(dest, old_used);
+ internal_zero_unused(dest, old_used);
/*
Adjust dest.used based on leading zeroes.
*/
- return clamp(dest);
+ return internal_clamp(dest);
}
/*
Low level squaring, b = a*a, HAC pp.596-597, Algorithm 14.16
Assumes `dest` and `src` to not be `nil`, and `src` to have been initialized.
*/
-_private_int_sqr :: proc(dest, src: ^Int) -> (err: Error) {
+_private_int_sqr :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
pa := src.used;
t := &Int{}; ix, iy: int;
/*
Grow `t` to maximum needed size, or `_DEFAULT_DIGIT_COUNT`, whichever is bigger.
*/
- if err = grow(t, max((2 * pa) + 1, _DEFAULT_DIGIT_COUNT)); err != nil { return err; }
+ if err = internal_grow(t, max((2 * pa) + 1, _DEFAULT_DIGIT_COUNT)); err != nil { return err; }
t.used = (2 * pa) + 1;
#no_bounds_check for ix = 0; ix < pa; ix += 1 {
@@ -243,23 +249,25 @@ _private_int_sqr :: proc(dest, src: ^Int) -> (err: Error) { }
}
- err = clamp(t);
- swap(dest, t);
- destroy(t);
+ err = internal_clamp(t);
+ internal_swap(dest, t);
+ internal_destroy(t);
return err;
}
/*
Divide by three (based on routine from MPI and the GMP manual).
*/
-_private_int_div_3 :: proc(quotient, numerator: ^Int) -> (remainder: DIGIT, err: Error) {
+_private_int_div_3 :: proc(quotient, numerator: ^Int, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {
+ context.allocator = allocator;
+
/*
b = 2^_DIGIT_BITS / 3
*/
b := _WORD(1) << _WORD(_DIGIT_BITS) / _WORD(3);
q := &Int{};
- if err = grow(q, numerator.used); err != nil { return 0, err; }
+ if err = internal_grow(q, numerator.used); err != nil { return 0, err; }
q.used = numerator.used;
q.sign = numerator.sign;
@@ -296,9 +304,9 @@ _private_int_div_3 :: proc(quotient, numerator: ^Int) -> (remainder: DIGIT, err: */
if quotient != nil {
err = clamp(q);
- swap(q, quotient);
+ internal_swap(q, quotient);
}
- destroy(q);
+ internal_destroy(q);
return remainder, nil;
}
@@ -314,19 +322,20 @@ _private_int_div_3 :: proc(quotient, numerator: ^Int) -> (remainder: DIGIT, err: It also doesn't consider the case that y has fewer than three digits, etc.
The overall algorithm is as described as 14.20 from HAC but fixed to treat these cases.
*/
-_private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^Int) -> (err: Error) {
- // if err = error_if_immutable(quotient, remainder); err != nil { return err; }
- // if err = clear_if_uninitialized(quotient, numerator, denominator); err != nil { return err; }
+_private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
+
+ if err = error_if_immutable(quotient, remainder); err != nil { return err; }
q, x, y, t1, t2 := &Int{}, &Int{}, &Int{}, &Int{}, &Int{};
- defer destroy(q, x, y, t1, t2);
+ defer internal_destroy(q, x, y, t1, t2);
- if err = grow(q, numerator.used + 2); err != nil { return err; }
+ if err = internal_grow(q, numerator.used + 2); err != nil { return err; }
q.used = numerator.used + 2;
- if err = init_multi(t1, t2); err != nil { return err; }
- if err = copy(x, numerator); err != nil { return err; }
- if err = copy(y, denominator); err != nil { return err; }
+ if err = internal_init_multi(t1, t2); err != nil { return err; }
+ if err = internal_copy(x, numerator); err != nil { return err; }
+ if err = internal_copy(y, denominator); err != nil { return err; }
/*
Fix the sign.
@@ -338,13 +347,12 @@ _private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^In /*
Normalize both x and y, ensure that y >= b/2, [b == 2**MP_DIGIT_BIT]
*/
- norm, _ := count_bits(y);
- norm %= _DIGIT_BITS;
+ norm := internal_count_bits(y) % _DIGIT_BITS;
if norm < _DIGIT_BITS - 1 {
norm = (_DIGIT_BITS - 1) - norm;
- if err = shl(x, x, norm); err != nil { return err; }
- if err = shl(y, y, norm); err != nil { return err; }
+ if err = internal_shl(x, x, norm); err != nil { return err; }
+ if err = internal_shl(y, y, norm); err != nil { return err; }
} else {
norm = 0;
}
@@ -360,19 +368,19 @@ _private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^In y = y*b**{n-t}
*/
- if err = shl_digit(y, n - t); err != nil { return err; }
+ if err = internal_shl_digit(y, n - t); err != nil { return err; }
- c, _ := cmp(x, y);
+ c := internal_cmp(x, y);
for c != -1 {
q.digit[n - t] += 1;
- if err = sub(x, x, y); err != nil { return err; }
- c, _ = cmp(x, y);
+ if err = internal_sub(x, x, y); err != nil { return err; }
+ c = internal_cmp(x, y);
}
/*
Reset y by shifting it back down.
*/
- shr_digit(y, n - t);
+ internal_shr_digit(y, n - t);
/*
Step 3. for i from n down to (t + 1).
@@ -411,11 +419,11 @@ _private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^In /*
Find left hand.
*/
- zero(t1);
+ internal_zero(t1);
t1.digit[0] = ((t - 1) < 0) ? 0 : y.digit[t - 1];
t1.digit[1] = y.digit[t];
t1.used = 2;
- if err = mul(t1, t1, q.digit[(i - t) - 1]); err != nil { return err; }
+ if err = internal_mul(t1, t1, q.digit[(i - t) - 1]); err != nil { return err; }
/*
Find right hand.
@@ -425,7 +433,7 @@ _private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^In t2.digit[2] = x.digit[i];
t2.used = 3;
- if t1_t2, _ := cmp_mag(t1, t2); t1_t2 != 1 {
+ if t1_t2 := internal_cmp_mag(t1, t2); t1_t2 != 1 {
break;
}
iter += 1; if iter > 100 { return .Max_Iterations_Reached; }
@@ -435,16 +443,16 @@ _private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^In Step 3.3 x = x - q{i-t-1} * y * b**{i-t-1}
*/
if err = int_mul_digit(t1, y, q.digit[(i - t) - 1]); err != nil { return err; }
- if err = shl_digit(t1, (i - t) - 1); err != nil { return err; }
- if err = sub(x, x, t1); err != nil { return err; }
+ if err = internal_shl_digit(t1, (i - t) - 1); err != nil { return err; }
+ if err = internal_sub(x, x, t1); err != nil { return err; }
/*
if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; }
*/
if x.sign == .Negative {
- if err = copy(t1, y); err != nil { return err; }
- if err = shl_digit(t1, (i - t) - 1); err != nil { return err; }
- if err = add(x, x, t1); err != nil { return err; }
+ if err = internal_copy(t1, y); err != nil { return err; }
+ if err = internal_shl_digit(t1, (i - t) - 1); err != nil { return err; }
+ if err = internal_add(x, x, t1); err != nil { return err; }
q.digit[(i - t) - 1] = (q.digit[(i - t) - 1] - 1) & _MASK;
}
@@ -458,14 +466,14 @@ _private_int_div_school :: proc(quotient, remainder, numerator, denominator: ^In x.sign = .Zero_or_Positive if z else numerator.sign;
if quotient != nil {
- clamp(q);
- swap(q, quotient);
+ internal_clamp(q);
+ internal_swap(q, quotient);
quotient.sign = .Negative if neg else .Zero_or_Positive;
}
if remainder != nil {
- if err = shr(x, x, norm); err != nil { return err; }
- swap(x, remainder);
+ if err = internal_shr(x, x, norm); err != nil { return err; }
+ internal_swap(x, remainder);
}
return nil;
@@ -601,7 +609,9 @@ _private_int_recursive_product :: proc(res: ^Int, start, stop: int, level := int If neither result is wanted, we have nothing to do.
*/
-_private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) {
+_private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
+
if res_gcd == nil && res_lcm == nil { return nil; }
/*
@@ -612,10 +622,10 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { GCD(0, 0) and LCM(0, 0) are both 0.
*/
if res_gcd != nil {
- if err = zero(res_gcd); err != nil { return err; }
+ if err = internal_zero(res_gcd); err != nil { return err; }
}
if res_lcm != nil {
- if err = zero(res_lcm); err != nil { return err; }
+ if err = internal_zero(res_lcm); err != nil { return err; }
}
return nil;
} else if a.used == 0 {
@@ -623,10 +633,10 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { We can early out with GCD = B and LCM = 0
*/
if res_gcd != nil {
- if err = abs(res_gcd, b); err != nil { return err; }
+ if err = internal_abs(res_gcd, b); err != nil { return err; }
}
if res_lcm != nil {
- if err = zero(res_lcm); err != nil { return err; }
+ if err = internal_zero(res_lcm); err != nil { return err; }
}
return nil;
} else if b.used == 0 {
@@ -634,25 +644,25 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { We can early out with GCD = A and LCM = 0
*/
if res_gcd != nil {
- if err = abs(res_gcd, a); err != nil { return err; }
+ if err = internal_abs(res_gcd, a); err != nil { return err; }
}
if res_lcm != nil {
- if err = zero(res_lcm); err != nil { return err; }
+ if err = internal_zero(res_lcm); err != nil { return err; }
}
return nil;
}
temp_gcd_res := &Int{};
- defer destroy(temp_gcd_res);
+ defer internal_destroy(temp_gcd_res);
/*
If neither `a` or `b` was zero, we need to compute `gcd`.
Get copies of `a` and `b` we can modify.
*/
u, v := &Int{}, &Int{};
- defer destroy(u, v);
- if err = copy(u, a); err != nil { return err; }
- if err = copy(v, b); err != nil { return err; }
+ defer internal_destroy(u, v);
+ if err = internal_copy(u, a); err != nil { return err; }
+ if err = internal_copy(v, b); err != nil { return err; }
/*
Must be positive for the remainder of the algorithm.
@@ -662,37 +672,37 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { /*
B1. Find the common power of two for `u` and `v`.
*/
- u_lsb, _ := count_lsb(u);
- v_lsb, _ := count_lsb(v);
+ u_lsb, _ := internal_count_lsb(u);
+ v_lsb, _ := internal_count_lsb(v);
k := min(u_lsb, v_lsb);
if k > 0 {
/*
Divide the power of two out.
*/
- if err = shr(u, u, k); err != nil { return err; }
- if err = shr(v, v, k); err != nil { return err; }
+ if err = internal_shr(u, u, k); err != nil { return err; }
+ if err = internal_shr(v, v, k); err != nil { return err; }
}
/*
Divide any remaining factors of two out.
*/
if u_lsb != k {
- if err = shr(u, u, u_lsb - k); err != nil { return err; }
+ if err = internal_shr(u, u, u_lsb - k); err != nil { return err; }
}
if v_lsb != k {
- if err = shr(v, v, v_lsb - k); err != nil { return err; }
+ if err = internal_shr(v, v, v_lsb - k); err != nil { return err; }
}
for v.used != 0 {
/*
Make sure `v` is the largest.
*/
- if c, _ := cmp_mag(u, v); c == 1 {
+ if internal_cmp_mag(u, v) == 1 {
/*
Swap `u` and `v` to make sure `v` is >= `u`.
*/
- swap(u, v);
+ internal_swap(u, v);
}
/*
@@ -703,14 +713,14 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { /*
Divide out all factors of two.
*/
- b, _ := count_lsb(v);
- if err = shr(v, v, b); err != nil { return err; }
+ b, _ := internal_count_lsb(v);
+ if err = internal_shr(v, v, b); err != nil { return err; }
}
/*
Multiply by 2**k which we divided out at the beginning.
*/
- if err = shl(temp_gcd_res, u, k); err != nil { return err; }
+ if err = internal_shl(temp_gcd_res, u, k); err != nil { return err; }
temp_gcd_res.sign = .Zero_or_Positive;
/*
@@ -718,7 +728,7 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { If we don't want `lcm`, we're done.
*/
if res_lcm == nil {
- swap(temp_gcd_res, res_gcd);
+ internal_swap(temp_gcd_res, res_gcd);
return nil;
}
@@ -726,7 +736,7 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { Computes least common multiple as `|a*b|/gcd(a,b)`
Divide the smallest by the GCD.
*/
- if c, _ := cmp_mag(a, b); c == -1 {
+ if internal_cmp_mag(a, b) == -1 {
/*
Store quotient in `t2` such that `t2 * b` is the LCM.
*/
@@ -741,7 +751,7 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { }
if res_gcd != nil {
- swap(temp_gcd_res, res_gcd);
+ internal_swap(temp_gcd_res, res_gcd);
}
/*
@@ -751,6 +761,104 @@ _private_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int) -> (err: Error) { return err;
}
+/*
+ Internal implementation of log.
+ Assumes `a` not to be `nil` and to have been initialized.
+*/
+_private_int_log :: proc(a: ^Int, base: DIGIT, allocator := context.allocator) -> (res: int, err: Error) {
+ bracket_low, bracket_high, bracket_mid, t, bi_base := &Int{}, &Int{}, &Int{}, &Int{}, &Int{};
+ defer destroy(bracket_low, bracket_high, bracket_mid, t, bi_base);
+
+ ic := #force_inline internal_cmp(a, base);
+ if ic == -1 || ic == 0 {
+ return 1 if ic == 0 else 0, nil;
+ }
+
+ if err = internal_set(bi_base, base, true, allocator); err != nil { return -1, err; }
+ if err = internal_clear(bracket_mid, false, allocator); err != nil { return -1, err; }
+ if err = internal_clear(t, false, allocator); err != nil { return -1, err; }
+ if err = internal_one(bracket_low, false, allocator); err != nil { return -1, err; }
+ if err = internal_set(bracket_high, base, false, allocator); err != nil { return -1, err; }
+
+ low := 0; high := 1;
+
+ /*
+ A kind of Giant-step/baby-step algorithm.
+ Idea shamelessly stolen from https://programmingpraxis.com/2010/05/07/integer-logarithms/2/
+ The effect is asymptotic, hence needs benchmarks to test if the Giant-step should be skipped
+ for small n.
+ */
+
+ for {
+ /*
+ Iterate until `a` is bracketed between low + high.
+ */
+ if #force_inline internal_cmp(bracket_high, a) != -1 { break; }
+
+ low = high;
+ if err = #force_inline internal_copy(bracket_low, bracket_high); err != nil { return -1, err; }
+ high <<= 1;
+ if err = #force_inline internal_sqr(bracket_high, bracket_high); err != nil { return -1, err; }
+ }
+
+ for (high - low) > 1 {
+ mid := (high + low) >> 1;
+
+ if err = #force_inline internal_pow(t, bi_base, mid - low); err != nil { return -1, err; }
+
+ if err = #force_inline internal_mul(bracket_mid, bracket_low, t); err != nil { return -1, err; }
+
+ mc := #force_inline internal_cmp(a, bracket_mid);
+ switch mc {
+ case -1:
+ high = mid;
+ internal_swap(bracket_mid, bracket_high);
+ case 0:
+ return mid, nil;
+ case 1:
+ low = mid;
+ internal_swap(bracket_mid, bracket_low);
+ }
+ }
+
+ fc := #force_inline internal_cmp(bracket_high, a);
+ res = high if fc == 0 else low;
+
+ return;
+}
+
+/*
+ Returns the log2 of an `Int`.
+ Assumes `a` not to be `nil` and to have been initialized.
+ Also assumes `base` is a power of two.
+*/
+_private_log_power_of_two :: proc(a: ^Int, base: DIGIT) -> (log: int, err: Error) {
+ base := base;
+ y: int;
+ for y = 0; base & 1 == 0; {
+ y += 1;
+ base >>= 1;
+ }
+ log = internal_count_bits(a);
+ return (log - 1) / y, err;
+}
+
+/*
+ Copies DIGITs from `src` to `dest`.
+ Assumes `src` and `dest` to not be `nil` and have been initialized.
+*/
+_private_copy_digits :: proc(dest, src: ^Int, digits: int) -> (err: Error) {
+ digits := digits;
+ /*
+ If dest == src, do nothing
+ */
+ if dest == src { return nil; }
+
+ digits = min(digits, len(src.digit), len(dest.digit));
+ mem.copy_non_overlapping(&dest.digit[0], &src.digit[0], size_of(DIGIT) * digits);
+ return nil;
+}
+
/*
======================== End of private procedures =======================
diff --git a/core/math/big/public.odin b/core/math/big/public.odin index f5dbbe06d..3ab5a8924 100644 --- a/core/math/big/public.odin +++ b/core/math/big/public.odin @@ -22,11 +22,13 @@ package big */
int_add :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, a, b);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, a, b); err != nil { return err; }
/*
All parameters have been initialized.
*/
- return #force_inline internal_int_add_signed(dest, a, b, allocator);
+ return #force_inline internal_int_add_signed(dest, a, b);
}
/*
@@ -37,11 +39,13 @@ int_add :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error */
int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return err; }
/*
Grow destination as required.
*/
- if err = grow(dest, a.used + 1, false, allocator); err != nil { return err; }
+ if err = grow(dest, a.used + 1); err != nil { return err; }
/*
All parameters have been initialized.
@@ -54,11 +58,13 @@ int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocato */
int_sub :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, number, decrease);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, number, decrease); err != nil { return err; }
/*
All parameters have been initialized.
*/
- return #force_inline internal_int_sub_signed(dest, number, decrease, allocator);
+ return #force_inline internal_int_sub_signed(dest, number, decrease);
}
/*
@@ -69,11 +75,13 @@ int_sub :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> */
int_sub_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return err; }
/*
Grow destination as required.
*/
- if err = grow(dest, a.used + 1, false, allocator); err != nil { return err; }
+ if err = grow(dest, a.used + 1); err != nil { return err; }
/*
All parameters have been initialized.
@@ -85,8 +93,10 @@ int_sub_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocato dest = src / 2
dest = src >> 1
*/
-int_halve :: proc(dest, src: ^Int) -> (err: Error) {
+int_halve :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, src);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, src); err != nil { return err; }
/*
Grow destination as required.
@@ -102,8 +112,10 @@ shr1 :: halve; dest = src * 2
dest = src << 1
*/
-int_double :: proc(dest, src: ^Int) -> (err: Error) {
+int_double :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, src);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, src); err != nil { return err; }
/*
Grow destination as required.
@@ -120,9 +132,11 @@ shl1 :: double; */
int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, src);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(src, dest); err != nil { return err; }
- return #force_inline internal_int_mul_digit(dest, src, multiplier, allocator);
+ return #force_inline internal_int_mul_digit(dest, src, multiplier);
}
/*
@@ -130,9 +144,11 @@ int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := context.a */
int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, src, multiplier);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, src, multiplier); err != nil { return err; }
- return #force_inline internal_int_mul(dest, src, multiplier, allocator);
+ return #force_inline internal_int_mul(dest, src, multiplier);
}
mul :: proc { int_mul, int_mul_digit, };
@@ -143,7 +159,9 @@ sqr :: proc(dest, src: ^Int) -> (err: Error) { return mul(dest, src, src); } divmod.
Both the quotient and remainder are optional and may be passed a nil.
*/
-int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int) -> (err: Error) {
+int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
+
/*
Early out if neither of the results is wanted.
*/
@@ -153,23 +171,29 @@ int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int) -> (err: E return #force_inline internal_divmod(quotient, remainder, numerator, denominator);
}
-int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) -> (remainder: DIGIT, err: Error) {
+int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {
assert_if_nil(quotient, numerator);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(numerator); err != nil { return 0, err; }
return #force_inline internal_divmod(quotient, numerator, denominator);
}
divmod :: proc{ int_divmod, int_divmod_digit, };
-int_div :: proc(quotient, numerator, denominator: ^Int) -> (err: Error) {
+int_div :: proc(quotient, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(quotient, numerator, denominator);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(numerator, denominator); err != nil { return err; }
return #force_inline internal_divmod(quotient, nil, numerator, denominator);
}
-int_div_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT) -> (err: Error) {
+int_div_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (err: Error) {
assert_if_nil(quotient, numerator);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(numerator); err != nil { return err; }
remainder: DIGIT;
@@ -183,15 +207,17 @@ div :: proc { int_div, int_div_digit, }; 0 <= remainder < denominator if denominator > 0
denominator < remainder <= 0 if denominator < 0
*/
-int_mod :: proc(remainder, numerator, denominator: ^Int) -> (err: Error) {
+int_mod :: proc(remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(remainder, numerator, denominator);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(numerator, denominator); err != nil { return err; }
return #force_inline internal_int_mod(remainder, numerator, denominator);
}
-int_mod_digit :: proc(numerator: ^Int, denominator: DIGIT) -> (remainder: DIGIT, err: Error) {
- return #force_inline internal_divmod(nil, numerator, denominator);
+int_mod_digit :: proc(numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {
+ return #force_inline internal_divmod(nil, numerator, denominator, allocator);
}
mod :: proc { int_mod, int_mod_digit, };
@@ -199,8 +225,10 @@ mod :: proc { int_mod, int_mod_digit, }; /*
remainder = (number + addend) % modulus.
*/
-int_addmod :: proc(remainder, number, addend, modulus: ^Int) -> (err: Error) {
+int_addmod :: proc(remainder, number, addend, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(remainder, number, addend);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(number, addend, modulus); err != nil { return err; }
return #force_inline internal_addmod(remainder, number, addend, modulus);
@@ -210,8 +238,10 @@ addmod :: proc { int_addmod, }; /*
remainder = (number - decrease) % modulus.
*/
-int_submod :: proc(remainder, number, decrease, modulus: ^Int) -> (err: Error) {
+int_submod :: proc(remainder, number, decrease, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(remainder, number, decrease);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(number, decrease, modulus); err != nil { return err; }
return #force_inline internal_submod(remainder, number, decrease, modulus);
@@ -221,8 +251,10 @@ submod :: proc { int_submod, }; /*
remainder = (number * multiplicand) % modulus.
*/
-int_mulmod :: proc(remainder, number, multiplicand, modulus: ^Int) -> (err: Error) {
+int_mulmod :: proc(remainder, number, multiplicand, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(remainder, number, multiplicand);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(number, multiplicand, modulus); err != nil { return err; }
return #force_inline internal_mulmod(remainder, number, multiplicand, modulus);
@@ -232,8 +264,10 @@ mulmod :: proc { int_mulmod, }; /*
remainder = (number * number) % modulus.
*/
-int_sqrmod :: proc(remainder, number, modulus: ^Int) -> (err: Error) {
+int_sqrmod :: proc(remainder, number, modulus: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(remainder, number, modulus);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(number, modulus); err != nil { return err; }
return #force_inline internal_sqrmod(remainder, number, modulus);
@@ -241,11 +275,11 @@ int_sqrmod :: proc(remainder, number, modulus: ^Int) -> (err: Error) { sqrmod :: proc { int_sqrmod, };
-int_factorial :: proc(res: ^Int, n: int) -> (err: Error) {
+int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator) -> (err: Error) {
if n < 0 || n > FACTORIAL_MAX_N { return .Invalid_Argument; }
assert_if_nil(res);
- return #force_inline internal_int_factorial(res, n);
+ return #force_inline internal_int_factorial(res, n, allocator);
}
factorial :: proc { int_factorial, };
@@ -265,17 +299,18 @@ factorial :: proc { int_factorial, }; k, start from previous result
*/
-int_choose_digit :: proc(res: ^Int, n, k: int) -> (err: Error) {
+int_choose_digit :: proc(res: ^Int, n, k: int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(res);
- if n < 0 || n > FACTORIAL_MAX_N { return .Invalid_Argument; }
+ context.allocator = allocator;
- if k > n { return zero(res); }
+ if n < 0 || n > FACTORIAL_MAX_N { return .Invalid_Argument; }
+ if k > n { return internal_zero(res); }
/*
res = n! / (k! * (n - k)!)
*/
n_fac, k_fac, n_minus_k_fac := &Int{}, &Int{}, &Int{};
- defer destroy(n_fac, k_fac, n_minus_k_fac);
+ defer internal_destroy(n_fac, k_fac, n_minus_k_fac);
if err = #force_inline internal_int_factorial(n_minus_k_fac, n - k); err != nil { return err; }
if err = #force_inline internal_int_factorial(k_fac, k); err != nil { return err; }
@@ -294,9 +329,9 @@ choose :: proc { int_choose_digit, }; 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; }
assert_if_nil(a, b);
+ context.allocator = allocator;
- if err = internal_clear_if_uninitialized(a, allocator); err != nil { return err; }
- if err = internal_clear_if_uninitialized(b, allocator); err != nil { return err; }
+ if err = internal_clear_if_uninitialized(a, b); err != nil { return err; }
return #force_inline internal_int_gcd_lcm(res_gcd, res_lcm, a, b);
}
gcd_lcm :: proc { int_gcd_lcm, };
@@ -304,24 +339,25 @@ gcd_lcm :: proc { int_gcd_lcm, }; /*
Greatest Common Divisor.
*/
-int_gcd :: proc(res, a, b: ^Int) -> (err: Error) {
- return #force_inline int_gcd_lcm(res, nil, a, b);
+int_gcd :: proc(res, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
+ return #force_inline int_gcd_lcm(res, nil, a, b, allocator);
}
gcd :: proc { int_gcd, };
/*
Least Common Multiple.
*/
-int_lcm :: proc(res, a, b: ^Int) -> (err: Error) {
- return #force_inline int_gcd_lcm(nil, res, a, b);
+int_lcm :: proc(res, a, b: ^Int, allocator := context.allocator) -> (err: Error) {
+ return #force_inline int_gcd_lcm(nil, res, a, b, allocator);
}
lcm :: proc { int_lcm, };
/*
remainder = numerator % (1 << bits)
*/
-int_mod_bits :: proc(remainder, numerator: ^Int, bits: int) -> (err: Error) {
+int_mod_bits :: proc(remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(remainder, numerator);
+ context.allocator = allocator;
if err = internal_clear_if_uninitialized(remainder, numerator); err != nil { return err; }
if bits < 0 { return .Invalid_Argument; }
@@ -335,8 +371,10 @@ mod_bits :: proc { int_mod_bits, }; /*
Logs and roots and such.
*/
-int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) {
+int_log :: proc(a: ^Int, base: DIGIT, allocator := context.allocator) -> (res: int, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return 0, err; }
return #force_inline internal_int_log(a, base);
@@ -350,8 +388,10 @@ log :: proc { int_log, digit_log, }; /*
Calculate `dest = base^power` using a square-multiply algorithm.
*/
-int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) {
+int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, base);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, base); err != nil { return err; }
return #force_inline internal_int_pow(dest, base, power);
@@ -360,10 +400,10 @@ int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) { /*
Calculate `dest = base^power` using a square-multiply algorithm.
*/
-int_pow_int :: proc(dest: ^Int, base, power: int) -> (err: Error) {
+int_pow_int :: proc(dest: ^Int, base, power: int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest);
- return #force_inline internal_pow(dest, base, power);
+ return #force_inline internal_pow(dest, base, power, allocator);
}
pow :: proc { int_pow, int_pow_int, small_pow, };
@@ -376,8 +416,10 @@ small_pow :: proc(base: _WORD, exponent: _WORD) -> (result: _WORD) { /*
This function is less generic than `root_n`, simpler and faster.
*/
-int_sqrt :: proc(dest, src: ^Int) -> (err: Error) {
+int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {
assert_if_nil(dest, src);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(dest, src); err != nil { return err; }
return #force_inline internal_int_sqrt(dest, src);
@@ -392,7 +434,9 @@ sqrt :: proc { int_sqrt, }; This algorithm uses Newton's approximation `x[i+1] = x[i] - f(x[i])/f'(x[i])`,
which will find the root in `log(n)` time where each step involves a fair bit.
*/
-int_root_n :: proc(dest, src: ^Int, n: int) -> (err: Error) {
+int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.allocator) -> (err: Error) {
+ context.allocator = allocator;
+
/*
Fast path for n == 2.
*/
@@ -418,36 +462,46 @@ int_is_initialized :: proc(a: ^Int) -> bool { return #force_inline internal_int_is_initialized(a);
}
-int_is_zero :: proc(a: ^Int) -> (zero: bool, err: Error) {
+int_is_zero :: proc(a: ^Int, allocator := context.allocator) -> (zero: bool, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return false, err; }
return #force_inline internal_is_zero(a), nil;
}
-int_is_positive :: proc(a: ^Int) -> (positive: bool, err: Error) {
+int_is_positive :: proc(a: ^Int, allocator := context.allocator) -> (positive: bool, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return false, err; }
return #force_inline internal_is_positive(a), nil;
}
-int_is_negative :: proc(a: ^Int) -> (negative: bool, err: Error) {
+int_is_negative :: proc(a: ^Int, allocator := context.allocator) -> (negative: bool, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return false, err; }
return #force_inline internal_is_negative(a), nil;
}
-int_is_even :: proc(a: ^Int) -> (even: bool, err: Error) {
+int_is_even :: proc(a: ^Int, allocator := context.allocator) -> (even: bool, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return false, err; }
return #force_inline internal_is_even(a), nil;
}
-int_is_odd :: proc(a: ^Int) -> (odd: bool, err: Error) {
+int_is_odd :: proc(a: ^Int, allocator := context.allocator) -> (odd: bool, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return false, err; }
return #force_inline internal_is_odd(a), nil;
@@ -457,8 +511,10 @@ platform_int_is_power_of_two :: #force_inline proc(a: int) -> bool { return ((a) != 0) && (((a) & ((a) - 1)) == 0);
}
-int_is_power_of_two :: proc(a: ^Int) -> (res: bool, err: Error) {
+int_is_power_of_two :: proc(a: ^Int, allocator := context.allocator) -> (res: bool, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return false, err; }
return #force_inline internal_is_power_of_two(a), nil;
@@ -467,8 +523,10 @@ int_is_power_of_two :: proc(a: ^Int) -> (res: bool, err: Error) { /*
Compare two `Int`s, signed.
*/
-int_compare :: proc(a, b: ^Int) -> (comparison: int, err: Error) {
+int_compare :: proc(a, b: ^Int, allocator := context.allocator) -> (comparison: int, err: Error) {
assert_if_nil(a, b);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a, b); err != nil { return 0, err; }
return #force_inline internal_cmp(a, b), nil;
@@ -478,8 +536,10 @@ int_cmp :: int_compare; /*
Compare an `Int` to an unsigned number upto the size of the backing type.
*/
-int_compare_digit :: proc(a: ^Int, b: DIGIT) -> (comparison: int, err: Error) {
+int_compare_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (comparison: int, err: Error) {
assert_if_nil(a);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a); err != nil { return 0, err; }
return #force_inline internal_cmp_digit(a, b), nil;
@@ -489,8 +549,10 @@ int_cmp_digit :: int_compare_digit; /*
Compare the magnitude of two `Int`s, unsigned.
*/
-int_compare_magnitude :: proc(a, b: ^Int) -> (res: int, err: Error) {
+int_compare_magnitude :: proc(a, b: ^Int, allocator := context.allocator) -> (res: int, err: Error) {
assert_if_nil(a, b);
+ context.allocator = allocator;
+
if err = internal_clear_if_uninitialized(a, b); err != nil { return 0, err; }
return #force_inline internal_cmp_mag(a, b), nil;
diff --git a/core/math/big/radix.odin b/core/math/big/radix.odin index 28c5a2559..acfcbcf70 100644 --- a/core/math/big/radix.odin +++ b/core/math/big/radix.odin @@ -19,9 +19,10 @@ import "core:mem" */ int_itoa_string :: proc(a: ^Int, radix := i8(-1), zero_terminate := false, allocator := context.allocator) -> (res: string, err: Error) { assert_if_nil(a); + context.allocator = allocator; a := a; radix := radix; - if err = clear_if_uninitialized(a, allocator); err != nil { return "", err; } + if err = clear_if_uninitialized(a); err != nil { return "", err; } /* Radix defaults to 10. */ @@ -46,7 +47,7 @@ int_itoa_string :: proc(a: ^Int, radix := i8(-1), zero_terminate := false, alloc /* Allocate the buffer we need. */ - buffer := make([]u8, size, allocator); + buffer := make([]u8, size); /* Write the digits out into the buffer. @@ -62,16 +63,17 @@ int_itoa_string :: proc(a: ^Int, radix := i8(-1), zero_terminate := false, alloc */ int_itoa_cstring :: proc(a: ^Int, radix := i8(-1), allocator := context.allocator) -> (res: cstring, err: Error) { assert_if_nil(a); + context.allocator = allocator; a := a; radix := radix; - if err = clear_if_uninitialized(a, allocator); err != nil { return "", err; } + if err = clear_if_uninitialized(a); err != nil { return "", err; } /* Radix defaults to 10. */ radix = radix if radix > 0 else 10; s: string; - s, err = int_itoa_string(a, radix, true, allocator); + s, err = int_itoa_string(a, radix, true); return cstring(raw_data(s)), err; } @@ -237,7 +239,10 @@ int_to_cstring :: int_itoa_cstring; Read a string [ASCII] in a given radix. */ int_atoi :: proc(res: ^Int, input: string, radix: i8, allocator := context.allocator) -> (err: Error) { + assert_if_nil(res); input := input; + context.allocator = allocator; + /* Make sure the radix is ok. */ @@ -247,7 +252,7 @@ int_atoi :: proc(res: ^Int, input: string, radix: i8, allocator := context.alloc /* Set the integer to the default of zero. */ - if err = zero(res, false, allocator); err != nil { return err; } + if err = internal_zero(res); err != nil { return err; } /* We'll interpret an empty string as zero. @@ -319,23 +324,21 @@ atoi :: proc { int_atoi, }; /* We size for `string` by default. */ -radix_size :: proc(a: ^Int, radix: i8, zero_terminate := false) -> (size: int, err: Error) { +radix_size :: proc(a: ^Int, radix: i8, zero_terminate := false, allocator := context.allocator) -> (size: int, err: Error) { a := a; - if radix < 2 || radix > 64 { - return -1, .Invalid_Argument; - } - if err = clear_if_uninitialized(a); err != nil { - return 0, err; - } + assert_if_nil(a); - if z, _ := is_zero(a); z { + if radix < 2 || radix > 64 { return -1, .Invalid_Argument; } + if err = clear_if_uninitialized(a); err != nil { return {}, err; } + + if internal_is_zero(a) { if zero_terminate { return 2, nil; } return 1, nil; } - if pot, _ := is_power_of_two(a); pot { + if internal_is_power_of_two(a) { /* Calculate `log` on a temporary "copy" with its sign set to positive. */ @@ -345,28 +348,26 @@ radix_size :: proc(a: ^Int, radix: i8, zero_terminate := false) -> (size: int, e digit = a.digit, }; - if size, err = log(t, DIGIT(radix)); err != nil { - return 0, err; - } + if size, err = internal_log(t, DIGIT(radix)); err != nil { return {}, err; } } else { la, k := &Int{}, &Int{}; - defer destroy(la, k); + defer internal_destroy(la, k); /* la = floor(log_2(a)) + 1 */ - bit_count, _ := count_bits(a); - err = set(la, bit_count); + bit_count := internal_count_bits(a); + if err = internal_set(la, bit_count); err != nil { return {}, err; } /* k = floor(2^29/log_2(radix)) + 1 */ lb := _log_bases; - err = set(k, lb[radix]); + if err = internal_set(k, lb[radix]); err != nil { return {}, err; } /* n = floor((la * k) / 2^29) + 1 */ - if err = mul(k, la, k); err != nil { return 0, err; } - if err = shr(k, k, _RADIX_SIZE_SCALE); err != nil { return 0, err; } + if err = internal_mul(k, la, k); err != nil { return 0, err; } + if err = internal_shr(k, k, _RADIX_SIZE_SCALE); err != nil { return {}, err; } /* The "+1" here is the "+1" in "floor((la * k) / 2^29) + 1" */ /* n = n + 1 + EOS + sign */ - size_, _ := get(k, u128); + size_, _ := internal_get(k, u128); size = int(size_); } @@ -429,11 +430,14 @@ RADIX_TABLE_REVERSE_SIZE :: 80; Stores a bignum as a ASCII string in a given radix (2..64) The buffer must be appropriately sized. This routine doesn't check. */ -_itoa_raw_full :: proc(a: ^Int, radix: i8, buffer: []u8, zero_terminate := false) -> (written: int, err: Error) { +_itoa_raw_full :: proc(a: ^Int, radix: i8, buffer: []u8, zero_terminate := false, allocator := context.allocator) -> (written: int, err: Error) { + assert_if_nil(a); + context.allocator = allocator; + temp, denominator := &Int{}, &Int{}; - if err = copy(temp, a); err != nil { return 0, err; } - if err = set(denominator, radix); err != nil { return 0, err; } + if err = internal_copy(temp, a); err != nil { return 0, err; } + if err = internal_set(denominator, radix); err != nil { return 0, err; } available := len(buffer); if zero_terminate { @@ -448,7 +452,7 @@ _itoa_raw_full :: proc(a: ^Int, radix: i8, buffer: []u8, zero_terminate := false remainder: DIGIT; for { if remainder, err = #force_inline internal_divmod(temp, temp, DIGIT(radix)); err != nil { - destroy(temp, denominator); + internal_destroy(temp, denominator); return len(buffer) - available, err; } available -= 1; @@ -463,7 +467,7 @@ _itoa_raw_full :: proc(a: ^Int, radix: i8, buffer: []u8, zero_terminate := false buffer[available] = '-'; } - destroy(temp, denominator); + internal_destroy(temp, denominator); /* If we overestimated the size, we need to move the buffer left. diff --git a/core/math/big/test.odin b/core/math/big/test.odin index 4aa0b93bf..aae3c1503 100644 --- a/core/math/big/test.odin +++ b/core/math/big/test.odin @@ -40,7 +40,7 @@ PyRes :: struct { err: Error; aa, bb, sum := &Int{}, &Int{}, &Int{}; - defer destroy(aa, bb, sum); + defer internal_destroy(aa, bb, sum); if err = atoi(aa, string(a), 16); err != nil { return PyRes{res=":add:atoi(a):", err=err}; } if err = atoi(bb, string(b), 16); err != nil { return PyRes{res=":add:atoi(b):", err=err}; } @@ -61,7 +61,7 @@ PyRes :: struct { err: Error; aa, bb, sum := &Int{}, &Int{}, &Int{}; - defer destroy(aa, bb, sum); + defer internal_destroy(aa, bb, sum); if err = atoi(aa, string(a), 16); err != nil { return PyRes{res=":sub:atoi(a):", err=err}; } if err = atoi(bb, string(b), 16); err != nil { return PyRes{res=":sub:atoi(b):", err=err}; } @@ -82,7 +82,7 @@ PyRes :: struct { err: Error; aa, bb, product := &Int{}, &Int{}, &Int{}; - defer destroy(aa, bb, product); + defer internal_destroy(aa, bb, product); if err = atoi(aa, string(a), 16); err != nil { return PyRes{res=":mul:atoi(a):", err=err}; } if err = atoi(bb, string(b), 16); err != nil { return PyRes{res=":mul:atoi(b):", err=err}; } @@ -102,7 +102,7 @@ PyRes :: struct { err: Error; aa, bb, quotient := &Int{}, &Int{}, &Int{}; - defer destroy(aa, bb, quotient); + defer internal_destroy(aa, bb, quotient); if err = atoi(aa, string(a), 16); err != nil { return PyRes{res=":div:atoi(a):", err=err}; } if err = atoi(bb, string(b), 16); err != nil { return PyRes{res=":div:atoi(b):", err=err}; } @@ -124,7 +124,7 @@ PyRes :: struct { l: int; aa := &Int{}; - defer destroy(aa); + defer internal_destroy(aa); if err = atoi(aa, string(a), 16); err != nil { return PyRes{res=":log:atoi(a):", err=err}; } if l, err = #force_inline internal_log(aa, base); err != nil { return PyRes{res=":log:log(a, base):", err=err}; } @@ -149,7 +149,7 @@ PyRes :: struct { err: Error; dest, bb := &Int{}, &Int{}; - defer destroy(dest, bb); + defer internal_destroy(dest, bb); if err = atoi(bb, string(base), 16); err != nil { return PyRes{res=":pow:atoi(base):", err=err}; } if err = #force_inline internal_pow(dest, bb, power); err != nil { return PyRes{res=":pow:pow(dest, base, power):", err=err}; } @@ -168,7 +168,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":sqrt:atoi(src):", err=err}; } if err = #force_inline internal_sqrt(src, src); err != nil { return PyRes{res=":sqrt:sqrt(src):", err=err}; } @@ -187,7 +187,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":root_n:atoi(src):", err=err}; } if err = #force_inline internal_root_n(src, src, power); err != nil { return PyRes{res=":root_n:root_n(src):", err=err}; } @@ -206,7 +206,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":shr_digit:atoi(src):", err=err}; } if err = #force_inline internal_shr_digit(src, digits); err != nil { return PyRes{res=":shr_digit:shr_digit(src):", err=err}; } @@ -225,7 +225,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":shl_digit:atoi(src):", err=err}; } if err = #force_inline internal_shl_digit(src, digits); err != nil { return PyRes{res=":shl_digit:shr_digit(src):", err=err}; } @@ -244,7 +244,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":shr:atoi(src):", err=err}; } if err = #force_inline internal_shr(src, src, bits); err != nil { return PyRes{res=":shr:shr(src, bits):", err=err}; } @@ -263,7 +263,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":shr_signed:atoi(src):", err=err}; } if err = #force_inline internal_shr_signed(src, src, bits); err != nil { return PyRes{res=":shr_signed:shr_signed(src, bits):", err=err}; } @@ -282,7 +282,7 @@ PyRes :: struct { err: Error; src := &Int{}; - defer destroy(src); + defer internal_destroy(src); if err = atoi(src, string(source), 16); err != nil { return PyRes{res=":shl:atoi(src):", err=err}; } if err = #force_inline internal_shl(src, src, bits); err != nil { return PyRes{res=":shl:shl(src, bits):", err=err}; } @@ -301,9 +301,9 @@ PyRes :: struct { err: Error; dest := &Int{}; - defer destroy(dest); + defer internal_destroy(dest); - if err = #force_inline factorial(dest, n); err != nil { return PyRes{res=":factorial:factorial(n):", err=err}; } + if err = #force_inline internal_int_factorial(dest, n); err != nil { return PyRes{res=":factorial:factorial(n):", err=err}; } r: cstring; r, err = int_itoa_cstring(dest, 16, context.temp_allocator); @@ -319,11 +319,11 @@ PyRes :: struct { err: Error; ai, bi, dest := &Int{}, &Int{}, &Int{}; - defer destroy(ai, bi, dest); + defer internal_destroy(ai, bi, dest); if err = atoi(ai, string(a), 16); err != nil { return PyRes{res=":gcd:atoi(a):", err=err}; } if err = atoi(bi, string(b), 16); err != nil { return PyRes{res=":gcd:atoi(b):", err=err}; } - if err = #force_inline gcd(dest, ai, bi); err != nil { return PyRes{res=":gcd:gcd(a, b):", err=err}; } + if err = #force_inline internal_int_gcd_lcm(dest, nil, ai, bi); err != nil { return PyRes{res=":gcd:gcd(a, b):", err=err}; } r: cstring; r, err = int_itoa_cstring(dest, 16, context.temp_allocator); @@ -339,11 +339,11 @@ PyRes :: struct { err: Error; ai, bi, dest := &Int{}, &Int{}, &Int{}; - defer destroy(ai, bi, dest); + defer internal_destroy(ai, bi, dest); if err = atoi(ai, string(a), 16); err != nil { return PyRes{res=":lcm:atoi(a):", err=err}; } if err = atoi(bi, string(b), 16); err != nil { return PyRes{res=":lcm:atoi(b):", err=err}; } - if err = #force_inline lcm(dest, ai, bi); err != nil { return PyRes{res=":lcm:lcm(a, b):", err=err}; } + if err = #force_inline internal_int_gcd_lcm(nil, dest, ai, bi); err != nil { return PyRes{res=":lcm:lcm(a, b):", err=err}; } r: cstring; r, err = int_itoa_cstring(dest, 16, context.temp_allocator); diff --git a/core/math/big/test.py b/core/math/big/test.py index ca0ec98c3..72082c2db 100644 --- a/core/math/big/test.py +++ b/core/math/big/test.py @@ -530,6 +530,11 @@ if __name__ == '__main__': print("---- math/big with two random {bits:,} bit numbers ----".format(bits=BITS))
print()
+ #
+ # We've already tested up to the 10th root.
+ #
+ TEST_ROOT_N_PARAMS = [2, 3, 4, 5, 6]
+
for test_proc in RANDOM_TESTS:
if BITS > 1_200 and test_proc in SKIP_LARGE: continue
if BITS > 4_096 and test_proc in SKIP_LARGEST: continue
@@ -545,6 +550,8 @@ if __name__ == '__main__': UNTIL_TIME = TOTAL_TIME + BITS / TIMED_BITS_PER_SECOND
# We run each test for a second per 20k bits
+ index = 0
+
while we_iterate():
a = randint(-(1 << BITS), 1 << BITS)
b = randint(-(1 << BITS), 1 << BITS)
@@ -566,7 +573,8 @@ if __name__ == '__main__': b = Error.Okay
elif test_proc == test_root_n:
a = randint(1, 1 << BITS)
- b = randint(1, 10);
+ b = TEST_ROOT_N_PARAMS[index]
+ index = (index + 1) % len(TEST_ROOT_N_PARAMS)
elif test_proc == test_shl_digit:
b = randint(0, 10);
elif test_proc == test_shr_digit:
|