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