i386/boot2/lzss.c

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