Decompressing Data with the DEFLATE Algorithm in JavaScript

The code below, when run, prompts the user to upload a compressed file in GZIP format, which will then be uncompressed, and the uncompressed data will be displayed both as hexadecimal digits and as UTF8 text.

This implementation of DEFLATE is basically a port of a Java implementation created by Nyuki Minase, an edited Java version of which I presented in a previous post. I tried to leave the code in this port as nearly identical as possible, but I had to make a few questionable changes here and there. The most distressing of these is where I commented out the writing of data to the output byte stream in Decompressor.decodeHuffmanBlock(), because it seemed to be appending nonsense to the end of my test data. But no doubt it was there for a reason. It should go without saying that any bugs in this implementation should be assumed to be my own.

I tested the program by creating a simple .txt file and compressing it to a .gz with 7-Zip.

Note that this implementation only does decompression, not compression.

decompressingwithdeflate


<html>
<body>

<!-- ui -->

	<div>
		<div><label>Compressed Bytes as Hexadecimal:</label></div>
		<div><input type="file" onchange="inputCompressedDataLoadFromFile_Changed(this);"></input></div>
		<div><textarea id="textareaCompressed" cols="32" rows="8"></textarea></div>
	</div>

	<div>
		<button onclick="buttonDecompress_Clicked();">Decompress</button>
	</div>

	<div>
		<div><label>Uncompressed Bytes as Hexadecimal:</label></div>
		<div><textarea id="textareaUncompressed" cols="32" rows="8"></textarea></div>

		<div><label>Uncompressed Bytes as Text (UTF8):</label></div>
		<div><textarea id="textareaUncompressedAsUTF8" cols="32" rows="8"></textarea></div>
	</div>

<!-- ui ends -->

<script type="text/javascript">

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.removeAt = function(index)
	{
		this.splice(index, 1);
		return this;
	}
}

function StringExtensions()
{
	// extension class
}
{
	String.prototype.padLeft = function(charToPadWith, lengthToPadTo)
	{
		var returnValue = this;
		while (returnValue.length < lengthToPadTo)
		{
			returnValue = charToPadWith + returnValue;
		}
		return returnValue;
	}
}

// ui events

function buttonDecompress_Clicked()
{
	var textareaCompressed = document.getElementById("textareaCompressed");	
	var bytesCompressedAsHexadecimal = textareaCompressed.value;
	var bytesCompressed = [];
	for (var i = 0; i < bytesCompressedAsHexadecimal.length; i += 2)
	{
		var byteAsHexadecimal = bytesCompressedAsHexadecimal.substr(i, 2);
		var byte = parseInt(byteAsHexadecimal, 16);
		bytesCompressed.push(byte);
	}

	var inflator = new Inflator();
	var bytesDecompressed = inflator.decompressBytes(bytesCompressed);

	var bytesDecompressedAsHexadecimal = "";
	var bytesDecompressedAsUTF8 = "";
	for (var i = 0; i < bytesDecompressed.length; i++)
	{
		var byte = bytesDecompressed[i];

		var byteAsHexadecimal = byte.toString(16).padLeft("0", 2);
		bytesDecompressedAsHexadecimal += byteAsHexadecimal;

		var byteAsUTF8 = String.fromCharCode(byte);
		bytesDecompressedAsUTF8 += byteAsUTF8;
	}

	var textareaUncompressed = document.getElementById("textareaUncompressed");
	textareaUncompressed.value = bytesDecompressedAsHexadecimal;

	var textareaUncompressedAsUTF8 = document.getElementById("textareaUncompressedAsUTF8");
	textareaUncompressedAsUTF8.value = bytesDecompressedAsUTF8;

}

