Unescape HTML · Odin 🤝 Fable 5.2
SHA-256
3f0f771fac546e3c07d8c79760bee48926c4d62de025967613ff4956f0a15f88
View source (45.7 KiB of Odin)
// unescape_html in Odin 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 6abdb35d 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: odin build unescape-nosimd.odin -file -target:freestanding_wasm32 -o:speed
// -no-entry-point -no-bounds-check -disable-assert -default-to-nil-allocator -no-crt
// -extra-linker-flags:"--initial-memory=3145728 --max-memory=3145728 -z stack-size=8192 --strip-all"
package unescape
import "base:intrinsics"
INPUT_CAP :: 1 << 20
// The largest growth is `≫⃒` (5 bytes) becoming 6 bytes.
OUTPUT_CAP :: INPUT_CAP / 5 * 6 + 8
PAD :: 128
FAST_BITS :: 12
FAST_TAIL :: 32
LEG_BITS :: 8
LEG_TAIL :: 16
LONG_BITS :: 11
LONG_MASK :: (1 << LONG_BITS) - 1
EMPTY :: max(u64)
// Bytes of input per stage-1 window; a multiple of 64.
WINDOW :: 4096
ONES :: u64(0x0101010101010101)
HIGH :: u64(0x8080808080808080)
HIST_SIZE :: 16130
ENTITY_COUNT :: 2125
LONG_COUNT :: 506
MODEL_BITS :: 18
MODEL_LIMIT :: 5
FAST_MUL :: u64(0xa59d054b12f5b905)
LEG_MUL :: u64(0xf880d97d1854e551)
LONG_MUL :: u64(0xa0c2995f40498cb3)
@(rodata)
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.
Entry :: struct {
key, val: u64,
}
Long :: struct {
name: [32]u8,
val: u64,
len: u32,
pad: u32,
}
input: [INPUT_CAP + PAD]u8
output: [OUTPUT_CAP + PAD]u8
fast: [(1 << FAST_BITS) + FAST_TAIL]Entry
leg: [(1 << LEG_BITS) + LEG_TAIL]Entry
longs: [LONG_COUNT]Long
long_slots: [1 << LONG_BITS]u16
// Longest legacy name starting with these two bytes (hashed), or 0.
leg_max: [4096]u8
pos: [WINDOW + 16]u32
ready: bool
// Windows-1252 remapping for references to 0x80-0x9F.
@(rodata)
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,
}
@(rodata)
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.
@(rodata)
len_mask := [64]u8 {
0 ..< 32 = 0xFF,
}
ld64 :: #force_inline proc "contextless" (p: [^]u8) -> u64 {
return intrinsics.unaligned_load((^u64)(p))
}
st64 :: #force_inline proc "contextless" (p: [^]u8, x: u64) {
intrinsics.unaligned_store((^u64)(p), x)
}
st32 :: #force_inline proc "contextless" (p: [^]u8, x: u32) {
intrinsics.unaligned_store((^u32)(p), x)
}
// Copies 16 bytes as two words.
cp16 :: #force_inline proc "contextless" (d: [^]u8, s: [^]u8) {
a := ld64(s)
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.
zeros :: #force_inline proc "contextless" (x: u64) -> u64 {
return ~(((x & ~HIGH) + ~HIGH) | x) & HIGH
}
// One bit per byte of the word at p that equals c, lowest byte first.
mask8 :: #force_inline proc "contextless" (p: [^]u8, c: u64) -> u64 {
return ((zeros(ld64(p) ~ (ONES * c)) >> 7) * 0x0102040810204080) >> 56
}
leg_slot :: #force_inline proc "contextless" (w: u64) -> u32 {
return ((u32(w) & 0xFFFF) * 0x9E3779B1) >> 20
}
long_hash :: #force_inline proc "contextless" (head, tail: u64, n: u32) -> u32 {
return u32((((head ~ ((tail << 29) | (tail >> 35))) + u64(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.
K :: u32(1 << 20)
// Step toward the bit just seen, as a 16-bit fraction: 2 / (2n + 3) after n uses.
@(rodata)
rate := [6]u16{43690, 26214, 18724, 14563, 11915, 10082}
rc_in: u32
rc_range: u32
rc_code: u32
hist: [HIST_SIZE]u8
last: [4096]u16
sym :: #force_no_inline proc "contextless" (ctx: ^[4]u32, nctx: u32, nbits: u32) -> u32 {
model := ([^]u32)(&output[0])
top := u32(1) << nbits
node: u32 = 1
for node < top {
slot: [4]u32
num, den: u32
for k in 0 ..< nctx {
s := ((ctx[k] + node * 0x2545F491) * 0x9E3779B1) >> (32 - MODEL_BITS)
slot[k] = s
e := model[s]
p := (e >> 16) ~ 0x8000
a := p - 0x8000 if p >= 0x8000 else 0x8000 - p
// Weigh a context by its order, how often it was seen and how sure it is.
w := ((e & 0xFFFF) * (1 + (a >> 12))) << k
num += p * w
den += w
}
p := (num / den if den != 0 else 0x8000) >> 4
if p == 0 do p = 1
bound := (rc_range >> 12) * p
bit: u32 = 1 if rc_code < bound else 0
if bit != 0 {
rc_range = bound
} else {
rc_code -= bound
rc_range -= bound
}
for rc_range < 1 << 24 {
rc_range <<= 8
rc_code = (rc_code << 8) | u32(packed_list[rc_in])
rc_in += 1
}
for k in 0 ..< nctx {
e := model[slot[k]]
q := i32((e >> 16) ~ 0x8000)
n := e & 0xFFFF
q += (((i32(bit) << 16) - q) * i32(rate[n])) >> 16
if n < MODEL_LIMIT do n += 1
model[slot[k]] = ((u32(q) ~ 0x8000) << 16) | n
}
node = node * 2 + bit
}
return node - top
}
// A code point as UTF-8 bytes in a word, low byte first, and their count.
utf8 :: #force_no_inline proc "contextless" (v: u32) -> (word: u32, n: u32) {
n = 1
if v > 0x7F do n += 1
if v > 0x7FF do n += 1
if v > 0xFFFF do n += 1
bits := (v >> 18) | (((v >> 12) & 0x3F) << 8) | (((v >> 6) & 0x3F) << 16) | ((v & 0x3F) << 24)
word = v if n == 1 else (bits >> (32 - 8 * n)) | utf8_marks[n]
return
}
init :: proc "contextless" () {
for &x in fast do x.key = EMPTY
for &x in leg do x.key = EMPTY
rc_range = max(u32)
rc_code = u32(packed_list[0]) << 24 | u32(packed_list[1]) << 16 | u32(packed_list[2]) << 8 | u32(packed_list[3])
rc_in = 4
cp, nl: u32
hn: u32 = 1
ctx: [4]u32
for _ in 0 ..< ENTITY_COUNT {
// Step from the previous code point: its bit length, then the bits below the top one.
ctx[0] = K
nb := sym(&ctx, 1, 5)
d := nb
if nb > 1 {
ctx[0] = 2 * K + nb
d = (u32(1) << (nb - 1)) + sym(&ctx, 1, nb - 1)
}
cp += d
word, vn := utf8(cp)
val := u64(word)
vn2: u32
ctx[0] = 3 * K + (1 if d == 0 else 0)
if sym(&ctx, 1, 1) != 0 {
ctx[0] = 4 * K
word, vn2 = utf8(sym(&ctx, 1, 16))
val |= u64(word) << (8 * vn)
}
val |= u64(vn + vn2) << 56
ctx[0] = 5 * K + (1 if cp < 256 else 0)
legacy := sym(&ctx, 1, 1) != 0
// Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
name: [40]u8
n, h, mp, ml: u32
for {
ctx[0] = 8 * K + (h & 63)
ctx[1] = 9 * K + (h & 4095)
ctx[2] = 13 * K + (u32(hist[mp]) if ml != 0 else 0) * 16 + min(ml, 3)
ctx[3] = 10 * K + (h & 0x3FFFF)
c := sym(&ctx, 4, 6)
if ml != 0 && u32(hist[mp]) == c {
ml += 1
mp += 1
} else {
ml = 0
}
hist[hn] = u8(c)
hn += 1
if c == 0 do break
first: u32 = 'a' - 37
if c < 37 do first = 'A' - 11
if c < 11 do first = '0' - 1
name[n] = u8(c + first)
n += 1
h = (h << 6) | c
if n >= 2 {
l := &last[h & 4095]
if ml == 0 && l^ != 0 {
mp = u32(l^)
ml = 1
}
l^ = u16(hn)
}
}
nm := ([^]u8)(&name[0])
if n <= 7 {
key := ld64(nm) | (u64(';') << (8 * n))
e := u32((key * FAST_MUL) >> (64 - FAST_BITS))
for fast[e].key != EMPTY do e += 1
fast[e] = Entry{key, val}
if legacy {
key = ld64(nm) | (u64(n) << 56)
e = u32((key * LEG_MUL) >> (64 - LEG_BITS))
for leg[e].key != EMPTY do e += 1
leg[e] = Entry{key, val}
s := leg_slot(key) // only the first two bytes matter
if u32(leg_max[s]) < n do leg_max[s] = u8(n)
}
} else {
l := &longs[nl]
nl += 1
cp16(([^]u8)(&l.name[0]), nm)
cp16(([^]u8)(&l.name[16]), nm[16:])
l.val = val
l.len = n
hh := long_hash(ld64(nm), ld64(nm[n - 8:]), n)
for long_slots[hh] != 0 do hh = (hh + 1) & LONG_MASK
long_slots[hh] = u16(nl)
}
}
ready = true
}
@(export)
input_ptr :: proc "c" () -> u32 {return u32(uintptr(&input[0]))}
@(export)
input_utf8_cap :: proc "c" () -> u32 {return INPUT_CAP}
@(export)
output_ptr :: proc "c" () -> u32 {return u32(uintptr(&output[0]))}
@(export)
output_utf8_cap :: proc "c" () -> u32 {return OUTPUT_CAP}
@(export)
render :: proc "c" (n: u32) -> u64 {
if !ready do #force_no_inline init()
size: u32 = min(n, INPUT_CAP)
src := ([^]u8)(&input[0])
dst := ([^]u8)(&output[0])
#unroll for k in u32(0) ..< 8 do st64(src[size + 8 * k:], 0)
// Stage 1 lists the position of every `&` in a window; stage 2 copies the text between
// references and decodes each one.
e, o, base: u32
for base < size {
lim := size - base > WINDOW ? base + WINDOW : size
out: u32 = 0
for {
mm: u64
#unroll for k in u32(0) ..< 8 do mm |= mask8(src[base + 8 * k:], '&') << (8 * k)
cnt := u32(intrinsics.count_ones(mm))
// Entries past cnt are garbage and are overwritten or ignored.
#unroll for k in u32(0) ..< 8 {
pos[out + k] = base + u32(intrinsics.count_trailing_zeros(mm))
mm &= mm - 1
}
if cnt > 8 {
for k := out + 8; mm != 0; k += 1 {
pos[k] = base + u32(intrinsics.count_trailing_zeros(mm))
mm &= mm - 1
}
}
out += cnt
base += 64
if base >= lim do break
}
for q in 0 ..< out {
i := pos[q]
// Everything this reference needs is loaded before the first store.
w := ld64(src[i + 1:])
// Copy the text since the last reference; src[i] is `&` and i < size.
{
gap := i - e
ca, cb, cc, cd := ld64(src[e:]), ld64(src[e + 8:]), ld64(src[e + 16:]), ld64(src[e + 24:])
st64(dst[o:], ca)
st64(dst[o + 8:], cb)
st64(dst[o + 16:], cc)
st64(dst[o + 24:], cd)
if gap > 32 {
j: u32 = 32
for {
cp16(dst[o + j:], src[e + j:])
j += 16
if j >= gap do break
}
}
o += gap
}
done: {
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.
numeric: {
hex := (u8(w >> 8) | 0x20) == 'x'
p := i + 2 + u32(hex)
d := ld64(src[p:])
t := d ~ 0x3030303030303030
digit := ~(((t & ~HIGH) + 0x7676767676767676) | t) & HIGH
y := d | 0x2020202020202020
ty := y & ~HIGH
// Letters a-f: 0x80 - 'a' = 0x1F, 0x7F - 'f' = 0x19.
letter := (ty + ONES * 0x1F) & ~(ty + ONES * 0x19) & ~y & HIGH
stop := ~(digit | (hex ? letter : 0)) & HIGH
v, end: u32
if stop != 0 {
nb := u32(intrinsics.count_trailing_zeros(stop)) & 0x38
if nb == 0 do break numeric
x := ((d & 0x0F0F0F0F0F0F0F0F) + 9 * (letter >> 7)) << (64 - nb)
x = (x * (hex ? 16 : 10) + (x >> 8)) & 0x00FF00FF00FF00FF
x = (x * (hex ? 256 : 100) + (x >> 16)) & 0x0000FFFF0000FFFF
v = u32(x * (hex ? 65536 : 10000) + (x >> 32))
end = p + (nb >> 3)
} else {
// Eight or more digits: saturate past U+10FFFF.
radix: u32 = hex ? 16 : 10
for {
c := u32(src[p]) - '0'
if c > 9 {
c = (u32(src[p]) | 0x20) - 'a' + 10
if c < 10 do c = 16
}
if c >= radix do break
v = v * radix + c
if v > 0x10FFFF do v = 0x110000
p += 1
}
end = p
}
i = end + u32(src[end] == ';')
if v - 0x80 < 0x20 {
v = u32(c1[v - 0x80])
} else if v == 0 || v - 0xD800 < 0x800 || v > 0x10FFFF {
v = 0xFFFD
}
// Lay the bits out as four UTF-8 bytes, then drop the unused leading ones.
ln := 1 + u32(v > 0x7F) + u32(v > 0x7FF) + u32(v > 0xFFFF)
bits := (v >> 18) | (((v >> 12) & 0x3F) << 8) | (((v >> 6) & 0x3F) << 16) | ((v & 0x3F) << 24)
word := (bits >> (32 - 8 * ln)) | utf8_marks[ln]
st32(dst[o:], ln == 1 ? v : word)
o += ln
break done
}
} else {
t := w ~ (ONES * 0x3B)
z := (t - ONES) & ~t & HIGH
if z != 0 {
// Bit index of the `;` byte; the key is the name and its `;`.
kb := u32(intrinsics.count_trailing_zeros(z)) & 0x38
key := w & ((u64(2) << (kb + 7)) - 1)
en := u32((key * FAST_MUL) >> (64 - FAST_BITS))
// The probe loop only finds the slot; the hit is handled after it.
k := fast[en].key
for k != key && k != EMPTY {
en += 1
k = fast[en].key
}
if k == key {
val := fast[en].val
st64(dst[o:], val)
o += u32(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.
np := src[i + 1:]
sm := u32((mask8(np[8:], ';') << 8) | (mask8(np[16:], ';') << 16) | (mask8(np[24:], ';') << 24))
if sm != 0 {
ln := u32(intrinsics.count_trailing_zeros(sm))
h := long_hash(w, ld64(np[ln - 8:]), ln)
lm := ([^]u8)(&len_mask[0])[32 - ln:]
a0 := w & ld64(lm)
a1 := ld64(np[8:]) & ld64(lm[8:])
a2 := ld64(np[16:]) & ld64(lm[16:])
a3 := ld64(np[24:]) & ld64(lm[24:])
for {
s := u32(long_slots[h])
if s == 0 do break
l := &longs[s - 1]
nm := ([^]u8)(&l.name[0])
diff := (a0 ~ ld64(nm)) | (a1 ~ ld64(nm[8:])) | (a2 ~ ld64(nm[16:])) | (a3 ~ ld64(nm[24:]))
if l.len == ln && diff == 0 {
st64(dst[o:], l.val)
o += u32(l.val >> 56)
i += 2 + ln
break done
}
h = (h + 1) & LONG_MASK
}
}
}
// Without `;`, the longest legacy name that is a prefix.
for k := u32(leg_max[leg_slot(w)]); k >= 2; k -= 1 {
// The length is part of the key, so a NUL after a shorter name cannot match.
key := (w & ((u64(1) << (8 * k)) - 1)) | (u64(k) << 56)
en := u32((key * LEG_MUL) >> (64 - LEG_BITS))
for {
if leg[en].key == key {
st64(dst[o:], leg[en].val)
o += u32(leg[en].val >> 56)
i += 1 + k
break done
}
if leg[en].key == EMPTY do break
en += 1
}
}
}
dst[o] = '&'
o += 1
i += 1
}
e = i
}
}
// Without a reference the input is the output.
if e == 0 do return (u64(uintptr(src)) << 32) | u64(size)
for j := e; j < size; j += 16 do cp16(dst[o + (j - e):], src[j:])
o += size - e
return (u64(uintptr(dst)) << 32) | u64(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/3f0f771fac546e3c07d8c79760bee48926c4d62de025967613ff4956f0a15f88.wasmMy two-stage decoder without SIMD, in Odin: starting from entry 6abdb35d, every vector operation 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 Odin entry 6abdb35d. 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/3f0f771fac546e3c07d8c79760bee48926c4d62de025967613ff4956f0a15f88.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
- 12 November 2026 at 00:17 UTC
- Language
- Odin
- Compiler
-
odin dev-2026-11:9a6991685build -file -target:freestanding_wasm32 -o:speed -no-entry-point -no-bounds-check -disable-assert -default-to-nil-allocator -no-crt -extra-linker-flags:"--initial-memory=3145728 --max-memory=3145728 -z stack-size=8192 --strip-all" - Size
- 12.6 KiB, gzip 9.5 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,674
- Loops
- 20
- Conditional branches
- 68
- Indirect calls
- 0
- Memory loads
- 85
- Memory stores
- 91
- SIMD instructions
- 0
- Potentially trapping instructions
- 177
Instruction sites in the binary, not executions, counted by qip.dev’s wasm-counts.