diff options
| -rw-r--r-- | Makefile | 12 | ||||
| -rw-r--r-- | README.md | 11 | ||||
| -rw-r--r-- | clectio.c | 13 | ||||
| -rw-r--r-- | lz.h | 112 | ||||
| -rw-r--r-- | mktext.c | 48 | ||||
| -rw-r--r-- | puff.c | 282 | ||||
| -rw-r--r-- | puff.h | 15 | ||||
| -rw-r--r-- | text_ef.lz | bin | 178377 -> 133281 bytes | |||
| -rw-r--r-- | text_of.lz | bin | 670644 -> 503463 bytes |
9 files changed, 353 insertions, 140 deletions
@@ -3,7 +3,11 @@ CC ?= cc CFLAGS = -std=c99 -Os -Wall -Wextra -LDFLAGS = -s +# -no-pie: this is a local CLI reading static embedded data with no attack +# surface, so it does not need PIE/ASLR. Dropping it lets the linker bake the +# string-table pointers in at link time instead of emitting ~57 KB of runtime +# relocations -- a ~6% smaller binary for free. +LDFLAGS = -s -no-pie PREFIX = /usr/local # The form to build is read from config.h so there is one source of truth. @@ -19,7 +23,7 @@ all: clectio config.h: cp config.def.h config.h -mktext: mktext.c lz.h +mktext: mktext.c $(CC) $(CFLAGS) -o $@ mktext.c bin2h: bin2h.c @@ -38,8 +42,8 @@ endif text.lz.h: bin2h text_$(FORM).lz ./bin2h text_$(FORM).lz > $@ -clectio: clectio.c config.h text.lz.h gen/liturgy_$(FORM).h lz.h - $(CC) $(CFLAGS) $(LDFLAGS) -o $@ clectio.c +clectio: clectio.c puff.c puff.h config.h text.lz.h gen/liturgy_$(FORM).h + $(CC) $(CFLAGS) $(LDFLAGS) -o $@ clectio.c puff.c size: clectio @ls -l clectio | awk '{printf "clectio (%s): %d bytes = %.0f KB\n","$(FORM)",$$5,$$5/1024}' @@ -41,8 +41,9 @@ chapter/verse numbering: make CORPUS=/path/to/mybible.tsv clectio compiles in only the ~12000 verses the lectionary actually cites, so the -binary stays around 1 MiB whatever the Bible. A verse the corpus lacks prints -blank; it never fails the day. +binary stays well under 1 MiB whatever the Bible. A verse the corpus lacks prints +blank; it never fails the day. (The default build needs only a compiler; a +`CORPUS=` rebuild also needs `gzip`, which `mktext` uses to pack the text.) ## Coverage @@ -53,11 +54,11 @@ guessed. To extend it, regenerate `gen/` with lectio's `clectio-gen`. clectio.c the program: date -> table lookup -> print config.def.h compile-time configuration - lz.h a tiny LZSS codec (keeps the compiled text small) - mktext.c build tool: resolve verse keys against a corpus, pack the text + puff.c/.h DEFLATE decompressor (Mark Adler's puff, public domain) + mktext.c build tool: resolve verse keys against a corpus, gzip-pack the text bin2h.c build tool: embed the packed text as C gen/ generated, corpus-independent data (calendar + citations) - text_of.lz the default Vulgate text, packed (one per form) + text_of.lz the default Vulgate text, DEFLATE-packed (one per form) ## Licence @@ -12,8 +12,8 @@ #include "config.h" #include LITURGY /* gen/liturgy_<form>.h: names,parts,cites_*,vpool,readings,rpool,days,cal,EPOCH,NDAYS */ -#include "text.lz.h" /* embedded LZSS text blob: text_lz[], text_lz_len */ -#include "lz.h" +#include "text.lz.h" /* embedded DEFLATE text blob: text_lz[], text_lz_len */ +#include "puff.h" #include <stdio.h> #include <stdlib.h> @@ -39,12 +39,13 @@ static long days_from_civil(long y, unsigned m, unsigned d) { } static void load_text(void) { - unsigned raw = text_lz[0] | text_lz[1] << 8 | text_lz[2] << 16 | (unsigned)text_lz[3] << 24; + unsigned long rawlen = text_lz[0] | text_lz[1] << 8 | text_lz[2] << 16 | (unsigned long)text_lz[3] << 24; + unsigned long dstlen = rawlen, srclen = text_lz_len - 4; size_t cap = 8192, n = 0; char *p; - textbuf = malloc(raw + 1); - lz_unpack(text_lz + 4, text_lz_len - 4, (unsigned char *)textbuf, raw); - textbuf[raw] = 0; + textbuf = malloc(rawlen + 1); + puff((unsigned char *)textbuf, &dstlen, text_lz + 4, &srclen); + textbuf[dstlen] = 0; verse = malloc(cap * sizeof(*verse)); verse[n++] = textbuf; for (p = textbuf; *p; p++) @@ -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 */ @@ -8,8 +8,6 @@ * usage: mktext verses.keys corpus.tsv out.lz * out.lz = [uint32 LE rawlen][LZSS-packed "chap:verse text\n" lines]. */ -#define LZ_PACK -#include "lz.h" #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -121,17 +119,41 @@ int main(int argc, char **argv) { if (missing) fprintf(stderr, "mktext: warning: %zu of %zu verses not in corpus (blank)\n", missing, nkeys); - size_t plen; - unsigned char *packed = lz_pack((unsigned char *)out, olen, &plen); + /* Pack: gzip the raw text, then strip the gzip container to the bare DEFLATE + * stream (10-byte header + 8-byte trailer) that clectio's puff() decodes. + * out.lz = [uint32 LE raw length][raw DEFLATE]. */ + { + char rawpath[4096], gzpath[4200], cmd[4300]; + FILE *rf, *of; + char *gz; + size_t gzn, deflen; + unsigned char hdr[4]; - FILE *of = fopen(argv[3], "wb"); - if (!of) { fprintf(stderr, "mktext: cannot write %s\n", argv[3]); return 1; } - unsigned char hdr[4] = { (unsigned char)olen, (unsigned char)(olen >> 8), - (unsigned char)(olen >> 16), (unsigned char)(olen >> 24) }; - fwrite(hdr, 1, 4, of); - fwrite(packed, 1, plen, of); - fclose(of); - fprintf(stderr, "mktext: %zu verses, %zu -> %zu bytes (%.1fx)\n", - nkeys, olen, plen, olen ? (double)olen / (double)plen : 0); + snprintf(rawpath, sizeof rawpath, "%s.raw", argv[3]); + rf = fopen(rawpath, "wb"); + if (!rf) { fprintf(stderr, "mktext: cannot write %s\n", rawpath); return 1; } + fwrite(out, 1, olen, rf); + fclose(rf); + + snprintf(cmd, sizeof cmd, "gzip -9nf '%s'", rawpath); + if (system(cmd) != 0) { fprintf(stderr, "mktext: gzip failed (is gzip installed?)\n"); return 1; } + snprintf(gzpath, sizeof gzpath, "%s.gz", rawpath); + gz = slurp(gzpath, &gzn); + remove(gzpath); + if (gzn < 18) { fprintf(stderr, "mktext: unexpected gzip output\n"); return 1; } + deflen = gzn - 18; /* drop 10-byte gzip header + 8-byte trailer */ + + of = fopen(argv[3], "wb"); + if (!of) { fprintf(stderr, "mktext: cannot write %s\n", argv[3]); return 1; } + hdr[0] = (unsigned char)olen; + hdr[1] = (unsigned char)(olen >> 8); + hdr[2] = (unsigned char)(olen >> 16); + hdr[3] = (unsigned char)(olen >> 24); + fwrite(hdr, 1, 4, of); + fwrite(gz + 10, 1, deflen, of); + fclose(of); + fprintf(stderr, "mktext: %zu verses, %zu -> %zu bytes (%.1fx)\n", + nkeys, olen, deflen + 4, olen ? (double)olen / (double)(deflen + 4) : 0); + } return 0; } @@ -0,0 +1,282 @@ +/* puff.c -- a simple inflate (DEFLATE decompressor). Public domain, + * by Mark Adler (zlib/contrib/puff), trimmed to the decode path clectio needs. + */ +#include "puff.h" +#include <setjmp.h> + +#define MAXBITS 15 /* maximum bits in a code */ +#define MAXLCODES 286 /* maximum number of literal/length codes */ +#define MAXDCODES 30 /* maximum number of distance codes */ +#define MAXCODES (MAXLCODES + MAXDCODES) +#define FIXLCODES 288 /* number of fixed literal/length codes */ +#define NIL ((unsigned char *)0) + +struct state { + unsigned char *out; /* output buffer */ + unsigned long outlen; /* available space at out */ + unsigned long outcnt; /* bytes written to out so far */ + const unsigned char *in; /* input buffer */ + unsigned long inlen; /* available input at in */ + unsigned long incnt; /* bytes read so far */ + int bitbuf; /* bit buffer */ + int bitcnt; /* number of bits in bit buffer */ + jmp_buf env; /* for premature-EOF longjmp */ +}; + +static int bits(struct state *s, int need) { + long val = s->bitbuf; + while (s->bitcnt < need) { + if (s->incnt == s->inlen) + longjmp(s->env, 1); + val |= (long)(s->in[s->incnt++]) << s->bitcnt; + s->bitcnt += 8; + } + s->bitbuf = (int)(val >> need); + s->bitcnt -= need; + return (int)(val & ((1L << need) - 1)); +} + +static int stored(struct state *s) { + unsigned len; + s->bitbuf = 0; + s->bitcnt = 0; + if (s->incnt + 4 > s->inlen) + return 2; + len = s->in[s->incnt++]; + len |= s->in[s->incnt++] << 8; + if (s->in[s->incnt++] != (~len & 0xff) || + s->in[s->incnt++] != ((~len >> 8) & 0xff)) + return -2; + if (s->incnt + len > s->inlen) + return 2; + if (s->out != NIL) { + if (s->outcnt + len > s->outlen) + return 1; + while (len--) + s->out[s->outcnt++] = s->in[s->incnt++]; + } else { + s->outcnt += len; + s->incnt += len; + } + return 0; +} + +struct huffman { + short *count; /* number of symbols of each length */ + short *symbol; /* canonically ordered symbols */ +}; + +static int decode(struct state *s, const struct huffman *h) { + int len, code = 0, first = 0, count, index = 0; + for (len = 1; len <= MAXBITS; len++) { + code |= bits(s, 1); + count = h->count[len]; + if (code - count < first) + return h->symbol[index + (code - first)]; + index += count; + first += count; + first <<= 1; + code <<= 1; + } + return -10; +} + +static int construct(struct huffman *h, const short *length, int n) { + int symbol, len, left; + short offs[MAXBITS + 1]; + for (len = 0; len <= MAXBITS; len++) + h->count[len] = 0; + for (symbol = 0; symbol < n; symbol++) + (h->count[length[symbol]])++; + if (h->count[0] == n) + return 0; + left = 1; + for (len = 1; len <= MAXBITS; len++) { + left <<= 1; + left -= h->count[len]; + if (left < 0) + return left; + } + offs[1] = 0; + for (len = 1; len < MAXBITS; len++) + offs[len + 1] = offs[len] + h->count[len]; + for (symbol = 0; symbol < n; symbol++) + if (length[symbol] != 0) + h->symbol[offs[length[symbol]]++] = (short)symbol; + return left; +} + +static int codes(struct state *s, const struct huffman *lencode, + const struct huffman *distcode) { + int symbol, len; + unsigned dist; + static const short lens[29] = { + 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, + 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258}; + static const short lext[29] = { + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, + 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; + static const short dists[30] = { + 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, + 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, + 8193, 12289, 16385, 24577}; + static const short dext[30] = { + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, + 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13}; + do { + symbol = decode(s, lencode); + if (symbol < 0) + return symbol; + if (symbol < 256) { + if (s->out != NIL) { + if (s->outcnt == s->outlen) + return 1; + s->out[s->outcnt] = (unsigned char)symbol; + } + s->outcnt++; + } else if (symbol > 256) { + symbol -= 257; + if (symbol >= 29) + return -10; + len = lens[symbol] + bits(s, lext[symbol]); + symbol = decode(s, distcode); + if (symbol < 0) + return symbol; + dist = (unsigned)dists[symbol] + (unsigned)bits(s, dext[symbol]); + if (dist > s->outcnt) + return -11; + if (s->out != NIL) { + if (s->outcnt + len > s->outlen) + return 1; + while (len--) { + s->out[s->outcnt] = s->out[s->outcnt - dist]; + s->outcnt++; + } + } else + s->outcnt += len; + } + } while (symbol != 256); + return 0; +} + +static int fixed(struct state *s) { + static int virgin = 1; + static short lencnt[MAXBITS + 1], lensym[FIXLCODES]; + static short distcnt[MAXBITS + 1], distsym[MAXDCODES]; + static struct huffman lencode, distcode; + if (virgin) { + int symbol; + short lengths[FIXLCODES]; + lencode.count = lencnt; + lencode.symbol = lensym; + distcode.count = distcnt; + distcode.symbol = distsym; + for (symbol = 0; symbol < 144; symbol++) + lengths[symbol] = 8; + for (; symbol < 256; symbol++) + lengths[symbol] = 9; + for (; symbol < 280; symbol++) + lengths[symbol] = 7; + for (; symbol < FIXLCODES; symbol++) + lengths[symbol] = 8; + construct(&lencode, lengths, FIXLCODES); + for (symbol = 0; symbol < MAXDCODES; symbol++) + lengths[symbol] = 5; + construct(&distcode, lengths, MAXDCODES); + virgin = 0; + } + return codes(s, &lencode, &distcode); +} + +static int dynamic(struct state *s) { + int nlen, ndist, ncode, index, err; + short lengths[MAXCODES]; + short lencnt[MAXBITS + 1], lensym[MAXLCODES]; + short distcnt[MAXBITS + 1], distsym[MAXDCODES]; + struct huffman lencode, distcode; + static const short order[19] = { + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; + lencode.count = lencnt; + lencode.symbol = lensym; + distcode.count = distcnt; + distcode.symbol = distsym; + nlen = bits(s, 5) + 257; + ndist = bits(s, 5) + 1; + ncode = bits(s, 4) + 4; + if (nlen > MAXLCODES || ndist > MAXDCODES) + return -3; + for (index = 0; index < ncode; index++) + lengths[order[index]] = (short)bits(s, 3); + for (; index < 19; index++) + lengths[order[index]] = 0; + err = construct(&lencode, lengths, 19); + if (err != 0) + return -4; + index = 0; + while (index < nlen + ndist) { + int symbol, len; + symbol = decode(s, &lencode); + if (symbol < 0) + return symbol; + if (symbol < 16) + lengths[index++] = (short)symbol; + else { + len = 0; + if (symbol == 16) { + if (index == 0) + return -5; + len = lengths[index - 1]; + symbol = 3 + bits(s, 2); + } else if (symbol == 17) + symbol = 3 + bits(s, 3); + else + symbol = 11 + bits(s, 7); + if (index + symbol > nlen + ndist) + return -6; + while (symbol--) + lengths[index++] = (short)len; + } + } + if (lengths[256] == 0) + return -9; + err = construct(&lencode, lengths, nlen); + if (err && (err < 0 || nlen != lencode.count[0] + lencode.count[1])) + return -7; + err = construct(&distcode, lengths + nlen, ndist); + if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1])) + return -8; + return codes(s, &lencode, &distcode); +} + +int puff(unsigned char *dest, unsigned long *destlen, + const unsigned char *source, unsigned long *sourcelen) { + struct state s; + int last, type, err; + s.out = dest; + s.outlen = *destlen; + s.outcnt = 0; + s.in = source; + s.inlen = *sourcelen; + s.incnt = 0; + s.bitbuf = 0; + s.bitcnt = 0; + if (setjmp(s.env) != 0) + err = 2; + else { + do { + last = bits(&s, 1); + type = bits(&s, 2); + err = type == 0 ? stored(&s) + : type == 1 ? fixed(&s) + : type == 2 ? dynamic(&s) + : -1; + if (err != 0) + break; + } while (!last); + } + if (err <= 0) { + *destlen = s.outcnt; + *sourcelen = s.incnt; + } + return err; +} @@ -0,0 +1,15 @@ +/* puff.h -- interface to puff(), a simple DEFLATE decompressor. + * puff.c is Mark Adler's public-domain reference inflate (from zlib/contrib). + * clectio uses it to unpack its compiled scripture text, which the build packs + * with gzip (a raw DEFLATE stream; the gzip header/trailer are stripped by + * mktext, which stores [uint32 raw length][raw DEFLATE]). + */ +#ifndef PUFF_H +#define PUFF_H + +int puff(unsigned char *dest, /* pointer to destination pointer */ + unsigned long *destlen, /* amount of output space / used */ + const unsigned char *source, /* pointer to source data pointer */ + unsigned long *sourcelen); /* amount of input available / used */ + +#endif Binary files differBinary files differ |