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 <stdint.h> // For uintptr_t. 29#include <string.h> 30#include <libkern/mkext.h> 31 32 33#define BASE 65521L /* largest prime smaller than 65536 */ 34#define NMAX 5552 // the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 35 36#define DO1(buf,i) {s1 += buf[i]; s2 += s1;} 37#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 38#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 39#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 40#define DO16(buf) DO8(buf,0); DO8(buf,8); 41 42u_int32_t 43mkext_adler32(uint8_t *buf, int32_t len) 44{ 45 unsigned long s1 = 1; // adler & 0xffff; 46 unsigned long s2 = 0; // (adler >> 16) & 0xffff; 47 int k; 48 49 50 while (len > 0) { 51 k = len < NMAX ? len : NMAX; 52 len -= k; 53 while (k >= 16) { 54 DO16(buf); 55 buf += 16; 56 k -= 16; 57 } 58 if (k != 0) do { 59 s1 += *buf++; 60 s2 += s1; 61 } while (--k); 62 s1 %= BASE; 63 s2 %= BASE; 64 } 65 return (s2 << 16) | s1; 66} 67 68 69/************************************************************** 70 LZSS.C -- A Data Compression Program 71*************************************************************** 72 4/6/1989 Haruhiko Okumura 73 Use, distribute, and modify this program freely. 74 Please send me your improved versions. 75 PC-VAN SCIENCE 76 NIFTY-Serve PAF01022 77 CompuServe 74050,1022 78 79**************************************************************/ 80 81#define N 4096 /* size of ring buffer - must be power of 2 */ 82#define F 18 /* upper limit for match_length */ 83#define THRESHOLD 2 /* encode string into position and length 84 if match_length is greater than this */ 85#define NIL N /* index for root of binary search trees */ 86 87struct encode_state { 88 /* 89 * left & right children & parent. These constitute binary search trees. 90 */ 91 int lchild[N + 1], rchild[N + 257], parent[N + 1]; 92 93 /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ 94 u_int8_t text_buf[N + F - 1]; 95 96 /* 97 * match_length of longest match. 98 * These are set by the insert_node() procedure. 99 */ 100 int match_position, match_length; 101}; 102 103 104int 105decompress_lzss(u_int8_t *dst, u_int32_t dstlen, u_int8_t *src, u_int32_t srclen) 106{ 107 /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ 108 u_int8_t text_buf[N + F - 1]; 109 u_int8_t *dststart = dst; 110 u_int8_t *dstend = dst + dstlen; 111 u_int8_t *srcend = src + srclen; 112 int i, j, k, r, c; 113 unsigned int flags; 114 115 dst = dststart; 116 srcend = src + srclen; 117 for (i = 0; i < N - F; i++) 118 text_buf[i] = ' '; 119 r = N - F; 120 flags = 0; 121 for ( ; ; ) { 122 if (((flags >>= 1) & 0x100) == 0) { 123 if (src < srcend) c = *src++; else break; 124 flags = c | 0xFF00; /* uses higher byte cleverly */ 125 } /* to count eight */ 126 if (flags & 1) { 127 if (src < srcend) c = *src++; else break; 128 *dst++ = c; 129 if (dst >= dstend) { 130 goto finish; 131 } 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 if (dst >= dstend) { 143 goto finish; 144 } 145 text_buf[r++] = c; 146 r &= (N - 1); 147 } 148 } 149 } 150finish: 151 return dst - dststart; 152} 153 154#if !KERNEL 155 156/* 157 * initialize state, mostly the trees 158 * 159 * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left 160 * children of node i. These nodes need not be initialized. Also, parent[i] 161 * is the parent of node i. These are initialized to NIL (= N), which stands 162 * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the 163 * tree for strings that begin with character i. These are initialized to NIL. 164 * Note there are 256 trees. */ 165static void init_state(struct encode_state *sp) 166{ 167 int i; 168 169 bzero(sp, sizeof(*sp)); 170 171 for (i = 0; i < N - F; i++) 172 sp->text_buf[i] = ' '; 173 for (i = N + 1; i <= N + 256; i++) 174 sp->rchild[i] = NIL; 175 for (i = 0; i < N; i++) 176 sp->parent[i] = NIL; 177} 178 179/* 180 * Inserts string of length F, text_buf[r..r+F-1], into one of the trees 181 * (text_buf[r]'th tree) and returns the longest-match position and length 182 * via the global variables match_position and match_length. 183 * If match_length = F, then removes the old node in favor of the new one, 184 * because the old one will be deleted sooner. Note r plays double role, 185 * as tree node and position in buffer. 186 */ 187static void insert_node(struct encode_state *sp, int r) 188{ 189 int i, p, cmp; 190 u_int8_t *key; 191 192 cmp = 1; 193 key = &sp->text_buf[r]; 194 p = N + 1 + key[0]; 195 sp->rchild[r] = sp->lchild[r] = NIL; 196 sp->match_length = 0; 197 for ( ; ; ) { 198 if (cmp >= 0) { 199 if (sp->rchild[p] != NIL) 200 p = sp->rchild[p]; 201 else { 202 sp->rchild[p] = r; 203 sp->parent[r] = p; 204 return; 205 } 206 } else { 207 if (sp->lchild[p] != NIL) 208 p = sp->lchild[p]; 209 else { 210 sp->lchild[p] = r; 211 sp->parent[r] = p; 212 return; 213 } 214 } 215 for (i = 1; i < F; i++) { 216 if ((cmp = key[i] - sp->text_buf[p + i]) != 0) 217 break; 218 } 219 if (i > sp->match_length) { 220 sp->match_position = p; 221 if ((sp->match_length = i) >= F) 222 break; 223 } 224 } 225 sp->parent[r] = sp->parent[p]; 226 sp->lchild[r] = sp->lchild[p]; 227 sp->rchild[r] = sp->rchild[p]; 228 sp->parent[sp->lchild[p]] = r; 229 sp->parent[sp->rchild[p]] = r; 230 if (sp->rchild[sp->parent[p]] == p) 231 sp->rchild[sp->parent[p]] = r; 232 else 233 sp->lchild[sp->parent[p]] = r; 234 sp->parent[p] = NIL; /* remove p */ 235} 236 237/* deletes node p from tree */ 238static void delete_node(struct encode_state *sp, int p) 239{ 240 int q; 241 242 if (sp->parent[p] == NIL) 243 return; /* not in tree */ 244 if (sp->rchild[p] == NIL) 245 q = sp->lchild[p]; 246 else if (sp->lchild[p] == NIL) 247 q = sp->rchild[p]; 248 else { 249 q = sp->lchild[p]; 250 if (sp->rchild[q] != NIL) { 251 do { 252 q = sp->rchild[q]; 253 } while (sp->rchild[q] != NIL); 254 sp->rchild[sp->parent[q]] = sp->lchild[q]; 255 sp->parent[sp->lchild[q]] = sp->parent[q]; 256 sp->lchild[q] = sp->lchild[p]; 257 sp->parent[sp->lchild[p]] = q; 258 } 259 sp->rchild[q] = sp->rchild[p]; 260 sp->parent[sp->rchild[p]] = q; 261 } 262 sp->parent[q] = sp->parent[p]; 263 if (sp->rchild[sp->parent[p]] == p) 264 sp->rchild[sp->parent[p]] = q; 265 else 266 sp->lchild[sp->parent[p]] = q; 267 sp->parent[p] = NIL; 268} 269 270#endif /* !KERNEL */ 271 272