/*
 * Copyright (C)2005-2023 Haxe Foundation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

package haxe.math.bigint;

import haxe.math.bigint.BigIntException;
import haxe.math.bigint.BigIntError;
import haxe.math.bigint.BigIntHelper;
import haxe.ds.Vector;
import haxe.io.Bytes;

/* Original code courtesy Chuck Batson (github.com/cbatson) */
@:noCompletion
@:noDoc
@:allow(unit)
@:allow(haxe.math.bigint)
class MutableBigInt_ extends BigInt_ {

	private var m_owned:Bool = false;

	private static var s_testAllocation:Bool = false;
	private static var s_debugAllocationPadding:Int = 0;
	
	//-----------------------------------------------------------------------
	// Public interface
	//-----------------------------------------------------------------------

	/**
		Set the value of this big int with an integer of value `value`.
		@param value The new integer value for this instance.
	**/
	public function setFromInt(value:Int):Void {
		ensureCapacity(1, false);
		m_data.set(0, value);
		m_count = 1;
	}

	/**
		Set the value of this big integer with the signed value
		represented by the hexadecimal string `value`.
		@param value A string containing a hexadecimal number.
	**/
	public inline function setFromHexSigned(value:String):Void {
		_setFromHex(value, true);
	}

	/**
		Set the value of this big integer with the unsigned value
		represented by the hexadecimal string `value`.
		@param value A string containing a hexadecimal number.
	**/
	public inline function setFromHexUnsigned(value:String):Void {
		_setFromHex(value, false);
	}

	/**
		Set the value of this big integer by parsing the given string.
		@param value The string representation of the number.
		@param radix The base of the number in the string (e.g., 10, 16).
	**/
	public function setFromString(value:String, radix:Int = 10):Void {
		if ((value == null) || (value.length < 1)) {
			throw new BigIntException(BigIntError.INVALID_ARGUMENT);
		}

		var negate = value.charCodeAt(0) == 0x2d; // '-' character
		var index = negate ? 1 : 0;

		if (value.length <= index) {
			throw new BigIntException(BigIntError.INVALID_ARGUMENT);
		}

		if (value.charCodeAt(index) == 0x30) { // '0'
			if (value.charCodeAt(index + 1) == 0x62) { // 'b' - binary
				radix = 2;
				index += 2;
			} else if (value.charCodeAt(index + 1) == 0x6F) { // 'o' - octal
				radix = 8;
				index += 2;
			} else if (value.charCodeAt(index + 1) == 0x78) { // 'x' - hex
				_setFromHex(value.substr(index + 2), false);
				if (negate) {
					BigIntArithmetic.negate(this, this);
				}
				return;
			}
		}

		if (radix == 16) {
			_setFromHex(value.substr(index), false);
			if (negate) {
				BigIntArithmetic.negate(this, this);
			}
			return;
		}

		this.setFromInt(0);
		var t = new MutableBigInt_();
		var endDigit:Int = 57;
		var extraEndDigit:Int = 0;

		if (radix <= 10) {
			endDigit = 48 + radix - 1;
		} else {
			extraEndDigit = radix - 11;
		}

		for (i in index...value.length) {
			var c = value.charCodeAt(i);
			if (((48 <= c) && (c <= endDigit))
				|| (radix > 10 && ((65 <= c && c <= (65 + extraEndDigit)) || (97 <= c && c <= (97 + extraEndDigit))))) {
				BigIntArithmetic.multiplyInt(t, this, radix);
				if (c <= endDigit) {
					BigIntArithmetic.addInt(this, t, c - 48);
				} else if (c <= (65 + extraEndDigit)) {
					BigIntArithmetic.addInt(this, t, c - 55);
				} else {
					BigIntArithmetic.addInt(this, t, c - 87);
				}
			} else {
				throw new BigIntException(BigIntError.INVALID_ARGUMENT);
			}
		}

		if (negate) {
			BigIntArithmetic.negate(this, this);
		}
	}

	/**
		Set the value of this big integer from a vector of unsigned `Int`s.
		@param value The `Vector` containing the integer words.
		@param length The number of words to use from the vector.
	**/
	public function setFromUnsignedInts(value:Vector<Int>, length:Int = 0):Void {
		if (length <= 0) {
			length = value.length;
		}
		var neg = value.get(length - 1) >>> 31;
		ensureCapacity(length + neg, false);
		m_data.set(length + neg - 1, 0);
		MultiwordArithmetic.copy(m_data, value, length);
		m_count = length + neg;
		compact();
	}
	
