sflcomp.c

短小精悍的C语言标准函数库。提供450个以上的可移植的算法和工具代码。

/*  ----------------------------------------------------------------<Prolog>-
    Name:       sflcomp.c
    Title:      Compression functions
    Package:    Standard Function Library (SFL)

    Written:    1991/05/20  iMatix SFL project team <[e-mail]>
    Revised:    1997/09/08

    Copyright:  Copyright (c) 1996-2000 iMatix Corporation
    License:    This is free software; you can redistribute it and/or modify
                it under the terms of the SFL License Agreement as provided
                in the file LICENSE.TXT.  This software is distributed in
                the hope that it will be useful, but without any warranty.
 ------------------------------------------------------------------</Prolog>-*/

#include "prelude.h"                    /*  Universal header file            */
#include "sflcomp.h"                    /*  Function prototypes              */


/*  Constants                                                                */

#define FLAG_COPY             0x80      /*  For LZ/RLE compression           */
#define FLAG_COMPRESS         0x40


/*  Local function prototypes                                                */

static byte get_match (const byte *source, word ptr, word source_size,
                       short *hash, word *size, short *pos);


/*  ---------------------------------------------------------------------[<]-
    Function: compress_block

    Synopsis: Takes up to 64Kb of uncompressed data in Source, compresses
    it using a fast LZ/RLE algorithm and places the result in Dest.  The
    compression technique is comparable to that used by Zip and such tools,
    but less agressive.  It is, however, fast enough to use in realtime.
    Returns the size of the compressed data.  To decompress the data, use
    the expand_block() function.
    ---------------------------------------------------------------------[>]-*/

word
compress_block (
    const byte *src,
    byte *dst,
    word src_size)
{
    static short
          Hash [4096];
    short SymbolAddress;
    word  Key;
    word  Size;
    byte  Bit = 0;
    word  Command = 0;
    word  src_index = 0;
    word  dst_size = 3;
    word  HeaderIndex = 1;

    dst [0] = FLAG_COMPRESS;
    for (Key = 0; Key < 4096; Key++)
        Hash [Key] = -1;

    while ((src_index < src_size) && (dst_size <= src_size))
      {
        if (Bit > 15)
          {
            dst [HeaderIndex]     = (byte) ((Command >> 8) & 0x00ff);
            dst [HeaderIndex + 1] = (byte) ( Command       & 0x00ff);
            HeaderIndex = dst_size;
            dst_size += 2;
            Bit = 0;
          }
        for (Size = 1;; Size++)
            if ((word) (src_index + Size) >= src_size
            || (src [src_index] != src [src_index + Size])
            || (Size >= 0x0fff))
                break;

        if (Size >= 16)
          {
            dst [dst_size++] = 0;
            dst [dst_size++] = (byte) (((word) (Size - 16) >> 8) & 0x00ff);
            dst [dst_size++] = (byte) ((Size - 16) & 0x00ff);
            dst [dst_size++] = src [src_index];
            src_index += Size;
            Command = (Command << 1) + 1;
          }
        else
        if (get_match (src, src_index, src_size,
                       Hash, &Size, &SymbolAddress) != 0)
          {
            Key = ((src_index - SymbolAddress) << 4) + (Size - 3);
            dst [dst_size++] = (byte) ((Key >> 8) & 0x00ff);
            dst [dst_size++] = (byte) (Key & 0x00ff);
            src_index += Size;
            Command = (Command << 1) + 1;
          }
        else
          {
            dst [dst_size++] = src [src_index++];
            Command = (Command << 1);
          }
        Bit++;
      }
    Command <<= (16 - Bit);
    dst [HeaderIndex]     = (byte) ((Command >> 8) & 0x00ff);
    dst [HeaderIndex + 1] = (byte) ( Command       & 0x00ff);

     if (dst_size > src_size)
      {
         for (dst_size = 0; dst_size < src_size; dst_size++)
             dst [dst_size + 1] = src [dst_size];
         dst [0] = FLAG_COPY;
         return (src_size + 1);
       }
     return (dst_size);
}


/*  ---------------------------------------------------------------------[<]-
    Function: expand_block

    Synopsis: Expands a block of data previously compressed using the
    compress_block() function.  The compressed block is passed in src;
    the expanded result in dst.  dst must be large enough to accomodate
    the largest possible decompressed block.  Returns the size of the
    uncompressed data.
    ---------------------------------------------------------------------[>]-*/

