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