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