function inputCompressedDataLoadFromFile_Changed(input)
{
	var file = input.files[0];
	var fileReader = new FileReader();
	fileReader.onload = function(event)
	{
		var fileContentsAsBinaryString = event.target.result;
		var bytesCompressed = fileContentsAsBinaryString;
		var bytesCompressedAsHexadecimal = "";
		for (var i = 0; i < bytesCompressed.length; i++)
		{
			var byte = bytesCompressed.charCodeAt(i);
			var byteAsHexadecimal = byte.toString(16).padLeft("0", 2);
			bytesCompressedAsHexadecimal += byteAsHexadecimal;
		}
		var textareaCompressed = document.getElementById("textareaCompressed");
		textareaCompressed.value = bytesCompressedAsHexadecimal;
	}
	fileReader.readAsBinaryString(file);
}

// DEFLATE implementation

// Most of the code below is a port 
// of a Java implementation of DEFLATE written by Nyuki Minase.

/*(MIT License)

Copyright © 2012 Nayuki Minase
Copyright © 2017 This Could Be Better

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:

* The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

* The Software is provided "as is", without warranty of any kind, express or
  implied, including but not limited to the warranties of merchantability,
  fitness for a particular purpose and noninfringement. In no event shall the
  authors or copyright holders be liable for any claim, damages or other
  liability, whether in an action of contract, tort or otherwise, arising from,
  out of or in connection with the Software or the use or other dealings in the
  Software.

*/

// main

function Inflator()
{
	// do nothing
}
{
	Inflator.prototype.decompressBytes = function(fileContentsAsBytes)
	{	
		var input = new BitStream(fileContentsAsBytes);

		let magicNumberForGZIP = input.readInteger16LE();
		if (magicNumberForGZIP != 35615)
			throw "Invalid GZIP magic number";

		var compressionMethodCode = input.readByte();
		if (compressionMethodCode != 8)
			throw "Unsupported compression method: " + (compressionMethodCode & 0xFF);

		var flags = input.readByte();

		// Reserved flags
		if ((flags & 0xE0) != 0)
			throw "Reserved flags are set";

		// Modification time
		var mtime = input.readInteger32LE();
		if (mtime != 0)
		{
			//console.log("Last modified: " + new DateTime(1970, 1, 1).add(mtime * 1000000L));
		}
		else
		{
			console.log("Last modified: N/A");
		}

		var extraFlags = input.readByte();

		// Extra flags
		switch (extraFlags) 
		{
			case 2:   console.log("Extra flags: Maximum compression");  break;
			case 4:   console.log("Extra flags: Fastest compression");  break;
			default:  console.log("Extra flags: Unknown");  break;
		}

		// Operating system
		var osCode = input.readByte();
		var os;
		switch (osCode & 0xFF) 
		{
			case   0:  os = "FAT";             break;
			case   1:  os = "Amiga";           break;
			case   2:  os = "VMS";             break;
			case   3:  os = "Unix";            break;
			case   4:  os = "VM/CMS";          break;
			case   5:  os = "Atari TOS";       break;
			case   6:  os = "HPFS";            break;
			case   7:  os = "Macintosh";       break;
			case   8:  os = "Z-System";        break;
			case   9:  os = "CP/M";            break;
			case  10:  os = "TOPS-20";         break;
			case  11:  os = "NTFS";            break;
			case  12:  os = "QDOS";            break;
			case  13:  os = "Acorn RISCOS";    break;
			case 255:  os = "Unknown";         break;
			default :  os = "Really unknown";  break;
		}
		console.log("Operating system: " + os);

		// Text flag
		if ((flags & 0x01) != 0)
		{
			console.log("Flag: Text");
		}

		// Extra flag
		if ((flags & 0x04) != 0) 
		{
			console.log("Flag: Extra");
			var len = input.readInteger16LE();
			input.readBytes(len);  // Skip extra data
		}

		// File name flag
		if ((flags & 0x08) != 0) 
		{
			var sb = "";
			while (true) 
			{
				var temp = input.readByte();
				if (input.hasMoreBits() == false)
					throw "EOFException";
				else if (temp == 0)  // Null-terminated string
					break;
				else
					sb += String.fromCharCode(temp);
			}
			console.log("File name: " + sb);
		}

		// Header CRC flag
		if ((flags & 0x02) != 0) {
			
			var crc = input.readInteger16LE(2);
			console.log("Header CRC-16: %04X%n", crc);
		}

		// Comment flag
		if ((flags & 0x10) != 0) {
			var sb = "";
			while (true) {
				var temp = input.readByte();
				if (input.hasMoreBits() == false)
					throw "EOFException";
				else if (temp == 0)  // Null-terminated string
					break;
				else
					sb += String.fromCharCode(temp);
			}
			console.log("Comment: " + sb);
		}

		// Decompress
		var bytesDecompressed = Decompressor.decompress
		(
			input
		);

		return bytesDecompressed;
	}
}

