1/* 2 * Copyright (c) 2000-2004 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 <string.h> 29#if KERNEL 30#include <libsa/mkext.h> 31#include <libsa/stdlib.h> 32#else 33#include <Kernel/libsa/mkext.h> 34#include <stdlib.h> 35#endif /* KERNEL */ 36 37#define BASE 65521L /* largest prime smaller than 65536 */ 38#define NMAX 5000 39// NMAX (was 5521) the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 40 41#define DO1(buf,i) {s1 += buf[i]; s2 += s1;} 42#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 43#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 44#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 45#define DO16(buf) DO8(buf,0); DO8(buf,8); 46 47__private_extern__ u_int32_t 48adler32(uint8_t *buf, int32_t len) 49{ 50 unsigned long s1 = 1; // adler & 0xffff; 51 unsigned long s2 = 0; // (adler >> 16) & 0xffff; 52 int k; 53 54 while (len > 0) { 55 k = len < NMAX ? len : NMAX; 56 len -= k; 57 while (k >= 16) { 58 DO16(buf); 59 buf += 16; 60 k -= 16; 61 } 62 if (k != 0) do { 63 s1 += *buf++; 64 s2 += s1; 65 } while (--k); 66 s1 %= BASE; 67 s2 %= BASE; 68 } 69 return (s2 << 16) | s1; 70} 71 72 73/************************************************************** 74 LZSS.C -- A Data Compression Program 75*************************************************************** 76 4/6/1989 Haruhiko Okumura 77 Use, distribute, and modify this program freely. 78 Please send me your improved versions. 79 PC-VAN SCIENCE 80 NIFTY-Serve PAF01022 81 CompuServe 74050,1022 82 83**************************************************************/ 84 85#define N 4096 /* size of ring buffer - must be power of 2 */ 86#define F 18 /* upper limit for match_length */ 87#define THRESHOLD 2 /* encode string into position and length 88 if match_length is greater than this */ 89#define NIL N /* index for root of binary search trees */ 90 91struct encode_state { 92 /* 93 * left & right children & parent. These constitute binary search trees. 94 */ 95 int lchild[N + 1], rchild[N + 257], parent[N + 1]; 96 97 /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ 98 u_int8_t text_buf[N + F - 1]; 99 100 /* 101 * match_length of longest match. 102 * These are set by the insert_node() procedure. 103 */ 104 int match_position, match_length; 105}; 106 107 108__private_extern__ int 109decompress_lzss(u_int8_t *dst, u_int8_t *src, u_int32_t srclen) 110{ 111 /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ 112 u_int8_t text_buf[N + F - 1]; 113 u_int8_t *dststart = dst; 114 u_int8_t *srcend = src + srclen; 115 int i, j, k, r, c; 116 unsigned int flags; 117 118 dst = dststart; 119 srcend = src + srclen; 120 for (i = 0; i < N - F; i++) 121 text_buf[i] = ' '; 122 r = N - F; 123 flags = 0; 124 for ( ; ; ) { 125 if (((flags >>= 1) & 0x100) == 0) { 126 if (src < srcend) c = *src++; else break; 127 flags = c | 0xFF00; /* uses higher byte cleverly */ 128 } /* to count eight */ 129 if (flags & 1) { 130 if (src < srcend) c = *src++; else break; 131 *dst++ = c; 132 text_buf[r++] = c; 133 r &= (N - 1); 134 } else { 135 if (src < srcend) i = *src++; else break; 136 if (src < srcend) j = *src++; else break; 137 i |= ((j & 0xF0) << 4); 138 j = (j & 0x0F) + THRESHOLD; 139 for (k = 0; k <= j; k++) { 140 c = text_buf[(i + k) & (N - 1)]; 141 *dst++ = c; 142 text_buf[r++] = c; 143 r &= (N - 1); 144 } 145 } 146 } 147 148 return dst - dststart; 149} 150 151#if !KERNEL 152 153/* 154 * initialize state, mostly the trees 155 * 156 * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left 157 * children of node i. These nodes need not be initialized. Also, parent[i] 158 * is the parent of node i. These are initialized to NIL (= N), which stands 159 * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the 160 * tree for strings that begin with character i. These are initialized to NIL. 161 * Note there are 256 trees. */ 162static void init_state(struct encode_state *sp) 163{ 164 int i; 165 166 bzero(sp, sizeof(*sp)); 167 168 for (i = 0; i < N - F; i++) 169 sp->text_buf[i] = ' '; 170 for (i = N + 1; i <= N + 256; i++) 171 sp->rchild[i] = NIL; 172 for (i = 0; i < N; i++) 173 sp->parent[i] = NIL; 174} 175 176/* 177 * Inserts string of length F, text_buf[r..r+F-1], into one of the trees 178 * (text_buf[r]'th tree) and returns the longest-match position and length 179 * via the global variables match_position and match_length. 180 * If match_length = F, then removes the old node in favor of the new one, 181 * because the old one will be deleted sooner. Note r plays double role, 182 * as tree node and position in buffer. 183 */ 184static void insert_node(struct encode_state *sp, int r) 185{ 186 int i, p, cmp; 187 u_int8_t *key; 188 189 cmp = 1; 190 key = &sp->text_buf[r]; 191 p = N + 1 + key[0]; 192 sp->rchild[r] = sp->lchild[r] = NIL; 193 sp->match_length = 0; 194 for ( ; ; ) { 195 if (cmp >= 0) { 196 if (sp->rchild[p] != NIL) 197 p = sp->rchild[p]; 198 else { 199 sp->rchild[p] = r; 200 sp->parent[r] = p; 201 return; 202 } 203 } else { 204 if (sp->lchild[p] != NIL) 205 p = sp->lchild[p]; 206 else { 207 sp->lchild[p] = r; 208 sp->parent[r] = p; 209 return; 210 } 211 } 212 for (i = 1; i < F; i++) { 213 if ((cmp = key[i] - sp->text_buf[p + i]) != 0) 214 break; 215 } 216 if (i > sp->match_length) { 217 sp->match_position = p; 218 if ((sp->match_length = i) >= F) 219 break; 220 } 221 } 222 sp->parent[r] = sp->parent[p]; 223 sp->lchild[r] = sp->lchild[p]; 224 sp->rchild[r] = sp->rchild[p]; 225 sp->parent[sp->lchild[p]] = r; 226 sp->parent[sp->rchild[p]] = r; 227 if (sp->rchild[sp->parent[p]] == p) 228 sp->rchild[sp->parent[p]] = r; 229 else 230 sp->lchild[sp->parent[p]] = r; 231 sp->parent[p] = NIL; /* remove p */ 232} 233 234/* deletes node p from tree */ 235static void delete_node(struct encode_state *sp, int p) 236{ 237 int q; 238 239 if (sp->parent[p] == NIL) 240 return; /* not in tree */ 241 if (sp->rchild[p] == NIL) 242 q = sp->lchild[p]; 243 else if (sp->lchild[p] == NIL) 244 q = sp->rchild[p]; 245 else { 246 q = sp->lchild[p]; 247 if (sp->rchild[q] != NIL) { 248 do { 249 q = sp->rchild[q]; 250 } while (sp->rchild[q] != NIL); 251 sp->rchild[sp->parent[q]] = sp->lchild[q]; 252 sp->parent[sp->lchild[q]] = sp->parent[q]; 253 sp->lchild[q] = sp->lchild[p]; 254 sp->parent[sp->lchild[p]] = q; 255 } 256 sp->rchild[q] = sp->rchild[p]; 257 sp->parent[sp->rchild[p]] = q; 258 } 259 sp->parent[q] = sp->parent[p]; 260 if (sp->rchild[sp->parent[p]] == p) 261 sp->rchild[sp->parent[p]] = q; 262 else 263 sp->lchild[sp->parent[p]] = q; 264 sp->parent[p] = NIL; 265} 266 267__private_extern__ u_int8_t * 268compress_lzss(u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srcLen) 269{ 270 /* Encoding state, mostly tree but some current match stuff */ 271 struct encode_state *sp; 272 273 int i, c, len, r, s, last_match_length, code_buf_ptr; 274 u_int8_t code_buf[17], mask; 275 u_int8_t *srcend = src + srcLen; 276 u_int8_t *dstend = dst + dstlen; 277 278 /* initialize trees */ 279 sp = (struct encode_state *) malloc(sizeof(*sp)); 280 init_state(sp); 281 282 /* 283 * code_buf[1..16] saves eight units of code, and code_buf[0] works 284 * as eight flags, "1" representing that the unit is an unencoded 285 * letter (1 byte), "0" a position-and-length pair (2 bytes). 286 * Thus, eight units require at most 16 bytes of code. 287 */ 288 code_buf[0] = 0; 289 code_buf_ptr = mask = 1; 290 291 /* Clear the buffer with any character that will appear often. */ 292 s = 0; r = N - F; 293 294 /* Read F bytes into the last F bytes of the buffer */ 295 for (len = 0; len < F && src < srcend; len++) 296 sp->text_buf[r + len] = *src++; 297 if (!len) 298 return (void *) 0; /* text of size zero */ 299 300 /* 301 * Insert the F strings, each of which begins with one or more 302 * 'space' characters. Note the order in which these strings are 303 * inserted. This way, degenerate trees will be less likely to occur. 304 */ 305 for (i = 1; i <= F; i++) 306 insert_node(sp, r - i); 307 308 /* 309 * Finally, insert the whole string just read. 310 * The global variables match_length and match_position are set. 311 */ 312 insert_node(sp, r); 313 do { 314 /* match_length may be spuriously long near the end of text. */ 315 if (sp->match_length > len) 316 sp->match_length = len; 317 if (sp->match_length <= THRESHOLD) { 318 sp->match_length = 1; /* Not long enough match. Send one byte. */ 319 code_buf[0] |= mask; /* 'send one byte' flag */ 320 code_buf[code_buf_ptr++] = sp->text_buf[r]; /* Send uncoded. */ 321 } else { 322 /* Send position and length pair. Note match_length > THRESHOLD. */ 323 code_buf[code_buf_ptr++] = (u_int8_t) sp->match_position; 324 code_buf[code_buf_ptr++] = (u_int8_t) 325 ( ((sp->match_position >> 4) & 0xF0) 326 | (sp->match_length - (THRESHOLD + 1)) ); 327 } 328 if ((mask <<= 1) == 0) { /* Shift mask left one bit. */ 329 /* Send at most 8 units of code together */ 330 for (i = 0; i < code_buf_ptr; i++) 331 if (dst < dstend) 332 *dst++ = code_buf[i]; 333 else 334 return (void *) 0; 335 code_buf[0] = 0; 336 code_buf_ptr = mask = 1; 337 } 338 last_match_length = sp->match_length; 339 for (i = 0; i < last_match_length && src < srcend; i++) { 340 delete_node(sp, s); /* Delete old strings and */ 341 c = *src++; 342 sp->text_buf[s] = c; /* read new bytes */ 343 344 /* 345 * If the position is near the end of buffer, extend the buffer 346 * to make string comparison easier. 347 */ 348 if (s < F - 1) 349 sp->text_buf[s + N] = c; 350 351 /* Since this is a ring buffer, increment the position modulo N. */ 352 s = (s + 1) & (N - 1); 353 r = (r + 1) & (N - 1); 354 355 /* Register the string in text_buf[r..r+F-1] */ 356 insert_node(sp, r); 357 } 358 while (i++ < last_match_length) { 359 delete_node(sp, s); 360 361 /* After the end of text, no need to read, */ 362 s = (s + 1) & (N - 1); 363 r = (r + 1) & (N - 1); 364 /* but buffer may not be empty. */ 365 if (--len) 366 insert_node(sp, r); 367 } 368 } while (len > 0); /* until length of string to be processed is zero */ 369 370 if (code_buf_ptr > 1) { /* Send remaining code. */ 371 for (i = 0; i < code_buf_ptr; i++) 372 if (dst < dstend) 373 *dst++ = code_buf[i]; 374 else 375 return (void *) 0; 376 } 377 378 return dst; 379} 380 381#endif /* !KERNEL */ 382 383