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