#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif

#include <stdio.h>
#include <string.h>
#include <platon/compress/rle.h>

/* Maximal run length support added by Nepto [2004-01-04] */
#define COMPRESS_MAX_RUN_LEN	65535 /* 2 ^ 16 - 1 */

	int
PLATON_FUNC(compress_rle)(src, dst, src_size)
	unsigned char *src;
	unsigned char *dst;
	int src_size;
{
	int
		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 */
	unsigned char
		cur_byte;                       /* Next byte to process */
	unsigned char
		*header;                        /* Header of unpacked string */
	int
		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 = 0;               /* 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 - src_scan + 1 < COMPRESS_MAX_RUN_LEN)
				run_end++;

			have_run = 1;
			if (header)                 /* If we have a previous unpacked */
			{                         /* string, close it */
				*header = (unsigned char) 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)
			{
				dst [dst_size++] = 0x00;
				dst [dst_size++] = (unsigned char) length;
			}
			else
				if (length < 256 && cur_byte == ' ')
				{
					dst [dst_size++] = 0x82;
					dst [dst_size++] = (unsigned char) length;
				}
				else
					if (length < 128)
					{
						dst [dst_size++] = (unsigned char) length | 0x80;
						dst [dst_size++] = cur_byte;
					}
					else
						if (length < 256)           /* Short run 128-255 bytes */
						{
							dst [dst_size++] = 0x80;
							dst [dst_size++] = (unsigned char) length;
							dst [dst_size++] = cur_byte;
						}
						else                        /* Long run 256-2^16 bytes */
						{
							dst [dst_size++] = 0x81;
							dst [dst_size++] = (unsigned char) (length & 0xff);
							dst [dst_size++] = (unsigned char) (length >> 8);
							dst [dst_size++] = cur_byte;
						}
		}
		else
		{
			if (!header)                /* Start new unpacked string if */
			{                         /* necessary */
				header = &dst [dst_size++];
				length = 0;
			}
			dst [dst_size++] = cur_byte;
			if (++length == 127)        /* Each string can be up to 127 */
			{                         /* bytes long (high bit cleared) */
				*header = (unsigned char) length;
				header  = NULL;
			}
		}
	}
	if (header)                         /* If we have a previous unpacked */
	{                                 /* string, close it */
		*header = (unsigned char) length;
		header  = NULL;
	}
	return (dst_size);                  /* Return compressed data size */
}

	int
PLATON_FUNC(uncompress_rle)(src, dst, src_size)
	const unsigned char *src;
	unsigned char *dst;
	int src_size;
{
	int
		dst_size,                       /* Size of expanded data */
	src_scan,                       /* Scan through source data */
	length;                         /* Size of the run or string */
	unsigned char
		cur_byte;                       /* Next byte to process */

	src_scan = 0;
	dst_size = 0;
	while (src_scan < src_size)
	{
		cur_byte = src [src_scan++];

		/* 1 to 127 is uncompressed string of 1 to 127 bytes */
		if (cur_byte > 0 && cur_byte < 128)
		{
			length = (int) cur_byte;
			memcpy(dst + dst_size, src + src_scan, length);
			src_scan += length;
			dst_size += length;
		}
		else                            /* Run of 3 or more bytes */
		{
			switch (cur_byte)
			{
				case 0x00:              /* Run of 3-255 zeroes */
					length   = src [src_scan++];
					cur_byte = 0;
					break;
				case 0x82:              /* Run of 3-255 spaces */
					length   = src [src_scan++];
					cur_byte = ' ';
					break;
				case 0x80:              /* Short run 128-255 bytes */
					length   = src [src_scan++];
					cur_byte = src [src_scan++];
					break;
				case 0x81:              /* Long run 256-2^16 bytes */
					length   = src [src_scan++];
					length  += src [src_scan++] << 8;
					cur_byte = src [src_scan++];
					break;
				default:                /* Run of 3 to 127 bytes */
					length = cur_byte & 127;
					cur_byte = src [src_scan++];
			}
			memset(dst + dst_size, cur_byte, length);
			dst_size += length;
		}
	}
	return (dst_size);                  /* Return expanded data size */
}

	int
