Skip to content

Instantly share code, notes, and snippets.

@Hafthor

Hafthor/SlowInflate.java

Last active November 11, 2021 21:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Hafthor/36ed5e6f298c29f2489c6af5f6bd53de to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Hafthor/36ed5e6f298c29f2489c6af5f6bd53de to your computer and use it in GitHub Desktop.
Download ZIP
Slow implementation of Inflate decompression with examples and explanations (zlib ~3x faster)
Raw
SlowInflate.java
package com.hafthor;
import java.util.Arrays;
public class SlowInflate {
public static void main(final String[] args) {
fixed();
fixedBetter();
dynamic();
stored();
}
private static void fixed() {
// echo -n "abcabcabcabc"|gzip -9|hexdump -C
// 00000000 1f 8b 08 00 13 08 59 61 02 03 4b 4c 4a 4e 84 21
// 00000010 00 34 2a 6e 5a 0c 00 00 00
// first 10 bytes are gzip header (see RFC 1952)
// last 10 bytes are gzip footer
// here's the meat of the deflated stream
// 4b 4c 4a 4e 84 21 00
// deflate sees this as a stream of bits in lsb-first order, which is a little weird, tbh
// so 4b 4c isn't 01001011 01001100 but 11010010 00110010
// here's the whole stream in byte-bit-reverse
// 4b 4c 4a 4e 84 21 00
// 11010010_00110010_01010010_01110010_00100001_10000100_00000000
// |\/\_______/\_______/\_______/\_______/\______/\___/\______/\/
// BFINAL=1_// \ / _______/ / \ \ \ \_ two slack bits
// BTYPE=10_/ \ / / ______________/ \___ \ \__ 0_000000=0+256=block end
// literal 'a' _______/./././..10010_001=0x91 -0x30=0x61 'a' \ \
// literal 'b' ________/././...10010_010=0x93 -0x30=0x62 'b' \ \
// literal 'c' _________/./....10010_011=0x93 -0x30=0x63 'c' / /
// literal 'a' __________/.....10010_001=0x91 -0x30=0x61 'a' / /
// length 00001_10=6+256=262 =0 extra bits, len=8___________/ \_distance 00010 =0 extra bits, dist=3
final byte[] output = new byte[12];
final byte[] input = new byte[]{0x4b, 0x4c, 0x4a, 0x4e, (byte) 0x84, 0x21, 0x00};
final var infl = new SlowInflate(input, output);
infl.inflate();
for (int i = 0; i < infl.outputPos; i++) System.out.printf("%02x ", output[i]);
System.out.println(" \"" + new String(output, 0, infl.outputPos) + "\"");
}
private static void fixedBetter() {
// but wait! We can do better by dropping the second 'a' literal and making the
// back-reference copy one more byte.
// 4b 4c 4a 86 23 00
// 11010010_00110010_01010010_01100001_11000100_00000000
// |\/\_______/\_______/\_______/\______/\___/\______/\/
// BFINAL=1_// \ / _______/ \ \_____ \ \_ two slack bits
// BTYPE=10_/ \ / / \________ \ \__ 0_000000=0+256=block end
// literal 'a' _______/././..10010_001=0x91 -0x30=0x61 'a'\ \
// literal 'b' ________/./...10010_010=0x92 -0x30=0x62 'b' \ \
// literal 'c' _________/....10010_011=0x93 -0x30=0x63 'c' / /
// length 00001_11=7+256=263 =0x, len=9___________________/ \_distance 00010 =0x, dist=3
final byte[] output = new byte[12];
final byte[] input = new byte[]{0x4b, 0x4c, 0x4a, (byte) 0x86, 0x23, 0x00};
var infl = new SlowInflate(input, output);
infl.inflate();
for (int i = 0; i < infl.outputPos; i++) System.out.printf("%02x ", output[i]);
System.out.println(" \"" + new String(output, 0, infl.outputPos) + "\"");
// FAQ
// Q: Why didn't gzip -9 do this?
// A: Not sure, but my guess is that a back-reference to position 0 might break some
// bad implementations of decompressors.
// Q: Would that really work if I plugged that into the gzip stream?
// A: Yes. echo -n 1f 8b 08 00 30 0a 59 61 02 03 4b 4c 4a 86 23 00 34 2a 6e 5a 0c 00 00 00 |xxd -p -r|gunzip
// Q: I plugged this into a byte buffer and tried to use Java's built-in Inflater and
// it didn't work.
// A: Java expects two zlib bytes at the beginning. 0x78 0x9C should work.
// ref: https://stackoverflow.com/a/17176881 and RFC 1950.
}
private static void dynamic() {
// echo -n "3.141592653589793238462643383"|gzip|hexdump -C|pbcopy
// echo -n "3.141592653589793238462643383"|grep -o .|sort|uniq -c|sort
// 1x .7 2x 1 3x 245689 7x 3 0x 0
final byte[] output = new byte[29];
final byte[] input = decodeHexdump(
"00000000 1f 8b 08 00 26 01 5f 61 00 03 05 c1 81 0d 00 30 |....&._a.......0|\n" +
"00000010 08 c3 b0 8f 26 d1 94 02 ff 3f 36 9b 57 ae 3e a5 |....&....?6.W.>.|\n" +
"00000020 e9 bd 39 c4 3a 8a 61 f9 c5 2f ea c6 1d 00 00 00 |..9.:.a../......|\n" +
"00000030\n"
);
// first 10 bytes are gzip header 1f 8b 08 00 26 01 5f 61 00 03
// last 8 bytes are gzip footer c5 2f ea c6 1d 00 00 00
// deflate stream content is 30 bytes or 240 bits
// 05 c1 81 0d 00 30 08 c3 b0 8f 26 d1 94 02 ff 3f 36 9b 57 ae 3e a5 e9 bd 39 c4 3a 8a 61 f9
// pos len description
// --- --- -----------------------------------------------------
// 0 1 BFINAL=1 - last block
// 1 2 BTYPE=10 - dynamic huffman block
// 3 14 dynamic header - HLIT=0 HDIST=1 HCLEN=14
// 17 42 HC 14x3b huffman code lengths for code length dictionary
// 16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15 <- code length dictionary order
// 0 0 3 3 0 0 0 0 0 3 0 2 0 3 0 3 0 3 which makes
// code length dictionary (0 through 18) = 3 3 3 3 2 3 0 0 0 0 0 0 0 0 0 0 0 0 3
// which makes huffman tree of 00=4, 010=0, 011=1, 100=2, 101=3, 110=5, 111=18
// 71 64* literal/length code lengths for codes 0 to and including 256+HLIT(0).
// 71 10 18 + 7 bits - skip to 35+11 = 46
// 81 3 5 - 5 bits for '.' (char 46)
// 84 3 0 - skip '/' (char 47)
// 87 3 0 - skip '0' (char 48)- it's not used in those first 28 digits of pi
// 90 13 4 - 4 bits for '1', 3 for '2', 2 for '3', 3 for '4', 4 for '5'
// 103 9 3 - 3 bits for '6', 4 for '7', 4 for '8', 4 for '9' (char 57)
// 112 10 18 + 7 bits(127) = skip 127+11 to from char 58 to 196
// 122 10 18 + 7 bits(49) = skip 49+11 from char 196 to code 256
// 132 3 5 - 5 bits for 256, makes a huffman tree of
// 00=51 '3' 010=50 '2' 011=52 '4' 100=54 '6' 1010=49 '1' 1011=53 '5'
// 1100=55 '7' 1101=56 '8' 1110=57 '9' 11110=46 '.' 11111=256 (end of block)
// 135 6* distance code lengths for HDIST+1 codes (but not used since there are no length codes defined)
// 135 3 011 - 1 bit for 0, distance 1
// 138 3 011 - 1 bit for 1, distance 2
// 141 99* codes for content (which was 232 bits worth of data) + end code (256)
// 141 2 00 = '3'
// 143 5 11110 = '.'
// 148 4 1010 = '1'
// ...
// 235 5 11111 = 256 (eof of block)
// 240 end of stream (zero slack bits)
//
// Q: Why did we have distance codes when we can't use them?
// A: Not sure, but perhaps it is to protect against bad implementations of decompressors.
// Note that removing them would only save 6 bits and 0 actual bytes in this case.
var infl = new SlowInflate(input, output);
infl.inflate();
for (int i = 0; i < infl.outputPos; i++) System.out.printf("%02x ", output[i]);
System.out.println(" \"" + new String(output, 0, infl.outputPos) + "\"");
}
private static void stored() {
// echo -n "3.141592653589793238462643383"|gzip|gzip|hexdump -C|pbcopy
final byte[] output = new byte[48];
final byte[] input = decodeHexdump(
"00000000 1f 8b 08 00 2d 25 5f 61 00 03 01 30 00 cf ff 1f |....-%_a...0....|\n" +
"00000010 8b 08 00 2d 25 5f 61 00 03 05 c1 81 0d 00 30 08 |...-%_a.......0.|\n" +
"00000020 c3 b0 8f 26 d1 94 02 ff 3f 36 9b 57 ae 3e a5 e9 |...&....?6.W.>..|\n" +
"00000030 bd 39 c4 3a 8a 61 f9 c5 2f ea c6 1d 00 00 00 aa |.9.:.a../.......|\n" +
"00000040 4f bf c8 30 00 00 00 |O..0...|\n" +
"00000047\n"
);
// first 10 bytes are the outer gzip header
// next 1 byte is the stored header (01) BFINAL=1 BTYPE=00 remaining bits of byte skipped
// next 4 byte are the stored length and bit-flipped length (30 00 cf ff)
// next 48 bytes are the inner file
// next 10 bytes are the inner gzip header
// next 30 bytes is the inner gzip content (see dynamic example above)
// next 8 bytes are the inner gzip footer
// last 8 bytes are the outer gzip footer
// decode the stored block
var infl = new SlowInflate(input, output);
infl.inflate();
for (int i = 0; i < infl.outputPos; i++) System.out.printf("%02x ", output[i]);
// decode the zip inside the zip (fixed huffman)
final byte[] input2 = Arrays.copyOfRange(output, 10, infl.outputPos - 8);
final byte[] output2 = new byte[29];
var infl2 = new SlowInflate(input2, output2);
infl2.inflate();
for (int i = 0; i < infl2.outputPos; i++) System.out.printf("%02x ", output2[i]);
System.out.println(" \"" + new String(output2, 0, infl2.outputPos) + "\"");
}
// just for testing - makes it easy to use hexdump -C|pbcopy to try stuff out
private static byte[] decodeHexdump(final String dump) {
final var lines = dump.split("\n");
final var bytes = new byte[lines.length*16];
var i = 0;
for (final var line : lines)
if (line.length() > 10)
for (final var hex : line.substring(10, 10 + 3 * 16).trim().split("\\s+"))
bytes[i++] = (byte) Integer.parseInt(hex.trim(), 16);
return Arrays.copyOfRange(bytes, 10, i - 8);
}
// actual decompression code begins here
private final byte[] input, output;
private int inputBitPos, outputPos;
private final int[] lengthForCode, distanceForCode;
public SlowInflate(final byte[] input, final byte[] output) {
this.input = input;
this.output = output;
inputBitPos = 0;
outputPos = 0;
lengthForCode = setupLengthCodes();
distanceForCode = setupDistanceCodes();
}
private static final int[] LENGTH_CODE_EXTRA_BITS = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
private int[] setupLengthCodes() {
// set up length encoding lookups (see 3.2.5 in RFC 1951)
// Extra Extra Extra
// Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
// ---- ---- ------ ---- ---- ------- ---- ---- -------
// 257 0 3 267 1 15,16 277 4 67-82
// 258 0 4 268 1 17,18 278 4 83-98
// 259 0 5 269 2 19-22 279 4 99-114
// 260 0 6 270 2 23-26 280 4 115-130
// 261 0 7 271 2 27-30 281 5 131-162
// 262 0 8 272 2 31-34 282 5 163-194
// 263 0 9 273 3 35-42 283 5 195-226
// 264 0 10 274 3 43-50 284 5 227-257
// 265 1 11,12 275 3 51-58 285 0 258
// 266 1 13,14 276 3 59-66
int[] lengthForCode = new int[LENGTH_CODE_EXTRA_BITS.length];
int code = 0, length = 3;
for (final int extraBits : LENGTH_CODE_EXTRA_BITS) {
lengthForCode[code++] = length;
length += 1 << extraBits;
}
lengthForCode[code-1]--; // yes, strange isn't it
if (code != 286 - 257 || length != 260) throw new AssertionError("length code lookup create failed");
return lengthForCode;
}
private static final int[] DISTANCE_CODE_EXTRA_BITS = new int[]{0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};
private int[] setupDistanceCodes() {
// set up distance encoding lookups (see 3.2.5 in RFC 1951)
// Extra Extra Extra
// Code Bits Dist Code Bits Dist Code Bits Distance
// ---- ---- ----- ---- ---- -------- ---- ---- ----------
// 0 0 1 10 4 33-48 20 9 1025-1536
// 1 0 2 11 4 49-64 21 9 1537-2048
// 2 0 3 12 5 65-96 22 10 2049-3072
// 3 0 4 13 5 97-128 23 10 3073-4096
// 4 1 5,6 14 6 129-192 24 11 4097-6144
// 5 1 7,8 15 6 193-256 25 11 6145-8192
// 6 2 9-12 16 7 257-384 26 12 8193-12288
// 7 2 13-16 17 7 385-512 27 12 12289-16384
// 8 3 17-24 18 8 513-768 28 13 16385-24576
// 9 3 25-32 19 8 769-1024 29 13 24577-32768
int[] distanceForCode = new int[DISTANCE_CODE_EXTRA_BITS.length];
int code = 0, distance = 1;
for (final int extraBits : DISTANCE_CODE_EXTRA_BITS) {
distanceForCode[code++] = distance;
distance += 1 << extraBits;
}
if (code != 30 || distance != 32769) throw new AssertionError("distance code lookup create failed");
return distanceForCode;
}
// very primitive version of inflate
// passed in buffer not checked for size overrun
// extremely slow
public void inflate() {
for (; ; ) {
// block start - read block header bits - ref 3.2.3 of RFC 1951
final int finalBlock = readBit(); // =1 if this is the last block in the stream
final int blockType = readForwardBits(2); // 0=uncompressed, 1=fixed huffman, 2=dynamic huffman, 3=reserved
switch (blockType) {
case 0 -> storedBlockInflate();
case 1 -> fixedHuffmanBlockInflate();
case 2 -> dynamicHuffmanBlockInflate();
default -> throw new AssertionError("unrecognized deflate block type 3");
}
if (finalBlock == 1) break;
}
}
private void storedBlockInflate() {
// advance to whole byte boundary
while ((inputBitPos & 7) != 0) inputBitPos++;
int len = readForwardBits(16), nlen = readForwardBits(16);
if ((nlen ^ 0xFFFF) != len) throw new RuntimeException("~nlen != len in stored block");
int bytePos = inputBitPos >> 3;
for (int i = 0; i < len; i++) output[outputPos++] = input[bytePos++];
inputBitPos = bytePos << 3;
}
private void fixedHuffmanBlockInflate() {
for (int code; (code = readFixedCode()) != 256; ) // read the huffman code (7-9 bits) - 256 = end of block
decodeCode(code, null);
}
private void dynamicHuffmanBlockInflate() {
// read/build huffman trees for literal/lengths and distance codes
final int lengthCodeCount = readForwardBits(5);
final int literalAndLengthsCodeCount = lengthCodeCount + 257; // 256 literals + 1 stop code
final int distanceCodesCount = readForwardBits(5) + 1; // +1 because we know we will have at least 1
final int codeLengthsCount = readForwardBits(4) + 4; // +4 because we know we will need to have code length 0
// build a code lengths huffman tree
final int[] codeLengths = new int[CODE_LENGTHS_ORDER.length];
for (int codeLengthsIndex = 0; codeLengthsIndex < codeLengthsCount; codeLengthsIndex++) {
int b = readForwardBits(3); System.out.printf("%d ", b);
codeLengths[CODE_LENGTHS_ORDER[codeLengthsIndex]] = b;
}
final int[][] huffCodeLens = buildHuffmanTree(codeLengths);
// gather code lengths for literals/length and distance codes
System.out.println();
final int[] allCodeLengths = new int[literalAndLengthsCodeCount + distanceCodesCount];
for (int allCodeLengthsIndex = 0; allCodeLengthsIndex < literalAndLengthsCodeCount + distanceCodesCount; ) {
final int codeLengthCode = readCodeWithHuffmanTree(huffCodeLens);
System.out.printf("%d ", codeLengthCode);
if (codeLengthCode >= 0 && codeLengthCode < 16) // number of bits in code or 0 (unused)
allCodeLengths[allCodeLengthsIndex++] = codeLengthCode;
else if (codeLengthCode == 16) { // repeat prior code 3-6 times
final int copyCount = readForwardBits(2) + 3;
final int src = allCodeLengths[allCodeLengthsIndex-1];
for (int i = 0; i < copyCount; i++)
allCodeLengths[allCodeLengthsIndex++] = src;
} else if (codeLengthCode == 17) { // 0 (unused) for 3-10 codes
allCodeLengthsIndex += readForwardBits(3) + 3;
} else if (codeLengthCode == 18) { // 0 (unused) for 11-138 codes
int x = readForwardBits(7);
allCodeLengthsIndex += x + 11;
} else
throw new RuntimeException("Unexpected code " + codeLengthCode + " encountered. Should be impossible.");
}
final int[] literalsAndLengthsCodeLengths = Arrays.copyOfRange(allCodeLengths, 0, literalAndLengthsCodeCount);
final int[] distanceCodeLengths = Arrays.copyOfRange(allCodeLengths, literalAndLengthsCodeCount, allCodeLengths.length);
// build huffman trees for literal/lengths and distance codes
final int[][] huffmanLiteralsAndLengths = buildHuffmanTree(literalsAndLengthsCodeLengths), huffmanDistanceLengths = buildHuffmanTree(distanceCodeLengths);
// read the dynamic stream
for (int code; (code = readCodeWithHuffmanTree(huffmanLiteralsAndLengths)) != 256; )
decodeCode(code, huffmanDistanceLengths);
}
private int readFixedCode() { // ref 3.2.6 of RFC 1951
int bits = readReverseBits(7); // code is 7 to 9 bits, but the first 7 will tell us how many more we need
// Lit Value Bits Codes
// 0 - 143 8 00110000 through 10111111 - first 7 bits = 0x18 - read one extra
// 144 - 255 9 110010000 through 111111111 - first 7 bits = 0x64 - read two extra
// 256 - 279 7 0000000 through 0010111 - first 7 bits = 0x00 - read zero extra
// 280 - 287 8 11000000 through 11000111 - first 7 bits = 0x60 - read one extra
int extraBits = bits >= 0x18 ? bits >= 0x64 ? 2 : 1 : 0;
// subtract the huffman code range start and add the literal range start
int huffmanCodeAdjustment = bits >= 0x60 ? bits >= 0x64 ? 144 - 0x190 : 280 - 0xc0 : bits >= 0x18 ? 0 - 0x30 : 256 - 0x0;
return (bits << extraBits) + readReverseBits(extraBits) + huffmanCodeAdjustment;
}
// first are the repeaters/copier, then 0 which marks unused codes, then the code lengths 1-15 in the
// order they are most likely to be used, so we can give a shorter codeLengthsCount to save bits
private static final int[] CODE_LENGTHS_ORDER = new int[]{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
// used by both fixed and dynamic huffman blocks
// given a code, will output a literal or any extra info required to know the <distance,length> to copy and copies
// assumes we've already exited the decoding loop if we got a 256 (this will throw if not)
private void decodeCode(int literalOrLengthCode, int[][] huffmanDistanceLengths) {
if (literalOrLengthCode < 256) { // literal
output[outputPos++] = (byte) literalOrLengthCode;
} else { // length/distance code
int lengthCode = literalOrLengthCode - 257;
int length = this.lengthForCode[lengthCode] + readForwardBits(LENGTH_CODE_EXTRA_BITS[lengthCode]);
// fixedHuffmanBlockInflate just reads 5 bits to figure out distanceIndex
int distanceCode = huffmanDistanceLengths == null ? readReverseBits(5) : readCodeWithHuffmanTree(huffmanDistanceLengths);
int distance = this.distanceForCode[distanceCode] + readForwardBits(DISTANCE_CODE_EXTRA_BITS[distanceCode]);
// copy length bytes start from -distance (length may be more than distance!)
outputCopy(outputPos - distance, length);
}
}
// only dynamic blocks use these two huffman methods below
// takes an array of lengths and builds a huffman tree for it
// so the reader can quickly decode the stream
// ref 3.2.2 of RFC 1951
// a b c d b a c d
// given [2,1,3,3] returns [null,[1,-1],[-1,-1,0,-1],[-1,-1,-1,-1,-1,-1,2,3]]
// so we can quickly read bits until we find our code
private int[][] buildHuffmanTree(int[] bitLengths) {
// scan for largest bit length
int maxLengths = 0;
for (int bitLength : bitLengths) if (bitLength > maxLengths) maxLengths = bitLength;
var tree = new int[maxLengths + 1][];
// for each bit length, shift the starting code and limit
int code = 0;
for (int bits = 1; bits <= maxLengths; bits++) {
int[] t = tree[bits] = new int[1 << bits];
Arrays.fill(t, -1); // prefill with -1 to indicate code not found at this bit length
// plug in the codes for lengths matching current bit length, advancing the code when we do
for (int i = 0; i < bitLengths.length; i++) if (bitLengths[i] == bits) t[code++] = i;
code <<= 1;
}
return tree;
}
// read a bit at a time until we find the valid code in the huffman tree
// given [null,[1,-1],[-1,-1,0,-1],[-1,-1,-1,-1,-1,-1,2,3]]
// would read a bit, if 0, would return 1, otherwise it would shift it and read another bit
// if bits are 10, would return 0, otherwise it would shift it and read another bit
// if bits are 110, would return 2 otherwise 3.
private int readCodeWithHuffmanTree(int[][] huffmanTree) {
int n = readBit(), code;
for (int bits = 1; bits < huffmanTree.length; bits++, n = (n << 1) + readBit())
if ((code = huffmanTree[bits][n]) != -1) return code;
throw new RuntimeException("Invalid code " + n);
}
// generic methods
// read a single bit, staring from the lsb
private int readBit() {
int bytePos = inputBitPos >> 3, bitPos = inputBitPos & 7;
inputBitPos++;
return (input[bytePos] >> bitPos) & 1;
}
// reads up to 31 bits (may give wrong results after that)
// nothing in inflate should be reading more than 15 bits at a time
// reads them in lsb-first order (ie: turns 0x80 to 0x01)
private int readReverseBits(final int bitCount) {
int n = 0;
for (int i = 0; i < bitCount; i++)
n = (n << 1) + readBit();
return n;
}
// reads up to 31 bits (may give wrong results after that)
// nothing in inflate should be reading more than 15 bits at a time
// reads them in msb-first order
private int readForwardBits(final int bitCount) {
int n = 0;
for (int i = 0; i < bitCount; i++)
n += readBit() << i;
return n;
}
// copies back referenced bytes in the output
private void outputCopy(final int sourceOffset, final int length) {
for (int i = sourceOffset; i < sourceOffset + length; ) output[outputPos++] = output[i++];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment