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