diff options
| -rw-r--r-- | core/math/big/compare.odin | 102 | ||||
| -rw-r--r-- | core/math/big/helpers.odin | 25 | ||||
| -rw-r--r-- | core/math/big/internal.odin | 662 | ||||
| -rw-r--r-- | core/math/big/private.odin | 2 | ||||
| -rw-r--r-- | core/math/big/public.odin (renamed from core/math/big/basic.odin) | 90 | ||||
| -rw-r--r-- | core/math/big/test.py | 6 |
6 files changed, 768 insertions, 119 deletions
diff --git a/core/math/big/compare.odin b/core/math/big/compare.odin deleted file mode 100644 index 2581a3c38..000000000 --- a/core/math/big/compare.odin +++ /dev/null @@ -1,102 +0,0 @@ -package big - -/* - Copyright 2021 Jeroen van Rijn <nom@duclavier.com>. - Made available under Odin's BSD-2 license. - - An arbitrary precision mathematics implementation in Odin. - For the theoretical underpinnings, see Knuth's The Art of Computer Programming, Volume 2, section 4.3. - The code started out as an idiomatic source port of libTomMath, which is in the public domain, with thanks. - - This file contains various comparison routines. - - We essentially just check if params are initialized before punting to the `internal_*` versions. - This has the side benefit of being able to add additional characteristics to numbers, like NaN, - and keep support for that contained. -*/ - -import "core:intrinsics" - -int_is_initialized :: proc(a: ^Int) -> bool { - if a == nil { return false; } - - return #force_inline internal_int_is_initialized(a); -} - -int_is_zero :: proc(a: ^Int) -> (zero: bool, err: Error) { - if a == nil { return false, .Invalid_Pointer; } - if err = 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) { - if a == nil { return false, .Invalid_Pointer; } - if err = 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) { - if a == nil { return false, .Invalid_Pointer; } - if err = 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) { - if a == nil { return false, .Invalid_Pointer; } - if err = 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) { - if a == nil { return false, .Invalid_Pointer; } - if err = clear_if_uninitialized(a); err != nil { return false, err; } - - return #force_inline internal_is_odd(a), nil; -} - -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) { - if a == nil { return false, .Invalid_Pointer; } - if err = clear_if_uninitialized(a); err != nil { return false, err; } - - return #force_inline internal_is_power_of_two(a), nil; -} - -/* - Compare two `Int`s, signed. -*/ -int_compare :: proc(a, b: ^Int) -> (comparison: int, err: Error) { - if a == nil || b == nil { return 0, .Invalid_Pointer; } - if err = clear_if_uninitialized(a, b); err != nil { return 0, err; } - - return #force_inline internal_cmp(a, b), nil; -} -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) { - if a == nil { return 0, .Invalid_Pointer; } - if err = clear_if_uninitialized(a); err != nil { return 0, err; } - - return #force_inline internal_cmp_digit(a, b), nil; -} -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) { - if a == nil || b == nil { return 0, .Invalid_Pointer; } - if err = clear_if_uninitialized(a, b); err != nil { return 0, err; } - - return #force_inline internal_cmp_mag(a, b), nil; -}
\ No newline at end of file diff --git a/core/math/big/helpers.odin b/core/math/big/helpers.odin index cf7492182..33f091399 100644 --- a/core/math/big/helpers.odin +++ b/core/math/big/helpers.odin @@ -13,8 +13,6 @@ import "core:mem" import "core:intrinsics" import rnd "core:math/rand" -// import "core:fmt" - /* TODO: Int.flags and Constants like ONE, NAN, etc, are not yet properly handled everywhere. */ @@ -26,6 +24,7 @@ int_destroy :: proc(integers: ..^Int) { integers := integers; for a in &integers { + assert(a != nil, "int_destroy(nil)"); mem.zero_slice(a.digit[:]); raw := transmute(mem.Raw_Dynamic_Array)a.digit; if raw.cap > 0 { @@ -328,7 +327,7 @@ zero :: clear; Set the `Int` to 1 and optionally shrink it to the minimum backing size. */ int_one :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { - return copy(a, ONE, minimize, allocator); + return copy(a, INT_ONE, minimize, allocator); } one :: proc { int_one, }; @@ -676,25 +675,29 @@ clamp :: proc(a: ^Int) -> (err: Error) { /* Initialize constants. */ -ONE, ZERO, MINUS_ONE, INF, MINUS_INF, NAN := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{}; +INT_ONE, INT_ZERO, INT_MINUS_ONE, INT_INF, INT_MINUS_INF, INT_NAN := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{}; initialize_constants :: proc() -> (res: int) { - set( ZERO, 0); ZERO.flags = {.Immutable}; - set( ONE, 1); ONE.flags = {.Immutable}; - set(MINUS_ONE, -1); MINUS_ONE.flags = {.Immutable}; + internal_set( INT_ZERO, 0); INT_ZERO.flags = {.Immutable}; + internal_set( INT_ONE, 1); INT_ONE.flags = {.Immutable}; + internal_set(INT_MINUS_ONE, -1); INT_MINUS_ONE.flags = {.Immutable}; /* We set these special values to -1 or 1 so they don't get mistake for zero accidentally. This allows for shortcut tests of is_zero as .used == 0. */ - set( NAN, 1); NAN.flags = {.Immutable, .NaN}; - set( INF, 1); INF.flags = {.Immutable, .Inf}; - set( INF, -1); MINUS_INF.flags = {.Immutable, .Inf}; + internal_set( INT_NAN, 1); INT_NAN.flags = {.Immutable, .NaN}; + internal_set( INT_INF, 1); INT_INF.flags = {.Immutable, .Inf}; + internal_set( INT_INF, -1); INT_MINUS_INF.flags = {.Immutable, .Inf}; return _DEFAULT_MUL_KARATSUBA_CUTOFF; } +/* + Destroy constants. + Optional for an EXE, as this would be called at the very end of a process. +*/ destroy_constants :: proc() { - destroy(ONE, ZERO, MINUS_ONE, INF, NAN); + internal_destroy(INT_ONE, INT_ZERO, INT_MINUS_ONE, INT_INF, INT_MINUS_INF, INT_NAN); } diff --git a/core/math/big/internal.odin b/core/math/big/internal.odin index 43d496215..952d0ed8b 100644 --- a/core/math/big/internal.odin +++ b/core/math/big/internal.odin @@ -31,6 +31,7 @@ package big import "core:mem" import "core:intrinsics" +import rnd "core:math/rand" /* Low-level addition, unsigned. Handbook of Applied Cryptography, algorithm 14.7. @@ -1232,7 +1233,7 @@ internal_int_pow :: proc(dest, base: ^Int, power: int) -> (err: Error) { /* Any base to the power zero is one. */ - return one(dest); + return #force_inline internal_one(dest); case 1: /* Any base to the power one is itself. @@ -1477,7 +1478,7 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int) -> (err: Error) { if ilog2 -= 1; ilog2 == 0 { break; } - if c := internal_cmp(t1, t2); c == 0 { break; } + if c = internal_cmp(t1, t2); c == 0 { break; } iterations += 1; if iterations == MAX_ITERATIONS_ROOT_N { return .Max_Iterations_Reached; @@ -1491,7 +1492,7 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int) -> (err: Error) { for { if err = internal_pow(t2, t1, n); err != nil { return err; } - c := internal_cmp(t2, a); + c = internal_cmp(t2, a); if c == 0 { swap(dest, t1); return nil; @@ -1512,7 +1513,7 @@ internal_int_root_n :: proc(dest, src: ^Int, n: int) -> (err: Error) { for { if err = internal_pow(t2, t1, n); err != nil { return err; } - c := internal_cmp(t2, a); + c = internal_cmp(t2, a); if c == 1 { if err = internal_sub(t1, t1, DIGIT(1)); err != nil { return err; } } else { @@ -1603,6 +1604,659 @@ private_int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) { Other internal helpers */ +/* + Deallocates the backing memory of one or more `Int`s. + Asssumes none of the `integers` to be a `nil`. +*/ +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 { + free(&a.digit[0]); + } + a = &Int{}; + } +} +internal_destroy :: proc{ internal_int_destroy, }; + +/* + Helpers to set an `Int` to a specific value. +*/ +internal_int_set_from_integer :: proc(dest: ^Int, src: $T, minimize := false, allocator := context.allocator) -> (err: Error) + where intrinsics.type_is_integer(T) { + src := src; + + if err = error_if_immutable(dest); err != nil { return err; } + if err = clear_if_uninitialized(dest); err != nil { return err; } + + dest.flags = {}; // We're not -Inf, Inf, NaN or Immutable. + + dest.used = 0; + dest.sign = .Zero_or_Positive if src >= 0 else .Negative; + src = abs(src); + + for src != 0 { + dest.digit[dest.used] = DIGIT(src) & _MASK; + dest.used += 1; + src >>= _DIGIT_BITS; + } + zero_unused(dest); + return nil; +} + +internal_set :: proc { internal_int_set_from_integer, internal_int_copy }; + +/* + Copy one `Int` to another. +*/ +internal_int_copy :: proc(dest, src: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + /* + If dest == src, do nothing + */ + if (dest == src) { return nil; } + + if err = error_if_immutable(dest); err != nil { return err; } + if err = clear_if_uninitialized(src); err != nil { return err; } + + /* + Grow `dest` to fit `src`. + If `dest` is not yet initialized, it will be using `allocator`. + */ + needed := src.used if minimize else max(src.used, _DEFAULT_DIGIT_COUNT); + + if err = grow(dest, needed, minimize, allocator); err != nil { + return err; + } + + /* + Copy everything over and zero high digits. + */ + for v, i in src.digit[:src.used] { + dest.digit[i] = v; + } + dest.used = src.used; + dest.sign = src.sign; + dest.flags = src.flags &~ {.Immutable}; + + zero_unused(dest); + return nil; +} +internal_copy :: proc { internal_int_copy, }; + +/* + In normal code, you can also write `a, b = b, a`. + However, that only swaps within the current scope. + This helper swaps completely. +*/ +internal_int_swap :: proc(a, b: ^Int) { + a := a; b := b; + + a.used, b.used = b.used, a.used; + a.sign, b.sign = b.sign, a.sign; + a.digit, b.digit = b.digit, a.digit; +} +internal_swap :: proc { internal_int_swap, }; + +/* + Set `dest` to |`src`|. +*/ +internal_int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) { + /* + Check that src is usable. + */ + if err = clear_if_uninitialized(src); err != nil { + return err; + } + /* + If `dest == src`, just fix `dest`'s sign. + */ + if (dest == src) { + dest.sign = .Zero_or_Positive; + return nil; + } + + /* + Copy `src` to `dest` + */ + if err = copy(dest, src, false, allocator); err != nil { + return err; + } + + /* + Fix sign. + */ + dest.sign = .Zero_or_Positive; + return nil; +} + +internal_platform_abs :: proc(n: $T) -> T where intrinsics.type_is_integer(T) { + return n if n >= 0 else -n; +} +internal_abs :: proc{ internal_int_abs, internal_platform_abs, }; + +/* + Set `dest` to `-src`. +*/ +internal_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) { + /* + Check that src is usable. + */ + if err = clear_if_uninitialized(src); err != nil { + return err; + } + /* + If `dest == src`, just fix `dest`'s sign. + */ + sign := Sign.Zero_or_Positive; + if z, _ := is_zero(src); z { + sign = .Negative; + } + if n, _ := is_neg(src); n { + sign = .Negative; + } + if (dest == src) { + dest.sign = sign; + return nil; + } + /* + Copy `src` to `dest` + */ + if err = copy(dest, src, false, allocator); err != nil { + return err; + } + + /* + Fix sign. + */ + dest.sign = sign; + return nil; +} + +/* + Helpers to extract values from the `Int`. +*/ +internal_int_bitfield_extract_single :: proc(a: ^Int, offset: int) -> (bit: _WORD, err: Error) { + return int_bitfield_extract(a, offset, 1); +} + +internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WORD, err: Error) { + /* + Check that `a` is usable. + */ + if err = clear_if_uninitialized(a); err != nil { return 0, err; } + /* + Early out for single bit. + */ + if count == 1 { + limb := offset / _DIGIT_BITS; + if limb < 0 || limb >= a.used { return 0, .Invalid_Argument; } + i := _WORD(1 << _WORD((offset % _DIGIT_BITS))); + return 1 if ((_WORD(a.digit[limb]) & i) != 0) else 0, nil; + } + + if count > _WORD_BITS || count < 1 { return 0, .Invalid_Argument; } + + /* + There are 3 possible cases. + - [offset:][:count] covers 1 DIGIT, + e.g. offset: 0, count: 60 = bits 0..59 + - [offset:][:count] covers 2 DIGITS, + e.g. offset: 5, count: 60 = bits 5..59, 0..4 + e.g. offset: 0, count: 120 = bits 0..59, 60..119 + - [offset:][:count] covers 3 DIGITS, + e.g. offset: 40, count: 100 = bits 40..59, 0..59, 0..19 + e.g. offset: 40, count: 120 = bits 40..59, 0..59, 0..39 + */ + + limb := offset / _DIGIT_BITS; + bits_left := count; + bits_offset := offset % _DIGIT_BITS; + + num_bits := min(bits_left, _DIGIT_BITS - bits_offset); + + shift := offset % _DIGIT_BITS; + mask := (_WORD(1) << uint(num_bits)) - 1; + res = (_WORD(a.digit[limb]) >> uint(shift)) & mask; + + bits_left -= num_bits; + if bits_left == 0 { return res, nil; } + + res_shift := num_bits; + num_bits = min(bits_left, _DIGIT_BITS); + mask = (1 << uint(num_bits)) - 1; + + res |= (_WORD(a.digit[limb + 1]) & mask) << uint(res_shift); + + bits_left -= num_bits; + if bits_left == 0 { return res, nil; } + + mask = (1 << uint(bits_left)) - 1; + res_shift += _DIGIT_BITS; + + res |= (_WORD(a.digit[limb + 2]) & mask) << uint(res_shift); + + return res, nil; +} + +/* + Resize backing store. + We don't need to pass the allocator, because the storage itself stores it. + + Assumes `a` not to be `nil`, and to have already been initialized. +*/ +internal_int_shrink :: proc(a: ^Int) -> (err: Error) { + if a == nil { + return .Invalid_Pointer; + } + + needed := max(_MIN_DIGIT_COUNT, a.used); + + if a.used != needed { + return grow(a, needed); + } + return nil; +} +internal_shrink :: proc { internal_int_shrink, }; + +internal_int_grow :: proc(a: ^Int, digits: int, allow_shrink := false, allocator := context.allocator) -> (err: Error) { + if a == nil { + return .Invalid_Pointer; + } + raw := transmute(mem.Raw_Dynamic_Array)a.digit; + + /* + We need at least _MIN_DIGIT_COUNT or a.used digits, whichever is bigger. + The caller is asking for `digits`. Let's be accomodating. + */ + needed := max(_MIN_DIGIT_COUNT, a.used, digits); + if !allow_shrink { + needed = max(needed, raw.cap); + } + + /* + If not yet iniialized, initialize the `digit` backing with the allocator we were passed. + Otherwise, `[dynamic]DIGIT` already knows what allocator was used for it, so resize will do the right thing. + */ + if raw.cap == 0 { + a.digit = mem.make_dynamic_array_len_cap([dynamic]DIGIT, needed, needed, allocator); + } else if raw.cap != needed { + resize(&a.digit, needed); + } + /* + Let's see if the allocation/resize worked as expected. + */ + if len(a.digit) != needed { + return .Out_Of_Memory; + } + return nil; +} +internal_grow :: proc { internal_int_grow, }; + +/* + Clear `Int` and resize it to the default size. +*/ +internal_int_clear :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + if a == nil { + return .Invalid_Pointer; + } + + raw := transmute(mem.Raw_Dynamic_Array)a.digit; + if raw.cap != 0 { + mem.zero_slice(a.digit[:a.used]); + } + a.sign = .Zero_or_Positive; + a.used = 0; + + return grow(a, a.used, minimize, allocator); +} +internal_clear :: proc { internal_int_clear, }; +internal_zero :: internal_clear; + +/* + Set the `Int` to 1 and optionally shrink it to the minimum backing size. +*/ +internal_int_one :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + return internal_copy(a, INT_ONE, minimize, allocator); +} +internal_one :: proc { internal_int_one, }; + +/* + Set the `Int` to -1 and optionally shrink it to the minimum backing size. +*/ +internal_int_minus_one :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + return internal_set(a, -1, minimize, allocator); +} +internal_minus_one :: proc { internal_int_minus_one, }; + +/* + Set the `Int` to Inf and optionally shrink it to the minimum backing size. +*/ +internal_int_inf :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + err = internal_set(a, 1, minimize, allocator); + a.flags |= { .Inf, }; + return err; +} +internal_inf :: proc { internal_int_inf, }; + +/* + Set the `Int` to -Inf and optionally shrink it to the minimum backing size. +*/ +internal_int_minus_inf :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + err = internal_set(a, -1, minimize, allocator); + a.flags |= { .Inf, }; + return err; +} +internal_minus_inf :: proc { internal_int_inf, }; + +/* + Set the `Int` to NaN and optionally shrink it to the minimum backing size. +*/ +internal_int_nan :: proc(a: ^Int, minimize := false, allocator := context.allocator) -> (err: Error) { + err = internal_set(a, 1, minimize, allocator); + a.flags |= { .NaN, }; + return err; +} +internal_nan :: proc { internal_int_nan, }; + +internal_power_of_two :: proc(a: ^Int, power: int) -> (err: Error) { + /* + Check that `a` is usable. + */ + if a == nil { + return .Invalid_Pointer; + } + + 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); err != nil { + return err; + } + /* + Zero the entirety. + */ + mem.zero_slice(a.digit[:]); + + /* + Set the bit. + */ + a.digit[power / _DIGIT_BITS] = 1 << uint((power % _DIGIT_BITS)); + return nil; +} + +internal_int_get_u128 :: proc(a: ^Int) -> (res: u128, err: Error) { + return internal_int_get(a, u128); +} +internal_get_u128 :: proc { internal_int_get_u128, }; + +internal_int_get_i128 :: proc(a: ^Int) -> (res: i128, err: Error) { + return internal_int_get(a, i128); +} +internal_get_i128 :: proc { internal_int_get_i128, }; + +internal_int_get_u64 :: proc(a: ^Int) -> (res: u64, err: Error) { + return internal_int_get(a, u64); +} +internal_get_u64 :: proc { internal_int_get_u64, }; + +internal_int_get_i64 :: proc(a: ^Int) -> (res: i64, err: Error) { + return internal_int_get(a, i64); +} +internal_get_i64 :: proc { internal_int_get_i64, }; + +internal_int_get_u32 :: proc(a: ^Int) -> (res: u32, err: Error) { + return internal_int_get(a, u32); +} +internal_get_u32 :: proc { internal_int_get_u32, }; + +internal_int_get_i32 :: proc(a: ^Int) -> (res: i32, err: Error) { + return internal_int_get(a, i32); +} +internal_get_i32 :: proc { internal_int_get_i32, }; + +/* + TODO: Think about using `count_bits` to check if the value could be returned completely, + and maybe return max(T), .Integer_Overflow if not? +*/ +internal_int_get :: proc(a: ^Int, $T: typeid) -> (res: T, err: Error) where intrinsics.type_is_integer(T) { + if err = clear_if_uninitialized(a); err != nil { return 0, err; } + + size_in_bits := int(size_of(T) * 8); + i := int((size_in_bits + _DIGIT_BITS - 1) / _DIGIT_BITS); + i = min(int(a.used), i); + + for ; i >= 0; i -= 1 { + res <<= uint(0) if size_in_bits <= _DIGIT_BITS else _DIGIT_BITS; + res |= T(a.digit[i]); + if size_in_bits <= _DIGIT_BITS { + break; + }; + } + + when !intrinsics.type_is_unsigned(T) { + /* + Mask off sign bit. + */ + res ~= 1 << uint(size_in_bits - 1); + /* + Set the sign. + */ + if a.sign == .Negative { + res = -res; + } + } + return; +} +internal_get :: proc { internal_int_get, }; + +internal_int_get_float :: proc(a: ^Int) -> (res: f64, err: Error) { + if err = clear_if_uninitialized(a); err != nil { + return 0, err; + } + + l := min(a.used, 17); // log2(max(f64)) is approximately 1020, or 17 legs. + fac := f64(1 << _DIGIT_BITS); + d := 0.0; + + for i := l; i >= 0; i -= 1 { + d = (d * fac) + f64(a.digit[i]); + } + + res = -d if a.sign == .Negative else d; + return; +} + +/* + Count bits in an `Int`. +*/ +internal_count_bits :: proc(a: ^Int) -> (count: int, err: Error) { + if err = clear_if_uninitialized(a); err != nil { + return 0, err; + } + /* + Fast path for zero. + */ + if z, _ := is_zero(a); z { + return 0, nil; + } + /* + Get the number of DIGITs and use it. + */ + count = (a.used - 1) * _DIGIT_BITS; + /* + Take the last DIGIT and count the bits in it. + */ + clz := int(intrinsics.count_leading_zeros(a.digit[a.used - 1])); + count += (_DIGIT_TYPE_BITS - clz); + return; +} + +/* + Returns the number of trailing zeroes before the first one. + Differs from regular `ctz` in that 0 returns 0. +*/ +internal_int_count_lsb :: proc(a: ^Int) -> (count: int, err: Error) { + if err = clear_if_uninitialized(a); err != nil { return -1, err; } + + _ctz :: intrinsics.count_trailing_zeros; + /* + Easy out. + */ + if z, _ := is_zero(a); z { return 0, nil; } + + /* + Scan lower digits until non-zero. + */ + x: int; + for x = 0; x < a.used && a.digit[x] == 0; x += 1 {} + + q := a.digit[x]; + x *= _DIGIT_BITS; + return x + count_lsb(q), nil; +} + +internal_platform_count_lsb :: #force_inline proc(a: $T) -> (count: int) + where intrinsics.type_is_integer(T) && intrinsics.type_is_unsigned(T) { + return int(intrinsics.count_trailing_zeros(a)) if a > 0 else 0; +} + +internal_count_lsb :: proc { internal_int_count_lsb, internal_platform_count_lsb, }; + +internal_int_random_digit :: proc(r: ^rnd.Rand = nil) -> (res: DIGIT) { + when _DIGIT_BITS == 60 { // DIGIT = u64 + return DIGIT(rnd.uint64(r)) & _MASK; + } else when _DIGIT_BITS == 28 { // DIGIT = u32 + return DIGIT(rnd.uint32(r)) & _MASK; + } else { + panic("Unsupported DIGIT size."); + } + + return 0; // We shouldn't get here. +} + +internal_int_rand :: proc(dest: ^Int, bits: int, r: ^rnd.Rand = nil) -> (err: Error) { + bits := bits; + + if bits <= 0 { return .Invalid_Argument; } + + digits := bits / _DIGIT_BITS; + bits %= _DIGIT_BITS; + + if bits > 0 { + digits += 1; + } + + if err = grow(dest, digits); err != nil { return err; } + + for i := 0; i < digits; i += 1 { + dest.digit[i] = int_random_digit(r) & _MASK; + } + if bits > 0 { + dest.digit[digits - 1] &= ((1 << uint(bits)) - 1); + } + dest.used = digits; + return nil; +} +internal_rand :: proc { internal_int_rand, }; + +/* + Internal helpers. +*/ +internal_assert_initialized :: proc(a: ^Int, loc := #caller_location) { + assert(internal_is_initialized(a), "`Int` was not properly initialized.", loc); +} + +internal_clear_if_uninitialized_single :: proc(arg: ^Int) -> (err: Error) { + if !internal_is_initialized(arg) { + if arg == nil { return nil; } + return internal_grow(arg, _DEFAULT_DIGIT_COUNT); + } + return err; +} + +internal_clear_if_uninitialized_multi :: proc(args: ..^Int) -> (err: Error) { + for i in args { + if i == nil { continue; } + if !internal_is_initialized(i) { + e := internal_grow(i, _DEFAULT_DIGIT_COUNT); + if e != nil { err = e; } + } + } + return err; +} +internal_clear_if_uninitialized :: proc {internal_clear_if_uninitialized_single, internal_clear_if_uninitialized_multi, }; + +internal_error_if_immutable_single :: proc(arg: ^Int) -> (err: Error) { + if arg != nil && .Immutable in arg.flags { return .Assignment_To_Immutable; } + return nil; +} + +internal_error_if_immutable_multi :: proc(args: ..^Int) -> (err: Error) { + for i in args { + if i != nil && .Immutable in i.flags { return .Assignment_To_Immutable; } + } + return nil; +} +internal_error_if_immutable :: proc {internal_error_if_immutable_single, internal_error_if_immutable_multi, }; + +/* + Allocates several `Int`s at once. +*/ +internal_int_init_multi :: proc(integers: ..^Int) -> (err: Error) { + integers := integers; + for a in &integers { + if err = internal_clear(a); err != nil { return err; } + } + return nil; +} + +internal_init_multi :: proc { internal_int_init_multi, }; + +_private_copy_digits :: proc(dest, src: ^Int, digits: int) -> (err: Error) { + digits := digits; + if err = clear_if_uninitialized(src); err != nil { return err; } + if err = clear_if_uninitialized(dest); err != nil { return err; } + /* + 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. + Typically very fast. Also fixes the sign if there are no more leading digits. +*/ +internal_clamp :: proc(a: ^Int) -> (err: Error) { + if err = internal_clear_if_uninitialized(a); err != nil { + return err; + } + for a.used > 0 && a.digit[a.used - 1] == 0 { + a.used -= 1; + } + + if z, _ := is_zero(a); z { + a.sign = .Zero_or_Positive; + } + return nil; +} + + internal_int_zero_unused :: #force_inline proc(dest: ^Int, old_used := -1) { /* If we don't pass the number of previously used DIGITs, we zero all remaining ones. diff --git a/core/math/big/private.odin b/core/math/big/private.odin index e9db6e3ef..84e699364 100644 --- a/core/math/big/private.odin +++ b/core/math/big/private.odin @@ -481,7 +481,7 @@ _private_int_div_small :: proc(quotient, remainder, numerator, denominator: ^Int c: int;
goto_end: for {
- if err = one(tq); err != nil { break goto_end; }
+ if err = internal_one(tq); err != nil { break goto_end; }
num_bits, _ := count_bits(numerator);
den_bits, _ := count_bits(denominator);
diff --git a/core/math/big/basic.odin b/core/math/big/public.odin index 425a5488c..2dbb8024f 100644 --- a/core/math/big/basic.odin +++ b/core/math/big/public.odin @@ -403,4 +403,92 @@ int_root_n :: proc(dest, src: ^Int, n: int) -> (err: Error) { return #force_inline internal_int_root_n(dest, src, n);
}
-root_n :: proc { int_root_n, };
\ No newline at end of file +root_n :: proc { int_root_n, };
+
+/*
+ Comparison routines.
+*/
+
+int_is_initialized :: proc(a: ^Int) -> bool {
+ if a == nil { return false; }
+
+ return #force_inline internal_int_is_initialized(a);
+}
+
+int_is_zero :: proc(a: ^Int) -> (zero: bool, err: Error) {
+ if a == nil { return false, .Invalid_Pointer; }
+ if err = 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) {
+ if a == nil { return false, .Invalid_Pointer; }
+ if err = 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) {
+ if a == nil { return false, .Invalid_Pointer; }
+ if err = 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) {
+ if a == nil { return false, .Invalid_Pointer; }
+ if err = 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) {
+ if a == nil { return false, .Invalid_Pointer; }
+ if err = clear_if_uninitialized(a); err != nil { return false, err; }
+
+ return #force_inline internal_is_odd(a), nil;
+}
+
+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) {
+ if a == nil { return false, .Invalid_Pointer; }
+ if err = clear_if_uninitialized(a); err != nil { return false, err; }
+
+ return #force_inline internal_is_power_of_two(a), nil;
+}
+
+/*
+ Compare two `Int`s, signed.
+*/
+int_compare :: proc(a, b: ^Int) -> (comparison: int, err: Error) {
+ if a == nil || b == nil { return 0, .Invalid_Pointer; }
+ if err = clear_if_uninitialized(a, b); err != nil { return 0, err; }
+
+ return #force_inline internal_cmp(a, b), nil;
+}
+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) {
+ if a == nil { return 0, .Invalid_Pointer; }
+ if err = clear_if_uninitialized(a); err != nil { return 0, err; }
+
+ return #force_inline internal_cmp_digit(a, b), nil;
+}
+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) {
+ if a == nil || b == nil { return 0, .Invalid_Pointer; }
+ if err = clear_if_uninitialized(a, b); err != nil { return 0, err; }
+
+ return #force_inline internal_cmp_mag(a, b), nil;
+}
\ No newline at end of file diff --git a/core/math/big/test.py b/core/math/big/test.py index 6bdff91db..ca0ec98c3 100644 --- a/core/math/big/test.py +++ b/core/math/big/test.py @@ -4,6 +4,7 @@ import math import os
import platform
import time
+import gc
from enum import Enum
#
@@ -93,6 +94,11 @@ class Error(Enum): Unimplemented = 127
#
+# Disable garbage collection
+#
+gc.disable()
+
+#
# Set up exported procedures
#
|