ntloader/libnt/xca.c

/*
 * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

/**
 * @file
 *
 * Xpress Compression Algorithm (MS-XCA) decompression
 *
 */

#include <stdint.h>
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include "huffman.h"
#include "xca.h"

#ifdef NTLOADER_UTIL
#define DBG(...) \
do \
{ \
    fprintf (stderr, __VA_ARGS__); \
} while (0)
#endif

/**
 * Decompress XCA-compressed data
 *
 * @v data		Compressed data
 * @v len		Length of compressed data
 * @v buf		Decompression buffer, or NULL
 * @ret out_len		Length of decompressed data, or negative error
 */
ssize_t xca_decompress (const void *data, size_t len, void *buf)
{
    const void *src = data;
    const void *end = (src + len);
    uint8_t *out = buf;
    size_t out_len = 0;
    size_t out_len_threshold = 0;
    const struct xca_huf_len *lengths;
    struct xca xca;
    uint32_t accum = 0;
    int extra_bits = 0;
    unsigned int huf;
    struct huffman_symbols *sym;
    unsigned int raw;
    unsigned int match_len;
    unsigned int match_offset_bits;
    unsigned int match_offset;
    const uint8_t *copy;
    int rc;

    /* Process data stream */
    while (src < end)
    {
        /* (Re)initialise decompressor if applicable */
        if (out_len >= out_len_threshold)
        {
            /* Construct symbol lengths */
            lengths = src;
            src += sizeof (*lengths);
            if (src > end)
            {
                DBG ("XCA too short to hold Huffman lengths "
                     "table at input offset %#zx\n", src - data);
                return -1;
            }
            for (raw = 0; raw < XCA_CODES; raw++)
                xca.lengths[raw] = xca_huf_len (lengths, raw);

            /* Construct Huffman alphabet */
            if ((rc = huffman_alphabet (&xca.alphabet,
                                        xca.lengths,
                                        XCA_CODES)) != 0)
                return rc;

            /* Initialise state */
            accum = XCA_GET16 (src);
            accum <<= 16;
            accum |= XCA_GET16 (src);
            extra_bits = 16;

            /* Determine next threshold */
            out_len_threshold = (out_len + XCA_BLOCK_SIZE);
        }

        /* Determine symbol */
        huf = (accum >> (32 - HUFFMAN_BITS));
        sym = huffman_sym (&xca.alphabet, huf);
        raw = huffman_raw (sym, huf);
        accum <<= huffman_len (sym);
        extra_bits -= huffman_len (sym);
        if (extra_bits < 0)
        {
            accum |= (XCA_GET16 (src) << (-extra_bits));
            extra_bits += 16;
        }

        /* Process symbol */
        if (raw < XCA_END_MARKER)
        {
            /* Literal symbol - add to output stream */
            if (buf)
                *(out++) = raw;
            out_len++;
        }
        else if ((raw == XCA_END_MARKER) && (src >= (end - 1)))
        {
            /* End marker symbol */
            return out_len;
        }
        else
        {
            /* LZ77 match symbol */
            raw -= XCA_END_MARKER;
            match_offset_bits = (raw >> 4);
            match_len = (raw & 0x0f);
            if (match_len == 0x0f)
            {
                match_len = XCA_GET8 (src);
                if (match_len == 0xff)
                {
                    match_len = XCA_GET16 (src);
                }
                else
                {
                    match_len += 0x0f;
                }
            }
            match_len += 3;
            if (match_offset_bits)
            {
                match_offset = ((accum >> (32 - match_offset_bits))
                                + (1 << match_offset_bits));
            }
            else
            {
                match_offset = 1;
            }
            accum <<= match_offset_bits;
            extra_bits -= match_offset_bits;
            if (extra_bits < 0)
            {
                accum |= (XCA_GET16 (src) << (-extra_bits));
                extra_bits += 16;
            }

            /* Copy data */
            out_len += match_len;
            if (buf)
            {
                copy = (out - match_offset);
                while (match_len--)
                    *(out++) = *(copy++);
            }
        }
    }

    /* Allow for termination with no explicit end marker symbol */
    if (src == end)
        return out_len;

    DBG ("XCA input overrun at output length %#zx\n", out_len);
    return -1;
}