class1.jsl

Bitmap 文件的压缩和解压缩

import java.io.*; 
import java.util.LinkedList; 

/** 
 * Compression or Decompression with Lempel-Ziv. 
 * 
 * Compression: java LempelZiv < INPUTFILE > OUTPUTFILE 
 *        e.g.: java LempelZiv < x.bmp > x.ziv 
 * 
 * Decompression: java LempelZiv -x < INPUTFILE > OUTPUTFILE 
 *          e.g.: java LempelZiv -x < x.ziv > x.bmp 
 */ 
public class LempelZiv 
{ 

	/* 
	 * To optimize the compression you can change MAX_NODES as follows:. 
	 * 0x0000007F-0x00000003: replace "short" in all three classes to "byte". 
	 * 0x00007FFF-0x00000080: let all "short"-phrases. 
	 * 0x7FFFFFFF-0x00008000: replace "short" in all three classes to "int". 
	 */ 
	private static final int MAX_NODES = 0x00007FFF; // or 32767 

	/* 
	 * The Lempel-Ziv algorithm 'zip'. 
	 */ 
	private static void lempelZivCompress (DataInputStream input, 
		DataOutputStream output) throws IOException 
	{ 

		// to structure the bit stream to a node tree 
		LempelZivTree tree = new LempelZivTree(MAX_NODES); 

		// saves the maximum of possible nodes 
		output.writeInt(MAX_NODES); 

		// all bits of input stream will be added to node tree 
		while (input.available() > 0) 
		{ 

			byte eightBits = input.readByte(); 

			// all bits of a byte will be added to node tree 
			for (int i = 7; i >= 0; i--) 
			{ 

				byte oneBit = (byte)((eightBits >> i) & (0x01)); 

				if (tree.addBit(oneBit)) 
				{ 
					// to save the current bit-node pair = (bit, id) 
					short pair = tree.getPair(); 
					output.writeShort(pair); 
				} 
			} 
		} 

		// if the last pair is uncomplete 
		// save the last uncomplete, neg. pair 
		// and terminate with '0' 
		if (tree.needTerminator()) 
		{ 
			short pair = tree.getPair(); 
			output.writeShort(pair); 
			output.writeShort(0x0000); 
		} 
	} // end of lempelZivCompress 

	/* 
	 * The Lempel-Ziv algorithm 'unzip'. 
	 */ 
	private static void lempelZivDecompress (DataInputStream input, 
		DataOutputStream output) throws IOException 
	{ 

		if (input.available() <= 4) 
		{ 
			// no output! 
			return; 
		} 

		int maxNodes = input.readInt(); 

		// to structure the bit stream to a node table 
		LempelZivTable table = new LempelZivTable(maxNodes); 

		LinkedList bits = new LinkedList(); 

		while (input.available() >= 3 * 2) 
		{ // 3 * 2 = 3 * size(short) 

			short pair = input.readShort(); 
			bits = table.getBitsOfPair(pair, bits); 
			writeBits(bits, output); 
		} 

		if (input.available() == 2 * 2) 
		{ 
			// the last 2 short values now! 
			short pairOrNode = input.readShort(); 
			short pairOrZero = input.readShort(); 

			if (pairOrZero == 0) 
			{ 
				// last pair is uncomplete 
				bits = table.getBitsOfNode(-pairOrNode, bits); 
				writeBits(bits, output); 
			} 
			else 
			{ 
				// last two pairs are complete 
				bits = table.getBitsOfPair(pairOrNode, bits); 
				writeBits(bits, output); 
				bits = table.getBitsOfPair(pairOrZero, bits); 
				writeBits(bits, output); 
			} 
		} 

	} // end of lempelZivDecompress 

	/* 
	 * Writes the given bits to the output as bytes and 
	 * removes the written bits from the given bit list. 
	 * The given bit list will contains a number of bits 
	 * lower than '8'. 
	 */ 
	private static void writeBits(LinkedList bits, DataOutputStream output) 
		throws IOException 
	{ 

		byte eightBits = 0x00; 
		byte bitsCount = 0; 

		while (bits.size() >= 8 - bitsCount) 
		{ 

			eightBits = (byte)(eightBits << 1); 

			if (((Boolean)bits.removeFirst()).booleanValue()) 
			{ 
				eightBits = (byte)(eightBits | 0x01); 
			} 

			bitsCount++; 

			if (bitsCount >= 8) 
			{ 

				output.writeByte((byte)eightBits); 

				eightBits = 0x00; 
				bitsCount = 0; 
			} 
		} 

	} // end of writeBits 

