namespace DbaMessageInserter;

internal readonly record struct DeflateToken(byte Literal, int Length, int Distance)
{
    public bool IsLiteral => Length == 0;

    public static DeflateToken FromLiteral(byte value)
    {
        return new DeflateToken(value, 0, 0);
    }

    public static DeflateToken FromMatch(int length, int distance)
    {
        return new DeflateToken(0, length, distance);
    }
}

/// <summary>
/// Readable greedy LZ77 matcher. A 3-byte hash chain is searched for at most
/// MaxChain candidates; this is intentionally simpler than production zlib.
/// </summary>
internal sealed class Lz77Matcher
{
    private const int WindowSize = 32_768;
    private const int MinimumMatch = 3;
    private const int MaximumMatch = 258;
    private const int HashSize = 65_536;

    private readonly byte[] _input;
    private readonly int[] _previousSameHash;
    private readonly int _maxChain;

    public Lz77Matcher(byte[] input, int maxChain = 128)
    {
        _input = input ?? throw new ArgumentNullException(nameof(input));

        if (maxChain <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(maxChain));
        }

        _maxChain = maxChain;
        _previousSameHash = BuildHashChains(input);
    }

    public List<DeflateToken> Tokenize(int offset, int length)
    {
        if (offset < 0 || length < 0 || offset > _input.Length - length)
        {
            throw new ArgumentOutOfRangeException(nameof(offset));
        }

        int end = offset + length;
        int position = offset;
        var tokens = new List<DeflateToken>(Math.Max(4, length / 2));

        while (position < end)
        {
            (int bestLength, int bestDistance) = FindBestMatch(position, end);

            if (bestLength >= MinimumMatch)
            {
                tokens.Add(DeflateToken.FromMatch(bestLength, bestDistance));
                position += bestLength;
            }
            else
            {
                tokens.Add(DeflateToken.FromLiteral(_input[position]));
                position++;
            }
        }

        return tokens;
    }

    private (int Length, int Distance) FindBestMatch(int position, int blockEnd)
    {
        int remaining = blockEnd - position;

        if (remaining < MinimumMatch || position + 2 >= _input.Length)
        {
            return (0, 0);
        }

        int maximumLength = Math.Min(MaximumMatch, remaining);
        int candidate = _previousSameHash[position];
        int checkedCandidates = 0;
        int bestLength = 0;
        int bestDistance = 0;

        while (candidate >= 0 && checkedCandidates < _maxChain)
        {
            int distance = position - candidate;

            if (distance > WindowSize)
            {
                // Hash chains move strictly backward, so all later candidates
                // are even farther away.
                break;
            }

            int matchLength = 0;

            // Overlapping matches are valid in DEFLATE. Reading from the known
            // original input makes this comparison straightforward.
            while (matchLength < maximumLength &&
                   _input[candidate + matchLength] == _input[position + matchLength])
            {
                matchLength++;
            }

            if (matchLength >= MinimumMatch && matchLength > bestLength)
            {
                bestLength = matchLength;
                bestDistance = distance;

                if (bestLength == maximumLength)
                {
                    break;
                }
            }

            candidate = _previousSameHash[candidate];
            checkedCandidates++;
        }

        return (bestLength, bestDistance);
    }

    private static int[] BuildHashChains(byte[] input)
    {
        var previous = new int[input.Length];
        Array.Fill(previous, -1);

        var head = new int[HashSize];
        Array.Fill(head, -1);

        for (int position = 0; position + 2 < input.Length; position++)
        {
            int hash = Hash3(input, position);
            previous[position] = head[hash];
            head[hash] = position;
        }

        return previous;
    }

    private static int Hash3(byte[] input, int position)
    {
        uint value = input[position];
        value = value * 257u + input[position + 1];
        value = value * 257u + input[position + 2];
        value ^= value >> 9;
        return (int)(value & (HashSize - 1));
    }
}