// classes

function BitStream(bytes)
{
	this.bytes = bytes;
	this.byteIndex = 0;
	this.bitOffsetWithinByte = 0;
}
{
	BitStream.prototype.alignWithByteBoundary = function()
	{
		if (this.bitOffsetWithinByte != 0)
		{
			this.bitOffsetWithinByte = 0;
			this.byteIndex++;
		}
	}

	BitStream.prototype.hasMoreBits = function()
	{
		return (this.byteIndex < this.bytes.length);
	}

	BitStream.prototype.readBit = function()
	{
		var byteCurrent = this.bytes[this.byteIndex];
		var returnValue = (byteCurrent >> (8 - this.bitOffsetWithinByte - 1)) & 0x1;
		this.bitOffsetWithinByte++;
		if (this.bitOffsetWithinByte >= 8)
		{
			this.bitOffsetWithinByte = 0;
			this.byteIndex++;
		}
		return returnValue;
	}

	BitStream.prototype.readBits = function(numberOfBits)
	{
		var returnValues = [];	

		for (var i = 0; i < numberOfBits; i++)
		{
			var bit = this.readBit();
			returnValues.push(bit);
		}

		return returnValues;
	}

	BitStream.prototype.readByte = function()
	{
		var returnValue = this.bytes[this.byteIndex];
		this.byteIndex++;
		return returnValue;
	}

	BitStream.prototype.readBytes = function(numberOfBytes)
	{
		var returnValues = [];

		for (var i = 0; i < numberOfBytes; i++)
		{
			var byte = this.bytes[this.byteIndex];
			returnValues.push(byte);
			this.byteIndex++;
		}

		return returnValues;
	}


	BitStream.prototype.readIntegerOfBitWidthLE = function(numberOfBits)
	{
		var returnValue = 0;

		var bits = this.readBits(numberOfBits);
		for (var i = 0; i < bits.length; i++)
		{
			var bit = bits[i];
			var bitValueInPlace = bit << i;
			returnValue = returnValue | bitValueInPlace;
		}

		return returnValue;
	}

	BitStream.prototype.readInteger16LE = function()
	{
		// 16-bit, little-endian

		var bytes = this.readBytes(2);
		var returnValue = bytes[0] | (bytes[1] << 8);
		return returnValue;
	}

	BitStream.prototype.readInteger32LE = function()
	{
		// 32-bit, little-endian

		var bytes = this.readBytes(4);
		var returnValue = 
			bytes[0] 
			| (bytes[1] << 8) 
			| (bytes[2] << 16) 
			| (bytes[3] << 24);
		return returnValue;
	}

	BitStream.prototype.writeByte = function(byte)
	{
		this.bytes.push(byte);
		this.byteIndex = this.bytes.length;
	}

	BitStream.prototype.writeBytes = function(bytesToWrite)
	{
		for (var i = 0; i < bytesToWrite.length; i++)
		{
			var byte = bytesToWrite[i];
			this.bytes.push(byte);
		}
		this.byteIndex = this.bytes.length;
	}
}

