// Very simple Deflater for educational purposes
//
// Limits:
//
// - ASCII characters only.
// - Maximum back reference is 4 characters, maximum length is 10 characters.
// - Buggy due to misunderstanding^Wlaziness of LSB/MSB on my part.
//
// Still, a string like 'BANANABANANABANANABANANABANANA' compresses 20%
public class Deflater(Stream stream)
{
private const int MinLength = 3;
private const int MaxLength = 4;
private const int MaxBackReference = 4;
public void Write(byte[] input)
{
var writer = new BitWriter(stream);
// begin of block 0b011 (LSB first)
writer.WriteBits(0b110, 3);
var position = 0;
while (position < input.Length)
{
// find a match
var (bestIndex, bestLength) = FindMatch(input, position);
if (bestLength >= MinLength)
{
// (length, distance)
var (length, distance) = (bestLength - MinLength + 1, position - bestIndex - 1);
// distance
writer.WriteBits((uint)length, 7);
writer.WriteBits((uint)distance, 5);
position += bestLength;
}
else
{
// literal
var literal = input[position] | 0b00110000; // Fixed Huffman
writer.WriteBits((uint)literal, 8);
position++;
}
}
// end of block
writer.WriteBits(0b0000000, 7);
writer.Flush();
}
private static (int BestIndex, int BestLength) FindMatch(byte[] input, int position)
{
var bestIndex = -1;
var bestLength = 0;
for (var i = Math.Max(0, position - MaxBackReference); i < position; i++)
{
var len = 0;
while (position + len < input.Length &&
input[i + len] == input[position + len] &&
len < MaxLength)
{
len++;
}
if (len <= bestLength)
{
continue;
}
bestLength = len;
bestIndex = i;
}
return (bestIndex, bestLength);
}
}
