﻿using System;

namespace Gnu.MP.BrickCoinProtocol.BouncyCastle.Math.EC.Multiplier
{
	internal abstract class WNafUtilities
	{
		public static readonly string PRECOMP_NAME = "bc_wnaf";

		private static readonly int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[] { 13, 41, 121, 337, 897, 2305 };

		private static readonly byte[] EMPTY_BYTES = new byte[0];
		private static readonly int[] EMPTY_INTS = new int[0];
		private static readonly ECPoint[] EMPTY_POINTS = new ECPoint[0];

		public static int[] GenerateCompactNaf(BigInteger k)
		{
			if((k.BitLength >> 16) != 0)
				throw new ArgumentException("must have bitlength < 2^16", "k");
			if(k.SignValue == 0)
				return EMPTY_INTS;

			BigInteger _3k = k.ShiftLeft(1).Add(k);

			int bits = _3k.BitLength;
			int[] naf = new int[bits >> 1];

			BigInteger diff = _3k.Xor(k);

			int highBit = bits - 1, length = 0, zeroes = 0;
			for(int i = 1; i < highBit; ++i)
			{
				if(!diff.TestBit(i))
				{
					++zeroes;
					continue;
				}

				int digit = k.TestBit(i) ? -1 : 1;
				naf[length++] = (digit << 16) | zeroes;
				zeroes = 1;
				++i;
			}

			naf[length++] = (1 << 16) | zeroes;

			if(naf.Length > length)
			{
				naf = Trim(naf, length);
			}

			return naf;
		}

		public static int[] GenerateCompactWindowNaf(int width, BigInteger k)
		{
			if(width == 2)
			{
				return GenerateCompactNaf(k);
			}

			if(width < 2 || width > 16)
				throw new ArgumentException("must be in the range [2, 16]", "width");
			if((k.BitLength >> 16) != 0)
				throw new ArgumentException("must have bitlength < 2^16", "k");
			if(k.SignValue == 0)
				return EMPTY_INTS;

			int[] wnaf = new int[k.BitLength / width + 1];

			// 2^width and a mask and sign bit set accordingly
			int pow2 = 1 << width;
			int mask = pow2 - 1;
			int sign = pow2 >> 1;

			bool carry = false;
			int length = 0, pos = 0;

			while(pos <= k.BitLength)
			{
				if(k.TestBit(pos) == carry)
				{
					++pos;
					continue;
				}

				k = k.ShiftRight(pos);

				int digit = k.IntValue & mask;
				if(carry)
				{
					++digit;
				}

				carry = (digit & sign) != 0;
				if(carry)
				{
					digit -= pow2;
				}

				int zeroes = length > 0 ? pos - 1 : pos;
				wnaf[length++] = (digit << 16) | zeroes;
				pos = width;
			}

			// Reduce the WNAF array to its actual length
			if(wnaf.Length > length)
			{
				wnaf = Trim(wnaf, length);
			}

			return wnaf;
		}

		public static byte[] GenerateJsf(BigInteger g, BigInteger h)
		{
			int digits = System.Math.Max(g.BitLength, h.BitLength) + 1;
			byte[] jsf = new byte[digits];

			BigInteger k0 = g, k1 = h;
			int j = 0, d0 = 0, d1 = 0;

			int offset = 0;
			while((d0 | d1) != 0 || k0.BitLength > offset || k1.BitLength > offset)
			{
				int n0 = ((int)((uint)k0.IntValue >> offset) + d0) & 7;
				int n1 = ((int)((uint)k1.IntValue >> offset) + d1) & 7;

				int u0 = n0 & 1;
				if(u0 != 0)
				{
					u0 -= (n0 & 2);
					if((n0 + u0) == 4 && (n1 & 3) == 2)
					{
						u0 = -u0;
					}
				}

				int u1 = n1 & 1;
				if(u1 != 0)
				{
					u1 -= (n1 & 2);
					if((n1 + u1) == 4 && (n0 & 3) == 2)
					{
						u1 = -u1;
					}
				}

				if((d0 << 1) == 1 + u0)
				{
					d0 ^= 1;
				}
				if((d1 << 1) == 1 + u1)
				{
					d1 ^= 1;
				}

				if(++offset == 30)
				{
					offset = 0;
					k0 = k0.ShiftRight(30);
					k1 = k1.ShiftRight(30);
				}

				jsf[j++] = (byte)((u0 << 4) | (u1 & 0xF));
			}

			// Reduce the JSF array to its actual length
			if(jsf.Length > j)
			{
				jsf = Trim(jsf, j);
			}

			return jsf;
		}