PLATON_FUNC(compress_nulls)(src, dst, src_size)
	unsigned char *src;
	unsigned char *dst;
	int src_size;
{
	int
		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 */
	unsigned char
		cur_byte;                       /* Next byte to process */
	unsigned char
		*header;                        /* Header of unpacked string */
	int
		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 = 0;               /* Unless we find a run */

		/* Two identical bytes may signal the start of a run */
		if (cur_byte == src [src_scan]
				&&  src_scan < 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 - src_scan + 1 < COMPRESS_MAX_RUN_LEN)
				run_end++;

			/* A run is 4+ identical bytes or 2+ nulls */
			if ((run_end - src_scan > 2) || cur_byte == 0)
			{
				have_run = 1;
				if (header)             /* If we have a previous unpacked */
				{                     /* string, close it */
					*header = (unsigned char) length;
					header  = NULL;
				}
				length = run_end - src_scan + 1;
				src_scan = run_end;
			}
		}
		if (have_run)
		{
			if (cur_byte == 0)
			{
				if (length < 128)       /* 2-127 binary zeroes */
					dst [dst_size++] = (unsigned char) (length | 0x80);
				else
					if (length < 256)       /* 128-256 binary zeroes */
					{
						dst [dst_size++] = 0x81;
						dst [dst_size++] = (unsigned char) length;
					}
					else                    /* 256-2^15 binary zeroes */
					{
						dst [dst_size++] = 0x80;
						dst [dst_size++] = (unsigned char) (length & 0xff);
						dst [dst_size++] = (unsigned char) (length >> 8);
					}
			}
			else
				if (length < 256)           /* Short run 4-255 bytes */
				{
					dst [dst_size++] = 0x00;
					dst [dst_size++] = (unsigned char) length;
					dst [dst_size++] = cur_byte;
				}
				else                        /* Long run 256-2^16 bytes */
				{
					dst [dst_size++] = 0x00;
					dst [dst_size++] = 0x00;
					dst [dst_size++] = (unsigned char) (length & 0xff);
					dst [dst_size++] = (unsigned char) (length >> 8);
					dst [dst_size++] = cur_byte;
				}
		}
		else
		{
			if (!header)                /* Start new unpacked string if */
			{                         /* necessary */
				header = &dst [dst_size++];
				length = 0;
			}
			dst [dst_size++] = cur_byte;
			if (++length == 127)        /* Each string can be up to 127 */
			{                         /* bytes long (high bit cleared) */
				*header = (unsigned char) length;
				header  = NULL;
			}
		}
	}
	if (header)                         /* If we have a previous unpacked */
	{                                 /* string, close it */
		*header = (unsigned char) length;
		header  = NULL;
	}
	return (dst_size);                  /* Return compressed data size */
}

	int
PLATON_FUNC(uncompress_nulls)(src, dst, src_size)
	const unsigned char *src;
	unsigned char *dst;
	int src_size;
{
	int
		dst_size,                       /* Size of expanded data */
	src_scan,                       /* Scan through source data */
	length;                         /* Size of the run or string */
	unsigned char
		cur_byte;                       /* Next byte to process */

	src_scan = 0;
	dst_size = 0;
	while (src_scan < src_size)
	{
		cur_byte = src [src_scan++];

		/* 1 to 127 is uncompressed string of 1 to 127 bytes */
		if (cur_byte > 0 && cur_byte < 128)
		{
			length = (int) cur_byte;
			memcpy(dst + dst_size, src + src_scan, length);
			src_scan += length;
			dst_size += length;
		}
		else                            /* Run of 2 or more bytes */
		{
			switch (cur_byte)
			{
				case 0x00:              /* Run of non-zero bytes */
					length = src [src_scan++];
					if (length == 0)    /* Stored as double-byte */
					{
						length   = src [src_scan++];
						length  += src [src_scan++] << 8;
					}
					cur_byte = src [src_scan++];
					break;
				case 0x80:              /* 256-2^16 zeroes */
					length   = src [src_scan++];
					length  += src [src_scan++] << 8;
					cur_byte = 0;
					break;
				case 0x81:              /* 128 to 255 zeroes */
					length   = src [src_scan++];
					cur_byte = 0;
					break;
				default:                /* 2 to 127 zeroes */
					length   = cur_byte & 127;
					cur_byte = 0;
			}
			memset(dst + dst_size, cur_byte, length);
			dst_size += length;
		}
	}
	return (dst_size);                  /* Return expanded data size */
}

	int
