// BarrettMu, a class for performing Barrett modular reduction computations in
// JavaScript.
//
// Requires BigInt.js.
//
// Copyright 2004-2005 David Shapiro.
//
// You may use, re-use, abuse, copy, and modify this code to your liking, but
// please keep this header.
//
// Thanks!
//
// Dave Shapiro
// dave@ohdave.com

function BarrettMu(m, callback)
{
    //Hack
    var _this = this;

    _this.modulus = biCopy(m);
    _this.k = biHighIndex(_this.modulus) + 1;
    var b2k = new BigInt();
    b2k.digits[2 * _this.k] = 1; // b2k = b^(2k)

    biDivide(b2k, _this.modulus,
	     function(quotient)
	     {
		 _this.mu = quotient;
		 _this.bkplus1 = new BigInt();
		 _this.bkplus1.digits[_this.k + 1] = 1; // bkplus1 = b^(k+1)
		 _this.modulo = BarrettMu_modulo;
		 _this.multiplyMod = BarrettMu_multiplyMod;
		 _this.powMod = BarrettMu_powMod;

		 callback(_this);
	     }
	    );
}

function BarrettMu_modulo(x, callback)
{
    // Yet another hack
    var _this = this;

    var q1 = biDivideByRadixPower(x, _this.k - 1);
    var q2;
    var q3;
    var r1;
    var r2term;
    var r2;
    var r;
    var rgtem;


    biMultiply(q1, _this.mu,
	       function(product)
	       {
		   q2 = product;
		   q3 = biDivideByRadixPower(q2, _this.k + 1);
		   r1 = biModuloByRadixPower(x, _this.k + 1);

		   ensure_response(f);
	       }
	      );

    function f() {
	biMultiply(q3, _this.modulus,
		   function(product)
		   {
		       r2term = product;
		       r2 = biModuloByRadixPower(r2term, _this.k + 1);
		       r = biSubtract(r1, r2);

		       if (r.isNeg) {
			   r = biAdd(r, _this.bkplus1);
		       }

		       rgtem = biCompare(r, _this.modulus) >= 0;

		       ensure_response(loop);
		   }
		  );
    }

    function loop() {
	if (rgtem) {
	    r = biSubtract(r, _this.modulus);
	    rgtem = biCompare(r, _this.modulus) >= 0;

	    ensure_response(loop);
	}
	else {
	    callback(r);
	}
    }
}

function BarrettMu_multiplyMod(x, y, callback)
{
    var _this = this;

    biMultiply(x, y,
	       function(product)
	       {
		   _this.modulo(product,
			       function(modulus)
			       {
				   callback(modulus);
			       }
			      );
	       }
	      );
}

function BarrettMu_powMod(x, y, callback)
{
    var _this = this;

    var result = new BigInt();
    result.digits[0] = 1;
    var a = x;
    var k = y;

    ensure_response(loop);

    function loop() {
	function continuation() {
	    k = biShiftRight(k, 1);
	    if (k.digits[0] == 0 && biHighIndex(k) == 0) {
		callback(result);
	    }

	    _this.multiplyMod(a, a,
			     function(modulus)
			     {
				 a = modulus;
				 ensure_response(loop);
			     }
			    );

	}

	if ((k.digits[0] & 1) != 0) {
	    _this.multiplyMod(result, a,
			     function(modulus)
			     {
				 result = modulus;

				 ensure_response(continuation);
			     }
			    );
	}
	else {
	    ensure_response(continuation);
	}
    }
}