big: Add `shl`, `shr` and `shrmod`.

4 files changed, 218 insertions, 27 deletions

diff --git a/core/math/big/basic.odin b/core/math/big/basic.odin
index 42db8b88e..cbabd073b 100644
--- a/core/math/big/basic.odin
+++ b/core/math/big/basic.odin
@@ -463,48 +463,47 @@ int_double :: proc(dest, src: ^Int) -> (err: Error) {
 double :: proc { int_double, };

 shl1   :: double;

 

-

 /*

-	dest = src % (2^power);

+	remainder = numerator % (1 << bits)

 */

-int_mod_power_of_two :: proc(dest, src: ^Int, power: int) -> (err: Error) {

-	dest := dest; src := src;

-	if err = clear_if_uninitialized(dest); err != .None {

+int_mod_bits :: proc(remainder, numerator: ^Int, bits: int) -> (err: Error) {

+	remainder := remainder; numerator := numerator;

+	if err = clear_if_uninitialized(remainder); err != .None {

 		return err;

 	}

-	if err = clear_if_uninitialized(src); err != .None {

+	if err = clear_if_uninitialized(numerator); err != .None {

 		return err;

 	}

 

-	if power  < 0 { return .Invalid_Argument; }

-	if power == 0 { return zero(dest); }

+	if bits  < 0 { return .Invalid_Argument; }

+	if bits == 0 { return zero(remainder); }

 

 	/*

 		If the modulus is larger than the value, return the value.

 	*/

-	err = copy(dest, src);

-	if power >= (src.used * _DIGIT_BITS) || err != .None {

+	err = copy(remainder, numerator);

+	if bits >= (numerator.used * _DIGIT_BITS) || err != .None {

 		return;

 	}

 

 	/*

 		Zero digits above the last digit of the modulus.

 	*/

-	zero_count := (power / _DIGIT_BITS) + 0 if (power % _DIGIT_BITS == 0) else 1;

+	zero_count := (bits / _DIGIT_BITS) + 0 if (bits % _DIGIT_BITS == 0) else 1;

 	/*

 		Zero remainder.

 	*/

 	if zero_count > 0 {

-		mem.zero_slice(dest.digit[zero_count:]);

+		mem.zero_slice(remainder.digit[zero_count:]);

 	}

 

 	/*

 		Clear the digit that is not completely outside/inside the modulus.

 	*/

-	dest.digit[power / _DIGIT_BITS] &= DIGIT(1 << DIGIT(power % _DIGIT_BITS)) - DIGIT(1);

-	return clamp(dest);

+	remainder.digit[bits / _DIGIT_BITS] &= DIGIT(1 << DIGIT(bits % _DIGIT_BITS)) - DIGIT(1);

+	return clamp(remainder);

 }

-mod_power_of_two :: proc { int_mod_power_of_two, };

+mod_bits :: proc { int_mod_bits, };

 

 /*

 	==========================

diff --git a/core/math/big/common.odin b/core/math/big/common.odin
index c8e219927..fcfdb3973 100644
--- a/core/math/big/common.odin
+++ b/core/math/big/common.odin
@@ -94,11 +94,11 @@ when size_of(rawptr) == 8 {
 	/*
 		We can use u128 as an intermediary.
 	*/
-	DIGIT        :: distinct(u64);
-	_WORD        :: distinct(u128);
+	DIGIT        :: distinct u64;
+	_WORD        :: distinct u128;
 } else {
-	DIGIT        :: distinct(u32);
-	_WORD        :: distinct(u64);
+	DIGIT        :: distinct u32;
+	_WORD        :: distinct u64;
 }
 #assert(size_of(_WORD) == 2 * size_of(DIGIT));
 
diff --git a/core/math/big/example.odin b/core/math/big/example.odin
index 1b8503233..b004d115d 100644
--- a/core/math/big/example.odin
+++ b/core/math/big/example.odin
@@ -57,16 +57,11 @@ demo :: proc() {
 	a, b, c := &Int{}, &Int{}, &Int{};
 	defer destroy(a, b, c);
 
-	err = set(a, -512);
+	err = set(a, 1);
 	err = set(b, 1);
 	err = set(c, -4);
 
-
-	err = mod_power_of_two(a, a, 10);
-	fmt.printf("%v (%v)\n", int_get_float(a));
-
-
-	print("a", a, 10);
+	print("a", a, 16);
 	print("b", b, 10);
 	print("c", c, 10);
 
diff --git a/core/math/big/logical.odin b/core/math/big/logical.odin
index 8bc468203..53e296dc1 100644
--- a/core/math/big/logical.odin
+++ b/core/math/big/logical.odin
@@ -11,6 +11,8 @@ package big
 	This file contains logical operations like `and`, `or` and `xor`.
 */
 
+import "core:mem"
+
 /*
 	The `and`, `or` and `xor` binops differ in two lines only.
 	We could handle those with a switch, but that adds overhead.
@@ -244,4 +246,199 @@ int_complement :: proc(dest, src: ^Int) -> (err: Error) {
 
 	return err;
 }
-complement :: proc { int_complement, };
\ No newline at end of file
+complement :: proc { int_complement, };
+
+/*
+	quotient, remainder := numerator >> bits;
+	`remainder` is allowed to be passed a `nil`, in which case `mod` won't be computed.
+*/
+int_shrmod :: proc(quotient, remainder, numerator: ^Int, bits: int) -> (err: Error) {
+	bits := bits;
+	if err = clear_if_uninitialized(quotient);  err != .None { return err; }
+	if err = clear_if_uninitialized(numerator); err != .None { return err; }
+
+	if bits < 0 { return .Invalid_Argument; }
+
+	if err = copy(quotient, numerator); err != .None { return err; }
+
+	/*
+		Shift right by a certain bit count (store quotient and optional remainder.)
+	   `numerator` should not be used after this.
+	*/
+	if remainder != nil {
+		if err = mod_bits(remainder, numerator, bits); err != .None { return err; }
+	}
+
+	/*
+		Shift by as many digits in the bit count.
+	*/
+	if bits >= _DIGIT_BITS {
+		if err = shr_digit(quotient, bits / _DIGIT_BITS); err != .None { return err; }
+	}
+
+	/*
+		Shift any bit count < _DIGIT_BITS.
+	*/
+	bits %= _DIGIT_BITS;
+	if bits != 0 {
+		mask  := DIGIT(1 << uint(bits)) - 1;
+		shift := DIGIT(_DIGIT_BITS - bits);
+		carry := DIGIT(0);
+
+		for x := quotient.used; x >= 0; x -= 1 {
+			/*
+				Get the lower bits of this word in a temp.
+			*/
+			fwd_carry := quotient.digit[x] & mask;
+
+			/*
+				Shift the current word and mix in the carry bits from the previous word.
+			*/
+	        quotient.digit[x] = (quotient.digit[x] >> uint(bits)) | (carry << shift);
+
+	        /*
+	        	Update carry from forward carry.
+	        */
+	        carry = fwd_carry;
+		}
+
+	}
+	return clamp(numerator);
+}
+shrmod :: proc { int_shrmod, };
+
+int_shr :: proc(dest, source: ^Int, bits: int) -> (err: Error) {
+	return shrmod(dest, nil, source, bits);
+}
+shr :: proc { int_shr, };
+
+/*
+	Shift right by `digits` * _DIGIT_BITS bits.
+*/
+int_shr_digit :: proc(quotient: ^Int, digits: int) -> (err: Error) {
+	/*
+		Check that `quotient` is usable.
+	*/
+	if err = clear_if_uninitialized(quotient); err != .None { return err; }
+
+	if digits <= 0 { return .None; }
+
+	/*
+		If digits > used simply zero and return.
+	*/
+	if digits > quotient.used {
+		return zero(quotient);
+	}
+
+   	/*
+		Much like `int_shl_digit`, this is implemented using a sliding window,
+		except the window goes the other way around.
+
+		b-2 | b-1 | b0 | b1 | b2 | ... | bb |   ---->
+		            /\                   |      ---->
+		             \-------------------/      ---->
+    */
+
+	for x := 0; x < (quotient.used - digits); x += 1 {
+    	quotient.digit[x] = quotient.digit[x + digits];
+	}
+	quotient.used -= digits;
+	_zero_unused(quotient);
+	return .None;
+}
+shr_digit :: proc { int_shr_digit, };
+
+/*
+	Shift left by a certain bit count.
+*/
+int_shl :: proc(dest, src: ^Int, bits: int) -> (err: Error) {
+	bits := bits;
+	if err = clear_if_uninitialized(src);  err != .None { return err; }
+	if err = clear_if_uninitialized(dest); err != .None { return err; }
+
+	if bits < 0 {
+		return .Invalid_Argument;
+	}
+
+	if err = copy(dest, src); err != .None { return err; }
+
+	/*
+		Grow `dest` to accommodate the additional bits.
+	*/
+	digits_needed := dest.used + (bits / _DIGIT_BITS) + 1;
+	if err = grow(dest, digits_needed); err != .None { return err; }
+	dest.used = digits_needed;
+	/*
+		Shift by as many digits in the bit count as we have.
+	*/
+	if bits >= _DIGIT_BITS {
+		if err = shl_digit(dest, bits / _DIGIT_BITS); err != .None { return err; }
+	}
+
+	/*
+		Shift any remaining bit count < _DIGIT_BITS
+	*/
+	bits %= _DIGIT_BITS;
+	if bits != 0 {
+		mask  := (DIGIT(1) << uint(bits)) - DIGIT(1);
+		shift := DIGIT(_DIGIT_BITS - bits);
+		carry := DIGIT(0);
+
+		for x:= 0; x <= dest.used; x+= 1 {		
+			fwd_carry := (dest.digit[x] >> shift) & mask;
+			dest.digit[x] = (dest.digit[x] << uint(bits) | carry) & _MASK;
+			carry = fwd_carry;
+		}
+
+		/*
+			Use final carry.
+		*/
+		if carry != 0 {
+			dest.digit[dest.used] = carry;
+			dest.used += 1;
+		}
+	}
+	return clamp(dest);
+}
+shl :: proc { int_shl, };
+
+
+/*
+	Shift left by `digits` * _DIGIT_BITS bits.
+*/
+int_shl_digit :: proc(quotient: ^Int, digits: int) -> (err: Error) {
+	/*
+		Check that `quotient` is usable.
+	*/
+	if err = clear_if_uninitialized(quotient); err != .None { return err; }
+
+	if digits <= 0 { return .None; }
+
+	/*
+		No need to shift a zero.
+	*/
+	z: bool;
+	if z, err = is_zero(quotient); z || err != .None { return err; }
+
+	/*
+		Resize `quotient` to accomodate extra digits.
+	*/
+	if err = grow(quotient, quotient.used + digits); err != .None { return err; }
+
+	/*
+		Increment the used by the shift amount then copy upwards.
+	*/
+   	quotient.used += digits;
+
+	/*
+		Much like `int_shr_digit`, this is implemented using a sliding window,
+		except the window goes the other way around.
+    */
+    for x := quotient.used; x >= digits; x -= 1 {
+    	quotient.digit[x] = quotient.digit[x - digits];
+    }
+
+    mem.zero_slice(quotient.digit[:digits]);
+    return .None;
+}
+shl_digit :: proc { int_shl_digit, };
\ No newline at end of file