Unescape HTML · Zig 🤝 Fable 5.2
SHA-256
f2b5a4fbd5c1ece6cd00f703f147220119316d5665baa09f81605c9188c6c999
View source (52.7 KiB of Zig)
// unescape_html in Zig without SIMD: decodes every HTML character reference in UTF-8 text
// the way Python's html.unescape does, and copies all other bytes unchanged.
//
// This is my SIMD entry 8aa42ef2 with every vector operation replaced by 64-bit word
// tricks (SWAR), so it runs on engines without the SIMD proposal:
// - 64 zero bytes are written after the input, so no load or loop needs a bounds check.
// - Two stages per 4 KiB window. Stage 1 reads eight 64-bit words per 64-byte block, turns
// each into 8 bits saying which bytes are `&` (an exact zero-byte test, then one multiply
// gathers the bits), and appends the positions to a list. Stage 2 walks the list: copy
// the text since the last reference (32 bytes unconditionally, more in a loop), then decode.
// - 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 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).
// - Longer names go through a second table and a masked compare of four words.
// - 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 path.
// The lookup tables are built on the first call from a 6.4 KB packed entity list: see `sym`
// and `init`.
//
// Build: zig build-exe unescape-nosimd.zig -target wasm32-freestanding -mcpu=generic+bulk_memory
// -O ReleaseSmall -fno-entry -rdynamic -fstrip --stack 8192 --initial-memory=3145728 --max-memory=3145728
const std = @import("std");
const INPUT_CAP: usize = 1 << 20;
// The largest growth is `≫⃒` (5 bytes) becoming 6 bytes.
const OUTPUT_CAP: usize = INPUT_CAP / 5 * 6 + 8;
const PAD = 128;
const FAST_BITS = 12;
const FAST_TAIL = 32;
const LEG_BITS = 8;
const LEG_TAIL = 16;
const LONG_BITS = 11;
const LONG_MASK = (1 << LONG_BITS) - 1;
const EMPTY: u64 = ~@as(u64, 0);
// Bytes of input per stage-1 window; a multiple of 64.
const WINDOW = 4096;
const ONES: u64 = 0x0101010101010101;
const HIGH: u64 = 0x8080808080808080;
const HIST_SIZE = 16130;
const ENTITY_COUNT = 2125;
const LONG_COUNT = 506;
const MODEL_BITS = 18;
const MODEL_LIMIT = 5;
const FAST_MUL: u64 = 0xa59d054b12f5b905;
const LEG_MUL: u64 = 0xf880d97d1854e551;
const LONG_MUL: u64 = 0xa0c2995f40498cb3;
const packed_list = [6403]u8{
222,225,26,230,115,49,156,154,131,111,47,238,23,226,36,124,177,10,212,147,22,18,106,98,
241,187,81,150,70,136,101,195,190,175,200,2,57,117,22,148,223,133,247,1,245,48,136,172,
158,15,4,210,106,239,138,145,213,20,255,183,153,220,207,159,81,179,120,249,67,103,45,186,
228,41,141,81,68,72,134,73,171,69,89,215,127,31,238,76,105,165,14,71,15,83,190,11,
179,202,70,217,98,226,211,59,6,154,27,161,3,30,215,225,31,79,105,226,225,101,231,23,
126,218,5,122,115,112,183,106,16,225,249,158,254,18,66,33,44,164,43,105,30,218,134,122,
132,224,196,61,77,183,23,150,12,198,174,224,95,10,79,232,121,7,21,239,253,74,129,242,
2,2,234,68,129,166,142,221,231,78,159,122,25,9,144,134,78,244,133,68,252,243,3,247,
240,160,184,129,69,207,235,151,174,249,167,243,37,254,194,192,4,244,9,68,130,225,99,254,
104,94,148,68,28,174,40,131,152,3,122,2,107,172,118,196,132,57,193,251,229,105,255,201,
57,57,231,201,148,138,220,68,100,136,102,210,11,156,44,215,46,126,30,129,72,77,100,16,
183,161,78,137,146,235,152,103,141,191,160,54,218,130,140,173,134,232,234,117,57,233,148,206,
223,240,159,49,248,77,84,188,46,94,219,119,240,15,180,221,185,227,36,2,39,13,127,186,
209,29,56,136,29,97,253,246,227,90,141,246,91,164,239,112,26,123,99,191,245,131,222,30,
125,246,39,217,164,130,160,224,55,82,138,76,104,238,115,48,249,48,159,236,232,224,145,184,
105,220,174,41,100,221,70,90,46,155,111,40,205,184,36,2,46,98,140,195,99,61,129,239,
22,9,45,87,178,95,175,255,134,126,142,178,50,110,151,79,130,148,123,230,51,143,48,116,
182,160,142,202,207,55,247,226,92,110,112,142,246,105,245,108,191,22,93,56,168,68,31,99,
114,232,136,24,80,208,76,246,101,6,224,23,43,156,155,121,35,60,215,104,82,68,140,149,
179,204,134,167,45,172,118,141,245,13,31,202,88,208,27,192,218,162,176,47,237,164,82,127,
116,112,149,57,89,70,89,208,3,79,207,118,73,35,67,88,72,158,118,2,69,140,128,110,
208,198,82,92,146,143,204,204,192,191,157,249,6,200,33,79,166,45,35,4,183,200,219,41,
174,113,171,62,60,249,222,97,112,89,162,90,59,195,229,121,140,156,117,157,221,99,166,89,
160,15,144,135,176,30,90,129,191,167,0,251,12,235,111,124,205,93,87,77,251,67,205,27,
146,120,173,224,115,65,54,92,200,86,87,26,15,146,127,240,124,97,121,84,164,17,110,201,
54,25,122,222,98,190,248,86,237,220,57,214,75,24,128,107,119,184,118,242,235,154,61,36,
236,216,153,24,89,233,81,21,15,72,123,2,94,201,60,80,21,172,111,220,119,95,250,131,
77,77,38,68,105,129,175,116,7,111,62,95,221,60,2,109,35,17,124,216,59,72,94,28,
119,251,193,132,48,99,105,54,222,197,219,151,252,93,102,162,246,1,126,250,9,34,132,37,
97,171,220,174,50,68,108,24,212,14,15,16,214,83,177,54,254,109,47,161,98,122,187,249,
20,193,250,77,89,95,173,189,26,57,225,211,153,227,179,181,53,216,89,142,117,14,63,29,
40,6,93,19,209,165,217,13,8,49,15,49,137,209,150,81,232,98,66,65,122,105,0,137,
167,12,103,188,200,158,245,141,218,220,124,198,64,41,33,9,177,73,71,133,11,227,136,209,
165,166,91,233,246,172,81,190,153,122,129,125,47,222,159,61,52,222,105,251,203,246,222,239,
136,76,92,164,208,60,139,254,110,183,151,223,231,69,245,146,59,241,57,85,162,119,219,124,
239,224,191,27,90,141,40,24,98,182,8,249,50,163,73,182,165,102,109,223,91,83,78,190,
253,230,192,138,239,138,174,31,96,125,207,175,70,235,65,249,232,206,190,68,157,52,138,141,
76,240,97,113,31,139,107,161,117,245,72,68,222,225,240,158,123,92,0,183,159,126,234,235,
26,245,77,59,70,128,152,110,18,0,123,38,124,78,10,84,118,22,0,148,222,112,218,182,
28,168,95,254,108,132,27,8,23,92,63,157,124,151,255,232,60,157,97,72,63,176,191,49,
113,34,147,151,161,108,144,30,98,219,141,186,33,247,70,2,216,174,58,26,145,35,36,167,
163,131,39,251,169,3,150,255,176,68,55,70,182,91,48,141,150,155,130,240,17,178,151,133,
227,232,65,99,196,227,130,254,99,31,171,209,140,104,186,89,22,217,159,52,227,28,192,2,
141,43,142,147,89,251,173,217,224,216,177,170,27,94,184,188,69,167,105,197,154,2,125,125,
251,207,246,147,83,36,87,64,18,140,172,69,49,84,115,150,16,31,58,202,178,248,98,42,
159,211,204,252,41,26,81,111,164,139,31,229,99,174,15,144,139,26,134,129,211,21,77,37,
173,14,2,179,62,109,80,171,236,177,50,250,69,179,238,118,180,175,49,138,194,14,132,66,
107,132,217,20,204,169,212,65,156,222,231,102,122,210,225,115,148,44,157,148,119,17,64,197,
21,159,230,103,131,174,31,0,123,165,247,62,81,7,170,211,132,122,76,147,107,217,200,111,
126,49,147,169,43,91,169,186,71,9,62,233,119,226,12,63,222,2,64,49,229,4,153,16,
223,115,198,216,120,181,229,228,11,231,244,178,50,150,77,10,132,214,241,79,24,25,180,31,
34,178,205,223,33,172,39,72,40,96,196,151,84,59,247,195,90,58,233,241,22,145,247,233,
175,22,178,151,166,177,141,170,162,221,192,23,33,57,203,238,73,102,49,108,99,2,222,151,
89,52,71,77,91,176,161,48,203,133,19,157,40,72,218,122,124,148,221,114,160,19,1,221,
229,46,3,63,243,26,201,119,52,79,78,119,84,152,222,166,92,155,104,16,117,203,36,218,
148,238,218,125,148,212,213,64,204,188,255,85,103,20,250,45,86,208,50,129,53,171,229,120,
202,224,165,90,110,168,200,149,224,147,12,89,64,151,116,217,78,52,86,193,126,59,255,172,
93,64,89,117,50,207,188,160,214,199,182,53,129,208,170,101,5,70,153,100,48,199,158,113,
124,163,248,87,95,226,234,40,111,169,85,60,233,125,62,64,106,235,164,88,215,175,35,160,
62,203,99,250,246,165,237,164,224,6,76,111,131,182,232,69,86,202,161,195,67,203,96,32,
207,102,3,116,102,250,236,106,205,107,171,209,132,189,241,185,158,156,208,184,73,94,55,126,
234,51,211,55,221,41,3,27,187,227,77,26,51,245,17,211,31,82,107,73,156,16,23,17,
184,3,188,33,218,15,196,255,181,11,76,221,36,102,59,5,55,191,242,141,233,217,159,51,
21,163,184,221,106,244,41,90,20,14,21,71,217,128,127,48,251,4,204,34,95,175,228,170,
188,221,241,184,179,22,130,160,159,9,199,14,222,101,79,111,20,226,238,196,172,191,14,246,
98,52,91,104,193,3,209,43,200,1,1,166,98,86,49,133,165,4,117,30,68,184,189,204,
234,148,230,154,191,48,61,251,105,176,254,236,72,38,55,223,216,119,83,121,67,34,249,251,
225,160,202,248,25,106,63,168,157,222,40,90,121,138,234,62,129,163,220,46,107,146,232,217,
8,244,186,230,28,76,149,143,88,181,195,40,49,241,45,111,13,78,188,108,226,237,177,18,
15,28,1,192,25,163,65,51,76,26,102,254,171,68,40,153,125,172,161,170,86,98,252,20,
187,173,222,198,50,233,119,158,229,226,218,229,162,169,95,181,113,92,75,10,165,61,226,195,
119,11,217,243,162,114,30,167,82,236,121,173,107,127,200,197,111,39,21,181,211,25,127,40,
44,203,196,207,154,63,141,143,49,53,28,223,103,163,3,38,227,220,63,188,184,189,36,255,
173,213,221,42,183,20,101,80,33,141,150,22,225,244,127,149,39,139,123,109,187,41,1,236,
50,225,171,130,27,91,41,88,210,24,176,234,244,192,144,254,145,165,122,186,69,186,61,174,
216,94,39,211,4,149,189,181,19,32,212,95,52,194,107,202,20,210,54,11,62,88,192,186,
119,105,200,20,170,110,141,181,143,235,186,206,253,100,27,89,6,226,107,45,36,60,112,79,
194,117,254,108,253,130,50,145,72,4,144,97,181,169,25,182,212,107,177,71,79,79,135,146,
182,98,143,9,78,235,9,10,135,0,175,195,195,152,62,186,136,81,39,155,40,232,70,175,
150,124,232,33,161,17,216,212,193,255,23,226,223,81,12,0,245,222,60,119,93,44,115,160,
128,254,144,41,152,218,237,211,158,191,154,218,199,249,54,36,201,143,141,171,11,121,71,25,
189,193,214,167,201,84,92,114,203,202,131,24,18,112,165,173,237,82,17,186,129,142,129,174,
50,111,55,86,169,100,172,176,127,179,120,89,224,230,92,171,4,100,110,125,237,175,233,80,
28,164,85,221,42,25,189,70,165,227,100,64,83,245,177,101,98,34,96,146,251,131,148,251,
199,73,40,251,57,126,86,53,10,114,250,35,85,49,168,215,197,145,101,95,135,152,249,201,
30,82,86,29,122,53,115,95,29,204,247,78,17,120,102,82,69,112,151,78,182,228,102,69,
192,21,159,219,155,42,26,175,221,161,225,136,175,219,115,121,151,11,83,142,158,182,206,236,
79,188,192,72,198,57,53,250,169,187,77,116,113,166,50,111,165,225,22,25,166,54,77,129,
19,194,179,186,138,41,77,181,166,58,94,4,205,221,111,156,121,247,227,69,97,194,1,5,
166,94,38,177,125,86,247,188,181,92,117,182,164,206,5,112,202,26,123,111,113,117,231,159,
117,78,113,164,135,179,168,43,138,79,159,152,48,21,184,247,215,42,115,50,193,40,243,82,
175,95,236,139,209,167,98,154,115,202,217,242,130,100,144,209,14,161,208,86,230,95,79,0,
66,74,212,132,63,97,12,22,122,176,170,33,175,24,145,166,18,144,166,202,63,86,64,214,
58,62,212,46,230,1,188,136,86,89,144,184,34,83,149,2,81,255,194,78,58,29,86,150,
155,216,225,10,181,185,85,169,221,68,217,208,123,31,37,96,183,231,72,164,247,118,19,124,
230,49,61,24,145,208,93,237,51,162,20,93,23,243,160,205,223,252,167,78,240,65,134,10,
114,157,0,84,148,183,15,248,213,233,203,116,24,144,119,164,156,4,120,171,28,165,107,27,
51,169,98,145,169,175,99,103,85,174,18,116,213,131,245,225,211,195,223,110,59,128,241,125,
71,211,192,141,220,157,229,171,202,52,61,68,194,109,46,23,135,166,68,122,11,200,247,101,
226,15,108,250,248,49,23,227,108,225,98,220,124,14,141,111,239,43,221,186,250,205,237,92,
251,126,117,154,97,48,85,84,68,188,235,128,47,156,112,173,6,211,81,165,152,121,220,18,
101,76,208,92,71,180,70,48,238,165,223,121,140,149,206,132,80,30,167,166,147,216,148,37,
184,182,120,199,162,161,207,94,228,194,219,31,125,237,143,132,167,165,148,185,195,245,140,178,
154,72,119,252,15,129,89,52,245,243,209,196,190,25,91,191,254,104,54,125,206,88,173,207,
72,33,22,27,113,196,176,44,216,148,70,65,240,6,74,150,169,103,229,23,102,52,180,150,
15,173,202,186,125,114,179,81,120,63,181,221,113,255,126,180,73,251,44,67,220,40,239,38,
236,47,210,61,165,218,67,222,242,193,140,215,29,27,69,105,124,203,243,174,194,192,169,156,
40,54,222,217,95,128,58,196,138,88,25,159,182,150,252,243,9,89,111,97,116,80,76,139,
126,153,90,15,114,173,158,32,106,232,118,32,87,46,47,68,107,157,91,64,44,88,247,246,
12,205,34,139,58,221,187,31,34,205,67,172,97,98,97,41,187,197,73,246,122,62,21,226,
246,153,69,12,156,136,27,26,181,182,91,237,47,57,8,210,184,219,59,43,228,83,46,103,
127,219,169,59,173,240,119,106,6,55,217,105,223,8,224,152,127,129,64,48,34,142,203,18,
168,17,248,173,38,126,63,143,215,53,195,29,201,124,22,234,88,214,219,161,8,105,183,172,
80,54,188,90,250,23,98,37,93,195,59,220,153,67,51,187,119,234,189,66,10,173,252,121,
226,64,217,179,91,118,228,90,51,165,141,182,201,10,201,15,28,178,128,93,195,183,248,252,
238,232,250,38,80,151,17,201,245,215,93,251,122,190,106,221,30,169,144,104,31,236,186,126,
205,35,50,12,100,250,188,78,136,77,148,193,39,168,238,196,110,28,224,5,97,178,198,15,
134,195,65,0,236,207,246,137,30,11,102,141,159,21,73,184,142,36,126,190,27,12,172,247,
207,157,162,48,159,237,195,185,231,41,22,177,116,216,234,33,231,45,186,214,194,60,183,65,
176,66,141,74,42,51,53,153,229,236,241,218,127,177,7,164,203,123,74,112,26,189,176,246,
55,91,134,29,248,118,247,215,182,127,19,208,168,80,37,89,33,55,203,117,30,168,169,36,
71,156,68,159,116,66,204,122,210,118,222,216,163,249,43,16,37,254,124,172,95,156,70,160,
114,167,32,27,6,94,209,166,118,191,119,0,228,7,222,56,232,117,184,39,163,164,98,34,
153,227,51,26,11,130,11,127,64,219,217,86,174,167,169,218,9,147,112,137,198,96,228,47,
136,147,225,107,5,186,47,150,6,71,132,235,196,79,117,201,192,108,93,106,22,5,146,87,
112,74,32,92,122,171,204,246,172,152,74,69,159,35,93,127,29,219,251,190,63,44,101,243,
89,65,64,28,194,120,189,30,51,56,249,109,99,25,145,156,188,74,67,122,157,127,34,136,
137,249,146,81,235,98,138,154,250,42,16,49,150,253,237,162,53,251,175,213,184,225,229,35,
32,255,251,53,141,207,164,216,152,225,210,196,54,113,24,105,36,61,165,131,241,47,11,144,
132,216,225,39,72,243,95,132,214,46,179,192,134,218,61,184,59,215,92,108,184,131,107,104,
24,71,27,214,196,114,86,178,188,46,145,211,115,43,6,212,135,105,36,146,87,97,237,176,
160,219,26,34,223,67,186,144,176,172,0,75,205,180,216,151,132,138,96,23,40,102,45,154,
219,124,188,153,23,20,162,139,205,143,136,145,184,191,188,102,239,119,68,18,84,233,16,40,
186,140,106,5,150,55,210,170,123,200,120,118,163,40,2,15,248,231,252,195,84,108,94,22,
101,72,200,177,119,180,21,210,113,127,233,187,124,110,183,173,229,107,3,170,140,246,27,27,
51,41,198,157,79,184,35,252,127,149,200,192,8,77,110,219,223,77,59,228,22,38,211,164,
205,148,214,239,69,137,151,162,24,215,153,247,119,91,95,86,191,179,28,180,174,219,151,220,
204,6,84,118,177,109,96,65,243,227,18,92,125,5,6,123,150,179,157,4,55,97,203,192,
133,242,200,209,168,14,101,165,188,218,119,152,144,10,18,196,92,133,210,134,188,231,90,74,
60,156,15,99,30,45,71,231,81,185,131,96,47,157,121,177,31,114,120,242,163,41,223,136,
110,150,115,13,79,148,85,55,187,96,3,79,182,255,184,125,106,162,241,91,148,38,213,175,
53,175,101,253,135,157,59,240,20,171,87,122,99,114,47,159,188,101,105,206,92,139,124,154,
5,146,171,190,108,206,152,182,153,212,169,228,100,189,143,203,179,118,69,139,137,229,131,18,
137,81,228,55,84,147,237,142,245,141,29,109,122,79,197,43,51,153,77,5,48,89,50,214,
22,56,189,110,178,15,108,118,168,131,67,224,57,128,16,183,6,6,81,0,24,234,149,21,
187,111,220,122,104,1,208,106,56,10,248,46,55,40,18,137,248,199,182,200,246,181,184,26,
119,243,59,21,214,241,142,205,97,145,80,94,27,233,127,163,201,196,159,142,132,61,60,200,
151,199,1,26,76,116,27,201,231,211,32,74,223,23,33,162,117,170,21,43,77,124,211,102,
95,187,204,59,46,181,249,93,92,40,193,53,143,239,157,29,130,144,5,24,113,88,202,106,
107,236,199,139,124,51,178,70,94,212,66,81,23,114,131,86,195,12,154,222,158,225,37,177,
196,51,244,247,64,129,120,176,90,183,239,147,49,130,105,118,160,107,23,238,254,169,214,245,
56,95,103,174,135,170,113,145,252,122,67,222,254,130,123,131,26,15,144,173,120,220,98,132,
113,70,210,231,131,160,248,50,101,15,58,82,203,158,159,64,207,218,12,55,213,197,139,207,
125,194,209,77,49,66,10,133,143,5,75,52,174,4,131,145,103,20,146,62,20,108,33,202,
229,152,232,134,76,23,255,84,24,183,90,196,239,49,254,7,116,100,153,241,99,220,167,116,
144,81,81,194,166,66,161,190,255,240,171,160,137,95,188,63,200,212,112,250,255,221,46,97,
28,97,163,129,124,22,51,194,134,25,21,137,57,47,212,56,57,90,98,104,160,112,59,13,
197,249,190,255,221,157,89,191,19,48,124,179,226,4,189,87,162,217,33,94,239,210,100,22,
38,249,215,124,115,6,15,40,169,37,88,146,210,182,11,217,59,158,155,55,12,44,198,82,
55,234,150,139,188,218,3,137,92,151,183,214,116,220,9,110,190,39,142,115,236,0,71,136,
248,221,36,171,242,252,51,150,203,98,21,53,197,224,203,247,177,113,84,89,134,118,177,125,
28,251,193,8,87,101,141,62,221,10,149,229,86,83,154,74,158,157,221,64,141,140,238,249,
120,65,9,212,103,35,35,33,118,66,117,77,71,55,168,6,77,195,219,33,156,226,125,178,
203,202,113,163,40,69,161,106,226,251,113,165,227,81,85,68,141,52,120,144,35,48,211,90,
24,184,100,255,226,11,72,28,185,104,233,140,80,114,176,86,209,126,80,144,214,65,225,241,
129,113,92,179,164,17,100,249,102,0,136,235,51,106,178,32,188,80,37,197,152,160,108,185,
203,27,204,98,99,61,203,88,98,141,55,55,154,183,209,123,111,18,236,123,82,36,225,103,
18,217,164,159,122,168,145,75,126,114,251,243,4,99,68,188,82,18,150,39,153,252,72,53,
219,193,125,36,216,254,62,202,159,72,94,245,6,153,179,195,174,111,175,63,85,89,221,140,
123,67,178,53,36,116,120,180,34,127,63,96,31,30,75,3,14,189,247,149,224,9,57,223,
162,211,225,168,244,141,143,81,174,51,118,102,61,239,85,232,163,61,80,106,86,111,21,5,
153,87,132,54,202,116,136,19,43,45,25,237,93,123,147,92,44,194,41,88,239,124,201,213,
101,198,215,99,194,130,10,234,24,196,16,162,131,200,230,82,192,94,226,157,172,201,202,130,
193,219,193,85,253,96,182,220,136,37,95,127,165,32,54,84,20,77,185,116,189,164,121,84,
228,200,15,179,15,242,20,37,113,167,150,31,45,45,223,213,33,238,113,133,128,117,65,231,
76,212,86,43,113,252,10,66,221,163,32,128,229,119,58,95,132,69,150,113,254,48,6,144,
5,125,56,144,81,226,192,237,154,74,214,211,111,152,235,174,21,14,239,17,192,141,147,119,
9,136,224,214,8,178,19,245,161,232,121,244,3,196,220,13,41,189,17,250,71,255,27,232,
65,92,160,51,165,187,142,38,249,27,184,94,239,237,133,180,29,215,226,193,236,55,66,107,
165,93,135,9,214,243,80,162,159,78,140,195,102,135,52,108,84,80,139,179,138,50,225,68,
248,92,80,13,1,77,148,215,179,196,101,208,38,39,244,236,219,159,96,194,68,254,103,251,
227,163,58,88,15,130,172,133,147,72,81,202,126,159,153,97,135,25,238,155,191,143,103,255,
186,96,122,83,63,178,202,251,233,140,59,93,71,235,87,161,221,46,45,57,211,41,57,169,
157,214,175,214,202,188,116,21,238,199,61,70,221,120,1,243,5,186,100,149,217,169,246,165,
226,215,175,2,91,158,109,170,162,206,226,206,182,173,156,82,169,170,105,42,124,57,134,92,
131,13,3,247,177,49,86,171,50,68,17,37,123,80,32,164,28,198,140,103,171,220,28,225,
9,191,234,150,213,184,29,115,160,50,218,90,200,130,146,252,182,190,124,248,255,61,96,62,
231,183,21,246,143,127,225,39,94,61,92,67,60,216,90,108,211,162,26,47,105,254,244,132,
207,30,15,71,22,16,169,138,150,48,51,124,171,112,165,245,239,21,119,53,208,110,31,25,
142,63,192,24,222,103,97,107,228,105,45,130,207,80,124,4,134,182,109,170,160,95,251,72,
53,81,248,19,92,181,73,148,27,146,183,224,23,93,216,233,81,116,30,182,38,28,100,253,
156,110,192,151,30,171,44,134,233,190,205,159,116,69,20,203,236,56,115,112,23,160,128,116,
80,63,178,190,44,42,81,101,8,20,80,234,55,154,19,89,247,134,87,155,9,68,187,121,
182,27,120,223,159,207,77,25,7,153,106,196,194,0,42,140,10,85,6,90,89,162,72,6,
156,119,251,56,213,113,109,83,233,165,35,38,192,242,44,165,79,47,89,208,112,175,171,195,
72,206,179,214,155,16,132,11,28,22,235,188,240,178,31,58,28,197,120,102,110,38,193,42,
42,28,68,44,89,224,146,193,227,201,247,36,245,227,201,162,69,76,141,37,55,216,176,247,
28,169,178,67,138,20,153,8,186,151,195,176,38,228,101,143,5,32,137,57,11,156,133,25,
139,85,146,226,191,235,105,17,217,9,173,143,16,71,155,22,251,185,177,169,2,104,155,91,
72,22,73,206,87,171,79,132,186,45,45,196,16,198,10,96,158,211,236,57,166,102,208,76,
128,207,188,31,116,204,225,212,144,61,62,92,142,77,211,137,226,179,184,234,96,1,24,247,
223,106,201,152,236,204,59,234,190,94,224,204,230,166,7,28,141,193,103,37,40,127,187,191,
55,215,206,85,253,218,215,251,7,38,233,140,64,113,240,109,210,187,11,106,252,211,201,47,
39,246,65,199,122,39,11,146,185,128,69,135,99,222,153,155,149,208,161,34,81,159,94,192,
43,107,59,119,119,232,152,213,113,140,221,153,206,64,17,60,210,202,118,31,55,145,184,145,
21,243,39,109,162,107,181,73,204,115,81,175,142,58,43,215,113,254,185,121,199,160,40,56,
219,219,129,55,184,27,98,115,96,167,77,230,145,206,51,194,48,5,224,194,72,123,69,233,
63,197,236,61,102,209,255,134,134,139,16,17,76,184,146,241,138,48,246,26,153,36,60,135,
166,11,200,132,138,152,186,47,114,230,237,77,76,51,124,75,51,55,228,239,48,218,202,141,
37,24,30,180,127,154,246,130,204,15,132,248,80,156,92,239,199,133,186,33,22,36,184,98,
209,69,165,95,33,216,34,222,12,109,46,99,81,24,253,226,205,89,159,128,62,211,132,246,
84,9,144,51,199,230,39,213,234,117,98,214,127,10,93,207,240,79,29,174,197,206,194,177,
229,96,229,255,123,145,200,34,82,128,34,240,24,79,83,217,29,189,88,241,133,56,0,155,
163,251,100,209,114,185,140,233,140,169,169,246,40,102,230,118,217,110,95,73,16,157,102,12,
225,141,171,248,5,61,219,17,14,2,48,204,149,26,100,200,93,169,253,143,68,201,234,130,
29,249,253,50,99,102,126,150,35,115,73,54,111,87,171,30,43,53,208,52,129,45,123,124,
178,44,216,100,176,44,122,94,163,239,139,226,166,85,198,53,143,1,249,152,125,78,78,96,
131,54,233,19,174,114,34,71,108,50,4,45,246,215,75,3,171,145,138,65,160,117,156,26,
136,220,145,112,64,201,18,46,217,253,119,3,254,191,47,188,83,99,220,62,201,229,119,69,
10,28,22,3,225,12,166,179,148,161,182,109,130,140,157,166,17,109,175,118,34,117,0,184,
85,154,143,160,70,73,52,128,65,159,213,65,118,248,202,134,113,229,28,57,212,15,133,102,
23,0,24,149,9,166,175,116,219,123,1,25,8,129,49,205,195,167,37,81,192,103,214,36,
160,226,126,182,177,96,108,94,24,27,70,67,127,151,56,59,93,44,172,161,19,162,24,77,
206,140,141,10,45,68,208,105,161,216,179,46,209,131,74,83,34,225,39,128,73,59,66,99,
24,194,107,180,245,60,75,165,113,132,151,201,102,202,250,71,47,121,62,7,182,184,82,60,
77,122,75,158,98,164,146,190,0,240,216,66,164,42,73,110,252,175,216,208,35,236,156,129,
127,120,128,38,54,208,127,230,86,80,69,158,211,255,171,183,205,16,119,140,245,62,99,80,
1,222,7,179,16,3,160,4,30,36,12,16,119,216,195,84,169,159,8,253,180,33,98,53,
35,129,43,121,199,83,7,28,113,95,30,3,183,216,232,174,174,216,144,66,225,203,248,123,
196,168,191,190,127,154,16,74,99,231,238,72,136,38,172,113,199,102,84,3,162,112,191,69,
75,89,40,74,164,42,222,121,150,247,27,82,135,39,29,80,56,220,97,249,89,105,147,209,
78,7,177,88,76,9,255,40,26,207,14,29,173,146,211,63,64,235,124,183,133,59,73,50,
116,187,64,165,113,184,49,192,49,241,139,240,72,248,113,37,232,89,16,179,210,249,152,240,
28,151,65,177,37,45,181,9,183,97,205,233,205,176,25,60,156,133,14,127,212,218,47,42,
26,202,63,35,157,52,155,114,67,143,94,11,139,217,89,61,18,228,34,250,4,150,136,187,
89,29,82,69,203,2,215,123,26,98,47,177,5,36,17,23,220,107,236,38,147,65,118,117,
101,18,249,78,9,238,103,163,78,80,52,68,185,21,114,183,208,192,162,67,182,179,128,117,
98,61,37,246,127,114,29,207,11,132,88,228,118,237,18,143,120,193,46,200,107,49,168,108,
0,77,193,107,7,184,110,105,34,61,92,140,218,17,42,226,136,188,62,126,197,150,237,81,
197,224,217,229,238,178,203,205,39,214,66,69,225,193,207,148,155,50,145,109,102,131,131,200,
149,232,68,153,209,61,12,146,176,45,181,234,131,75,81,59,57,152,229,81,76,113,96,231,
248,235,167,173,150,231,211,34,255,241,141,138,90,120,142,140,149,60,40,110,135,244,120,227,
252,168,192,69,172,66,25,238,20,37,80,74,234,218,239,35,228,131,91,223,179,179,202,245,
119,7,61,20,107,225,89,148,150,86,215,211,240,186,33,251,135,181,233,154,32,113,133,227,
24,52,2,205,85,111,124,224,165,138,152,239,99,120,122,132,222,109,20,134,183,77,40,168,
169,13,196,80,61,193,241,90,236,236,253,237,27,48,115,74,117,110,189,199,150,65,103,146,
41,137,231,33,81,148,148,55,198,93,101,187,179,185,93,164,24,88,64,114,184,51,82,57,
81,51,110,10,56,82,160,74,40,181,74,139,52,135,43,40,236,39,230,193,177,220,79,96,
29,126,21,2,5,234,5,197,134,64,49,62,32,141,56,23,41,93,113,84,7,159,137,255,
210,103,160,191,255,203,64,234,199,198,224,92,189,236,241,107,55,59,234,128,229,82,243,199,
37,81,159,20,136,169,63,146,233,80,178,241,219,251,37,216,223,202,227,113,159,112,189,91,
38,143,116,120,196,32,26,204,89,149,7,246,57,216,163,247,173,111,42,123,0,217,210,159,
99,63,33,136,159,34,215,19,98,2,141,160,246,8,184,226,93,47,66,111,58,155,138,37,
52,31,167,231,50,91,117,138,220,73,159,164,103,78,239,115,254,208,121,53,172,20,54,34,
220,32,44,182,243,59,29,38,153,218,195,23,224,148,33,236,120,173,117,78,156,125,186,37,
91,245,64,232,77,241,8,23,42,120,147,232,232,210,227,184,130,57,201,113,35,196,95,55,
132,127,11,4,147,254,13,244,17,104,135,239,93,175,157,22,213,184,15,201,67,34,44,181,
191,208,142,141,208,30,12,188,191,39,58,10,173,9,146,10,195,113,121,39,7,156,113,4,
176,203,205,40,214,188,150,191,145,247,63,219,132,225,208,48,86,196,40,255,46,232,138,150,
119,189,134,124,32,85,129,71,155,79,236,143,203,220,243,14,20,101,97,10,177,223,188,90,
113,202,34,188,11,253,34,78,60,1,196,133,60,204,142,188,151,196,8,132,214,136,214,52,
121,77,164,124,179,133,205,136,6,67,196,100,200,221,139,128,132,1,229,195,227,89,1,187,
81,35,70,61,230,188,50,11,42,219,98,222,126,129,37,80,200,5,113,134,62,7,101,182,
223,98,66,198,158,108,48,99,25,54,220,114,220,222,21,80,145,52,103,27,72,247,248,167,
103,48,151,148,231,63,76,48,141,181,212,24,238,67,28,191,45,124,30,231,216,87,113,118,
189,5,229,136,85,222,57,41,197,57,174,245,41,66,241,35,226,205,193,15,71,253,67,228,
202,93,20,90,194,43,150,173,136,136,39,11,53,157,238,84,129,131,125,
};
// The value's UTF-8 bytes in the low bytes and its length in the top byte.
const Entry = extern struct { key: u64, val: u64 };
const Long = extern struct { name: [32]u8, val: u64, len: u32, pad: u32 };
var input: [INPUT_CAP + PAD]u8 align(64) = undefined;
// Zeroed, because the packed list's model is built here on the first call.
var output align(64) = [_]u8{0} ** (OUTPUT_CAP + PAD);
var fast: [(1 << FAST_BITS) + FAST_TAIL]Entry = undefined;
var leg: [(1 << LEG_BITS) + LEG_TAIL]Entry = undefined;
var longs: [LONG_COUNT]Long align(64) = std.mem.zeroes([LONG_COUNT]Long);
var long_slots = [_]u16{0} ** (1 << LONG_BITS);
// Longest legacy name starting with these two bytes (hashed), or 0.
var leg_max = [_]u8{0} ** 4096;
var pos: [WINDOW + 16]u32 = undefined;
var ready: bool = false;
// Windows-1252 remapping for references to 0x80-0x9F.
const c1 = [32]u16{
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,
};
const utf8_marks = [5]u32{ 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.
var len_mask align(64) = [_]u8{0} ** 64;
inline fn ld64(p: [*]const u8) u64 {
return @as(*align(1) const u64, @ptrCast(p)).*;
}
inline fn st64(p: [*]u8, x: u64) void {
@as(*align(1) u64, @ptrCast(p)).* = x;
}
inline fn st32(p: [*]u8, x: u32) void {
@as(*align(1) u32, @ptrCast(p)).* = x;
}
// Copies 16 bytes as two words.
inline fn cp16(d: [*]u8, s: [*]const u8) void {
const a = ld64(s);
const b = ld64(s + 8);
st64(d, a);
st64(d + 8, b);
}
// 0x80 in each byte of x that is zero. Exact: no carry crosses a byte.
inline fn zeros(x: u64) u64 {
return ~(((x & ~HIGH) +% ~HIGH) | x) & HIGH;
}
// One bit per byte of the word at p that equals c, lowest byte first.
inline fn mask8(p: [*]const u8, c: u8) u64 {
return ((zeros(ld64(p) ^ (ONES * @as(u64, c))) >> 7) *% 0x0102040810204080) >> 56;
}
inline fn legSlot(w: u64) usize {
return ((@as(u32, @truncate(w)) & 0xFFFF) *% 0x9E3779B1) >> 20;
}
inline fn longHash(head: u64, tail: u64, n: usize) usize {
return @intCast((((head ^ std.math.rotl(u64, tail, 29)) +% n) *% LONG_MUL) >> (64 - LONG_BITS));
}
// 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 16-bit probability (stored XOR 0x8000, so zeroed memory means one
// half) and a count of how often it was used. The model lives in the output buffer, which
// is free until the first reference is decoded.
const K: u32 = 1 << 20;
// Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
const rate = [6]u16{ 43690, 26214, 18724, 14563, 11915, 10082 };
var rc_in: [*]const u8 = &packed_list;
var rc_range: u32 = 0xFFFFFFFF;
var rc_code: u32 = 0;
var hist = [_]u8{0} ** HIST_SIZE;
var last = [_]u16{0} ** 4096;
noinline fn sym(ctx: []const u32, nbits: u32) u32 {
@branchHint(.cold);
const model: [*]u32 = @ptrCast(@alignCast(&output));
const top = @as(u32, 1) << @intCast(nbits);
var node: u32 = 1;
while (node < top) {
var slot: [4]*u32 = undefined;
var num: u32 = 0;
var den: u32 = 0;
for (ctx, 0..) |c, k| {
const s = &model[((c +% node *% 0x2545F491) *% 0x9E3779B1) >> (32 - MODEL_BITS)];
slot[k] = s;
const p = (s.* >> 16) ^ 0x8000;
const a = if (p >= 0x8000) p - 0x8000 else 0x8000 - p;
// Weigh a context by its order, how often it was seen and how sure it is.
const w = ((s.* & 0xFFFF) * (1 + (a >> 12))) << @intCast(k);
num +%= p *% w;
den +%= w;
}
var p = (if (den != 0) num / den else 0x8000) >> 4;
if (p == 0) p = 1;
const bound = (rc_range >> 12) *% p;
const bit: u32 = @intFromBool(rc_code < bound);
if (bit != 0) {
rc_range = bound;
} else {
rc_code -%= bound;
rc_range -%= bound;
}
while (rc_range < 1 << 24) {
rc_range <<= 8;
rc_code = (rc_code << 8) | rc_in[0];
rc_in += 1;
}
for (slot[0..ctx.len]) |s| {
var q: i32 = @intCast((s.* >> 16) ^ 0x8000);
var n = s.* & 0xFFFF;
q += (((@as(i32, @intCast(bit)) << 16) - q) * @as(i32, rate[n])) >> 16;
if (n < MODEL_LIMIT) n += 1;
s.* = ((@as(u32, @intCast(q)) ^ 0x8000) << 16) | n;
}
node = node * 2 + bit;
}
return node - top;
}
// A code point as UTF-8 bytes in a word, low byte first.
noinline fn utf8(v: u32, len: *u32) u32 {
@branchHint(.cold);
const n: u32 = 1 + @as(u32, @intFromBool(v > 0x7F)) + @intFromBool(v > 0x7FF) + @intFromBool(v > 0xFFFF);
const bits = (v >> 18) | (((v >> 12) & 0x3F) << 8) | (((v >> 6) & 0x3F) << 16) | ((v & 0x3F) << 24);
len.* = n;
return if (n == 1) v else (bits >> @intCast(32 - 8 * n)) | utf8_marks[n];
}
noinline fn init() void {
@branchHint(.cold);
@memset(std.mem.asBytes(&fast), 0xFF);
@memset(std.mem.asBytes(&leg), 0xFF);
@memset(len_mask[0..32], 0xFF);
rc_code = std.mem.readInt(u32, packed_list[0..4], .big);
rc_in += 4;
var cp: u32 = 0;
var nl: usize = 0;
var hn: u32 = 1;
var ctx: [4]u32 = undefined;
for (0..ENTITY_COUNT) |_| {
// Step from the previous code point: its bit length, then the bits below the top one.
ctx[0] = K;
const nb = sym(ctx[0..1], 5);
var d = nb;
if (nb > 1) {
ctx[0] = 2 * K + nb;
d = (@as(u32, 1) << @intCast(nb - 1)) + sym(ctx[0..1], nb - 1);
}
cp += d;
var vn: u32 = 0;
var vn2: u32 = 0;
var val: u64 = utf8(cp, &vn);
ctx[0] = 3 * K + @intFromBool(d == 0);
if (sym(ctx[0..1], 1) != 0) {
ctx[0] = 4 * K;
val |= @as(u64, utf8(sym(ctx[0..1], 16), &vn2)) << @intCast(8 * vn);
}
val |= @as(u64, vn + vn2) << 56;
ctx[0] = 5 * K + @intFromBool(cp < 256);
const legacy = sym(ctx[0..1], 1) != 0;
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
var name = [_]u8{0} ** 40;
var n: usize = 0;
var h: u32 = 0;
var mp: usize = 0;
var ml: u32 = 0;
while (true) {
ctx[0] = 8 * K + (h & 63);
ctx[1] = 9 * K + (h & 4095);
ctx[2] = 13 * K + (if (ml != 0) @as(u32, hist[mp]) else 0) * 16 + @min(ml, 3);
ctx[3] = 10 * K + (h & 0x3FFFF);
const c = sym(&ctx, 6);
if (ml != 0 and hist[mp] == c) {
ml += 1;
mp += 1;
} else ml = 0;
hist[hn] = @intCast(c);
hn += 1;
if (c == 0) break;
const first: u32 = if (c < 11) '0' - 1 else if (c < 37) 'A' - 11 else 'a' - 37;
name[n] = @intCast(c + first);
n += 1;
h = (h << 6) | c;
if (n >= 2) {
const l = &last[h & 4095];
if (ml == 0 and l.* != 0) {
mp = l.*;
ml = 1;
}
l.* = @intCast(hn);
}
}
const nm: [*]const u8 = &name;
if (n <= 7) {
var key = ld64(nm) | (@as(u64, ';') << @intCast(8 * n));
var e: [*]Entry = @ptrCast(&fast[@intCast((key *% FAST_MUL) >> (64 - FAST_BITS))]);
while (e[0].key != EMPTY) e += 1;
e[0] = .{ .key = key, .val = val };
if (legacy) {
key = ld64(nm) | (@as(u64, n) << 56);
e = @ptrCast(&leg[@intCast((key *% LEG_MUL) >> (64 - LEG_BITS))]);
while (e[0].key != EMPTY) e += 1;
e[0] = .{ .key = key, .val = val };
const s = legSlot(key); // only the first two bytes matter
if (leg_max[s] < n) leg_max[s] = @intCast(n);
}
} else {
const l = &longs[nl];
nl += 1;
l.name = name[0..32].*;
l.val = val;
l.len = @intCast(n);
var hh = longHash(ld64(nm), ld64(nm + n - 8), n);
while (long_slots[hh] != 0) hh = (hh + 1) & LONG_MASK;
long_slots[hh] = @intCast(nl);
}
}
ready = true;
}
export fn input_ptr() u32 {
return @intCast(@intFromPtr(&input));
}
export fn input_utf8_cap() u32 {
return INPUT_CAP;
}
export fn output_ptr() u32 {
return @intCast(@intFromPtr(&output));
}
export fn output_utf8_cap() u32 {
return OUTPUT_CAP;
}
export fn render(n: u32) u64 {
if (!ready) init();
const size: usize = @min(n, INPUT_CAP);
const src: [*]u8 = &input;
const dst: [*]u8 = &output;
@memset((src + size)[0..64], 0);
// Stage 1 lists the position of every `&` in a window; stage 2 copies the text between
// references and decodes each one.
var e: usize = 0;
var o: usize = 0;
var base: usize = 0;
while (base < size) {
const lim = if (size - base > WINDOW) base + WINDOW else size;
var out: [*]u32 = &pos;
while (true) {
const blk = src + base;
var mm: u64 = 0;
inline for (0..8) |k| mm |= mask8(blk + 8 * k, '&') << (8 * k);
const cnt: usize = @popCount(mm);
const b: u32 = @intCast(base);
// Entries past cnt are garbage and are overwritten or ignored.
inline for (0..4) |k| {
out[k] = b + @ctz(mm);
mm &= mm -% 1;
}
if (cnt > 4) {
@branchHint(.unlikely);
inline for (4..8) |k| {
out[k] = b + @ctz(mm);
mm &= mm -% 1;
}
var k: usize = 8;
while (mm != 0) : (k += 1) {
out[k] = b + @ctz(mm);
mm &= mm -% 1;
}
}
out += cnt;
base += 64;
if (base >= lim) break;
}
var q: [*]const u32 = &pos;
while (@intFromPtr(q) < @intFromPtr(out)) : (q += 1) {
var i: usize = q[0];
// Everything this reference needs is loaded before the first store.
const w = ld64(src + i + 1);
// Copy the text since the last reference; src[i] is `&` and i < size.
{
const len = i - e;
const ca = ld64(src + e);
const cb = ld64(src + e + 8);
const cc = ld64(src + e + 16);
const cd = ld64(src + e + 24);
st64(dst + o, ca);
st64(dst + o + 8, cb);
st64(dst + o + 16, cc);
st64(dst + o + 24, cd);
if (len > 32) {
var j: usize = 32;
while (true) {
cp16(dst + o + j, src + e + j);
j += 16;
if (j >= len) break;
}
}
o += len;
}
done: {
if (@as(u8, @truncate(w)) == '#') numeric: {
// Decimal and hexadecimal share one branch-free path: classify 8 bytes,
// take the digits before the first other byte, and fold them pairwise.
const hex = (@as(u8, @truncate(w >> 8)) | 0x20) == 'x';
var p = src + i + 2 + @intFromBool(hex);
const d = ld64(p);
const t = d ^ 0x3030303030303030;
const digit = ~(((t & ~HIGH) +% 0x7676767676767676) | t) & HIGH;
const y = d | 0x2020202020202020;
const ty = y & ~HIGH;
const letter = (ty +% ONES * (0x80 - 'a')) & ~(ty +% ONES * (0x7F - 'f')) & ~y & HIGH;
const stop = ~(digit | (if (hex) letter else 0)) & HIGH;
var v: u32 = 0;
var end: usize = undefined;
if (stop != 0) {
const nb: u32 = @ctz(stop) & 0x38;
if (nb == 0) break :numeric;
var x = ((d & 0x0F0F0F0F0F0F0F0F) +% 9 * (letter >> 7)) << @intCast(64 - nb);
x = (x *% @as(u64, if (hex) 16 else 10) +% (x >> 8)) & 0x00FF00FF00FF00FF;
x = (x *% @as(u64, if (hex) 256 else 100) +% (x >> 16)) & 0x0000FFFF0000FFFF;
v = @truncate(x *% @as(u64, if (hex) 65536 else 10000) +% (x >> 32));
end = @intFromPtr(p) - @intFromPtr(src) + (nb >> 3);
} else {
// Eight or more digits: saturate past U+10FFFF.
@branchHint(.unlikely);
const radix: u32 = if (hex) 16 else 10;
while (true) {
var c: u32 = @as(u32, p[0]) -% '0';
if (c > 9) {
c = (@as(u32, p[0]) | 0x20) -% 'a' +% 10;
if (c < 10) c = 16;
}
if (c >= radix) break;
v = v * radix + c;
if (v > 0x10FFFF) v = 0x110000;
p += 1;
}
end = @intFromPtr(p) - @intFromPtr(src);
}
i = end + @intFromBool(src[end] == ';');
if (v -% 0x80 < 0x20) {
v = c1[v - 0x80];
} else if (v == 0 or v -% 0xD800 < 0x800 or v > 0x10FFFF) {
v = 0xFFFD;
}
// Lay the bits out as four UTF-8 bytes, then drop the unused leading ones.
const len: u32 = 1 + @as(u32, @intFromBool(v > 0x7F)) + @intFromBool(v > 0x7FF) + @intFromBool(v > 0xFFFF);
const bits = v >> 18 | (v >> 12 & 0x3F) << 8 | (v >> 6 & 0x3F) << 16 | (v & 0x3F) << 24;
const word = bits >> @intCast(32 - 8 * len) | utf8_marks[len];
st32(dst + o, if (len == 1) v else word);
o += len;
break :done;
} else {
const t = w ^ (ONES * ';');
const z = (t -% ONES) & ~t & HIGH;
if (z != 0) {
// Bit index of the `;` byte; the key is the name and its `;`.
const kb: u32 = @ctz(z) & 0x38;
const key = w & ((@as(u64, 2) << @intCast(kb + 7)) -% 1);
// The probe loop only finds the slot; the hit is handled after it.
var en: [*]const Entry = @ptrCast(&fast[@intCast((key *% FAST_MUL) >> (64 - FAST_BITS))]);
var k = en[0].key;
while (k != key and k != EMPTY) {
@branchHint(.unlikely);
en += 1;
k = en[0].key;
}
if (k == key) {
const val = en[0].val;
st64(dst + o, val);
o += @intCast(val >> 56);
i += 2 + (kb >> 3);
break :done;
}
} else {
// No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
const np = src + i + 1;
const sm: u32 = @intCast(mask8(np + 8, ';') << 8 | mask8(np + 16, ';') << 16 | mask8(np + 24, ';') << 24);
if (sm != 0) {
const len: usize = @ctz(sm);
var h = longHash(w, ld64(np + len - 8), len);
const lm: [*]const u8 = @as([*]const u8, &len_mask) + 32 - len;
const a0 = w & ld64(lm);
const a1 = ld64(np + 8) & ld64(lm + 8);
const a2 = ld64(np + 16) & ld64(lm + 16);
const a3 = ld64(np + 24) & ld64(lm + 24);
while (true) {
const s = long_slots[h];
if (s == 0) break;
const l = &longs[s - 1];
const nm: [*]const u8 = &l.name;
const diff = (a0 ^ ld64(nm)) | (a1 ^ ld64(nm + 8)) | (a2 ^ ld64(nm + 16)) | (a3 ^ ld64(nm + 24));
if (l.len == len and diff == 0) {
st64(dst + o, l.val);
o += @intCast(l.val >> 56);
i += 2 + len;
break :done;
}
h = (h + 1) & LONG_MASK;
}
}
}
// Without `;`, the longest legacy name that is a prefix.
var k: usize = leg_max[legSlot(w)];
while (k >= 2) : (k -= 1) {
// The length is part of the key, so a NUL after a shorter name cannot match.
const key = (w & ((@as(u64, 1) << @intCast(8 * k)) - 1)) | @as(u64, k) << 56;
var en: [*]const Entry = @ptrCast(&leg[@intCast((key *% LEG_MUL) >> (64 - LEG_BITS))]);
while (true) {
if (en[0].key == key) {
st64(dst + o, en[0].val);
o += @intCast(en[0].val >> 56);
i += 1 + k;
break :done;
}
if (en[0].key == EMPTY) break;
en += 1;
}
}
}
dst[o] = '&';
o += 1;
i += 1;
}
e = i;
}
}
// Without a reference the input is the output.
if (e == 0) return @as(u64, @intFromPtr(&input)) << 32 | size;
var j = e;
while (j < size) : (j += 16) cp16(dst + o + (j - e), src + j);
o += size - e;
return @as(u64, @intFromPtr(&output)) << 32 | o;
}
// pack.py, which produced `packed_list`:
//
// """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=18, limit=5, narrow=False)
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/f2b5a4fbd5c1ece6cd00f703f147220119316d5665baa09f81605c9188c6c999.wasmMy two-stage decoder without SIMD, in Zig: every vector operation of entry 8aa42ef2 is replaced by 64-bit word tricks. Stage 1 finds each ampersand with an exact zero-byte test on eight words per 64-byte block and one multiply per word to gather the bits; copies move two words per 16 bytes; long names use a masked compare of four words.
- Builds on
- Port of my no-SIMD C entry 1d840c50, derived from my Zig entry 8aa42ef2. The range coder is the LZMA one.
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/f2b5a4fbd5c1ece6cd00f703f147220119316d5665baa09f81605c9188c6c999.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
- 11 November 2026 at 13:14 UTC
- Language
- Zig
- Compiler
-
zig 0.15.2build-exe -target wasm32-freestanding -mcpu=generic+bulk_memory -O ReleaseSmall -fno-entry -rdynamic -fstrip --stack 8192 --initial-memory=3145728 --max-memory=3145728 - Size
- 11.5 KiB, gzip 9.3 KiB
- Download
- ~150 ms on Slow 4G (Lighthouse’s 1.6 Mbps, 150 ms round trips)
- Memory
- 48 pages (3 MiB)
- SIMD
- no
- AI models
- claude-fable-5-2
Functions, loops, branches and other static counts
- Functions
- 8
- Instructions
- 2,205
- Loops
- 20
- Conditional branches
- 55
- Indirect calls
- 0
- Memory loads
- 71
- Memory stores
- 61
- SIMD instructions
- 0
- Potentially trapping instructions
- 137
Instruction sites in the binary, not executions, counted by qip.dev’s wasm-counts.