	/**
		Set the value from a portion of another `Vector` of `Int`s.
		@param source The source vector.
		@param sourcePosition The starting position in the source vector.
		@param length The number of words to copy.
	**/
	public function setFromVector(source : Vector<Int32>, sourcePosition:Int, length : Int ) : Void
	{
		ensureCapacity(length , false);
		Vector.blit(source, sourcePosition, m_data, 0, length);
		m_count = length;
	}

	/**
		Set the value from a `Bytes` sequence, interpreted as signed big-endian.
		@param value The source `Bytes`.
		@param offset The starting offset in the bytes.
		@param valueLength The number of bytes to read.
	**/
	public function setFromBigEndianBytesSigned(value:Bytes, offset:Int = 0, valueLength:Int = 0):Void {
		if (value == null) {
			throw new BigIntException(BigIntError.INVALID_ARGUMENT);
		}
		if (valueLength <= 0) {
			valueLength = value.length;
		}
		if (offset + valueLength > value.length) {
			throw new BigIntException(BigIntError.BUFFER_TOO_SMALL);
		}
		if (valueLength < 1) {
			setFromInt(0);
			return;
		}
		var length = (valueLength + 3) >> 2;
		ensureCapacity(length, false);
		m_data.set(length - 1, 0);
		var pos = 0;
		var i = offset + valueLength;
		while (i >= offset + 4) {
			m_data.set(pos++, (value.get(i - 1) << 0) | (value.get(i - 2) << 8) | (value.get(i - 3) << 16) | (value.get(i - 4) << 24));
			i -= 4;
		}
		if (i > offset) {
			var x:Int = 0;
			for (j in offset...i) {
				x = (x << 8) | value.get(j);
			}
			m_data.set(pos++, x);
		}
		m_count = length;
		compact();
	}

	/**
		Set the value from a `Bytes` sequence, interpreted as unsigned big-endian.
		@param value The source `Bytes`.
		@param offset The starting offset in the bytes.
		@param valueLength The number of bytes to read.
	**/
	public function setFromBigEndianBytesUnsigned(value:Bytes, offset:Int = 0, valueLength:Int = 0):Void {
		if (valueLength <= 0) {
			valueLength = value.length;
		}
		if (offset + valueLength > value.length) {
			throw new BigIntException(BigIntError.BUFFER_TOO_SMALL);
		}
		if (valueLength < 1) {
			setFromInt(0);
			return;
		}
		var neg = ((valueLength & 3) == 0) ? (value.get(0) >> 7) : 0;
		var length = (valueLength + 3) >> 2;
		ensureCapacity(length + neg, false);
		m_data.set(length + neg - 1, 0);
		var pos = 0;
		var i = offset + valueLength;
		while (i >= offset + 4) {
			m_data.set(pos++, (value.get(i - 1) << 0) | (value.get(i - 2) << 8) | (value.get(i - 3) << 16) | (value.get(i - 4) << 24));
			i -= 4;
		}
		if (i > offset) {
			var x:Int = 0;
			for (j in offset...i) {
				x = (x << 8) | value.get(j);
			}
			m_data.set(pos++, x);
		}
		m_count = length + neg;
		compact();
	}

	/**
		Set the value from a `Bytes` sequence, interpreted as unsigned little-endian.
		@param value The source `Bytes`.
		@param offset The starting offset in the bytes.
		@param valueLength The number of bytes to read.
	**/
	public function setFromLittleEndianBytesUnsigned(value:Bytes, offset:Int = 0, valueLength:Int = 0):Void {
		if (valueLength <= 0) {
			valueLength = value.length;
		}
		if (offset + valueLength > value.length) {
			throw new BigIntException(BigIntError.BUFFER_TOO_SMALL);
		}
		if (valueLength < 1) {
			setFromInt(0);
			return;
		}
		var neg = ((valueLength & 3) == 0) ? (value.get(valueLength - 1) >> 7) : 0;
		var length = (valueLength + 3) >> 2;
		ensureCapacity(length + neg, false);
		m_data.set(length + neg - 1, 0);
		var pos = 0;
		var i = offset;
		while (i <= offset + valueLength - 4) {
			m_data.set(pos++, (value.get(i + 0) << 0) | (value.get(i + 1) << 8) | (value.get(i + 2) << 16) | (value.get(i + 3) << 24));
			i += 4;
		}
		if (i < offset + valueLength) {
			var x:Int = 0;
			for (j in i...offset + valueLength) {
				x |= value.get(j) << ((j - i) << 3);
			}
			m_data.set(pos++, x);
		}
		m_count = length + neg;
		compact();
	}

