bootx.tproj/sl.subproj/lzss.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /**************************************************************
  26  LZSS.C -- A Data Compression Program
  27 ***************************************************************
  28     4/6/1989 Haruhiko Okumura
  29     Use, distribute, and modify this program freely.
  30     Please send me your improved versions.
  31         PC-VAN      SCIENCE
  32         NIFTY-Serve PAF01022
  33         CompuServe  74050,1022
  34
  35 **************************************************************/
  36 /*
  37  *  lzss.c - Package for decompressing lzss compressed objects
  38  *
  39  *  Copyright (c) 2003 Apple Computer, Inc.
  40  *
  41  *  DRI: Josh de Cesare
  42  */
  43
  44 #include <sl.h>
  45
  46 #define N         4096  /* size of ring buffer - must be power of 2 */
  47 #define F         18    /* upper limit for match_length */
  48 #define THRESHOLD 2     /* encode string into position and length
  49                            if match_length is greater than this */
  50 #define NIL       N     /* index for root of binary search trees */
  51
  52 int
  53 decompress_lzss(u_int8_t *dst, u_int8_t *src, u_int32_t srclen)
  54 {
  55     /* ring buffer of size N, with extra F-1 bytes to aid string comparison */
  56     u_int8_t text_buf[N + F - 1];
  57     u_int8_t *dststart = dst;
  58     u_int8_t *srcend = src + srclen;
  59     int  i, j, k, r, c;
  60     unsigned int flags;
  61
  62     dst = dststart;
  63     srcend = src + srclen;
  64     for (i = 0; i < N - F; i++)
  65         text_buf[i] = ' ';
  66     r = N - F;
  67     flags = 0;
  68     for ( ; ; ) {
  69         if (((flags >>= 1) & 0x100) == 0) {
  70             if (src < srcend) c = *src++; else break;
  71             flags = c | 0xFF00;  /* uses higher byte cleverly */
  72         }   /* to count eight */
  73         if (flags & 1) {
  74             if (src < srcend) c = *src++; else break;
  75             *dst++ = c;
  76             text_buf[r++] = c;
  77             r &= (N - 1);
  78         } else {
  79             if (src < srcend) i = *src++; else break;
  80             if (src < srcend) j = *src++; else break;
  81             i |= ((j & 0xF0) << 4);
  82             j  =  (j & 0x0F) + THRESHOLD;
  83             for (k = 0; k <= j; k++) {
  84                 c = text_buf[(i + k) & (N - 1)];
  85                 *dst++ = c;
  86                 text_buf[r++] = c;
  87                 r &= (N - 1);
  88             }
  89         }
  90     }
  91
  92     return dst - dststart;
  93 }