1 | /*␊ |
2 | * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.␊ |
3 | *␊ |
4 | * @APPLE_LICENSE_HEADER_START@␊ |
5 | * ␊ |
6 | * Portions Copyright (c) 1999-2003 Apple Computer, Inc. All Rights␊ |
7 | * Reserved. This file contains Original Code and/or Modifications of␊ |
8 | * Original Code as defined in and that are subject to the Apple Public␊ |
9 | * Source License Version 2.0 (the "License"). You may not use this file␊ |
10 | * except in compliance with the License. Please obtain a copy of the␊ |
11 | * License at http://www.apple.com/publicsource and read it before using␊ |
12 | * this file.␊ |
13 | * ␊ |
14 | * The Original Code and all software distributed under the License are␊ |
15 | * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER␊ |
16 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,␊ |
17 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,␊ |
18 | * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the␊ |
19 | * License for the specific language governing rights and limitations␊ |
20 | * under the License.␊ |
21 | * ␊ |
22 | * @APPLE_LICENSE_HEADER_END@␊ |
23 | */␊ |
24 | /**************************************************************␊ |
25 | LZSS.C -- A Data Compression Program␊ |
26 | ***************************************************************␊ |
27 | 4/6/1989 Haruhiko Okumura␊ |
28 | Use, distribute, and modify this program freely.␊ |
29 | Please send me your improved versions.␊ |
30 | PC-VAN SCIENCE␊ |
31 | NIFTY-Serve PAF01022␊ |
32 | CompuServe 74050,1022␊ |
33 | ␊ |
34 | **************************************************************/␊ |
35 | /*␊ |
36 | * lzss.c - Package for decompressing lzss compressed objects␊ |
37 | *␊ |
38 | * Copyright (c) 2003 Apple Computer, Inc.␊ |
39 | *␊ |
40 | * DRI: Josh de Cesare␊ |
41 | */␊ |
42 | ␊ |
43 | #include <sl.h>␊ |
44 | ␊ |
45 | #define N 4096 /* size of ring buffer - must be power of 2 */␊ |
46 | #define F 18 /* upper limit for match_length */␊ |
47 | #define THRESHOLD 2 /* encode string into position and length␊ |
48 | if match_length is greater than this */␊ |
49 | #define NIL N /* index for root of binary search trees */␊ |
50 | ␊ |
51 | struct encode_state {␊ |
52 | /*␊ |
53 | * left & right children & parent. These constitute binary search trees.␊ |
54 | */␊ |
55 | ␉int lchild[N + 1], rchild[N + 257], parent[N + 1];␊ |
56 | ␊ |
57 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */␊ |
58 | ␉u_int8_t text_buf[N + F - 1];␊ |
59 | ␊ |
60 | /*␊ |
61 | * match_length of longest match.␊ |
62 | * These are set by the insert_node() procedure.␊ |
63 | */␊ |
64 | ␉int match_position, match_length;␊ |
65 | };␊ |
66 | ␊ |
67 | int␊ |
68 | decompress_lzss( u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen )␊ |
69 | {␊ |
70 | ␉/* ring buffer of size N, with extra F-1 bytes to aid string comparison */␊ |
71 | ␉u_int8_t text_buf[N + F - 1];␊ |
72 | ␉u_int8_t *dststart = dst;␊ |
73 | ␉u_int8_t *dstend = dst + dstlen;␊ |
74 | ␉u_int8_t *srcend = src + srclen;␊ |
75 | ␉int i, j, k, r, c;␊ |
76 | ␉unsigned int flags;␊ |
77 | ␊ |
78 | ␉dst = dststart;␊ |
79 | ␉srcend = src + srclen;␊ |
80 | ␉for (i = 0; i < N - F; i++)␊ |
81 | ␉␉text_buf[i] = ' ';␊ |
82 | ␉r = N - F;␊ |
83 | ␉flags = 0;␊ |
84 | ␉for ( ; ; ) {␊ |
85 | ␉␉if (((flags >>= 1) & 0x100) == 0) {␊ |
86 | ␉␉␉if (src < srcend) c = *src++; else break;␊ |
87 | ␉␉␉flags = c | 0xFF00; /* uses higher byte cleverly */␊ |
88 | ␉␉} /* to count eight */␊ |
89 | ␉␉if (flags & 1) {␊ |
90 | ␉␉␉if (src < srcend) c = *src++; else break;␊ |
91 | ␉␉␉*dst++ = c;␊ |
92 | ␉␉␉if (dst >= dstend) {␊ |
93 | ␉␉␉␉goto finish;␊ |
94 | ␉␉␉}␊ |
95 | ␉␉␉text_buf[r++] = c;␊ |
96 | ␉␉␉r &= (N - 1);␊ |
97 | ␉␉} else {␊ |
98 | ␉␉␉if (src < srcend) i = *src++; else break;␊ |
99 | ␉␉␉if (src < srcend) j = *src++; else break;␊ |
100 | ␉␉␉i |= ((j & 0xF0) << 4);␊ |
101 | ␉␉␉j = (j & 0x0F) + THRESHOLD;␊ |
102 | ␉␉␉for (k = 0; k <= j; k++) {␊ |
103 | ␉␉␉␉c = text_buf[(i + k) & (N - 1)];␊ |
104 | ␉␉␉␉*dst++ = c;␊ |
105 | ␉␉␉␉if (dst >= dstend) {␊ |
106 | ␉␉␉␉␉goto finish;␊ |
107 | ␉␉␉␉}␊ |
108 | ␉␉␉␉text_buf[r++] = c;␊ |
109 | ␉␉␉␉r &= (N - 1);␊ |
110 | ␉␉␉}␊ |
111 | ␉␉}␊ |
112 | ␉}␊ |
113 | finish:␊ |
114 | ␉return dst - dststart;␊ |
115 | }␊ |
116 | ␊ |
117 | /*␊ |
118 | * initialize state, mostly the trees␊ |
119 | *␊ |
120 | * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left␊ |
121 | * children of node i. These nodes need not be initialized. Also, parent[i]␊ |
122 | * is the parent of node i. These are initialized to NIL (= N), which stands␊ |
123 | * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the␊ |
124 | * tree for strings that begin with character i. These are initialized to NIL.␊ |
125 | * Note there are 256 trees. */␊ |
126 | static void init_state(struct encode_state *sp)␊ |
127 | {␊ |
128 | int i;␊ |
129 | ␊ |
130 | bzero(sp, sizeof(*sp));␊ |
131 | ␊ |
132 | for (i = 0; i < N - F; i++)␊ |
133 | sp->text_buf[i] = ' ';␊ |
134 | for (i = N + 1; i <= N + 256; i++)␊ |
135 | sp->rchild[i] = NIL;␊ |
136 | for (i = 0; i < N; i++)␊ |
137 | sp->parent[i] = NIL;␊ |
138 | }␊ |
139 | ␊ |
140 | /*␊ |
141 | * Inserts string of length F, text_buf[r..r+F-1], into one of the trees␊ |
142 | * (text_buf[r]'th tree) and returns the longest-match position and length␊ |
143 | * via the global variables match_position and match_length.␊ |
144 | * If match_length = F, then removes the old node in favor of the new one,␊ |
145 | * because the old one will be deleted sooner. Note r plays double role,␊ |
146 | * as tree node and position in buffer.␊ |
147 | */␊ |
148 | static void insert_node(struct encode_state *sp, int r)␊ |
149 | {␊ |
150 | int i, p, cmp;␊ |
151 | u_int8_t *key;␊ |
152 | ␊ |
153 | cmp = 1;␊ |
154 | key = &sp->text_buf[r];␊ |
155 | p = N + 1 + key[0];␊ |
156 | sp->rchild[r] = sp->lchild[r] = NIL;␊ |
157 | sp->match_length = 0;␊ |
158 | for ( ; ; ) {␊ |
159 | if (cmp >= 0) {␊ |
160 | if (sp->rchild[p] != NIL)␊ |
161 | p = sp->rchild[p];␊ |
162 | else {␊ |
163 | sp->rchild[p] = r;␊ |
164 | sp->parent[r] = p;␊ |
165 | return;␊ |
166 | }␊ |
167 | } else {␊ |
168 | if (sp->lchild[p] != NIL)␊ |
169 | p = sp->lchild[p];␊ |
170 | else {␊ |
171 | sp->lchild[p] = r;␊ |
172 | sp->parent[r] = p;␊ |
173 | return;␊ |
174 | }␊ |
175 | }␊ |
176 | for (i = 1; i < F; i++) {␊ |
177 | if ((cmp = key[i] - sp->text_buf[p + i]) != 0)␊ |
178 | break;␊ |
179 | }␊ |
180 | if (i > sp->match_length) {␊ |
181 | sp->match_position = p;␊ |
182 | if ((sp->match_length = i) >= F)␊ |
183 | break;␊ |
184 | }␊ |
185 | }␊ |
186 | sp->parent[r] = sp->parent[p];␊ |
187 | sp->lchild[r] = sp->lchild[p];␊ |
188 | sp->rchild[r] = sp->rchild[p];␊ |
189 | sp->parent[sp->lchild[p]] = r;␊ |
190 | sp->parent[sp->rchild[p]] = r;␊ |
191 | if (sp->rchild[sp->parent[p]] == p)␊ |
192 | sp->rchild[sp->parent[p]] = r;␊ |
193 | else␊ |
194 | sp->lchild[sp->parent[p]] = r;␊ |
195 | sp->parent[p] = NIL; /* remove p */␊ |
196 | }␊ |
197 | ␊ |
198 | /* deletes node p from tree */␊ |
199 | static void delete_node(struct encode_state *sp, int p)␊ |
200 | {␊ |
201 | int q;␊ |
202 | ␊ |
203 | if (sp->parent[p] == NIL)␊ |
204 | return; /* not in tree */␊ |
205 | if (sp->rchild[p] == NIL)␊ |
206 | q = sp->lchild[p];␊ |
207 | else if (sp->lchild[p] == NIL)␊ |
208 | q = sp->rchild[p];␊ |
209 | else {␊ |
210 | q = sp->lchild[p];␊ |
211 | if (sp->rchild[q] != NIL) {␊ |
212 | do {␊ |
213 | q = sp->rchild[q];␊ |
214 | } while (sp->rchild[q] != NIL);␊ |
215 | sp->rchild[sp->parent[q]] = sp->lchild[q];␊ |
216 | sp->parent[sp->lchild[q]] = sp->parent[q];␊ |
217 | sp->lchild[q] = sp->lchild[p];␊ |
218 | sp->parent[sp->lchild[p]] = q;␊ |
219 | }␊ |
220 | sp->rchild[q] = sp->rchild[p];␊ |
221 | sp->parent[sp->rchild[p]] = q;␊ |
222 | }␊ |
223 | sp->parent[q] = sp->parent[p];␊ |
224 | if (sp->rchild[sp->parent[p]] == p)␊ |
225 | sp->rchild[sp->parent[p]] = q;␊ |
226 | else␊ |
227 | sp->lchild[sp->parent[p]] = q;␊ |
228 | sp->parent[p] = NIL;␊ |
229 | }␊ |
230 | ␊ |
231 | u_int8_t *compress_lzss( u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srcLen )␊ |
232 | {␊ |
233 | /* Encoding state, mostly tree but some current match stuff */␊ |
234 | struct encode_state *sp;␊ |
235 | ␊ |
236 | int i, c, len, r, s, last_match_length, code_buf_ptr;␊ |
237 | u_int8_t code_buf[17], mask;␊ |
238 | u_int8_t *srcend = src + srcLen;␊ |
239 | u_int8_t *dstend = dst + dstlen;␊ |
240 | ␊ |
241 | /* initialize trees */␊ |
242 | sp = (struct encode_state *) malloc(sizeof(*sp));␊ |
243 | init_state(sp);␊ |
244 | ␊ |
245 | /*␊ |
246 | * code_buf[1..16] saves eight units of code, and code_buf[0] works␊ |
247 | * as eight flags, "1" representing that the unit is an unencoded␊ |
248 | * letter (1 byte), "0" a position-and-length pair (2 bytes).␊ |
249 | * Thus, eight units require at most 16 bytes of code.␊ |
250 | */␊ |
251 | code_buf[0] = 0;␊ |
252 | code_buf_ptr = mask = 1;␊ |
253 | ␊ |
254 | /* Clear the buffer with any character that will appear often. */␊ |
255 | s = 0; r = N - F;␊ |
256 | ␊ |
257 | /* Read F bytes into the last F bytes of the buffer */␊ |
258 | for (len = 0; len < F && src < srcend; len++)␊ |
259 | sp->text_buf[r + len] = *src++;␊ |
260 | if (!len)␊ |
261 | return (void *) 0; /* text of size zero */␊ |
262 | ␊ |
263 | /*␊ |
264 | * Insert the F strings, each of which begins with one or more␊ |
265 | * 'space' characters. Note the order in which these strings are␊ |
266 | * inserted. This way, degenerate trees will be less likely to occur.␊ |
267 | */␊ |
268 | for (i = 1; i <= F; i++)␊ |
269 | insert_node(sp, r - i);␊ |
270 | ␊ |
271 | /*␊ |
272 | * Finally, insert the whole string just read.␊ |
273 | * The global variables match_length and match_position are set.␊ |
274 | */␊ |
275 | insert_node(sp, r);␊ |
276 | do {␊ |
277 | /* match_length may be spuriously long near the end of text. */␊ |
278 | if (sp->match_length > len)␊ |
279 | sp->match_length = len;␊ |
280 | if (sp->match_length <= THRESHOLD) {␊ |
281 | sp->match_length = 1; /* Not long enough match. Send one byte. */␊ |
282 | code_buf[0] |= mask; /* 'send one byte' flag */␊ |
283 | code_buf[code_buf_ptr++] = sp->text_buf[r]; /* Send uncoded. */␊ |
284 | } else {␊ |
285 | /* Send position and length pair. Note match_length > THRESHOLD. */␊ |
286 | code_buf[code_buf_ptr++] = (u_int8_t) sp->match_position;␊ |
287 | code_buf[code_buf_ptr++] = (u_int8_t)␊ |
288 | ( ((sp->match_position >> 4) & 0xF0)␊ |
289 | | (sp->match_length - (THRESHOLD + 1)) );␊ |
290 | }␊ |
291 | if ((mask <<= 1) == 0) { /* Shift mask left one bit. */␊ |
292 | /* Send at most 8 units of code together */␊ |
293 | for (i = 0; i < code_buf_ptr; i++)␊ |
294 | if (dst < dstend)␊ |
295 | *dst++ = code_buf[i];␊ |
296 | else␊ |
297 | return (void *) 0;␊ |
298 | code_buf[0] = 0;␊ |
299 | code_buf_ptr = mask = 1;␊ |
300 | }␊ |
301 | last_match_length = sp->match_length;␊ |
302 | for (i = 0; i < last_match_length && src < srcend; i++) {␊ |
303 | delete_node(sp, s); /* Delete old strings and */␊ |
304 | c = *src++;␊ |
305 | sp->text_buf[s] = c; /* read new bytes */␊ |
306 | ␊ |
307 | /*␊ |
308 | * If the position is near the end of buffer, extend the buffer␊ |
309 | * to make string comparison easier.␊ |
310 | */␊ |
311 | if (s < F - 1)␊ |
312 | sp->text_buf[s + N] = c;␊ |
313 | ␊ |
314 | /* Since this is a ring buffer, increment the position modulo N. */␊ |
315 | s = (s + 1) & (N - 1);␊ |
316 | r = (r + 1) & (N - 1);␊ |
317 | ␊ |
318 | /* Register the string in text_buf[r..r+F-1] */␊ |
319 | insert_node(sp, r);␊ |
320 | }␊ |
321 | while (i++ < last_match_length) {␊ |
322 | delete_node(sp, s);␊ |
323 | ␊ |
324 | /* After the end of text, no need to read, */␊ |
325 | s = (s + 1) & (N - 1);␊ |
326 | r = (r + 1) & (N - 1);␊ |
327 | /* but buffer may not be empty. */␊ |
328 | if (--len)␊ |
329 | insert_node(sp, r);␊ |
330 | }␊ |
331 | } while (len > 0); /* until length of string to be processed is zero */␊ |
332 | ␊ |
333 | if (code_buf_ptr > 1) { /* Send remaining code. */␊ |
334 | for (i = 0; i < code_buf_ptr; i++)␊ |
335 | if (dst < dstend)␊ |
336 | *dst++ = code_buf[i];␊ |
337 | else␊ |
338 | return (void *) 0;␊ |
339 | }␊ |
340 | ␊ |
341 | return dst;␊ |
342 | }␊ |
343 | |