	/**
		Resets the value of this `MutableBigInt` to zero.
	**/
	public function clear():Void {
		MultiwordArithmetic.setZero(m_data, m_data.length);
		m_count = 1;
	}

	/**
		Copy the value from big integer `other` into this big
		integer.
	**/
	private function copyFrom(other:BigInt_):Void {
		if (other != this) {
			ensureCapacity(other.m_count, false);
			for (i in 0...other.m_count) {
				m_data.set(i, other.m_data.get(i));
			}
			m_count = other.m_count;
		}
	}

	private function fixedSizeCopyFrom(other:BigInt_, size:Int, value:Int = 0):Void {
		if (other != this) {
			ensureCapacity(size, false);
			var maxSize:Int = (size > other.m_count) ? other.m_count : size;
			for (i in 0...maxSize) {
				m_data.set(i, other.m_data.get(i));
			}
			var diffSize = size - maxSize;
			while (diffSize > 0) {
				m_data.set(maxSize++, value);
				diffSize--;
			}
			m_count = size;
		}
	}

	//-----------------------------------------------------------------------
	// Private implementation
	//-----------------------------------------------------------------------

	private inline function setShort(n:Int32, v:Int32):Void {
		var s:Int = (n & 1) << 4;
		var t:Int = m_data.get(n >> 1) & (~0xffff >>> s);
		m_data.set(n >> 1, t | ((v & 0xffff) << s));
	}

	private function copy(other:MutableBigInt_):Void {
		this.m_data = other.m_data;
		this.m_count = other.m_count;
		this.m_owned = other.m_owned;
	}

	private inline function ensureCapacity(n:Int, preserve:Bool):Void {
		#if debug
		if (s_testAllocation) {
			ensureCapacityDebug(n, preserve);
			return;
		}
		#end
		ensureCapacityProd(n, preserve);
	}

	@:noCompletion
	private function ensureCapacityDebug(n:Int, preserve:Bool):Void {
		// always allocate the minimum amount necessary, to catch
		// bounds edge cases as well as use of stale buffer data
		if (preserve && (m_data != null) && (m_count > 0)) {
			n = (m_count > n) ? m_count : n;
			n += s_debugAllocationPadding;
			var newData = new Vector<Int>(n);
			for (i in 0...m_count) {
				newData.set(i, m_data.get(i));
			}
			for (i in m_count...n) {
				newData.set(i, 0xdeadbeef);
			}
			m_data = newData;
		} else {
			n += s_debugAllocationPadding;
			m_data = new Vector<Int>(n);
			for (i in 0...n) {
				m_data.set(i, 0xdeadbeef);
			}
		}
	}

	@:noCompletion
	private function ensureCapacityProd(n:Int, preserve:Bool):Void {
		if (n < 1) {
			throw new BigIntException(BigIntError.INVALID_ARGUMENT);
		}
		if ((!m_owned) || (m_data == null) || (n > m_data.length)) {
			n = BigIntHelper.clp2(n);
			if (preserve && (m_data != null)) {
				var newData = new Vector<Int>(n);
				for (i in 0...m_count) {
					newData.set(i, m_data.get(i));
				}
				m_data = newData;
			} else {
				m_data = new Vector<Int>(n);
				for(i in 0...n) {
					m_data.set(i,0);
				}
			}
		}
		m_owned = true;
	}

	private function new() {
		super();
	}

	private static function fromInt(other:Int):MutableBigInt_ {
		var c = BigInt_.getCachedValue(other);
		if (c != null) {
			return fromBigInt(c);
		}
		var r = new MutableBigInt_();
		r.ensureCapacity(1, false);
		r.m_data.set(0, other);
		r.m_count = 1;
		return r;
	}

	private static function fromBigInt(other:BigInt_):MutableBigInt_ {
		// TODO: this will be problematic if `other` is actually a MutableBigInt_
		var r = new MutableBigInt_(); // unowned
		r.m_data = other.m_data;
		r.m_count = other.m_count;
		return r;
	}

	//-----------------------------------------------------------------------
	// Static helpers
	//-----------------------------------------------------------------------

