/* 
 * LZ Decompression functions
 *
 * Copyright 1996 Marcus Meissner
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 *
 * NOTES
 *
 * The LZ (Lempel Ziv) decompression was used in win16 installation programs.
 * It is a simple tabledriven decompression engine, the algorithm is not
 * documented as far as I know. WINE does not contain a compressor for
 * this format.
 *
 * The implementation is complete and there have been no reports of failures
 * for some time.
 *
 * TODO:
 *
 *   o Check whether the return values are correct
 *
 */

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define LZ_MAGIC_LEN    8
#define LZ_HEADER_LEN   14

/* Format of first 14 byte of LZ compressed file */
struct lzfileheader {
    uint8_t magic[LZ_MAGIC_LEN];
    uint8_t compressiontype;
    uint8_t lastchar;
    uint32_t reallength;
};
static const uint8_t LZMagic[LZ_MAGIC_LEN]={'S','Z','D','D',0x88,0xf0,0x27,0x33};
#define LZ_TABLE_SIZE 0x1000

typedef struct _lzstate {
    uint8_t *inbuf;
    size_t inpos, insize;
    uint8_t  is_compressed; /* is input a compressed file/buffer? */
    uint8_t   lastchar;  /* the last char of the filename */

    uint32_t  reallength;   /* the decompressed length of the file */
    uint32_t  realcurrent;  /* the position the decompressor currently is */
    uint32_t  realwanted;   /* the position the user wants to read from */

    uint8_t   table[LZ_TABLE_SIZE]; /* the rotating LZ table */
    uint32_t  curtabent;    /* CURrent TABle ENTry */

    uint8_t   stringlen;    /* length and position of current string */
    uint32_t  stringpos;    /* from stringtable */
    uint16_t  bytetype; /* bitmask within blocks */
} lzstate;

static int _lzget(lzstate *lzs, uint8_t *b) {
    if (lzs->inpos < lzs->insize) {
        *b = lzs->inbuf[lzs->inpos++];
        return 1;
    } else {
        return 0;
    }
}

/* internal function, reads lzheader
 * returns BADINHANDLE for non filedescriptors
 * return 0 for file not compressed using LZ
 * return UNKNOWNALG for unknown algorithm
 * returns lzfileheader in *head
 */
static uint32_t read_header(uint8_t *lzheaderbuf, uint32_t lzheaderlen, struct lzfileheader *head)
{
    if (lzheaderlen < LZ_HEADER_LEN) {
        return 0;
    }
    memcpy(head->magic, lzheaderbuf, LZ_MAGIC_LEN);
    head->compressiontype = lzheaderbuf[LZ_MAGIC_LEN];
    head->lastchar = lzheaderbuf[LZ_MAGIC_LEN+1];

    /* FIXME: consider endianess on non-intel architectures */
    memcpy(&(head->reallength), lzheaderbuf+LZ_MAGIC_LEN+2, 4);

    if (memcmp(head->magic, LZMagic, LZ_MAGIC_LEN))
        return 0;
    if (head->compressiontype != 'A')
        return -1;
    return 1;
}

void LZInit(lzstate *lzs, uint8_t *inbuf, size_t insize)
{
    unsigned int *tptr4 = (unsigned int*)lzs->table;
    size_t i;
    struct lzfileheader head;
    uint32_t ret = read_header(inbuf, LZ_HEADER_LEN, &head);
    if (ret == 0) {
        return;
    }

    lzs->is_compressed = 1;
    lzs->inbuf = inbuf;
    lzs->insize = insize;
    lzs->inpos = LZ_HEADER_LEN;
    lzs->lastchar   = head.lastchar;
    lzs->reallength = head.reallength;

    /* Yes, preinitialize with spaces */
    //memset(lzs->table,' ',LZ_TABLE_SIZE);
    for(i=0; i<LZ_TABLE_SIZE/4; i++) {
        tptr4[i] = 0x20202020;
    }
    /* Yes, start 16 byte from the END of the table */
    lzs->curtabent  = 0xff0;
}

