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);
            }
        }
        
    }
}