1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright (c) 1998 by Sun Microsystems, Inc.
24 * All rights reserved.
25 */
26
27 /*
28 * NOTE: this file is compiled into the kernel, cprboot, and savecore.
29 * Therefore it must compile in kernel, boot, and userland source context;
30 * so if you ever change this code, avoid references to external symbols.
31 *
32 * This compression algorithm is a derivative of LZRW1, which I'll call
33 * LZJB in the classic LZ* spirit. All LZ* (Lempel-Ziv) algorithms are
34 * based on the same basic principle: when a "phrase" (sequences of bytes)
35 * is repeated in a data stream, we can save space by storing a reference to
36 * the previous instance of that phrase (a "copy item") rather than storing
37 * the phrase itself (a "literal item"). The compressor remembers phrases
38 * in a simple hash table (the "Lempel history") that maps three-character
39 * sequences (the minimum match) to the addresses where they were last seen.
40 *
41 * A copy item must encode both the length and the location of the matching
42 * phrase so that decompress() can reconstruct the original data stream.
43 * For example, here's how we'd encode "yadda yadda yadda, blah blah blah"
44 * (with "_" replacing spaces for readability):
45 *
46 * Original:
47 *
48 * y a d d a _ y a d d a _ y a d d a , _ b l a h _ b l a h _ b l a h
49 *
50 * Compressed:
51 *
52 * y a d d a _ 6 11 , _ b l a h 5 10
53 *
54 * In the compressed output, the "6 11" simply means "to get the original
55 * data, execute memmove(ptr, ptr - 6, 11)". Note that in this example,
56 * the match at "6 11" actually extends beyond the current location and
57 * overlaps it. That's OK; like memmove(), decompress() handles overlap.
58 *
59 * There's still one more thing decompress() needs to know, which is how to
60 * distinguish literal items from copy items. We encode this information
61 * in an 8-bit bitmap that precedes each 8 items of output; if the Nth bit
62 * is set, then the Nth item is a copy item. Thus the full encoding for
63 * the example above would be:
64 *
65 * 0x40 y a d d a _ 6 11 , 0x20 _ b l a h 5 10
66 *
67 * Finally, the "6 11" isn't really encoded as the two byte values 6 and 11
68 * in the output stream because, empirically, we get better compression by
69 * dedicating more bits to offset, fewer to match length. LZJB uses 6 bits
70 * to encode the match length, 10 bits to encode the offset. Since copy-item
71 * encoding consumes 2 bytes, we don't generate copy items unless the match
72 * length is at least 3; therefore, we can store (length - 3) in the 6-bit
73 * match length field, which extends the maximum match from 63 to 66 bytes.
74 * Thus the 2-byte encoding for a copy item is as follows:
75 *
76 * byte[0] = ((length - 3) << 2) | (offset >> 8);
77 * byte[1] = (uint8_t)offset;
78 *
79 * In our example above, an offset of 6 with length 11 would be encoded as:
80 *
81 * byte[0] = ((11 - 3) << 2) | (6 >> 8) = 0x20
82 * byte[1] = (uint8_t)6 = 0x6
83 *
84 * Similarly, an offset of 5 with length 10 would be encoded as:
85 *
86 * byte[0] = ((10 - 3) << 2) | (5 >> 8) = 0x1c
87 * byte[1] = (uint8_t)5 = 0x5
88 *
89 * Putting it all together, the actual LZJB output for our example is:
90 *
91 * 0x40 y a d d a _ 0x2006 , 0x20 _ b l a h 0x1c05
92 *
93 * The main differences between LZRW1 and LZJB are as follows:
94 *
95 * (1) LZRW1 is sloppy about buffer overruns. LZJB never reads past the
96 * end of its input, and never writes past the end of its output.
97 *
98 * (2) LZJB allows a maximum match length of 66 (vs. 18 for LZRW1), with
99 * the trade-off being a shorter look-behind (1K vs. 4K for LZRW1).
100 *
101 * (3) LZJB records only the low-order 16 bits of pointers in the Lempel
102 * history (which is all we need since the maximum look-behind is 1K),
103 * and uses only 256 hash entries (vs. 4096 for LZRW1). This makes
104 * the compression hash small enough to allocate on the stack, which
105 * solves two problems: (1) it saves 64K of kernel/cprboot memory,
106 * and (2) it makes the code MT-safe without any locking, since we
107 * don't have multiple threads sharing a common hash table.
108 *
109 * (4) LZJB is faster at both compression and decompression, has a
110 * better compression ratio, and is somewhat simpler than LZRW1.
111 *
112 * Finally, note that LZJB is non-deterministic: given the same input,
113 * two calls to compress() may produce different output. This is a
114 * general characteristic of most Lempel-Ziv derivatives because there's
115 * no need to initialize the Lempel history; not doing so saves time.
116 */
117
118 #include <sys/types.h>
119 #include <sys/param.h>
120
121 #define MATCH_BITS 6
122 #define MATCH_MIN 3
123 #define MATCH_MAX ((1 << MATCH_BITS) + (MATCH_MIN - 1))
124 #define OFFSET_MASK ((1 << (16 - MATCH_BITS)) - 1)
125 #define LEMPEL_SIZE 256
126
127 size_t
compress(void * s_start,void * d_start,size_t s_len)128 compress(void *s_start, void *d_start, size_t s_len)
129 {
130 uchar_t *src = s_start;
131 uchar_t *dst = d_start;
132 uchar_t *cpy, *copymap = NULL;
133 int copymask = 1 << (NBBY - 1);
134 int mlen, offset;
135 uint16_t *hp;
136 uint16_t lempel[LEMPEL_SIZE]; /* uninitialized; see above */
137
138 while (src < (uchar_t *)s_start + s_len) {
139 if ((copymask <<= 1) == (1 << NBBY)) {
140 if (dst >= (uchar_t *)d_start + s_len - 1 - 2 * NBBY) {
141 mlen = s_len;
142 for (src = s_start, dst = d_start; mlen; mlen--)
143 *dst++ = *src++;
144 return (s_len);
145 }
146 copymask = 1;
147 copymap = dst;
148 *dst++ = 0;
149 }
150 if (src > (uchar_t *)s_start + s_len - MATCH_MAX) {
151 *dst++ = *src++;
152 continue;
153 }
154 hp = &lempel[((src[0] + 13) ^ (src[1] - 13) ^ src[2]) &
155 (LEMPEL_SIZE - 1)];
156 offset = (intptr_t)(src - *hp) & OFFSET_MASK;
157 *hp = (uint16_t)(uintptr_t)src;
158 cpy = src - offset;
159 if (cpy >= (uchar_t *)s_start && cpy != src &&
160 src[0] == cpy[0] && src[1] == cpy[1] && src[2] == cpy[2]) {
161 *copymap |= copymask;
162 for (mlen = MATCH_MIN; mlen < MATCH_MAX; mlen++)
163 if (src[mlen] != cpy[mlen])
164 break;
165 *dst++ = ((mlen - MATCH_MIN) << (NBBY - MATCH_BITS)) |
166 (offset >> NBBY);
167 *dst++ = (uchar_t)offset;
168 src += mlen;
169 } else {
170 *dst++ = *src++;
171 }
172 }
173 return (dst - (uchar_t *)d_start);
174 }
175
176 size_t
decompress(void * s_start,void * d_start,size_t s_len,size_t d_len)177 decompress(void *s_start, void *d_start, size_t s_len, size_t d_len)
178 {
179 uchar_t *src = s_start;
180 uchar_t *dst = d_start;
181 uchar_t *s_end = (uchar_t *)s_start + s_len;
182 uchar_t *d_end = (uchar_t *)d_start + d_len;
183 uchar_t *cpy, copymap = '\0';
184 int copymask = 1 << (NBBY - 1);
185
186 if (s_len >= d_len) {
187 size_t d_rem = d_len;
188 while (d_rem-- != 0)
189 *dst++ = *src++;
190 return (d_len);
191 }
192
193 while (src < s_end && dst < d_end) {
194 if ((copymask <<= 1) == (1 << NBBY)) {
195 copymask = 1;
196 copymap = *src++;
197 }
198 if (copymap & copymask) {
199 int mlen = (src[0] >> (NBBY - MATCH_BITS)) + MATCH_MIN;
200 int offset = ((src[0] << NBBY) | src[1]) & OFFSET_MASK;
201 src += 2;
202 if ((cpy = dst - offset) >= (uchar_t *)d_start)
203 while (--mlen >= 0 && dst < d_end)
204 *dst++ = *cpy++;
205 else
206 /*
207 * offset before start of destination buffer
208 * indicates corrupt source data
209 */
210 return (dst - (uchar_t *)d_start);
211 } else {
212 *dst++ = *src++;
213 }
214 }
215 return (dst - (uchar_t *)d_start);
216 }
217
218 uint32_t
checksum32(void * cp_arg,size_t length)219 checksum32(void *cp_arg, size_t length)
220 {
221 uchar_t *cp, *ep;
222 uint32_t sum = 0;
223
224 for (cp = cp_arg, ep = cp + length; cp < ep; cp++)
225 sum = ((sum >> 1) | (sum << 31)) + *cp;
226 return (sum);
227 }
228