1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/* 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 */
|
