src/lzunpack.c

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // decompression code license (ONLY decompression code)
   3 //
   4 // Copyright (c) 1997-2001 John Sadler (john_sadler@alum.mit.edu)
   5 // All rights reserved.
   6 //
   7 // Redistribution and use in source and binary forms, with or without
   8 // modification, are permitted provided that the following conditions
   9 // are met:
  10 //
  11 //   * Redistributions of source code must retain the above copyright
  12 //     notice, this list of conditions and the following disclaimer.
  13 //
  14 //   * Redistributions in binary form must reproduce the above copyright
  15 //     notice, this list of conditions and the following disclaimer in the
  16 //     documentation and/or other materials provided with the distribution.
  17 //
  18 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  19 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21 // ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  22 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24 // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28 // SUCH DAMAGE.
  29 //
  30 #include "lzcommon.c"
  31
  32
  33 static inline void bitGetString (unsigned char *destination, const unsigned char *source, int offset, int count, int destAlignment) {
  34   int bit = destAlignment-count;
  35   //
  36   while (count--) bitSet(destination, bit++, bitGet(source, offset++));
  37 }
  38
  39
  40 static int lzDecodeHeaderField (const unsigned char *data, int *byteOffset) {
  41   unsigned char id;
  42   int networkOrder, length;
  43   //
  44   id = data[(*byteOffset)++];
  45   if (id < 252) return id;
  46   networkOrder = 0;
  47   length = (id == 253 ? 2: 4);
  48   bitGetString(((unsigned char *)&networkOrder), data, (*byteOffset)*8, length*8, sizeof(networkOrder)*8);
  49   (*byteOffset) += length;
  50   return nwu32(networkOrder);
  51 }
  52
  53
  54 static int lzUncompress (const unsigned char *compressed, char **uncompressed_p, size_t *uncompressedSize_p) {
  55   unsigned char *window, *buffer, *uncompressed, *initialWindow;
  56   int bitstreamLength, inputPosition, uncompressedSize;
  57   //
  58   *uncompressed_p = NULL;
  59   inputPosition = 0;
  60   bitstreamLength = lzDecodeHeaderField(compressed, &inputPosition);
  61   uncompressedSize = lzDecodeHeaderField(compressed, &inputPosition);
  62   bitstreamLength += (inputPosition *= 8);
  63   uncompressed = (unsigned char *)calloc(uncompressedSize+1, 1);
  64   if (uncompressed == NULL) return -1;
  65   window = buffer = uncompressed;
  66   initialWindow = buffer+LZ_WINDOW_SIZE;
  67   //
  68   while (inputPosition != bitstreamLength) {
  69     int length, token = bitGet(compressed, inputPosition);
  70     //
  71     ++inputPosition;
  72     if (token) {
  73       /* phrase token */
  74       int offset = 0;
  75       //
  76       bitGetString((unsigned char *)&offset, compressed, inputPosition, LZ_PHRASE_BITS-(1+LZ_NEXT_BITS), sizeof(offset)*8);
  77       offset = nwu32(offset);
  78       inputPosition += LZ_PHRASE_BITS-(1+LZ_NEXT_BITS);
  79       length = (offset&((1<<LZ_LENGTH_BITS)-1))+LZ_MINIMUM_USEFUL_MATCH;
  80       offset >>= LZ_LENGTH_BITS;
  81       memmove(buffer, window+offset, length);
  82       buffer += length;
  83       ++length;
  84     } else {
  85       length = 1;
  86     }
  87     /* symbol token */
  88     *buffer = 0;
  89     bitGetString(buffer++, compressed, inputPosition, LZ_NEXT_BITS, sizeof(*buffer)*8);
  90     inputPosition += LZ_NEXT_BITS;
  91     if (buffer > initialWindow) window = buffer-LZ_WINDOW_SIZE;
  92   }
  93   //
  94   *uncompressed_p = (char *)uncompressed;
  95   *uncompressedSize_p = uncompressedSize;
  96   return 0;
  97 }