function CanonicalCode(codeLengths)
{

	if (codeLengths == null)
	{
		throw "Argument is null";
	}

	this.codeLengths = codeLengths.slice(0);
	for (var i = 0; i < codeLengths.length; i++) 
	{
		var x = codeLengths[i];
		if (x < 0)
		{
			throw "Illegal code length";
		}
	}
}
{
	// static classes 

	CanonicalCode.constructor2 = function(tree, symbolLimit) 
	{
		var codeLengths = new Array(symbolLimit);
		var returnValue = new CanonicalCode(codeLengths);
		returnValue.buildCodeLengths(tree.root, 0);
	}

	CanonicalCode.prototype.buildCodeLengths = function(node, depth) 
	{
		if (node.constructor.name == "InternalNode") 
		{
			var internalNode = node;
			this.buildCodeLengths(internalNode.leftChild , depth + 1);
			this.buildCodeLengths(internalNode.rightChild, depth + 1);
		} 
		else if (node.constructor.name == "Leaf") 
		{
			var symbol = node.symbol;
			if (codeLengths[symbol] != 0)
			{
				throw "Symbol has more than one code"; 
			}
			if (symbol >= codeLengths.length)
			{
				throw "Symbol exceeds symbol limit";
			}
			this.codeLengths[symbol] = depth;
		} 
		else 
		{
			throw "Illegal node type";
		}
	}

	CanonicalCode.prototype.getSymbolLimit = function() 
	{
		return this.codeLengths.length;
	}

	CanonicalCode.prototype.getCodeLength = function(symbol) 
	{
		if (symbol < 0 || symbol >= this.codeLengths.length)
		{
			throw "Symbol out of range";
		}
		return this.codeLengths[symbol];
	}

	CanonicalCode.prototype.toCodeTree = function() 
	{
		var nodes = [];
		for (var i = this.max(this.codeLengths); i >= 1; i--) 
		{  
			// Descend through positive code lengths
			var newNodes = [];

			// Add leaves for symbols with code length i
			for (var j = 0; j < this.codeLengths.length; j++) {
				if (this.codeLengths[j] == i)
					newNodes.push(new Leaf(j));
			}

			// Merge nodes from the previous deeper layer
			for (var j = 0; j < nodes.length; j += 2)
			{
				newNodes.push(new InternalNode(nodes[j], nodes[j + 1]));
			}

			nodes = newNodes;
			if (nodes.length % 2 != 0)
			{
				throw "This canonical code does not represent a Huffman code tree";
			}
		}

		if (nodes.length != 2)
		{
			throw "This canonical code does not represent a Huffman code tree";
		}
		return new CodeTree(new InternalNode(nodes[0], nodes[1]), this.codeLengths.length);
	}

	CanonicalCode.prototype.max = function(array) 
	{
		var result = array[0];
		for (var i = 0; i < array.length; i++)
		{
			var x = array[i];
			result = Math.max(x, result);
		}
		return result;
	}	
}

function CircularDictionary(size)
{
	this.data = new Array(size);
	this.index = 0;

	if (IntegerMath.isPowerOf2(size))
	{
		this.mask = size - 1;
	}
	else
	{
		this.mask = 0;
	}
}
{
	CircularDictionary.prototype.append = function(b) 
	{
		this.data[this.index] = b;
		if (this.mask != 0)
			this.index = (this.index + 1) & this.mask;
		else
			this.index = (this.index + 1) % this.data.length;
	}

	CircularDictionary.prototype.copy = function(dist, len, out)
	{
		if (len < 0 || dist < 1 || dist > this.data.length)
		{
			throw "IllegalArgumentException";
		}

		if (this.mask != 0) 
		{
			var readIndex = (this.index - dist + this.data.length) & this.mask;
			for (var i = 0; i < len; i++) 
			{
				out.write(this.data[readIndex]);
				this.data[this.index] = this.data[readIndex];
				readIndex = (readIndex + 1) & this.mask;
				this.index = (this.index + 1) & this.mask;
			}
		} 
		else 
		{
			var readIndex = (this.index - dist + this.data.length) % this.data.length;
			for (var i = 0; i < len; i++) 
			{
				out.write(this.data[readIndex]);
				this.data[this.index] = this.data[readIndex];
				readIndex = (readIndex + 1) % this.data.length;
				this.index = (this.index + 1) % this.data.length;
			}
		}
	}	
}