		public static byte[] GenerateNaf(BigInteger k)
		{
			if(k.SignValue == 0)
				return EMPTY_BYTES;

			BigInteger _3k = k.ShiftLeft(1).Add(k);

			int digits = _3k.BitLength - 1;
			byte[] naf = new byte[digits];

			BigInteger diff = _3k.Xor(k);

			for(int i = 1; i < digits; ++i)
			{
				if(diff.TestBit(i))
				{
					naf[i - 1] = (byte)(k.TestBit(i) ? -1 : 1);
					++i;
				}
			}

			naf[digits - 1] = 1;

			return naf;
		}

		/**
         * Computes the Window NAF (non-adjacent Form) of an integer.
         * @param width The width <code>w</code> of the Window NAF. The width is
         * defined as the minimal number <code>w</code>, such that for any
         * <code>w</code> consecutive digits in the resulting representation, at
         * most one is non-zero.
         * @param k The integer of which the Window NAF is computed.
         * @return The Window NAF of the given width, such that the following holds:
         * <code>k = &amp;sum;<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
         * </code>, where the <code>k<sub>i</sub></code> denote the elements of the
         * returned <code>byte[]</code>.
         */
		public static byte[] GenerateWindowNaf(int width, BigInteger k)
		{
			if(width == 2)
			{
				return GenerateNaf(k);
			}

			if(width < 2 || width > 8)
				throw new ArgumentException("must be in the range [2, 8]", "width");
			if(k.SignValue == 0)
				return EMPTY_BYTES;

			byte[] wnaf = new byte[k.BitLength + 1];

			// 2^width and a mask and sign bit set accordingly
			int pow2 = 1 << width;
			int mask = pow2 - 1;
			int sign = pow2 >> 1;

			bool carry = false;
			int length = 0, pos = 0;

			while(pos <= k.BitLength)
			{
				if(k.TestBit(pos) == carry)
				{
					++pos;
					continue;
				}

				k = k.ShiftRight(pos);

				int digit = k.IntValue & mask;
				if(carry)
				{
					++digit;
				}

				carry = (digit & sign) != 0;
				if(carry)
				{
					digit -= pow2;
				}

				length += (length > 0) ? pos - 1 : pos;
				wnaf[length++] = (byte)digit;
				pos = width;
			}

			// Reduce the WNAF array to its actual length
			if(wnaf.Length > length)
			{
				wnaf = Trim(wnaf, length);
			}

			return wnaf;
		}

		public static int GetNafWeight(BigInteger k)
		{
			if(k.SignValue == 0)
				return 0;

			BigInteger _3k = k.ShiftLeft(1).Add(k);
			BigInteger diff = _3k.Xor(k);

			return diff.BitCount;
		}

		public static WNafPreCompInfo GetWNafPreCompInfo(ECPoint p)
		{
			return GetWNafPreCompInfo(p.Curve.GetPreCompInfo(p, PRECOMP_NAME));
		}

		public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo)
		{
			if((preCompInfo != null) && (preCompInfo is WNafPreCompInfo))
			{
				return (WNafPreCompInfo)preCompInfo;
			}

			return new WNafPreCompInfo();
		}

