1 | /* |
2 | * Copyright (c) 2000-2016 Apple Computer, Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | #include <stdint.h> // For uintptr_t. |
29 | #include <string.h> |
30 | #include <libkern/mkext.h> |
31 | |
32 | |
33 | #define BASE 65521L /* largest prime smaller than 65536 */ |
34 | #define NMAX 5552 // the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 |
35 | |
36 | #define DO1(buf, i) {s1 += buf[i]; s2 += s1;} |
37 | #define DO2(buf, i) DO1(buf,i); DO1(buf,i+1); |
38 | #define DO4(buf, i) DO2(buf,i); DO2(buf,i+2); |
39 | #define DO8(buf, i) DO4(buf,i); DO4(buf,i+4); |
40 | #define DO16(buf) DO8(buf,0); DO8(buf,8); |
41 | |
42 | u_int32_t |
43 | mkext_adler32(uint8_t *buf, int32_t len) |
44 | { |
45 | unsigned long s1 = 1; // adler & 0xffff; |
46 | unsigned long s2 = 0; // (adler >> 16) & 0xffff; |
47 | int k; |
48 | |
49 | |
50 | while (len > 0) { |
51 | k = len < NMAX ? len : NMAX; |
52 | len -= k; |
53 | while (k >= 16) { |
54 | DO16(buf); |
55 | buf += 16; |
56 | k -= 16; |
57 | } |
58 | if (k != 0) { |
59 | do { |
60 | s1 += *buf++; |
61 | s2 += s1; |
62 | } while (--k); |
63 | } |
64 | s1 %= BASE; |
65 | s2 %= BASE; |
66 | } |
67 | return (u_int32_t)((s2 << 16) | s1); |
68 | } |
69 | |
70 | |
71 | /************************************************************** |
72 | * LZSS.C -- A Data Compression Program |
73 | *************************************************************** |
74 | * 4/6/1989 Haruhiko Okumura |
75 | * Use, distribute, and modify this program freely. |
76 | * Please send me your improved versions. |
77 | * PC-VAN SCIENCE |
78 | * NIFTY-Serve PAF01022 |
79 | * CompuServe 74050,1022 |
80 | * |
81 | **************************************************************/ |
82 | |
83 | #define N 4096 /* size of ring buffer - must be power of 2 */ |
84 | #define F 18 /* upper limit for match_length */ |
85 | #define THRESHOLD 2 /* encode string into position and length |
86 | * if match_length is greater than this */ |
87 | #if !KERNEL |
88 | #define NIL N /* index for root of binary search trees */ |
89 | #endif |
90 | |
91 | struct encode_state { |
92 | /* |
93 | * left & right children & parent. These constitute binary search trees. |
94 | */ |
95 | int lchild[N + 1], rchild[N + 257], parent[N + 1]; |
96 | |
97 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ |
98 | u_int8_t text_buf[N + F - 1]; |
99 | |
100 | /* |
101 | * match_length of longest match. |
102 | * These are set by the insert_node() procedure. |
103 | */ |
104 | int match_position, match_length; |
105 | }; |
106 | |
107 | |
108 | int |
109 | decompress_lzss(u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen) |
110 | { |
111 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ |
112 | u_int8_t text_buf[N + F - 1]; |
113 | u_int8_t *dststart = dst; |
114 | u_int8_t *dstend = dst + dstlen; |
115 | u_int8_t *srcend = src + srclen; |
116 | int i, j, k, r; |
117 | u_int8_t c; |
118 | unsigned int flags; |
119 | |
120 | dst = dststart; |
121 | srcend = src + srclen; |
122 | for (i = 0; i < N - F; i++) { |
123 | text_buf[i] = ' '; |
124 | } |
125 | r = N - F; |
126 | flags = 0; |
127 | for (;;) { |
128 | if (((flags >>= 1) & 0x100) == 0) { |
129 | if (src < srcend) { |
130 | c = *src++; |
131 | } else { |
132 | break; |
133 | } |
134 | flags = c | 0xFF00; /* uses higher byte cleverly */ |
135 | } /* to count eight */ |
136 | if (flags & 1) { |
137 | if (src < srcend) { |
138 | c = *src++; |
139 | } else { |
140 | break; |
141 | } |
142 | *dst++ = c; |
143 | if (dst >= dstend) { |
144 | goto finish; |
145 | } |
146 | text_buf[r++] = c; |
147 | r &= (N - 1); |
148 | } else { |
149 | if (src < srcend) { |
150 | i = *src++; |
151 | } else { |
152 | break; |
153 | } |
154 | if (src < srcend) { |
155 | j = *src++; |
156 | } else { |
157 | break; |
158 | } |
159 | i |= ((j & 0xF0) << 4); |
160 | j = (j & 0x0F) + THRESHOLD; |
161 | for (k = 0; k <= j; k++) { |
162 | c = text_buf[(i + k) & (N - 1)]; |
163 | *dst++ = c; |
164 | if (dst >= dstend) { |
165 | goto finish; |
166 | } |
167 | text_buf[r++] = c; |
168 | r &= (N - 1); |
169 | } |
170 | } |
171 | } |
172 | finish: |
173 | return (int)(dst - dststart); |
174 | } |
175 | |
176 | #if !KERNEL |
177 | |
178 | /* |
179 | * initialize state, mostly the trees |
180 | * |
181 | * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left |
182 | * children of node i. These nodes need not be initialized. Also, parent[i] |
183 | * is the parent of node i. These are initialized to NIL (= N), which stands |
184 | * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the |
185 | * tree for strings that begin with character i. These are initialized to NIL. |
186 | * Note there are 256 trees. */ |
187 | static void |
188 | init_state(struct encode_state *sp) |
189 | { |
190 | int i; |
191 | |
192 | bzero(sp, sizeof(*sp)); |
193 | |
194 | for (i = 0; i < N - F; i++) { |
195 | sp->text_buf[i] = ' '; |
196 | } |
197 | for (i = N + 1; i <= N + 256; i++) { |
198 | sp->rchild[i] = NIL; |
199 | } |
200 | for (i = 0; i < N; i++) { |
201 | sp->parent[i] = NIL; |
202 | } |
203 | } |
204 | |
205 | /* |
206 | * Inserts string of length F, text_buf[r..r+F-1], into one of the trees |
207 | * (text_buf[r]'th tree) and returns the longest-match position and length |
208 | * via the global variables match_position and match_length. |
209 | * If match_length = F, then removes the old node in favor of the new one, |
210 | * because the old one will be deleted sooner. Note r plays double role, |
211 | * as tree node and position in buffer. |
212 | */ |
213 | static void |
214 | insert_node(struct encode_state *sp, int r) |
215 | { |
216 | int i, p, cmp; |
217 | u_int8_t *key; |
218 | |
219 | cmp = 1; |
220 | key = &sp->text_buf[r]; |
221 | p = N + 1 + key[0]; |
222 | sp->rchild[r] = sp->lchild[r] = NIL; |
223 | sp->match_length = 0; |
224 | for (;;) { |
225 | if (cmp >= 0) { |
226 | if (sp->rchild[p] != NIL) { |
227 | p = sp->rchild[p]; |
228 | } else { |
229 | sp->rchild[p] = r; |
230 | sp->parent[r] = p; |
231 | return; |
232 | } |
233 | } else { |
234 | if (sp->lchild[p] != NIL) { |
235 | p = sp->lchild[p]; |
236 | } else { |
237 | sp->lchild[p] = r; |
238 | sp->parent[r] = p; |
239 | return; |
240 | } |
241 | } |
242 | for (i = 1; i < F; i++) { |
243 | if ((cmp = key[i] - sp->text_buf[p + i]) != 0) { |
244 | break; |
245 | } |
246 | } |
247 | if (i > sp->match_length) { |
248 | sp->match_position = p; |
249 | if ((sp->match_length = i) >= F) { |
250 | break; |
251 | } |
252 | } |
253 | } |
254 | sp->parent[r] = sp->parent[p]; |
255 | sp->lchild[r] = sp->lchild[p]; |
256 | sp->rchild[r] = sp->rchild[p]; |
257 | sp->parent[sp->lchild[p]] = r; |
258 | sp->parent[sp->rchild[p]] = r; |
259 | if (sp->rchild[sp->parent[p]] == p) { |
260 | sp->rchild[sp->parent[p]] = r; |
261 | } else { |
262 | sp->lchild[sp->parent[p]] = r; |
263 | } |
264 | sp->parent[p] = NIL; /* remove p */ |
265 | } |
266 | |
267 | /* deletes node p from tree */ |
268 | static void |
269 | delete_node(struct encode_state *sp, int p) |
270 | { |
271 | int q; |
272 | |
273 | if (sp->parent[p] == NIL) { |
274 | return; /* not in tree */ |
275 | } |
276 | if (sp->rchild[p] == NIL) { |
277 | q = sp->lchild[p]; |
278 | } else if (sp->lchild[p] == NIL) { |
279 | q = sp->rchild[p]; |
280 | } else { |
281 | q = sp->lchild[p]; |
282 | if (sp->rchild[q] != NIL) { |
283 | do { |
284 | q = sp->rchild[q]; |
285 | } while (sp->rchild[q] != NIL); |
286 | sp->rchild[sp->parent[q]] = sp->lchild[q]; |
287 | sp->parent[sp->lchild[q]] = sp->parent[q]; |
288 | sp->lchild[q] = sp->lchild[p]; |
289 | sp->parent[sp->lchild[p]] = q; |
290 | } |
291 | sp->rchild[q] = sp->rchild[p]; |
292 | sp->parent[sp->rchild[p]] = q; |
293 | } |
294 | sp->parent[q] = sp->parent[p]; |
295 | if (sp->rchild[sp->parent[p]] == p) { |
296 | sp->rchild[sp->parent[p]] = q; |
297 | } else { |
298 | sp->lchild[sp->parent[p]] = q; |
299 | } |
300 | sp->parent[p] = NIL; |
301 | } |
302 | |
303 | #endif /* !KERNEL */ |
304 | |