/**
 * @fileoverview
 * BISON - Binary Interchange Standard and Object Notation
 * This file contains an exemplary implementation of the BISON format. 
 * Support for 64 bit integers as well as the "stream" type are missing from
 * this implementation since JavaScript itself does not support these types.
 * The code herein is by no means optimal in terms of performance or
 * error-handling. It has also not been tested to such an extend that it would
 * be safe to use it in a production environment.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 * 
 * If you find this useful or if you would like to contribute to this project,
 * please let me know. Thank you.
 * 
 * Copyright (c) 2006 by Kai Jäger
 * 
 * @author	Kai Jäger [jaeger_at_xwrs_dot_net] 
 * @version	1.0
 */

/**
 * Tells Bison whether to use single or double precision when encoding floating 
 * point values. Double precision floats are 8 bytes wide while single 
 * precision floats only use 4 bytes.
 * 
 * @type Boolean
 */ 
Bison.useDoublePrecision = false;

/**
 * Repeats the given string.
 * 
 * @param	{Number} times The number of times the string should be repeated
 * @return	The repeated string
 * @type	String 
 */
String.prototype.repeat = function(times) {
	var repeatedStr = "";
	for (var i = 0; i < times; i++) {
		repeatedStr += this;
	}
	return repeatedStr;
}

/**
 * Reverses a string
 * 
 * @return	The reversed string
 * @type	String
 */
String.prototype.reverse = function() {
	var reversedString = "";
	for (var i = this.length - 1; i >= 0; i--) {
		reversedString += this.charAt(i);
	}
	return reversedString;
}

String.prototype.binCharCodeAt = function(index) {
	var charCode = this.charCodeAt(index);
	if (charCode <= 0xFF) {
		return charCode;
	} else if (charCode <= 0xFFFF) {
		return (charCode & 0x00FF);
	} else if (charCode <= 0xFFFFFF) {
		return (charCode & 0x0000FF);
	} else {
		return (charCode & 0x000000FF);
	}
}

/**
 * Provides methods for serializing or deserializing objects or primitive types
 * into or from a binary format.  
 * 
 * @constructor
 */
