namespace AssetExtractor;

/// <summary>
/// Decoder for the LZHUF format (LZSS + adaptive Huffman, Okumura/Yoshizaki 1988),
/// as written by the Delphi TLZRW1 component in "Good" mode.
/// Stream layout: [4B magic "LZH!" = 0x4C5A4821 LE][4B LE original size][LZHUF bitstream].
/// </summary>
public static class Lzh
{
    public const uint LzhMagic = (((((uint)'L' << 8) + 'Z') << 8) + 'H' << 8) + '!';

    const int N = 4096;           // ring buffer size
    const int F = 60;             // lookahead buffer size
    const int Threshold = 2;
    const int NChar = 256 - Threshold + F;  // 314 character codes
    const int T = NChar * 2 - 1;  // 627, size of freq table
    const int R = T - 1;          // 626, root position
    const int MaxFreq = 0x8000;

    // Tables for decoding the upper 6 bits of the match position
    static readonly byte[] DCode = BuildDCode();
    static readonly byte[] DLen = BuildDLen();

    static byte[] BuildDCode()
    {
        // Canonical LZHUF d_code table: value 0 ×32; 1..3 ×16; 4..11 ×8; 12..23 ×4; 24..47 ×2; 48..63 ×1
        var t = new byte[256];
        int i = 0, v = 0;
        foreach (var (values, run) in new[] { (1, 32), (3, 16), (8, 8), (12, 4), (24, 2), (16, 1) })
            for (int g = 0; g < values; g++, v++)
                for (int k = 0; k < run; k++)
                    t[i++] = (byte)v;
        return t;
    }

    static byte[] BuildDLen()
    {
        // Canonical LZHUF d_len table: 3 ×32, 4 ×48, 5 ×64, 6 ×48, 7 ×48, 8 ×16
        var t = new byte[256];
        int i = 0;
        foreach (var (count, val) in new[] { (32, 3), (48, 4), (64, 5), (48, 6), (48, 7), (16, 8) })
            for (int k = 0; k < count; k++)
                t[i++] = (byte)val;
        return t;
    }

    public static byte[] Decompress(byte[] file)
    {
        if (file.Length < 8 || BitConverter.ToUInt32(file, 0) != LzhMagic)
            throw new InvalidDataException("Not an LZH!-compressed TLZRW1 stream.");
        int origSize = BitConverter.ToInt32(file, 4);
        return Decode(file, 8, origSize);
    }

    static byte[] Decode(byte[] src, int srcOffset, int origSize)
    {
        var output = new byte[origSize];
        int outPos = 0;

        // adaptive Huffman state
        var freq = new int[T + 1];
        var prnt = new int[T + NChar];
        var son = new int[T];

        // init tree
        for (int i = 0; i < NChar; i++)
        {
            freq[i] = 1;
            son[i] = i + T;
            prnt[i + T] = i;
        }
        for (int i = 0, j = NChar; j <= R; i += 2, j++)
        {
            freq[j] = freq[i] + freq[i + 1];
            son[j] = i;
            prnt[i] = j;
            prnt[i + 1] = j;
        }
        freq[T] = 0xFFFF;
        prnt[R] = 0;

        // ring buffer, initialized to spaces
        var ring = new byte[N + F - 1];
        Array.Fill(ring, (byte)0x20);
        int r = N - F;

        // bit reader
        int srcPos = srcOffset;
        uint getbuf = 0;
        int getlen = 0;

        int GetBit()
        {
            while (getlen <= 8)
            {
                uint b = srcPos < src.Length ? src[srcPos++] : 0u;
                getbuf |= b << (8 - getlen);
                getlen += 8;
            }
            int result = (int)((getbuf >> 15) & 1);
            getbuf = (getbuf << 1) & 0xFFFF;
            getlen--;
            return result;
        }

        int GetByte()
        {
            while (getlen <= 8)
            {
                uint b = srcPos < src.Length ? src[srcPos++] : 0u;
                getbuf |= b << (8 - getlen);
                getlen += 8;
            }
            int result = (int)((getbuf >> 8) & 0xFF);
            getbuf = (getbuf << 8) & 0xFFFF;
            getlen -= 8;
            return result;
        }

        void Update(int c)
        {
            if (freq[R] == MaxFreq)
                Reconstruct();

            c = prnt[c + T];
            do
            {
                int k = ++freq[c];
                // if order is disturbed, swap nodes
                int l = c + 1;
                if (k > freq[l])
                {
                    while (k > freq[l + 1]) l++;
                    freq[c] = freq[l];
                    freq[l] = k;

                    int i = son[c];
                    prnt[i] = l;
                    if (i < T) prnt[i + 1] = l;

                    int j = son[l];
                    son[l] = i;

                    prnt[j] = c;
                    if (j < T) prnt[j + 1] = c;
                    son[c] = j;

                    c = l;
                }
                c = prnt[c];
            } while (c != 0);
        }

        void Reconstruct()
        {
            // collect leaf nodes, halve frequencies
            int j = 0;
            for (int i = 0; i < T; i++)
            {
                if (son[i] >= T)
                {
                    freq[j] = (freq[i] + 1) / 2;
                    son[j] = son[i];
                    j++;
                }
            }
            // rebuild internal nodes
            for (int i = 0, k = NChar; k < T; i += 2, k++)
            {
                int f = freq[i] + freq[i + 1];
                int l = k;
                while (f < freq[l - 1]) l--;
                Array.Copy(freq, l, freq, l + 1, k - l);
                freq[l] = f;
                Array.Copy(son, l, son, l + 1, k - l);
                son[l] = i;
            }
            // reconnect parent pointers
            for (int i = 0; i < T; i++)
            {
                int k = son[i];
                prnt[k] = i;
                if (k < T) prnt[k + 1] = i;
            }
        }

        int DecodeChar()
        {
            int c = son[R];
            while (c < T)
                c = son[c + GetBit()];
            c -= T;
            Update(c);
            return c;
        }

        int DecodePosition()
        {
            // upper 6 bits from table
            int i = GetByte();
            int c = DCode[i] << 6;
            int j = DLen[i] - 2;
            // read lower 6 bits verbatim
            while (j-- > 0)
                i = (i << 1) + GetBit();
            return c | (i & 0x3F);
        }

        while (outPos < origSize)
        {
            int c = DecodeChar();
            if (c < 256)
            {
                output[outPos++] = (byte)c;
                ring[r] = (byte)c;
                r = (r + 1) & (N - 1);
            }
            else
            {
                int pos = (r - DecodePosition() - 1) & (N - 1);
                int len = c - 255 + Threshold;
                for (int k = 0; k < len && outPos < origSize; k++)
                {
                    byte b = ring[(pos + k) & (N - 1)];
                    output[outPos++] = b;
                    ring[r] = b;
                    r = (r + 1) & (N - 1);
                }
            }
        }

        return output;
    }
}