// 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 cursor = 0;
        while (cursor < input.Length)
        {
            // find a match
            var bestIndex = -1;
            var bestLength = 0;

            for (var i = Math.Max(0, cursor - MaxBackReference); i < cursor; i++)
            {
                var len = 0;
                while (cursor + len < input.Length &&
                       input[i + len] == input[cursor + len] &&
                       len < MaxLength)
                {
                    len++;
                }

                if (len <= bestLength)
                {
                    continue;
                }

                bestLength = len;
                bestIndex = i;
            }

            if (bestLength >= MinLength)
            {
                // (length, distance)
                var length = bestLength - MinLength + 1;
                var distance = (uint)(cursor - bestIndex - 1);

                // distance
                writer.WriteBits((uint)length, 7);
                writer.WriteBits(distance, 5);

                cursor += bestLength;
            }
            else
            {
                // literal
                var literal = (uint)(input[cursor] + 48); // Fixed Huffman
                writer.WriteBits(literal, 8);
                cursor++;
            }
        }

        // end of block
        writer.WriteBits(0b0000000, 7);

        writer.Flush();
    }
}