RFC 1951 “Deflate” compression

Question

This is a little project I did over Christmas, I wanted to understand a bit more about how RFC 1951 (https://www.ietf.org/rfc/rfc1951.txt) compression worked, mostly out of curiosity really. RFC 1951 is used to compress PNG images, zip files and portions of PDF files ( and probably other things as well ). I have tried to keep the C# code fairly simple, concise and hopefully comprehensible, rather than being too concerned with efficiency. Here's the code:

using Generic = System.Collections.Generic; 

class Encoder : Generic.List<byte> // Data compression per RFC 1950, RFC 1951.
{
  public Generic.List<byte> Deflate( byte [] inp )
  {
    Clear();
    Add( 0x78); Add( 0x9C ); // RFC 1950 bytes.
    ReadInp( inp );
    while ( DoOutput( 1 ) == 0 );
    FlushBitBuf();
    Put32( Adler32( inp ) ); // RFC 1950 checksum.
    // System.Console.WriteLine( "Encoder.Deflate, input size=" + inp.Length + " output size=" + this.Count );
    return this;  
  }

  class PosList{ public int Pos; public PosList Next; } // List of 3-byte match positions.

  void ReadInp( byte [] input ) // LZ77 compression, per RFC 1951.
  { 
    Generic.Dictionary<int,PosList> dict = new Generic.Dictionary<int,PosList>(); 
    int n = input.Length;
    SetIBufSize( n );  

    int w = 0; // Holds last 3 bytes of input.
    int todo = 0; // Number of bytes in w that have not yet been output to IBuf, can be negative when a match is found.
    int pendingMatchLen = 0, pendingDist = 0;

    for ( int i = 0; i < 2 && i < n; i += 1 ) { w = ( w << 8 ) | input[ i ]; todo += 1; }

    for ( int i = 2; i < n; i += 1 )
    {
      w = ( ( w << 8 ) | input[ i ] ) & 0xffffff; todo += 1;
      PosList e, x = new PosList(); x.Pos = i;
      int bestMatchLen = 0, bestDist = 0;
      if ( dict.TryGetValue( w, out e ) )
      {
        x.Next = e;
        PosList p = x;
        if ( todo >= 3 ) while ( e != null )
        {
          int dist = i - e.Pos; if ( dist > 32768 ) { p.Next = null; break; }
          int matchLen = MatchLen( input, dist, i );
          if ( matchLen > bestMatchLen ) { bestMatchLen = matchLen; bestDist = dist; }  
          p = e; e = e.Next;         
        }
      }
      dict[ w ] = x; ISpace();

      // "Lazy matching" RFC 1951 p.15 : if there are overlapping matches, there is a choice over which of the match to use.
      // Example: "abc012bc345.... abc345". Here abc345 can be encoded as either [abc][345] or as a[bc345].
      // Since a range typically needs more bits to encode than a literal, choose the latter.

      if ( pendingMatchLen > 0 )
      {
        if ( bestMatchLen > pendingMatchLen || bestMatchLen == pendingMatchLen && bestDist < pendingDist )
        { IPut( input[ i-3 ] ); todo -= 1; }
        else // Save the pending match, suppress bestMatch if any.
        {
          IPut( 257 + pendingMatchLen );
          IPut( pendingDist );
          todo -= pendingMatchLen;
          bestMatchLen = 0;
        }
        pendingMatchLen = 0;
      }
      if ( bestMatchLen > 0 ) { pendingMatchLen = bestMatchLen; pendingDist = bestDist; }
      else if ( todo == 3  ) { IPut( w >> 16 ); todo = 2; }      
    } // End of main input loop.
    if ( pendingMatchLen > 0 )
    {
      IPut( 257 + pendingMatchLen );
      IPut( pendingDist );
      todo -= pendingMatchLen;
    }
    while ( todo > 0 ){ todo -= 1; IPut( (byte)( w >> (todo*8) ) ); }
  } // end ReadInp

  int MatchLen( byte [] input, int dist, int i )
  {
    // We have a match of 3 bytes, this function computes total match.
    int end = input.Length; if ( end - i > 256 ) end = i + 256; // Maximum match is 258.
    int x = i + 1; while ( x < end && input[ x ] == input[ x-dist ] ) x += 1;
    return x - i + 2; 
  }

  ushort [] IBuf; // Intermediate circular buffer, holds output from LZ77 algorithm.
  const int IBufSizeMax = 0x40000;
  int IBufSize, IBufI, IBufJ;
  void IPut( int x ) { IBuf[ IBufI++ ] = (ushort)x; if ( IBufI == IBufSize ) IBufI = 0; }
  int IGet(){ int result = IBuf[ IBufJ++ ]; if ( IBufJ == IBufSize ) IBufJ = 0; return result; }
  int ICount(){ if ( IBufI >= IBufJ ) return IBufI - IBufJ; else return IBufI + IBufSize - IBufJ; } // Number of values in IBuf.
  void ISpace(){ while ( ICount() > IBufSize - 10 ) DoOutput( 0 ); } // Ensure IBuf has space for at least 10 values.
  void SetIBufSize( int x ) { x += 20; if ( x > IBufSizeMax ) x = IBufSizeMax; if ( IBufSize < x ) { IBufSize = x; IBuf = new ushort[ x ]; } }

  byte DoOutput( byte lastBlock ) // While DoBlock fails, retry with a smaller amount of input.
  {
    int n = ICount();
    while ( !DoBlock( n, lastBlock ) ) { lastBlock = 0; n -= n / 20; }
    return lastBlock;
  }

  // RFC 1951 encoding constants.
  static byte [] ClenAlphabet = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
  static byte [] MatchExtra = { 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 };
  static ushort [] MatchOff = { 3,4,5,6, 7,8,9,10, 11,13,15,17, 19,23,27,31, 35,43,51,59, 67,83,99,115, 131,163,195,227, 258, 0xffff };
  static byte [] DistExtra = { 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 };
  static ushort [] DistOff = { 1,2,3,4, 5,7,9,13, 17,25,33,49, 65,97,129,193, 257,385,513,769, 1025,1537,2049,3073,
     4097,6145,8193,12289, 16385,24577, 0xffff };

  int   [] LitFreq = new int   [ 288 ], DistFreq = new int   [ 32 ], LenFreq = new int   [ 19 ];
  byte  [] LitLen  = new byte  [ 288 ], DistLen  = new byte  [ 32 ], LenLen  = new byte  [ 19 ];
  ushort[] LitCode = new ushort[ 288 ], DistCode = new ushort[ 32 ], LenCode = new ushort[ 19 ];

  bool DoBlock( int n, byte lastBlock )
  {
    // First compute symbol frequencies.
    Clear( LitFreq ); Clear( DistFreq );
    int saveIBufJ = IBufJ;
    int got = 0; while ( got < n )
    {
      int x = IGet(); got += 1;
      if ( x < 256 ) LitFreq[ x ] += 1;
      else
      { 
        x -= 257;
        int dist = IGet(); got += 1;
        int mc = 0; while ( x >= MatchOff[ mc ] ) mc += 1; mc -= 1;
        int dc = 0; while ( dist >= DistOff[ dc ] ) dc += 1; dc -= 1;
        LitFreq[ 257 + mc ] += 1;
        DistFreq[ dc ] += 1;
      }
    }
    LitFreq[ 256 ] += 1; // End of block code.
    IBufJ = saveIBufJ;

    // Now compute Huffman codes.
    int nLitCode = Huff.ComputeCode( 15, LitFreq, LitLen, LitCode ); if ( nLitCode < 0 ) return false;
    int nDistCode = Huff.ComputeCode( 15, DistFreq, DistLen, DistCode ); if ( nDistCode < 0 ) return false;
    if ( nDistCode == 0 ) nDistCode = 1;

    Clear( LenFreq );
    LenPass = 1; DoLengths( nLitCode, LitLen, true ); DoLengths( nDistCode, DistLen, false );

    if ( Huff.ComputeCode( 7, LenFreq, LenLen, LenCode ) < 0 ) return false;

    int nLenCode = 19; while ( nLenCode > 4 && LenLen[ ClenAlphabet[ nLenCode - 1 ] ] == 0 ) nLenCode -= 1;

    // Now output dynamic Huffman block. For small blocks fixed coding might work better, not implemented.
    PutBit( lastBlock );
    PutBits( 2, 2 );
    PutBits( 5, nLitCode - 257 ); PutBits( 5, nDistCode - 1 ); PutBits( 4, nLenCode - 4 );
    for ( int i = 0; i < nLenCode; i += 1 ) PutBits( 3, LenLen[ ClenAlphabet[ i ] ] );

    LenPass = 2; DoLengths( nLitCode, LitLen, true ); DoLengths( nDistCode, DistLen, false ); 

    got = 0; while ( got < n ) // Similar to loop above, but does output instead of computing symbol frequencies.
    {
      int x = IGet(); got += 1;
      if ( x < 256 ) PutBits( LitLen[ x ], LitCode[ x ] );
      else
      { 
        x -= 257;
        int dist = IGet(); got += 1;
        int mc = 0; while ( x >= MatchOff[ mc ] ) mc += 1; mc -= 1;
        int dc = 0; while ( dist >= DistOff[ dc ] ) dc += 1; dc -= 1;
        PutBits( LitLen[ 257 + mc ], LitCode[ 257 + mc ] );
        PutBits( MatchExtra[ mc ], x-MatchOff[ mc ] );
        PutBits( DistLen[ dc ], DistCode[ dc ] );
        PutBits( DistExtra[ dc ], dist-DistOff[ dc ] );
      }
    }
    PutBits( LitLen[ 256 ], LitCode[ 256 ] ); // End of block code.
    return true;
  } // end DoBlock

  // Run length encoding of code lengths - RFC 1951, page 13.

  int LenPass, Plen, ZeroRun, Repeat;

  void PutLenCode( int code ) { if ( LenPass == 1 ) LenFreq[ code ] += 1; else PutBits( LenLen[ code ], LenCode[ code ] ); }

  void DoLengths( int n, byte [] a, bool isLit )
  {
    if ( isLit ) { Plen = 0; ZeroRun = 0; Repeat = 0; }
    for ( int i = 0; i < n; i += 1 )
    {
      int len = a[ i ];
      if ( len == 0 ){ EncRepeat(); ZeroRun += 1; Plen = 0; }
      else if ( len == Plen ) { Repeat += 1; }
      else { EncZeroRun(); EncRepeat(); PutLenCode( len ); Plen = len; }
    }      
    if ( !isLit ) { EncZeroRun(); EncRepeat(); }
  }

  void EncRepeat()
  {
    while ( Repeat > 0 )
    {
      if ( Repeat < 3 ) { PutLenCode( Plen ); Repeat -= 1; }
      else { int x = Repeat; if ( x > 6 ) x = 6; PutLenCode( 16 ); if ( LenPass == 2 ) PutBits( 2, x-3 ); Repeat -= x;  }
    }
  }

  void EncZeroRun()
  {
    while ( ZeroRun > 0 )
    {
      if ( ZeroRun < 3 ) { PutLenCode( 0 ); ZeroRun -= 1; }
      else if ( ZeroRun < 11 ) { PutLenCode( 17 ); if ( LenPass == 2 ) PutBits( 3, ZeroRun-3 ); ZeroRun = 0;  }
      else { int x = ZeroRun; if ( x > 138 ) x = 138; PutLenCode( 18 ); if ( LenPass == 2 ) PutBits( 7, x - 11 ); ZeroRun -= x; }
    }
  }

  public static uint Adler32( byte [] b ) // Checksum function per RFC 1950.
  {
    uint s1 = 1, s2 = 0;
    for ( int i = 0; i < b.Length; i += 1 )
    {
      s1 = ( s1 + b[ i ] ) % 65521;
      s2 = ( s2 + s1 ) % 65521;
    }
    return s2*65536 + s1;    
  }

  static void Clear( int [] f ){ System.Array.Clear( f, 0, f.Length ); }

  // Output stream.
  byte Buf = 0, M = 1;
  void PutBit( int b ) { if ( b != 0 ) Buf |= M; M <<= 1; if ( M == 0 ) { Add(Buf); Buf = 0; M = 1; } }
  void PutBits( int n, int x ) { for ( int i = 0; i < n; i += 1 ) { PutBit( x & 1 ); x >>= 1; } }
  void FlushBitBuf(){ while ( M != 1 ) PutBit( 0 ); }
  void Put32( uint x ) { Add( (byte)( x >> 24 ) ); Add( (byte)( x >> 16 ) ); Add( (byte)( x >> 8 ) ); Add( (byte) x ); } 

}  // end class Encoder

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

class Huff // Given a list of frequencies (freq), compute Huffman code lengths (nbits) and codes (tree_code).
{
  public static int ComputeCode( int bitLimit, int [] freq, byte [] nbits, ushort [] tree_code )
  {
    int ncode = freq.Length;
    Node [] heap = new Node[ ncode ];
    int hn = 0;
    for ( int i = 0; i < ncode; i += 1 )
    {
      int f = freq[ i ];
      if ( f > 0 )
      {
        Node n = new Node();
        n.Freq = f;
        n.Code = (ushort)i;
        HeapInsert( heap, hn, n );
        hn += 1;
      }
    }

    for ( int i = 0; i < nbits.Length; i += 1 ) nbits[ i ] = 0;
    if ( hn <= 1 ) // Special case.
    { if ( hn == 1 ) nbits[ heap[ 0 ].Code ] = 1; }
    else
    {
      while ( hn > 1 ) // Keep pairing the lowest frequency nodes.
      {
        Node n = new Node();
        hn -= 1; n.Left = HeapRemove( heap, hn );
        hn -= 1; n.Right = HeapRemove( heap, hn );
        n.Freq =  n.Left.Freq + n.Right.Freq;  
        n.Depth = (byte) ( 1 + ( n.Left.Depth > n.Right.Depth ? n.Left.Depth : n.Right.Depth ) );    
        HeapInsert( heap, hn, n );
        hn += 1;
      }
      Walk( nbits, heap[ 0 ], 0 ); // Walk the tree to find the code lengths (nbits).
    }

    for ( int i = 0; i < ncode; i += 1 ) if ( nbits[ i ] > bitLimit ) return -1;

    // Now compute codes, code below is from RFC 1951 page 7.

    int maxBits = 0;
    for ( int i = 0; i < ncode; i += 1 ) if ( nbits[ i ] > maxBits ) maxBits = nbits[ i ];

    int [] bl_count = new int[ maxBits+1 ];
    for ( int i = 0; i < ncode; i += 1 ) bl_count[ nbits[ i ] ] += 1;

    int [] next_code = new int[ maxBits+1 ];
    int code = 0; bl_count[ 0 ] = 0;
    for ( int i = 0; i < maxBits; i += 1 ) 
    {
      code = ( code + bl_count[ i ] ) << 1;
      next_code[ i+1 ] = code;
    }

    for ( int i = 0; i < ncode; i += 1 ) 
    {
      int len = nbits[ i ];
      if ( len != 0 ) 
      {
        tree_code[ i ] = (ushort)Reverse( next_code[ len ], len );
        next_code[ len ] += 1;
      }
    }
    while ( ncode > 0 && nbits[ ncode - 1 ] == 0 ) ncode -= 1;

    //System.Console.WriteLine( "Huff.ComputeCode" );
    //for ( int i = 0; i < ncode; i += 1 ) if ( nbits[ i ] > 0 )
    //  System.Console.WriteLine( "i=" + i + " len=" + nbits[ i ] + " tc=" + tree_code[ i ].ToString("X") + " freq=" + freq[ i ] );

    return ncode;
  }

  class Node{ public Node Left, Right; public int Freq; public ushort Code; public byte Depth; }

  static int Reverse( int x, int bits )
  { int result = 0; for ( int i = 0; i < bits; i += 1 ) { result <<= 1; result |= x & 1; x >>= 1; } return result; } 

  static void Walk( byte [] a, Node n, int len )
  { if ( n.Left == null ) a[ n.Code ] = (byte)len; else { Walk( a, n.Left, len+1 ); Walk( a, n.Right, len+1 ); } }

  static bool LessThan( Node a, Node b )
  { return a.Freq < b.Freq || a.Freq == b.Freq && a.Depth < b.Depth; }

  // See e.g. https://en.wikipedia.org/wiki/Heap_(data_structure) for information on heap data structure.

  static void HeapInsert( Node [] heap, int h, Node n ) // h is size of heap before insertion.
  {
    int j = h;
    while ( j > 0 )
    {
      int p = ( j - 1 ) / 2; // Index of parent.
      Node pn = heap[ p ];
      if ( !LessThan( n, pn ) ) break;
      heap[ j ] = pn; // Demote parent.
      j = p;
    }    
    heap[ j ] = n;
  }

  static Node HeapRemove( Node [] heap, int h ) // h is size of heap after removal.
  {
    Node result = heap[ 0 ];
    Node n = heap[ h ];
    int j = 0;
    while ( true )
    {
      int c = j * 2 + 1; if ( c >= h ) break;
      Node cn = heap[ c ];
      if ( c + 1 < h )
      {
        Node cn2 = heap[ c + 1 ];
        if ( LessThan( cn2, cn ) ) { c += 1; cn = cn2; }
      } 
      if ( !LessThan( cn, n ) ) break;
      heap[ j ] = cn; j = c;  
    }
    heap[ j ] = n;
    return result;
  }

} // end class Huff

Answer 1

Welcome to Code Review. I am sorry but I do not find your code as comprehensible as you were hoping. I find myself more aligned to the comment by @t3chb0t.

I really must ask have you ever read any parts of the C# Naming Guidelines? I am not saying that to be mean. Given that you are a new poster, we do try to be nice but unfortunately sometimes a certain bluntness cannot be avoided.

Something to also consider is that you should favor composition over inheritance (Wikipedia link). Here is a good StackOverflow link on it too. Rather than class Encoder implementing List<byte>, it would be better to have a private field of List<byte>. This also prevents someone from inadvertently performing any method that modifies the encoded value, such as an Add, Clear, or Remove. You could then expose that field publicly as a read only value.

You have a fair amount in a section related to the intermediate circular buffer. This bugs me for several reasons. For one, I think the buffer, variables, and methods could be put into its own class, even if its a private internal class. And having variable names being with "I" conflicts with the naming guideline on many fronts: (1) variables should begin with lowercase letters, and (2) a capital "I" makes me think its an Interface.

I applaud you for emphasizing simple and concise over efficient. Next I would urge you think strongly about readability. Ask yourself how well a mediocre C# developer would understand your code without having to ask you questions about it.

Answer 2

Readability

To expand a bit on what Rick and t3chb0t already said, here are some specific things that hurt the readability of your code:

• Unnecessary abbreviations and undescriptive names. Some names convey virtually no meaning at all (n, w, x, p), while others are very unclear or do not accurately describe their meaning: ReadInp apparently performs deflation, not just input reading, and what does the 'do' in DoBlock mean?
• Stuffing multiple statements on a single line. This makes code much more difficult to 'scan', and code that's difficult to read tends to be difficult to maintain and debug.
  • Especially jarring are lines like
    int mc = 0; while (x >= MatchOff[mc]) mc += 1; mc -= 1;
    There's no clear distinction between what's part of the while loop body and what's not. This can lead to subtle problems. Putting each statement on a separate line, and indenting the loop body makes it easier to identify the control flow at a glance.
  • Declaring multiple variables of the same type at once, separated by commas, also falls under this: it requires more care to see whether each has been properly initialized, and if not, whether that was intentional or not.
• Related to the above point, the occasional omission of braces and sometimes inconsistent indentation doesn't help either.
• Lack of whitespace:
  • Adding an empty line between subsequent if statements makes it more clear that they're not related, which makes it easier to quickly scan control flow.
  • Leave an empty lines between methods to provide some 'breathing space'. A wall of text is more difficult to read than an article that's split up into chapters and paragraphs.
• Magic values - specific (numeric) values whose meaning is unclear, such as 19, 256, 257 and 288. Try using properly named constants instead.

C# specific

• It's strange to see using Generic = System.Collections.Generic;. Namespace aliases are useful to prevent name clashes, but in my experience that's rarely a problem. In this case, System.Collections.Generic is so ubiquitously used that doing anything else than using System.Collections.Generic; will only cause confusion.
• C# supports type inference, so Dictionary<int, PosList> dict = new Dictionary<int, PosList>(); can be simplified to var dict = new Dictionary<int, PosList>();.
• out variables can be declared in-line, so if (dict.TryGetValue(w, out e)) can be simplified to if (dict.TryGetValue(w, out PosList e)) or if (dict.TryGetValue(w, out var e)).

Design

• Inheritance is the wrong tool here, as Rick already pointed out. Just because an encoder uses byte-sequences as input and output does not make it a list of bytes itself. Note how calling Deflate again will overwrite the result of any previous calls - that's very surprising behavior (in a negative way). Also note that a lot of state that is only useful during the actual deflation is kept around - wasting memory, and making your job more difficult because you have to remember to properly reset things.
• I see two designs that could work well here:
  • A Stream-based design, where you provide a CompressionStream class that inherits from Stream (it's a stream that you can read decompressed data from) and that wraps another Stream (which contains the still-compressed data). This integrates well with file and network stream reading, among other things. Be sure to read up on how disposal (IDisposable) works.
  • An IEnumerable<byte>-based design, with an IEnumerable<byte> Deflate(IEnumerable<byte> compressedData) method. This lets you pass in a variety of collections, including arrays, lists and lazily evaluated sequences such as the results of Linq extension methods. Returning an IEnumerable<byte> allows you to return any of these as well, and lets you use yield, which can be useful in certain cases. Deflate(byteArray.Skip(4)), for example, deflates all but the first 4 bytes from byteArray, without any modifications to your code. And if Deflate uses yield, then Deflate(byteArray).Take(4) only deflates the first 4 bytes, while Deflate(byteArray).ToArray() gives you an array that contains all deflated data.
• Rick also mentioned those buffer-related methods, they're better moved to a separate buffer class. The same can be said for those 'output stream' methods. Take a look at how StreamWriter lets you write text to an underlying Stream, while taking care of things like encoding and buffering. You could create a similar construction for writing bits.