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