	private function _setFromHex(value:String, signed:Bool):Void {
		if (value == null) {
			throw new BigIntException(BigIntError.INVALID_ARGUMENT);
		}

		var index = value.length;
		if (index <= 0) {
			throw new BigIntException(BigIntError.INVALID_ARGUMENT);
		}

		var hexDigitCount = 0;
		for (i in 0...index) {
			var c = value.charCodeAt(i);
			if (c != 32) { // check for a space
				hexDigitCount++;
			}
		}

		var wordsNeeded = (hexDigitCount + 7) >> 3;

		// For unsigned, we need an extra word if the top bit is set
		var extra:Int = signed ? 0 : 1;
		ensureCapacity(wordsNeeded + extra, false);

		for (i in 0...wordsNeeded + extra) {
			m_data.set(i, 0);
		}

		var wordIndex = 0;
		var currentWord:Int32 = 0;
		var bitsInCurrentWord = 0;

		var charIndex = index - 1;
		while (charIndex >= 0) {
			var c:Int = value.charCodeAt(charIndex);
			var digit:Int;

			if ((48 <= c) && (c <= 57)) { // '0'-'9'
				digit = c - 48;
			} else if ((65 <= c) && (c <= 70)) { // 'A'-'F'
				digit = c - 55;
			} else if ((97 <= c) && (c <= 102)) { // 'a'-'f'
				digit = c - 87;
			} else if (c == 32) { // space - skip
				charIndex--;
				continue;
			} else {
				throw new BigIntException(BigIntError.INVALID_ARGUMENT);
			}

			currentWord |= (digit << bitsInCurrentWord);
			bitsInCurrentWord += 4;

			if (bitsInCurrentWord >= 32) {
				m_data.set(wordIndex++, currentWord);
				currentWord = 0;
				bitsInCurrentWord = 0;
			}

			charIndex--;
		}

		if (bitsInCurrentWord > 0) {
			if (signed) {
				var topBit = bitsInCurrentWord - 1;
				if ((currentWord & (1 << topBit)) != 0) {
					// Negative number - extend sign bits
					var mask:Int32 = ~((1 << bitsInCurrentWord) - 1);
					currentWord |= mask;
				}
			}
			m_data.set(wordIndex++, currentWord);
		}

		m_count = wordIndex;

		// For unsigned,do not interpret as negative
		if (!signed && m_count > 0) {
			var topWord = m_data.get(m_count - 1);
			if (topWord < 0) {
				m_data.set(m_count++, 0);
			}
		}

		compact();
	}

	@:noCompletion
	private static inline function multiplyAssignInt2(a7:MutableBigInt_, b:Int):Void {
		var r = new MutableBigInt_();
		BigIntArithmetic.multiplyInt(r, a7, b);
		a7.copy(r);
	}

	@:noCompletion
	private static inline function multiplyAssign2(a8:MutableBigInt_, b:BigInt_):Void {
		var r = new MutableBigInt_();
		BigIntArithmetic.multiply(r, a8, b);
		a8.copy(r);
	}

	@:noCompletion
	private static inline function divideAssignInt2(a9:MutableBigInt_, b:Int):Void {
		var q = new MutableBigInt_();
		BigIntArithmetic.divideInt(a9, b, q);
		a9.copy(q);
	}

	@:noCompletion
	private static inline function divideAssign2(a10:MutableBigInt_, b:BigInt_):Void {
		var q = new MutableBigInt_();
		BigIntArithmetic.divide(a10, b, q, null);
		a10.copy(q);
	}

	@:noCompletion
	private static inline function modulusAssignInt2(a11:MutableBigInt_, b:Int):Void {
		var q = new MutableBigInt_();
		var r = BigIntArithmetic.divideInt(a11, b, q);
		a11.setFromInt(r);
	}

	@:noCompletion
	private static inline function modulusAssign2(a12:MutableBigInt_, b:BigInt_):Void {
		var q = new MutableBigInt_();
		var r = new MutableBigInt_();
		BigIntArithmetic.divide(a12, b, q, r);
		a12.copy(r);
	}

	@:noCompletion
	private static inline function arithmeticShiftLeftAssign2(a13:MutableBigInt_, b:Int):Void {
		BigIntArithmetic.arithmeticShiftLeft(a13, a13, b);
	}

	@:noCompletion
	private static inline function arithmeticShiftRightAssign2(a14:MutableBigInt_, b:Int):Void {
		BigIntArithmetic.arithmeticShiftRight(a14, a14, b);
	}
}
