lzrw1-a.c

一个基于lZW压缩算法的高效实现

/*Header Note
-----------
WARNING: In November 1993, someone found a bug in lzrw1-a.68000
which arises if the last item in a compressed data is a copy item of lengh
17 or 18. I haven't checked the code below, but the bug could be in here too.
I'm not sure. So please check for this before using this code.
If yopu don't want to bother with it, just use LZRW1.c.
-Ross.


THE LZRW1-A ALGORITHM IN C
==========================
Author : Ross N. Williams.
Date   : 25-Jun-1991.

1. This is my implementation in  C of my LZRW1-A algorithm. LZRW1-A
is a direct descendant of LZRW1 and was derived by:
   a. Increasing the copy length range from 3..16 to 3..18.
   b. Performing extensive optmizations.

2. This file has been copied into a test harness and works.

3. This code is public domain.  The algorithm is not patented and is a
member  of the  LZ77 class  of algorithms  which seem  to be  clear of
patent challenges.

4. Warning:  This code  is non-deterministic insofar  as it  may yield
different  compressed representations  of the  same file  on different
runs. (However, it will always decompress correctly to the original).

5. If you use this code in anger (e.g. in a product) drop me a note at
[e-mail] and I will put you  on a mailing list which will be
invoked if anyone finds a bug in this code.

6.   The  internet   newsgroup  comp.compression   might  also   carry
information on this algorithm from time to time.

7. This  code makes use  of a 68000  memory block copy  routine called
fast_copy   which   is   available   in   a   separate   file   called
fast_copy.68000. The first argument is  the source address, the second
the  destination address  and  the third,  the  length  in bytes.  See
fast_copy.68000 for an exact formal definition of the semantics of the
fast_copy procedure.

8. Header files can be found in lzrw_headers.h.*/

/******************************************************************************/
/*                                                                            */
/*                                  LZRW1-A.C                                 */
/*                                                                            */
/******************************************************************************/
/*                                                                            */
/* Author  : Ross Williams.                                                   */
/* Date    : 25 June 1991.                                                    */
/* Release : 1.                                                               */
/*                                                                            */
/******************************************************************************/
/*                                                                            */
/* This file contains an implementation of the LZRW1-A data compression       */
/* algorithm in C.                                                            */
/*                                                                            */
/* The algorithm is a general purpose compression algorithm that runs fast    */
/* and gives reasonable compression. The algorithm is a member of the Lempel  */
/* Ziv family of algorithms and bases its compression on the presence in the  */
/* data of repeated substrings.                                               */
/*                                                                            */
/* The algorithm/code is based on the LZRW1 algorithm/code. Changes are:      */
/*    1) The copy length range is now 3..18 instead of 3..16 as in LZRW1.     */
/*    2) The code for both the compressor and decompressor has been optimized */
/*       and made a little more portable.                                     */
/*                                                                            */
/* This algorithm and code is public domain. As the algorithm is based on the */
/* LZ77 class of algorithms, it is unlikely to be the subject of a patent     */
/* challenge.                                                                 */
/*                                                                            */
/* WARNING: This algorithm is non-deterministic. Its compression performance  */
/* may vary slightly from run to run.                                         */
/*                                                                            */
/******************************************************************************/

                            /* INCLUDE FILES                                  */
                            /* =============                                  */
#include "lzrw.h"           /* Defines symbols for the non portable stuff.    */
                            /* Defines single exported function "compress".   */
//#include "fast_copy.h"      /* Fast memory copy routine.                      */

/******************************************************************************/

/* The following structure is returned by the "compress" function below when  */
/* the user asks the function to return identifying information.              */
/* The most important field in the record is the working memory field which   */
/* tells the calling program how much working memory should be passed to      */
/* "compress" when it is called to perform a compression or decompression.    */
/* For more information on this structure see "compress.h".                   */

#define U(X) ((ULONG) X)

static struct compress_identity identity =
{
 U(0x4B3E387B),                           /* Algorithm identification number. */
 U(U(4)*U(4096)+U(3)),                    /* Working memory (bytes) to alg.   */
 "LZRW1-A",                               /* Name of algorithm.               */
 "1.0",                                   /* Version number of algorithm.     */
 "22-Jun-1991",                           /* Date of algorithm.               */
 "Public Domain",                         /* Copyright notice.                */
 "Ross N. Williams",                      /* Author of algorithm.             */
 "Renaissance Software",                  /* Affiliation of author.           */
 "Public Domain"                          /* Vendor of algorithm.             */
};

void compress_compress  (UBYTE *,UBYTE *,ULONG,UBYTE *,ULONG *);
void compress_decompress(UBYTE *,UBYTE *,ULONG,UBYTE *,ULONG *);

/******************************************************************************/

/* This function is the only function exported by this module.                */
/* Depending on its first parameter, the function can be requested to         */
/* compress a block of memory, decompress a block of memory, or to identify   */
/* itself. For more information, see the specification file "compress.h".     */

EXPORT void compress(action,wrk_mem,src_adr,src_len,dst_adr,p_dst_len)
UWORD     action;      /* Action to be performed.                             */
UBYTE   *wrk_mem;      /* Address of working memory we can use.               */
UBYTE   *src_adr;      /* Address of input data.                              */
ULONG    src_len;      /* Length  of input data.                              */
UBYTE   *dst_adr;      /* Address to put output data.                         */
ULONG *p_dst_len;      /* Address of longword for length of output data.      */
{
 switch (action)
   {
    case COMPRESS_ACTION_IDENTITY:
       *p_dst_len=(ULONG) &identity;
       break;
    case COMPRESS_ACTION_COMPRESS:
       compress_compress(wrk_mem,src_adr,src_len,dst_adr,p_dst_len);
       break;
    case COMPRESS_ACTION_DECOMPRESS:
       compress_decompress(wrk_mem,src_adr,src_len,dst_adr,p_dst_len);
       break;
   }
}

/******************************************************************************/
/*                                                                            */
/* The remainder of this file contains some definitions and two more          */
/* functions, one for compression and one for decompression. This section     */
/* contains information and definitions common to both algorithms.            */
/* Most of this information relates to the compression format which is common */
/* to both routines.                                                          */
/*                                                                            */
/******************************************************************************/
/*                                                                            */
/*                     DEFINITION OF COMPRESSED FILE FORMAT                   */