function CodeTree(root, symbolLimit)
{
	// public final InternalNode root;  // Not null

	// Stores the code for each symbol, or null if the symbol has no code.
	// For example, if symbol 5 has code 10011, then codes.get(5) is the list [1, 0, 0, 1, 1].
	// private List<List<Integer>> codes;

	// Every symbol in the tree 'root' must be strictly less than 'symbolLimit'.

	if (root == null)
	{
		throw "Argument is null";
	}
	this.root = root;

	this.codes = [];  // Initially all null
	for (var i = 0; i < symbolLimit; i++)
	{
		this.codes.push(null);
	}

	this.buildCodeList(root, []);  // Fills 'codes' with appropriate data
}
{
	CodeTree.prototype.buildCodeList = function(node, prefix) 
	{
		var nodeConstructorName = node.constructor.name;
		if (nodeConstructorName == "InternalNode") 
		{
			var internalNode = node;

			prefix.push(0);
			this.buildCodeList(internalNode.leftChild , prefix);
			prefix.removeAt(prefix.length - 1);

			prefix.push(1);
			this.buildCodeList(internalNode.rightChild, prefix);
			prefix.removeAt(prefix.length - 1);	
		} 
		else if (nodeConstructorName == "Leaf") 
		{
			var leaf = node;
			if (leaf.symbol >= this.codes.length)
			{
				throw "Symbol exceeds symbol limit";
			}
			if (this.codes[leaf.symbol] != null)
			{
				throw "Symbol has more than one code";
			}
			this.codes[leaf.symbol] = new Array(prefix); // ?
		} 
		else 
		{
			throw "Illegal node type";
		}
	}

	CodeTree.prototype.getCode = function(symbol) 
	{
		if (symbol < 0)
		{
			throw new "Illegal symbol";
		}
		else if (this.codes[symbol] == null)
		{
			throw "No code for given symbol";
		}
		else
		{
			return this.codes[symbol];
		}
	}

	// Returns a string showing all the codes in this tree. The format is subject to change. Useful for debugging.
	CodeTree.prototype.toString = function() 
	{
		var sb = "";
		sb = this.toString2("", root, sb);
		return sb;
	}

	CodeTree.prototype.toString2 = function(prefix, node, sb) 
	{
		var nodeConstructorName = node.constructor.name;
		if (nodeConstructorName == "InternalNode") 
		{
			var internalNode = node;
			sb = this.toString2(prefix + "0", internalNode.leftChild , sb);
			sb = this.toString2(prefix + "1", internalNode.rightChild, sb);
		} 
		else if (nodeConstructorName == "Leaf") 
		{
			sb += String.format("Code %s: Symbol %d%n", prefix, node.symbol);
		} 
		else 
		{
			throw "Illegal node type";
		}

		return sb;
	}	
}

function InternalNode(leftChild, rightChild)
{
	if (leftChild == null || rightChild == null)
	{
		throw "Argument is null";
	}
	this.leftChild = leftChild;
	this.rightChild = rightChild;
}

function Leaf(symbol)
{	
	if (symbol < 0)
		throw "Illegal symbol value";
	this.symbol = symbol;
}

