i386/boot2/lzss.c

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