/*
 * Variable Length Integer
 * (C) Copyright by Rafael Vuijk (aka Dark Fader)
 * Note: No negative numbers supported, so kind of useless to steal >:)
 */

var VLI_base = 65536;
var VLI_bits = 16;
var VLI_bitshift = 4;		// darn... oh well, 16 bits is good enough

function VLI(n)
{
	this.constructor = VLI_VLI;
	switch (typeof(n))
	{
		case "undefined": this.constructor(); return this;
		case "string": this.constructor(); this.fromInt(parseInt(n)); return this;
		case "number": this.constructor(); this.fromInt(n); return this;
		case "object": if (n.typename == "VLI")
		{
			var cloned = n.clone();
			this.parts = cloned.parts;
			//alert(this.typename);
			return this;
		}
		default: throw "Invalid argument";
	}
}

function VLI_VLI()
{
	// attributes
	//this.negative = false;
	this.typename = "VLI";
	this.parts = new Array();

	// methods
	this.clone = VLI_clone;
	this.clean = VLI_clean;
	this.isNul = VLI_isNul;
	this.compareTo = VLI_compareTo;
	this.shl = VLI_shl;
	this.getBit = VLI_getBit;
	this.fromInt = VLI_fromInt;
	this.toInt = VLI_toInt;
	this.valueOf = this.toInt;
	this.toString = VLI_toString;
	this.add = VLI_add;
	this.sub = VLI_sub;
	this.mul = VLI_mul;
	this.div = VLI_div;
}

function VLI_clone()
{
	var other = new VLI();
	for (var i=0; i<this.parts.length; i++)
	{
		other.parts[i] = this.parts[i];
	}
	return other;
}

function VLI_clean()
{
	// clean up some zero's
	while (this.parts[this.parts.length-1] == 0) this.parts.length--;
}

function VLI_isNul()
{
	this.clean();
	return (this.parts.length == 0);
}

function VLI_compareTo(other)
{
	var maxlength = Math.max(this.parts.length, other.parts.length);
	for (var i=maxlength-1; i>=0; i--)
	{
		var t = i < this.parts.length ? this.parts[i] : 0;
		var o = i < other.parts.length ? other.parts[i] : 0;
		if (t > o) return +1;
		if (t < o) return -1;
	}
	return 0;
}

function VLI_toString()
{
	var result = "0x";
	if (!this.parts.length) result += "0";
	else for (var i=this.parts.length-1; i>=0; i--)
	{
		var hex = this.parts[i].toString(16);
		while (hex.length < VLI_bits/4) hex = "0" + hex;
		result += hex;
	}
	return result;
}

function VLI_shl(num)
{
	var result = new VLI();
	var offset = num >>> VLI_bitshift;
	for (i=0; i<offset+1; i++) result.parts[i] = 0;	// clear before offset
	var s1 = (num & (VLI_bits-1));
	var s2 = VLI_bits - s1;
	for (var i=0; i<this.parts.length; i++)
	{
		var n = this.parts[i];
		result.parts[i+offset] |= (n << s1) & (VLI_base-1);
		result.parts[i+offset+1] |= (n >>> s2);
	}
	result.clean();
	return result;
}

function VLI_getBit(num)
{
	var i = num >>> VLI_bitshift;
	if (i >= this.parts.length) return 0;
	return this.parts[i] >>> (num & (VLI_bits-1)) & 1;
}

function VLI_add(other)
{
	var result = new VLI();
	var carry = 0;
	var maxlength = Math.max(this.parts.length, other.parts.length);
	var i;
	for (i=0; i<maxlength; i++)
	{
		var t = i < this.parts.length ? this.parts[i] : 0;
		var o = i < other.parts.length ? other.parts[i] : 0;
		var n = t + o + carry;
		carry = n >>> VLI_bits;
		result.parts[i] = n & (VLI_base-1);
	}
	if (carry) result.parts[i] = carry;
	return result;
}

function VLI_sub(other)
{
	var result = new VLI();
	var carry = 0;
	var maxlength = Math.max(this.parts.length, other.parts.length);
	var i;
	for (i=0; i<maxlength; i++)
	{
		var t = i < this.parts.length ? this.parts[i] : 0;
		var o = i < other.parts.length ? other.parts[i] : 0;
		var n = t - o + carry;
		carry = n >>> VLI_bits;
		result.parts[i] = n & (VLI_base-1);
	}
	if (carry) result.parts[i] = carry;
	return result;
}

function VLI_mul(other)
{
	var result = new VLI();
	for (var offset=0; offset<other.parts.length; offset++)
	{
		var digit = other.parts[offset];

		var muldigited = new VLI();
		var i;
		for (i=0; i<offset; i++) muldigited.parts[i] = 0;	// clear before offset
		var carry = 0;
		for (i=0; i<this.parts.length; i++)
		{
			var n = this.parts[i] * digit + carry;
			carry = n >>> VLI_bits;
			muldigited.parts[i+offset] = n & (VLI_base-1);
		}
		if (carry) muldigited.parts[i+offset] = carry;

		result = result.add(muldigited);
	}
	result.clean();
	return result;
}

var VLI_remainder = 0;	//new VLI();
function VLI_div(divisor, preshift)
{
	//if (divisor.compareTo(new VLI(0)) == 0) throw "Divide by zero!";

	var dividend = this.clone();	// temporary
	var orig_num_bits = (dividend.parts.length + 0) * VLI_bits;
	var num_bits = orig_num_bits;
	var remainder = new VLI();

	/*if (preshift == true)
	{
		var undo_dividend;
		while (remainder.compareTo(divisor) < 0)
		{
			var bit = dividend.getBit(orig_num_bits-1);
			remainder = remainder.shl(1);
			remainder.parts[0] |= bit;
			undo_dividend = dividend;
			dividend = dividend.shl(1);
			num_bits--;
		}

		dividend = undo_dividend;
		remainder = remainder.div(new VLI(2));	// ******** should make a right shift
		num_bits++;
	}*/

	// do the actual division
	var result = new VLI();
  	for (var i=0; i<num_bits; i++)
  	{
  		remainder = remainder.shl(1).add(new VLI(dividend.getBit(orig_num_bits-1)));
    	var q = (divisor.compareTo(remainder) > 0) ? 0 : 1;
    	dividend = dividend.shl(1);
    	result = result.shl(1).add(new VLI(q));
    	if (q) remainder = remainder.sub(divisor);
  	}

  	VLI_remainder = remainder.valueOf();

	result.clean();
  	return result;
}

function VLI_fromInt(n)
{
	var i;
	for (i=0; n>0; i++)
	{
		this.parts[i] = n & (VLI_base-1); n >>>= VLI_bits;
	}
	this.parts.length = i;
}

function VLI_toInt()
{
	var n = 0;
	for (var i=0; i<this.parts.length; i++)
	{
		n += this.parts[i] << (VLI_bits*i);
	}
	return n;
}