17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
227c478bd9Sstevel@tonic-gate /*
237c478bd9Sstevel@tonic-gate * Copyright (c) 1998 by Sun Microsystems, Inc.
247c478bd9Sstevel@tonic-gate * All rights reserved.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate /*
287c478bd9Sstevel@tonic-gate * NOTE: this file is compiled into the kernel, cprboot, and savecore.
297c478bd9Sstevel@tonic-gate * Therefore it must compile in kernel, boot, and userland source context;
307c478bd9Sstevel@tonic-gate * so if you ever change this code, avoid references to external symbols.
317c478bd9Sstevel@tonic-gate *
327c478bd9Sstevel@tonic-gate * This compression algorithm is a derivative of LZRW1, which I'll call
337c478bd9Sstevel@tonic-gate * LZJB in the classic LZ* spirit. All LZ* (Lempel-Ziv) algorithms are
347c478bd9Sstevel@tonic-gate * based on the same basic principle: when a "phrase" (sequences of bytes)
357c478bd9Sstevel@tonic-gate * is repeated in a data stream, we can save space by storing a reference to
367c478bd9Sstevel@tonic-gate * the previous instance of that phrase (a "copy item") rather than storing
377c478bd9Sstevel@tonic-gate * the phrase itself (a "literal item"). The compressor remembers phrases
387c478bd9Sstevel@tonic-gate * in a simple hash table (the "Lempel history") that maps three-character
397c478bd9Sstevel@tonic-gate * sequences (the minimum match) to the addresses where they were last seen.
407c478bd9Sstevel@tonic-gate *
417c478bd9Sstevel@tonic-gate * A copy item must encode both the length and the location of the matching
427c478bd9Sstevel@tonic-gate * phrase so that decompress() can reconstruct the original data stream.
437c478bd9Sstevel@tonic-gate * For example, here's how we'd encode "yadda yadda yadda, blah blah blah"
447c478bd9Sstevel@tonic-gate * (with "_" replacing spaces for readability):
457c478bd9Sstevel@tonic-gate *
467c478bd9Sstevel@tonic-gate * Original:
477c478bd9Sstevel@tonic-gate *
487c478bd9Sstevel@tonic-gate * 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
497c478bd9Sstevel@tonic-gate *
507c478bd9Sstevel@tonic-gate * Compressed:
517c478bd9Sstevel@tonic-gate *
527c478bd9Sstevel@tonic-gate * y a d d a _ 6 11 , _ b l a h 5 10
537c478bd9Sstevel@tonic-gate *
547c478bd9Sstevel@tonic-gate * In the compressed output, the "6 11" simply means "to get the original
557c478bd9Sstevel@tonic-gate * data, execute memmove(ptr, ptr - 6, 11)". Note that in this example,
567c478bd9Sstevel@tonic-gate * the match at "6 11" actually extends beyond the current location and
577c478bd9Sstevel@tonic-gate * overlaps it. That's OK; like memmove(), decompress() handles overlap.
587c478bd9Sstevel@tonic-gate *
597c478bd9Sstevel@tonic-gate * There's still one more thing decompress() needs to know, which is how to
607c478bd9Sstevel@tonic-gate * distinguish literal items from copy items. We encode this information
617c478bd9Sstevel@tonic-gate * in an 8-bit bitmap that precedes each 8 items of output; if the Nth bit
627c478bd9Sstevel@tonic-gate * is set, then the Nth item is a copy item. Thus the full encoding for
637c478bd9Sstevel@tonic-gate * the example above would be:
647c478bd9Sstevel@tonic-gate *
657c478bd9Sstevel@tonic-gate * 0x40 y a d d a _ 6 11 , 0x20 _ b l a h 5 10
667c478bd9Sstevel@tonic-gate *
677c478bd9Sstevel@tonic-gate * Finally, the "6 11" isn't really encoded as the two byte values 6 and 11
687c478bd9Sstevel@tonic-gate * in the output stream because, empirically, we get better compression by
697c478bd9Sstevel@tonic-gate * dedicating more bits to offset, fewer to match length. LZJB uses 6 bits
707c478bd9Sstevel@tonic-gate * to encode the match length, 10 bits to encode the offset. Since copy-item
717c478bd9Sstevel@tonic-gate * encoding consumes 2 bytes, we don't generate copy items unless the match
727c478bd9Sstevel@tonic-gate * length is at least 3; therefore, we can store (length - 3) in the 6-bit
737c478bd9Sstevel@tonic-gate * match length field, which extends the maximum match from 63 to 66 bytes.
747c478bd9Sstevel@tonic-gate * Thus the 2-byte encoding for a copy item is as follows:
757c478bd9Sstevel@tonic-gate *
767c478bd9Sstevel@tonic-gate * byte[0] = ((length - 3) << 2) | (offset >> 8);
777c478bd9Sstevel@tonic-gate * byte[1] = (uint8_t)offset;
787c478bd9Sstevel@tonic-gate *
797c478bd9Sstevel@tonic-gate * In our example above, an offset of 6 with length 11 would be encoded as:
807c478bd9Sstevel@tonic-gate *
817c478bd9Sstevel@tonic-gate * byte[0] = ((11 - 3) << 2) | (6 >> 8) = 0x20
827c478bd9Sstevel@tonic-gate * byte[1] = (uint8_t)6 = 0x6
837c478bd9Sstevel@tonic-gate *
847c478bd9Sstevel@tonic-gate * Similarly, an offset of 5 with length 10 would be encoded as:
857c478bd9Sstevel@tonic-gate *
867c478bd9Sstevel@tonic-gate * byte[0] = ((10 - 3) << 2) | (5 >> 8) = 0x1c
877c478bd9Sstevel@tonic-gate * byte[1] = (uint8_t)5 = 0x5
887c478bd9Sstevel@tonic-gate *
897c478bd9Sstevel@tonic-gate * Putting it all together, the actual LZJB output for our example is:
907c478bd9Sstevel@tonic-gate *
917c478bd9Sstevel@tonic-gate * 0x40 y a d d a _ 0x2006 , 0x20 _ b l a h 0x1c05
927c478bd9Sstevel@tonic-gate *
937c478bd9Sstevel@tonic-gate * The main differences between LZRW1 and LZJB are as follows:
947c478bd9Sstevel@tonic-gate *
957c478bd9Sstevel@tonic-gate * (1) LZRW1 is sloppy about buffer overruns. LZJB never reads past the
967c478bd9Sstevel@tonic-gate * end of its input, and never writes past the end of its output.
977c478bd9Sstevel@tonic-gate *
987c478bd9Sstevel@tonic-gate * (2) LZJB allows a maximum match length of 66 (vs. 18 for LZRW1), with
997c478bd9Sstevel@tonic-gate * the trade-off being a shorter look-behind (1K vs. 4K for LZRW1).
1007c478bd9Sstevel@tonic-gate *
1017c478bd9Sstevel@tonic-gate * (3) LZJB records only the low-order 16 bits of pointers in the Lempel
1027c478bd9Sstevel@tonic-gate * history (which is all we need since the maximum look-behind is 1K),
1037c478bd9Sstevel@tonic-gate * and uses only 256 hash entries (vs. 4096 for LZRW1). This makes
1047c478bd9Sstevel@tonic-gate * the compression hash small enough to allocate on the stack, which
1057c478bd9Sstevel@tonic-gate * solves two problems: (1) it saves 64K of kernel/cprboot memory,
1067c478bd9Sstevel@tonic-gate * and (2) it makes the code MT-safe without any locking, since we
1077c478bd9Sstevel@tonic-gate * don't have multiple threads sharing a common hash table.
1087c478bd9Sstevel@tonic-gate *
1097c478bd9Sstevel@tonic-gate * (4) LZJB is faster at both compression and decompression, has a
1107c478bd9Sstevel@tonic-gate * better compression ratio, and is somewhat simpler than LZRW1.
1117c478bd9Sstevel@tonic-gate *
1127c478bd9Sstevel@tonic-gate * Finally, note that LZJB is non-deterministic: given the same input,
1137c478bd9Sstevel@tonic-gate * two calls to compress() may produce different output. This is a
1147c478bd9Sstevel@tonic-gate * general characteristic of most Lempel-Ziv derivatives because there's
1157c478bd9Sstevel@tonic-gate * no need to initialize the Lempel history; not doing so saves time.
1167c478bd9Sstevel@tonic-gate */
1177c478bd9Sstevel@tonic-gate
1187c478bd9Sstevel@tonic-gate #include <sys/types.h>
119*6d89ca53SIgor Kozhukhov #include <sys/param.h>
1207c478bd9Sstevel@tonic-gate
1217c478bd9Sstevel@tonic-gate #define MATCH_BITS 6
1227c478bd9Sstevel@tonic-gate #define MATCH_MIN 3
1237c478bd9Sstevel@tonic-gate #define MATCH_MAX ((1 << MATCH_BITS) + (MATCH_MIN - 1))
1247c478bd9Sstevel@tonic-gate #define OFFSET_MASK ((1 << (16 - MATCH_BITS)) - 1)
1257c478bd9Sstevel@tonic-gate #define LEMPEL_SIZE 256
1267c478bd9Sstevel@tonic-gate
1277c478bd9Sstevel@tonic-gate size_t
compress(void * s_start,void * d_start,size_t s_len)1287c478bd9Sstevel@tonic-gate compress(void *s_start, void *d_start, size_t s_len)
1297c478bd9Sstevel@tonic-gate {
1307c478bd9Sstevel@tonic-gate uchar_t *src = s_start;
1317c478bd9Sstevel@tonic-gate uchar_t *dst = d_start;
132*6d89ca53SIgor Kozhukhov uchar_t *cpy, *copymap = NULL;
1337c478bd9Sstevel@tonic-gate int copymask = 1 << (NBBY - 1);
1347c478bd9Sstevel@tonic-gate int mlen, offset;
1357c478bd9Sstevel@tonic-gate uint16_t *hp;
1367c478bd9Sstevel@tonic-gate uint16_t lempel[LEMPEL_SIZE]; /* uninitialized; see above */
1377c478bd9Sstevel@tonic-gate
1387c478bd9Sstevel@tonic-gate while (src < (uchar_t *)s_start + s_len) {
1397c478bd9Sstevel@tonic-gate if ((copymask <<= 1) == (1 << NBBY)) {
1407c478bd9Sstevel@tonic-gate if (dst >= (uchar_t *)d_start + s_len - 1 - 2 * NBBY) {
1417c478bd9Sstevel@tonic-gate mlen = s_len;
1427c478bd9Sstevel@tonic-gate for (src = s_start, dst = d_start; mlen; mlen--)
1437c478bd9Sstevel@tonic-gate *dst++ = *src++;
1447c478bd9Sstevel@tonic-gate return (s_len);
1457c478bd9Sstevel@tonic-gate }
1467c478bd9Sstevel@tonic-gate copymask = 1;
1477c478bd9Sstevel@tonic-gate copymap = dst;
1487c478bd9Sstevel@tonic-gate *dst++ = 0;
1497c478bd9Sstevel@tonic-gate }
1507c478bd9Sstevel@tonic-gate if (src > (uchar_t *)s_start + s_len - MATCH_MAX) {
1517c478bd9Sstevel@tonic-gate *dst++ = *src++;
1527c478bd9Sstevel@tonic-gate continue;
1537c478bd9Sstevel@tonic-gate }
1547c478bd9Sstevel@tonic-gate hp = &lempel[((src[0] + 13) ^ (src[1] - 13) ^ src[2]) &
1557c478bd9Sstevel@tonic-gate (LEMPEL_SIZE - 1)];
1567c478bd9Sstevel@tonic-gate offset = (intptr_t)(src - *hp) & OFFSET_MASK;
1577c478bd9Sstevel@tonic-gate *hp = (uint16_t)(uintptr_t)src;
1587c478bd9Sstevel@tonic-gate cpy = src - offset;
1597c478bd9Sstevel@tonic-gate if (cpy >= (uchar_t *)s_start && cpy != src &&
1607c478bd9Sstevel@tonic-gate src[0] == cpy[0] && src[1] == cpy[1] && src[2] == cpy[2]) {
1617c478bd9Sstevel@tonic-gate *copymap |= copymask;
1627c478bd9Sstevel@tonic-gate for (mlen = MATCH_MIN; mlen < MATCH_MAX; mlen++)
1637c478bd9Sstevel@tonic-gate if (src[mlen] != cpy[mlen])
1647c478bd9Sstevel@tonic-gate break;
1657c478bd9Sstevel@tonic-gate *dst++ = ((mlen - MATCH_MIN) << (NBBY - MATCH_BITS)) |
1667c478bd9Sstevel@tonic-gate (offset >> NBBY);
1677c478bd9Sstevel@tonic-gate *dst++ = (uchar_t)offset;
1687c478bd9Sstevel@tonic-gate src += mlen;
1697c478bd9Sstevel@tonic-gate } else {
1707c478bd9Sstevel@tonic-gate *dst++ = *src++;
1717c478bd9Sstevel@tonic-gate }
1727c478bd9Sstevel@tonic-gate }
1737c478bd9Sstevel@tonic-gate return (dst - (uchar_t *)d_start);
1747c478bd9Sstevel@tonic-gate }
1757c478bd9Sstevel@tonic-gate
1767c478bd9Sstevel@tonic-gate size_t
decompress(void * s_start,void * d_start,size_t s_len,size_t d_len)1777c478bd9Sstevel@tonic-gate decompress(void *s_start, void *d_start, size_t s_len, size_t d_len)
1787c478bd9Sstevel@tonic-gate {
1797c478bd9Sstevel@tonic-gate uchar_t *src = s_start;
1807c478bd9Sstevel@tonic-gate uchar_t *dst = d_start;
1817c478bd9Sstevel@tonic-gate uchar_t *s_end = (uchar_t *)s_start + s_len;
1827c478bd9Sstevel@tonic-gate uchar_t *d_end = (uchar_t *)d_start + d_len;
183*6d89ca53SIgor Kozhukhov uchar_t *cpy, copymap = '\0';
1847c478bd9Sstevel@tonic-gate int copymask = 1 << (NBBY - 1);
1857c478bd9Sstevel@tonic-gate
1867c478bd9Sstevel@tonic-gate if (s_len >= d_len) {
1877c478bd9Sstevel@tonic-gate size_t d_rem = d_len;
1887c478bd9Sstevel@tonic-gate while (d_rem-- != 0)
1897c478bd9Sstevel@tonic-gate *dst++ = *src++;
1907c478bd9Sstevel@tonic-gate return (d_len);
1917c478bd9Sstevel@tonic-gate }
1927c478bd9Sstevel@tonic-gate
1937c478bd9Sstevel@tonic-gate while (src < s_end && dst < d_end) {
1947c478bd9Sstevel@tonic-gate if ((copymask <<= 1) == (1 << NBBY)) {
1957c478bd9Sstevel@tonic-gate copymask = 1;
1967c478bd9Sstevel@tonic-gate copymap = *src++;
1977c478bd9Sstevel@tonic-gate }
1987c478bd9Sstevel@tonic-gate if (copymap & copymask) {
1997c478bd9Sstevel@tonic-gate int mlen = (src[0] >> (NBBY - MATCH_BITS)) + MATCH_MIN;
2007c478bd9Sstevel@tonic-gate int offset = ((src[0] << NBBY) | src[1]) & OFFSET_MASK;
2017c478bd9Sstevel@tonic-gate src += 2;
2027c478bd9Sstevel@tonic-gate if ((cpy = dst - offset) >= (uchar_t *)d_start)
2037c478bd9Sstevel@tonic-gate while (--mlen >= 0 && dst < d_end)
2047c478bd9Sstevel@tonic-gate *dst++ = *cpy++;
2057c478bd9Sstevel@tonic-gate else
2067c478bd9Sstevel@tonic-gate /*
2077c478bd9Sstevel@tonic-gate * offset before start of destination buffer
2087c478bd9Sstevel@tonic-gate * indicates corrupt source data
2097c478bd9Sstevel@tonic-gate */
2107c478bd9Sstevel@tonic-gate return (dst - (uchar_t *)d_start);
2117c478bd9Sstevel@tonic-gate } else {
2127c478bd9Sstevel@tonic-gate *dst++ = *src++;
2137c478bd9Sstevel@tonic-gate }
2147c478bd9Sstevel@tonic-gate }
2157c478bd9Sstevel@tonic-gate return (dst - (uchar_t *)d_start);
2167c478bd9Sstevel@tonic-gate }
2177c478bd9Sstevel@tonic-gate
2187c478bd9Sstevel@tonic-gate uint32_t
checksum32(void * cp_arg,size_t length)2197c478bd9Sstevel@tonic-gate checksum32(void *cp_arg, size_t length)
2207c478bd9Sstevel@tonic-gate {
2217c478bd9Sstevel@tonic-gate uchar_t *cp, *ep;
2227c478bd9Sstevel@tonic-gate uint32_t sum = 0;
2237c478bd9Sstevel@tonic-gate
2247c478bd9Sstevel@tonic-gate for (cp = cp_arg, ep = cp + length; cp < ep; cp++)
2257c478bd9Sstevel@tonic-gate sum = ((sum >> 1) | (sum << 31)) + *cp;
2267c478bd9Sstevel@tonic-gate return (sum);
2277c478bd9Sstevel@tonic-gate }
228