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) do { |
59 | s1 += *buf++; |
60 | s2 += s1; |
61 | } while (--k); |
62 | s1 %= BASE; |
63 | s2 %= BASE; |
64 | } |
65 | return (s2 << 16) | s1; |
66 | } |
67 | |
68 | |
69 | /************************************************************** |
70 | LZSS.C -- A Data Compression Program |
71 | *************************************************************** |
72 | 4/6/1989 Haruhiko Okumura |
73 | Use, distribute, and modify this program freely. |
74 | Please send me your improved versions. |
75 | PC-VAN SCIENCE |
76 | NIFTY-Serve PAF01022 |
77 | CompuServe 74050,1022 |
78 | |
79 | **************************************************************/ |
80 | |
81 | #define N 4096 /* size of ring buffer - must be power of 2 */ |
82 | #define F 18 /* upper limit for match_length */ |
83 | #define THRESHOLD 2 /* encode string into position and length |
84 | if match_length is greater than this */ |
85 | #if !KERNEL |
86 | #define NIL N /* index for root of binary search trees */ |
87 | #endif |
88 | |
89 | struct encode_state { |
90 | /* |
91 | * left & right children & parent. These constitute binary search trees. |
92 | */ |
93 | int lchild[N + 1], rchild[N + 257], parent[N + 1]; |
94 | |
95 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ |
96 | u_int8_t text_buf[N + F - 1]; |
97 | |
98 | /* |
99 | * match_length of longest match. |
100 | * These are set by the insert_node() procedure. |
101 | */ |
102 | int match_position, match_length; |
103 | }; |
104 | |
105 | |
106 | int |
107 | decompress_lzss(u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen) |
108 | { |
109 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ |
110 | u_int8_t text_buf[N + F - 1]; |
111 | u_int8_t *dststart = dst; |
112 | u_int8_t *dstend = dst + dstlen; |
113 | u_int8_t *srcend = src + srclen; |
114 | int i, j, k, r, c; |
115 | unsigned int flags; |
116 | |
117 | dst = dststart; |
118 | srcend = src + srclen; |
119 | for (i = 0; i < N - F; i++) |
120 | text_buf[i] = ' '; |
121 | r = N - F; |
122 | flags = 0; |
123 | for ( ; ; ) { |
124 | if (((flags >>= 1) & 0x100) == 0) { |
125 | if (src < srcend) c = *src++; else break; |
126 | flags = c | 0xFF00; /* uses higher byte cleverly */ |
127 | } /* to count eight */ |
128 | if (flags & 1) { |
129 | if (src < srcend) c = *src++; else break; |
130 | *dst++ = c; |
131 | if (dst >= dstend) { |
132 | goto finish; |
133 | } |
134 | text_buf[r++] = c; |
135 | r &= (N - 1); |
136 | } else { |
137 | if (src < srcend) i = *src++; else break; |
138 | if (src < srcend) j = *src++; else break; |
139 | i |= ((j & 0xF0) << 4); |
140 | j = (j & 0x0F) + THRESHOLD; |
141 | for (k = 0; k <= j; k++) { |
142 | c = text_buf[(i + k) & (N - 1)]; |
143 | *dst++ = c; |
144 | if (dst >= dstend) { |
145 | goto finish; |
146 | } |
147 | text_buf[r++] = c; |
148 | r &= (N - 1); |
149 | } |
150 | } |
151 | } |
152 | finish: |
153 | return dst - dststart; |
154 | } |
155 | |
156 | #if !KERNEL |
157 | |
158 | /* |
159 | * initialize state, mostly the trees |
160 | * |
161 | * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left |
162 | * children of node i. These nodes need not be initialized. Also, parent[i] |
163 | * is the parent of node i. These are initialized to NIL (= N), which stands |
164 | * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the |
165 | * tree for strings that begin with character i. These are initialized to NIL. |
166 | * Note there are 256 trees. */ |
167 | static void init_state(struct encode_state *sp) |
168 | { |
169 | int i; |
170 | |
171 | bzero(sp, sizeof(*sp)); |
172 | |
173 | for (i = 0; i < N - F; i++) |
174 | sp->text_buf[i] = ' '; |
175 | for (i = N + 1; i <= N + 256; i++) |
176 | sp->rchild[i] = NIL; |
177 | for (i = 0; i < N; i++) |
178 | sp->parent[i] = NIL; |
179 | } |
180 | |
181 | /* |
182 | * Inserts string of length F, text_buf[r..r+F-1], into one of the trees |
183 | * (text_buf[r]'th tree) and returns the longest-match position and length |
184 | * via the global variables match_position and match_length. |
185 | * If match_length = F, then removes the old node in favor of the new one, |
186 | * because the old one will be deleted sooner. Note r plays double role, |
187 | * as tree node and position in buffer. |
188 | */ |
189 | static void insert_node(struct encode_state *sp, int r) |
190 | { |
191 | int i, p, cmp; |
192 | u_int8_t *key; |
193 | |
194 | cmp = 1; |
195 | key = &sp->text_buf[r]; |
196 | p = N + 1 + key[0]; |
197 | sp->rchild[r] = sp->lchild[r] = NIL; |
198 | sp->match_length = 0; |
199 | for ( ; ; ) { |
200 | if (cmp >= 0) { |
201 | if (sp->rchild[p] != NIL) |
202 | p = sp->rchild[p]; |
203 | else { |
204 | sp->rchild[p] = r; |
205 | sp->parent[r] = p; |
206 | return; |
207 | } |
208 | } else { |
209 | if (sp->lchild[p] != NIL) |
210 | p = sp->lchild[p]; |
211 | else { |
212 | sp->lchild[p] = r; |
213 | sp->parent[r] = p; |
214 | return; |
215 | } |
216 | } |
217 | for (i = 1; i < F; i++) { |
218 | if ((cmp = key[i] - sp->text_buf[p + i]) != 0) |
219 | break; |
220 | } |
221 | if (i > sp->match_length) { |
222 | sp->match_position = p; |
223 | if ((sp->match_length = i) >= F) |
224 | break; |
225 | } |
226 | } |
227 | sp->parent[r] = sp->parent[p]; |
228 | sp->lchild[r] = sp->lchild[p]; |
229 | sp->rchild[r] = sp->rchild[p]; |
230 | sp->parent[sp->lchild[p]] = r; |
231 | sp->parent[sp->rchild[p]] = r; |
232 | if (sp->rchild[sp->parent[p]] == p) |
233 | sp->rchild[sp->parent[p]] = r; |
234 | else |
235 | sp->lchild[sp->parent[p]] = r; |
236 | sp->parent[p] = NIL; /* remove p */ |
237 | } |
238 | |
239 | /* deletes node p from tree */ |
240 | static void delete_node(struct encode_state *sp, int p) |
241 | { |
242 | int q; |
243 | |
244 | if (sp->parent[p] == NIL) |
245 | return; /* not in tree */ |
246 | if (sp->rchild[p] == NIL) |
247 | q = sp->lchild[p]; |
248 | else if (sp->lchild[p] == NIL) |
249 | q = sp->rchild[p]; |
250 | else { |
251 | q = sp->lchild[p]; |
252 | if (sp->rchild[q] != NIL) { |
253 | do { |
254 | q = sp->rchild[q]; |
255 | } while (sp->rchild[q] != NIL); |
256 | sp->rchild[sp->parent[q]] = sp->lchild[q]; |
257 | sp->parent[sp->lchild[q]] = sp->parent[q]; |
258 | sp->lchild[q] = sp->lchild[p]; |
259 | sp->parent[sp->lchild[p]] = q; |
260 | } |
261 | sp->rchild[q] = sp->rchild[p]; |
262 | sp->parent[sp->rchild[p]] = q; |
263 | } |
264 | sp->parent[q] = sp->parent[p]; |
265 | if (sp->rchild[sp->parent[p]] == p) |
266 | sp->rchild[sp->parent[p]] = q; |
267 | else |
268 | sp->lchild[sp->parent[p]] = q; |
269 | sp->parent[p] = NIL; |
270 | } |
271 | |
272 | #endif /* !KERNEL */ |
273 | |
274 | |