A Simple Data-Compression Technique

Listing 1 COMPRS.C

/*
 * COMPRS.C - Ross Data Compression (RDC)
 *            compress function
 *
 * Written by Ed Ross, 1/92
 *
 * compress inbuff_len bytes of inbuff into outbuff
 * using hash_len entries in hash_tbl.
 *
 * return length of outbuff, or "0 - inbuff_len"
 * if inbuff could not be compressed.                 */

#include <string.h>

typedef unsigned char uchar;    /*  8 bits, unsigned */
typedef unsigned int uint;      /* 16 bits, unsigned */

int rdc_compress(uchar *inbuff, uint inbuff_len,
              uchar *outbuff,
              uchar *hash_tbl[], uint hash_len)
{
uchar   *in_idx = inbuff;
uchar   *inbuff_end = inbuff + inbuff_len;
uchar   *anchor;
uchar   *pat_idx;
uint    cnt;
uint    gap;
uint    c;
uint    hash;
uint    *ctrl_idx = (uint *) outbuff;
uint    ctrl_bits;
uint    ctrl_cnt = 0;

uchar   *out_idx = outbuff + sizeof(uint);
uchar   *outbuff_end = outbuff + (inbuff_len - 48);

  /* skip the compression for a small buffer */

  if (inbuff_len <= 18)
  {
    memcpy(outbuff, inbuff, inbuff_len);
    return 0 - inbuff_len;
  }

  /* adjust # hash entries so hash algorithm can
     use 'and' instead of 'mod' */

  hash_len--;

  /* scan thru inbuff */

  while (in_idx < inbuff_end)
  {
    /* make room for the control bits
       and check for outbuff overflow */

    if (ctrl_cnt++ == 16)
    {
      *ctrl_idx = ctrl_bits;
      ctrl_cnt = 1;
      ctrl_idx = (uint *) out_idx;
      out_idx += 2;

      if (out_idx > outbuff_end)
      {
        memcpy(outbuff, inbuff, inbuff_len);
        return 0 - inbuff_len;
      }
    }

    /* look for rle */

    anchor = in_idx;
    c = *in_idx++;

    while (in_idx < inbuff_end
          && *in_idx == c
          && (in_idx - anchor) < 4114)
        in_idx++;

    /* store compression code if character is
       repeated more than 2 times */

    if ((cnt = in_idx - anchor) > 2)
    {
      if (cnt <= 18)         /* short rle */
      {
        *out_idx++ = cnt - 3;
        *out_idx++ = c;
      }
      else                   /* long rle */
      {
        cnt -= 19;
        *out_idx++ = 16 + (cnt & 00F);
        *out_idx++ = cnt >> 4;
        *out_idx++ = c;
      }
    ctrl_bits = (ctrl_bits << 1) | 1;

    continue;
  }

  /* look for pattern if 2 or more characters
     remain in the input buffer */

  in_idx = anchor;

  if ((inbuff_end - in_idx) > 2)
  {
    /* locate offset of possible pattern
      in sliding dictionary */

    hash = ((((in_idx[0] & 15) << 8) | in_idx[1]) ^
        ((in_idx[0] >> 4) | (in_idx[2] << 4)))
        & hash_len;

    pat_idx = hash_tbl[hash];
    hash_tbl[hash] = in_idx;

    /* compare characters if we're within 4098 bytes */

    if ((gap = in_idx - pat_idx) <= 4098)
    {
      while (in_idx < inbuff_end
            && pat_idx < anchor && *pat_idx == *in_idx
            && (in_idx - anchor) < 271)
      {
        in_idx++;
        pat_idx++;
      }

      /* store pattern if it is more than 2 characters */

      if ((cnt = in_idx - anchor) > 2)
      {
        gap -= 3;

        if (cnt <= 15)          /* short pattern */
        {
          *out_idx++ = (cnt << 4) + (gap & 0x0F);
          *out_idx++ = gap >> 4;
        }
        else                    /* long pattern */
        {
          *out_idx++ = 32 + (gap & 0x0F);
          *out_idx++ = gap >> 4;
          *out_idx++ = cnt - 16;
        }

        ctrl_bits = (ctrl bits << 1) | 1;

        continue;
      }
    }
  }

    /* can't compress this character
      so copy it to outbuff */

    *out_idx++ = c;
    in_idx = ++anchor;
    ctrl_bits <<= 1;
  }

  /* save last load of control bits */

  ctrl_bits <<= (16 - ctrl_cnt);
  *ctrl_idx = ctrl_ bits;

  /* and return size of compressed buffer */

  return out_idx - outbuff;
}
/* End of File */