/* SPDX-License-Identifier: MIT
* In-place HTML character-reference decoder in two Wasm pages.
* Entity mappings: WHATWG HTML named character references, from Python
* html.entities.html5. The table lives in a passive data segment, outside
* linear memory; each lookup copies one first-letter bucket into scratch.
*
* render() moves the input to the end of the buffer and decodes forward from
* the start, so output never overtakes unread input unless it has grown by
* more than the free space in front of the input. In that case render returns
* the failure bit rather than overwrite input.
*/
#include
/* Canonical Huffman tables generated by gen4.py: counts per code length, then
* symbols; PAIR holds the byte-pair merges (symbol 128+i -> PAIR[2i], PAIR[2i+1]). */
#define P_CNT 0
#define P_SYM 10
#define C_CNT 28
#define C_SYM 40
#define K_CNT 224
#define K_SYM 230
#define S_CNT 248
#define S_SYM 251
#define PAIR 255
static const unsigned char huff[] = {0,2,2,1,4,2,3,1,1,2,1,2,3,4,5,0,6,7,8,9,11,10,12,13,14,15,16,17,0,1,0,0,2,15,21,32,71,14,20,8,0,101,116,1,2,99,100,104,105,107,108,109,110,111,112,114,115,117,97,98,102,103,113,118,119,121,128,130,132,136,140,141,145,147,150,157,158,159,163,68,69,72,83,129,133,135,137,144,151,152,153,156,160,162,165,166,168,175,178,179,182,184,185,187,188,189,191,192,195,196,198,65,66,67,70,76,80,82,84,85,106,120,122,134,138,139,142,149,161,164,173,174,176,177,180,181,186,193,199,202,203,204,205,208,209,210,213,214,215,216,217,218,219,220,221,223,225,226,227,228,230,231,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,251,252,253,254,51,52,53,73,74,79,86,148,155,170,172,194,197,200,49,50,56,71,77,78,81,131,143,154,167,171,183,201,206,207,211,212,222,229,54,55,87,89,90,169,224,232,0,0,1,12,3,2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,18,1,1,2,0,1,2,3,97,114,114,111,97,108,129,119,111,110,97,99,111,116,105,108,108,101,113,117,105,103,110,116,101,114,99,121,105,109,115,99,112,102,143,114,65,114,100,134,104,116,105,114,102,114,111,114,110,103,101,115,69,137,138,148,128,131,101,113,154,130,128,114,101,100,117,115,114,105,97,112,101,116,146,131,114,101,102,116,111,144,116,101,99,116,100,101,117,169,118,101,149,99,117,98,111,119,135,171,105,110,133,172,108,97,115,104,66,128,101,170,115,142,117,109,114,155,104,128,105,139,108,161,86,183,190,151,117,112,176,110,97,116,115,164,116,97,133,101,112,128,99,174,114,97,99,128,160,135,136,167,146,114,105,115,101,101,97,152,201,132,114,114,84,177,82,155,112,129,108,108,101,139,180,139,97,181,116,162,200,173,117,114,111,108,105,99,101,167,84,206,194,140,207,136,186,156,98,128,108,138,133,114,142,153,211,165,166,224,83,112,233,197,98,114,212,120,68,134,101,103,76,222,71,232,109,105,110,69,109,229,103,132,108,111,116,111,115,115,128,101,109,97,76,153,250,115,99,99,142,101,100,193};
static const uint32_t second_cp[8] = {106,817,819,824,8202,8402,8421,65024};
#define SCRATCH 586
#define EXPORT __attribute__((visibility("default")))
#define PAGES 2
#define STACK 256
#define BUF (PAGES * 65536 - STACK - SCRATCH - 1024)
static unsigned char scratch[SCRATCH];
static unsigned char buf[BUF];
static const uint16_t cp1252[32] = {
0x20AC, 0x81, 0x201A, 0x0192, 0x201E, 0x2026, 0x2020, 0x2021,
0x02C6, 0x2030, 0x0160, 0x2039, 0x0152, 0x8D, 0x017D, 0x8F,
0x90, 0x2018, 0x2019, 0x201C, 0x201D, 0x2022, 0x2013, 0x2014,
0x02DC, 0x2122, 0x0161, 0x203A, 0x0153, 0x9D, 0x017E, 0x0178};
/* Placeholder: the build replaces this body with memory.init from the table. */
__attribute__((noinline)) EXPORT void tbl(void *dst, uint32_t off, uint32_t n) {
__builtin_memcpy(dst, (const void *)off, n);
}
EXPORT uint32_t input_ptr(void) { return (uint32_t)buf; }
EXPORT uint32_t input_utf8_cap(void) { return BUF; }
EXPORT uint32_t output_utf8_cap(void) { return BUF; }
static unsigned utf8_len(uint32_t c) { return c < 0x80 ? 1 : c < 0x800 ? 2 : c < 0x10000 ? 3 : 4; }
static unsigned char *put(unsigned char *w, uint32_t c) {
if (c < 0x80) { *w++ = c; return w; }
if (c < 0x800) { *w++ = 0xC0 | c >> 6; }
else {
if (c < 0x10000) { *w++ = 0xE0 | c >> 12; }
else { *w++ = 0xF0 | c >> 18; *w++ = 0x80 | (c >> 12 & 63); }
*w++ = 0x80 | (c >> 6 & 63);
}
*w++ = 0x80 | (c & 63);
return w;
}
static const unsigned char *bits_p;
static uint32_t bits_pos;
static uint32_t bits(unsigned n) {
uint32_t v = 0;
for (unsigned i = 0; i < n; i++, bits_pos++)
v |= (uint32_t)(bits_p[bits_pos >> 3] >> (bits_pos & 7) & 1) << i;
return v;
}
/* Canonical Huffman decode (as in zlib's puff): counts per length, then symbols. */
static unsigned dec(unsigned cnt, unsigned sym) {
int code = 0, first = 0, index = 0;
const unsigned char *c = huff + cnt;
for (;;) {
code |= bits(1);
int count = *c++;
if (code - count < first) return huff[sym + index + code - first];
index += count; first += count; first <<= 1; code <<= 1;
}
}
static uint32_t hist[4];
/* Appends symbol t to name, expanding byte-pair merges (t >= 128). */
static unsigned emit(unsigned char *name, unsigned len, unsigned t) {
if (t < 128) { name[len] = t; return len + 1; }
const unsigned char *p = huff + PAIR + 2 * (t - 128);
return emit(name, emit(name, len, p[0]), p[1]);
}
/* Matches name s[0..n). Returns bytes consumed after '&': n + 1 for an exact
* match followed by ';', else the length of the longest legacy prefix, else 0. */
static unsigned lookup(const unsigned char *s, unsigned n, int semi, uint32_t *c1, uint32_t *c2) {
unsigned b = (s[0] | 32) - 'a';
if (b > 25) return 0;
b += s[0] & 32 ? 26 : 0;
uint16_t ix[2];
tbl(ix, b * 2, 4);
tbl(scratch, ix[0], ix[1] - ix[0]);
bits_p = scratch; bits_pos = 0;
unsigned char name[32];
unsigned best = 0, nv = 0;
for (int i = 0; i < 4; i++) hist[i] = 0;
for (;;) {
unsigned len = dec(P_CNT, P_SYM), t;
if (!len) break;
while ((t = dec(C_CNT, C_SYM)) > 3) len = emit(name, len, t);
/* Values are deltas from a prediction: Xfr/Xopf/Xscr map onto the
* Mathematical Alphanumeric Symbols block; other names pick one of the
* last four values in the bucket. */
uint32_t tail, pred;
__builtin_memcpy(&tail, name + 1, 4);
uint32_t rule = len == 3 && (uint16_t)tail == ('f' | 'r' << 8) ? 0x1D504
: len == 4 && (tail & 0xFFFFFF) == ('o' | 'p' << 8 | 'f' << 16) ? 0x1D538
: len == 4 && (tail & 0xFFFFFF) == ('s' | 'c' << 8 | 'r' << 16) ? 0x1D49C : 0;
pred = rule ? rule + b : hist[(nv - 1 - dec(S_CNT, S_SYM)) & 3];
unsigned k = dec(K_CNT, K_SYM);
uint32_t z = k ? 1u << (k - 1) | bits(k - 1) : 0;
uint32_t v = pred + ((z >> 1) ^ -(z & 1));
if (!rule) hist[nv++ & 3] = v;
uint32_t v2 = t & 2 ? second_cp[bits(3)] : 0;
/* Names are sorted, so once one sorts after s[0..n), none later can match. */
unsigned i = 1, lim = len < n ? len : n;
while (i < lim && name[i] == s[i]) i++;
if (i < lim) { if (name[i] > s[i]) break; continue; }
if (len > n) break;
if (semi && len == n) best = n + 1;
else if (!(t & 1) || len <= best) continue;
else best = len;
*c1 = v; *c2 = v2;
if (best > n) break;
}
return best;
}
static int stop(unsigned char c) {
return c == '\t' || c == '\n' || c == '\f' || c == ' ' || c == '<' || c == '&' || c == '#' || c == ';';
}
EXPORT uint64_t render(uint32_t len) {
unsigned char *end = buf + BUF, *r = end - len, *w = buf;
__builtin_memmove(r, buf, len);
while (r < end) {
unsigned char c = *r;
if (c != '&') { *w++ = c; r++; continue; }
unsigned char *p = r + 1, *after;
uint32_t c1, c2 = 0;
if (p < end && *p == '#') {
p++;
unsigned hex = p < end && (*p | 32) == 'x';
p += hex;
unsigned char *digits = p;
uint32_t num = 0;
while (p < end) {
unsigned d = *p - '0';
if (d > 9) {
if (!hex) break;
d = (*p | 32) - 'a';
if (d > 5) break;
d += 10;
}
num = num * (hex ? 16 : 10) + d;
if (num > 0x10FFFF) num = 0x110000;
p++;
}
if (p == digits) { *w++ = c; r++; continue; }
if (p < end && *p == ';') p++;
if (num == 0 || (num >= 0xD800 && num <= 0xDFFF) || num > 0x10FFFF) num = 0xFFFD;
else if (num >= 0x80 && num <= 0x9F) num = cp1252[num - 0x80];
c1 = num;
after = p;
} else {
unsigned n = 0;
while (p + n < end && n < 32 && !stop(p[n])) n++;
unsigned m = n ? lookup(p, n, p + n < end && p[n] == ';', &c1, &c2) : 0;
if (!m) { *w++ = c; r++; continue; }
after = p + m;
}
if (w + utf8_len(c1) + (c2 ? utf8_len(c2) : 0) > after) return 1ULL << 63;
w = put(w, c1);
if (c2) w = put(w, c2);
r = after;
}
return (uint64_t)(uint32_t)buf << 32 | (uint32_t)(w - buf);
}
/* ---------------------------------------------------------------------------
* Build (zig cc 0.15.2 (Clang 20.1.2), wasm-tools 1.263.0:
* python3 gen4.py 127 # writes table4.bin; header constants inlined above
* zig cc -target wasm32-freestanding -Oz -mbulk-memory -nostdlib
* -Wl,--no-entry -Wl,--export-memory -Wl,-z,stack-size=256
* -Wl,--initial-memory=131072 -Wl,--max-memory=131072
* -Wl,--export=input_ptr -Wl,--export=input_utf8_cap
* -Wl,--export=output_utf8_cap -Wl,--export=render -Wl,--export=tbl
* -Wl,--strip-all unescape.c -o raw.wasm
* python3 patch.py raw.wasm table4.bin unescape.wasm
* patch.py swaps the tbl placeholder for memory.init and appends table4.bin
* as a passive data segment.
*
* ----- gen4.py -----
* # gen4.py NMERGE: builds the passive entity table (table4.bin) and the Huffman
* # header constants (tab4.json, inlined into the source). Per first-letter bucket,
* # a byte-aligned LSB-first bit stream of records, names in sorted order:
* # Huffman P(prefix length shared with the previous name, >= 1; 0 ends bucket)
* # Huffman C(name symbols..., then terminator 0-3 = legacy | pair << 1)
* # symbols 128+i are byte-pair merges expanding to PAIR[2i], PAIR[2i+1]
* # value prediction: Xfr/Xopf/Xscr use base + letter index; other names take
* # Huffman S(choice among the last four values in the bucket)
* # Huffman K(k = bit length of zigzag delta from prediction) + (k-1) raw bits
* # if pair: 3-bit index into second_cp.
* import html.entities as e, collections, heapq, sys, json
* NM = int(sys.argv[1])
* h = e.html5
* names = sorted({k.rstrip(';') for k in h})
* SECOND = sorted({ord(h[n + ';'][1]) for n in names if len(h[n + ';']) > 1})
* order = [chr(c) for c in range(65, 91)] + [chr(c) for c in range(97, 123)]
* BASE = {'fr': 0x1D504, 'opf': 0x1D538, 'scr': 0x1D49C}
* recs = []; prev = ''
* for n in names:
* if prev[:1] != n[:1]: prev = n[0]; hist = [0] * 4
* p = 1
* while p < min(len(n), len(prev)) and n[p] == prev[p]: p += 1
* v = [ord(c) for c in h[n + ';']]
* rule = n[1:] in BASE
* if rule: cands = [BASE[n[1:]] + order.index(n[0])]
* else: cands = hist[::-1]
* best = None
* for i, pv in enumerate(cands):
* d = v[0] - pv; z = (d << 1) ^ (d >> 63)
* if best is None or z.bit_length() < best[0]: best = (z.bit_length(), i, z)
* if not rule: hist = hist[1:] + [v[0]]
* term = (n in h) | ((len(v) > 1) << 1)
* recs.append([n[0], p, [ord(c) for c in n[p:]], term, best[0], best[2], SECOND.index(v[1]) if len(v) > 1 else 0, None if rule else best[1]])
* prev = n
* pairs = []
* for i in range(NM):
* pc = collections.Counter()
* for r in recs:
* s = r[2]
* for a, b in zip(s, s[1:]): pc[a, b] += 1
* if not pc: break
* (a, b), c = pc.most_common(1)[0]
* if c < 3: break
* sym = 128 + i; pairs += [a, b]
* for r in recs:
* s = r[2]; o = []; j = 0
* while j < len(s):
* if j + 1 < len(s) and s[j] == a and s[j + 1] == b: o.append(sym); j += 2
* else: o.append(s[j]); j += 1
* r[2] = o
*
* def lengths(cnt):
* hp = [(c, i, [s]) for i, (s, c) in enumerate(sorted(cnt.items()))]; heapq.heapify(hp)
* L = {s: 0 for s in cnt}; k = len(hp)
* while len(hp) > 1:
* a = heapq.heappop(hp); b = heapq.heappop(hp)
* for s in a[2] + b[2]: L[s] += 1
* heapq.heappush(hp, (a[0] + b[0], k, a[2] + b[2])); k += 1
* assert max(L.values()) <= 15, max(L.values())
* return L
* def canon(L):
* syms = sorted(L, key=lambda s: (L[s], s)); code = 0; codes = {}; last = 0
* for s in syms:
* code <<= (L[s] - last); last = L[s]; codes[s] = (code, L[s]); code += 1
* cnt = [0] * 16
* for s in syms: cnt[L[s]] += 1
* return codes, cnt, syms
* alph = {a: collections.Counter() for a in 'PCKS'}
* alph['P'][0] += len(order)
* for b, p, s, t, k, z, sec, sel in recs:
* if sel is not None: alph['S'][sel] += 1
* alph['P'][p] += 1; alph['K'][k] += 1
* for c in s: alph['C'][c] += 1
* alph['C'][t] += 1
* tabs = {a: canon(lengths(c)) for a, c in alph.items()}
* class Bits:
* def __init__(s): s.out = bytearray(); s.acc = 0; s.n = 0
* def put(s, v, n):
* for i in range(n): s.bit((v >> i) & 1)
* def bit(s, b):
* s.acc |= b << s.n; s.n += 1
* if s.n == 8: s.out.append(s.acc); s.acc = 0; s.n = 0
* def huff(s, a, sym):
* code, n = tabs[a][0][sym]
* for i in range(n - 1, -1, -1): s.bit((code >> i) & 1)
* def done(s):
* if s.n: s.out.append(s.acc); s.acc = 0; s.n = 0
* return s.out
* streams = {c: Bits() for c in order}
* for b, p, s, t, k, z, sec, sel in recs:
* w = streams[b]; w.huff('P', p)
* for c in s: w.huff('C', c)
* w.huff('C', t)
* if sel is not None: w.huff('S', sel)
* w.huff('K', k)
* if k > 1: w.put(z, k - 1)
* if t & 2: w.put(sec, 3)
* idx = bytearray(); body = bytearray(); base = 2 * 53
* for c in order:
* streams[c].huff('P', 0)
* idx += (base + len(body)).to_bytes(2, 'little'); body += streams[c].done()
* idx += (base + len(body)).to_bytes(2, 'little')
* open('table4.bin', 'wb').write(idx + body)
* hdr = bytearray(); off = {}
* for a in 'PCKS':
* codes, cnt, syms = tabs[a]
* top = max(i for i in range(16) if cnt[i])
* off[a + '_CNT'] = len(hdr); hdr += bytes(cnt[1:top + 1])
* off[a + '_SYM'] = len(hdr); hdr += bytes(syms)
* off['PAIR'] = len(hdr); hdr += bytes(pairs)
* mx = max(len(s.out) for s in streams.values())
* json.dump(dict(off=off, huff=list(hdr), second=SECOND + [0] * (8 - len(SECOND)), scratch=mx + 8), open('tab4.json', 'w'))
* print(NM, 'table', len(idx + body), 'hdr', len(hdr), 'total', len(idx + body) + len(hdr), 'maxbucket', mx, file=sys.stderr)
*
* ----- patch.py -----
* # Replace the exported `tbl` placeholder with memory.init from a passive table segment.
* import re, subprocess, sys
* raw, table, out = sys.argv[1:4]
* wat = subprocess.run(['wasm-tools', 'print', raw], check=True, capture_output=True, text=True).stdout
* m = re.search(r'\(export "tbl" \(func (\d+)\)\)\n', wat)
* fn = m.group(1); wat = wat.replace(m.group(0), '')
* start = wat.index(f'(func (;{fn};) ')
* depth, i = 0, start
* while True:
* if wat[i] == '(': depth += 1
* elif wat[i] == ')':
* depth -= 1
* if depth == 0: break
* i += 1
* head = wat[start:wat.index('\n', start)]
* seg = sum(1 for _ in re.finditer(r'^\s*\(data ', wat, re.M))
* wat = wat[:start] + head + f'\n local.get 0\n local.get 1\n local.get 2\n memory.init {seg}\n )' + wat[i + 1:]
* data = open(table, 'rb').read()
* esc = ''.join(f'\\{b:02x}' for b in data)
* k = wat.rstrip().rindex(')')
* wat = wat[:k] + f' (data "{esc}")\n)\n'
* open(out + '.wat', 'w').write(wat)
* subprocess.run(['wasm-tools', 'parse', out + '.wat', '-o', out], check=True)
* subprocess.run(['wasm-tools', 'validate', out], check=True)
*/