function Decompressor(input)
{
	// These were formerly static variables.

	var llcodelens = new Array(288);
	llcodelens.fill(8, 0, 144);
	llcodelens.fill(9, 144, 256);
	llcodelens.fill(7, 256, 280);
	llcodelens.fill(8, 280, 288);
	this.llcodelens = llcodelens;

	this.fixedLiteralLengthCode = new CanonicalCode(llcodelens).toCodeTree();
	this.distcodelens = new Array(32);

	this.distcodelens.fill(5);
	this.fixedDistanceCode = new CanonicalCode(this.distcodelens).toCodeTree();

	// The original constructor picks up here.

	this.input = input;
	this.output = new BitStream([]);
	this.dictionary = new CircularDictionary(32 * 1024);

	// Process the stream of blocks
	while (true) 
	{
		// Block header
		var isFinal = (input.readBit() == 1);  // bfinal
		var type = input.readIntegerOfBitWidthLE(2); // btype

		// Decompress by type
		if (type == 0)
		{
			this.decompressUncompressedBlock();
		}
		else if (type == 1 || type == 2) 
		{
			var litLenCode, distCode;
			if (type == 1) 
			{
				litLenCode = this.fixedLiteralLengthCode;
				distCode = this.fixedDistanceCode;
			} 
			else 
			{
				var temp = this.decodeHuffmanCodes(input);
				litLenCode = temp[0];
				distCode = temp[1];
			}

			this.decompressHuffmanBlock(litLenCode, distCode);	
		} 
		else if (type == 3)
		{
			throw "Invalid block type";
		}
		else
		{
			throw "AssertionError";
		}

		if (isFinal)
		{
			break;
		}
	}
}
{	
	// static methods

	/* Public method */
	Decompressor.decompress = function(input)
	{
		var decompressor = new Decompressor(input);
		return decompressor.output.bytes;
	}

	// For handling static Huffman codes (btype = 1)
	Decompressor.fixedLiteralLengthCode = null; // todo
	Decompressor.fixedDistanceCode = null; // todo

	// For handling dynamic Huffman codes (btype = 2)
	Decompressor.prototype.decodeHuffmanCodes = function(input)
	{
		var numLitLenCodes = input.readIntegerOfBitWidthLE(5) + 257;  // hlit  + 257
		var numDistCodes = input.readIntegerOfBitWidthLE(5) + 1;      // hdist +   1

		var numCodeLenCodes = input.readIntegerOfBitWidthLE(4) + 4;   // hclen +   4
		var codeLenCodeLen = new Array(19);
		codeLenCodeLen[16] = input.readIntegerOfBitWidthLE(3);
		codeLenCodeLen[17] = input.readIntegerOfBitWidthLE(3);
		codeLenCodeLen[18] = input.readIntegerOfBitWidthLE(3);
		codeLenCodeLen[ 0] = input.readIntegerOfBitWidthLE(3);
		for (var i = 0; i < numCodeLenCodes - 4; i++) 
		{
			if (i % 2 == 0)
				codeLenCodeLen[8 + i / 2] = input.readIntegerOfBitWidthLE(3);
			else
				codeLenCodeLen[7 - i / 2] = input.readIntegerOfBitWidthLE(3);
		}
		var codeLenCode = new CanonicalCode(codeLenCodeLen).toCodeTree();

		var codeLens = new Array(numLitLenCodes + numDistCodes);
		var runVal = -1;
		var runLen = 0;
		for (var i = 0; i < codeLens.length; i++) 
		{
			if (runLen > 0) 
			{
				codeLens[i] = runVal;
				runLen--;	
			} 
			else 
			{
				var sym = this.decodeSymbol(codeLenCode);
				if (sym < 16) 
				{
					codeLens[i] = sym;
					runVal = sym;
				} 
				else 
				{
					if (sym == 16) 
					{
						if (runVal == -1)
						{
							throw "No code length value to copy";
						}
						runLen = input.readIntegerOfBitWidthLE(2) + 3;
					} 
					else if (sym == 17) 
					{
						runVal = 0;
						runLen = input.readIntegerOfBitWidthLE(3) + 3;
					} 
					else if (sym == 18) 
					{
						runVal = 0;
						runLen = input.readIntegerOfBitWidthLE(7) + 11;
					} 
					else
					{
						throw "AssertionError";
					}

					i--;
				}
			}
		}
		if (runLen > 0)
		{
			throw "Run exceeds number of codes";
		}

		// Create code trees
		var litLenCodeLen = codeLens.slice(0, numLitLenCodes); // ?
		var litLenCode = new CanonicalCode(litLenCodeLen).toCodeTree();

		var distCodeLen = codeLens.slice(numLitLenCodes, codeLens.length); // ?
		var distCode;
		if (distCodeLen.length == 1 && distCodeLen[0] == 0)
		{
			distCode = null;  // Empty distance code; the block shall be all literal symbols
		}
		else
		{
			distCode = new CanonicalCode(distCodeLen).toCodeTree();
		}

		return [litLenCode, distCode];
	}

	/* Block decompression methods */

	Decompressor.prototype.decompressUncompressedBlock = function()
	{
		// Discard bits to align to byte boundary
		this.input.alignWithByteBoundary();

		// Read length
		var len  = this.input.readInteger16LE();
		var nlen = this.input.readInteger16LE();
		var nlenCalculated = len ^ 0xFFFF; 
		if (nlenCalculated != nlen) 
		{
			throw "Invalid length in uncompressed block";
		}

		// Copy bytes
		for (var i = 0; i < len; i++) 
		{
			var temp = this.input.readByte();
			if (this.input.hasMoreBits() == false)
			{
				throw "EOFException";
			}
			this.output.writeByte(temp);
			this.dictionary.append(temp);
		}
	}

	Decompressor.prototype.decompressHuffmanBlock = function(litLenCode, distCode)
	{
		if (litLenCode == null)
		{
			throw "NullPointerException";
		}

		while (true) 
		{
			var sym = this.decodeSymbol(litLenCode);
			if (sym == 256)  // End of block
			{
				break;
			}

			if (sym < 256) 
			{  
				// Literal byte

				// Leaving the next line in
				// causes strange junk to appear 
				// at the end of the uncompressed data.
				// Not sure what's going on.
				//this.output.writeByte(sym);

				this.dictionary.append(sym);
			} 
			else 
			{  // Length and distance for copying
				var len = this.decodeRunLength(sym);
				if (distCode == null)
				{
					throw "Length symbol encountered with empty distance code";
				}
				var distSym = this.decodeSymbol(distCode);
				var dist = this.decodeDistance(distSym);
				this.dictionary.copy(dist, len, output);
			}
		}
	}

	/* Symbol decoding methods */
	Decompressor.prototype.decodeSymbol = function(code)
	{
		var currentNode = code.root;
		while (true) 
		{
			var temp = this.input.readBit();
			var nextNode;
			if (temp == 0)
			{			
				nextNode = currentNode.leftChild;
			}
			else if (temp == 1)
			{
				nextNode = currentNode.rightChild;
			}
			else
			{
				throw "AssertionError";
			}

			var nextNodeConstructorName = nextNode.constructor.name;
			if (nextNodeConstructorName == "Leaf")
			{
				return nextNode.symbol;
			}
			else if (nextNodeConstructorName == "InternalNode")
			{
				currentNode = nextNode;
			}
			else
			{
				throw "AssertionError";
			}
		}
	}

	Decompressor.prototype.decodeRunLength = function(sym)
	{
		if (sym < 257 || sym > 285)
		{
			throw "Invalid run length symbol: " + sym;
		}
		else if (sym <= 264)
		{
			return sym - 254;
		}
		else if (sym <= 284) 
		{
			var i = (sym - 261) / 4;  // Number of extra bits to read
			return (((sym - 265) % 4 + 4) << i) + 3 + input.readIntegerOfBitWidthLE(i);
		} 
		else  // sym == 285
		{
			return 258;
		}
	}

	Decompressor.prototype.decodeDistance = function(sym)
	{
		if (sym <= 3)
		{
			return sym + 1;
		}
		else if (sym <= 29) 
		{
			var i = sym / 2 - 1;  // Number of extra bits to read
			return ((sym % 2 + 2) << i) + 1 + input.readIntegerOfBitWidthLE(i);
		} 
		else
		{
			throw "Invalid distance symbol: " + sym;
		}
	}
}

function IntegerMath()
{
	// static class
}
{
	IntegerMath.isPowerOf2 = function(valueToCheck)
	{
		return ((Math.log(valueToCheck) / Math.log(2)) % 0) == 0;
	}
}

</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s