Skip to content

armgit / Filee

Public Imported from GitHub
0

Free, open-source file converter. Convert 263 formats offline by drag & drop — images, PDF, Word, Excel, PowerPoint, HWP/HWPX, video, audio, e-books and archives. No upload, no Office needed.

15.4 KB
Raw Blame
// bzip2 decompression in managed code, written for ALZip archives: ALZ stores bzip2 blocks without the "BZh" stream
// header, marks each block with "DLZ\x01" (instead of the 48-bit block magic, the block CRC and the "randomised" bit)
// and ends with "DLZ\x02". Standard bzip2 streams (used by EGG) are read too. The block format itself (Huffman
// coded MTF/RLE2 symbols, Burrows-Wheeler transform, RLE1) is plain bzip2.

namespace Filee.Engines.Archives;

/// <summary>Decodes standard or ALZ-framed bzip2 data.</summary>
internal sealed class Bzip2Decoder
{
    private const ulong BlockMagic = 0x314159265359;
    private const ulong StreamEndMagic = 0x177245385090;
    private const uint AlzBlockMarker = 0x444C5A01; // "DLZ\x01"
    private const uint AlzEndMarker = 0x444C5A02;   // "DLZ\x02"
    private const int MaxCodeLength = 20;
    private const int GroupSize = 50;
    private const int MaxSelectors = 18002;

    private static readonly uint[] BlockCrcTable = CreateBlockCrcTable();

    private readonly Stream _input;
    private readonly Stream _output;
    private readonly long _maxOutput;
    private readonly byte[] _inBuffer = new byte[64 * 1024];
    private int _inPos;
    private int _inLength;
    private ulong _bits;
    private int _bitCount;
    private long _written;
    private int[] _tt = [];

    private Bzip2Decoder(Stream input, Stream output, long maxOutput)
    {
        _input = input;
        _output = output;
        _maxOutput = maxOutput;
    }

    /// <summary>Decompresses <paramref name="input"/> to <paramref name="output"/>.</summary>
    /// <param name="alzFraming">True for ALZ's variant of the stream framing (see the file comment).</param>
    /// <param name="maxOutput">Stops with an error when the data would unpack to more bytes than this.</param>
    /// <returns>Number of bytes written.</returns>
    public static long Decompress(Stream input, Stream output, bool alzFraming, long maxOutput, CancellationToken cancellationToken)
    {
        var decoder = new Bzip2Decoder(input, output, maxOutput);
        if (alzFraming)
            decoder.DecodeAlz(cancellationToken);
        else
            decoder.DecodeStandard(cancellationToken);
        return decoder._written;
    }

    private void DecodeAlz(CancellationToken cancellationToken)
    {
        // ALZip always writes 900k blocks and leaves out the stream header.
        while (TryReadBits(32, out var marker))
        {
            cancellationToken.ThrowIfCancellationRequested();
            if (marker == AlzEndMarker)
                return;
            if (marker != AlzBlockMarker)
                throw new InvalidDataException("bzip2 block marker missing");
            DecodeBlock(9, expectedCrc: null);
        }
    }

    private void DecodeStandard(CancellationToken cancellationToken)
    {
        // Several streams may follow each other (pbzip2, "cat a.bz2 b.bz2").
        var first = true;
        while (true)
        {
            if (!TryReadBits(8, out var b))
            {
                if (first)
                    throw new InvalidDataException("empty bzip2 data");
                return;
            }
            // Some writers leave out the "BZ" signature and start with "h9".
            if (b == 'B')
            {
                if (ReadBits(8) != 'Z')
                    throw new InvalidDataException("not bzip2 data");
                b = ReadBits(8);
            }
            if (b != 'h')
                throw new InvalidDataException("not bzip2 data");
            var level = (int)ReadBits(8) - '0';
            if (level is < 1 or > 9)
                throw new InvalidDataException("invalid bzip2 block size");
            first = false;

            uint combined = 0;
            while (true)
            {
                cancellationToken.ThrowIfCancellationRequested();
                var magic = ((ulong)ReadBits(24) << 24) | ReadBits(24);
                var crc = ReadBits(32);
                if (magic == StreamEndMagic)
                {
                    if (crc != combined)
                        throw new InvalidDataException("bzip2 stream checksum mismatch");
                    break;
                }
                if (magic != BlockMagic)
                    throw new InvalidDataException("bzip2 block magic missing");
                if (ReadBits(1) != 0)
                    throw new InvalidDataException("randomised bzip2 blocks (bzip2 0.9.0) are not supported");
                DecodeBlock(level, crc);
                combined = ((combined << 1) | (combined >> 31)) ^ crc;
            }
            // The next stream starts on a byte boundary.
            _bitCount -= _bitCount % 8;
        }
    }