size_t LZRead(lzstate *lzs, uint8_t *vbuf, size_t toread)
{
    uint8_t b, *buf = vbuf;
    size_t howmuch = toread;

    if (!lzs->is_compressed) {
        if (toread > lzs->insize) {
            toread = lzs->insize;
        }
        memcpy(buf, lzs->inbuf, toread);
        return toread;
    }

/* The decompressor itself is in a define, cause we need it twice
 * in this function. (the decompressed byte will be in b)
 */
#define DECOMPRESS_ONE_BYTE                         \
        if (lzs->stringlen) {                   \
            b = lzs->table[lzs->stringpos]; \
            lzs->stringpos = (lzs->stringpos+1)&0xFFF;  \
            lzs->stringlen--;               \
        } else {                        \
            if (!(lzs->bytetype&0x100)) {           \
                if (_lzget(lzs, &b) != 1)           \
                    return toread-howmuch;      \
                lzs->bytetype = b|0xFF00;       \
            }                       \
            if (lzs->bytetype & 1) {            \
                if (_lzget(lzs, &b) != 1)           \
                    return toread-howmuch;      \
            } else {                    \
                uint8_t b1,b2;              \
                                    \
                if (_lzget(lzs, &b1) != 1)          \
                    return toread-howmuch;      \
                if (_lzget(lzs, &b2) != 1)          \
                    return toread-howmuch;      \
                /* Format:              \
                 * b1 b2                \
                 * AB CD                \
                 * where CAB is the stringoffset in the table\
                 * and D+3 is the len of the string \
                 */                 \
                lzs->stringpos  = b1|((b2&0xf0)<<4);    \
                lzs->stringlen  = (b2&0xf)+2;       \
                /* 3, but we use a  byte already below ... */\
                b = lzs->table[lzs->stringpos];\
                lzs->stringpos = (lzs->stringpos+1)&0xFFF;\
            }                       \
            lzs->bytetype>>=1;              \
        }                           \
        /* store b in table */                  \
        lzs->table[lzs->curtabent++]= b;            \
        lzs->curtabent  &= 0xFFF;               \
        lzs->realcurrent++;

    /* if someone has seeked, we have to bring the decompressor
     * to that position
     */
    if (lzs->realcurrent!=lzs->realwanted) {
        /* if the wanted position is before the current position
         * I see no easy way to unroll ... We have to restart at
         * the beginning. *sigh*
         */
        if (lzs->realcurrent>lzs->realwanted) {
            /* flush decompressor state */
            unsigned int ii, *tptr4 = (unsigned int*)lzs->table;
            lzs->inpos = LZ_HEADER_LEN;
            lzs->realcurrent= 0;
            lzs->bytetype   = 0;
            lzs->stringlen  = 0;
            //memset(lzs->table,' ',LZ_TABLE_SIZE);
            for(ii=0; ii<LZ_TABLE_SIZE/4; ii++) {
                tptr4[ii] = 0x20202020;
            }
            lzs->curtabent  = 0xFF0;
        }
        while (lzs->realcurrent<lzs->realwanted) {
            DECOMPRESS_ONE_BYTE;
        }
    }

    while (howmuch) {
        DECOMPRESS_ONE_BYTE;
        lzs->realwanted++;
        *buf++      = b;
        howmuch--;
    }
    return toread;
#undef DECOMPRESS_ONE_BYTE
}

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>

uint8_t *slurp_file(char *path, uint64_t *filesize);

int main(int argc, char **argv) {
    uint64_t filesz = 0;
    uint8_t *outbuf = NULL, *inbuf = slurp_file(argv[1], &filesz);
    lzstate lzs;
    memset(&lzs, 0, sizeof(lzstate));
    LZInit(&lzs, inbuf, filesz);
    fprintf(stderr, "LZState: is_compressed: %u, lastchar: %c (0x%02X), compressed size: %lu, uncompressed size: %u\n", lzs.is_compressed, lzs.lastchar, lzs.lastchar, filesz, lzs.reallength);
    outbuf = malloc(lzs.reallength+1);
    LZRead(&lzs, outbuf, lzs.reallength);
    write(1, outbuf, lzs.reallength);
    return 0;
}