Inflate动态Huffman解压缩

上个已经实现GZIP压缩文件格式的Inflate静态Huffman解压，这个实现Inflate的无压缩输出和动态Huffman解压。

Java语言实现，Eclipse下编写。

范式Huffman解码实现，输入huffman编码，输出原始数据

    // 范式huffman解码
	static class CanonicalCode {
		Vector<Node> table = new Vector<>();
		
		public CanonicalCode(int[] len) {
			for (int i=0; i<len.length; i++)
				if (len[i] != 0) // 过滤0-即不使用的节点
					table.add( new Node(i, len[i]) ); // value, bits Length (值, 待编码的编码长度)
			
			// 按编码长度+值排序
			Collections.sort(table, new Comparator<>() {
				@Override
				public int compare(Node o1, Node o2) {
					return o1.bitLen!=o2.bitLen ? o1.bitLen-o2.bitLen : o1.value - o2.value;
				}
			});
			
			// 初始化第一个节点，实现规则1
			table.get(0).code = 1 << table.get(0).bitLen;
			
			// 计算每一个值得huffman编码
			for (int i=1; i<table.size(); i++) {
				Node node = table.get(i);
				Node prev = table.get(i-1);
				
				if (node.bitLen == prev.bitLen)  // 如果位长相等+1，实现规则2
					node.code = prev.code + 1;
				else if (node.bitLen > prev.bitLen)	// 位长不等，实现规则3
					node.code = ( prev.code + 1) << (node.bitLen - prev.bitLen);  // 左移'位长差'
			}
		}
		
		// 打印符号和huffman码的对应关系
		void debug() {
			for (int i=0; i<table.size(); i++) {
				Node n = table.get(i);
				System.out.println( n);
			}
		}
		
		// 根据传入的huffman编码，得到原始数值
		Integer findValue(int code) {
			for (Node node : table)
				if (node.code == code)
					return node.value;
			return null;
		}
	}

无压缩数据解码：

	bis.alignByte(); // 对齐字节边界
	
	int len = bis.ReadBits(16);
	int nlen = bis.ReadBits(16);
	assert len + nlen == 65535;
	
	for (int i=0; i<len; i++) {
		baos.Write(bis.ReadBits(8));
	}

动态huffman解码：

	else if (bType == 2) { // dynamic huffman
		// length有29个
		int hlit = bis.ReadBits(5);  // CL1数量 - 字/长度 码个数, LIT(literal/length)
		// distance码有30个
		int hdist = bis.ReadBits(5); // CL2数量 - 距离 码个数, DIST(distance)
		int hclen = bis.ReadBits(4); // c_len:code lengths for the code length
		
		int cl1_num = hlit + 257;  // CL1(Code Length 1): 'literal/length' length (literal[0..255]+压缩块结束[256] = 257)
		int cl2_num = hdist + 1;   // CL2(Code Length 2): 'distance code' length
		int ccl_num = hclen + 4;   // 
		
		int[] cl1 = new int[cl1_num];
		int[] cl2 = new int[cl2_num];
		int[] ccl = new int[19]; // ccl bits
		
		// 读取CCL
		Arrays.fill(ccl, 0);
		int[] PermutationtTable = new int[] {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
		
		for (int i=0; i<ccl_num; i++) { // 读取CCL, 每个3bit
			int p = PermutationtTable[i];
			ccl[p] = bis.ReadBits(3);
		}

		// 通过CCL构建范式huffman编码
		CanonicalCode codes = new CanonicalCode(ccl);

		//读取CL1和CL2,'literal/length' Sequence 码流 + dist流
		IntBuffer sq = IntBuffer.allocate(cl1_num + cl2_num);
		int prevValue = -1, cl_decode_num = 0;

		while (cl_decode_num < cl1_num + cl2_num) {
			Integer value = null;
			int code = 1;
			
			// 范式huffman解码
			int bits = 1;
			while (value == null) {
				code = (code << 1 ) | bis.ReadBit();  // huffman编码
				value = codes.findValue( code); // 查找对应的符号
				
				if ( (bits++) > 15 )
					throw new java.lang.IllegalArgumentException();
			}
			
			// 处理value， 实现 0-15，16，17，18 这套规则
			int[] bs;
			if (value == 17) { // 标识长度
				int len = bis.ReadBits(3) + 3;
				bs = new int[len];
				Arrays.fill(bs, (byte)0);
			}
			else if (value == 18) {
				int len = bis.ReadBits(7) + 11;
				bs = new int[len];
				Arrays.fill(bs, (byte)0);
			}
			else if (value == 16) {
				int len = bis.ReadBits(2) + 3;
				bs = new int[len];
				Arrays.fill(bs, (byte) prevValue);
			}
			else if (value >=0 && value <= 15){
				bs = new int[] {  value };
				prevValue = value;
			}
			else 
				throw new java.lang.IllegalArgumentException(value + "");
			
			sq.put(bs); // 写入符号
			cl_decode_num += bs.length; // 增加已得到的码流长度
		}
		
		int[] bs = sq.array();
		// 分别得到CL1和CL2 
		System.arraycopy(bs, 0, cl1, 0, cl1.length);
		System.arraycopy(bs, cl1.length, cl2, 0, cl2.length);

		CanonicalCode code1 = new CanonicalCode(cl1); // literal/length解码器
		CanonicalCode code2 = new CanonicalCode(cl2); // distance解码器
		
		// 解码
		Integer value = null;
		do {
			// 解literal/length码
			int code = 1;
			do {
				code = (code << 1) | bis.ReadBit(); // 读取Huffman code
				value = code1.findValue(code);
			} while (value == null);
			
			// 判断
			if (value >= 0 && value <= 255)// literal
				baos.Write(value);
			else if (value == 256) // 结束标志
				break ;
			else if (value >= 257 && value <= 285) { // length
				// 处理长度
				int length = LengthExtraCodeLengthsTable.get(value);
				int bits = LengthExtraCodeBitsTable.get(value); // 扩展bit长
				
				if (bits != 0) {
					int ext =  ReadExtCode(bis, bits);
					length = length + ext;
				}
				
				// 读取huffman编码
				code = 1;
				do {
					code = (code << 1) | bis.ReadBit(); // 读取Huffman code
					value = code2.findValue(code);
				} while (value == null);
				
				// 处理距离
				int distance = DistanceExtraCodeLengthsTable.get(value);
				bits = DistanceExtraCodeBitsTable.get(value); // 距离扩展
				if (bits != 0) {
					int ext =ReadExtCode(bis , bits);
					distance = distance + ext;
				}

				// LZ77滑动窗口计算获取量
				int[] arr = baos.GetInts();
				int d = arr.length - distance;
				if (d < 0) {
					d = 0;
					length = length + distance - arr.length;
				}
				
				// 读取滑动窗口，写入到结果
				for (int i=0; i<length; i++) {
					int m = arr[ d + i];
					
					baos.Write(m);
					arr = baos.GetInts();
				}

			}
		} while (value != 256);
	}

输出结果：

对待压缩文件sample-5.svg 计算md5值，得到：84018a59da62b5af9de4c0843ce5d0b6

使用gzip对文件压缩

使用Java程序对压缩后的文件sample-5.svg.gz解压缩，得到sample.svg

对解压后的文件计算md5值，得到84018a59da62b5af9de4c0843ce5d0b6

解压前文件的md5值==解压后的文件的md5值。