src/lzpack.c

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // compression code license (ONLY compression 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 int lzCompareWindow (const unsigned char *window, const unsigned char *buffer,
  34   int *offset, unsigned char *next, int windowSize, int bufferSize)
  35 {
  36   const unsigned char *windowEnd, *bufferEnd, *windowTrace;
  37   int longest = 0;
  38   unsigned char bufferFirst = buffer[0];
  39   //
  40   *next = bufferFirst;
  41   /*
  42   ** we can't match more than bufferSize-1 characters...
  43   ** we need to reserve the last character for the "next",
  44   ** and this also prevents us from returning LZ_BUFFER_LENGTH
  45   ** as the length (which won't work, max we can store is LZ_BUFFER_LENGTH-1)
  46   */
  47   --bufferSize;
  48   windowEnd = window+windowSize;
  49   bufferEnd = buffer+bufferSize;
  50   //
  51   for (windowTrace = window; windowTrace < windowEnd; ++windowTrace) {
  52     const unsigned char *bufferTrace, *windowTrace2;
  53     int length;
  54     //
  55     if (*windowTrace != bufferFirst) continue;
  56     bufferTrace = buffer;
  57     for (windowTrace2 = windowTrace; windowTrace2 < windowEnd && bufferTrace < bufferEnd && *windowTrace2 == *bufferTrace; ++windowTrace2, ++bufferTrace) ;
  58     length = windowTrace2-windowTrace;
  59     if (length > longest && length >= LZ_MINIMUM_USEFUL_MATCH) {
  60       *offset = windowTrace-window;
  61       longest = length;
  62       *next = *bufferTrace;
  63     }
  64   }
  65   //
  66   return longest;
  67 }
  68
  69
  70 static void lzEncodeHeaderField (unsigned char *data, unsigned int input, int *byteOffset) {
  71   if (input <= 252) {
  72     data[(*byteOffset)++] = (unsigned char)input;
  73   } else {
  74     unsigned char id;
  75     int length, inputPosition, bitsOffset;
  76     //
  77     if (input <= 65536) {
  78       id = 253;
  79       length = 2;
  80     } else {
  81       id = 254;
  82       length = 4;
  83     }
  84     //
  85     input = nwu32(input);
  86     inputPosition = (sizeof(uint32_t)*8)-(length*8);
  87     //bitsOffset;
  88     data[(*byteOffset)++] = (unsigned char)id;
  89     bitsOffset = *byteOffset*8;
  90     (*byteOffset) += length;
  91     //
  92     for (int i = 0; i < length*8; ++i) {
  93       bitSet(data, bitsOffset++, bitGet((unsigned char *)&input, inputPosition++));
  94     }
  95   }
  96 }
  97
  98
  99 static int lzCompress (const char *src, size_t srcLen, unsigned char **pdest, size_t *pdestLen) {
 100   unsigned char *compressed;
 101   const unsigned char *window;
 102   const unsigned char *buffer;
 103   int outputPosition;
 104   int remaining;
 105   int windowSize;
 106   int headerLength;
 107   unsigned char headerBuffer[10];
 108   int compressedSize;
 109   int totalSize;
 110   //
 111   *pdest = NULL;
 112   //
 113   compressed = (unsigned char *)calloc(((srcLen*5)/4)+10, 1);
 114   if (compressed == NULL) return -1;
 115   //
 116   window = buffer = (const unsigned char *)src;
 117   //
 118   outputPosition = 0;
 119   remaining = srcLen;
 120   windowSize = 0;
 121   //
 122   while (remaining > 0) {
 123     int bufferSize = MIN(remaining, LZ_BUFFER_SIZE);
 124     int useWindowSize = MIN(remaining, windowSize);
 125     int offset = 0;
 126     //
 127     unsigned long token;
 128     int tokenLength;
 129     unsigned char next;
 130     //
 131     int length = lzCompareWindow(window, buffer, &offset, &next, useWindowSize, bufferSize);
 132     //
 133     if (length > 1) {
 134       /* phrase token */
 135       //assert(length-LZ_MINIMUM_USEFUL_MATCH < (1<<LZ_LENGTH_BITS));
 136       token =
 137         (1<<(LZ_PHRASE_BITS-1)) |
 138         (offset<<(LZ_PHRASE_BITS-LZ_TYPE_BITS-LZ_OFFSET_BITS)) |
 139         ((length-LZ_MINIMUM_USEFUL_MATCH)<<(LZ_PHRASE_BITS-LZ_TYPE_BITS-LZ_OFFSET_BITS-LZ_LENGTH_BITS)) |
 140         next;
 141       tokenLength = LZ_PHRASE_BITS;
 142     } else {
 143       token = next;
 144       tokenLength = LZ_SYMBOL_BITS;
 145     }
 146     token = nwu32(token);
 147     for (int i = 0; i < tokenLength; ++i) {
 148       int inputPosition = (sizeof(uint32_t)*8)-tokenLength+i;
 149       bitSet(compressed, outputPosition, bitGet((unsigned char *)&token, inputPosition));
 150       ++outputPosition;
 151     }
 152     ++length;
 153     buffer += length;
 154     if (windowSize == LZ_WINDOW_SIZE) {
 155       window += length;
 156     } else {
 157       if (windowSize+length < LZ_WINDOW_SIZE) {
 158         windowSize += length;
 159       } else {
 160         window += windowSize+length-LZ_WINDOW_SIZE;
 161         windowSize = LZ_WINDOW_SIZE;
 162       }
 163     }
 164     remaining -= length;
 165   }
 166   headerLength = 0;
 167   memset(&headerBuffer, 0, sizeof(headerBuffer));
 168   lzEncodeHeaderField(headerBuffer, outputPosition, &headerLength);
 169   lzEncodeHeaderField(headerBuffer, srcLen, &headerLength);
 170   /* plug in header */
 171   compressedSize = (((outputPosition-1)/8)+1);
 172   totalSize = compressedSize+headerLength;
 173   compressed = (unsigned char *)realloc(compressed, totalSize);
 174   memmove(compressed+headerLength, compressed, compressedSize);
 175   memcpy(compressed, headerBuffer, headerLength);
 176   //
 177   *pdest = compressed;
 178   *pdestLen = totalSize;
 179   //
 180   return 0;
 181 }