I have substantially revised my earlier implementation, it now seems to be competitive with the standard C# ZLib implementation, increasing compression while being faster for moderate length inputs, and slightly slower for large inputs ( data dependent ) - see long initial comment below for details.
It may also be competitive with google's Zopfli, which is much slower but which aims to maximise compression with a sophisticated algorithm to divide the input into blocks.
The code below chooses a blocksize ( for each individual block ) according to whether a larger blocksize improves compression.
After a fair bit of consideration, I decided against using _ for private field names, except if there is a clash with a property name ( as in the Heap class below ). I also opened a github account with my C# code for writing PDF files, which is my use for the code below.
I don't have specific questions for review, but would be interested in alternative ideas for dividing the input into blocks.
namespace Pdf {
/* RFC 1951 compression ( https://www.ietf.org/rfc/rfc1951.txt ) aims to compress a stream of bytes using :
(1) LZ77 matching, where if an input sequences of at least 3 bytes re-occurs, it may be coded
as a <length,distance> pointer.
(2) Huffman coding, where variable length codes are used, with more frequently used symbols encoded in less bits.
The input may be split into blocks, a new block introduces a new set of Huffman codes. The choice of block
boundaries can affect compression. The method used to determine the block size is as follows:
(1) The size of the next block to be output is set to an initial value.
(2) A comparison is made between encoding two blocks of this size, or a double-length block.
(3) If the double-length encoding is better, that becomes the block size, and the process repeats.
LZ77 compression is implemented as suggested in the standard, although no attempt is made to
truncate searches ( except searches terminate when the distance limit of 32k bytes is reached ).
Only dynamic huffman blocks are used, no attempt is made to use Fixed or Copy blocks.
Deflator ( this code) typically achieves better compression than ZLib ( http://www.componentace.com/zlib_.NET.htm
via https://zlib.net/, default settings ) by a few percent, and is faster on small inputs, but slower
on large inputs ( perhaps due to searches not being truncated ).
For example, compressing a font file FreeSans.ttf ( 264,072 bytes ), Zlib output is 148,324 bytes
in 44 milliseconds, whereas Deflator output is 144,289 bytes, 4,035 bytes smaller, in 59 milliseconds.
Compressing a C# source file of 19,483 bytes, Zlib output size was 5,965 bytes in 27 milliseconds,
whereas Deflator output was 5,890 bytes, 75 bytes smaller, in 16 milliseconds.
Sample usage:
byte [] data = { 1, 2, 3, 4 };
var mbs = new MemoryBitStream();
Deflator.Deflate( data, mbs, 1 );
byte [] deflated_data = mbs.ToArray();
The MemoryBitStream may alternatively be copied to a stream, this may be useful when writing PDF files ( the intended use case ).
Auxiliary top level classes/structs ( included in this file ):
* OutBitStream.
* MemoryBitStream : an implementation of OutBitStream.
* HuffmanCoding calculates Huffman codes.
* Heap : used to implemnt HuffmanCoding.
*/
sealed class Deflator
{
public static void Deflate( byte [] input, OutBitStream output, int format )
{
Deflator d = new Deflator( input, output );
if ( format == 1 ) output.WriteBits( 16, 0x9c78 ); // RFC 1950 bytes.
d.FindMatches( input );
d.Buffered = input.Length;
while ( !d.OutputBlock( true ) );
if ( format == 1 )
{
output.Pad( 8 );
output.WriteBits( 32, Adler32( input ) ); // RFC 1950 checksum.
}
}
// Private constants.
// RFC 1951 limits.
private const int MinMatch = 3;
private const int MaxMatch = 258;
private const int MaxDistance = 0x8000;
private const int StartBlockSize = 0x1000; // Initial blocksize, actual may be larger or smaller. Need not be power of two.
private const bool DynamicBlockSize = true;
private const int MaxBufferSize = 0x8000; // Must be power of 2.
// Instead of initialising LZ77 hashTable and link arrays to -(MaxDistance+1), EncodePosition
// is added when storing a value and subtracted when retrieving a value.
// This means a default value of 0 will always be more distant than MaxDistance.
private const int EncodePosition = MaxDistance + 1;
// Private fields.
private byte [] Input;
private OutBitStream Output;
private int Buffered; // How many Input bytes have been processed to intermediate buffer.
private int Finished; // How many Input bytes have been written to Output.
// Intermediate circular buffer for storing LZ77 matches.
private int [] PositionBuffer;
private ushort [] LengthBuffer;
private ushort [] DistanceBuffer;
private int BufferMask;
private int BufferWrite, BufferRead; // Indexes for writing and reading.
// Private functions and classes.
private Deflator( byte [] input, OutBitStream output )
{
Input = input;
Output = output;
int bufferSize = CalcBufferSize( input.Length / 3, MaxBufferSize );
PositionBuffer = new int[ bufferSize ];
LengthBuffer = new ushort[ bufferSize ];
DistanceBuffer = new ushort[ bufferSize ];
BufferMask = bufferSize - 1;
}
public static int CalcBufferSize( int n, int max )
// Calculates a power of 2 >= n, but not more than max.
{
if ( n >= max ) return max;
int result = 1;
while ( result < n ) result = result << 1;
return result;
}
private void FindMatches( byte [] input ) // LZ77 compression.
{
if ( input.Length < MinMatch ) return;
int limit = input.Length - 2;
int hashShift = CalcHashShift( limit * 2 );
uint hashMask = ( 1u << ( MinMatch * hashShift ) ) - 1;
int [] hashTable = new int[ hashMask + 1 ];
int [] link = new int[ limit ];
int position = 0; // position in input.
uint hash = ( (uint)input[ 0 ] << hashShift ) + input[ 1 ];
while ( position < limit )
{
hash = ( ( hash << hashShift ) + input[ position + 2 ] ) & hashMask;
int hashEntry = hashTable[ hash ];
hashTable[ hash ] = position + EncodePosition;
if ( position >= hashEntry ) // Equivalent to position - ( hashEntry - EncodePosition ) > MaxDistance.
{
position += 1;
continue;
}
link[ position ] = hashEntry;
int distance, match = BestMatch( input, link, hashEntry - EncodePosition, position, out distance );
position += 1;
if ( match < MinMatch ) continue;
// "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 single literal, choose the latter.
while ( position < limit )
{
hash = ( ( hash << hashShift ) + input[ position + 2 ] ) & hashMask;
hashEntry = hashTable[ hash ];
hashTable[ hash ] = position + EncodePosition;
if ( position >= hashEntry ) break;
link[ position ] = hashEntry;
int distance2, match2 = BestMatch( input, link, hashEntry - EncodePosition, position, out distance2 );
if ( match2 > match || match2 == match && distance2 < distance )
{
match = match2;
distance = distance2;
position += 1;
}
else break;
}
int copyEnd = SaveMatch( position - 1, match, distance );
if ( copyEnd > limit ) copyEnd = limit;
position += 1;
// Advance to end of copied section.
while ( position < copyEnd )
{
hash = ( ( hash << hashShift ) + input[ position + 2 ] ) & hashMask;
link[ position ] = hashTable[ hash ];
hashTable[ hash ] = position + EncodePosition;
position += 1;
}
}
}
private static int BestMatch( byte [] input, int [] link, int oldPosition, int position, out int distance )
{
int avail = input.Length - position;
if ( avail > MaxMatch ) avail = MaxMatch;
int bestMatch = 0, bestDistance = 0;
while ( true )
{
if ( input[ position + bestMatch ] == input[ oldPosition + bestMatch ] )
{
int match = MatchLength( input, position, oldPosition );
if ( match > bestMatch )
{
bestMatch = match;
bestDistance = position - oldPosition;
if ( bestMatch == avail ) break;
}
}
oldPosition = link[ oldPosition ];
if ( position >= oldPosition ) break;
oldPosition -= EncodePosition;
}
distance = bestDistance;
return bestMatch;
}
private static int MatchLength( byte [] input, int p, int q )
{
int end = input.Length;
if ( end > p + MaxMatch ) end = p + MaxMatch;
int pstart = p;
while ( p < end && input[ p ] == input [ q ] )
{
p += 1;
q += 1;
}
return p - pstart;
}
private static int CalcHashShift( int n )
{
int p = 1;
int result = 0;
while ( n > p )
{
p = p << MinMatch;
result += 1;
if ( result == 6 ) break;
}
return result;
}
private int SaveMatch ( int position, int length, int distance )
// Called from FindMatches to save a <length,distance> match. Returns position + length.
{
// System.Console.WriteLine( "SaveMatch at " + position + " length=" + length + " distance=" + distance );
int i = BufferWrite;
PositionBuffer[ i ] = position;
LengthBuffer[ i ] = (ushort) length;
DistanceBuffer[ i ] = (ushort) distance;
i = ( i + 1 ) & BufferMask;
if ( i == BufferRead ) OutputBlock( false );
BufferWrite = i;
position += length;
Buffered = position;
return position;
}
private bool OutputBlock( bool last )
{
int blockSize = Buffered - Finished; // Uncompressed size in bytes.
if ( blockSize > StartBlockSize )
{
blockSize = ( last && blockSize < StartBlockSize*2 ) ? blockSize >> 1 : StartBlockSize;
}
Block b;
int bits; // Compressed size in bits.
// While block construction fails, reduce blockSize.
while ( true )
{
b = new Block( this, blockSize, null, out bits );
if ( bits >= 0 ) break;
blockSize -= blockSize / 3;
}
// Investigate larger block size.
while ( b.End < Buffered && DynamicBlockSize )
{
// b2 is a block which starts just after b.
int bits2; Block b2 = new Block( this, blockSize, b, out bits2 );
if ( bits2 < 0 ) break;
// b3 is the block which encodes b and b2 together.
int bits3; Block b3 = new Block( this, b2.End - b.Start, null, out bits3 );
if ( bits3 < 0 ) break;
if ( bits3 > bits + bits2 ) break;
bits = bits3;
b = b3;
blockSize += blockSize;
}
// Output the block.
if ( b.End < Buffered ) last = false;
b.WriteBlock( this, last );
return last;
}
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;
}
private class Block
{
public readonly int Start, End; // Range of input encoded.
public Block( Deflator d, int blockSize, Block previous, out int bits )
// The block is not immediately output, to allow caller to try different block sizes.
// Instead, the number of bits neeed to encoded the block is returned ( excluding "extra" bits ).
{
Output = d.Output;
bits = -1;
if ( previous == null )
{
Start = d.Finished;
BufferStart = d.BufferRead;
}
else
{
Start = previous.End;
BufferStart = previous.BufferEnd;
}
int avail = d.Buffered - Start;
if ( blockSize > avail ) blockSize = avail;
End = TallyFrequencies( d, blockSize );
Lit.Used[ 256 ] += 1; // End of block code.
if ( Lit.ComputeCodes() || Dist.ComputeCodes() ) return;
if ( Dist.Count == 0 ) Dist.Count = 1;
// Compute length encoding.
DoLengthPass( 1 );
if ( Len.ComputeCodes() ) return;
// The length codes are permuted before being stored ( so that # of trailing zeroes is likely to be more ).
Len.Count = 19; while ( Len.Count > 4 && Len.Bits[ ClenAlphabet[ Len.Count - 1 ] ] == 0 ) Len.Count -= 1;
bits = 17 + 3 * Len.Count + Len.Total() + Lit.Total() + Dist.Total();
}
public void WriteBlock( Deflator d, bool last )
{
OutBitStream output = Output;
output.WriteBits( 1, last ? 1u : 0u );
output.WriteBits( 2, 2 );
output.WriteBits( 5, (uint)( Lit.Count - 257 ) );
output.WriteBits( 5, (uint)( Dist.Count - 1 ) );
output.WriteBits( 4, (uint)( Len.Count - 4 ) );
for ( int i = 0; i < Len.Count; i += 1 )
output.WriteBits( 3, Len.Bits[ ClenAlphabet[ i ] ] );
DoLengthPass( 2 );
PutCodes( d );
output.WriteBits( Lit.Bits[ 256 ], Lit.Codes[ 256 ] ); // End of block code
}
// Block private fields and constants.
private OutBitStream Output;
private int BufferStart, BufferEnd;
// Huffman codings : Lit = Literal or Match Code, Dist = Distance code, Len = Length code.
HuffmanCoding Lit = new HuffmanCoding(15,288), Dist = new HuffmanCoding(15,32), Len = new HuffmanCoding(7,19);
// Counts for code length encoding.
private int LengthPass, PreviousLength, ZeroRun, Repeat;
// RFC 1951 constants.
private readonly static byte [] ClenAlphabet = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
private readonly 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 };
private readonly 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 };
private readonly 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 };
private readonly 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 };
// Block private functions.
private int TallyFrequencies( Deflator d, int blockSize )
{
int position = Start;
int end = position + blockSize;
int bufferRead = BufferStart;
while ( position < end && bufferRead != d.BufferWrite )
{
int matchPosition = d.PositionBuffer[ bufferRead ];
if ( matchPosition >= end ) break;
int length = d.LengthBuffer[ bufferRead ];
int distance = d.DistanceBuffer[ bufferRead ];
bufferRead = ( bufferRead + 1 ) & d.BufferMask;
byte [] input = d.Input;
while ( position < matchPosition )
{
Lit.Used[ input[ position ] ] += 1;
position += 1;
}
position += length;
// Compute match and distance codes.
int mc = 0; while ( length >= MatchOff[ mc ] ) mc += 1; mc -= 1;
int dc = 29; while ( distance < DistOff[ dc ] ) dc -= 1;
Lit.Used[ 257 + mc ] += 1;
Dist.Used[ dc ] += 1;
}
while ( position < end )
{
Lit.Used[ d.Input[ position ] ] += 1;
position += 1;
}
BufferEnd = bufferRead;
return position;
}
private void PutCodes( Deflator d )
{
byte [] input = d.Input;
OutBitStream output = d.Output;
int position = Start;
int bufferRead = BufferStart;
while ( position < End && bufferRead != d.BufferWrite )
{
int matchPosition = d.PositionBuffer[ bufferRead ];
if ( matchPosition >= End ) break;
int length = d.LengthBuffer[ bufferRead ];
int distance = d.DistanceBuffer[ bufferRead ];
bufferRead = ( bufferRead + 1 ) & d.BufferMask;
while ( position < matchPosition )
{
byte b = d.Input[ position ];
output.WriteBits( Lit.Bits[ b ], Lit.Codes[ b ] );
position += 1;
}
position += length;
// Compute match and distance codes.
int mc = 0; while ( length >= MatchOff[ mc ] ) mc += 1; mc -= 1;
int dc = 29; while ( distance < DistOff[ dc ] ) dc -= 1;
output.WriteBits( Lit.Bits[ 257 + mc ], Lit.Codes[ 257 + mc ] );
output.WriteBits( MatchExtra[ mc ], (uint)(length-MatchOff[ mc ] ) );
output.WriteBits( Dist.Bits[ dc ], Dist.Codes[ dc ] );
output.WriteBits( DistExtra[ dc ], (uint)(distance-DistOff[ dc ] ) );
}
while ( position < End )
{
byte b = input[ position ];
output.WriteBits( Lit.Bits[ b ], Lit.Codes[ b ] );
position += 1;
}
d.BufferRead = bufferRead;
d.Finished = position;
}
// Run length encoding of code lengths - RFC 1951, page 13.
private void DoLengthPass( int pass )
{
LengthPass = pass;
EncodeLengths( Lit.Count, Lit.Bits, true );
EncodeLengths( Dist.Count, Dist.Bits, false );
}
private void PutLength( int code )
{
if ( LengthPass == 1 )
Len.Used[ code ] += 1;
else
Output.WriteBits( Len.Bits[ code ], Len.Codes[ code ] );
}
private void EncodeLengths( int n, byte [] lengths, bool isLit )
{
if ( isLit )
{
PreviousLength = 0;
ZeroRun = 0;
Repeat = 0;
}
for ( int i = 0; i < n; i += 1 )
{
int length = lengths[ i ];
if ( length == 0 )
{
EncodeRepeat();
ZeroRun += 1;
PreviousLength = 0;
}
else if ( length == PreviousLength )
{
Repeat += 1;
}
else
{
EncodeZeroRun();
EncodeRepeat();
PutLength( length );
PreviousLength = length;
}
}
if ( !isLit )
{
EncodeZeroRun();
EncodeRepeat();
}
}
private void EncodeRepeat()
{
while ( Repeat > 0 )
{
if ( Repeat < 3 )
{
PutLength( PreviousLength );
Repeat -= 1;
}
else
{
int x = Repeat;
if ( x > 6 ) x = 6;
PutLength( 16 );
if ( LengthPass == 2 )
{
Output.WriteBits( 2, (uint)( x - 3 ) );
}
Repeat -= x;
}
}
}
private void EncodeZeroRun()
{
while ( ZeroRun > 0 )
{
if ( ZeroRun < 3 )
{
PutLength( 0 );
ZeroRun -= 1;
}
else if ( ZeroRun < 11 )
{
PutLength( 17 );
if ( LengthPass == 2 ) Output.WriteBits( 3, (uint)( ZeroRun - 3 ) );
ZeroRun = 0;
}
else
{
int x = ZeroRun;
if ( x > 138 ) x = 138;
PutLength( 18 );
if ( LengthPass == 2 ) Output.WriteBits( 7, (uint)( x - 11 ) );
ZeroRun -= x;
}
}
}
} // end class Block
} // end class Deflator
// ******************************************************************************
struct HuffmanCoding // Variable length coding.
{
public int Count; // Number of used symbols.
public int [] Used; // Count of how many times a symbol is used in the block being encoded.
public byte [] Bits; // Number of bits used to encode a symbol.
public ushort [] Codes; // Huffman code for a symbol ( bit 0 is most significant ).
private int Limit; // Maxiumum number of bits for a code.
public HuffmanCoding( int limit, int symbols )
{
Limit = limit;
Count = symbols;
Used = new int[ symbols ];
Bits = new byte[ symbols ];
Codes = new ushort[ symbols ];
}
public int Total()
{
int result = 0, count = Count;
for ( int i = 0; i < count; i += 1 )
result += Used[i] * Bits[i];
return result;
}
public bool ComputeCodes() // returns true if Limit is exceeded.
{
int count = Count;
Heap<TreeNode> heap = new Heap<TreeNode>( count, TreeNode.LessThan );
for ( int i = 0; i < Count; i += 1 )
{
int used = Used[ i ];
if ( used > 0 ) heap.Insert( new Leaf( (ushort)i, used ) );
}
int maxBits = 0;
if ( heap.Count == 1 )
{
heap.Remove().GetBits( Bits, 1 );
maxBits = 1;
}
else if ( heap.Count > 1 )
{
do // Keep pairing the lowest frequency TreeNodes.
{
heap.Insert( new Branch( heap.Remove(), heap.Remove() ) );
} while ( heap.Count > 1 );
TreeNode root = heap.Remove();
maxBits = root.Depth;
if ( maxBits > Limit ) return true;
root.GetBits( Bits, 0 ); // Walk the tree to find the code lengths (Bits).
}
// Compute codes, code below is from RFC 1951 page 7.
int [] bl_count = new int[ maxBits + 1 ];
for ( int i = 0; i < count; i += 1 ) bl_count[ Bits[ 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 < count; i += 1 )
{
int length = Bits[ i ];
if ( length != 0 )
{
Codes[ i ] = (ushort)Reverse( next_code[ length ], length );
next_code[ length ] += 1;
}
}
// Reduce count if there are unused symbols.
while ( count > 0 && Bits[ count - 1 ] == 0 ) count -= 1;
Count = count;
//System.Console.WriteLine( "HuffEncoder.ComputeCodes" );
// for ( int i = 0; i < count; i += 1 ) if ( Bits[ i ] > 0 )
// System.Console.WriteLine( "i=" + i + " len=" + Bits[ i ] + " tc=" + Codes[ i ].ToString("X") + " freq=" + Used[ i ] );
return false;
}
private static int Reverse( int x, int bits )
// Reverse a string of bits ( ready to be output as Huffman code ).
{
int result = 0;
for ( int i = 0; i < bits; i += 1 )
{
result <<= 1;
result |= x & 1;
x >>= 1;
}
return result;
}
private abstract class TreeNode
{
public int Used;
public byte Depth;
public static bool LessThan( TreeNode a, TreeNode b )
{
return a.Used < b.Used || a.Used == b.Used && a.Depth < b.Depth;
}
public abstract void GetBits( byte [] nbits, int length );
}
private class Leaf : TreeNode
{
public ushort Code;
public Leaf( ushort code, int used )
{
Code = code;
Used = used;
}
public override void GetBits( byte [] nbits, int length )
{
nbits[ Code ] = (byte)length;
}
} // end class Leaf
private class Branch : TreeNode
{
TreeNode Left, Right;
public Branch( TreeNode left, TreeNode right )
{
Left = left;
Right = right;
Used = left.Used + right.Used;
Depth = (byte)( 1 + ( left.Depth > right.Depth ? left.Depth : right.Depth ) );
}
public override void GetBits( byte [] nbits, int length )
{
Left.GetBits( nbits, length + 1 );
Right.GetBits( nbits, length + 1 );
}
} // end class Branch
} // end struct HuffmanCoding
// ******************************************************************************
sealed class Heap<T> // An array organised so the smallest element can be efficiently removed.
{
public delegate bool DLessThan( T a, T b );
public int Count { get{ return _Count; } }
private int _Count;
private T [] Array;
private DLessThan LessThan;
public Heap ( int capacity, DLessThan lessThan )
{
Array = new T[ capacity ];
LessThan = lessThan;
}
public void Insert( T e )
{
int j = _Count++;
while ( j > 0 )
{
int p = ( j - 1 ) / 2; // Index of parent.
T pe = Array[ p ];
if ( !LessThan( e, pe ) ) break;
Array[ j ] = pe; // Demote parent.
j = p;
}
Array[ j ] = e;
}
public T Remove() // Returns the smallest element.
{
T result = Array[ 0 ];
_Count -= 1;
T e = Array[ _Count ];
Array[ _Count ] = default(T);
int j = 0;
while ( true )
{
int c = j * 2 + 1; if ( c >= _Count ) break;
T ce = Array[ c ];
if ( c + 1 < _Count )
{
T ce2 = Array[ c + 1 ];
if ( LessThan( ce2, ce ) ) { c += 1; ce = ce2; }
}
if ( !LessThan( ce, e ) ) break;
Array[ j ] = ce; j = c;
}
Array[ j ] = e;
return result;
}
} // end class Heap
// ******************************************************************************
abstract class OutBitStream
{
public void WriteBits( int n, ulong value )
// Write first n ( 0 <= n <= 64 ) bits of value to stream, least significant bit is written first.
// Unused bits of value must be zero, i.e. value must be in range 0 .. 2^n-1.
{
if ( n + BitsInWord >= WordCapacity )
{
Save( Word | value << BitsInWord );
int space = WordCapacity - BitsInWord;
value >>= space;
n -= space;
Word = 0;
BitsInWord = 0;
}
Word |= value << BitsInWord;
BitsInWord += n;
}
public void Pad( int n )
// Pad with zero bits to n bit boundary where n is power of 2 in range 1,2,4..64, typically n=8.
{
int w = BitsInWord % n;
if ( w > 0 ) WriteBits( n - w, 0 );
}
public abstract void Save( ulong word );
protected const int WordSize = sizeof(ulong); // Size of Word in bytes.
protected const int WordCapacity = WordSize * 8; // Number of bits that can be stored Word
protected ulong Word; // Bits are first stored in Word, when full, Word is saved.
protected int BitsInWord; // Number of bits currently stored in Word.
}
// ******************************************************************************
sealed class MemoryBitStream : OutBitStream
{
// ByteSize returns the current size in bytes.
// CopyTo copies the contents to a Stream.
// ToArray returns the contents as an array of bytes.
public int ByteSize()
{
return ( CompleteChunks * Chunk.Capacity + WordsInCurrentChunk ) * WordSize + ( BitsInWord + 7 ) / 8;
}
public void CopyTo( System.IO.Stream s )
{
byte [] buffer = new byte [ WordSize ];
for ( Chunk c = FirstChunk; c != null; c = c.Next )
{
int n = ( c == CurrentChunk ) ? WordsInCurrentChunk : Chunk.Capacity;
for ( int j = 0; j < n; j += 1 )
{
ulong w = c.Words[ j ];
unchecked
{
buffer[0] = (byte) w;
buffer[1] = (byte)( w >> 8 );
buffer[2] = (byte)( w >> 16 );
buffer[3] = (byte)( w >> 24 );
buffer[4] = (byte)( w >> 32 );
buffer[5] = (byte)( w >> 40 );
buffer[6] = (byte)( w >> 48 );
buffer[7] = (byte)( w >> 56 );
}
s.Write( buffer, 0, 8 );
}
}
int biw = BitsInWord;
ulong word = Word;
while ( biw > 0 )
{
s.WriteByte( unchecked( (byte) word ) );
word >>= 8;
biw -= 8;
}
}
public byte [] ToArray()
{
byte [] buffer = new byte[ ByteSize() ];
int i = 0;
for ( Chunk c = FirstChunk; c != null; c = c.Next )
{
int n = ( c == CurrentChunk ) ? WordsInCurrentChunk : Chunk.Capacity;
for ( int j = 0; j < n; j += 1 )
{
ulong w = c.Words[ j ];
unchecked
{
buffer[i++] = (byte) w;
buffer[i++] = (byte)( w >> 8 );
buffer[i++] = (byte)( w >> 16 );
buffer[i++] = (byte)( w >> 24 );
buffer[i++] = (byte)( w >> 32 );
buffer[i++] = (byte)( w >> 40 );
buffer[i++] = (byte)( w >> 48 );
buffer[i++] = (byte)( w >> 56 );
}
}
}
int biw = BitsInWord;
ulong word = Word;
while ( biw > 0 )
{
buffer[ i++ ] = unchecked( (byte) word );
word >>= 8;
biw -= 8;
}
return buffer;
}
public MemoryBitStream()
{
FirstChunk = new Chunk();
CurrentChunk = FirstChunk;
}
public override void Save( ulong word )
{
if ( WordsInCurrentChunk == Chunk.Capacity )
{
Chunk nc = new Chunk();
CurrentChunk.Next = nc;
CurrentChunk = nc;
CompleteChunks += 1;
WordsInCurrentChunk = 0;
}
CurrentChunk.Words[ WordsInCurrentChunk++ ] = word;
}
private int WordsInCurrentChunk; // Number of words stored in CurrentChunk.
private int CompleteChunks; // Number of complete Chunks.
private Chunk FirstChunk, CurrentChunk;
private class Chunk
{
public const int Capacity = 256;
public ulong [] Words = new ulong[ Capacity ];
public Chunk Next;
}
} // end class MemoryBitStream
} // namespace