function Bison() {
	/**
	 * Constant definitions for the various data types.
	 */
	var TYPE_NULL = 0x01;
	var TYPE_UNDEFINED = 0x02;
	var TYPE_BOOLEAN_TRUE = 0x03;
	var TYPE_BOOLEAN_FALSE = 0x04;
	var TYPE_INT8 = 0x05;
	var TYPE_INT16 = 0x06;
	var TYPE_INT24 = 0x07;
	var TYPE_INT32 = 0x08;
	var TYPE_INT40 = 0x09;
	var TYPE_INT48 = 0x0A;
	var TYPE_INT56 = 0x0B;
	var TYPE_INT64 = 0x0C;
	var TYPE_SINGLE = 0x0D;
	var TYPE_DOUBLE = 0x0E;
	var TYPE_STRING = 0x0F;
	var TYPE_ARRAY = 0x10;
	var TYPE_OBJECT = 0x11;
	var TYPE_STREAM = 0x12;  	
	
	/**
	 * Index is used by the _deserialize method. This closure, although not
	 * especially pretty, is needed due to the recursive nature of the method.
	 * 
	 * @ignore
	 */
	var index = 0;
	
	/**
	 * Returns an array containing the individual bits of the given 
	 * unsigned integer value.
	 * 
	 * @private
	 * @param	{Number} number The number to process
	 * @return	An array containing the individual bits
	 * @type	Array
	 */
	function getNumberBits(number) {
		var numBits = [];
		var index = 0;
		do {
			numBits[index] = number % 2;
			number >>= 1;
			index++;
		} while (number > 0 && index < 1024);	
		numBits.reverse();
		return numBits;
	}
	
	/**
	 * Takes an array of bits, packs each octet of bits into one byte and
	 * returns the byte sequence.
	 * 
	 * @private
	 * @param	{Array} bits An array containing the bits to pack
	 * @return	The packed bits as a string
	 * @type	String
	 */
	function packBits(bits) {
		var bitStr = bits.join('');
		var packedBits = "";
		for (var i = (bitStr.length >> 3) - 1; i >= 0; i--)  {
			packedBits += String.fromCharCode(parseInt(bitStr.substr(i * 8, 8), 2));
		}
		return packedBits;
	}
	
	/**
	 * Decodes the binary representation of a variable length signed or unsigned 
	 * integer value into a number.
	 * Signed integers need to be in twos-complement notation.
	 * 
	 * @private
	 * @param	{String} byteStream A stream of bytes
	 * @return	The decoded integer
	 * @type	Number
	 */
	function unpackInt(byteStream) {
		var num = 0;
		var sign = (byteStream.binCharCodeAt(byteStream.length - 1) & 0x80) > 0;
		if (sign) {
			byteStream = byteStream + new String(String.fromCharCode(0xFF)).repeat(4 - byteStream.length);
		}
		for (var i = byteStream.length - 1; i >= 0; i--) {
			num <<= 8;
			num |= byteStream.binCharCodeAt(i);			
		}
		if (sign) {
			num--;
			num = ~num;
			num = -num;	
		}
		return num;
	}	
	
	/**
	 * Takes an IEEE single- or double precision floating point number in binary
	 * form and decodes it into a number.
	 * 
	 * @private
	 * @param	{String} byteStream A stream of bytes
	 * @return	The decoded float
	 * @type	Number
	 */
	function unpackFloat(byteStream) {
		var isDouble = byteStream.length == 8;
		byteStream = byteStream.reverse();
		
		var byteArr = [];
		for (var i = 0; i < byteStream.length; i++) {
			byteArr[i] = byteStream.binCharCodeAt(i);
		}

		var sign = (byteArr[0] & 0x80) > 0;	

		if (isDouble) {
			var exponent = (((byteArr[0] & 0x7F) << 4) | ((byteArr[1] & 0xF0) >> 4)) - 1023;
			var mantissaLength = 52;
			var offset = 4;
		} else {
			var exponent = (((byteArr[0] & 0x7F) << 1) | (byteArr[1] & 0x80) >> 7) - 127;
			var mantissaLength = 23;
			var offset = 1;
		}
		var frac = 1.0;
		var fracPart = 1;
		var currByte;
		for (var i = offset; i < mantissaLength + offset; i++) {
			currByte = byteArr[(i >> 3) + 1];
			fracPart *= 0.5;
			if (currByte & (1 << (7 - (i % 8)))) {
				frac += fracPart; 	
			}
		}
		var floatValue = 0.0;
		floatValue = Math.pow(2, exponent) * frac;
		if (sign) {
			floatValue = -floatValue;	
		}
		return floatValue;
	}	
	
	/**
	 * Flips the bits of the given bit array (1 becomes 0, 0 becomes 1).
	 * 
	 * @private
	 * @param	{Array} bits An array of bits
	 * @return	The flipped bit array
	 * @type	Array
	 */
	function flipBits(bits) {
		for (var i = 0; i < bits.length; i++) {
			bits[i] = (bits[i] == 1?0:1);
		}
		return bits;
	}
	
	/**
	 * Increments a binary number by one
	 * 
	 * @private
	 * @param	{Array} bits An array of bits
	 * @return	The increment number as a bit array
	 * @type	Array
	 */
	function binInc(bits) {
		var overflow = 1;
		var done = false;
		for (var i = bits.length - 1; i >= 0; i--) {
			switch (bits[i] + overflow) {
				case 1:
					bits[i] = 1;
					done = true;
					break;
				case 2:
					bits[i] = 0;
					overflow = 1;
					break;
				case 3:
					bits[i] = 1;
					overflow = 1;
					break;
			}	
			if (done) {
				break;
			}
		}
		if (!done) {
			bits = [1].concat(bits);
		}
		return bits;
	}
	
	/**
	 * Increases the size of the given bit array by either prepending or
	 * appending the necessary number of zeros to achieve the length 
	 * specified by the len parameter.
	 * 
	 * @private
	 * @param	{Array} bits An array of bits
	 * @param	{Number} len The desired length
	 * @append	{Boolean} append Whether the zeros should be pre- or appended
	 * @return	A bit array that has the desired length
	 * @type	{Array}
	 */
	function zeroFill(bits, len, append) {
		if (bits.length < len) {
			var zeros = new Array(len - bits.length);
			for (var i = 0; i < zeros.length; i++) {
				zeros[i] = 0;
			}
			if (!append || arguments.length == 2) {
				return zeros.concat(bits);
			} else {
				return bits.concat(zeros);
			}
		} else {
			return bits;
		}
	}
	
	/**
	 * Converts the given integer or floating point number into binary form.
	 * The method first determines the type and length of the number and then
	 * either converts it using twos-complement or IEEE floating point notation. 
	 * 
	 * @private
	 * @param	{Number} number The number to convert
	 * @return	A stream of bytes holding the binary representation of the number
	 * @type	String
	 */
	function numberToBinary(number) {
		var numberStream = "";
		var sign = (number < 0?1:0);
		number = Math.abs(number);
		if (Math.abs(number - parseInt(number)) > 0) {
			var exponentSize = 8;
			var mantissaSize = 23;
			var bias = 127;
			var floatType = TYPE_SINGLE;

			if (Bison.useDoublePrecision) {
				exponentSize = 11;
				mantissaSize = 52;
				bias = 1023;
				floatType = TYPE_DOUBLE;
			}
			
			var intPart = parseInt(number);
			var fracPart = number - intPart;
			var intBits = getNumberBits(intPart);
			var fracBits = [];			
			index = 0;
			do {
				fracPart *= 2;			
				if (fracPart >= 1) {
					fracBits[index] = 1;
					fracPart--;
				} else {
					fracBits[index] = 0;
				}
				index++;
			} while (fracPart > 0 && index < 1024);
			var mantissa = intBits.concat(fracBits);
			var exponent = 0;
			if (intBits.length == 1 && intBits[0] == 0) {
				for (var i = 0; i < mantissa.length; i++) {
					exponent++;
					if (mantissa[i] == 1) {
						break;
					}
				}
				mantissa = mantissa.slice(exponent, exponent + mantissaSize);
				exponent--;
				exponent *= -1;
			} else {
				exponent = intBits.length - 1;
				mantissa = mantissa.slice(1, mantissaSize + 1);
			}
			exponent += bias;	
			var exponentBits = getNumberBits(exponent);
			var floatBits = [sign].concat(zeroFill(exponentBits, exponentSize)).concat(zeroFill(mantissa, mantissaSize, true));
			var bytes = packBits(floatBits);
			numberStream += String.fromCharCode(floatType) + bytes;
		} else {
			var numBits = getNumberBits(number);

			numBits = zeroFill(numBits, Math.ceil(numBits.length / 8) * 8);
			if (sign == 1) {
				numBits = binInc(flipBits(numBits));	
				if (numBits[0] == 0) {
					numBits = [1, 1, 1, 1, 1, 1, 1, 1].concat(numBits);
				}
			} else {
				if (numBits[0] == 1) {
					numBits = [0, 0, 0, 0, 0, 0, 0, 0].concat(numBits);
				}				
			}
			numberStream = packBits(numBits);
			switch (numberStream.length) {
				case 1:
					numberStream = String.fromCharCode(TYPE_INT8) + numberStream;
					break;
				case 2:
					numberStream = String.fromCharCode(TYPE_INT16) + numberStream;
					break;
				case 3:
					numberStream = String.fromCharCode(TYPE_INT24) + numberStream;
					break;
				case 4:
					numberStream = String.fromCharCode(TYPE_INT32) + numberStream;
					break;
				case 5:
					numberStream = String.fromCharCode(TYPE_INT40) + numberStream;
					break;
				case 6:
					numberStream = String.fromCharCode(TYPE_INT48) + numberStream;
					break;
				case 7:
					numberStream = String.fromCharCode(TYPE_INT56) + numberStream;
					break;
				case 8:
					numberStream = String.fromCharCode(TYPE_INT64) + numberStream;
					break;
			}
		}
		return numberStream;
	}
	
	/**
	 * Applies yEnc encoding to the given byte stream. The encoding eliminates
	 * null-bytes and other problematic characters through a special encoding.
	 * The actual implementation differs slightly from the original yEnc
	 * standard.
	 * 
	 * @private
	 * @param	{String} byteStream A stream of bytes
	 * @return	The encoded byte stream
	 * @type	String
	 */
	function yEncode(byteStream) {
		var encodedStr = "";
		for (var i = 0; i < byteStream.length; i++) {
			var value = (byteStream.binCharCodeAt(i) + 42) % 256;
            
            if (value == 0 || value == 10 || value == 13 || value == 61) {
                encodedStr += "=" + String.fromCharCode((value + 64) % 256);
            } else {
                encodedStr += String.fromCharCode(value);
            }
        }		
		return encodedStr;
	}
	
	/**
	 * Decodes the given byte stream
	 * 
	 * @private
	 * @param	{String} byteStream A stream of bytes
	 * @return	The decoded byte stream
	 * @type	String
	 */
	function yDecode(byteStream) {
		var decodedStr = "";
		for (var i = 0; i < byteStream.length; i++) {
			if (byteStream.charAt(i) == "=") {
				i++;
				decodedStr += String.fromCharCode((byteStream.binCharCodeAt(i) - 64) - 42);
            } else {
                decodedStr += String.fromCharCode(byteStream.binCharCodeAt(i) - 42);
            }
        }
        return decodedStr;
	}
	
	/**
	 * This recursive function takes an object or primitive type and serializes
	 * it into a binary format. 
	 * 
	 * @private
	 * @param	{Mixed} obj The object to encode
	 * @return	A stream of bytes
	 * @type	String
	 */
	function _serialize(obj) {
		var byteStream = "";
		var type = typeof(obj);
		if (typeof(obj) == "object" && !obj) {
			type = "null";
		}
		switch (type) {
			case "null":
				byteStream += String.fromCharCode(TYPE_NULL);
				break;
			case "undefined":
				byteStream += String.fromCharCode(TYPE_UNDEFINED);
				break;
			case "boolean":
				byteStream += String.fromCharCode(obj?TYPE_BOOLEAN_TRUE:TYPE_BOOLEAN_FALSE);
				break;
			case "number":
				byteStream += numberToBinary(obj);			
				break;
			case "string":
				byteStream += String.fromCharCode(TYPE_STRING) + obj + "\0";
				break;
			case "object":
				var i = 0;
				var isArray = true;
				for (var element in obj) {
					if (element != i) {
						isArray = false;
						break;
					}
					i++;									
				}
				byteStream += (isArray?String.fromCharCode(TYPE_ARRAY):String.fromCharCode(TYPE_OBJECT));
				var memberCount = 0;
				var objStream = "";
				for (var member in obj) {
					if (!isArray) {
						objStream += member + "\0";
					} 
					objStream += _serialize(obj[member]);
					memberCount++;
				}
				byteStream += packBits(zeroFill(getNumberBits(memberCount), 16));
				byteStream += objStream;
				break;
		}
		return byteStream;
	}
	
	/**
	 * This recursive function takes a stream of bytes an turns it into either
	 * an object or a primitive type.
	 * 
	 * @private
	 * @param	{String} byteStream The byte stream to decode
	 * @return	An object or primitive type
	 * @type	Mixed
	 * @throws	Error If an unrecognized type identifier is found
	 */	
	function _deserialize(byteStream) {
		var type = unpackInt(byteStream.charAt(index));
		index++;
		switch (type) {
			case TYPE_NULL:
				return null;
			case TYPE_UNDEFINED:
				return;
			case TYPE_BOOLEAN_TRUE:
				return true;
			case TYPE_BOOLEAN_FALSE:
				return false;
			case TYPE_INT8:
			case TYPE_INT16:
			case TYPE_INT24:
			case TYPE_INT32:
			case TYPE_INT40:
			case TYPE_INT48:
			case TYPE_INT56:
			case TYPE_INT64:
				var bytes = type - TYPE_INT8 + 1;
				var number = "";
				for (var i = 0; i < bytes; i++) {
					number += byteStream.charAt(index);
					index++;
				}  			
				return unpackInt(number);
			case TYPE_SINGLE:
			case TYPE_DOUBLE:
				var bytes = (type - TYPE_SINGLE + 1) * 4;
				var number = "";
				for (var i = 0; i < bytes; i++) {
					number += byteStream.charAt(index);
					index++;
				}  		
				return unpackFloat(number);
			case TYPE_STRING:
				var string = "";
				while (byteStream.binCharCodeAt(index) > 0) {
					string += byteStream.charAt(index);
					index++;
				}      
				index++;
				return string;	
			case TYPE_OBJECT:
			case TYPE_ARRAY:
				var isArray = (type == TYPE_ARRAY);
				var obj = {};
				if (isArray) {
					var obj = [];
				}
				var temp = "";
				for (var i = 0; i < 2; i++) {
					temp += byteStream.charAt(index);
					index++;
				}  
				var memberCount = unpackInt(temp);
				for (var i = 0; i < memberCount; i++) {
					if (!isArray) {
						var member = "";
						while (byteStream.binCharCodeAt(index) > 0) {
							member += byteStream.charAt(index);
							index++;
						}
						index++;
					} else {
						member = i;
					}      
					obj[member] = _deserialize(byteStream);			
				}
				return obj;
			default:
				throw new Error("Invalid type identifier found.");
		}
	}
	
	/**
	 * Takes the given object or primitive type and serializes it. yEnc encoding
	 * is applied to the byte stream before it is returned.
	 * 
	 * @param	{Mixed} obj The object or primitive type that will be serialized
	 * @return	A sequence of bytes representing the serialized object
	 * @type	String
	 */
	this.serialize = function(obj) {
		return yEncode("FMB" + _serialize(obj));
	}

	/**
	 * Takes a stream of bytes, decodes it using a yEnc decoder and deserializes the
	 * object or primitive type it represents.
	 * 
	 * @param	{String} byteStream A stream of bytes representing the serialized 
	 * 			object
	 * @return	The deserialized object or primitive type
	 * @type	Mixed
	 * @throws	Error If an unrecognized type identifier is found
	 */
	this.deserialize = function(byteStream) {
		index = 0;
		byteStream = yDecode(byteStream);
		if (byteStream.substr(0, 3) != "FMB") {
			throw new Error("Not a valid BISON message");
		}
		return _deserialize(byteStream.substr(3, byteStream.length - 3));
	}
}