PLATON_FUNC(compress_bits)(src, dst, src_size)
	unsigned char *src;
	unsigned char *dst;
	int src_size;
{
	int
		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 */
	unsigned char
		cur_byte;                       /* Next byte to process */
	unsigned char
		*header;                        /* Header of unpacked string */
	static int
		single_bits [256];              /* Bytes with one bit set */
	static int
		initialised = 0;            /* First time flag */

	/* The single_bits table provides a fast lookup for bytes with */
	/* one bit set.  The 'interesting' bytes are non-zero in the table */
	/* where their value is the output code value (0-7) + 1. */
	if (!initialised)                   /* First time?  Initialise */
	{
		memset(single_bits, 0, 256);
		single_bits [1]   = 1;
		single_bits [2]   = 2;
		single_bits [4]   = 3;
		single_bits [8]   = 4;
		single_bits [16]  = 5;
		single_bits [32]  = 6;
		single_bits [64]  = 7;
		single_bits [128] = 8;
	}

	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++];

		/* - Look for 1 or more binary zeroes, and compress into a run ------- */

		if (cur_byte == 0)
		{
			src [src_size] = 0xff;      /* Stop with a sentinel */
			run_end = src_scan;         /* src_scan <= src_size */
			while (src [run_end] == 0
					&& run_end - src_scan + 1 < COMPRESS_MAX_RUN_LEN)
				run_end++;

			if (header)                 /* If we have a previous unpacked */
			{                         /* string, close it */
				*header = (unsigned char) length + 7;
				header  = NULL;
			}
			length = run_end - src_scan + 1;
			src_scan = run_end;
			if (length < 127)           /* 1-126 binary zeroes */
				dst [dst_size++] = (unsigned char) (++length | 0x80);
			else
				if (length < 381)           /* 127-380 binary zeroes */
				{
					dst [dst_size++] = 0x81;
					dst [dst_size++] = (unsigned char) length - 127;
				}
				else                        /* 381-2^16 binary zeroes */
				{
					dst [dst_size++] = 0x80;
					dst [dst_size++] = (unsigned char) (length & 0xff);
					dst [dst_size++] = (unsigned char) (length >> 8);
				}
		}
		else

			/* - Next, look for bytes with 1 bit set; we encode these as 1 byte -- */

			if (single_bits [cur_byte])     /* Single bit value? */
			{
				dst [dst_size++] = single_bits [cur_byte] - 1;
				if (header)                 /* If we have a previous unpacked */
				{                         /* string, close it */
					*header = (unsigned char) length + 7;
					header  = NULL;
				}
			}
			else

				/* - Next, look for a run of 4 or more identical (non-zero) bytes ---- */

				if (cur_byte == src [src_scan]
						&&  cur_byte == src [src_scan + 1]
						&&  cur_byte == src [src_scan + 2]
						&& (src_scan < src_size - 2))
				{
					src [src_size] = !cur_byte; /* Stick in a sentinel byte */
					run_end = src_scan;         /* src_scan <= src_size */
					while (src [run_end] == cur_byte
							&& run_end - src_scan + 1 < COMPRESS_MAX_RUN_LEN)
						run_end++;

					if (header)                 /* If we have a previous unpacked */
					{                         /* string, close it */
						*header = (unsigned char) length + 7;
						header  = NULL;
					}
					length = run_end - src_scan + 1;
					src_scan = run_end;

					if (length < 256)           /* Short run 4-255 bytes */
					{
						dst [dst_size++] = 0x81;
						dst [dst_size++] = 0xFE;
						dst [dst_size++] = (unsigned char) length;
						dst [dst_size++] = cur_byte;
					}
					else                        /* Long run 256-2^16 bytes */
					{
						dst [dst_size++] = 0x81;
						dst [dst_size++] = 0xFF;
						dst [dst_size++] = (unsigned char) (length & 0xff);
						dst [dst_size++] = (unsigned char) (length >> 8);
						dst [dst_size++] = cur_byte;
					}
				}
				else

					/* - Lastly, compress unpackable strings into chunks of 120 bytes ---- */

				{
					if (!header)                /* Start new unpacked string if */
					{                         /* necessary */
						header = &dst [dst_size++];
						length = 0;
					}
					dst [dst_size++] = cur_byte;
					if (++length == 120)        /* Each string can be up to 120 */
					{                         /* bytes long (high bit cleared) */
						*header = (unsigned char) length + 7;
						header  = NULL;
					}
				}
	}
	if (header)                         /* If we have a previous unpacked */
	{                                 /* string, close it */
		*header = (unsigned char) length + 7;
		header  = NULL;
	}
	return (dst_size);                  /* Return compressed data size */
}

	int
