using System;
using sharp.extensions;
namespace BigInt
{
	public static class BigIntMath
	{
		/* Public Interface */

		public static bool sign(UInt32[] value){
			return (value[value.Length - 1] & (1 << 31)) != 0;
		}

		public static int log2(UInt32[] value)
		{
			switch (sign(value)){
				case false:
					for (int n = value.Length << 5; n > 0; n--)
					{
						if ((value[(n - 1) >> 5] & (1 << ((n - 1) & 0x1F))) != 0)
						{
							return n - 1;
						}
					}
					return 0;
				case true:
					for (int n = (value.Length << 5)-1; n > 0; n--)
					{
						if ((value[(n - 1) >> 5] & (1 << ((n - 1) & 0x1F))) == 0)
						{
							return 1 - n;
						}
					}
					return 0;
			}
			return 0;
		}

		public static bool isZero(UInt32[] value){
			foreach (UInt32 v in value){
				if (v != 0){
					return false;
				}
			}
			return true;
		}

		public static UInt32[] ones(UInt32[] value){
			UInt32[] result = value.Segment(0);
			for (int n = 0; n < result.Length;n++){
				result[n] ^= 0xffffffff;
			}
			return result;
		}

		public static UInt32[] twos(UInt32[] value){
			UInt32[] result = ones(value);
			UInt32[] one = new UInt32[]{1};
			result = add(result, one);
			return result;
		}

		/**
		 * Extend signed integer to higher width
		 **/
		public static UInt32[] extendSigned(UInt32[] value,int width){
			UInt32[] result = value.Segment(0).Extend(width);
			if (sign(value))
			{
				for (int n = value.Length; n < width; n++)
				{
					result[n] = 0xFFFFFFFF;
				}
			}
			return result;
		}

		public static void extendEqualSigned(ref UInt32[] a, ref UInt32[] b){
			int width = a.Length > b.Length ? a.Length : b.Length;

			a = extendSigned(a, width);
			b = extendSigned(b, width);
		}

		public static UInt32[] signedFromUnsigned(UInt32[] value){
			if (sign(value)){
				return value.Extend(value.Length+1);
			}
			return value;
		}

		/**
		 * Reduce signed integer to smallest width, needed to represent its value
		 **/
		public static UInt32[] reduceSigned(UInt32[] value){
			int n = value.Length;

			//Console.WriteLine("reduceSigned(): < {0}", value.getBytes().Reverse().toHexString());

			for (; n > 1; n--){
				if (
					((value[n-1] != 0) || ((value[n-2] & (1<<31))!=0)) && ((value[n-1] != 0xFFFFFFFF) || ((value[n-2] & (1<<31))==0))
				){
					break;
				}
			}
			value = value.Segment(0, n);

			//Console.WriteLine("reduceSigned(): > {0}", value.getBytes().Reverse().toHexString());

			return value;
		}

		/**
		* Reduce unsigned integer to smallest width, needed to represent its value 
		**/
		public static UInt32[] reduceUnsigned(UInt32[] value)
		{
			int n = value.Length;
			for (; n > 1; n--){
				if (value[n-1] != 0){
					break;
				}
			}
			return value.Segment(0,n);
		}

		public static UInt32[] add(UInt32[] a, UInt32[] b)
		{
			UInt32 c = 0;

			a = a.Segment(0);
			extendEqualSigned(ref a, ref b);

			for (int n = 0; n < a.Length; n++)
			{
				a[n] = add(a[n], b[n], ref c);
			}
			return a;
		}

		public static UInt32[] sub(UInt32[] a, UInt32[] b)
		{
			UInt32 c = 0;
			a = a.Segment(0);

			extendEqualSigned(ref a, ref b);

			for (int n = 0; n < a.Length; n++)
			{
				a[n] = sub(a[n], b[n], ref c);
			}
			return a;
		}

		public static UInt32[] umul(UInt32[] a, UInt32[] b)
		{
			UInt32[] result = new UInt32[a.Length + b.Length];

			for (int l1 = 0; l1 < a.Length; l1++)
			{
				for (int l2 = 0; l2 < (b.Length); l2++)
				{
					int target = l1 + l2;
					UInt64 ui64 = ((UInt64)a[l1] * b[l2]);
					for (int ct = target; (ct < result.Length) && (ui64 != 0); ct++){
						ui64 += result[ct];
						result[ct] = (UInt32)ui64;
						ui64 >>= 32;
					}
				}
			}

			return result;
		}

		public static UInt32[] smul(UInt32[] a, UInt32[] b)
		{
			a = extendSigned(a, a.Length << 1);
			b = extendSigned(b, b.Length << 1);

			UInt32[] result = new UInt32[(a.Length + b.Length)>>1];

			for (int l1 = 0; l1 < a.Length; l1++)
			{
				for (int l2 = 0; l2 < (b.Length); l2++)
				{
					int target = l1 + l2;
					UInt64 ui64 = ((UInt64)a[l1] * b[l2]);
					for (int ct = target; (ct < result.Length) && (ui64 != 0); ct++)
					{
						ui64 += result[ct];
						result[ct] = (UInt32)ui64;
						ui64 >>= 32;
					}
				}
			}
			return result;
		}

		/**
		 * @brief Calulate a / b. (unsigned values)
		 * @returns Result of division.
		 **/
		public static UInt32[] udiv(UInt32[] a,UInt32[] b){
			return udivmod(ref a, b);
		}
		public static UInt32[] umod(UInt32[] a,UInt32[] b){
			UInt32[] m = a.Segment(0);
			udivmod(ref m,b);
			return m;
		}

