/* Algorithm (c) Ed Ross. See RDCN.doc (bottom) for more info. */
/* Amiga implementation by Niklas Sjöberg (both C and .asm)
   reachable on 2:203/415.3@Fidonet

   After this comment, source is identical to that one in CUJ Oct 92.
*/

/* compress inbuff_len bytes of inbuff into outbuff
 * using hash_len entries in hash_tbl
 *
 * return length of outbuff, or 0 - inbufflen if inbuff could not
 * be compressed
 *
*/

#include <string.h>

typedef unsigned char uchar;
typedef unsigned short int uint;

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, *pat_idx;

  uint cnt, gap, c, hash;
  uint *ctrl_idx = (uint *) outbuff;
  uint ctrl_bits = 0;
  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 through inbuff */

  while (in_idx < inbuff_end)
    {
      /* Make room for the controlbits and check for outbuff oveflow */

      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 compressions 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 & 0x0F);
	      *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 the offste of possible pattern i 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's 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
		    {
		      *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;
}