PLATON_FUNC(uncompress_bits)(src, dst, src_size)
	const unsigned char *src;
	unsigned char *dst;
	int src_size;
{
	int
		dst_size,                       /* Size of expanded data */
	src_scan,                       /* Scan through source data */
	length;                         /* Size of the run or string */
	unsigned char
		cur_byte;                       /* Next byte to process */

	src_scan = 0;
	dst_size = 0;
	while (src_scan < src_size)
	{
		cur_byte = src [src_scan++];

		if (cur_byte < 8)               /* Single bit in position 0 to 7 */
			dst [dst_size++] = 1 << cur_byte;
		else
			if (cur_byte < 128)             /* String of 1 to 120 bytes */
			{
				length = (int) cur_byte - 7;
				memcpy(dst + dst_size, src + src_scan, length);
				src_scan += length;
				dst_size += length;
			}
			else                            /* Run of 1 or more bytes */
			{
				switch (cur_byte)
				{
					case 0x80:              /* 381-2^16 binary zeroes */
						length   = src [src_scan++];
						length  += src [src_scan++] << 8;
						cur_byte = 0;
						break;
					case 0x81:
						length = src [src_scan++];
						if (length == 0xFE) /* 4-255 non-zero bytes */
						{
							length   = src [src_scan++];
							cur_byte = src [src_scan++];
						}
						else
							if (length == 0xFF) /* Run of 256-2^15 non-zero bytes */
							{
								length   = src [src_scan++];
								length  += src [src_scan++] << 8;
								cur_byte = src [src_scan++];
							}
							else
							{
								length  += 127;
								cur_byte = 0;   /* 127 to 380 zeroes */
							}
						break;
					default:                /* 1 to 126 zeroes */
						length   = (cur_byte - 1) & 127;
						cur_byte = 0;
				}
				memset(dst + dst_size, cur_byte, length);
				dst_size += length;
			}
	}
	return (dst_size);                  /* Return expanded data size */
}

#if defined(SELF) || defined(SELFTEST) || defined(SELF_COMPRESS_RLE)

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#include <platon/compress/lz-rle.h>

/* Device /dev/stdin especially useful for something like this:
while :; do find /usr/ -type f -exec cat {} \;; done 2>/dev/null | ./rle
*/
#define DATA_DEVICE		"/dev/stdin"
#define APPLY_CLEAN		0
#define N_ALGORITHMS	4
#define BUFSIZE			2682079
#undef  BUFSIZE
#define BUFSIZE			2000000
#if 0
#  include <limits.h>
#  undef  BUFSIZE
#  define BUFSIZE			INT_MAX / 2
#endif

	int