	/** 
	 * The main program which realizes the compress or decompress with the 
	 * Lempel-Ziv algorithms <u><i>zip</i></u> and <u><i>unzip</i></u>. 
	 * @param args the parameters of command line of system. 
	 *        Use the parameter <code>-x</code> to decompress the input stream. 
	 * @throws IOException if it happens by using in- or out-streams. 
	 */ 
	public static void main (String[] args) throws IOException 
	{ 

		BufferedInputStream bufferedInput = new BufferedInputStream(System.in); 
		BufferedOutputStream bufferedOutput = new BufferedOutputStream(System.out); 

		DataInputStream input = new DataInputStream(bufferedInput); 
		DataOutputStream output = new DataOutputStream(bufferedOutput); 

		boolean compress = true; 

		// searches for '-x' in argument list. 
		for (int i = 0; i < args.length; i++) 
		{ 

			if (args[i].equals("-x")) 
			{ 
				compress = false; 
				break; 
			} 
		} 

		if (compress) 
		{ 
			lempelZivCompress(input, output); 
		} 
		else 
		{ 
			lempelZivDecompress(input, output); 
		} 

		output.close(); 
		input.close(); 

	} // end of main 
} // end of public class LempelZiv

	/** 
	 * This class is only for Lempel-Ziv compression. 
	 */ 
public class LempelZivTree 
{ 

	/* maximum of nodes */ 
	private int maxNodes; 

	/* the root of nodes tree */ 
	private Node root; 

	/* identity of current node */ 
	private int currentId; 

	/* the current node (is never null) */ 
	private Node currentNode; 

	/* the last node (null if uncomplete pair) */ 
	private Node lastNode; 

	/* the last bit of last node */ 
	private byte lastBit; 

	/** 
	 * Instantiates the <code>LempelZivTree</code> object. 
	 * @param maxNodes the maximum of nodes. 
	 */ 
	public LempelZivTree (int maxNodes) 
	{ 

		this.maxNodes = maxNodes; 

		this.currentId = 1; 

		this.root = new Node(this.currentId); 
		this.currentNode = this.root; 

		this.lastNode = null; 
		this.lastBit = 0x00; 

	} // end of constructor LempelZipTree 

	/** 
	 * Adds a bit to the internal tree. 
	 * @param oneBit the bit. 
	 * @return <code>true</code> if pair is complete with given bit, 
	 *         <code>false</code> otherwise. 
	 */ 
	public boolean addBit (byte oneBit) 
	{ 

		// actualize the node references 
		this.lastNode = this.currentNode; 
		this.currentNode = this.lastNode.children[oneBit]; 

		// store the given bit 
		this.lastBit = oneBit; 

		if (this.currentNode == null) 
		{ 

			// creates a new node if the maximum of nodes 
			// is not reached 
			if (this.maxNodes > this.currentId) 
			{ 
				this.currentId++; 
				this.currentNode = new Node(this.currentId); 
				this.lastNode.children[oneBit] = this.currentNode; 
			} 

			this.currentNode = this.root; 

			// save pair with getPair 
			return true; 

		} 
		else 
		{ 

			this.lastNode = null; 

			// do not save pair 
			return false; 
		} 

	} // end of addBit 

	/** 
	 * Returns a complete of uncomplete pair. 
	 * @return complete pair 
	 *         if last <code>addBit</code> operation was <code>true</code>; 
	 *         uncomplete pair 
	 *         if last <code>addBit</code> operation was <code>false</code>. 
	 */ 
	public short getPair () 
	{ 

		short result; 

		// chooses the right pair 
		if (this.lastNode == null) 
		{ 

			// returns the uncomplete, negative pair = (-id) 
			result = (short)this.currentNode.id; 
			result *= -1; 

		} 
		else 
		{ 

			// returns the complete pair = (bit, id) 
			result = (short)this.lastNode.id; 

			// the bit is the sign of node 
			if (this.lastBit == 0x01) 
			{ 
				result *= -1; 
			} 
		} 

		return result; 
	} 

	/** 
	 * Returns whether the compress algorithm need a special termination: 
	 * negative node and '0'.<br> 
	 * <u>Use it, if you adds all bits with <code>addBit</code> operation</u>. 
	 * @return <code>true</code> if the output stream needs 
	 *         special termination (because of uncomplete pair), 
	 *         <code>false</code> otherwise. 
	 */ 
	public boolean needTerminator () 
	{ 

		// true if the pair is uncomplete 
		return this.lastNode == null; 
	} 

	/* Node for the tree of nodes */ 
	private class Node 
	{ 

		/* identity of node */ 
		private int id; 

		/* the next two nodes */ 
		private Node[] children; 

		/* instantiates a node */ 
		private Node (int id) 
		{ 

			this.id = id; 

			// use it, with ...children[aBit] 
			this.children = new Node[2]; 

		} // end of contructor Node 
	} // end of private class Node 
} // end of public class LempelZivTree