/* lz.h -- a tiny LZSS codec (public domain), used to keep the compiled scripture
 * text small enough to fit a floppy. clectio only needs lz_unpack; the build
 * tool mktext defines LZ_PACK to also get the compressor. Round-trip tested.
 *
 * Stream = repeated { control byte (8 flags, MSB first); then, per flag:
 *   flag 1 -> one literal byte
 *   flag 0 -> a match: 16-bit big-endian distance (1..65535) + 1 length byte L,
 *             copy (L + LZ_MINM) bytes from `distance` back }.
 */
#ifndef LZ_H
#define LZ_H
#include <stddef.h>

#define LZ_WIN  65536
#define LZ_MINM 3
#define LZ_MAXM 258 /* 255 + LZ_MINM */

/* Decompress `in` (inlen bytes) into `out`, stopping once rawlen bytes emitted.
 * inline so the packer-only build (mktext) does not warn it unused. */
static inline void lz_unpack(const unsigned char *in, size_t inlen,
                             unsigned char *out, size_t rawlen) {
	size_t p = 0, o = 0;
	while (o < rawlen && p < inlen) {
		unsigned char ctrl = in[p++];
		int b;
		for (b = 0; b < 8 && o < rawlen && p < inlen; b++) {
			if (ctrl & (0x80 >> b)) {
				out[o++] = in[p++];
			} else {
				unsigned dist = ((unsigned)in[p] << 8) | in[p + 1];
				unsigned len = (unsigned)in[p + 2] + LZ_MINM;
				const unsigned char *s = out + o - dist;
				p += 3;
				while (len-- && o < rawlen)
					out[o++] = *s++;
			}
		}
	}
}

#ifdef LZ_PACK
#include <stdlib.h>

static unsigned lz__hash(const unsigned char *s) {
	return (((unsigned)s[0] * 506832829u) ^ ((unsigned)s[1] * 2246822519u) ^
	        ((unsigned)s[2] * 3266489917u)) >> 15 & 0x1FFFF;
}

/* Compress src[srclen] into a malloc'd buffer (caller frees); *outlen is set. */
static unsigned char *lz_pack(const unsigned char *src, size_t srclen, size_t *outlen) {
	unsigned char *out = malloc(srclen + srclen / 8 + 64);
	int *head = malloc(0x20000 * sizeof(int));
	int *prev = malloc((srclen + 1) * sizeof(int));
	size_t o = 0, i = 0, k;
	for (k = 0; k < 0x20000; k++)
		head[k] = -1;
	while (i < srclen) {
		size_t ctrlpos = o++;
		unsigned char ctrl = 0;
		int bit;
		for (bit = 0; bit < 8 && i < srclen; bit++) {
			int bestlen = 0, bestdist = 0;
			if (i + LZ_MINM <= srclen) {
				unsigned h = lz__hash(src + i);
				int j = head[h], tries = 128;
				while (j >= 0 && (size_t)(i - (size_t)j) < LZ_WIN && tries--) {
					size_t l = 0, maxl = srclen - i;
					if (maxl > LZ_MAXM)
						maxl = LZ_MAXM;
					while (l < maxl && src[(size_t)j + l] == src[i + l])
						l++;
					if ((int)l > bestlen) {
						bestlen = (int)l;
						bestdist = (int)(i - (size_t)j);
						if (l == maxl)
							break;
					}
					j = prev[j];
				}
			}
			if (bestlen >= LZ_MINM) {
				size_t e = i + (size_t)bestlen; /* ctrl bit stays 0 for a match */
				out[o++] = (unsigned char)((bestdist >> 8) & 0xFF);
				out[o++] = (unsigned char)(bestdist & 0xFF);
				out[o++] = (unsigned char)(bestlen - LZ_MINM);
				while (i < e) {
					if (i + LZ_MINM <= srclen) {
						unsigned h = lz__hash(src + i);
						prev[i] = head[h];
						head[h] = (int)i;
					}
					i++;
				}
			} else {
				ctrl |= (unsigned char)(0x80 >> bit); /* literal */
				if (i + LZ_MINM <= srclen) {
					unsigned h = lz__hash(src + i);
					prev[i] = head[h];
					head[h] = (int)i;
				}
				out[o++] = src[i++];
			}
		}
		out[ctrlpos] = ctrl;
	}
	free(head);
	free(prev);
	*outlen = o;
	return out;
}
#endif /* LZ_PACK */
#endif /* LZ_H */