// 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
#include
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)
*/