Unescape HTML · C 🤝 Fable 5.2
SHA-256
f7b472378bafa3c69d5637027219dc5d1739a03e8042c65bdd7b53d60a66a358
View source (47.7 KiB of C)
// unescape_html in C with Wasm SIMD: decodes every HTML character reference in UTF-8 text
// the way Python's html.unescape does, and copies all other bytes unchanged.
//
// The design goal is a short path per reference with few unpredictable branches:
// - 64 zero bytes are written after the input, so no load or loop needs a bounds check and
// nothing stale from an earlier input can be mistaken for part of a reference.
// - Two stages per 4 KiB window. Stage 1 turns each 64-byte block into a bitmask of its `&`
// and appends their positions to a list, without branching on what it finds. Stage 2
// walks the list: copy the text since the last reference (32 bytes unconditionally, more
// in a loop), then decode. The next position is known before the current reference is
// decoded, so consecutive references do not wait on each other.
// - Inputs without `&` are returned in place; nothing is copied.
// - A name of up to 7 bytes ending in `;` is looked up without measuring it: the first `;`
// in the next 8 bytes is found with a SWAR zero-byte test, the bytes up to it are the key,
// and one multiply indexes an open-addressed table of 16-byte entries (key, value, length).
// A hit proves the name; legacy and common names sit in their home slot.
// - Longer names go through a second table and one masked 32-byte vector compare.
// - Without `;` only the 106 legacy names match. A filter on the first two bytes gives the
// longest legacy name that could start there, usually none.
// - Numeric references of up to 7 digits, decimal or hexadecimal, share one branch-free
// SWAR path, and the code point is encoded as UTF-8 without branching on its length.
// The lookup tables are built on the first call from a 6.7 KB packed entity list (24.5 KB
// unpacked), so the size of the list costs nothing per reference: see `sym` and `init`.
// Memory is 7 pages (448 KiB): the buffers hold 128 KiB of input, and unpacking borrows
// the output buffer for its working memory.
//
// Build: zig cc -target wasm32-freestanding -O3 -msimd128 -mbulk-memory -nostdlib
// -Wl,--no-entry -Wl,--export-memory -Wl,--initial-memory=458752 -Wl,--max-memory=458752
// -Wl,-z,stack-size=8192 -Wl,--strip-all -o unescape-lowmem.wasm unescape-lowmem.c
// then: wasm-opt -O3 --enable-simd --enable-bulk-memory unescape-lowmem.wasm -o unescape-lowmem.wasm
#include <stdint.h>
#include <wasm_simd128.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
// The official suite and benchmark send at most 104,000 bytes; 128 KiB keeps memory small.
#define INPUT_CAP (1u << 17)
// The largest growth is `≫⃒` (5 bytes) becoming 6 bytes.
#define OUTPUT_CAP (INPUT_CAP / 5 * 6 + 8)
#define PAD 128
#define FAST_BITS 12
#define FAST_TAIL 32
#define LEG_BITS 8
#define LEG_TAIL 16
#define LONG_BITS 11
#define EMPTY (~(u64)0)
// Bytes of input per stage-1 window; a multiple of 64.
#define WINDOW 4096
#define HIST_SIZE 16130
#define ENTITY_COUNT 2125
#define LONG_COUNT 506
#define MODEL_BITS 16
#define MODEL_LIMIT 5
#define FAST_MUL 0xa59d054b12f5b905ull
#define LEG_MUL 0xf880d97d1854e551ull
#define LONG_MUL 0xa0c2995f40498cb3ull
static const u8 packed[6687] = {
222,225,26,230,115,49,144,190,58,140,204,218,145,211,103,41,60,228,215,89,198,70,136,31,
120,107,161,60,145,117,23,224,59,50,82,153,166,225,41,200,223,241,49,49,235,105,79,34,
245,209,18,155,26,64,233,141,35,163,78,234,106,47,137,126,73,59,237,168,88,188,151,19,
153,33,229,86,50,57,35,236,152,12,222,37,155,218,56,106,183,106,67,155,9,17,68,5,
251,212,169,139,139,242,196,16,22,132,182,173,0,21,86,254,103,163,13,17,161,164,21,213,
238,13,212,52,176,7,109,4,134,56,247,170,56,193,8,165,52,120,1,140,26,41,13,141,
22,22,31,69,77,96,17,232,215,156,228,252,42,232,21,24,224,48,224,209,194,156,31,50,
151,176,224,105,87,251,82,179,36,236,219,133,155,181,85,168,64,30,180,148,116,207,185,107,
138,251,191,117,214,13,175,173,180,68,162,135,12,143,152,190,157,242,50,140,49,49,247,211,
174,46,207,34,111,92,236,224,40,17,141,47,150,39,3,115,5,141,82,93,223,195,141,110,
20,1,169,73,224,182,218,46,155,138,230,66,245,112,126,213,74,11,5,110,232,1,85,23,
119,178,223,57,0,180,111,163,123,51,255,145,145,220,231,159,116,225,205,245,55,187,29,129,
218,0,228,74,79,104,45,104,113,54,193,52,166,11,18,51,144,102,197,190,63,142,61,102,
184,6,198,168,123,222,21,233,161,31,56,85,85,142,215,49,170,127,202,124,99,100,31,32,
117,191,36,171,227,153,192,42,136,217,165,194,206,1,135,115,72,51,194,62,60,98,242,29,
71,43,144,196,232,127,222,188,111,190,112,164,97,60,2,99,13,252,99,166,240,46,22,191,
84,46,79,5,249,142,71,212,120,53,250,205,107,109,218,144,110,175,156,71,109,214,136,53,
170,163,166,231,85,255,136,153,201,54,51,99,218,41,149,41,209,201,205,242,251,38,45,226,
29,59,231,51,46,164,234,65,7,75,190,137,65,196,249,127,115,189,160,180,83,250,47,93,
166,99,229,205,192,159,65,146,182,132,182,9,177,211,237,0,67,139,142,232,110,199,224,110,
11,181,12,247,91,153,249,84,22,63,213,96,211,84,37,176,254,49,10,225,116,222,77,239,
206,139,211,204,110,122,173,4,87,58,97,151,60,135,23,62,194,238,24,169,233,109,39,3,
217,143,255,253,139,125,164,82,131,193,189,67,153,45,199,249,18,145,107,247,124,78,132,147,
38,21,122,200,215,21,87,40,202,110,241,26,249,83,212,67,184,37,247,94,136,220,29,229,
85,190,230,239,234,148,246,141,233,198,8,246,179,29,107,61,138,179,197,198,99,172,118,199,
239,151,15,133,252,182,209,172,63,191,194,42,84,50,200,181,163,212,79,240,43,123,212,65,
251,83,134,125,250,3,77,153,85,11,93,56,212,51,82,178,253,178,173,9,206,27,189,229,
170,3,151,91,200,8,151,125,206,108,76,203,67,216,78,145,40,104,251,23,10,66,103,160,
207,159,177,1,161,183,124,2,7,92,86,3,142,0,12,78,77,24,19,238,169,235,134,250,
200,41,0,101,236,25,145,242,202,71,153,255,208,133,71,228,161,96,121,25,84,65,60,105,
161,69,60,62,51,190,208,43,163,59,43,229,64,7,199,213,207,239,101,47,176,17,189,245,
92,203,36,170,187,202,74,31,101,106,55,21,170,99,52,212,8,109,24,80,225,199,12,65,
213,232,140,143,220,130,229,128,254,210,195,123,206,101,162,230,17,227,162,165,91,233,231,128,
186,230,48,35,46,94,145,139,184,137,221,60,154,41,197,156,179,225,77,52,198,199,223,132,
196,69,71,248,124,170,67,130,190,19,125,24,30,64,140,250,83,48,224,6,15,24,206,70,
39,245,27,249,31,10,158,240,146,2,33,36,129,98,172,154,146,12,83,190,69,177,48,103,
19,159,65,196,10,180,185,4,20,64,108,60,202,242,79,128,254,47,237,237,110,12,120,19,
78,111,17,85,191,107,107,25,38,54,68,5,109,47,80,39,230,56,215,29,19,127,178,73,
104,25,217,252,57,58,50,56,212,89,56,180,89,123,140,135,204,94,51,247,153,45,202,122,
120,240,241,255,108,51,127,41,124,146,246,110,90,37,233,28,16,119,134,67,180,52,211,9,
64,79,26,237,209,116,11,146,93,120,212,207,230,82,112,19,207,84,248,153,214,47,246,223,
50,32,195,126,42,244,135,141,174,31,208,193,25,34,86,136,110,23,183,36,224,2,134,1,
101,41,35,170,30,59,214,203,141,230,240,10,51,240,177,227,89,60,237,65,140,238,139,218,
95,174,47,47,24,255,41,11,163,90,23,128,209,26,108,58,135,71,181,193,45,105,222,23,
230,139,127,15,128,178,163,34,10,245,177,196,88,31,217,100,164,38,193,201,166,19,186,10,
111,229,170,206,37,234,148,112,225,109,63,61,122,204,42,136,195,171,237,66,252,180,96,110,
99,36,235,54,241,96,210,40,205,91,177,174,144,15,41,42,153,120,253,117,109,155,69,41,
144,227,237,153,65,136,185,166,0,136,33,159,232,44,201,251,132,192,187,222,217,70,99,208,
15,180,170,13,16,97,84,178,49,10,49,107,175,249,190,188,130,51,199,19,57,63,157,63,
18,151,76,242,202,54,219,219,249,87,170,160,151,136,76,20,193,112,196,124,245,166,56,231,
179,254,137,136,172,126,43,50,105,235,251,132,211,139,124,245,191,12,180,197,142,181,27,175,
97,185,134,139,72,205,39,207,25,232,81,5,71,48,109,198,113,12,19,29,51,117,48,56,
48,95,219,152,248,222,157,217,114,91,213,167,184,92,89,44,199,22,0,235,226,184,71,198,
30,245,69,234,80,5,118,238,59,210,242,15,10,13,37,13,79,23,139,205,171,44,177,173,
96,62,113,100,28,234,196,17,6,224,52,227,124,222,145,11,242,16,249,174,90,174,72,125,
35,251,42,167,68,117,185,245,91,184,26,237,200,174,216,101,218,100,196,109,246,139,216,123,
209,77,24,132,156,153,155,144,87,13,191,181,31,197,251,73,120,92,31,100,2,181,217,184,
168,23,159,104,26,84,228,114,47,125,230,31,208,223,184,197,95,4,81,94,110,222,116,64,
197,58,146,67,214,224,74,5,113,230,234,220,200,61,34,140,131,115,227,189,85,14,43,86,
212,36,47,25,249,81,81,69,184,116,249,191,254,47,246,32,160,136,180,122,51,64,235,16,
105,248,189,192,156,44,78,128,65,203,121,160,121,124,162,135,192,174,75,38,102,91,170,247,
61,115,100,105,155,200,203,101,122,118,192,136,126,178,104,17,175,62,98,185,58,133,211,188,
113,178,13,93,216,253,248,171,108,27,27,133,174,155,39,136,86,96,188,185,243,190,142,157,
183,248,163,67,116,54,93,126,2,19,70,52,146,5,82,157,240,17,127,117,117,27,7,100,
193,173,219,57,216,75,235,22,198,241,70,73,79,11,248,138,43,47,63,207,64,238,171,157,
56,97,170,15,51,240,194,81,104,36,79,249,203,79,233,75,190,17,79,16,238,177,245,194,
206,105,95,38,155,135,115,69,76,107,231,197,254,16,38,206,32,98,143,66,3,117,173,97,
39,204,97,43,150,182,235,105,9,5,60,148,109,28,214,131,223,29,181,106,173,175,136,225,
196,250,29,63,186,180,20,124,148,59,20,57,205,247,60,121,152,0,222,191,234,133,8,7,
0,207,224,227,4,53,151,197,73,246,127,148,94,216,76,136,183,199,163,234,112,10,5,227,
242,169,108,160,134,112,178,166,221,29,178,56,53,12,142,109,37,143,89,70,95,38,112,11,
4,197,96,254,72,185,111,135,160,195,121,25,235,74,164,78,110,38,140,62,76,14,13,24,
112,31,55,30,12,143,27,107,183,104,234,55,108,176,22,174,155,197,129,196,64,216,27,87,
57,237,163,200,23,185,187,218,104,226,133,186,132,118,169,198,239,34,192,33,130,27,178,127,
129,207,115,149,107,24,217,28,57,50,125,10,170,135,236,239,251,91,176,121,103,74,105,12,
170,112,110,149,138,182,229,37,153,60,221,162,127,89,196,79,157,200,159,251,140,115,123,55,
193,202,61,113,141,167,209,22,230,215,207,203,12,61,76,105,190,194,243,29,134,26,120,67,
66,185,148,98,61,97,218,112,213,165,57,169,178,53,233,161,117,20,56,201,56,154,54,44,
231,49,11,212,5,198,185,208,191,15,147,239,47,222,236,35,34,157,156,237,109,254,206,62,
152,10,188,56,187,42,208,196,20,5,241,32,40,187,22,113,0,155,159,73,122,167,9,201,
208,64,212,116,149,45,224,106,120,59,221,204,135,143,240,191,104,90,179,92,59,254,102,188,
166,40,229,41,108,190,250,130,147,38,222,91,126,238,25,141,159,106,77,27,72,3,88,176,
16,109,5,13,101,128,174,220,219,52,214,251,96,248,8,249,218,200,212,183,34,129,252,249,
227,102,67,212,160,120,240,70,32,18,233,44,30,167,15,117,249,45,191,79,175,129,68,91,
21,84,241,148,202,231,62,216,191,124,198,55,143,60,224,241,129,144,96,15,196,115,9,24,
4,239,202,240,178,234,199,141,153,211,86,103,28,123,47,215,197,50,96,191,6,255,186,96,
188,32,155,234,236,165,245,254,114,16,221,48,0,114,148,241,65,233,161,114,186,135,225,180,
151,250,0,138,68,67,133,104,187,244,173,192,188,21,155,185,215,113,189,88,158,208,28,91,
226,52,72,53,41,91,197,198,126,197,95,28,34,154,22,93,170,75,32,147,130,179,196,141,
161,151,160,187,118,148,112,123,47,31,197,88,64,156,11,123,45,222,155,227,104,100,249,80,
20,148,159,36,241,115,219,232,63,52,232,233,138,146,4,89,244,232,122,24,53,24,168,238,
16,52,90,83,230,248,107,253,133,182,227,16,13,104,88,211,223,200,9,23,235,50,177,213,
207,16,241,200,135,217,243,168,29,193,161,21,238,87,216,119,11,42,205,185,135,123,7,87,
71,230,184,64,151,114,192,17,85,250,197,213,76,126,34,10,173,27,70,253,255,235,230,227,
65,118,158,177,103,82,31,109,202,203,53,248,97,127,252,165,38,88,147,102,74,37,124,111,
38,81,192,223,154,194,240,232,106,142,151,108,76,190,90,168,60,121,38,231,48,24,137,13,
127,21,144,97,84,210,102,116,39,156,221,167,46,131,14,92,130,93,61,44,181,115,140,159,
245,247,238,14,124,148,41,244,252,105,234,96,6,59,188,89,172,65,85,75,84,238,254,217,
122,125,87,99,245,19,247,39,100,89,168,87,38,117,11,252,57,235,200,243,89,43,30,232,
199,125,163,61,232,134,90,177,70,104,241,93,199,16,35,55,73,250,185,82,75,1,186,81,
174,180,255,1,184,134,61,242,157,30,123,82,23,70,188,15,165,25,25,21,203,252,193,167,
198,64,86,31,44,72,201,34,241,69,117,215,190,112,195,241,135,174,23,186,128,190,121,250,
36,229,75,143,46,16,6,155,228,188,67,235,85,149,44,125,17,212,162,189,13,116,77,104,
184,76,102,219,89,17,179,74,44,104,62,83,127,101,41,35,89,234,199,248,131,110,230,149,
199,235,64,16,243,29,10,185,86,22,117,173,95,183,138,102,251,193,177,204,188,241,225,251,
189,5,240,254,162,22,230,75,88,175,108,114,141,180,39,98,199,156,188,139,48,18,116,108,
129,19,243,141,32,1,155,61,41,35,12,44,206,165,250,174,216,228,221,95,128,105,228,122,
49,107,149,250,200,219,135,1,144,120,97,137,139,12,101,150,182,219,13,180,110,236,146,35,
87,255,144,28,151,23,196,3,109,2,18,78,10,209,102,195,64,178,17,215,142,134,214,88,
174,44,212,32,24,86,77,224,137,181,174,103,143,196,49,177,166,118,80,62,37,201,91,249,
76,194,144,141,169,166,121,245,110,229,197,235,114,169,245,122,116,73,91,165,232,128,105,115,
164,68,232,35,148,176,194,92,167,118,54,255,206,145,156,215,240,103,44,242,192,150,90,214,
46,158,156,219,21,164,242,144,232,230,9,34,153,246,243,33,182,94,128,191,139,10,114,165,
136,188,69,11,226,74,130,61,140,32,77,235,194,150,226,149,180,157,88,189,136,89,81,46,
161,253,6,128,190,239,185,251,113,252,200,179,7,210,38,84,110,5,1,246,68,150,143,152,
250,106,150,92,21,77,222,145,208,109,70,33,215,200,34,190,24,62,94,182,234,105,93,61,
74,25,30,67,130,163,163,25,208,165,214,149,137,133,243,121,97,98,119,220,52,232,26,7,
181,215,40,14,249,244,55,33,219,110,255,167,42,142,236,87,248,192,7,130,205,134,250,211,
64,233,77,237,131,195,118,28,180,160,42,236,40,188,178,153,140,99,34,176,92,20,230,240,
195,101,44,39,95,84,249,163,71,152,54,169,128,214,213,155,120,115,115,144,174,87,117,40,
109,118,14,98,58,135,13,46,38,97,72,190,146,215,110,208,155,177,136,225,65,91,204,48,
180,90,181,50,201,25,39,65,154,190,201,251,113,188,120,81,181,106,162,207,114,159,253,61,
243,2,42,82,100,223,129,51,145,57,238,5,219,148,51,76,236,17,210,143,177,33,148,40,
76,236,151,150,251,230,162,38,83,147,213,8,127,53,83,27,129,104,83,139,99,216,152,247,
13,26,245,247,157,44,196,227,100,176,201,15,87,166,175,44,61,13,83,111,183,6,205,125,
60,98,184,135,229,220,208,94,38,5,136,40,252,196,137,92,63,198,146,187,2,164,16,250,
219,116,156,225,227,28,58,81,232,208,6,231,48,137,189,143,87,28,136,34,245,49,59,81,
188,211,6,209,182,193,13,241,88,101,37,86,250,24,42,252,173,186,182,48,56,72,129,215,
6,8,91,165,88,107,24,250,23,52,85,6,160,0,107,144,209,54,212,31,167,22,115,151,
68,119,65,29,65,175,190,141,59,104,244,42,160,88,151,57,215,4,195,24,39,22,238,32,
177,154,109,2,198,181,101,130,181,149,226,27,162,133,80,122,137,240,236,165,213,128,39,116,
16,105,195,53,185,144,8,123,251,227,217,195,253,10,60,231,188,120,50,58,135,165,78,111,
84,64,65,183,15,50,228,62,42,135,197,81,56,28,5,47,180,136,83,92,119,184,143,132,
148,46,33,8,30,140,135,12,113,26,220,59,16,178,78,148,15,20,15,240,156,77,157,54,
129,140,204,72,209,170,234,93,15,132,181,111,197,191,187,86,209,1,252,79,181,172,100,200,
88,44,255,54,217,135,201,43,74,143,52,12,167,176,165,140,106,31,92,52,50,68,180,209,
15,142,189,190,70,123,7,239,64,241,192,156,51,82,52,18,209,7,93,108,91,168,56,140,
150,253,11,223,120,181,215,162,54,201,102,74,4,95,75,153,22,95,224,106,111,151,212,39,
16,223,42,68,64,254,187,16,228,69,235,248,35,157,6,7,178,66,209,1,23,9,126,216,
127,79,62,163,149,191,178,236,160,5,141,202,180,151,18,90,15,204,74,203,99,12,15,3,
2,112,246,80,129,84,150,72,243,5,237,194,247,165,20,155,100,110,151,190,2,155,110,103,
136,71,130,47,67,252,130,30,253,209,178,64,66,217,158,82,32,124,161,86,142,14,71,58,
235,59,97,248,125,128,56,107,160,238,116,49,221,164,173,77,134,214,17,136,184,142,94,236,
181,128,235,124,227,99,236,31,34,187,135,44,220,114,42,29,18,132,148,95,6,100,223,58,
57,148,117,76,48,27,137,67,25,80,144,103,12,115,15,142,104,120,64,206,248,71,126,96,
112,166,229,87,188,11,181,169,8,203,69,192,119,100,28,87,218,67,41,147,236,194,148,93,
175,156,175,26,254,152,69,99,224,214,72,52,220,237,127,205,238,209,144,47,74,121,105,47,
206,151,125,114,46,63,64,99,163,108,53,84,102,224,242,195,145,119,67,244,147,13,224,7,
66,72,236,57,100,155,22,113,124,139,194,95,169,115,45,143,24,142,203,183,154,159,193,14,
191,133,183,243,191,162,108,246,91,105,85,132,137,190,200,218,37,181,133,113,230,155,1,46,
228,234,174,101,161,218,25,63,246,113,14,106,110,217,32,247,35,255,3,51,247,179,218,227,
103,69,224,161,75,46,73,205,133,14,17,242,0,35,160,154,216,174,38,251,48,10,219,152,
161,96,88,133,84,178,91,45,111,26,21,146,211,247,208,15,215,83,173,253,224,57,198,184,
150,74,103,192,117,115,18,119,238,231,78,14,245,15,245,173,246,152,41,42,253,154,225,19,
40,50,215,211,42,220,135,31,78,238,32,211,26,28,28,178,96,68,51,182,162,35,11,143,
143,2,157,108,22,160,15,208,12,164,108,134,185,241,47,34,146,87,78,190,102,39,27,53,
8,195,45,209,41,17,68,25,184,217,81,155,52,163,236,161,165,43,136,87,188,169,47,103,
19,242,87,111,104,64,83,171,211,14,211,136,90,54,100,68,195,141,150,188,54,173,110,237,
124,97,167,63,191,184,132,3,100,154,225,167,9,80,162,33,90,32,88,102,136,138,177,13,
112,162,198,115,172,192,187,49,65,250,18,220,229,51,130,112,29,125,203,86,83,28,60,147,
39,241,207,138,198,61,219,123,234,78,123,11,239,228,185,175,167,195,77,101,19,244,87,81,
222,169,81,135,35,213,130,7,224,72,123,24,119,52,2,211,160,105,151,181,180,79,253,26,
52,61,151,113,231,252,4,50,50,61,243,237,15,99,159,126,131,255,85,203,157,83,101,45,
13,197,69,33,126,105,167,142,22,158,202,58,174,180,17,235,9,175,190,213,224,107,244,219,
4,115,134,182,181,44,120,236,193,129,207,99,47,14,230,73,198,54,75,218,145,225,188,140,
99,144,95,236,182,208,170,209,120,149,4,37,69,187,80,60,187,82,61,98,55,9,32,232,
121,28,44,165,99,99,10,79,254,123,60,186,11,152,174,237,152,176,72,23,244,154,32,237,
226,249,104,167,63,200,254,184,201,111,125,66,75,185,226,165,0,60,154,66,64,141,64,230,
222,72,199,51,223,107,0,235,102,90,40,141,213,33,13,60,15,6,89,250,53,246,144,65,
120,146,253,19,83,217,230,94,172,84,247,196,67,240,102,193,95,242,219,244,234,207,112,82,
170,217,158,219,74,17,36,203,222,254,211,134,223,191,71,164,149,252,79,97,168,187,59,141,
137,98,157,181,38,87,215,191,206,112,73,0,168,60,104,31,8,89,124,49,74,139,21,238,
123,128,18,22,241,211,41,84,243,51,206,109,230,77,2,136,110,75,30,207,115,136,231,8,
183,131,23,50,154,165,59,169,196,60,149,2,234,22,5,151,131,112,81,45,189,116,212,157,
34,98,90,194,12,128,169,200,9,89,118,7,79,168,121,66,214,231,43,113,141,38,60,120,
173,82,44,155,205,121,81,15,248,84,46,114,85,152,215,17,100,161,128,182,118,103,218,107,
0,91,197,175,56,227,132,164,27,78,181,43,35,158,56,222,137,37,243,212,53,37,1,48,
56,118,243,201,174,156,161,169,14,252,49,246,107,12,152,6,34,138,228,158,143,27,193,82,
119,14,139,244,25,31,78,26,106,105,84,208,236,244,121,57,32,39,190,91,180,71,186,255,
226,136,155,249,128,172,135,133,82,172,196,203,122,56,82,147,225,164,45,167,78,187,115,58,
210,168,40,190,103,196,135,59,38,73,127,87,75,172,205,148,8,175,255,142,44,171,233,95,
190,201,150,92,207,21,245,112,85,147,60,139,148,92,165,220,104,77,75,228,126,119,112,191,
126,103,62,240,200,99,200,184,68,166,182,167,139,25,236,32,143,128,185,88,94,142,2,148,
107,201,248,220,27,63,188,52,1,27,201,127,26,221,203,204,81,218,103,239,24,190,75,27,
34,183,129,207,226,113,41,104,69,104,200,186,37,111,5,77,16,202,151,143,223,0,8,66,
242,106,248,95,100,97,16,163,249,202,148,236,52,179,225,40,171,49,124,208,54,213,30,170,
104,129,28,10,177,31,160,48,28,34,219,105,199,7,218,254,158,241,46,66,8,15,21,159,
150,89,242,226,117,154,150,156,149,33,32,119,154,156,160,20,138,82,114,127,143,238,34,179,
111,228,32,15,127,65,157,40,183,225,208,138,151,180,119,122,38,172,39,98,54,145,210,194,
164,253,62,137,49,198,199,175,69,121,216,41,35,117,208,103,79,84,120,157,167,37,115,80,
28,199,96,41,118,38,188,236,204,200,144,253,235,77,9,71,84,12,104,208,181,233,100,131,
105,132,28,219,89,251,250,230,182,46,121,123,147,5,208,239,67,50,130,14,83,130,84,179,
163,111,159,165,113,93,135,153,127,131,182,12,137,242,141,70,11,183,7,89,162,211,144,176,
14,229,157,137,148,36,87,235,71,177,142,85,237,216,26,70,183,60,92,32,135,223,90,88,
210,37,180,251,183,111,58,89,192,245,214,14,74,65,0,92,157,140,101,49,15,18,70,84,
151,253,25,141,38,120,66,213,86,135,202,22,104,163,48,24,46,203,115,35,248,244,126,49,
194,90,31,100,182,7,161,179,224,52,106,24,13,85,62,209,88,77,83,47,127,105,41,190,
107,161,8,103,185,165,206,48,37,150,203,126,204,97,7,198,209,63,159,238,215,40,246,155,
129,162,59,239,31,98,53,118,226,70,35,142,223,195,207,187,146,54,45,61,90,31,146,103,
112,91,126,208,134,222,183,40,186,11,155,112,173,164,89,34,165,164,81,185,172,104,163,240,
117,91,67,19,129,206,90,158,202,7,135,6,236,125,182,241,36,17,170,107,38,90,180,149,
120,114,8,83,127,244,236,190,111,33,227,189,219,230,237,83,30,69,67,210,14,67,159,68,
239,192,8,85,233,239,56,204,145,43,131,54,8,221,131,59,8,82,135,119,159,50,94,218,
102,132,219,142,62,52,56,112,86,113,167,75,138,90,129,255,243,73,56,109,119,196,56,60,
71,166,212,143,204,218,97,48,118,13,237,55,100,103,213,45,204,36,27,181,92,136,81,235,
33,11,189,204,209,224,157,17,210,112,67,198,166,226,246,250,155,239,104,138,161,249,191,239,
220,163,3,190,238,214,5,87,93,81,192,11,32,174,197,30,92,141,173,228,247,164,35,149,
97,28,157,237,33,249,79,53,91,146,32,243,241,57,83,76,148,92,16,40,31,14,87,222,
204,133,211,92,114,238,146,82,41,82,57,128,121,129,214,198,227,240,107,139,8,104,104,80,
222,36,223,163,52,213,245,206,7,133,56,150,202,99,79,169,191,89,67,192,117,183,201,74,
157,9,24,206,75,227,124,101,223,34,240,125,254,161,234,137,106,127,234,175,147,253,126,56,
112,6,212,215,118,183,209,205,119,5,81,179,55,171,49,61,210,62,156,213,231,52,91,6,
34,74,69,101,153,245,120,175,24,228,37,52,41,25,200,215,189,28,44,59,2,80,167,61,
112,75,154,10,26,99,125,209,44,145,245,185,151,53,195,238,73,184,60,43,129,180,169,65,
210,163,104,4,49,85,153,111,58,143,162,100,153,100,133,105,186,30,244,55,26,131,146,228,
154,76,173,254,114,90,102,49,240,252,153,64,111,200,195,190,50,169,156,137,181,32,22,227,
250,11,8,188,100,106,232,115,210,4,172,187,246,208,30,55,186,37,122,147,57,102,209,45,
6,198,218,100,114,159,165,19,228,12,172,255,137,188,140,29,2,4,11,17,126,63,246,234,
18,212,243,115,54,123,166,160,255,61,246,66,190,45,165,236,248,29,254,112,111,108,165,119,
195,152,36,247,27,52,171,179,220,95,147,120,225,18,57,79,4,32,30,104,23,52,126,52,
149,197,173,102,81,37,193,178,242,44,75,92,223,143,58,145,190,228,142,233,161,147,41,101,
100,120,25,223,37,214,136,164,201,25,151,172,215,220,91,151,28,36,206,37,9,30,225,195,
179,192,164,179,245,207,173,241,112,96,144,209,253,135,237,253,169,62,161,48,129,75,188,28,
241,109,7,55,158,46,107,32,209,34,14,178,59,9,131,12,100,239,43,200,116,119,187,164,
59,68,84,101,65,87,242,128,119,24,132,16,209,4,196,23,231,116,126,222,207,26,241,232,
65,166,234,201,101,88,152,242,200,253,70,249,0,177,234,215,229,102,10,178,206,66,202,220,
250,12,125,36,209,139,152,58,173,203,245,139,135,18,157,237,180,23,186,91,121,66,138,187,
226,5,177,21,88,30,203,6,67,189,99,180,73,221,108,168,74,69,237,73,104,126,170,189,
75,240,75,246,204,116,29,99,189,26,120,90,200,141,111,218,136,114,97,100,196,167,50,245,
101,224,147,216,252,134,239,163,212,96,57,232,14,218,146,46,212,37,72,185,208,50,19,26,
75,237,116,127,221,251,10,197,26,187,166,65,222,166,143,48,31,247,62,238,195,114,15,91,
143,62,50,253,45,184,1,7,205,219,199,153,123,96,82,222,144,213,205,68,200,195,152,77,
232,75,188,34,64,32,3,39,29,5,115,215,74,204,14,252,116,84,166,196,229,153,237,51,
171,253,199,108,178,202,41,130,138,153,141,58,101,71,56,175,215,206,167,140,242,125,57,216,
5,73,112,123,113,6,128,169,235,190,93,34,126,250,181,105,185,128,82,49,158,225,4,151,
28,59,159,252,114,145,76,236,159,239,183,147,84,173,146,209,184,210,223,142,221,129,187,147,
22,82,9,118,175,242,11,128,47,188,29,140,166,67,255,146,1,206,250,144,102,27,81,125,
217,4,27,218,57,21,74,122,211,83,165,18,52,183,89,91,249,192,95,23,11,244,119,133,
243,18,193,10,54,84,173,247,161,82,155,232,25,33,150,141,98,206,132,159,128,90,97,61,
23,36,148,64,128,154,209,182,42,207,11,31,128,3,70,171,131,105,16,12,226,240,180,186,
180,67,1,8,139,172,158,210,24,91,111,104,197,175,102,201,74,217,15,143,196,154,228,11,
148,235,94,4,22,160,116,195,28,232,94,92,213,165,30,51,70,190,173,149,232,81,82,83,
152,35,63,180,196,105,16,253,81,164,75,94,57,90,146,215,34,105,64,189,122,249,150,6,
123,29,186,75,159,173,201,208,46,141,133,240,163,72,162,197,65,76,255,64,91,174,13,40,
118,228,105,87,164,197,47,197,89,222,246,111,140,236,244,53,48,106,59,100,170,143,31,170,
249,115,184,34,217,241,244,229,1,207,226,74,34,102,199,220,153,113,87,73,111,30,193,83,
210,6,38,157,79,236,53,103,242,241,44,207,4,234,248,124,105,61,95,185,194,114,118,3,
161,41,68,149,246,125,27,242,153,101,141,100,245,151,163,23,157,42,237,241,213,168,183,89,
61,139,213,204,149,183,164,156,250,131,19,81,78,80,205,144,137,151,122,3,237,196,14,50,
64,54,186,44,12,192,10,124,79,87,103,238,199,248,45,162,5,18,101,119,228,66,219,36,
173,189,205,234,103,78,110,24,158,18,252,15,12,65,254,50,171,30,109,23,78,217,212,231,
133,134,121,45,78,222,162,113,218,83,125,161,250,195,103,77,71,89,19,81,57,238,15,199,
222,63,18,70,141,193,70,79,181,107,190,159,156,134,79,35,151,237,4,145,216,2,209,157,
214,191,84,43,62,223,95,96,6,231,203,79,39,159,77,65,215,78,188,221,90,84,239,89,
137,73,238,222,36,20,162,31,191,82,63,200,93,134,214,198,59,150,195,71,205,216,106,165,
73,208,146,158,87,114,183,95,244,129,137,99,177,0,139,66,10,152,44,72,67,211,207,72,
6,33,10,161,97,121,148,240,178,127,79,12,146,188,226,103,59,178,214,0,127,105,82,95,
39,56,241,160,63,40,218,164,62,39,86,93,151,243,177,47,238,179,166,116,227,128,198,59,
157,148,234,243,74,21,34,157,27,165,159,11,7,217,36,50,222,42,167,188,54,216,121,95,
248,143,148,91,190,37,92,230,104,3,184,26,18,204,135,107,199,71,110,118,199,56,141,179,
6,132,147,203,10,59,127,79,72,150,76,8,23,193,32,168,232,15,176,222,153,100,30,110,
178,199,109,226,228,7,226,192,208,130,133,58,193,108,208,8,156,93,66,249,98,79,218,55,
204,146,110,156,161,231,251,204,111,3,212,219,100,223,14,130,242,100,102,116,115,141,35,74,
176,216,77,78,132,249,11,77,105,232,121,157,143,45,220,97,43,135,67,95,251,10,246,104,
84,227,187,184,93,37,108,162,18,232,62,134,180,112,152,40,150,171,252,108,188,61,59,11,
209,6,41,71,219,241,5,250,91,154,59,225,116,160,34,220,37,229,136,205,168,74,183,9,
76,147,143,13,76,223,179,147,252,57,155,209,12,108,0,146,147,171,243,239,45,145,219,199,
233,24,23,88,149,102,11,66,164,109,238,35,237,194,36,22,219,91,70,44,56,145,95,245,
99,79,237,73,86,89,59,23,77,228,129,65,30,145,5,193,80,250,127,36,50,167,253,238,
132,138,153,61,53,187,190,154,154,154,100,122,39,177,159,56,77,31,107,62,163,83,188,56,
128,130,31,249,81,56,102,49,171,20,50,116,86,176,246,164,185,8,117,52,105,7,161,30,
208,4,76,27,132,168,124,190,213,191,83,236,215,111,62,121,130,217,6,105,27,59,52,244,
198,90,116,165,138,57,77,65,127,190,81,27,201,6,244,178,53,24,225,246,139,61,85,95,
48,185,97,228,161,74,113,214,109,190,127,55,82,246,97,214,162,178,31,170,19,71,85,202,
6,217,98,7,71,152,11,65,172,34,107,136,8,10,186,138,228,165,176,41,149,113,108,234,
115,104,191,75,236,139,82,148,221,98,112,26,172,40,125,42,243,19,49,249,244,142,191,179,
96,200,65,56,122,55,231,59,92,94,64,122,10,24,169,174,167,72,181,9,186,16,252,124,
49,69,48,66,141,33,175,64,217,243,40,83,83,226,246,139,86,36,104,153,79,231,37,57,
36,68,140,209,221,71,10,222,83,85,252,213,74,153,202,
};
// The value's UTF-8 bytes in the low bytes and its length in the top byte.
typedef struct { u64 key, val; } Entry;
typedef struct { u8 name[32]; u64 val; u32 len; u32 pad; } Long;
static u8 input[INPUT_CAP + PAD] __attribute__((aligned(16)));
static u8 output[OUTPUT_CAP + PAD] __attribute__((aligned(16)));
static Entry fast[(1 << FAST_BITS) + FAST_TAIL];
static Entry leg[(1 << LEG_BITS) + LEG_TAIL];
static Long longs[LONG_COUNT] __attribute__((aligned(16)));
static u16 long_slots[1 << LONG_BITS];
// Longest legacy name starting with these two bytes (hashed), or 0.
static u8 leg_max[4096];
static u32 pos[WINDOW + 16];
static u32 ready;
// Windows-1252 remapping for references to 0x80-0x9F.
static const u16 c1[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,
};
static const u32 utf8_marks[5] = {0, 0, 0x80C0, 0x8080E0, 0x808080F0};
// Byte j of the 32 loaded at `len_mask + 32 - n` is 0xFF when j < n: 32 bytes of 0xFF, then 32 of 0.
static u8 len_mask[64] __attribute__((aligned(16)));
#define ONES 0x0101010101010101ull
#define HIGH 0x8080808080808080ull
#define LIKELY(x) __builtin_expect(!!(x), 1)
#define UNLIKELY(x) __builtin_expect(!!(x), 0)
static inline u64 ld64(const u8 *p) { u64 x; __builtin_memcpy(&x, p, 8); return x; }
static inline void st64(u8 *p, u64 x) { __builtin_memcpy(p, &x, 8); }
static inline void st32(u8 *p, u32 x) { __builtin_memcpy(p, &x, 4); }
static inline v128_t ld(const u8 *p) { return wasm_v128_load(p); }
static inline void st(u8 *p, v128_t v) { wasm_v128_store(p, v); }
static inline u32 amps(v128_t v) { return wasm_i8x16_bitmask(wasm_i8x16_eq(v, wasm_i8x16_splat('&'))); }
static inline u32 leg_slot(u64 w) { return (((u32)w & 0xFFFF) * 0x9E3779B1u) >> 20; }
static inline u64 rotl(u64 x, u32 r) { return x << r | x >> (64 - r); }
static inline u32 long_hash(u64 head, u64 tail, u32 n) {
return (u32)((((head ^ rotl(tail, 29)) + n) * LONG_MUL) >> (64 - LONG_BITS));
}
// Lay the bits of a code point out as four UTF-8 bytes, then drop the unused leading ones.
__attribute__((always_inline)) static inline u32 utf8(u32 v, u32 *len) {
u32 n = 1 + (v > 0x7F) + (v > 0x7FF) + (v > 0xFFFF);
u32 bits = v >> 18 | (v >> 12 & 0x3F) << 8 | (v >> 6 & 0x3F) << 16 | (v & 0x3F) << 24;
*len = n;
return n == 1 ? v : bits >> (32 - 8 * n) | utf8_marks[n];
}
// The entity list is stored packed and read once, on the first call. Entities are ordered
// by code point, so a value is a small step from the one before, and each name is coded
// with an adaptive binary range coder (the LZMA one) whose model mixes four contexts:
// the previous one, two and three characters, and a match model that predicts the
// character that followed the last place the previous two were seen. pack.py, printed
// at the end of this file, is the matching packer.
//
// A model entry is a 12-bit probability (stored XOR 0x800, so zeroed memory means one
// half) and a 4-bit count of how often it was used. The model's 128 KiB live in the output
// buffer, which is free until the first reference is decoded.
#define MODEL ((u16 *)output)
_Static_assert(sizeof output >= (2u << MODEL_BITS), "the model must fit in the output buffer");
#define SMALL __attribute__((minsize, noinline))
#define K (1u << 20)
SMALL static u32 utf8_once(u32 v, u32 *len) { return utf8(v, len); }
// Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
static const u16 rate[6] = {43690, 26214, 18724, 14563, 11915, 10082};
static const u8 *rc_in;
static u8 hist[HIST_SIZE];
static u16 last[4096];
static u32 rc_range, rc_code;
SMALL static u32 sym(const u32 *ctx, u32 nctx, u32 nbits) {
u32 node = 1, top = 1u << nbits;
do {
u16 *slot[4];
u32 num = 0, den = 0;
for (u32 k = 0; k < nctx; k++) {
u16 *s = slot[k] = &MODEL[((ctx[k] + node * 0x2545F491u) * 0x9E3779B1u) >> (32 - MODEL_BITS)];
int32_t p = *s >> 4 ^ 0x800, a = p - 0x800;
// Weigh a context by its order, how often it was seen and how sure it is.
u32 w = ((*s & 15u) * (1 + ((u32)(a < 0 ? -a : a) >> 8))) << k;
num += (u32)p * w;
den += w;
}
u32 p = den ? num / den : 0x800;
if (!p) p = 1;
u32 bound = (rc_range >> 12) * p, bit = rc_code < bound;
if (bit) rc_range = bound;
else rc_code -= bound, rc_range -= bound;
while (rc_range < 1u << 24) {
rc_range <<= 8;
rc_code = rc_code << 8 | *rc_in++;
}
for (u32 k = 0; k < nctx; k++) {
int32_t q = *slot[k] >> 4 ^ 0x800, n = *slot[k] & 15;
q += ((((int32_t)bit << 12) - q) * rate[n]) >> 16;
if (n < MODEL_LIMIT) n++;
*slot[k] = (u16)((q ^ 0x800) << 4 | n);
}
node = node * 2 + bit;
} while (node < top);
return node - top;
}
SMALL static void init(void) {
__builtin_memset(fast, 255, sizeof fast);
__builtin_memset(leg, 255, sizeof leg);
__builtin_memset(len_mask, 255, 32);
rc_in = packed + 4;
rc_range = ~0u;
rc_code = (u32)packed[0] << 24 | (u32)packed[1] << 16 | (u32)packed[2] << 8 | packed[3];
u32 cp = 0, nl = 0, hn = 1, ctx[4];
for (u32 r = 0; r < ENTITY_COUNT; r++) {
// Step from the previous code point: its bit length, then the bits below the top one.
ctx[0] = K;
u32 nb = sym(ctx, 1, 5), d = nb;
if (nb > 1) {
ctx[0] = 2 * K + nb;
d = (1u << (nb - 1)) + sym(ctx, 1, nb - 1);
}
cp += d;
u32 vn, vn2 = 0;
u64 val = utf8_once(cp, &vn);
ctx[0] = 3 * K + !d;
if (sym(ctx, 1, 1)) {
ctx[0] = 4 * K;
val |= (u64)utf8_once(sym(ctx, 1, 16), &vn2) << (8 * vn);
}
val |= (u64)(vn + vn2) << 56;
ctx[0] = 5 * K + (cp < 256);
u32 legacy = sym(ctx, 1, 1);
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
u8 name[40];
__builtin_memset(name, 0, 40);
u32 n = 0, h = 0, c, mp = 0, ml = 0;
for (;;) {
ctx[0] = 8 * K + (h & 63);
ctx[1] = 9 * K + (h & 4095);
ctx[2] = 13 * K + (ml ? hist[mp] : 0) * 16 + (ml < 3 ? ml : 3);
ctx[3] = 10 * K + (h & 0x3FFFF);
c = sym(ctx, 4, 6);
if (ml && hist[mp] == c) ml++, mp++;
else ml = 0;
hist[hn++] = (u8)c;
if (!c) break;
name[n++] = (u8)(c + (c < 11 ? '0' - 1 : c < 37 ? 'A' - 11 : 'a' - 37));
h = h << 6 | c;
if (n >= 2) {
u16 *l = &last[h & 4095];
if (!ml && *l) mp = *l, ml = 1;
*l = (u16)hn;
}
}
if (n <= 7) {
u64 key = ld64(name) | (u64)';' << (8 * n);
Entry *e = &fast[(key * FAST_MUL) >> (64 - FAST_BITS)];
while (e->key != EMPTY) e++;
e->key = key;
e->val = val;
if (legacy) {
key = ld64(name) | (u64)n << 56;
e = &leg[(key * LEG_MUL) >> (64 - LEG_BITS)];
while (e->key != EMPTY) e++;
e->key = key;
e->val = val;
u32 s = leg_slot(key); // only the first two bytes matter
if (leg_max[s] < n) leg_max[s] = n;
}
} else {
Long *l = &longs[nl++];
__builtin_memcpy(l->name, name, 32);
l->val = val;
l->len = n;
u32 hh = long_hash(ld64(name), ld64(name + n - 8), n);
while (long_slots[hh]) hh = (hh + 1) & ((1 << LONG_BITS) - 1);
long_slots[hh] = nl;
}
}
ready = 1;
}
__attribute__((export_name("input_ptr"))) u32 input_ptr(void) { return (u32)(uintptr_t)input; }
__attribute__((export_name("input_utf8_cap"))) u32 input_utf8_cap(void) { return INPUT_CAP; }
__attribute__((export_name("output_ptr"))) u32 output_ptr(void) { return (u32)(uintptr_t)output; }
__attribute__((export_name("output_utf8_cap"))) u32 output_utf8_cap(void) { return OUTPUT_CAP; }
__attribute__((export_name("render"))) u64 render(u32 n) {
if (UNLIKELY(!ready)) init();
u32 size = n < INPUT_CAP ? n : INPUT_CAP;
const u8 *src = input;
u8 *dst = output;
const v128_t zero = wasm_i8x16_splat(0);
st(input + size, zero);
st(input + size + 16, zero);
st(input + size + 32, zero);
st(input + size + 48, zero);
// Stage 1 lists the position of every `&` in a window; stage 2 copies the text between
// references and decodes each one. Knowing the next position before the current
// reference is decoded keeps the references independent of each other.
u32 e = 0, o = 0, base = 0;
while (base < size) {
u32 lim = size - base > WINDOW ? base + WINDOW : size;
u32 *out = pos;
do {
const v128_t amp = wasm_i8x16_splat('&');
v128_t ea = wasm_i8x16_eq(ld(src + base), amp), eb = wasm_i8x16_eq(ld(src + base + 16), amp);
v128_t ec = wasm_i8x16_eq(ld(src + base + 32), amp), ed = wasm_i8x16_eq(ld(src + base + 48), amp);
{
u64 mm = (u64)wasm_i8x16_bitmask(ea) | (u64)wasm_i8x16_bitmask(eb) << 16 |
(u64)wasm_i8x16_bitmask(ec) << 32 | (u64)wasm_i8x16_bitmask(ed) << 48;
u32 cnt = __builtin_popcountll(mm);
// Entries past cnt are garbage and are overwritten or ignored.
out[0] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[1] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[2] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[3] = base + __builtin_ctzll(mm); mm &= mm - 1;
if (UNLIKELY(cnt > 4)) {
out[4] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[5] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[6] = base + __builtin_ctzll(mm); mm &= mm - 1;
out[7] = base + __builtin_ctzll(mm); mm &= mm - 1;
for (u32 k = 8; UNLIKELY(mm); k++) {
out[k] = base + __builtin_ctzll(mm);
mm &= mm - 1;
}
}
out += cnt;
}
base += 64;
} while (base < lim);
for (const u32 *q = pos; q < out; q++) {
u32 i = *q;
// Copy the text since the last reference; src[i] is `&` and i < size.
{
u32 len = i - e;
st(dst + o, ld(src + e));
st(dst + o + 16, ld(src + e + 16));
if (len > 32) {
u32 j = 32;
do {
st(dst + o + j, ld(src + e + j));
j += 16;
} while (j < len);
}
o += len;
}
u64 w = ld64(src + i + 1);
if ((u8)w == '#') {
// Decimal and hexadecimal share one branch-free path: classify 8 bytes, take
// the digits before the first other byte, and fold them pairwise.
u32 hex = (((u32)w >> 8 & 0xFF) | 0x20) == 'x';
const u8 *p = src + i + 2 + hex;
u64 d = ld64(p);
u64 t = d ^ 0x3030303030303030ull;
u64 digit = ~(((t & ~HIGH) + 0x7676767676767676ull) | t) & HIGH;
u64 y = d | 0x2020202020202020ull, ty = y & ~HIGH;
u64 letter = (ty + ONES * (0x80 - 'a')) & ~(ty + ONES * (0x7F - 'f')) & ~y & HIGH;
u64 stop = ~(digit | (hex ? letter : 0)) & HIGH;
u32 v, end;
if (LIKELY(stop)) {
u32 nb = __builtin_ctzll(stop) & 0x38;
if (UNLIKELY(!nb)) goto bare;
u64 x = ((d & 0x0F0F0F0F0F0F0F0Full) + 9 * (letter >> 7)) << (64 - nb);
x = (x * (hex ? 16 : 10) + (x >> 8)) & 0x00FF00FF00FF00FFull;
x = (x * (hex ? 256 : 100) + (x >> 16)) & 0x0000FFFF0000FFFFull;
v = (u32)(x * (hex ? 65536 : 10000) + (x >> 32));
end = (u32)(p - src) + (nb >> 3);
} else {
// Eight or more digits: saturate past U+10FFFF.
u32 c, base = hex ? 16 : 10;
v = 0;
for (;;) {
c = *p - '0';
if (c > 9) c = ((*p | 0x20) - 'a') + 10, c = c < 10 ? 16 : c;
if (c >= base) break;
v = v * base + c;
if (v > 0x10FFFF) v = 0x110000;
p++;
}
end = (u32)(p - src);
}
i = end + (src[end] == ';');
if (UNLIKELY(v - 0x80 < 0x20)) v = c1[v - 0x80];
else if (UNLIKELY(v == 0 || v - 0xD800 < 0x800 || v > 0x10FFFF)) v = 0xFFFD;
u32 len, word = utf8(v, &len);
st32(dst + o, word);
o += len;
goto next;
}
{
u64 t = w ^ (ONES * ';');
u64 z = (t - ONES) & ~t & HIGH;
if (LIKELY(z)) {
// Bit index of the `;` byte; the key is the name and its `;`.
u32 kb = __builtin_ctzll(z) & 0x38;
u64 key = w & (((u64)2 << (kb + 7)) - 1);
const Entry *e = &fast[(key * FAST_MUL) >> (64 - FAST_BITS)];
for (;;) {
u64 k = e->key;
if (LIKELY(k == key)) {
u64 val = e->val;
st64(dst + o, val);
o += (u32)(val >> 56);
i += 2 + (kb >> 3);
goto next;
}
if (k == EMPTY) break;
e++;
}
} else {
// No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
v128_t s0 = ld(src + i + 1), s1 = ld(src + i + 17);
const v128_t semi = wasm_i8x16_splat(';');
u32 sm = wasm_i8x16_bitmask(wasm_i8x16_eq(s0, semi)) | wasm_i8x16_bitmask(wasm_i8x16_eq(s1, semi)) << 16;
if (sm) {
u32 len = __builtin_ctz(sm);
u32 h = long_hash(w, ld64(src + i + 1 + len - 8), len);
v128_t m0 = ld(len_mask + 32 - len), m1 = ld(len_mask + 48 - len);
for (u32 s; (s = long_slots[h]) != 0; h = (h + 1) & ((1 << LONG_BITS) - 1)) {
const Long *l = &longs[s - 1];
v128_t diff = wasm_v128_or(
wasm_v128_xor(wasm_v128_and(s0, m0), ld(l->name)),
wasm_v128_xor(wasm_v128_and(s1, m1), ld(l->name + 16)));
if (l->len == len && !wasm_v128_any_true(diff)) {
st64(dst + o, l->val);
o += (u32)(l->val >> 56);
i += 2 + len;
goto next;
}
}
}
}
// Without `;`, the longest legacy name that is a prefix.
for (u32 k = leg_max[leg_slot(w)]; k >= 2; k--) {
// The length is part of the key, so a NUL after a shorter name cannot match.
u64 key = (w & (((u64)1 << (8 * k)) - 1)) | (u64)k << 56;
const Entry *e = &leg[(key * LEG_MUL) >> (64 - LEG_BITS)];
for (;;) {
if (e->key == key) {
st64(dst + o, e->val);
o += (u32)(e->val >> 56);
i += 1 + k;
goto next;
}
if (e->key == EMPTY) break;
e++;
}
}
}
bare:
dst[o] = '&';
o += 1;
i += 1;
next:
e = i;
}
}
// Without a reference the input is the output.
if (e == 0) return (u64)(u32)(uintptr_t)input << 32 | size;
for (u32 j = e; j < size; j += 16) st(dst + o + (j - e), ld(src + j));
o += size - e;
return (u64)(u32)(uintptr_t)output << 32 | o;
}
/* pack.py, which produced `packed`:
"""Packs the entity list for unescape-small: entities ordered by code point, coded with an
adaptive binary range coder whose contexts are the previous one, two and three name
characters and a match model. The C unpacker in unescape-small.in.c mirrors Model and Decoder exactly.
"""
import html.entities
M32 = 0xFFFFFFFF
K = 1 << 20
HASH_A, HASH_B = 0x2545F491, 0x9E3779B1
# Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
RATE = [43690, 26214, 18724, 14563, 11915, 10082]
html5 = html.entities.html5
NAMES = {k[:-1]: v for k, v in html5.items() if k.endswith(';')}
LEGACY = {k for k in html5 if not k.endswith(';')}
ALPHA = '\0' + '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
CODE = {c: i for i, c in enumerate(ALPHA)}
ORDER = sorted(NAMES, key=lambda n: ([ord(c) for c in NAMES[n]], n))
def tdiv(a, b):
"""Division truncating toward zero, as in C."""
q = abs(a) // abs(b)
return q if (a < 0) == (b < 0) else -q
class Model:
def __init__(self, bits=16, limit=6, narrow=False):
# narrow: 16-bit entries holding a 12-bit probability and a 4-bit count,
# instead of 32-bit entries holding 16 bits of each.
self.t = [0] * (1 << bits)
self.bits, self.limit, self.narrow = bits, limit, narrow
def load(self, s):
e = self.t[s]
return ((e >> 4) ^ 0x800, e & 15) if self.narrow else ((e >> 16) ^ 0x8000, e & 0xFFFF)
def slots(self, ctxs, node):
return [(((c + node * HASH_A) * HASH_B) & M32) >> (32 - self.bits) for c in ctxs]
def predict(self, slots):
"""12-bit probability that the bit is 1."""
num = den = 0
for k, s in enumerate(slots):
p, n = self.load(s)
half, shift = (0x800, 8) if self.narrow else (0x8000, 12)
w = (n * (1 + (abs(p - half) >> shift))) << k
num += p * w
den += w
if self.narrow:
p = num // den if den else 0x800
else:
p = (num // den if den else 0x8000) >> 4
return min(max(p, 1), 4095)
def update(self, slots, bit):
for s in slots:
p, n = self.load(s)
one = 0x1000 if self.narrow else 0x10000
p += (((one if bit else 0) - p) * RATE[n]) >> 16
if n < self.limit:
n += 1
self.t[s] = (p ^ 0x800) << 4 | n if self.narrow else (p ^ 0x8000) << 16 | n
class Encoder:
def __init__(self):
self.low, self.range, self.cache, self.pending, self.out = 0, M32, 0, 1, bytearray()
def shift_low(self):
if self.low < 0xFF000000 or self.low > M32:
carry = self.low >> 32
byte = self.cache
while self.pending:
self.out.append((byte + carry) & 0xFF)
byte = 0xFF
self.pending -= 1
self.cache = self.low >> 24 & 0xFF
self.pending += 1
self.low = (self.low << 8) & M32
def bit(self, p, bit):
bound = (self.range >> 12) * p
if bit:
self.range = bound
else:
self.low += bound
self.range -= bound
while self.range < 1 << 24:
self.range = (self.range << 8) & M32
self.shift_low()
def finish(self):
for _ in range(5):
self.shift_low()
assert self.out[0] == 0
return bytes(self.out[1:])
class Decoder:
def __init__(self, data):
self.data, self.pos, self.range = data + bytes(8), 4, M32
self.code = int.from_bytes(data[:4], 'big')
def bit(self, p):
bound = (self.range >> 12) * p
if self.code < bound:
self.range = bound
bit = 1
else:
self.code -= bound
self.range -= bound
bit = 0
while self.range < 1 << 24:
self.range = (self.range << 8) & M32
self.code = (self.code << 8 | self.data[self.pos]) & M32
self.pos += 1
return bit
class Coder:
"""Runs the same field sequence for packing (values given) and unpacking (values None)."""
def __init__(self, data=None, **kw):
self.m = Model(**kw)
self.enc = Encoder() if data is None else None
self.dec = Decoder(data) if data is not None else None
self.hist, self.last = [0], [0] * 4096
def sym(self, ctxs, nbits, value=None):
node = 1
for i in range(nbits - 1, -1, -1):
slots = self.m.slots(ctxs, node)
p = self.m.predict(slots)
if self.enc:
b = value >> i & 1
self.enc.bit(p, b)
else:
b = self.dec.bit(p)
self.m.update(slots, b)
node = node * 2 + b
return node - (1 << nbits)
def entity(self, cp, rec=None):
"""rec = (name, [code points], legacy) when packing. Returns the same when unpacking."""
name, cps, legacy = rec if rec else (None, None, None)
d = cps[0] - cp if rec else None
nb = self.sym([1 * K], 5, d.bit_length() if rec else None)
if nb > 1:
d = (1 << (nb - 1)) + self.sym([2 * K + nb], nb - 1, d - (1 << (nb - 1)) if rec else None)
else:
d = nb
cp += d
second = 0
if self.sym([3 * K + (d == 0)], 1, len(cps) - 1 if rec else None):
second = self.sym([4 * K], 16, cps[1] if rec else None)
leg = self.sym([5 * K + (cp < 256)], 1, int(legacy) if rec else None)
# The match model predicts the character that followed the last place the previous
# two characters were seen, and how many predictions in a row have been right.
h, out, mp, ml = 0, '', 0, 0
for i in range(64):
ctxs = [8 * K + (h & 63), 9 * K + (h & 4095),
13 * K + (self.hist[mp] if ml else 0) * 16 + min(ml, 3), 10 * K + (h & 0x3FFFF)]
c = self.sym(ctxs, 6, CODE[(name + '\0')[i]] if rec else None)
if ml and self.hist[mp] == c:
ml += 1
mp += 1
else:
ml = 0
self.hist.append(c)
if c == 0:
break
out += ALPHA[c]
h = h << 6 | c
if i >= 1:
if ml == 0 and self.last[h & 4095]:
mp, ml = self.last[h & 4095], 1
self.last[h & 4095] = len(self.hist)
return out, [cp, second] if second else [cp], bool(leg)
def records():
return [(n, [ord(c) for c in NAMES[n]], n in LEGACY) for n in ORDER]
def pack(**kw):
c = Coder(**kw)
cp = 0
for rec in records():
assert len(rec[1]) <= 2 and rec[1][0] >= cp and (len(rec[1]) == 1 or rec[1][1] < 0x10000)
c.entity(cp, rec)
cp = rec[1][0]
return c.enc.finish()
def unpack(data, count, **kw):
c = Coder(data, **kw)
cp, out = 0, []
for _ in range(count):
rec = c.entity(cp)
cp = rec[1][0]
out.append(rec)
return out
if __name__ == '__main__':
import sys
blob = pack(bits=18, limit=5)
assert unpack(blob, len(ORDER), bits=18, limit=5) == records()
print('round trip ok', len(blob))
# This file: pack(bits=16, limit=5, narrow=True)
*/
Download source MIT licensed — build on it
Run it on the example input with qipdo (Node.js 22 or newer):
printf '%s' 'Fish & chips — café <3 😀 © 2026 ¬it;' | npx qipdo calculated.world components/f7b472378bafa3c69d5637027219dc5d1739a03e8042c65bdd7b53d60a66a358.wasmThe two-stage SIMD decoder in 7 pages of memory (448 KiB) instead of 48. The buffers hold 128 KiB of input, above the largest input in the official suite and benchmark; longer input is truncated. The entity list is packed to 6.7 KB with an adaptive binary range coder and unpacked once, on the first call, using the output buffer as its working memory, so the hot loop is the same as in the larger builds. The packer (Python) is included at the end of the source.
- Builds on
- Derived from my C submission 882dd447-827a-49f0-ab31-8581e4ec31eb. Entity list from Python's html.entities.html5 (WHATWG named character references). Range coder follows the LZMA binary coder.
Try it
Output
Step through this Wasm running on the input above. Focus the debugger, then press Space to run, N to step over or ? for all keys.
To debug it in your terminal with qiptui (Node.js 22 or newer):
First download the Wasm and the example input:
curl -o unescape_html.wasm https://calculated.world/components/f7b472378bafa3c69d5637027219dc5d1739a03e8042c65bdd7b53d60a66a358.wasm
printf '%s' 'Fish & chips — café <3 😀 © 2026 ¬it;' > input.txtThen step through it in the qipdb debugger:
npx qiptui \
-F component=@unescape_html.wasm \
-F 'input=<input.txt' \
qip.dev/tui/qipdb.wasmThe debugger command fetches qipdb from qip.dev and keeps it in memory.
Build details
Compiler, size, memory and checksum
- Submitted
- 10 November 2026 at 12:14 UTC
- Language
- C
- Compiler
-
zig cc 0.15.2 (Clang 20.1.2) + Binaryen wasm-opt 130-target wasm32-freestanding -O3 -msimd128 -mbulk-memory -nostdlib -Wl,--no-entry -Wl,--export-memory -Wl,--initial-memory=458752 -Wl,--max-memory=458752 -Wl,-z,stack-size=8192 -Wl,--strip-all; then wasm-opt -O3 --enable-simd --enable-bulk-memory - Size
- 10.6 KiB, gzip 9.2 KiB
- Download
- ~150 ms on Slow 4G (Lighthouse’s 1.6 Mbps, 150 ms round trips)
- Memory
- 7 pages (448 KiB)
- SIMD
- yes
- AI models
- claude-fable-5-2
Functions, loops, branches and other static counts
- Functions
- 7
- Instructions
- 1,868
- Loops
- 20
- Conditional branches
- 58
- Indirect calls
- 0
- Memory loads
- 43
- Memory stores
- 51
- SIMD instructions
- 52
- Potentially trapping instructions
- 122
Instruction sites in the binary, not executions, counted by qip.dev’s wasm-counts.