diff options
Diffstat (limited to 'lz.h')
| -rw-r--r-- | lz.h | 111 |
1 files changed, 111 insertions, 0 deletions
@@ -0,0 +1,111 @@ +/* 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. */ +static 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[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 */ |