1 ////////////////////////////////////////////////////////////////////////////////
2 // compression code license (ONLY compression code)
4 // Copyright (c) 1997-2001 John Sadler (john_sadler@alum.mit.edu)
5 // All rights reserved.
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions
11 // * Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
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.
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
33 static int lzCompareWindow (const unsigned char *window
, const unsigned char *buffer
,
34 int *offset
, unsigned char *next
, int windowSize
, int bufferSize
)
36 const unsigned char *windowEnd
, *bufferEnd
, *windowTrace
;
38 unsigned char bufferFirst
= buffer
[0];
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)
48 windowEnd
= window
+windowSize
;
49 bufferEnd
= buffer
+bufferSize
;
51 for (windowTrace
= window
; windowTrace
< windowEnd
; ++windowTrace
) {
52 const unsigned char *bufferTrace
, *windowTrace2
;
55 if (*windowTrace
!= bufferFirst
) continue;
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
;
70 static void lzEncodeHeaderField (unsigned char *data
, unsigned int input
, int *byteOffset
) {
72 data
[(*byteOffset
)++] = (unsigned char)input
;
75 int length
, inputPosition
, bitsOffset
;
86 inputPosition
= (sizeof(uint32_t)*8)-(length
*8);
88 data
[(*byteOffset
)++] = (unsigned char)id
;
89 bitsOffset
= *byteOffset
*8;
90 (*byteOffset
) += length
;
92 for (int i
= 0; i
< length
*8; ++i
) {
93 bitSet(data
, bitsOffset
++, bitGet((unsigned char *)&input
, inputPosition
++));
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
;
107 unsigned char headerBuffer
[10];
113 compressed
= (unsigned char *)calloc(((srcLen
*5)/4)+10, 1);
114 if (compressed
== NULL
) return -1;
116 window
= buffer
= (const unsigned char *)src
;
122 while (remaining
> 0) {
123 int bufferSize
= MIN(remaining
, LZ_BUFFER_SIZE
);
124 int useWindowSize
= MIN(remaining
, windowSize
);
131 int length
= lzCompareWindow(window
, buffer
, &offset
, &next
, useWindowSize
, bufferSize
);
135 //assert(length-LZ_MINIMUM_USEFUL_MATCH < (1<<LZ_LENGTH_BITS));
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
)) |
141 tokenLength
= LZ_PHRASE_BITS
;
144 tokenLength
= LZ_SYMBOL_BITS
;
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
));
154 if (windowSize
== LZ_WINDOW_SIZE
) {
157 if (windowSize
+length
< LZ_WINDOW_SIZE
) {
158 windowSize
+= length
;
160 window
+= windowSize
+length
-LZ_WINDOW_SIZE
;
161 windowSize
= LZ_WINDOW_SIZE
;
167 memset(&headerBuffer
, 0, sizeof(headerBuffer
));
168 lzEncodeHeaderField(headerBuffer
, outputPosition
, &headerLength
);
169 lzEncodeHeaderField(headerBuffer
, srcLen
, &headerLength
);
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
);
178 *pdestLen
= totalSize
;