Minimal ZIP file – part III 
       ==============================
       
       
       This article is part of a series. 
       
 (DIR) Creating a valid ZIP-file
 (DIR) Use .NET’s DeflateStream
       - No dependencies (coding the DEFLATE algorithm) 👈 
 (DIR) Calculating the CRC-32
       
       Introduction 
       -------------
       
       
       In the previous part a little cheating was done by using an off-the-shelve DeflateStream . 
       
 (DIR) previous part
       
       So how challenging is it to implement the DEFLATE algorithm from scratch? It depends! 
       
       
       About DEFLATE 
       --------------
       
       
       A DEFLATE stream is a combination of LZ77 1 and Huffman coding 2 . Easy, right? I did both of them before, but creating valid ZIP-files with both of them is another animal. 
       
 (DIR) 1
 (DIR) 2
       
       DEFLATE is documented in RFC 1951 3 which is only 17 pages. However, after reading it many times and looking at existing implementations (some of them over 1000 lines of cryptic C code), it left me puzzled. 
       
 (HTM) RFC 1951 
 (DIR) 3
       
       Solution 
       ---------
       
       
       Ultimately, I decided to take a bunch of shortcuts and ended up with a very simple Deflater for educational purposes. Only LZ77 is implemented without dynamic Huffman , and fixed Huffman codes 4 are hardcoded. This explains points 1 and 2 below. Fixed Huffman codes only work with small values. 
       
 (DIR) 4
       
       The limits of this implementation are: 
       
       - ASCII characters only. 
       - Maximum back reference is 4 characters, maximum length is 10 characters. 
       - Pretty buggy due to misunderstanding laziness of LSB / MSB on my part. 
       
       Despite these horrible limits, a string like ‘BANANABANANABANANABANANABANANA’ gets 20% smaller 5 . Success! Not bad if you consider that deflate uses 32 kB back references unlike this implementation. 
       
 (DIR) 5
       
       Source code 
       ------------
       
       
       The idea behind the code is to brute force search for repeating runs of characters, when found a pair (length, distance) is written out instead of the run. If no run is found, something called a literal is written. 
       
       
       There is no gain or even a loss for small runs, but longer runs take advantage. 
       
       
       This is ‘just’ three nested loops, but for readability the two inner loops are extracted to a method FindMatch() . 
       
       
       And a method to find a match as long as possible: 
       
 (DIR) LZ77.cs
       
       A separate class BitWriter ( BitWriter.cs ) was introduced to keep a minimum amount of red tape. Although Deflater and BitWriter do not have the same contract as e.g. DeflateStream integrating it in the existing code is easy: 
       
 (DIR) BitWriter.cs
       
       Again, Info-ZIP’s zip agrees: 
       
       
       Writing more extensive Huffman codes (either fixed or dynamic) is left as an exercise for the reader or out of scope as Bertrik likes to say. 
       
       
       Next up 
       --------
       
       
       In the next part another dependency will be removed; calculating the CRC-32. 
       
 (DIR) next part
       ----------------------------------
       -  Wikipedia: LZ77 and LZ78  ↩︎  
       
       Wikipedia: LZ77 and LZ78  ↩︎ 
       
 (HTM) LZ77 and LZ78 
 (DIR) ↩︎
       -  en.wikipedia.org/wiki/Huffman_coding  ↩︎  
       
       en.wikipedia.org/wiki/Huffman_coding  ↩︎ 
       
 (HTM) en.wikipedia.org/wiki/Huffman_coding 
 (DIR) ↩︎
       -  Very important: RFC 1951 Errata  ↩︎  
       
       Very important: RFC 1951 Errata  ↩︎ 
       
 (HTM) RFC 1951 Errata 
 (DIR) ↩︎
       -  Doing fixed Huffman instead of LZ77 was also an option, but it actually inflates the data in this case. ↩︎  
       
       Doing fixed Huffman instead of LZ77 was also an option, but it actually inflates the data in this case. ↩︎ 
       
 (DIR) ↩︎
       -  DeflateStream gets it down 63%, can you do better than that? ↩︎  
       
       DeflateStream gets it down 63%, can you do better than that? ↩︎ 
       
 (DIR) ↩︎
 (DIR) previous Minimal ZIP file – part II
       
 (DIR) next Minimal ZIP file – part IV
       
       
       Related 
       --------
       
 (DIR) Gopher enabled
 (TXT) Goofy gopher (.svg) 
 (DIR) http2gopher
 (TXT) /img/fallback.svg (.svg) 
 (DIR) Data compression 101
 (TXT) /img/fallback.svg (.svg) 
 (DIR) [Talk] Datacompressie
 (TXT) bits (.svg) 
 (DIR) Delphi Tetris
 (IMG) Delphi Tetris (.png) 
 (DIR) PicoSearch - TF-IDF in 50 lines
 (TXT) /img/fallback.svg (.svg) 
 (DIR) Software engineering, een volwassen vak?
 (IMG) Boekje (.jpeg) 
 (DIR) Blaztris
 (TXT) /img/fallback.svg (.svg) 
 (DIR) Upgrade application without source code
 (TXT) Bits (.svg) 
 (DIR) Colossus PoC
 (IMG) screenshot of colossus visualiser and malfunction controller (.png)