namespace DbaMessageInserter;

public sealed record DeflateBlockLog(
    int Index,
    DeflateBlockType RequestedType,
    DeflateBlockType Type,
    bool IsFinal,
    int InputOffset,
    int InputLength,
    long StartBit,
    long EndBit,
    int DbaBitCapacity,
    int DbaPayloadBitsWritten,
    long? StoredCandidateBits,
    long? FixedCandidateBits,
    long? DynamicCandidateBits)
{
    public long EncodedBitLength => EndBit - StartBit;
    public long DbaStartBit => StartBit + 3;
    public bool WasAutomaticallySelected => RequestedType == DeflateBlockType.Auto;
}

public sealed record RawDeflateResult(
    byte[] CompressedBytes,
    IReadOnlyList<DeflateBlockLog> Blocks,
    long MeaningfulEndBit,
    long BytePaddedEndBit,
    int TotalDbaCapacityBits,
    int TotalDbaPayloadBitsWritten);

/// <summary>
/// Raw-DEFLATE encoder with explicit physical block control.
///
/// For an Auto data block, this encoder:
/// 1. creates one shared greedy-LZ77 token stream,
/// 2. builds a block-specific, length-limited Dynamic Huffman tree,
/// 3. calculates the exact Stored, Fixed, and Dynamic bit counts, including
///    the Stored block's current-position alignment padding,
/// 4. writes the smallest candidate.
///
/// NPNCB/DBA handling is unchanged: DBA bits are written immediately after the
/// three-bit BFINAL/BTYPE=00 header and before LEN=0/NLEN=0xFFFF.
/// </summary>
public static class RawDeflateEncoder
{
    private static readonly int[] LengthBases =
    {
        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
    };