    /// <summary>Decodes one block, starting at origPtr (after magic, CRC and randomised bit).</summary>
    private void DecodeBlock(int level, uint? expectedCrc)
    {
        var blockMax = level * 100_000;
        if (_tt.Length < blockMax)
            _tt = new int[blockMax];
        var tt = _tt;

        var origPtr = (int)ReadBits(24);

        // Symbols used in this block, as a 16x16 bitmap.
        var seqToUnseq = new byte[256];
        var inUseCount = 0;
        var inUse16 = ReadBits(16);
        for (var i = 0; i < 16; i++)
        {
            if ((inUse16 & (0x8000u >> i)) == 0)
                continue;
            var bits = ReadBits(16);
            for (var j = 0; j < 16; j++)
                if ((bits & (0x8000u >> j)) != 0)
                    seqToUnseq[inUseCount++] = (byte)(i * 16 + j);
        }
        if (inUseCount == 0)
            throw new InvalidDataException("bzip2 block uses no symbols");
        var alphaSize = inUseCount + 2;

        var groupCount = (int)ReadBits(3);
        var selectorCount = (int)ReadBits(15);
        if (groupCount is < 2 or > 6 || selectorCount < 1)
            throw new InvalidDataException("invalid bzip2 block header");

        // Selectors (which Huffman table each group of 50 symbols uses), MTF and unary coded.
        var selectors = new byte[Math.Min(selectorCount, MaxSelectors)];
        Span<byte> mtfGroups = stackalloc byte[6];
        for (var i = 0; i < groupCount; i++)
            mtfGroups[i] = (byte)i;
        for (var i = 0; i < selectorCount; i++)
        {
            var j = 0;
            while (ReadBits(1) == 1)
                if (++j >= groupCount)
                    throw new InvalidDataException("invalid bzip2 selector");
            var value = mtfGroups[j];
            for (; j > 0; j--)
                mtfGroups[j] = mtfGroups[j - 1];
            mtfGroups[0] = value;
            if (i < selectors.Length)
                selectors[i] = value; // bzip2 1.0.8 reads but ignores selectors beyond the limit
        }

        // Code lengths, delta coded, and the canonical Huffman decode tables built from them.
        var limit = new int[groupCount, MaxCodeLength + 2];
        var baseTable = new int[groupCount, MaxCodeLength + 2];
        var perm = new int[groupCount, 258];
        var minLengths = new int[groupCount];
        var lengths = new int[alphaSize];
        for (var t = 0; t < groupCount; t++)
        {
            var current = (int)ReadBits(5);
            for (var i = 0; i < alphaSize; i++)
            {
                while (true)
                {
                    if (current is < 1 or > MaxCodeLength)
                        throw new InvalidDataException("invalid bzip2 code length");
                    if (ReadBits(1) == 0)
                        break;
                    current += ReadBits(1) == 0 ? 1 : -1;
                }
                lengths[i] = current;
            }
            minLengths[t] = BuildDecodeTable(lengths, alphaSize, t, limit, baseTable, perm);
        }

        // MTF / RLE2 symbols → block bytes.
        Span<byte> mtf = stackalloc byte[256];
        for (var i = 0; i < 256; i++)
            mtf[i] = (byte)i;
        Span<int> counts = stackalloc int[256];
        counts.Clear();
        var endOfBlock = inUseCount + 1;
        var length = 0;
        var groupIndex = -1;
        var groupLeft = 0;
        var table = 0;

        var symbol = NextSymbol();
        while (symbol != endOfBlock)
        {
            if (symbol <= 1)
            {
                // RUNA / RUNB: a bijective base-2 run length of the symbol at the MTF front.
                var run = 0;
                var weight = 1;
                do
                {
                    if (weight > blockMax)
                        throw new InvalidDataException("bzip2 run too long");
                    run += (symbol + 1) * weight;
                    weight <<= 1;
                    symbol = NextSymbol();
                } while (symbol <= 1);

                var value = seqToUnseq[mtf[0]];
                if (length + run > blockMax)
                    throw new InvalidDataException("bzip2 block too long");
                counts[value] += run;
                tt.AsSpan(length, run).Fill(value);
                length += run;
                continue;
            }

            if (length >= blockMax)
                throw new InvalidDataException("bzip2 block too long");
            var index = symbol - 1;
            if (index >= inUseCount)
                throw new InvalidDataException("invalid bzip2 symbol");
            var front = mtf[index];
            mtf[..index].CopyTo(mtf[1..]);
            mtf[0] = front;
            var b = seqToUnseq[front];
            counts[b]++;
            tt[length++] = b;
            symbol = NextSymbol();
        }
        if (origPtr < 0 || origPtr >= Math.Max(length, 1))
            throw new InvalidDataException("invalid bzip2 origin pointer");

        // Inverse Burrows-Wheeler transform: link every position to its successor.
        Span<int> starts = stackalloc int[256];
        var sum = 0;
        for (var i = 0; i < 256; i++)
        {
            starts[i] = sum;
            sum += counts[i];
        }
        for (var i = 0; i < length; i++)
        {
            var b = tt[i] & 0xFF;
            tt[starts[b]++] |= i << 8;
        }

        // Walk the chain and undo the initial run-length coding (4 equal bytes + a count byte).
        var crc = 0xFFFFFFFFu;
        var buffer = new byte[64 * 1024];
        var used = 0;
        var position = length == 0 ? 0 : tt[origPtr] >> 8;
        var previous = -1;
        var repeat = 0;
        for (var i = 0; i < length; i++)
        {
            var entry = tt[position];
            var b = entry & 0xFF;
            position = entry >> 8;
            if (repeat == 4)
            {
                for (var k = 0; k < b; k++)
                    Emit((byte)previous);
                repeat = 0;
                previous = -1;
                continue;
            }
            repeat = b == previous ? repeat + 1 : 1;
            previous = b;
            Emit((byte)b);
        }
        Flush();

        if (expectedCrc is { } expected && ~crc != expected)
            throw new InvalidDataException("bzip2 block checksum mismatch");

        void Emit(byte value)
        {
            crc = (crc << 8) ^ BlockCrcTable[(crc >> 24) ^ value];
            buffer[used++] = value;
            if (used == buffer.Length)
                Flush();
        }

        void Flush()
        {
            if (used == 0)
                return;
            _written += used;
            if (_written > _maxOutput)
                throw new InvalidDataException("the data unpacks to more than the archive declares");
            _output.Write(buffer, 0, used);
            used = 0;
        }

        int NextSymbol()
        {
            if (groupLeft == 0)
            {
                if (++groupIndex >= selectors.Length)
                    throw new InvalidDataException("bzip2 selectors exhausted");
                table = selectors[groupIndex];
                groupLeft = GroupSize;
            }
            groupLeft--;
            var bitsUsed = minLengths[table];
            var code = (int)ReadBits(bitsUsed);
            while (bitsUsed <= MaxCodeLength && code > limit[table, bitsUsed])
            {
                bitsUsed++;
                code = (code << 1) | (int)ReadBits(1);
            }
            if (bitsUsed > MaxCodeLength)
                throw new InvalidDataException("invalid bzip2 Huffman code");
            var slot = code - baseTable[table, bitsUsed];
            if (slot is < 0 or >= 258)
                throw new InvalidDataException("invalid bzip2 Huffman code");
            return perm[table, slot];
        }
    }

