| 1 | /*␊ |
| 2 | * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.␊ |
| 3 | *␊ |
| 4 | * @APPLE_LICENSE_HEADER_START@␊ |
| 5 | * ␊ |
| 6 | * Portions Copyright (c) 1999-2003 Apple Computer, Inc. All Rights␊ |
| 7 | * Reserved. This file contains Original Code and/or Modifications of␊ |
| 8 | * Original Code as defined in and that are subject to the Apple Public␊ |
| 9 | * Source License Version 2.0 (the "License"). You may not use this file␊ |
| 10 | * except in compliance with the License. Please obtain a copy of the␊ |
| 11 | * License at http://www.apple.com/publicsource and read it before using␊ |
| 12 | * this file.␊ |
| 13 | * ␊ |
| 14 | * The Original Code and all software distributed under the License are␊ |
| 15 | * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER␊ |
| 16 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,␊ |
| 17 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,␊ |
| 18 | * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the␊ |
| 19 | * License for the specific language governing rights and limitations␊ |
| 20 | * under the License.␊ |
| 21 | * ␊ |
| 22 | * @APPLE_LICENSE_HEADER_END@␊ |
| 23 | */␊ |
| 24 | /**************************************************************␊ |
| 25 | LZSS.C -- A Data Compression Program␊ |
| 26 | ***************************************************************␊ |
| 27 | 4/6/1989 Haruhiko Okumura␊ |
| 28 | Use, distribute, and modify this program freely.␊ |
| 29 | Please send me your improved versions.␊ |
| 30 | PC-VAN SCIENCE␊ |
| 31 | NIFTY-Serve PAF01022␊ |
| 32 | CompuServe 74050,1022␊ |
| 33 | ␊ |
| 34 | **************************************************************/␊ |
| 35 | /*␊ |
| 36 | * lzss.c - Package for decompressing lzss compressed objects␊ |
| 37 | *␊ |
| 38 | * Copyright (c) 2003 Apple Computer, Inc.␊ |
| 39 | *␊ |
| 40 | * DRI: Josh de Cesare␊ |
| 41 | */␊ |
| 42 | ␊ |
| 43 | #include <sl.h>␊ |
| 44 | ␊ |
| 45 | #define N 4096 /* size of ring buffer - must be power of 2 */␊ |
| 46 | #define F 18 /* upper limit for match_length */␊ |
| 47 | #define THRESHOLD 2 /* encode string into position and length␊ |
| 48 | if match_length is greater than this */␊ |
| 49 | #define NIL N /* index for root of binary search trees */␊ |
| 50 | ␊ |
| 51 | struct encode_state {␊ |
| 52 | /*␊ |
| 53 | * left & right children & parent. These constitute binary search trees.␊ |
| 54 | */␊ |
| 55 | ␉int lchild[N + 1], rchild[N + 257], parent[N + 1];␊ |
| 56 | ␊ |
| 57 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */␊ |
| 58 | ␉u_int8_t text_buf[N + F - 1];␊ |
| 59 | ␊ |
| 60 | /*␊ |
| 61 | * match_length of longest match.␊ |
| 62 | * These are set by the insert_node() procedure.␊ |
| 63 | */␊ |
| 64 | ␉int match_position, match_length;␊ |
| 65 | };␊ |
| 66 | ␊ |
| 67 | int decompress_lzss( u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen )␊ |
| 68 | {␊ |
| 69 | /* ring buffer of size N, with extra F-1 bytes to aid string comparison */␊ |
| 70 | u_int8_t text_buf[N + F - 1];␊ |
| 71 | u_int8_t *dststart = dst;␊ |
| 72 | u_int8_t *dstend = dst + dstlen;␊ |
| 73 | u_int8_t *srcend = src + srclen;␊ |
| 74 | int i, j, k, r, c;␊ |
| 75 | unsigned int flags;␊ |
| 76 | ␊ |
| 77 | dst = dststart;␊ |
| 78 | srcend = src + srclen;␊ |
| 79 | for (i = 0; i < N - F; i++)␊ |
| 80 | text_buf[i] = ' ';␊ |
| 81 | r = N - F;␊ |
| 82 | flags = 0;␊ |
| 83 | for ( ; ; ) {␊ |
| 84 | if (((flags >>= 1) & 0x100) == 0) {␊ |
| 85 | if (src < srcend) c = *src++; else break;␊ |
| 86 | flags = c | 0xFF00; /* uses higher byte cleverly */␊ |
| 87 | } /* to count eight */␊ |
| 88 | if (flags & 1) {␊ |
| 89 | if (src < srcend) c = *src++; else break;␊ |
| 90 | *dst++ = c;␊ |
| 91 | if (dst >= dstend) {␊ |
| 92 | goto finish;␊ |
| 93 | }␊ |
| 94 | text_buf[r++] = c;␊ |
| 95 | r &= (N - 1);␊ |
| 96 | } else {␊ |
| 97 | if (src < srcend) i = *src++; else break;␊ |
| 98 | if (src < srcend) j = *src++; else break;␊ |
| 99 | i |= ((j & 0xF0) << 4);␊ |
| 100 | j = (j & 0x0F) + THRESHOLD;␊ |
| 101 | for (k = 0; k <= j; k++) {␊ |
| 102 | c = text_buf[(i + k) & (N - 1)];␊ |
| 103 | *dst++ = c;␊ |
| 104 | if (dst >= dstend) {␊ |
| 105 | goto finish;␊ |
| 106 | }␊ |
| 107 | text_buf[r++] = c;␊ |
| 108 | r &= (N - 1);␊ |
| 109 | }␊ |
| 110 | }␊ |
| 111 | }␊ |
| 112 | finish:␊ |
| 113 | return dst - dststart;␊ |
| 114 | }␊ |
| 115 | ␊ |
| 116 | /*␊ |
| 117 | * initialize state, mostly the trees␊ |
| 118 | *␊ |
| 119 | * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left␊ |
| 120 | * children of node i. These nodes need not be initialized. Also, parent[i]␊ |
| 121 | * is the parent of node i. These are initialized to NIL (= N), which stands␊ |
| 122 | * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the␊ |
| 123 | * tree for strings that begin with character i. These are initialized to NIL.␊ |
| 124 | * Note there are 256 trees. */␊ |
| 125 | static void init_state(struct encode_state *sp)␊ |
| 126 | {␊ |
| 127 | int i;␊ |
| 128 | ␊ |
| 129 | bzero(sp, sizeof(*sp));␊ |
| 130 | ␊ |
| 131 | for (i = 0; i < N - F; i++)␊ |
| 132 | sp->text_buf[i] = ' ';␊ |
| 133 | for (i = N + 1; i <= N + 256; i++)␊ |
| 134 | sp->rchild[i] = NIL;␊ |
| 135 | for (i = 0; i < N; i++)␊ |
| 136 | sp->parent[i] = NIL;␊ |
| 137 | }␊ |
| 138 | ␊ |
| 139 | /*␊ |
| 140 | * Inserts string of length F, text_buf[r..r+F-1], into one of the trees␊ |
| 141 | * (text_buf[r]'th tree) and returns the longest-match position and length␊ |
| 142 | * via the global variables match_position and match_length.␊ |
| 143 | * If match_length = F, then removes the old node in favor of the new one,␊ |
| 144 | * because the old one will be deleted sooner. Note r plays double role,␊ |
| 145 | * as tree node and position in buffer.␊ |
| 146 | */␊ |
| 147 | static void insert_node(struct encode_state *sp, int r)␊ |
| 148 | {␊ |
| 149 | int i, p, cmp;␊ |
| 150 | u_int8_t *key;␊ |
| 151 | ␊ |
| 152 | cmp = 1;␊ |
| 153 | key = &sp->text_buf[r];␊ |
| 154 | p = N + 1 + key[0];␊ |
| 155 | sp->rchild[r] = sp->lchild[r] = NIL;␊ |
| 156 | sp->match_length = 0;␊ |
| 157 | for ( ; ; ) {␊ |
| 158 | if (cmp >= 0) {␊ |
| 159 | if (sp->rchild[p] != NIL)␊ |
| 160 | p = sp->rchild[p];␊ |
| 161 | else {␊ |
| 162 | sp->rchild[p] = r;␊ |
| 163 | sp->parent[r] = p;␊ |
| 164 | return;␊ |
| 165 | }␊ |
| 166 | } else {␊ |
| 167 | if (sp->lchild[p] != NIL)␊ |
| 168 | p = sp->lchild[p];␊ |
| 169 | else {␊ |
| 170 | sp->lchild[p] = r;␊ |
| 171 | sp->parent[r] = p;␊ |
| 172 | return;␊ |
| 173 | }␊ |
| 174 | }␊ |
| 175 | for (i = 1; i < F; i++) {␊ |
| 176 | if ((cmp = key[i] - sp->text_buf[p + i]) != 0)␊ |
| 177 | break;␊ |
| 178 | }␊ |
| 179 | if (i > sp->match_length) {␊ |
| 180 | sp->match_position = p;␊ |
| 181 | if ((sp->match_length = i) >= F)␊ |
| 182 | break;␊ |
| 183 | }␊ |
| 184 | }␊ |
| 185 | sp->parent[r] = sp->parent[p];␊ |
| 186 | sp->lchild[r] = sp->lchild[p];␊ |
| 187 | sp->rchild[r] = sp->rchild[p];␊ |
| 188 | sp->parent[sp->lchild[p]] = r;␊ |
| 189 | sp->parent[sp->rchild[p]] = r;␊ |
| 190 | if (sp->rchild[sp->parent[p]] == p)␊ |
| 191 | sp->rchild[sp->parent[p]] = r;␊ |
| 192 | else␊ |
| 193 | sp->lchild[sp->parent[p]] = r;␊ |
| 194 | sp->parent[p] = NIL; /* remove p */␊ |
| 195 | }␊ |
| 196 | ␊ |
| 197 | /* deletes node p from tree */␊ |
| 198 | static void delete_node(struct encode_state *sp, int p)␊ |
| 199 | {␊ |
| 200 | int q;␊ |
| 201 | ␊ |
| 202 | if (sp->parent[p] == NIL)␊ |
| 203 | return; /* not in tree */␊ |
| 204 | if (sp->rchild[p] == NIL)␊ |
| 205 | q = sp->lchild[p];␊ |
| 206 | else if (sp->lchild[p] == NIL)␊ |
| 207 | q = sp->rchild[p];␊ |
| 208 | else {␊ |
| 209 | q = sp->lchild[p];␊ |
| 210 | if (sp->rchild[q] != NIL) {␊ |
| 211 | do {␊ |
| 212 | q = sp->rchild[q];␊ |
| 213 | } while (sp->rchild[q] != NIL);␊ |
| 214 | sp->rchild[sp->parent[q]] = sp->lchild[q];␊ |
| 215 | sp->parent[sp->lchild[q]] = sp->parent[q];␊ |
| 216 | sp->lchild[q] = sp->lchild[p];␊ |
| 217 | sp->parent[sp->lchild[p]] = q;␊ |
| 218 | }␊ |
| 219 | sp->rchild[q] = sp->rchild[p];␊ |
| 220 | sp->parent[sp->rchild[p]] = q;␊ |
| 221 | }␊ |
| 222 | sp->parent[q] = sp->parent[p];␊ |
| 223 | if (sp->rchild[sp->parent[p]] == p)␊ |
| 224 | sp->rchild[sp->parent[p]] = q;␊ |
| 225 | else␊ |
| 226 | sp->lchild[sp->parent[p]] = q;␊ |
| 227 | sp->parent[p] = NIL;␊ |
| 228 | }␊ |
| 229 | ␊ |
| 230 | u_int8_t *compress_lzss( u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen )␊ |
| 231 | {␊ |
| 232 | /* Encoding state, mostly tree but some current match stuff */␊ |
| 233 | struct encode_state *sp;␊ |
| 234 | ␊ |
| 235 | int i, c, len, r, s, last_match_length, code_buf_ptr;␊ |
| 236 | u_int8_t code_buf[17], mask;␊ |
| 237 | u_int8_t *srcend = src + srclen;␊ |
| 238 | u_int8_t *dstend = dst + dstlen;␊ |
| 239 | ␊ |
| 240 | /* initialize trees */␊ |
| 241 | sp = (struct encode_state *) malloc(sizeof(*sp));␊ |
| 242 | init_state(sp);␊ |
| 243 | ␊ |
| 244 | /*␊ |
| 245 | * code_buf[1..16] saves eight units of code, and code_buf[0] works␊ |
| 246 | * as eight flags, "1" representing that the unit is an unencoded␊ |
| 247 | * letter (1 byte), "0" a position-and-length pair (2 bytes).␊ |
| 248 | * Thus, eight units require at most 16 bytes of code.␊ |
| 249 | */␊ |
| 250 | code_buf[0] = 0;␊ |
| 251 | code_buf_ptr = mask = 1;␊ |
| 252 | ␊ |
| 253 | /* Clear the buffer with any character that will appear often. */␊ |
| 254 | s = 0; r = N - F;␊ |
| 255 | ␊ |
| 256 | /* Read F bytes into the last F bytes of the buffer */␊ |
| 257 | for (len = 0; len < F && src < srcend; len++)␊ |
| 258 | sp->text_buf[r + len] = *src++;␊ |
| 259 | if (!len)␊ |
| 260 | return (void *) 0; /* text of size zero */␊ |
| 261 | ␊ |
| 262 | /*␊ |
| 263 | * Insert the F strings, each of which begins with one or more␊ |
| 264 | * 'space' characters. Note the order in which these strings are␊ |
| 265 | * inserted. This way, degenerate trees will be less likely to occur.␊ |
| 266 | */␊ |
| 267 | for (i = 1; i <= F; i++)␊ |
| 268 | insert_node(sp, r - i);␊ |
| 269 | ␊ |
| 270 | /*␊ |
| 271 | * Finally, insert the whole string just read.␊ |
| 272 | * The global variables match_length and match_position are set.␊ |
| 273 | */␊ |
| 274 | insert_node(sp, r);␊ |
| 275 | do {␊ |
| 276 | /* match_length may be spuriously long near the end of text. */␊ |
| 277 | if (sp->match_length > len)␊ |
| 278 | sp->match_length = len;␊ |
| 279 | if (sp->match_length <= THRESHOLD) {␊ |
| 280 | sp->match_length = 1; /* Not long enough match. Send one byte. */␊ |
| 281 | code_buf[0] |= mask; /* 'send one byte' flag */␊ |
| 282 | code_buf[code_buf_ptr++] = sp->text_buf[r]; /* Send uncoded. */␊ |
| 283 | } else {␊ |
| 284 | /* Send position and length pair. Note match_length > THRESHOLD. */␊ |
| 285 | code_buf[code_buf_ptr++] = (u_int8_t) sp->match_position;␊ |
| 286 | code_buf[code_buf_ptr++] = (u_int8_t)␊ |
| 287 | ( ((sp->match_position >> 4) & 0xF0)␊ |
| 288 | | (sp->match_length - (THRESHOLD + 1)) );␊ |
| 289 | }␊ |
| 290 | if ((mask <<= 1) == 0) { /* Shift mask left one bit. */␊ |
| 291 | /* Send at most 8 units of code together */␊ |
| 292 | for (i = 0; i < code_buf_ptr; i++)␊ |
| 293 | if (dst < dstend)␊ |
| 294 | *dst++ = code_buf[i];␊ |
| 295 | else␊ |
| 296 | return (void *) 0;␊ |
| 297 | code_buf[0] = 0;␊ |
| 298 | code_buf_ptr = mask = 1;␊ |
| 299 | }␊ |
| 300 | last_match_length = sp->match_length;␊ |
| 301 | for (i = 0; i < last_match_length && src < srcend; i++) {␊ |
| 302 | delete_node(sp, s); /* Delete old strings and */␊ |
| 303 | c = *src++;␊ |
| 304 | sp->text_buf[s] = c; /* read new bytes */␊ |
| 305 | ␊ |
| 306 | /*␊ |
| 307 | * If the position is near the end of buffer, extend the buffer␊ |
| 308 | * to make string comparison easier.␊ |
| 309 | */␊ |
| 310 | if (s < F - 1)␊ |
| 311 | sp->text_buf[s + N] = c;␊ |
| 312 | ␊ |
| 313 | /* Since this is a ring buffer, increment the position modulo N. */␊ |
| 314 | s = (s + 1) & (N - 1);␊ |
| 315 | r = (r + 1) & (N - 1);␊ |
| 316 | ␊ |
| 317 | /* Register the string in text_buf[r..r+F-1] */␊ |
| 318 | insert_node(sp, r);␊ |
| 319 | }␊ |
| 320 | while (i++ < last_match_length) {␊ |
| 321 | delete_node(sp, s);␊ |
| 322 | ␊ |
| 323 | /* After the end of text, no need to read, */␊ |
| 324 | s = (s + 1) & (N - 1);␊ |
| 325 | r = (r + 1) & (N - 1);␊ |
| 326 | /* but buffer may not be empty. */␊ |
| 327 | if (--len)␊ |
| 328 | insert_node(sp, r);␊ |
| 329 | }␊ |
| 330 | } while (len > 0); /* until length of string to be processed is zero */␊ |
| 331 | ␊ |
| 332 | if (code_buf_ptr > 1) { /* Send remaining code. */␊ |
| 333 | for (i = 0; i < code_buf_ptr; i++)␊ |
| 334 | if (dst < dstend)␊ |
| 335 | *dst++ = code_buf[i];␊ |
| 336 | else␊ |
| 337 | return (void *) 0;␊ |
| 338 | }␊ |
| 339 | return dst;␊ |
| 340 | }␊ |
| 341 | |