word
expand_block (
    const byte *src,
    byte *dst,
    word src_size)
{
    word SymbolAddress;
    word ChunkSize;
    word Counter;
    word Command = 0;
    word src_index = 1;
    word dst_size = 0;
    byte Bit = 0;

    if (src [0] == FLAG_COPY)
      {
        for (dst_size = 1; dst_size < src_size; dst_size++)
            dst [dst_size - 1] = src [dst_size];
        return (src_size - 1);
      }
    while (src_index < src_size)
      {
        if (Bit == 0)
          {
            Command  = src [src_index++] << 8;
            Command += src [src_index++];
            Bit = 16;
          }
        if (Command & 0x8000)
          {
            SymbolAddress =  (word) (src [src_index++] << 4);
            SymbolAddress += (word) (src [src_index] >> 4);
            if (SymbolAddress)
              {
                ChunkSize = (word) (src [src_index++] & 0x0f) + 3;
                SymbolAddress = dst_size - SymbolAddress;
                for (Counter = 0; Counter < ChunkSize; Counter++)
                    dst [dst_size++] = dst [SymbolAddress++];
              }
            else
              {
                ChunkSize  = (word) (src [src_index++] << 8);
                ChunkSize += (word) (src [src_index++] + 16);
                for (Counter = 0; Counter < ChunkSize; Counter++)
                    dst [dst_size++] = src [src_index];
                src_index++;
              }
          }
        else
            dst [dst_size++] = src [src_index++];

        Command <<= 1;
        Bit--;
      }
    return (dst_size);
}


/*  -------------------------------------------------------------------------
 *  get_match -- local
 *
 *  Finds a match for the bytes at the specified offset.
 */

static byte get_match (const byte *source, word ptr, word source_size,
                       short *hash, word *size, short *pos)
{
    word hash_value;

    hash_value = (word) (40543L * (long) ((((source [ptr]      << 4) ^
                                             source [ptr + 1]) << 4) ^
                                             source [ptr + 2]) >> 4) & 0xfff;
    *pos = hash [hash_value];
    hash [hash_value] = ptr;
    if ((word) ((*pos != -1) && ((ptr - *pos)) < 4096U))
      {
        for (*size = 0;; (*size)++)
            if ((*size >= 18)
            || ((word) (ptr + *size) >= source_size)
            || (source [ptr + *size] != source [*pos + *size]))
                break;

        return (byte) (*size >= 3);
      }
    return (FALSE);
}


/*  ---------------------------------------------------------------------[<]-
    Function: compress_rle

    Synopsis: Takes a block of uncompressed data in src, compresses
    it using a RLE algorithm and places the result in dst.  To decompress
    the data, use the expand_rle () function.  Returns the size of the
    compressed data.  The dst buffer should be 10% larger than the src
    buffer.  The src buffer must be at least src_size + 1 bytes long.  It
    may be modified.  The compressed data contains these strings:
    <Table>
    [01-7F][data...]     String of uncompressed data, 1 to 127 bytes.
    [83-FF][byte]        Run of 3 to 127 identical bytes.
    [80][len][byte]      Run of 128 to 255 identical bytes.
    [81][lo][hi][byte]   Run of 256 to 2^16 identical bytes.
    [82][len]            Run of 3 to 255 spaces.
    [00][len]            Run of 3 to 255 binary zeroes.
    </Table>
    ---------------------------------------------------------------------[>]-*/

word
compress_rle (
    byte *src,
    byte *dst,
    word src_size)
{
    word
        dst_size,                       /*  Size of compressed data          */
        src_scan,                       /*  Scan through source data         */
        run_end,                        /*  Points to end of run of bytes    */
        length = 0;                     /*  Size of the run or string        */
    byte
        cur_byte,                       /*  Next byte to process             */
        *header;                        /*  Header of unpacked string        */
    Bool
        have_run;                       /*  TRUE when we have a run          */

    src_scan = 0;                       /*  Start at beginning of source     */
    dst_size = 0;                       /*  No output yet                    */
    header   = NULL;                    /*  No open unpacked string          */
    while (src_scan < src_size)
      {
        cur_byte = src [src_scan++];
        have_run = FALSE;               /*  Unless we find a run             */

        /*  Three identical bytes signals the start of a run                 */
        if (cur_byte == src [src_scan]
        &&  cur_byte == src [src_scan + 1]
        && (src_scan + 1 < src_size))
          {
            /*  Stick-in a sentinel character to ensure that the run ends    */
            src [src_size] = !cur_byte;
            run_end = src_scan;         /*  src_scan <= src_size             */
            while (src [run_end] == cur_byte)
                run_end++;

            have_run = TRUE;
            if (header)                 /*  If we have a previous unpacked   */
              {                         /*    string, close it               */
                *header = (byte) length;
                header  = NULL;
              }
            length = run_end - src_scan + 1;
            src_scan = run_end;
          }
        if (have_run)
          {
            /*  We compress short runs of spaces and nulls separately        */
            if (length < 256 && cur_byte == 0)
              {