diff options
Diffstat (limited to 'v_windows/v/vlib/math/big')
-rw-r--r-- | v_windows/v/vlib/math/big/big.c.v | 344 | ||||
-rw-r--r-- | v_windows/v/vlib/math/big/big.js.v | 198 | ||||
-rw-r--r-- | v_windows/v/vlib/math/big/big_test.v | 181 |
3 files changed, 723 insertions, 0 deletions
diff --git a/v_windows/v/vlib/math/big/big.c.v b/v_windows/v/vlib/math/big/big.c.v new file mode 100644 index 0000000..7ef0534 --- /dev/null +++ b/v_windows/v/vlib/math/big/big.c.v @@ -0,0 +1,344 @@ +module big + +// Wrapper for https://github.com/kokke/tiny-bignum-c +#flag -I @VEXEROOT/thirdparty/bignum +#flag @VEXEROOT/thirdparty/bignum/bn.o +#include "bn.h" + +struct C.bn { +mut: + array [32]u32 +} + +// Big unsigned integer number. +type Number = C.bn + +fn C.bignum_init(n &Number) + +fn C.bignum_from_int(n &Number, i u64) + +fn C.bignum_to_int(n &Number) int + +fn C.bignum_from_string(n &Number, s &char, nbytes int) + +fn C.bignum_to_string(n &Number, s &char, maxsize int) + +// c = a + b +fn C.bignum_add(a &Number, b &Number, c &Number) + +// c = a - b +fn C.bignum_sub(a &Number, b &Number, c &Number) + +// c = a * b +fn C.bignum_mul(a &Number, b &Number, c &Number) + +// c = a / b +fn C.bignum_div(a &Number, b &Number, c &Number) + +// c = a % b +fn C.bignum_mod(a &Number, b &Number, c &Number) + +// c = a/b d=a%b +fn C.bignum_divmod(a &Number, b &Number, c &Number, d &Number) + +// c = a & b +fn C.bignum_and(a &Number, b &Number, c &Number) + +// c = a | b +fn C.bignum_or(a &Number, b &Number, c &Number) + +// c = a xor b +fn C.bignum_xor(a &Number, b &Number, c &Number) + +// b = a << nbits +fn C.bignum_lshift(a &Number, b &Number, nbits int) + +// b = a >> nbits +fn C.bignum_rshift(a &Number, b &Number, nbits int) + +fn C.bignum_cmp(a &Number, b &Number) int + +fn C.bignum_is_zero(a &Number) int + +// n++ +fn C.bignum_inc(n &Number) + +// n-- +fn C.bignum_dec(n &Number) + +// c = a ^ b +fn C.bignum_pow(a &Number, b &Number, c &Number) + +// b = integer_square_root_of(a) +fn C.bignum_isqrt(a &Number, b &Number) + +// copy src number to dst number +fn C.bignum_assign(dst &Number, src &Number) + +// new returns a bignum, initialized to 0 +pub fn new() Number { + return Number{} +} + +// conversion actions to/from big numbers: +// from_int converts an ordinary int number `i` to big.Number +pub fn from_int(i int) Number { + n := Number{} + C.bignum_from_int(&n, i) + return n +} + +// from_u64 converts an ordinary u64 number `u` to big.Number +pub fn from_u64(u u64) Number { + n := Number{} + C.bignum_from_int(&n, u) + return n +} + +// from_hex_string converts a hex string to big.Number +pub fn from_hex_string(input string) Number { + mut s := input.trim_prefix('0x') + if s.len == 0 { + s = '0' + } + padding := '0'.repeat((8 - s.len % 8) % 8) + s = padding + s + n := Number{} + C.bignum_from_string(&n, &char(s.str), s.len) + return n +} + +// from_string converts a decimal string to big.Number +pub fn from_string(input string) Number { + mut n := from_int(0) + for _, c in input { + d := from_int(int(c - `0`)) + n = (n * big.ten) + d + } + return n +} + +// from_bytes converts an array of bytes (little-endian) to a big.Number. +// Higher precedence bytes are expected at lower indices in the array. +pub fn from_bytes(input []byte) ?Number { + if input.len > 128 { + return error('input array too large. big.Number can only hold up to 1024 bit numbers') + } + // pad input + mut padded_input := []byte{len: ((input.len + 3) & ~0x3) - input.len, cap: (input.len + 3) & ~0x3, init: 0x0} + padded_input << input + // combine every 4 bytes into a u32 and insert into n.array + mut n := Number{} + for i := 0; i < padded_input.len; i += 4 { + x3 := u32(padded_input[i]) + x2 := u32(padded_input[i + 1]) + x1 := u32(padded_input[i + 2]) + x0 := u32(padded_input[i + 3]) + val := (x3 << 24) | (x2 << 16) | (x1 << 8) | x0 + n.array[(padded_input.len - i) / 4 - 1] = val + } + return n +} + +// .int() converts (a small) big.Number `n` to an ordinary integer. +pub fn (n &Number) int() int { + r := C.bignum_to_int(n) + return r +} + +const ( + ten = from_int(10) +) + +// .str returns a decimal representation of the big unsigned integer number n. +pub fn (n &Number) str() string { + if n.is_zero() { + return '0' + } + mut digits := []byte{} + mut x := n.clone() + + for !x.is_zero() { + // changes to reflect new api + div, mod := divmod(&x, &big.ten) + digits << byte(mod.int()) + `0` + x = div + } + return digits.reverse().bytestr() +} + +// .hexstr returns a hexadecimal representation of the bignum `n` +pub fn (n &Number) hexstr() string { + mut buf := [8192]byte{} + mut s := '' + unsafe { + bp := &buf[0] + // NB: C.bignum_to_string(), returns the HEXADECIMAL representation of the bignum n + C.bignum_to_string(n, &char(bp), 8192) + s = tos_clone(bp) + } + if s.len == 0 { + return '0' + } + return s +} + +// ////////////////////////////////////////////////////////// +// overloaded ops for the numbers: +pub fn (a &Number) + (b &Number) Number { + c := Number{} + C.bignum_add(a, b, &c) + return c +} + +pub fn (a &Number) - (b &Number) Number { + c := Number{} + C.bignum_sub(a, b, &c) + return c +} + +pub fn (a &Number) * (b &Number) Number { + c := Number{} + C.bignum_mul(a, b, &c) + return c +} + +pub fn (a &Number) / (b &Number) Number { + c := Number{} + C.bignum_div(a, b, &c) + return c +} + +pub fn (a &Number) % (b &Number) Number { + c := Number{} + C.bignum_mod(a, b, &c) + return c +} + +// divmod returns a pair of quotient and remainder from div modulo operation +// between two bignums `a` and `b` +pub fn divmod(a &Number, b &Number) (Number, Number) { + c := Number{} + d := Number{} + C.bignum_divmod(a, b, &c, &d) + return c, d +} + +// ////////////////////////////////////////////////////////// +pub fn cmp(a &Number, b &Number) int { + return C.bignum_cmp(a, b) +} + +pub fn (a &Number) is_zero() bool { + return C.bignum_is_zero(a) != 0 +} + +pub fn (mut a Number) inc() { + C.bignum_inc(&a) +} + +pub fn (mut a Number) dec() { + C.bignum_dec(&a) +} + +pub fn pow(a &Number, b &Number) Number { + c := Number{} + C.bignum_pow(a, b, &c) + return c +} + +pub fn (a &Number) isqrt() Number { + b := Number{} + C.bignum_isqrt(a, &b) + return b +} + +// ////////////////////////////////////////////////////////// +pub fn b_and(a &Number, b &Number) Number { + c := Number{} + C.bignum_and(a, b, &c) + return c +} + +pub fn b_or(a &Number, b &Number) Number { + c := Number{} + C.bignum_or(a, b, &c) + return c +} + +pub fn b_xor(a &Number, b &Number) Number { + c := Number{} + C.bignum_xor(a, b, &c) + return c +} + +pub fn (a &Number) lshift(nbits int) Number { + b := Number{} + C.bignum_lshift(a, &b, nbits) + return b +} + +pub fn (a &Number) rshift(nbits int) Number { + b := Number{} + C.bignum_rshift(a, &b, nbits) + return b +} + +pub fn (a &Number) clone() Number { + b := Number{} + C.bignum_assign(&b, a) + return b +} + +// ////////////////////////////////////////////////////////// +pub fn factorial(nn &Number) Number { + mut n := nn.clone() + mut a := nn.clone() + n.dec() + mut i := 1 + for !n.is_zero() { + res := a * n + n.dec() + a = res + i++ + } + return a +} + +pub fn fact(n int) Number { + return factorial(from_int(n)) +} + +// bytes returns an array of the bytes for the number `n`, +// in little endian format, where .bytes()[0] is the least +// significant byte. The result is NOT trimmed, and will contain 0s, even +// after the significant bytes. +// This method is faster than .bytes_trimmed(), but may be less convenient. +// Example: assert big.from_int(1).bytes()[0] == byte(0x01) +// Example: assert big.from_int(1024).bytes()[1] == byte(0x04) +// Example: assert big.from_int(1048576).bytes()[2] == byte(0x10) +pub fn (n &Number) bytes() []byte { + mut res := []byte{len: 128, init: 0} + unsafe { C.memcpy(res.data, n, 128) } + return res +} + +// bytes_trimmed returns an array of the bytes for the number `n`, +// in little endian format, where .bytes_trimmed()[0] is the least +// significant byte. The result is trimmed, so that *the last* byte +// of the result is also the the last meaningfull byte, != 0 . +// Example: assert big.from_int(1).bytes_trimmed() == [byte(0x01)] +// Example: assert big.from_int(1024).bytes_trimmed() == [byte(0x00), 0x04] +// Example: assert big.from_int(1048576).bytes_trimmed() == [byte(0x00), 0x00, 0x10] +pub fn (n &Number) bytes_trimmed() []byte { + mut res := []byte{len: 128, init: 0} + unsafe { C.memcpy(res.data, n, 128) } + mut non_zero_idx := 127 + for ; non_zero_idx >= 0; non_zero_idx-- { + if res[non_zero_idx] != 0 { + break + } + } + res.trim(non_zero_idx + 1) + return res +} diff --git a/v_windows/v/vlib/math/big/big.js.v b/v_windows/v/vlib/math/big/big.js.v new file mode 100644 index 0000000..0ed469c --- /dev/null +++ b/v_windows/v/vlib/math/big/big.js.v @@ -0,0 +1,198 @@ +module big + +struct JS.BigInt {} + +#const jsNumber = Number; + +pub struct Number { +} + +pub fn new() Number { + return Number{} +} + +pub fn from_int(i int) Number { + n := Number{} + #n.value = BigInt(+i) + + return n +} + +pub fn from_u64(u u64) Number { + n := Number{} + #n.value = BigInt(u.val) + + return n +} + +pub fn from_hex_string(input string) Number { + n := Number{} + #n.value = BigInt(input.val) + + return n +} + +pub fn from_string(input string) Number { + n := Number{} + #n.value = BigInt(input.val) + + return n +} + +pub fn (n &Number) int() int { + r := 0 + #r.val = jsNumber(n.val.value) + + return r +} + +pub fn (n &Number) str() string { + s := '' + #s.str = n.val.value + "" + + return s +} + +pub fn (a &Number) + (b &Number) Number { + c := Number{} + #c.value = a.val.value + b.val.value + + return c +} + +pub fn (a &Number) - (b &Number) Number { + c := Number{} + #c.value = a.val.value - b.val.value + + return c +} + +pub fn (a &Number) / (b &Number) Number { + c := Number{} + #c.value = a.val.value / b.val.value + + return c +} + +pub fn (a &Number) * (b &Number) Number { + c := Number{} + #c.value = a.val.value * b.val.value + + return c +} + +/* +pub fn (a &Number) % (b &Number) Number { + c := Number{} + # c.value = a.val.value % b.val.value + return c +}*/ + +pub fn divmod(a &Number, b &Number) (Number, Number) { + c := Number{} + d := Number{} + #c.value = a.val.value / b.val.value + #d.value = a.val.value % b.val.value + + return c, d +} + +pub fn cmp(a &Number, b &Number) int { + res := 0 + + #if (a.val.value < b.val.value) res.val = -1 + #else if (a.val.value > b.val.value) res.val = 1 + #else res.val = 0 + + return res +} + +pub fn (a &Number) is_zero() bool { + res := false + #res.val = a.val.value == BigInt(0) + + return res +} + +pub fn (mut a Number) inc() { + #a.val.value = a.val.value + BigInt(1) +} + +pub fn (mut a Number) dec() { + #a.val.value = a.val.value - BigInt(1) +} + +pub fn (a &Number) isqrt() Number { + b := Number{} + #let x0 = a.val.value >> 1n + #if (x0) { + #let x1 = (x0 + a.val.value / x0) >> 1n + #while (x1 < x0) { + #x0 = x1 + #x1 = (x0 + a.val.value / x0) >> 1n + #} + #b.value = x0 + #} else { b.value = a.val.value; } + + return b +} + +pub fn b_and(a &Number, b &Number) Number { + c := Number{} + #c.value = a.val.value & b.val.value + + return c +} + +pub fn b_or(a &Number, b &Number) Number { + c := Number{} + #c.value = a.val.value | b.val.value + + return c +} + +pub fn b_xor(a &Number, b &Number) Number { + c := Number{} + #c.value = a.val.value ^ b.val.value + + return c +} + +pub fn (a &Number) lshift(nbits int) Number { + c := Number{} + #c.value = a.val.value << BigInt(+nbits) + + return c +} + +pub fn (a &Number) rshift(nbits int) Number { + c := Number{} + #c.value = a.val.value << BigInt(+nbits) + + return c +} + +pub fn (a &Number) clone() Number { + b := Number{} + #b.value = a.val.value + + return b +} + +pub fn factorial(nn &Number) Number { + mut n := nn.clone() + mut a := nn.clone() + n.dec() + mut i := 1 + for !n.is_zero() { + res := a * n + n.dec() + a = res + i++ + } + return a +} + +pub fn fact(n int) Number { + return factorial(from_int(n)) +} diff --git a/v_windows/v/vlib/math/big/big_test.v b/v_windows/v/vlib/math/big/big_test.v new file mode 100644 index 0000000..9da5845 --- /dev/null +++ b/v_windows/v/vlib/math/big/big_test.v @@ -0,0 +1,181 @@ +import math.big + +fn test_new_big() { + n := big.new() + assert sizeof(big.Number) == 128 + assert n.hexstr() == '0' +} + +fn test_from_int() { + assert big.from_int(255).hexstr() == 'ff' + assert big.from_int(127).hexstr() == '7f' + assert big.from_int(1024).hexstr() == '400' + assert big.from_int(2147483647).hexstr() == '7fffffff' + assert big.from_int(-1).hexstr() == 'ffffffffffffffff' +} + +fn test_from_u64() { + assert big.from_u64(255).hexstr() == 'ff' + assert big.from_u64(127).hexstr() == '7f' + assert big.from_u64(1024).hexstr() == '400' + assert big.from_u64(4294967295).hexstr() == 'ffffffff' + assert big.from_u64(4398046511104).hexstr() == '40000000000' + assert big.from_u64(-1).hexstr() == 'ffffffffffffffff' +} + +fn test_plus() { + mut a := big.from_u64(2) + b := big.from_u64(3) + c := a + b + assert c.hexstr() == '5' + assert (big.from_u64(1024) + big.from_u64(1024)).hexstr() == '800' + a += b + assert a.hexstr() == '5' + a.inc() + assert a.hexstr() == '6' + a.dec() + a.dec() + assert a.hexstr() == '4' +} + +fn test_minus() { + a := big.from_u64(2) + mut b := big.from_u64(3) + c := b - a + assert c.hexstr() == '1' + e := big.from_u64(1024) + ee := e - e + assert ee.hexstr() == '0' + b -= a + assert b.hexstr() == '1' +} + +fn test_divide() { + a := big.from_u64(2) + mut b := big.from_u64(3) + c := b / a + assert c.hexstr() == '1' + assert (b % a).hexstr() == '1' + e := big.from_u64(1024) // dec(1024) == hex(0x400) + ee := e / e + assert ee.hexstr() == '1' + assert (e / a).hexstr() == '200' + assert (e / (a * a)).hexstr() == '100' + b /= a + assert b.hexstr() == '1' +} + +fn test_multiply() { + mut a := big.from_u64(2) + b := big.from_u64(3) + c := b * a + assert c.hexstr() == '6' + e := big.from_u64(1024) + e2 := e * e + e4 := e2 * e2 + e8 := e2 * e2 * e2 * e2 + e9 := e8 + big.from_u64(1) + d := ((e9 * e9) + b) * c + assert e4.hexstr() == '10000000000' + assert e8.hexstr() == '100000000000000000000' + assert e9.hexstr() == '100000000000000000001' + assert d.hexstr() == '60000000000000000000c00000000000000000018' + a *= b + assert a.hexstr() == '6' +} + +fn test_mod() { + assert (big.from_u64(13) % big.from_u64(10)).int() == 3 + assert (big.from_u64(13) % big.from_u64(9)).int() == 4 + assert (big.from_u64(7) % big.from_u64(5)).int() == 2 +} + +fn test_divmod() { + x, y := big.divmod(big.from_u64(13), big.from_u64(10)) + assert x.int() == 1 + assert y.int() == 3 + p, q := big.divmod(big.from_u64(13), big.from_u64(9)) + assert p.int() == 1 + assert q.int() == 4 + c, d := big.divmod(big.from_u64(7), big.from_u64(5)) + assert c.int() == 1 + assert d.int() == 2 +} + +fn test_from_str() { + assert big.from_string('9870123').str() == '9870123' + assert big.from_string('').str() == '0' + assert big.from_string('0').str() == '0' + assert big.from_string('1').str() == '1' + for i := 1; i < 307; i += 61 { + input := '9'.repeat(i) + out := big.from_string(input).str() + // eprintln('>> i: $i input: $input.str()') + // eprintln('>> i: $i out: $out.str()') + assert input == out + } +} + +fn test_from_hex_str() { + assert big.from_hex_string('0x123').hexstr() == '123' + for i in 1 .. 33 { + input := 'e'.repeat(i) + out := big.from_hex_string(input).hexstr() + assert input == out + } + assert big.from_string('0').hexstr() == '0' +} + +fn test_str() { + assert big.from_u64(255).str() == '255' + assert big.from_u64(127).str() == '127' + assert big.from_u64(1024).str() == '1024' + assert big.from_u64(4294967295).str() == '4294967295' + assert big.from_u64(4398046511104).str() == '4398046511104' + assert big.from_int(int(4294967295)).str() == '18446744073709551615' + assert big.from_int(-1).str() == '18446744073709551615' + assert big.from_hex_string('e'.repeat(80)).str() == '1993587900192849410235353592424915306962524220866209251950572167300738410728597846688097947807470' +} + +fn test_factorial() { + f5 := big.factorial(big.from_u64(5)) + assert f5.hexstr() == '78' + f100 := big.factorial(big.from_u64(100)) + assert f100.hexstr() == '1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000' +} + +fn trimbytes(n int, x []byte) []byte { + mut res := x.clone() + res.trim(n) + return res +} + +fn test_bytes() { + assert big.from_int(0).bytes().len == 128 + assert big.from_hex_string('e'.repeat(100)).bytes().len == 128 + assert trimbytes(3, big.from_int(1).bytes()) == [byte(0x01), 0x00, 0x00] + assert trimbytes(3, big.from_int(1024).bytes()) == [byte(0x00), 0x04, 0x00] + assert trimbytes(3, big.from_int(1048576).bytes()) == [byte(0x00), 0x00, 0x10] +} + +fn test_bytes_trimmed() { + assert big.from_int(0).bytes_trimmed().len == 0 + assert big.from_hex_string('AB'.repeat(50)).bytes_trimmed().len == 50 + assert big.from_int(1).bytes_trimmed() == [byte(0x01)] + assert big.from_int(1024).bytes_trimmed() == [byte(0x00), 0x04] + assert big.from_int(1048576).bytes_trimmed() == [byte(0x00), 0x00, 0x10] +} + +fn test_from_bytes() ? { + assert big.from_bytes([]) ?.hexstr() == '0' + assert big.from_bytes([byte(0x13)]) ?.hexstr() == '13' + assert big.from_bytes([byte(0x13), 0x37]) ?.hexstr() == '1337' + assert big.from_bytes([byte(0x13), 0x37, 0xca]) ?.hexstr() == '1337ca' + assert big.from_bytes([byte(0x13), 0x37, 0xca, 0xfe]) ?.hexstr() == '1337cafe' + assert big.from_bytes([byte(0x13), 0x37, 0xca, 0xfe, 0xba]) ?.hexstr() == '1337cafeba' + assert big.from_bytes([byte(0x13), 0x37, 0xca, 0xfe, 0xba, 0xbe]) ?.hexstr() == '1337cafebabe' + assert big.from_bytes([]byte{len: 128, init: 0x0}) ?.hexstr() == '0' + if x := big.from_bytes([]byte{len: 129, init: 0x0}) { + return error('expected error, got $x') + } +} |