		public static UInt32[] udivmod(ref UInt32[] _a, UInt32[] b)
		{
			UInt32[] a = _a;

			if (cmp(a, b) < 0)
			{
				return new UInt32[a.Length];
			}

			UInt32[] result = new UInt32[a.Length];
			UInt32[] d = b.Segment(0).Extend(a.Length);

			int lg2a, lg2b, shift;

			lg2a = log2(a);
			lg2b = log2(d);
			shift = lg2a - lg2b;

			if (shift > 0)
			{
				shl(d, shift);
			}

			for (int n = 0; n <= (shift); n++)
			{
				shl(result, 1);

				if (cmp(d, a) <= 0)
				{
					result[0] |= 1;
					a = sub(a, d);
				}

				shr(d, 1);
			}
			_a = a;
			return result;
		}

		/**
		 * @brief Calulate a / b. (unsigned values)
		 * @returns Result of division. a[] will contain reminder.
		 **/
		public static UInt32[] sdiv(UInt32[] a, UInt32[] b)
		{
			return sdivmod(ref a, b);
		}
		public static UInt32[] smod(UInt32[] a, UInt32[] b)
		{
			UInt32[] m = a.Segment(0);
			sdivmod(ref m, b);
			return m;
		}

		/**
		 * sdivmod ( a , b )
		 * 
		 * Calculate Quotient and Reminder of a / b using signed integer arithmetics
		 * returns quotient
		 * leaves reminder in <param name="a">
		 * 
		 **/
		public static UInt32[] sdivmod(ref UInt32[] a, UInt32[] b)
		{
			bool sgna, sgnb;

			sgna = sign(a);
			sgnb = sign(b);

			//Console.WriteLine("sdivmod():        a = {0}",a.getBytes().Reverse().toHexString());
			//Console.WriteLine("sdivmod():        b = {0}",b.getBytes().Reverse().toHexString());

			if (sgna){
				a = twos(a);
			}
			if (sgnb){
				b = twos(b);
			}

			UInt32[] result = udivmod(ref a, b);

			if (sgna != sgnb){
				result = twos(result);
			}
			if (sgna){
				a = twos(a);
			}

			//Console.WriteLine("sdivmod():   result = {0}",result.getBytes().Reverse().toHexString());
			//Console.WriteLine("sdivmod(): reminder = {0}",a.getBytes().Reverse().toHexString());

			return result;
		}

		/**
		 * @brief Logical Shift Left
		 **/
		public static void shl(UInt32[] a, int n)
		{
			if (n > 0)
			{
				int step = n >> 5;
				n &= 0x1F;

				for (int i = a.Length; i > 0; i--)
				{
					int b1 = i - 1 - step;
					int b2 = b1 - 1;

					if (b1 >= 0){
						a[i - 1] = (a[b1] << n);
						if ((n != 0)&&(b2 >= 0))
						{
							a[i - 1] |= ((a[b2] >> (32 - n)));
						}
					} else {
						a[i - 1] = 0;
					}
				}
			}
		}
		/**
		 * @brief Logical Shift Right
		 **/
		public static void shr(UInt32[] a, int n)
		{
			if (n > 0)
			{
				bool s = sign(a);
				int step = n >> 5;
				n &= 0x1F;

				for (int i = 0; i < a.Length; i++)
				{
					int b1 = i + step;
					int b2 = b1 + 1;

					if (b1 < a.Length)
					{
						a[i] = (a[b1] >> n);
						if ((b2 == a.Length) && (s)){
							a[i] |= ((0xffffffff << (32 - n)));
						} else if ((n != 0) && (b2 < a.Length))
						{
							a[i] |= ((a[b2] << (32 - n)));
						}

					} else {
						a[i] = s ? 0xFFFFFFFF : 0;
					}
				}
			}
		}

		/**
		 * @brief Compare
		 * @returns Negative Value if a<b, Positive Value if a>b,0 if equal
		 **/
		public static int cmp(UInt32[] a, UInt32[] b)
		{
			a = a.Segment(0);
			b = b.Segment(0);
			extendEqualSigned(ref a, ref b);

			UInt32[] result = sub(a, b);

			if (isZero(result))
			{
				return 0;
			}
			else if (sign(result))
			{
				return -1;
			}
			else
			{
				return 1;
			}
		}






		/* Helper Functions */

		private static UInt32 add(UInt32 a, UInt32 b, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)carry + (UInt64)a + (UInt64)b;
			carry = (UInt32)(ui64 >> 32);
			return (UInt32)(ui64 & 0xffffffff);
		}
		private static UInt32 add(UInt32 a, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)carry + (UInt64)a;
			carry = (UInt32)(ui64 >> 32);
			return (UInt32)(ui64 & 0xffffffff);
		}

		private static UInt32 sub(UInt32 a, UInt32 b, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)a - (UInt64)b - (UInt64)carry;
			carry = (ui64 & (1UL << 63)) != 0 ? (UInt32)1 : (UInt32)0;
			return (UInt32)(ui64 & 0xffffffff);
		}
		private static UInt32 sub(UInt32 a, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)a - (UInt64)carry;
			carry = (ui64 & (1UL << 63)) != 0 ? (UInt32)1 : (UInt32)0;
			return (UInt32)(ui64 & 0xffffffff);
		}

		private static UInt32 shl(UInt32 a, int n, ref UInt32 carry)
		{
			UInt64 result = (UInt64)((UInt64)a << n) | carry;
			carry = (UInt32)(result >> 32);
			return (UInt32)result;
		}
		private static UInt32 shr(UInt32 a, int n, ref UInt32 carry)
		{
			UInt64 result = (UInt64)((UInt64)a << (32 - n)) | ((UInt64)carry << 32);
			carry = (UInt32)result;
			return (UInt32)(result >> 32);
		}







	}
}