    /// <summary>Canonical Huffman decode tables as in the reference bzip2 (limit / base / perm per code length).</summary>
    /// <returns>The shortest code length.</returns>
    private static int BuildDecodeTable(int[] lengths, int alphaSize, int t, int[,] limit, int[,] baseTable, int[,] perm)
    {
        var minLength = MaxCodeLength;
        var maxLength = 0;
        for (var i = 0; i < alphaSize; i++)
        {
            minLength = Math.Min(minLength, lengths[i]);
            maxLength = Math.Max(maxLength, lengths[i]);
        }

        var p = 0;
        for (var len = minLength; len <= maxLength; len++)
            for (var symbol = 0; symbol < alphaSize; symbol++)
                if (lengths[symbol] == len)
                    perm[t, p++] = symbol;

        Span<int> countAtLength = stackalloc int[MaxCodeLength + 2];
        countAtLength.Clear();
        for (var i = 0; i < alphaSize; i++)
            countAtLength[lengths[i] + 1]++;
        for (var i = 1; i < MaxCodeLength + 2; i++)
            countAtLength[i] += countAtLength[i - 1];

        for (var i = 0; i < MaxCodeLength + 2; i++)
        {
            limit[t, i] = -1; // lengths outside min..max never match, so decoding continues to longer codes
            baseTable[t, i] = countAtLength[i];
        }

        var code = 0;
        for (var len = minLength; len <= maxLength; len++)
        {
            code += countAtLength[len + 1] - countAtLength[len];
            limit[t, len] = code - 1;
            code <<= 1;
        }
        for (var len = minLength + 1; len <= maxLength; len++)
            baseTable[t, len] = ((limit[t, len - 1] + 1) << 1) - countAtLength[len];
        return minLength;
    }

    private uint ReadBits(int count)
    {
        if (!TryReadBits(count, out var value))
            throw new InvalidDataException("bzip2 data ends unexpectedly");
        return value;
    }

    /// <summary>Reads up to 32 bits, most significant first; false when the input is exhausted.</summary>
    private bool TryReadBits(int count, out uint value)
    {
        while (_bitCount < count)
        {
            if (_inPos == _inLength)
            {
                _inLength = _input.Read(_inBuffer, 0, _inBuffer.Length);
                _inPos = 0;
                if (_inLength == 0)
                {
                    value = 0;
                    return false;
                }
            }
            _bits = (_bits << 8) | _inBuffer[_inPos++];
            _bitCount += 8;
        }
        _bitCount -= count;
        value = (uint)((_bits >> _bitCount) & ((1UL << count) - 1));
        return true;
    }

    /// <summary>bzip2's block CRC: CRC-32 with the polynomial 0x04C11DB7, most significant bit first.</summary>
    private static uint[] CreateBlockCrcTable()
    {
        var table = new uint[256];
        for (uint i = 0; i < 256; i++)
        {
            var c = i << 24;
            for (var k = 0; k < 8; k++)
                c = (c & 0x80000000) != 0 ? (c << 1) ^ 0x04C11DB7 : c << 1;
            table[i] = c;
        }
        return table;
    }
}