main(argc, argv)
	int argc;
	char **argv;
{
	register int i, j, rcycle, phase;
	register int fd;

	int dest_size;
	float ratio;

	unsigned char *buf_tmp,
		buf_bck[BUFSIZE + 1],
	buf_start[BUFSIZE + 1],
	buf_end[BUFSIZE + BUFSIZE / 5 + 100];

	struct {
		char *name;
		int failures;
		float min_ratio;
		float max_ratio;
		int (*compress)  (      unsigned char *, unsigned char *, int);
		int (*uncompress)(const unsigned char *, unsigned char *, int);
	} algorithms[N_ALGORITHMS] = {
		{"LZ-RLE", 0, 100, -100, compress_lz_rle, uncompress_lz_rle},
		{"RLE",    0, 100, -100, compress_rle,    uncompress_rle},
		{"NULLS",  0, 100, -100, compress_nulls,  uncompress_nulls},
		{"BITS",   0, 100, -100, compress_bits,   uncompress_bits}
	};

	setbuf(stdout, NULL);

	if (strcmp("/dev/stdin", DATA_DEVICE)) {
		if ((fd = open(DATA_DEVICE, O_RDONLY)) == -1) {
			fprintf(stderr, "cannot open /dev/urandom\n");
			return 1;
		}
	} else {
		fd = 0;
	}

	for (i = 0; ; i++) {
		phase = i % N_ALGORITHMS;

		printf("[%05d] [%6s] read ", i, algorithms[phase].name);
		for (rcycle = 0, buf_tmp = buf_bck; buf_tmp < buf_bck + BUFSIZE; rcycle++) {
			if ((j = read(fd, buf_tmp, BUFSIZE - (buf_tmp - buf_bck))) <= 0) {
				fprintf(stderr, "read() failure (%d returned)\n", j);
				return 2;
			}
			buf_tmp += j;
		}

#if APPLY_CLEAN
		/* Cleaning random data a bit */
		for (j = 0; j + (int) buf_bck[j] < BUFSIZE; ) {
			int size = buf_bck[j] + 1;
			memset(buf_bck + j, 0, size);
			j += (int) size;           /* move over cleaned nulls */
			j += (int) buf_bck[j] + 1; /* some part remains uncleaned */
		}
#endif

		printf("[%4dc] copy ", rcycle);
		memcpy(buf_start, buf_bck, BUFSIZE);

		printf("[%7d] pack ", BUFSIZE);
		dest_size = algorithms[phase].compress(buf_start, buf_end, BUFSIZE);
		ratio     = (float) ((dest_size - BUFSIZE) * 100) / BUFSIZE;

		if (ratio < algorithms[phase].min_ratio)
			algorithms[phase].min_ratio = ratio;
		if (ratio > algorithms[phase].max_ratio)
			algorithms[phase].max_ratio = ratio;

		printf("[%7d] %% [%+7.2f%%] extr ", dest_size, ratio);
		dest_size = algorithms[phase].uncompress(buf_end, buf_start, dest_size);

		printf("[%7d] comp ", dest_size);

		if (dest_size != BUFSIZE || memcmp(buf_bck, buf_start, BUFSIZE)) {
			printf("[FAILURE]\n");
			algorithms[phase].failures++;
		} else {
			printf("[OK]\n");
		}

		if (i > 0 && ! (i % 100)) {
			for (j = 0; j < N_ALGORITHMS; j++) {
				printf("[STATS] [%6s] -- failures = %d -- "
						"min_ratio = %+9.4f%% -- max_ratio = %+9.4f%%\n",
						algorithms[j].name, algorithms[j].failures,
						algorithms[j].min_ratio, algorithms[j].max_ratio);
			}
		}

#if 0
		for (j = 0; j < 20; j++) {
			printf("[%X]", buf_end[j]);
		}
		putchar('\n');
#endif

	}

	return 0; /* never reached */
}

#endif /* #if defined(SELF) || defined(SELFTEST) || defined(SELF_COMPRESS_RLE) */