usr/src/uts/common/os/compress.c

   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
 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
 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
 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 }