    private static readonly int[] LengthExtraBits =
    {
        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 static readonly int[] DistanceBases =
    {
        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
    };

    private static readonly int[] DistanceExtraBits =
    {
        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 static readonly int[] CodeLengthAlphabetOrder =
    {
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
        11, 4, 12, 3, 13, 2, 14, 1, 15
    };

    private static readonly byte[] FixedLiteralLengthCodeLengths =
        BuildFixedLiteralLengthCodeLengths();

    private static readonly byte[] FixedDistanceCodeLengths =
        Enumerable.Repeat((byte)5, 32).ToArray();

    private static readonly HuffmanTable FixedLiteralLengthTable =
        HuffmanTable.FromCodeLengths(FixedLiteralLengthCodeLengths, 15);

    private static readonly HuffmanTable FixedDistanceTable =
        HuffmanTable.FromCodeLengths(FixedDistanceCodeLengths, 15);

    public static RawDeflateResult Encode(
        byte[] input,
        IReadOnlyList<DeflateBlockSpec> plan)
    {
        return Encode(input, plan, ReadOnlySpan<byte>.Empty);
    }

    /// <summary>
    /// dbaPayloadBytes are consumed LSB-first only by NPNCB alignment areas.
    /// Unused DBA positions are explicitly filled with zero.
    /// </summary>
    public static RawDeflateResult Encode(
        byte[] input,
        IReadOnlyList<DeflateBlockSpec> plan,
        ReadOnlySpan<byte> dbaPayloadBytes)
    {
        if (input is null) throw new ArgumentNullException(nameof(input));
        if (plan is null) throw new ArgumentNullException(nameof(plan));
        DeflateBlockPlanner.Validate(plan, input.Length);

        var matcher = new Lz77Matcher(input);
        using var output = new MemoryStream();
        var writer = new BitWriter(output);
        var logs = new List<DeflateBlockLog>(plan.Count);
        int dbaPayloadBitIndex = 0;
        int totalDbaCapacityBits = 0;
        int totalDbaPayloadBitsWritten = 0;

        for (int index = 0; index < plan.Count; index++)
        {
            DeflateBlockSpec block = plan[index];
            bool isFinal = index == plan.Count - 1;
            long startBit = writer.BitPosition;
            int dbaBitCapacity = 0;
            int dbaPayloadBitsWritten = 0;
            long? storedCandidateBits = null;
            long? fixedCandidateBits = null;
            long? dynamicCandidateBits = null;
            DeflateBlockType actualType = block.Type;

            switch (block.Type)
            {
                case DeflateBlockType.Auto:
                {
                    AdaptiveBlockDecision decision = AnalyzeAdaptiveBlock(
                        matcher,
                        block.Offset,
                        block.Length,
                        startBit);

                    actualType = decision.SelectedType;
                    storedCandidateBits = decision.StoredBits;
                    fixedCandidateBits = decision.FixedBits;
                    dynamicCandidateBits = decision.DynamicBits;

                    WriteAdaptiveDecision(writer, input, block, isFinal, decision);
                    break;
                }

                case DeflateBlockType.Stored:
                    WriteStoredBlock(
                        writer,
                        input.AsSpan(block.Offset, block.Length),
                        isFinal);
                    break;

                case DeflateBlockType.Fixed:
                    WriteCompressedBlock(
                        writer,
                        matcher.Tokenize(block.Offset, block.Length),
                        FixedLiteralLengthTable,
                        FixedDistanceTable,
                        btype: 1,
                        isFinal: isFinal,
                        dynamicPlan: null);
                    break;

                case DeflateBlockType.Dynamic:
                {
                    List<DeflateToken> tokens = matcher.Tokenize(block.Offset, block.Length);
                    DynamicBlockPlan dynamicPlan = DynamicBlockPlan.Build(tokens);
                    WriteCompressedBlock(
                        writer,
                        tokens,
                        dynamicPlan.LiteralLengthTable,
                        dynamicPlan.DistanceTable,
                        btype: 2,
                        isFinal: isFinal,
                        dynamicPlan: dynamicPlan);
                    break;
                }

                case DeflateBlockType.Npncb:
                    (dbaBitCapacity, dbaPayloadBitsWritten) = WriteNpncbBlock(
                        writer,
                        isFinal,
                        dbaPayloadBytes,
                        ref dbaPayloadBitIndex);
                    totalDbaCapacityBits = checked(totalDbaCapacityBits + dbaBitCapacity);
                    totalDbaPayloadBitsWritten = checked(
                        totalDbaPayloadBitsWritten + dbaPayloadBitsWritten);
                    break;

                default:
                    throw new ArgumentOutOfRangeException(nameof(block.Type));
            }

            long endBit = writer.BitPosition;

            if (block.Type == DeflateBlockType.Auto)
            {
                long expectedBits = actualType switch
                {
                    DeflateBlockType.Stored => storedCandidateBits!.Value,
                    DeflateBlockType.Fixed => fixedCandidateBits!.Value,
                    DeflateBlockType.Dynamic => dynamicCandidateBits!.Value,
                    _ => throw new InvalidOperationException("Auto selected a non-data block.")
                };

                if (endBit - startBit != expectedBits)
                {
                    throw new InvalidOperationException(
                        $"Adaptive cost mismatch: expected {expectedBits} bits, wrote {endBit - startBit} bits.");
                }
            }

            logs.Add(new DeflateBlockLog(
                index,
                block.Type,
                actualType,
                isFinal,
                block.Offset,
                block.Length,
                startBit,
                endBit,
                dbaBitCapacity,
                dbaPayloadBitsWritten,
                storedCandidateBits,
                fixedCandidateBits,
                dynamicCandidateBits));
        }

        int totalPayloadBits = checked(dbaPayloadBytes.Length * 8);
        if (dbaPayloadBitIndex != totalPayloadBits)
        {
            throw new ArgumentException(
                $"The DBA payload needs {totalPayloadBits} bits, but the block plan provides only {totalDbaCapacityBits} bits.",
                nameof(dbaPayloadBytes));
        }

        long meaningfulEndBit = writer.BitPosition;
        writer.AlignToByte();
        long bytePaddedEndBit = writer.BitPosition;

        return new RawDeflateResult(
            output.ToArray(),
            logs,
            meaningfulEndBit,
            bytePaddedEndBit,
            totalDbaCapacityBits,
            totalDbaPayloadBitsWritten);
    }

    private static AdaptiveBlockDecision AnalyzeAdaptiveBlock(
        Lz77Matcher matcher,
        int offset,
        int length,
        long startBit)
    {
        List<DeflateToken> tokens = matcher.Tokenize(offset, length);
        DynamicBlockPlan dynamicPlan = DynamicBlockPlan.Build(tokens);

        long storedBits = GetStoredBlockBitLength(startBit, length);
        long fixedBits = checked(
            3L + GetCompressedPayloadBitLength(
                tokens,
                FixedLiteralLengthTable,
                FixedDistanceTable));
        long dynamicBits = checked(
            3L + dynamicPlan.HeaderBitLength +
            GetCompressedPayloadBitLength(
                tokens,
                dynamicPlan.LiteralLengthTable,
                dynamicPlan.DistanceTable));

        // Strictly smaller candidates replace the current winner. Therefore a
        // tie is resolved Stored -> Fixed -> Dynamic. The output size is equal
        // in a tie; retaining the simpler earlier representation is deliberate.
        DeflateBlockType selectedType = DeflateBlockType.Stored;
        long selectedBits = storedBits;

        if (fixedBits < selectedBits)
        {
            selectedType = DeflateBlockType.Fixed;
            selectedBits = fixedBits;
        }

        if (dynamicBits < selectedBits)
        {
            selectedType = DeflateBlockType.Dynamic;
        }

        return new AdaptiveBlockDecision(
            selectedType,
            tokens,
            dynamicPlan,
            storedBits,
            fixedBits,
            dynamicBits);
    }

    private static void WriteAdaptiveDecision(
        BitWriter writer,
        byte[] input,
        DeflateBlockSpec block,
        bool isFinal,
        AdaptiveBlockDecision decision)
    {
        switch (decision.SelectedType)
        {
            case DeflateBlockType.Stored:
                WriteStoredBlock(
                    writer,
                    input.AsSpan(block.Offset, block.Length),
                    isFinal);
                break;

            case DeflateBlockType.Fixed:
                WriteCompressedBlock(
                    writer,
                    decision.Tokens,
                    FixedLiteralLengthTable,
                    FixedDistanceTable,
                    btype: 1,
                    isFinal: isFinal,
                    dynamicPlan: null);
                break;

            case DeflateBlockType.Dynamic:
                WriteCompressedBlock(
                    writer,
                    decision.Tokens,
                    decision.DynamicPlan.LiteralLengthTable,
                    decision.DynamicPlan.DistanceTable,
                    btype: 2,
                    isFinal: isFinal,
                    dynamicPlan: decision.DynamicPlan);
                break;

            default:
                throw new InvalidOperationException("Adaptive selection returned a non-data block.");
        }
    }

    private static long GetStoredBlockBitLength(long startBit, int dataLength)
    {
        if (startBit < 0) throw new ArgumentOutOfRangeException(nameof(startBit));
        if (dataLength < 0 || dataLength > ushort.MaxValue)
            throw new ArgumentOutOfRangeException(nameof(dataLength));

        long afterHeader = checked(startBit + 3L);
        int alignmentBits = (int)((8L - (afterHeader & 7L)) & 7L);
        return checked(3L + alignmentBits + 32L + 8L * dataLength);
    }

    private static long GetCompressedPayloadBitLength(
        IReadOnlyList<DeflateToken> tokens,
        HuffmanTable literalLengthTable,
        HuffmanTable distanceTable)
    {
        long bits = 0;

        foreach (DeflateToken token in tokens)
        {
            if (token.IsLiteral)
            {
                bits = checked(bits + literalLengthTable.Lengths[token.Literal]);
                continue;
            }

            GetLengthEncoding(
                token.Length,
                out int lengthSymbol,
                out _,
                out int lengthExtraBitCount);
            GetDistanceEncoding(
                token.Distance,
                out int distanceSymbol,
                out _,
                out int distanceExtraBitCount);

            bits = checked(
                bits +
                literalLengthTable.Lengths[lengthSymbol] +
                lengthExtraBitCount +
                distanceTable.Lengths[distanceSymbol] +
                distanceExtraBitCount);
        }

        return checked(bits + literalLengthTable.Lengths[256]);
    }

    private static (int CapacityBits, int PayloadBitsWritten) WriteNpncbBlock(
        BitWriter writer,
        bool isFinal,
        ReadOnlySpan<byte> dbaPayloadBytes,
        ref int dbaPayloadBitIndex)
    {
        // NPNCB: BFINAL/BTYPE=00, DBA, LEN=0x0000, NLEN=0xFFFF.
        WriteBlockHeader(writer, isFinal, btype: 0);
        int capacityBits = writer.BitsUntilByteBoundary;
        int payloadBitsWritten = 0;
        int totalPayloadBits = checked(dbaPayloadBytes.Length * 8);

        for (int i = 0; i < capacityBits; i++)
        {
            uint bit = 0;
            if (dbaPayloadBitIndex < totalPayloadBits)
            {
                int byteIndex = dbaPayloadBitIndex >> 3;
                int bitIndex = dbaPayloadBitIndex & 7;
                bit = (uint)((dbaPayloadBytes[byteIndex] >> bitIndex) & 1);
                dbaPayloadBitIndex++;
                payloadBitsWritten++;
            }

            // Actual DBA write. Remaining slots stay zero.
            writer.WriteBits(bit, 1);
        }

        if (!writer.IsByteAligned)
            throw new InvalidOperationException("NPNCB DBA did not end byte-aligned.");

        writer.WriteUInt16LittleEndian(0x0000);
        writer.WriteUInt16LittleEndian(0xFFFF);
        return (capacityBits, payloadBitsWritten);
    }

    private static void WriteStoredBlock(
        BitWriter writer,
        ReadOnlySpan<byte> data,
        bool isFinal)
    {
        if (data.Length > ushort.MaxValue)
        {
            throw new ArgumentOutOfRangeException(
                nameof(data),
                "A Stored block is limited to 65535 bytes.");
        }

        WriteBlockHeader(writer, isFinal, btype: 0);
        writer.AlignToByte();

        ushort length = (ushort)data.Length;
        ushort complement = (ushort)~length;

        writer.WriteUInt16LittleEndian(length);
        writer.WriteUInt16LittleEndian(complement);
        writer.WriteAlignedBytes(data);
    }

    private static void WriteCompressedBlock(
        BitWriter writer,
        IReadOnlyList<DeflateToken> tokens,
        HuffmanTable literalLengthTable,
        HuffmanTable distanceTable,
        int btype,
        bool isFinal,
        DynamicBlockPlan? dynamicPlan)
    {
        WriteBlockHeader(writer, isFinal, btype);

        if (btype == 2)
        {
            if (dynamicPlan is null)
                throw new ArgumentNullException(nameof(dynamicPlan));
            dynamicPlan.WriteHeader(writer);
        }
        else if (dynamicPlan is not null)
        {
            throw new ArgumentException("A Dynamic plan is valid only for BTYPE=10.", nameof(dynamicPlan));
        }

        foreach (DeflateToken token in tokens)
        {
            if (token.IsLiteral)
            {
                literalLengthTable.WriteSymbol(writer, token.Literal);
                continue;
            }

            GetLengthEncoding(
                token.Length,
                out int lengthSymbol,
                out int lengthExtraValue,
                out int lengthExtraBits);

            literalLengthTable.WriteSymbol(writer, lengthSymbol);
            writer.WriteBits((uint)lengthExtraValue, lengthExtraBits);

            GetDistanceEncoding(
                token.Distance,
                out int distanceSymbol,
                out int distanceExtraValue,
                out int distanceExtraBits);

            distanceTable.WriteSymbol(writer, distanceSymbol);
            writer.WriteBits((uint)distanceExtraValue, distanceExtraBits);
        }

        literalLengthTable.WriteSymbol(writer, 256); // End-of-block.
    }

    private static void WriteBlockHeader(BitWriter writer, bool isFinal, int btype)
    {
        writer.WriteBits(isFinal ? 1u : 0u, 1); // BFINAL
        writer.WriteBits((uint)btype, 2);        // BTYPE, LSB first
    }

    private static void GetLengthEncoding(
        int length,
        out int symbol,
        out int extraValue,
        out int extraBits)
    {
        if (length < 3 || length > 258)
            throw new ArgumentOutOfRangeException(nameof(length));

        for (int index = 0; index < LengthBases.Length; index++)
        {
            int baseLength = LengthBases[index];
            int bitCount = LengthExtraBits[index];
            int maximum = baseLength + (bitCount == 0 ? 0 : (1 << bitCount) - 1);

            if (length <= maximum)
            {
                symbol = 257 + index;
                extraValue = length - baseLength;
                extraBits = bitCount;
                return;
            }
        }

        throw new InvalidOperationException("No DEFLATE length code was found.");
    }

    private static void GetDistanceEncoding(
        int distance,
        out int symbol,
        out int extraValue,
        out int extraBits)
    {
        if (distance < 1 || distance > 32_768)
            throw new ArgumentOutOfRangeException(nameof(distance));

        for (int index = 0; index < DistanceBases.Length; index++)
        {
            int baseDistance = DistanceBases[index];
            int bitCount = DistanceExtraBits[index];
            int maximum = baseDistance + (bitCount == 0 ? 0 : (1 << bitCount) - 1);

            if (distance <= maximum)
            {
                symbol = index;
                extraValue = distance - baseDistance;
                extraBits = bitCount;
                return;
            }
        }

        throw new InvalidOperationException("No DEFLATE distance code was found.");
    }

    private static byte[] BuildFixedLiteralLengthCodeLengths()
    {
        var lengths = new byte[288];

        for (int symbol = 0; symbol <= 143; symbol++) lengths[symbol] = 8;
        for (int symbol = 144; symbol <= 255; symbol++) lengths[symbol] = 9;
        for (int symbol = 256; symbol <= 279; symbol++) lengths[symbol] = 7;
        for (int symbol = 280; symbol <= 287; symbol++) lengths[symbol] = 8;

        return lengths;
    }

    private static void EnsureAtLeastTwoActiveSymbols(
        long[] frequencies,
        IReadOnlyList<int> preferredDummyOrder)
    {
        int activeCount = 0;
        foreach (long frequency in frequencies)
        {
            if (frequency > 0) activeCount++;
        }

        foreach (int symbol in preferredDummyOrder)
        {
            if (activeCount >= 2) return;
            if (symbol < 0 || symbol >= frequencies.Length)
                throw new ArgumentOutOfRangeException(nameof(preferredDummyOrder));
            if (frequencies[symbol] != 0) continue;

            frequencies[symbol] = 1;
            activeCount++;
        }

        if (activeCount < 2)
            throw new InvalidOperationException("Could not add enough dummy Huffman symbols.");
    }

    private static int FindLastNonZero(IReadOnlyList<byte> values)
    {
        for (int index = values.Count - 1; index >= 0; index--)
        {
            if (values[index] != 0) return index;
        }

        return -1;
    }

    private static List<CodeLengthRleToken> EncodeCodeLengths(
        IReadOnlyList<byte> codeLengths)
    {
        var result = new List<CodeLengthRleToken>();
        int index = 0;

        while (index < codeLengths.Count)
        {
            byte value = codeLengths[index];
            int runLength = 1;

            while (index + runLength < codeLengths.Count &&
                   codeLengths[index + runLength] == value)
            {
                runLength++;
            }

            if (value == 0)
            {
                int remaining = runLength;

                while (remaining >= 11)
                {
                    int count = Math.Min(remaining, 138);
                    int remainder = remaining - count;

                    // Avoid leaving one or two literal zeros after a long run
                    // when the remainder can instead be encoded by symbol 17.
                    if (remainder is 1 or 2)
                        count -= 3 - remainder;

                    result.Add(new CodeLengthRleToken(18, count - 11, 7));
                    remaining -= count;
                }

                if (remaining >= 3)
                {
                    int count = Math.Min(remaining, 10);
                    result.Add(new CodeLengthRleToken(17, count - 3, 3));
                    remaining -= count;
                }

                while (remaining-- > 0)
                    result.Add(new CodeLengthRleToken(0, 0, 0));
            }
            else
            {
                result.Add(new CodeLengthRleToken(value, 0, 0));
                int remaining = runLength - 1;

                while (remaining >= 3)
                {
                    int count = Math.Min(remaining, 6);
                    result.Add(new CodeLengthRleToken(16, count - 3, 2));
                    remaining -= count;
                }

                while (remaining-- > 0)
                    result.Add(new CodeLengthRleToken(value, 0, 0));
            }

            index += runLength;
        }

        return result;
    }

    private sealed record AdaptiveBlockDecision(
        DeflateBlockType SelectedType,
        IReadOnlyList<DeflateToken> Tokens,
        DynamicBlockPlan DynamicPlan,
        long StoredBits,
        long FixedBits,
        long DynamicBits);

    private sealed record CodeLengthRleToken(
        int Symbol,
        int ExtraValue,
        int ExtraBitCount);

    private sealed class DynamicBlockPlan
    {
        private DynamicBlockPlan(
            int literalLengthCodeCount,
            int distanceCodeCount,
            int codeLengthCodeCount,
            byte[] codeLengthAlphabetLengths,
            IReadOnlyList<CodeLengthRleToken> encodedCodeLengths,
            HuffmanTable literalLengthTable,
            HuffmanTable distanceTable,
            HuffmanTable codeLengthAlphabetTable,
            long headerBitLength)
        {
            LiteralLengthCodeCount = literalLengthCodeCount;
            DistanceCodeCount = distanceCodeCount;
            CodeLengthCodeCount = codeLengthCodeCount;
            CodeLengthAlphabetLengths = codeLengthAlphabetLengths;
            EncodedCodeLengths = encodedCodeLengths;
            LiteralLengthTable = literalLengthTable;
            DistanceTable = distanceTable;
            CodeLengthAlphabetTable = codeLengthAlphabetTable;
            HeaderBitLength = headerBitLength;
        }

        public int LiteralLengthCodeCount { get; }
        public int DistanceCodeCount { get; }
        public int CodeLengthCodeCount { get; }
        public byte[] CodeLengthAlphabetLengths { get; }
        public IReadOnlyList<CodeLengthRleToken> EncodedCodeLengths { get; }
        public HuffmanTable LiteralLengthTable { get; }
        public HuffmanTable DistanceTable { get; }
        public HuffmanTable CodeLengthAlphabetTable { get; }
        public long HeaderBitLength { get; }

        public static DynamicBlockPlan Build(IReadOnlyList<DeflateToken> tokens)
        {
            var literalLengthFrequencies = new long[286];
            var distanceFrequencies = new long[30];

            foreach (DeflateToken token in tokens)
            {
                if (token.IsLiteral)
                {
                    literalLengthFrequencies[token.Literal]++;
                    continue;
                }

                GetLengthEncoding(
                    token.Length,
                    out int lengthSymbol,
                    out _,
                    out _);
                GetDistanceEncoding(
                    token.Distance,
                    out int distanceSymbol,
                    out _,
                    out _);

                literalLengthFrequencies[lengthSymbol]++;
                distanceFrequencies[distanceSymbol]++;
            }

            literalLengthFrequencies[256]++; // End-of-block.
            EnsureAtLeastTwoActiveSymbols(
                literalLengthFrequencies,
                Enumerable.Range(0, literalLengthFrequencies.Length).ToArray());
            EnsureAtLeastTwoActiveSymbols(
                distanceFrequencies,
                Enumerable.Range(0, distanceFrequencies.Length).ToArray());

            byte[] literalLengthCodeLengths =
                LengthLimitedHuffmanBuilder.Build(literalLengthFrequencies, 15);
            byte[] distanceCodeLengths =
                LengthLimitedHuffmanBuilder.Build(distanceFrequencies, 15);

            int literalLengthCodeCount = Math.Max(
                257,
                FindLastNonZero(literalLengthCodeLengths) + 1);
            int distanceCodeCount = Math.Max(
                1,
                FindLastNonZero(distanceCodeLengths) + 1);

            var combinedCodeLengths = new byte[
                checked(literalLengthCodeCount + distanceCodeCount)];
            Array.Copy(
                literalLengthCodeLengths,
                0,
                combinedCodeLengths,
                0,
                literalLengthCodeCount);
            Array.Copy(
                distanceCodeLengths,
                0,
                combinedCodeLengths,
                literalLengthCodeCount,
                distanceCodeCount);

            List<CodeLengthRleToken> encodedCodeLengths =
                EncodeCodeLengths(combinedCodeLengths);
            var codeLengthFrequencies = new long[19];

            foreach (CodeLengthRleToken token in encodedCodeLengths)
                codeLengthFrequencies[token.Symbol]++;

            EnsureAtLeastTwoActiveSymbols(
                codeLengthFrequencies,
                CodeLengthAlphabetOrder);

            byte[] codeLengthAlphabetLengths =
                LengthLimitedHuffmanBuilder.Build(codeLengthFrequencies, 7);
            int codeLengthCodeCount = 4;

            for (int orderIndex = CodeLengthAlphabetOrder.Length - 1;
                 orderIndex >= 4;
                 orderIndex--)
            {
                if (codeLengthAlphabetLengths[CodeLengthAlphabetOrder[orderIndex]] != 0)
                {
                    codeLengthCodeCount = orderIndex + 1;
                    break;
                }
            }

            HuffmanTable literalLengthTable =
                HuffmanTable.FromCodeLengths(literalLengthCodeLengths, 15);
            HuffmanTable distanceTable =
                HuffmanTable.FromCodeLengths(distanceCodeLengths, 15);
            HuffmanTable codeLengthAlphabetTable =
                HuffmanTable.FromCodeLengths(codeLengthAlphabetLengths, 7);

            long headerBitLength = checked(14L + 3L * codeLengthCodeCount);
            foreach (CodeLengthRleToken token in encodedCodeLengths)
            {
                headerBitLength = checked(
                    headerBitLength +
                    codeLengthAlphabetTable.Lengths[token.Symbol] +
                    token.ExtraBitCount);
            }

            return new DynamicBlockPlan(
                literalLengthCodeCount,
                distanceCodeCount,
                codeLengthCodeCount,
                codeLengthAlphabetLengths,
                encodedCodeLengths,
                literalLengthTable,
                distanceTable,
                codeLengthAlphabetTable,
                headerBitLength);
        }

        public void WriteHeader(BitWriter writer)
        {
            writer.WriteBits((uint)(LiteralLengthCodeCount - 257), 5); // HLIT
            writer.WriteBits((uint)(DistanceCodeCount - 1), 5);       // HDIST
            writer.WriteBits((uint)(CodeLengthCodeCount - 4), 4);     // HCLEN

            for (int orderIndex = 0;
                 orderIndex < CodeLengthCodeCount;
                 orderIndex++)
            {
                int symbol = CodeLengthAlphabetOrder[orderIndex];
                writer.WriteBits(CodeLengthAlphabetLengths[symbol], 3);
            }

            foreach (CodeLengthRleToken token in EncodedCodeLengths)
            {
                CodeLengthAlphabetTable.WriteSymbol(writer, token.Symbol);
                writer.WriteBits((uint)token.ExtraValue, token.ExtraBitCount);
            }
        }
    }
}