		/**
         * Determine window width to use for a scalar multiplication of the given size.
         * 
         * @param bits the bit-length of the scalar to multiply by
         * @return the window size to use
         */
		public static int GetWindowSize(int bits)
		{
			return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS);
		}

		/**
         * Determine window width to use for a scalar multiplication of the given size.
         * 
         * @param bits the bit-length of the scalar to multiply by
         * @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width
         * @return the window size to use
         */
		public static int GetWindowSize(int bits, int[] windowSizeCutoffs)
		{
			int w = 0;
			for(; w < windowSizeCutoffs.Length; ++w)
			{
				if(bits < windowSizeCutoffs[w])
				{
					break;
				}
			}
			return w + 2;
		}

		public static ECPoint MapPointWithPrecomp(ECPoint p, int width, bool includeNegated,
			ECPointMap pointMap)
		{
			ECCurve c = p.Curve;
			WNafPreCompInfo wnafPreCompP = Precompute(p, width, includeNegated);

			ECPoint q = pointMap.Map(p);
			WNafPreCompInfo wnafPreCompQ = GetWNafPreCompInfo(c.GetPreCompInfo(q, PRECOMP_NAME));

			ECPoint twiceP = wnafPreCompP.Twice;
			if(twiceP != null)
			{
				ECPoint twiceQ = pointMap.Map(twiceP);
				wnafPreCompQ.Twice = twiceQ;
			}

			ECPoint[] preCompP = wnafPreCompP.PreComp;
			ECPoint[] preCompQ = new ECPoint[preCompP.Length];
			for(int i = 0; i < preCompP.Length; ++i)
			{
				preCompQ[i] = pointMap.Map(preCompP[i]);
			}
			wnafPreCompQ.PreComp = preCompQ;

			if(includeNegated)
			{
				ECPoint[] preCompNegQ = new ECPoint[preCompQ.Length];
				for(int i = 0; i < preCompNegQ.Length; ++i)
				{
					preCompNegQ[i] = preCompQ[i].Negate();
				}
				wnafPreCompQ.PreCompNeg = preCompNegQ;
			}

			c.SetPreCompInfo(q, PRECOMP_NAME, wnafPreCompQ);

			return q;
		}

		public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated)
		{
			ECCurve c = p.Curve;
			WNafPreCompInfo wnafPreCompInfo = GetWNafPreCompInfo(c.GetPreCompInfo(p, PRECOMP_NAME));

			int iniPreCompLen = 0, reqPreCompLen = 1 << System.Math.Max(0, width - 2);

			ECPoint[] preComp = wnafPreCompInfo.PreComp;
			if(preComp == null)
			{
				preComp = EMPTY_POINTS;
			}
			else
			{
				iniPreCompLen = preComp.Length;
			}

			if(iniPreCompLen < reqPreCompLen)
			{
				preComp = ResizeTable(preComp, reqPreCompLen);

				if(reqPreCompLen == 1)
				{
					preComp[0] = p.Normalize();
				}
				else
				{
					int curPreCompLen = iniPreCompLen;
					if(curPreCompLen == 0)
					{
						preComp[0] = p;
						curPreCompLen = 1;
					}

					ECFieldElement iso = null;

					if(reqPreCompLen == 2)
					{
						preComp[1] = p.ThreeTimes();
					}
					else
					{
						ECPoint twiceP = wnafPreCompInfo.Twice, last = preComp[curPreCompLen - 1];
						if(twiceP == null)
						{
							twiceP = preComp[0].Twice();
							wnafPreCompInfo.Twice = twiceP;

							/*
                             * For Fp curves with Jacobian projective coordinates, use a (quasi-)isomorphism
                             * where 'twiceP' is "affine", so that the subsequent additions are cheaper. This
                             * also requires scaling the initial point's X, Y coordinates, and reversing the
                             * isomorphism as part of the subsequent normalization.
                             * 
                             *  NOTE: The correctness of this optimization depends on:
                             *      1) additions do not use the curve's A, B coefficients.
                             *      2) no special cases (i.e. Q +/- Q) when calculating 1P, 3P, 5P, ...
                             */
							if(ECAlgorithms.IsFpCurve(c) && c.FieldSize >= 64)
							{
								switch(c.CoordinateSystem)
								{
									case ECCurve.COORD_JACOBIAN:
									case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
									case ECCurve.COORD_JACOBIAN_MODIFIED:
										{
											iso = twiceP.GetZCoord(0);
											twiceP = c.CreatePoint(twiceP.XCoord.ToBigInteger(),
												twiceP.YCoord.ToBigInteger());

											ECFieldElement iso2 = iso.Square(), iso3 = iso2.Multiply(iso);
											last = last.ScaleX(iso2).ScaleY(iso3);

											if(iniPreCompLen == 0)
											{
												preComp[0] = last;
											}
											break;
										}
								}
							}
						}

						while(curPreCompLen < reqPreCompLen)
						{
							/*
                             * Compute the new ECPoints for the precomputation array. The values 1, 3,
                             * 5, ..., 2^(width-1)-1 times p are computed
                             */
							preComp[curPreCompLen++] = last = last.Add(twiceP);
						}
					}

					/*
                     * Having oft-used operands in affine form makes operations faster.
                     */
					c.NormalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso);
				}
			}

			wnafPreCompInfo.PreComp = preComp;

			if(includeNegated)
			{
				ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg;

				int pos;
				if(preCompNeg == null)
				{
					pos = 0;
					preCompNeg = new ECPoint[reqPreCompLen];
				}
				else
				{
					pos = preCompNeg.Length;
					if(pos < reqPreCompLen)
					{
						preCompNeg = ResizeTable(preCompNeg, reqPreCompLen);
					}
				}

				while(pos < reqPreCompLen)
				{
					preCompNeg[pos] = preComp[pos].Negate();
					++pos;
				}

				wnafPreCompInfo.PreCompNeg = preCompNeg;
			}

			c.SetPreCompInfo(p, PRECOMP_NAME, wnafPreCompInfo);

			return wnafPreCompInfo;
		}

		private static byte[] Trim(byte[] a, int length)
		{
			byte[] result = new byte[length];
			Array.Copy(a, 0, result, 0, result.Length);
			return result;
		}

		private static int[] Trim(int[] a, int length)
		{
			int[] result = new int[length];
			Array.Copy(a, 0, result, 0, result.Length);
			return result;
		}

		private static ECPoint[] ResizeTable(ECPoint[] a, int length)
		{
			ECPoint[] result = new ECPoint[length];
			Array.Copy(a, 0, result, 0, a.Length);
			return result;
		}
	}
}
