| # Deflate |
| |
| Deflate is a general purpose compression format, using Huffman codes and |
| Lempel-Ziv style length-distance back-references. It is specified in [RFC |
| 1951](https://www.ietf.org/rfc/rfc1951.txt). |
| |
| Gzip ([RFC 1952](https://www.ietf.org/rfc/rfc1952.txt)) and zlib ([RFC |
| 1950](https://www.ietf.org/rfc/rfc1950.txt)) are two thin wrappers (with |
| similar purpose, but different wire formats) around the raw deflate encoding. |
| Gzip (the file format) is used by the `gzip` and `tar` command line tools and |
| by the HTTP network protocol. Zlib is used by the ELF executable and PNG image |
| file formats. |
| |
| [Zip](https://support.pkware.com/display/PKZIP/APPNOTE) (also known as PKZIP) |
| is another wrapper, similar to combining gzip with tar, that can compress |
| multiple files into a single archive. Zip is widely used by the ECMA Office |
| Open XML format, the OASIS Open Document Format for Office Applications and the |
| Java JAR format. |
| |
| Wrangling those formats that build on deflate (gzip, zip and zlib) is not |
| provided by this package. For zlib, look at the `std/zlib` package instead. The |
| other formats are TODO. |
| |
| For example, look at `test/data/romeo.txt*`. First, the uncompressed text: |
| |
| $ xxd test/data/romeo.txt |
| 00000000: 526f 6d65 6f20 616e 6420 4a75 6c69 6574 Romeo and Juliet |
| 00000010: 0a45 7863 6572 7074 2066 726f 6d20 4163 .Excerpt from Ac |
| etc |
| 00000390: 740a 536f 2073 7475 6d62 6c65 7374 206f t.So stumblest o |
| 000003a0: 6e20 6d79 2063 6f75 6e73 656c 3f0a n my counsel?. |
| |
| The raw deflate encoding: |
| |
| $ xxd test/data/romeo.txt.deflate |
| 00000000: 4d53 c16e db30 0cbd f32b d853 2e46 0e3d MS.n.0...+.S.F.= |
| 00000010: 2e87 20ed 0234 c5ba 0049 861e 861d 149b .. ..4...I...... |
| etc |
| 00000200: 7d13 8ffd b9a3 24bb 68f4 eb30 7a59 610d }.....$.h..0zYa. |
| 00000210: 7f01 .. |
| |
| The gzip format wraps a variable length header (in this case, 20 bytes) and 8 |
| byte footer around the raw deflate data. The header contains the NUL-terminated |
| C string name of the original, uncompressed file, "romeo.txt", amongst other |
| data. The footer contains a 4 byte CRC32 checksum and a 4 byte length of the |
| uncompressed file (0x3ae = 942 bytes). |
| |
| $ xxd test/data/romeo.txt.gz |
| 00000000: 1f8b 0808 26d8 5d59 0003 726f 6d65 6f2e ....&.]Y..romeo. |
| 00000010: 7478 7400 4d53 c16e db30 0cbd f32b d853 txt.MS.n.0...+.S |
| etc |
| 00000210: de5d 2c67 7d13 8ffd b9a3 24bb 68f4 eb30 .],g}.....$.h..0 |
| 00000220: 7a59 610d 7f01 ef07 e5ab ae03 0000 zYa........... |
| |
| The zlib format wraps a 2 byte header and 4 byte footer around the raw deflate |
| data. The footer contains a 4 byte Adler32 checksum. TODO: move this to |
| std/zlib/README.md. |
| |
| $ xxd test/data/romeo.txt.zlib |
| 00000000: 789c 4d53 c16e db30 0cbd f32b d853 2e46 x.MS.n.0...+.S.F |
| 00000010: 0e3d 2e87 20ed 0234 c5ba 0049 861e 861d .=.. ..4...I.... |
| etc |
| 00000200: 2c67 7d13 8ffd b9a3 24bb 68f4 eb30 7a59 ,g}.....$.h..0zY |
| 00000210: 610d 7f01 57bb 3ede a...W.>. |
| |
| |
| # Wire Format Worked Example |
| |
| Consider `test/data/romeo.txt.deflate`. The relevant spec is RFC 1951. |
| |
| offset xoffset ASCII hex binary |
| 000000 0x0000 M 0x4D 0b_0100_1101 |
| 000001 0x0001 S 0x53 0b_0101_0011 |
| 000002 0x0002 . 0xC1 0b_1100_0001 |
| 000003 0x0003 n 0x6E 0b_0110_1110 |
| 000004 0x0004 . 0xDB 0b_1101_1011 |
| 000005 0x0005 0 0x30 0b_0011_0000 |
| 000006 0x0006 . 0x0C 0b_0000_1100 |
| 000007 0x0007 . 0xBD 0b_1011_1101 |
| 000008 0x0008 . 0xF3 0b_1111_0011 |
| 000009 0x0009 + 0x2B 0b_0010_1011 |
| 000010 0x000A . 0xD8 0b_1101_1000 |
| 000011 0x000B S 0x53 0b_0101_0011 |
| 000012 0x000C . 0x2E 0b_0010_1110 |
| 000013 0x000D F 0x46 0b_0100_0110 |
| 000014 0x000E . 0x0E 0b_0000_1110 |
| 000015 0x000F = 0x3D 0b_0011_1101 |
| 000016 0x0010 . 0x2E 0b_0010_1110 |
| 000017 0x0011 . 0x87 0b_1000_0111 |
| 000018 0x0012 0x20 0b_0010_0000 |
| 000019 0x0013 . 0xED 0b_1110_1101 |
| etc |
| 000522 0x020A . 0xEB 0b_1110_1011 |
| 000523 0x020B 0 0x30 0b_0011_0000 |
| 000524 0x020C z 0x7A 0b_0111_1010 |
| 000525 0x020D Y 0x59 0b_0101_1001 |
| 000526 0x020E a 0x61 0b_0110_0001 |
| 000527 0x020F . 0x0D 0b_0000_1101 |
| 000528 0x0210 . 0x7F 0b_0111_1111 |
| 000529 0x0211 . 0x01 0b_0000_0001 |
| |
| Starting at the top: |
| |
| offset xoffset ASCII hex binary |
| 000000 0x0000 M 0x4D 0b_0100_1101 |
| |
| As per the RFC section 3.2.3. Details of block format: |
| |
| - BFINAL is the first (LSB) bit, 0b1. This block is the final block. |
| - BTYPE is the next two bits in natural (MSB to LSB) order, 0b10, which means |
| a block that's compressed with dynamic Huffman codes. |
| |
| There are 3 block types: uncompressed, compressed with fixed Huffman codes and |
| compressed with dynamic Huffman codes. The first type is straightforward: |
| containing a uint16 length `N` (and its complement, for error detection) and |
| then `N` literal bytes. The second type is the same as the third type but with |
| built-in `lcode` and `dcode` tables (see below). The third type is the |
| interesting part of the deflate format, and its deconstruction continues below. |
| |
| |
| ## Dynamic Huffman Blocks |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000000 0x0000 M 0x4D 0b_0100_1... |
| 000001 0x0001 S 0x53 0b_0101_0011 |
| 000002 0x0002 . 0xC1 0b_1100_0001 |
| |
| As per the RFC section 3.2.7. Compression with dynamic Huffman codes, three |
| variables (5, 5 and 4 bits) are read in the same natural (MSB to LSB) order: |
| |
| - HLIT = 0b01001 = 9 |
| - HDIST = 0b10011 = 19 |
| - HCLEN = 0b1010 = 10 |
| |
| Adding the implicit biases give: |
| |
| nlit = 9 + 257 = 266 |
| ndist = 19 + 1 = 20 |
| nclen = 10 + 4 = 14 |
| |
| |
| ## Code Length Code Lengths |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000002 0x0002 . 0xC1 0b_1100_000. |
| 000003 0x0003 n 0x6E 0b_0110_1110 |
| 000004 0x0004 . 0xDB 0b_1101_1011 |
| 000005 0x0005 0 0x30 0b_0011_0000 |
| 000006 0x0006 . 0x0C 0b_0000_1100 |
| 000007 0x0007 . 0xBD 0b_1011_1101 |
| |
| There are 19 possible code length code lengths (this is not a typo), but the |
| wire format order is shuffled (in the idiosyncratic order: 16, 17, 18, 0, 8, |
| ..., 15) so that later elements are more likely to be zero (and hence |
| compressible). There are `nclen` (in this case, 14) explicit code length code |
| lengths, 3 bits each. |
| |
| clcode_lengths[16] = 0b000 = 0 |
| clcode_lengths[17] = 0b100 = 4 |
| clcode_lengths[18] = 0b101 = 5 |
| clcode_lengths[ 0] = 0b011 = 3 |
| clcode_lengths[ 8] = 0b011 = 3 |
| clcode_lengths[ 7] = 0b011 = 3 |
| clcode_lengths[ 9] = 0b011 = 3 |
| clcode_lengths[ 6] = 0b011 = 3 |
| clcode_lengths[10] = 0b000 = 0 |
| clcode_lengths[ 5] = 0b011 = 3 |
| clcode_lengths[11] = 0b000 = 0 |
| clcode_lengths[ 4] = 0b011 = 3 |
| clcode_lengths[12] = 0b000 = 0 |
| clcode_lengths[ 3] = 0b101 = 5 |
| |
| The remaining (19 - `nclen`) = 5 entries are implicitly zero: |
| |
| clcode_lengths[13] = 0 |
| clcode_lengths[ 2] = 0 |
| clcode_lengths[14] = 0 |
| clcode_lengths[ 1] = 0 |
| clcode_lengths[15] = 0 |
| |
| Undoing the shuffle gives: |
| |
| clcode_lengths[ 0] = 3 |
| clcode_lengths[ 1] = 0 |
| clcode_lengths[ 2] = 0 |
| clcode_lengths[ 3] = 5 |
| clcode_lengths[ 4] = 3 |
| clcode_lengths[ 5] = 3 |
| clcode_lengths[ 6] = 3 |
| clcode_lengths[ 7] = 3 |
| clcode_lengths[ 8] = 3 |
| clcode_lengths[ 9] = 3 |
| clcode_lengths[10] = 0 |
| clcode_lengths[11] = 0 |
| clcode_lengths[12] = 0 |
| clcode_lengths[13] = 0 |
| clcode_lengths[14] = 0 |
| clcode_lengths[15] = 0 |
| clcode_lengths[16] = 0 |
| clcode_lengths[17] = 4 |
| clcode_lengths[18] = 5 |
| |
| For `clcode`s, there are 7 + 1 + 2 = 10 non-zero entries: 7 3-bit codes, 1 |
| 4-bit code and 2 5-bit codes. The canonical Huffman encoding's map from bits to |
| `clcode`s is: |
| |
| bits clcode |
| 0b000 0 |
| 0b001 4 |
| 0b010 5 |
| 0b011 6 |
| 0b100 7 |
| 0b101 8 |
| 0b110 9 |
| 0b1110 17 |
| 0b11110 3 |
| 0b11111 18 |
| |
| Call that Huffman table `H-CL`. |
| |
| |
| ## Lcodes and Dcodes |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000007 0x0007 . 0xBD 0b_1011_1... |
| 000008 0x0008 . 0xF3 0b_1111_0011 |
| 000009 0x0009 + 0x2B 0b_0010_1011 |
| 000010 0x000A . 0xD8 0b_1101_1000 |
| 000011 0x000B S 0x53 0b_0101_0011 |
| 000012 0x000C . 0x2E 0b_0010_1110 |
| 000013 0x000D F 0x46 0b_0100_0110 |
| |
| When decoding via a Huffman table, bits are read in LSB to MSB order, |
| right-to-left in this debugging output. Extra bits, if any, are then read in |
| the other, natural order (MSB to LSB). Decoding via `H-CL` gives: |
| |
| bits clcode |
| 0b1110 17, 3 extra bits = 0b111 = 7 |
| 0b001 4 |
| 0b11111 18, 7 extra bits = 0b0001010 = 10 |
| 0b001 4 |
| 0b101 8 |
| 0b1110 17, 3 extra bits = 0b010 = 2 |
| 0b100 7 |
| 0b1110 17, 3 extra bits = 0b001 = 1 |
| 0b011 6 |
| 0b000 0 |
| |
| Still in the RFC section 3.2.7., this means: |
| |
| lcode_lengths has 3 + 7 = 10 consecutive zeroes |
| lcode_lengths[ 10] = 4 |
| lcode_lengths has 11 + 10 = 21 consecutive zeroes |
| lcode_lengths[ 32] = 4 |
| lcode_lengths[ 33] = 8 |
| lcode_lengths has 3 + 2 = 5 consecutive zeroes |
| lcode_lengths[ 39] = 7 |
| lcode_lengths has 3 + 1 = 4 consecutive zeroes |
| lcode_lengths[ 44] = 6 |
| lcode_lengths[ 45] = 0 |
| |
| After decoding the first 10 code lengths, the bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000013 0x000D F 0x46 0b_01.._.... |
| |
| Continuing to read all `nlit` (266) `lcode` lengths and `ndist` (20) `dcode` |
| lengths (zeroes are not shown here): |
| |
| lcode_lengths[ 10] = 4 |
| lcode_lengths[ 32] = 4 |
| lcode_lengths[ 33] = 8 |
| lcode_lengths[ 39] = 7 |
| lcode_lengths[ 44] = 6 |
| lcode_lengths[ 46] = 7 |
| lcode_lengths[ 50] = 8 |
| lcode_lengths[ 58] = 9 |
| lcode_lengths[ 59] = 7 |
| lcode_lengths[ 63] = 7 |
| etc |
| lcode_lengths[264] = 9 |
| lcode_lengths[265] = 9 |
| |
| and |
| |
| dcode_lengths[ 5] = 6 |
| dcode_lengths[ 6] = 5 |
| dcode_lengths[ 8] = 4 |
| dcode_lengths[ 9] = 5 |
| dcode_lengths[10] = 3 |
| etc |
| dcode_lengths[18] = 3 |
| dcode_lengths[19] = 6 |
| |
| The `H-CL` table is no longer used from here onwards. |
| |
| For `lcode`s, there are 6 + 9 + 10 + 16 + 10 + 12 = 63 non-zero entries: 6 |
| 4-bit codes, 9 5-bit codes, 10 6-bit codes, 16 7-bit codes, 10 8-bit codes and |
| 12 9-bit codes. The canonical Huffman encoding's map from bits to `lcode` |
| values is: |
| |
| bits lcode |
| 0b0000 10 |
| 0b0001 32 |
| 0b0010 101 |
| 0b0011 116 |
| 0b0100 257 |
| 0b0101 259 |
| 0b01100 97 |
| 0b01101 104 |
| 0b01110 105 |
| 0b01111 110 |
| 0b10000 111 |
| 0b10001 114 |
| 0b10010 115 |
| 0b10011 258 |
| 0b10100 260 |
| 0b101010 44 |
| 0b101011 99 |
| 0b101100 100 |
| 0b101101 102 |
| 0b101110 108 |
| 0b101111 109 |
| 0b110000 112 |
| 0b110001 117 |
| 0b110010 119 |
| 0b110011 121 |
| 0b1101000 39 |
| 0b1101001 46 |
| 0b1101010 59 |
| 0b1101011 63 |
| 0b1101100 65 |
| 0b1101101 69 |
| 0b1101110 73 |
| 0b1101111 79 |
| 0b1110000 82 |
| 0b1110001 83 |
| 0b1110010 84 |
| 0b1110011 98 |
| 0b1110100 103 |
| 0b1110101 261 |
| 0b1110110 262 |
| 0b1110111 263 |
| 0b11110000 33 |
| 0b11110001 50 |
| 0b11110010 66 |
| 0b11110011 67 |
| 0b11110100 72 |
| 0b11110101 74 |
| 0b11110110 77 |
| 0b11110111 87 |
| 0b11111000 107 |
| 0b11111001 118 |
| 0b111110100 58 |
| 0b111110101 68 |
| 0b111110110 76 |
| 0b111110111 78 |
| 0b111111000 85 |
| 0b111111001 91 |
| 0b111111010 93 |
| 0b111111011 120 |
| 0b111111100 122 |
| 0b111111101 256 |
| 0b111111110 264 |
| 0b111111111 265 |
| |
| Call that Huffman table `H-L`. |
| |
| For `dcode`s, there are 5 + 4 + 3 + 2 = 14 non-zero entries: 5 3-bit codes, 4 |
| 4-bit codes, 3 5-bit codes and 2 6-bit codes. The canonical Huffman encoding's |
| map from bits to `dcode` values is: |
| |
| bits dcode |
| 0b000 10 |
| 0b001 14 |
| 0b010 16 |
| 0b011 17 |
| 0b100 18 |
| 0b1010 8 |
| 0b1011 12 |
| 0b1100 13 |
| 0b1101 15 |
| 0b11100 6 |
| 0b11101 9 |
| 0b11110 11 |
| 0b111110 5 |
| 0b111111 19 |
| |
| Call that Huffman table `H-D`. |
| |
| |
| ## Decoding Literals |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000052 0x0034 . 0xE7 0b_1..._.... |
| 000053 0x0035 C 0x43 0b_0100_0011 |
| 000054 0x0036 . 0xE8 0b_1110_1000 |
| 000055 0x0037 ) 0x29 0b_0010_1001 |
| 000056 0x0038 . 0xA0 0b_1010_0000 |
| 000057 0x0039 . 0xF1 0b_1111_0001 |
| |
| Decoding from that bit stream via `H-L` gives some literal bytes (where the |
| `lcode` value is < 256): |
| |
| bits lcode |
| 0b1110000 82 (ASCII 'R') |
| 0b10000 111 (ASCII 'o') |
| 0b101111 109 (ASCII 'm') |
| 0b0010 101 (ASCII 'e') |
| 0b10000 111 (ASCII 'o') |
| 0b0001 32 (ASCII ' ') |
| 0b01100 97 (ASCII 'a') |
| 0b01111 110 (ASCII 'n') |
| |
| |
| ## Decoding Back-References |
| |
| This continues, up until we get to the "O Romeo, Romeo! wherefore art thou |
| Romeo?" line. |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000089 0x0059 . 0xC1 0b_11.._.... |
| 000090 0x005A . 0x1E 0b_0001_1110 |
| 000091 0x005B . 0x0F 0b_0000_1111 |
| 000092 0x005C . 0xF9 0b_1111_1001 |
| |
| Decoding from that bit stream via `H-L` gives: |
| |
| bits lcode |
| 0b1101111 79 (ASCII 'O') |
| 0b0001 32 (ASCII ' ') |
| 0b1110000 82 (ASCII 'R') |
| 0b10011 258 |
| |
| This 258 is our first non-literal `lcode`, the start of a length-distance |
| back-reference. We first need to decode the length. The RFC section 3.2.5. |
| Compressed blocks (length and distance codes) says that an `lcode` of 258 means |
| that length=4 with no extra bits. |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000092 0x005C . 0xF9 0b_111._.... |
| 000093 0x005D Y 0x59 0b_0101_1001 |
| |
| We next decode via `H-D` instead of `H-L`. |
| |
| bits dcode |
| 0b11110 11 |
| |
| Again, from section 3.2.5., a `dcode` of 11 means a distance in the range [49, |
| 64], 49 plus 4 extra bits. The next 4 bits are 0b0110=6, so the distance is 55. |
| We therefore copy length=4 bytes from distance=55 bytes ago: "omeo". |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000093 0x005D Y 0x59 0b_01.._.... |
| 000094 0x005E U 0x55 0b_0101_0101 |
| 000095 0x005F > 0x3E 0b_0011_1110 |
| |
| We go back to decoding via `H-L`, which gives |
| |
| bits lcode |
| 0b101010 44 (ASCII ',') |
| 0b10100 260 |
| |
| This is another non-literal. Section 3.2.5. says that an `lcode` of 260 means |
| length=6 with no extra bits. |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000095 0x005F > 0x3E 0b_0011_111. |
| |
| Decode with `H-D`. |
| |
| bits dcode |
| 0b111110 5 |
| |
| Again, from section 3.2.5., a `dcode` of 5 means a distance in the range [7, |
| 8], 7 plus 1 extra bit. The next 1 bits are 0b0=0, so the distance is 7. We |
| therefore copy length=6 bytes from distance=7 bytes ago: " Romeo". |
| |
| The bit stream is now at: |
| |
| offset xoffset ASCII hex binary |
| 000096 0x0060 . 0x0F 0b_0000_1111 |
| |
| We go back to decoding via `H-L`, which gives |
| |
| bits lcode |
| 0b11110000 33 (ASCII '!') |
| |
| And on we go. |
| |
| |
| ## End of Block |
| |
| The block finishes with the bit stream at: |
| |
| offset xoffset ASCII hex binary |
| 000522 0x020A . 0xEB 0b_1110_101. |
| 000523 0x020B 0 0x30 0b_0011_0000 |
| 000524 0x020C z 0x7A 0b_0111_1010 |
| 000525 0x020D Y 0x59 0b_0101_1001 |
| 000526 0x020E a 0x61 0b_0110_0001 |
| 000527 0x020F . 0x0D 0b_0000_1101 |
| 000528 0x0210 . 0x7F 0b_0111_1111 |
| 000529 0x0211 . 0x01 0b_0000_0001 |
| |
| The decoding is: |
| |
| bits lcode |
| 0b101011 99 (ASCII 'c') |
| 0b10000 111 (ASCII 'o') |
| 0b110001 117 (ASCII 'u') |
| 0b01111 110 (ASCII 'n') |
| 0b0100 257 (length=3 + 0_extra_bits...) |
| |
| bits dcode |
| 0b1101 15 (distance=193 + 6_extra_bits, 0b000010 in MSB to LSB order; |
| length=3, distance=195: copy "sel") |
| |
| bits lcode |
| 0b1101011 63 (ASCII '?') |
| 0b0000 10 (ASCII '\n') |
| 0b111111101 256 (end of block) |
| |
| In other words, the block ends with "counsel?\n". |
| |
| |
| # More Wire Format Examples |
| |
| See `test/data/artificial/deflate-*.commentary.txt` |
