/**

 * BigInteger

 * 

 * An ActionScript 3 implementation of BigInteger (light version)

 * Copyright (c) 2007 Henri Torgemane

 * 

 * Derived from:

 * 		The jsbn library, Copyright (c) 2003-2005 Tom Wu

 * 

 * See LICENSE.txt for full license information.

 */

package com.hurlant.math

{

	import com.hurlant.crypto.prng.Random;

	import com.hurlant.util.Hex;

	import com.hurlant.util.Memory;

	import flash.utils.ByteArray;

	use namespace bi_internal;

	public class BigInteger

	{

		public static const DB:int = 30; // number of significant bits per chunk

		public static const DV:int = (1<<DB);

		public static const DM:int = (DV-1); // Max value in a chunk

		public static const BI_FP:int = 52;

		public static const FV:Number = Math.pow(2, BI_FP);

		public static const F1:int = BI_FP - DB;

		public static const F2:int = 2*DB - BI_FP;

		public static const ZERO:BigInteger = nbv(0);

		public static const ONE:BigInteger  = nbv(1);

		/*bi_internal */public var t:int; // number of chunks.

		bi_internal var s:int; // sign

		bi_internal var a:Array; // chunks

		/**

		 * 

		 * @param value

		 * @param radix  WARNING: If value is ByteArray, this holds the number of bytes to use.

		 * @param unsigned

		 * 

		 */

		public function BigInteger(value:* = null, radix:int = 0, unsigned:Boolean = false) {

			a = new Array;

			if (value is String) {

				if (radix&&radix!=16) throw new Error("BigInteger construction with radix!=16 is not supported.");

				value = Hex.toArray(value);

				radix=0;

			}

			if (value is ByteArray) {

				var array:ByteArray = value as ByteArray;

				var length:int = radix || (array.length - array.position);

				fromArray(array, length, unsigned);

			}

		}

		public function dispose():void {

			var r:Random = new Random;

			for (var i:uint=0;i<a.length;i++) {

				a[i] = r.nextByte();

				delete a[i];

			}

			a=null;

			t=0;

			s=0;

			Memory.gc();

		}

		public function toString(radix:Number=16):String {

			if (s<0) return "-"+negate().toString(radix);

			var k:int;

			switch (radix) {

				case 2:   k=1; break;

				case 4:   k=2; break;

				case 8:   k=3; break;

				case 16:  k=4; break;

				case 32:  k=5; break;

				default:

//					return toRadix(radix);

			}

			var km:int = (1<<k)-1;

			var d:int = 0;

			var m:Boolean = false;

			var r:String = "";

			var i:int = t;

			var p:int = DB-(i*DB)%k;

			if (i-->0) {

				if (p<DB && (d=a[i]>>p)>0) {

					m = true;

					r = d.toString(36);

				}

				while (i >= 0) {

					if (p<k) {

						d = (a[i]&((1<<p)-1))<<(k-p);

						d|= a[--i]>>(p+=DB-k);

					} else {

						d = (a[i]>>(p-=k))&km;

						if (p<=0) {

							p += DB;

							--i;

						}

					}

					if (d>0) {

						m = true;

					}

					if (m) {

						r += d.toString(36);

					}

				}

			}

			return m?r:"0";

		}

		public function toArray(array:ByteArray):uint {

			const k:int = 8;

			const km:int = (1<<8)-1;

			var d:int = 0;

			var i:int = t;

			var p:int = DB-(i*DB)%k;

			var m:Boolean = false;

			var c:int = 0;

			if (i-->0) {

				if (p<DB && (d=a[i]>>p)>0) {

					m = true;

					array.writeByte(d);

					c++;

				}

				while (i >= 0) {

					if (p<k) {

						d = (a[i]&((1<<p)-1))<<(k-p);

						d|= a[--i]>>(p+=DB-k);

					} else {

						d = (a[i]>>(p-=k))&km;

						if (p<=0) {

							p += DB;

							--i;

						}

					}

					if (d>0) {

						m = true;

					}

					if (m) {

						array.writeByte(d);

						c++;

					}

				}

			}

			return c;

		}

		/**

		 * best-effort attempt to fit into a Number.

		 * precision can be lost if it just can't fit.

		 */

		public function valueOf():Number {

			if (s==-1) {

				return -negate().valueOf();

			}

			var coef:Number = 1;

			var value:Number = 0;

			for (var i:uint=0;i<t;i++) {

				value += a[i]*coef;

				coef *= DV;

			}

			return value;

		}

		/**

		 * -this

		 */

		public function negate():BigInteger {

			var r:BigInteger = nbi();

			ZERO.subTo(this, r);

			return r;

		}

		/**

		 * |this|

		 */

		public function abs():BigInteger {

			return (s<0)?negate():this;

		}

		/**

		 * return + if this > v, - if this < v, 0 if equal

		 */

		public function compareTo(v:BigInteger):int {

			var r:int = s - v.s;

			if (r!=0) {

				return r;

			}

			var i:int = t;

			r = i-v.t;

			if (r!=0) {

				return r;

			}

			while (--i >=0) {

				r=a[i]-v.a[i];

				if (r != 0) return r;

			}

			return 0;

		}

		/**

		 * returns bit length of the integer x

		 */

		bi_internal function nbits(x:int):int {

			var r:int = 1;

			var t:int;

			if ((t=x>>>16) != 0) { x = t; r += 16; }

			if ((t=x>>8) != 0) { x = t; r += 8; }

			if ((t=x>>4) != 0) { x = t; r += 4; }

			if ((t=x>>2) != 0) { x = t; r += 2; }

			if ((t=x>>1) != 0) { x = t; r += 1; }

			return r;

		}

		/**

		 * returns the number of bits in this

		 */

		public function bitLength():int {

			if (t<=0) return 0;

			return DB*(t-1)+nbits(a[t-1]^(s&DM));

		}

		/**

		 * 

		 * @param v

		 * @return this % v

		 * 

		 */

		public function mod(v:BigInteger):BigInteger {

			var r:BigInteger = nbi();

			abs().divRemTo(v,null,r);

			if (s<0 && r.compareTo(ZERO)>0) {

				v.subTo(r,r);

			}

			return r;

		}

		/**

		 * this^e % m, 0 <= e < 2^32

		 */

		public function modPowInt(e:int, m:BigInteger):BigInteger {

			var z:IReduction;

			if (e<256 || m.isEven()) {

				z = new ClassicReduction(m);

			} else {

				z = new MontgomeryReduction(m);

			}

			return exp(e, z);

		}

		/**

		 * copy this to r

		 */

		bi_internal function copyTo(r:BigInteger):void {

			for (var i:int = t-1; i>=0; --i) {

				r.a[i] = a[i];

			}

			r.t = t;

			r.s = s;

		}

		/**

		 * set from integer value "value", -DV <= value < DV

		 */

		bi_internal function fromInt(value:int):void {

			t = 1;

			s = (value<0)?-1:0;

			if (value>0) {

				a[0] = value;

			} else if (value<-1) {

				a[0] = value+DV;

			} else {

				t = 0;

			}

		}

		/**

		 * set from ByteArray and length,

		 * starting a current position

		 * If length goes beyond the array, pad with zeroes.

		 */

		bi_internal function fromArray(value:ByteArray, length:int, unsigned:Boolean = false):void {

			var p:int = value.position;

			var i:int = p+length;

			var sh:int = 0;

			const k:int = 8;

			t = 0;

			s = 0;

			while (--i >= p) {

				var x:int = i<value.length?value[i]:0;

				if (sh == 0) {

					a[t++] = x;

				} else if (sh+k > DB) {

					a[t-1] |= (x&((1<<(DB-sh))-1))<<sh;

					a[t++] = x>>(DB-sh);

				} else {

					a[t-1] |= x<<sh;

				}

				sh += k;

				if (sh >= DB) sh -= DB;

			}

			if (!unsigned && (value[0]&0x80)==0x80) {

				s = -1;

				if (sh > 0) {

					a[t-1] |= ((1<<(DB-sh))-1)<<sh;

				}

			}

			clamp();

			value.position = Math.min(p+length,value.length);

		}

		/**

		 * clamp off excess high words

		 */

		bi_internal function clamp():void {

			var c:int = s&DM;

			while (t>0 && a[t-1]==c) {

				--t;

			}

		}

		/**

		 * r = this << n*DB

		 */

		bi_internal function dlShiftTo(n:int, r:BigInteger):void {

			var i:int;

			for (i=t-1; i>=0; --i) {

				r.a[i+n] = a[i];

			}

			for (i=n-1; i>=0; --i) {

				r.a[i] = 0;

			}

			r.t = t+n;

			r.s = s;

		}

		/**

		 * r = this >> n*DB

		 */

		bi_internal function drShiftTo(n:int, r:BigInteger):void {

			var i:int;

			for (i=n; i<t; ++i) {

				r.a[i-n] = a[i];

			}

			r.t = Math.max(t-n,0);

			r.s = s;