package com.hurlant.math

{

	use namespace bi_internal;

	internal class BarrettReduction implements IReduction

	{

		private var m:BigInteger;

		private var r2:BigInteger;

		private var q3:BigInteger;

		private var mu:BigInteger;

		public function BarrettReduction(m:BigInteger) {

			// setup Barrett

			r2 = new BigInteger;

			q3 = new BigInteger;

			BigInteger.ONE.dlShiftTo(2*m.t, r2);

			mu = r2.divide(m);

			this.m = m;

		}

		public function revert(x:BigInteger):BigInteger

		{

			return x;

		}

		/**

		 * 

		 * @param x

		 * @param y

		 * @param r = x*y mod m; x != r

		 * 

		 */

		public function mulTo(x:BigInteger, y:BigInteger, r:BigInteger):void

		{

			x.multiplyTo(y, r);

			reduce(r);

		}

		/**

		 * 

		 * @param x

		 * @param r = x^2 mod m; x != r

		 * 

		 */

		public function sqrTo(x:BigInteger, r:BigInteger):void

		{

			x.squareTo(r);

			reduce(r);

		}

		public function convert(x:BigInteger):BigInteger

		{

			if (x.s<0 || x.t>2*m.t) {

				return x.mod(m);

			} else if (x.compareTo(m)<0) {

				return x;

			} else {

				var r:BigInteger = new BigInteger;

				x.copyTo(r);

				reduce(r);

				return r;

			}

		}

		/**

		 * 

		 * @param x = x mod m (HAC 14.42)

		 * 

		 */

		public function reduce(lx:BigInteger):void

		{

			var x:BigInteger = lx as BigInteger;

			x.drShiftTo(m.t-1,r2);

			if (x.t>m.t+1) {

				x.t = m.t+1;

				x.clamp();

			}

			mu.multiplyUpperTo(r2, m.t+1, q3);

			m.multiplyLowerTo(q3, m.t+1, r2);

			while (x.compareTo(r2)<0) {

				x.dAddOffset(1, m.t+1);

			}

			x.subTo(r2,x);

			while (x.compareTo(m)>=0) {

				x.subTo(m,x);

			}

		}

	}

}