;; unescape_html in hand-written WebAssembly text with SIMD: decodes every HTML character
;; reference in UTF-8 text the way Python's html.unescape does, and copies all other bytes
;; unchanged.
;;
;; The design is the one from my C entry, written directly so that nothing a compiler adds
;; is left: no stack, no stack pointer, every table at a fixed address.
;; - 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 turns each 64-byte block into a bitmask of its `&`
;; and appends their 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 where they are; nothing is copied.
;; - A name of up to 7 bytes ending in `;` is looked up without measuring it: the first `;`
;; in the next 8 bytes is found with a SWAR zero-byte test, the bytes up to it are the key,
;; and one multiply indexes an open-addressed table of 16-byte entries (key, value).
;; - Longer names go through a second table and one masked 32-byte vector compare.
;; - Without `;` only the 106 legacy names match. A filter on the first two bytes gives the
;; longest legacy name that could start there, usually none.
;; - Numeric references of up to 7 digits, decimal or hexadecimal, share one branch-free
;; SWAR path.
;; - The entity list is stored packed (5.9 KB for 2,125 names) and unpacked on the first
;; call: see $sym and $init. pack_mix.py, at the end of this file, is the matching packer.
;;
;; Memory map (bytes):
;; 0 packed entity list, then the Windows-1252 table, model rates, UTF-8 marks
;; 5968 ctx: the contexts of the symbol being unpacked; 6000 slot: their model entries;
;; 6032 their stretched probabilities; 6064 five sets of six mixing weights
;; 6192 name: the name being unpacked, zero padded
;; 6240 leg_max: longest legacy name starting with two bytes (hashed), or 0
;; 10336 long_slots: hash of a long name -> its number in `longs`, or 0
;; 14432 last: match model, where two characters were last seen
;; 22624 pos: positions of `&` in the current window (first, the unpacker's squash and stretch tables)
;; 39072 hist: every name character unpacked so far
;; 55216 longs: 48-byte records (name[32], value, length) for names of 8 bytes or more
;; 79504 fast: (key, value) entries for names of up to 7 bytes; empty key = all ones
;; 145552 leg: the same for legacy names, keyed with the length in the top byte
;; 149904 len_mask: 32 bytes of 0xFF, then 32 of 0
;; 149968 output, and 262144 bytes into the same buffer:
;; 412112 input, 1048576 bytes and padding
;; Output and input share one buffer, a technique from my earlier entries (4a6e243a and
;; others): a reference grows by at most 1.2x (`≫⃒` is 5 bytes in, 6 out), so the write
;; position stays at least 52429 bytes behind the read position and decoding in
;; place is safe. The bytes before the input also hold the unpacker's model on the first call.
;; A value is its UTF-8 bytes in the low bytes of an i64 and its length in the top byte.
;;
;; Build: wat2wasm unescape.wat -o unescape-wat.wasm
(module
(memory (export "memory") 23 23)
;; Range coder state: the first four bytes of the list are folded into $code here.
(global $range (mut i32) (i32.const -1))
(global $code (mut i32) (i32.const 0xDEE14C7F))
(global $in (mut i32) (i32.const 4))
(global $ulen (mut i32) (i32.const 0))
(data (i32.const 0) "\de\e1\4c\7f\b4\1a\b7\28\75\6f\d4\01\dc\f3\50\13\89\93\7d\81\07\07\89\10\82\9e\8a\7d\05\ea\c4\6a\59\45\c5\f3\88\56\da\98\6d\6c\45\21\37\47\9f\58\55\33\70\33\6b\8d\33\16\9a\b4\21\8c\3f\9a\83\98\0d\5e\1e\e4\17\fb\87\ec\81\ba\dc\06\61\0b\63\21\dd\d9\e0\4b\8e\45\0c\9f\ab\19\ce\fe\86\72\b0\af\84\e4\92\60\62\1e\9a\de\96\47\f3\42\94\ae\85\1e\8e\83\b1\9f\85\82\a0\7b\c1\80\95\cc\ee\c0\bd\11\aa\9d\b0\6a\3f\b5\67\64\73\f5\a3\19\30\78\30\52\5a\ac\64\2f\90\ca\7a\48\a3\75\4b\7c\78\75\16\07\0e\aa\df\60\0a\92\4d\ad\12\bf\59\04\f4\73\07\4f\d2\09\21\38\3b\d7\f1\99\3b\24\bd\49\52\e0\8b\5a\5d\13\d3\f8\e6\d9\a7\12\85\89\f5\c6\37\73\4b\9e\d3\d6\1a\09\57\d1\d3\04\b1\ec\ba\f1\10\0a\0e\43\ce\96\58\f9\3c\a7\6b\68\b7\01\89\a2\b3\03\3b\dd\98\30\36\44\e9\9e\64\b7\93\c6\6e\d0\d5\16\96\0a\b0\12\74\be\c0\4e\0f\30\37\ec\1e\d9\17\46\a9\32\14\52\34\a4\89\73\e8\70\65\b0\01\43\95\5c\39\b5\42\11\e9\0b\81\8b\71\b2\87\2f\fd\8f\84\55\44\ba\48\03\67\96\d3\08\b3\a8\46\cb\41\a9\6b\40\ab\22\b4\21\83\10\12\88\ca\1b\de\35\65\33\65\f8\f5\9e\78\4a\08\50\14\91\b4\1a\1e\3c\86\7a\6f\2d\c6\3d\12\ab\a1\9a\6e\42\e8\c7\f4\7b\28\c0\1b\2f\48\8d\7a\d2\c3\39\7a\c1\eb\33\f2\62\85\24\42\e7\1e\98\8d\80\7a\31\fe\2e\fe\1d\9e\8c\9d\68\be\07\9f\ef\f9\1e\87\b5\56\70\84\89\0c\a1\4a\8f\5a\71\d6\5e\54\ae\a7\a4\33\0c\86\4c\54\d0\a2\a7\e4\98\36\d9\95\89\6f\d5\ed\eb\c3\72\d1\72\12\98\ce\61\43\4a\8e\c7\3e\80\89\3c\03\26\46\8c\e7\fd\95\85\ef\a5\df\3d\a5\b8\f4\18\9d\df\aa\55\03\bf\40\4b\56\17\4b\78\55\9f\b7\32\f4\1b\bd\01\6e\3d\d6\b7\9f\55\b5\c2\23\0c\1d\1e\d7\ef\91\e7\e9\db\e5\3d\c0\c2\d4\a4\2d\7f\7f\c9\75\b2\f9\a5\12\2e\75\91\13\30\f7\fa\e3\3d\19\16\67\20\44\ce\2f\ec\a9\ca\af\e4\b3\d5\fe\6f\0a\3e\b1\2f\4d\67\9c\e5\62\4b\2f\e2\df\88\a9\0a\09\47\72\14\67\be\f1\77\40\fd\e9\f3\da\51\d9\d7\0c\69\1f\1d\89\d3\d1\94\cf\df\99\46\88\f2\dc\67\f7\a1\cb\d9\d4\7e\da\62\e8\6b\f7\74\e6\c2\54\89\06\41\c9\ef\02\2a\86\72\01\8d\ed\d0\c1\7e\9c\da\48\e2\30\f9\40\f6\13\2c\53\69\a1\4f\83\90\84\5a\d9\ea\bc\c1\76\37\f1\0f\dd\05\71\0a\59\d0\a7\9c\89\f2\78\b2\56\b1\27\a5\f0\40\2a\d9\2b\05\b3\1c\dc\f4\c5\87\c4\83\6d\b9\58\9e\2f\7d\e9\62\56\0d\6e\70\2f\2f\0a\47\2e\07\c9\b8\58\3d\bb\c9\bb\d1\9f\5d\af\84\34\73\e8\01\50\6d\7a\9f\28\2a\29\f1\30\0e\09\a8\ac\10\2b\eb\52\22\f6\3d\5c\96\5f\c8\df\18\b9\9c\bb\aa\8b\1b\f8\e6\42\9d\96\2c\f8\a0\83\93\89\9c\6b\b5\2f\0d\1b\45\94\4e\55\b6\fd\42\06\17\fb\23\a6\e6\c7\9a\70\03\39\a0\77\89\1c\88\49\bf\92\42\90\a8\5a\1b\62\99\b8\5e\79\7c\e5\12\db\e3\8a\af\53\ec\3f\d9\c7\df\b5\8a\df\d5\cf\62\1c\1f\ef\ed\64\4b\32\83\7b\7a\6b\46\7f\7d\78\77\45\b0\8f\c8\2e\58\35\d8\e9\b6\b5\9d\cc\84\13\de\06\c7\71\df\d0\54\0b\81\35\27\55\ba\cb\d8\ec\f1\f9\35\12\cc\da\a6\73\f8\91\c6\2e\ce\fe\ae\d9\e8\8a\5c\7b\78\47\30\3a\48\9d\06\aa\cb\5e\ad\35\c3\54\0f\e1\f0\40\dc\ec\cc\69\36\61\6d\11\49\bc\d8\e6\2a\0d\7e\d4\f8\e1\d8\02\03\60\8d\ad\5c\eb\b0\91\3e\72\ad\d4\15\0b\e3\da\0d\3b\21\7b\dc\8e\82\3a\c5\d5\76\e8\be\4e\23\6d\f9\0f\f8\10\ec\96\b9\ee\9b\1f\de\46\fe\52\f4\58\95\39\10\49\08\cc\48\39\ec\aa\36\1a\b8\f8\9b\55\2a\55\cc\75\7c\16\81\33\47\9e\ff\ce\1a\61\b2\80\f6\28\d9\55\c2\00\a6\04\77\f3\21\f0\9b\6e\ce\28\a4\f7\4a\91\37\fc\72\83\21\bb\7f\cc\2a\f5\14\0b\18\6b\c8\09\15\a8\a5\e2\d2\43\ba\9c\70\5a\8c\0a\e4\b0\a8\1a\aa\2a\c9\52\ab\70\6f\f5\e9\76\eb\a8\1b\24\34\32\00\3b\0c\cf\28\d2\6f\92\f3\a2\81\4c\88\f7\7a\23\b8\fd\ad\e3\1d\e4\b9\eb\80\34\f3\f2\ec\4e\3b\ef\c3\74\fc\e5\74\97\55\02\01\17\f7\6c\06\c6\8b\a4\18\6e\00\3f\33\ee\25\21\18\a1\ee\ca\57\e2\1f\0e\09\dd\1f\90\2c\37\ea\8c\11\0d\99\e9\2d\1c\32\56\b9\b7\b5\7a\6c\ae\0c\e0\51\0c\cf\45\7c\c5\72\02\51\a7\68\85\f1\93\ea\81\82\a9\a1\fe\59\1c\00\d6\30\22\61\b5\f6\43\87\fa\78\09\2b\da\34\7e\2d\fb\3a\9b\f0\d1\9a\25\d8\f5\98\cb\01\c0\ff\b7\90\10\c6\43\4e\68\fc\95\d6\3b\de\db\54\e2\55\b3\f1\44\43\34\7d\94\9c\e4\58\5c\bc\25\2a\75\a0\f2\9c\ea\99\d9\f2\78\f4\2f\73\72\96\5a\b1\c7\1e\b2\38\e1\fb\b8\67\74\73\7a\a3\ee\07\50\cb\9b\cd\c9\97\d8\9a\53\ed\62\59\92\29\42\fa\b4\7b\6f\57\b9\1e\87\b3\d6\35\35\31\28\b6\30\e5\57\85\ec\2a\95\0f\0d\2d\12\80\74\3d\6a\8e\d9\56\f5\f3\fb\db\e0\4b\66\10\2e\50\1b\9d\37\1b\cc\e0\ac\04\a4\c2\93\da\60\9e\d3\7a\7d\a9\37\2b\52\fc\3a\9a\20\72\cd\4c\fb\00\6b\d8\57\41\28\cf\ae\d4\c8\3e\6c\bb\90\a2\90\21\eb\ae\7e\59\97\e9\03\ec\79\6b\f6\de\0a\6c\53\fa\90\25\62\03\31\ec\53\65\47\78\31\ce\ba\f2\7e\c7\5e\1c\32\97\92\e7\f9\70\98\19\76\b8\13\1b\d4\11\b5\6c\53\7d\69\ad\95\72\2e\83\3b\3f\f3\30\33\5b\4d\b1\2e\3f\81\ef\0e\99\ff\5e\c4\2d\fe\69\5f\47\91\17\65\1c\1c\2b\fd\47\1c\cb\25\60\67\e9\55\7f\ef\25\78\f4\37\79\1d\c0\5c\33\a1\cb\71\94\9a\85\f1\84\46\79\56\51\b2\20\9c\8e\67\57\e5\96\de\ba\a2\fc\e9\f3\c1\12\bd\35\a8\5b\9b\ea\d0\d7\74\59\7d\e8\47\bb\7e\f4\43\5d\93\5f\be\6a\82\7c\10\41\4b\2b\db\ce\56\24\e4\d6\5b\04\ee\df\78\50\7d\64\21\5c\9b\d9\96\1f\a4\05\a6\ea\87\39\16\e3\4b\38\f4\59\34\27\9e\43\15\47\4c\eb\dd\70\11\f2\2c\eb\fa\4e\54\bf\1d\57\1c\10\d3\b2\6d\9f\ae\44\35\fd\bc\33\e2\5d\b5\50\97\ef\0b\3f\60\f3\e4\43\0a\5c\a2\34\78\9f\14\69\c2\9b\45\44\47\77\80\98\e0\f2\c0\14\32\8b\fc\5a\d7\1e\27\c1\3d\e6\13\63\00\c1\55\2c\2d\f2\e1\94\d6\08\07\62\81\37\de\b1\e3\03\ee\7d\98\ee\98\fc\5c\6a\b9\8e\c1\99\3b\7b\6a\75\bd\4e\d2\35\35\59\e2\ff\84\f2\4a\3c\92\df\31\ed\3b\f3\34\a4\e1\92\6c\5b\1d\39\9a\c7\6f\11\35\14\c1\3c\45\97\d6\e8\74\a0\71\78\63\89\e6\af\e8\a2\1d\08\1a\a4\13\a4\4b\0e\2f\4e\af\e8\fb\3a\07\2f\c4\b7\ff\95\5e\ea\0c\b1\40\c8\d2\3d\49\11\93\d3\03\31\62\fc\2c\11\cf\17\0a\85\dc\a4\6f\cc\e3\8d\cf\b6\98\14\0e\f2\60\0c\4f\6a\ec\bf\eb\42\8b\d6\64\92\df\ab\38\45\08\62\1f\6f\03\ed\ce\29\9f\b6\99\20\cb\e7\46\76\cb\c1\13\b0\4e\bb\a7\56\f8\76\07\dd\3b\6a\21\4e\96\05\99\14\52\a5\4d\72\7a\42\69\93\ce\b0\09\f3\b2\34\5b\a5\be\18\38\2b\85\5f\76\2d\98\8c\43\fa\c4\ad\de\3c\df\b8\66\38\2c\c5\08\a8\12\72\f8\a0\17\d9\c9\67\63\5c\89\80\d7\13\4d\f2\23\fa\da\7a\29\7c\14\05\6c\7f\2f\f0\5d\ff\ef\79\67\90\3b\72\b7\ad\d7\a3\d2\70\cf\eb\aa\16\09\64\4b\04\09\96\ba\89\00\d7\84\81\d7\4f\63\ad\a5\df\e8\17\45\7d\06\4d\08\c9\dd\94\08\9c\9c\e8\13\cc\13\77\59\d6\4b\b7\83\06\8c\10\4f\18\5c\af\47\a2\8d\8f\cd\b6\31\88\f2\f1\03\cd\cc\45\ba\b5\35\7e\f8\ef\1f\61\7a\a1\03\74\98\d1\f7\3d\b5\2d\cd\bb\0b\af\05\20\69\2d\e5\61\9d\db\93\16\39\40\a8\e0\7c\0a\02\1b\0a\c6\48\85\ef\71\15\62\43\25\d1\99\94\e5\31\9e\8f\30\38\e7\b5\77\91\e0\4e\01\e9\5a\51\55\f3\08\96\9e\43\a9\78\5a\ab\68\b1\a9\66\5c\4c\a5\e0\f1\50\62\aa\a4\fe\13\24\50\90\9b\de\fe\21\4a\2b\ee\1c\b1\cd\0f\ee\a0\e4\e4\9c\b3\87\fb\8e\a7\9e\09\08\bf\ae\df\a9\ea\0d\cd\6b\85\fa\4e\b2\42\20\01\92\07\23\66\3c\1f\24\5d\da\c2\03\03\36\03\23\8f\6c\75\4a\7d\84\95\e4\58\d6\ac\6e\a5\73\ed\1f\fd\83\80\e8\72\c4\97\6b\6c\34\bd\b4\56\25\dd\6f\1f\dd\62\0d\b9\01\e2\90\44\c0\86\33\f1\79\d0\79\3f\c4\8b\ba\62\ea\6e\1b\2f\f8\3a\b8\63\b9\16\a7\ae\aa\6b\ea\3b\4c\03\6e\cd\45\c9\28\d4\a9\58\5d\68\b6\3b\44\52\79\b6\ef\c4\7b\fc\a0\20\93\65\8f\e1\10\48\41\d8\be\eb\72\f0\40\e6\9b\e4\a0\a5\f4\26\2b\ed\ce\95\1f\aa\af\b3\2c\a2\9a\c9\e0\fa\57\ad\14\6c\42\0a\7f\9a\51\bd\ca\7e\00\3d\e8\bd\34\69\f5\99\75\a5\2d\f2\4f\8d\27\61\0b\12\79\10\89\3b\f7\38\9e\8f\16\06\00\3b\e2\30\25\f3\be\b4\fe\4f\c4\e1\c7\38\05\5e\b1\de\67\0b\c0\48\3f\89\5a\fa\e8\b3\4b\2f\dd\6c\89\c5\ef\1f\7f\9a\8e\ef\d0\f9\f0\33\26\f6\42\d5\6c\3c\68\dc\a9\4c\86\d6\92\e9\91\ea\c8\0e\57\57\41\c1\2e\0a\d5\2d\25\ac\5e\77\2c\07\d5\97\67\ab\33\07\a2\4e\24\b2\ae\73\9c\c0\9f\f4\85\a1\89\88\fc\8b\3d\9f\af\43\44\2b\32\3e\a1\20\1c\4a\f2\8b\55\21\c2\01\ad\2d\dc\43\22\b0\0b\6c\81\85\1a\69\c8\44\26\81\f4\a8\43\df\3a\67\5d\f2\4b\b5\bd\74\cf\9f\16\30\1e\49\94\55\fe\02\2d\90\80\aa\50\5e\af\d2\b1\16\29\a8\aa\1a\ed\05\00\94\fc\84\4f\cc\e6\b3\1f\df\e8\25\b9\17\f7\8c\55\ca\b7\5c\e3\51\5b\6b\9d\01\38\9e\e7\8b\f5\71\a4\cb\ce\e6\7f\b3\53\df\65\e2\e3\de\be\25\ac\4b\de\15\7e\6b\aa\57\cf\8b\8c\b3\b9\53\6e\e6\bc\f8\d0\52\19\d3\f2\a0\3b\9d\e2\00\00\12\d6\8c\6e\bf\0e\79\4f\5e\0a\c4\fd\0a\12\e8\c1\b0\ef\b7\65\ac\7d\f0\e9\9b\27\34\27\e4\ba\92\e2\0a\84\5a\18\00\93\8d\63\ac\08\af\9d\f3\ab\df\64\af\d6\95\7c\79\da\e9\fd\fb\99\bd\3b\e3\9c\64\9e\7e\a5\0a\96\c0\1b\99\b0\98\29\20\e5\5c\da\ab\6b\26\3a\c1\84\4d\45\93\99\69\29\7b\e2\57\27\94\ce\b9\49\f9\8e\95\d8\52\16\7e\59\dd\8d\bc\2e\49\19\7a\fd\50\c7\0c\b4\b3\c8\8d\be\50\9c\24\3d\a8\08\81\7c\43\3e\7b\34\57\97\ea\04\3b\fd\5e\90\3e\51\2a\30\d6\b5\0f\ef\a1\5c\d1\d4\a2\eb\2b\30\e7\35\fd\d9\6e\61\bc\d0\fa\f8\3b\d3\1c\d5\49\46\c7\94\43\5f\1d\0f\1e\d1\46\7e\b5\55\f5\b4\1a\f6\e6\35\27\35\31\5c\0e\57\27\49\8c\7f\9b\aa\01\8c\cc\7e\85\e1\89\6a\bb\f5\46\a2\34\fa\58\cf\0e\ef\53\07\42\86\e5\b0\8b\dd\4e\31\1e\d1\78\7f\43\01\86\1d\92\af\a0\b1\8d\6e\bd\75\bf\94\6d\ff\46\ca\fc\c3\6f\5b\43\a7\5a\60\08\94\d7\1b\3f\3b\04\a4\d4\6f\65\0b\f9\ab\60\8c\c4\a4\20\de\00\b6\94\e9\c3\ed\26\bc\6b\13\97\e5\6c\ee\90\c2\77\07\dd\d5\24\17\6b\9d\b1\0d\f2\6e\3b\6c\73\f2\97\e4\e3\38\4e\03\da\e9\e3\ab\7f\9c\4e\42\af\b9\7c\b4\f0\71\c1\d4\61\16\f5\dc\21\1c\a1\c1\24\63\1b\20\f9\39\a9\7a\66\d5\d1\c6\97\cf\ab\81\26\23\69\4f\e6\f6\a6\a7\05\02\8b\c5\0b\97\79\e4\68\f4\f7\71\39\56\57\fc\8d\fa\8a\c2\65\5b\f2\30\ee\75\8a\34\bc\69\8d\a7\ce\71\08\d4\b0\5e\83\c8\65\2b\5c\9c\06\1a\aa\d4\85\92\8d\96\22\33\fd\93\62\8f\4b\28\c7\d2\22\63\9b\e0\5a\47\81\46\d3\c4\15\02\42\4a\b3\f0\0b\3c\b2\9e\c5\1a\06\d3\62\9b\2f\78\d8\02\ce\f3\a5\25\e3\9f\ab\ab\d5\58\f4\50\fd\8a\d0\b4\ed\9a\1f\e1\58\31\a0\6f\5a\db\8d\c1\dc\38\09\2f\2e\55\fe\aa\c1\7a\11\23\e6\e0\c1\db\3c\78\cc\50\c8\ce\cd\a7\2d\50\de\6f\5f\f3\17\41\c2\36\29\81\19\4a\31\fc\e9\c5\4d\c3\4e\8e\db\ac\49\2e\ee\5a\d7\32\56\46\9f\23\bc\cf\ab\04\59\ff\f9\0d\d9\68\10\4b\60\24\e6\9e\2a\71\a5\5f\90\23\d5\bc\58\0b\13\29\63\97\3e\39\76\67\82\2e\b0\d2\91\8d\8e\6e\ae\71\9f\11\a2\1c\30\17\fa\87\da\11\fe\7e\27\00\45\b1\36\7a\39\f3\2d\95\95\e3\03\d5\33\17\19\bd\69\6c\ee\2b\67\34\47\3a\48\dc\e5\a0\5a\56\b8\36\cf\d3\e9\5d\4f\bf\47\c1\81\fb\8a\67\90\ac\06\be\76\e7\81\d5\67\bb\e0\cd\61\65\13\a4\42\80\35\1f\bc\0b\c2\a1\fb\5f\da\e1\55\34\52\97\51\05\bf\59\f3\2e\62\15\00\16\2b\4c\01\7c\e6\a3\47\73\13\af\89\80\a4\e1\6f\59\fd\7c\ac\3c\36\23\48\61\c2\04\08\61\54\89\8d\dd\8c\5b\bf\31\1b\2c\42\fe\0b\7a\a1\10\86\ae\c8\83\5f\24\92\38\bd\88\90\20\a8\07\61\d1\de\43\ff\47\ae\84\fe\1d\ef\3a\af\29\a1\ae\30\43\c2\18\c1\ac\b7\0e\7f\91\20\e2\4b\fb\92\b4\cd\4b\b7\46\6b\db\2b\82\d4\65\ee\ff\8c\0e\66\2e\b7\81\e1\e3\9c\38\07\5c\43\0d\04\16\67\29\1c\45\aa\cb\24\d5\16\9b\17\34\54\70\16\2a\01\51\20\5f\62\08\3b\ef\3d\67\b7\e2\05\f5\13\af\f6\01\14\ba\b1\ca\61\b9\d9\3d\fe\be\dc\d3\90\97\27\f7\3e\6d\97\66\28\8e\63\78\e9\3e\f4\d2\dd\3f\ae\16\22\69\48\20\67\e2\c2\50\1f\be\c9\85\28\00\0d\58\63\5a\cb\fb\0a\c2\6f\ff\64\4b\d3\c6\46\2b\e2\af\02\65\4a\c6\68\88\43\8b\7b\ee\6d\c4\67\2c\f3\00\78\83\aa\e9\44\12\7c\56\af\f2\cc\59\8b\4b\92\1a\a7\7d\b0\de\24\7b\51\bc\60\a8\97\37\e7\67\6c\58\e7\32\05\67\01\82\61\7d\e4\04\ec\07\a2\2c\be\c7\a3\d4\3c\18\f4\12\9b\8b\72\f2\f3\a4\ee\5e\3e\97\3f\7c\57\cf\a9\22\5b\16\49\b8\12\d3\1f\e5\4a\06\42\01\9f\80\1f\72\f8\9d\00\56\05\ff\50\84\4c\92\73\c6\7f\32\9a\53\8b\c7\82\57\99\e8\85\5e\a2\a6\eb\72\6c\ec\0d\2d\11\2f\47\02\f1\2d\b7\0c\1d\53\58\b0\ab\c7\1a\1d\fa\f6\9f\23\d8\f9\a9\8c\c3\bb\39\74\f4\f5\a6\88\37\71\02\65\70\21\bb\8d\c8\cf\74\8f\47\09\4e\7c\67\96\ec\fb\77\12\f7\0a\3a\f6\f4\47\97\9c\97\f5\38\73\45\bb\8a\2f\61\c8\ee\05\6f\72\77\57\8e\05\dc\02\e8\02\c4\cc\5b\12\48\3a\58\f8\34\0b\8d\e3\4d\b9\83\20\73\34\08\30\0a\b7\da\e1\ca\c1\ca\7a\98\fa\10\a6\0c\c0\29\71\03\c6\2c\59\f7\6b\56\c1\a2\09\98\0c\c5\ec\25\88\de\90\ea\21\37\cc\da\1c\6d\2b\22\08\c2\ed\34\f5\0b\8d\ad\1b\38\d8\3f\67\51\28\e2\de\b4\14\93\76\da\08\df\5b\6d\03\a9\ef\f4\0b\3a\11\c9\c0\38\56\54\1f\5a\1d\c8\99\f0\08\41\ee\0e\34\f6\fe\55\a7\a8\b0\ce\2c\99\c8\7a\81\e6\71\67\1b\b1\a2\92\a9\5b\24\bc\f9\9d\af\09\26\ea\a0\a1\9e\27\5d\bc\a6\fe\fb\d8\95\a2\86\db\af\6f\d0\a4\2b\57\25\6d\54\06\29\aa\b4\db\d3\40\0d\77\2d\e8\d4\2d\74\72\9e\d2\f8\6c\0d\f3\e8\6a\fa\22\d1\a9\bb\19\f1\45\8b\0f\01\35\86\4d\d3\ef\ce\b5\f7\8f\45\b6\49\f8\37\81\60\37\51\ab\4b\73\3d\db\cd\a9\8a\2e\5a\f9\b8\f1\c7\eb\57\35\53\f3\09\6c\f4\9d\9e\24\f4\43\f4\59\3b\a9\b8\d1\25\b8\be\8d\7d\04\4a\09\8e\ce\b5\fc\9b\2b\fe\0f\13\7c\70\68\0c\5a\57\2c\22\67\4b\40\01\54\11\d6\4e\a7\65\95\43\61\f5\ba\7b\7d\12\fc\8d\f6\94\e9\ec\bb\e8\aa\8b\e0\71\a2\00\2b\a0\09\47\45\8e\7b\28\fa\19\bb\1c\1d\a5\f1\30\2a\d1\b9\61\23\ab\2d\7c\60\6d\fb\14\b5\d3\b0\7d\73\58\1f\52\f5\28\67\2c\d0\c3\dc\74\96\b9\06\ff\38\6c\e8\0a\69\ad\f2\ca\24\4f\61\1a\75\52\0d\bf\69\2c\ae\a6\fc\d0\e6\78\83\76\c1\29\64\9a\88\c9\60\e3\07\82\cb\ae\a0\1d\dc\e9\94\2b\e6\06\56\58\55\79\47\69\31\af\8b\aa\3b\6f\6c\4b\16\63\2a\23\fa\dc\00\59\12\fc\66\aa\8e\e1\2c\ba\2d\5b\25\c6\d2\c6\f5\4c\3c\b0\df\06\67\24\11\1d\f3\d7\2d\bd\cb\84\dd\23\39\8b\cb\35\df\c2\23\d2\ad\8d\1b\57\73\a7\ec\d9\5d\be\63\d8\95\e5\dc\2e\72\60\4e\a3\8a\3e\85\29\0f\c7\be\87\24\f8\c4\7e\7f\27\64\e9\df\19\b5\b1\e3\72\29\8c\ee\e4\63\35\11\b3\c8\f8\16\98\7e\89\be\b3\b6\d0\b3\da\27\29\97\9f\d8\52\9f\81\1f\a6\11\78\c8\25\bf\2f\f4\5e\84\f3\01\08\c5\3b\50\44\aa\04\a7\29\0f\a3\fa\87\b2\65\eb\bc\a0\f7\61\c4\5b\80\6b\88\1a\15\40\39\4b\52\75\1b\46\00\64\e4\5e\02\d5\31\fd\2f\f9\9d\33\44\5a\f0\19\55\c2\ec\0b\f2\d2\01\d0\e4\63\82\d2\97\c6\d2\24\59\c4\8a\93\11\b4\58\61\d6\8e\a9\0b\90\d6\aa\d2\e4\bd\4c\67\05\fe\8e\fa\a4\d7\5d\e5\62\1a\5f\6e\e3\02\66\fe\0d\b7\db\48\ff\f0\b7\9e\67\e1\3b\60\34\9f\f7\a0\53\bb\62\7d\80\c7\11\26\68\d3\4f\25\97\60\15\fe\60\13\4f\fe\dc\d5\c8\56\f1\78\08\95\91\f8\57\84\85\56\d9\c0\3a\a6\f0\5b\29\09\50\d1\7c\95\3a\1f\36\4f\10\53\68\bf\ae\eb\55\98\c6\d1\0f\ae\ab\a4\5d\8a\e2\a4\4c\77\a8\2e\ad\c2\87\46\17\22\8b\3c\27\f4\c3\67\d0\e9\d8\fa\ad\8d\fe\81\d2\7d\d8\61\ab\70\46\7f\9a\0f\41\4a\9d\88\91\22\33\86\9e\79\c6\f1\bb\95\0d\fa\95\81\2a\98\fb\ef\a1\8c\bb\cb\ff\a7\97\88\36\dd\e9\d1\15\4d\89\ce\51\ae\7e\7c\80\40\48\3c\a0\41\d5\83\a7\26\23\13\a8\16\47\bc\47\4b\f1\c3\81\0a\21\ee\2f\99\00\a7\74\7d\45\81\86\17\ea\6c\2e\8c\81\2e\f3\53\34\f1\ff\46\64\74\81\48\52\f2\fd\f6\8d\2a\28\a2\d4\e1\0f\48\79\3a\c6\d6\ff\74\d4\f1\f1\53\4e\6e\91\58\9a\39\20\6a\00\3e\b0\a9\41\a8\fb\f4\99\50\4b\ee\4b\cb\e4\98\17\15\01\ac\2d\40\22\da\05\a3\9b\f8\0f\6a\ec\6f\ec\a6\c7\52\65\8e\f5\24\63\64\3d\17\1d\be\66\6a\65\a2\a8\5d\8e\6f\67\81\9a\fc\e1\3e\7d\e2\ae\02\9a\ad\5f\09\46\c0\3e\e7\12\8e\f0\99\e9\80\30\a8\98\21\03\e1\3c\07\76\d9\0e\11\a9\41\e4\61\1f\61\28\95\db\9d\dc\42\0b\52\86\51\d0\c5\87\88\88\7f\37\c4\ce\e6\79\a2\5b\86\f9\01\42\15\b0\71\21\b6\5e\91\3a\3d\a5\d5\01\8d\3b\28\de\c7\6a\17\29\84\ea\bf\d0\26\dc\7d\81\9b\41\aa\c4\cc\1a\73\46\2d\7e\61\21\c1\40\1e\11\d0\cd\31\89\6c\8c\d7\35\0b\ae\3e\20\28\30\a1\e9\d7\e4\2e\77\29\2b\fc\ec\98\ba\8d\f0\04\62\ff\fc\6d\c2\ad\dc\7f\41\25\9f\d0\77\c5\5d\70\af\a6\18\08\3c\32\8a\4b\41\1c\4b\d6\2d\ad\6b\08\74\36\f9\8d\7a\88\f5\ce\a9\3b\e7\d7\46\73\10\92\fc\ef\28\5d\ff\4b\20\2f\8f\cc\44\c6\e5\15\81\19\e9\5c\0e\db\7a\05\f9\9a\70\3a\23\03\9f\2a\18\ba\df\a3\d3\10\a8\86\0a\51\ee\d1\0f\8e\2a\a0\bb\4a\0c\fb\2b\50\79\5e\5a\9b\ed\bd\15\37\5f\aa\06\27\d2\f9\2e\25\de\e7\3e\2b\2c\5f\e7\ce\7f\e1\2f\9d\a8\20\19\d5\05\66\ef\2e\c0\96\49\9d\93\36\69\d2\46\1e\4a\18\dc\01\a0\f9\92\09\5e\f2\d6\86\57\5f\3f\86\8f\40\bb\f4\01\d3\8a\5d\cb\10\9f\8f\40\35\e2\0e\a2\c3\5e\29\f0\fc\b7\3a\29\ce\6d\52\1c\6b\44\9b\12\30\5d\fd\87\7b\1f\d0\b8\bf\10\33\e8\f2\77\7d\e0\18\d2\a2\37\c9\06\64\17\9c\0f\6a\59\38\68\21\11\52\54\2c\cf\1e\14\d8\48\7c\1f\95\ce\4c\23\cd\1f\90\2a\19\be\60\d5\8f\4f\ff\02\2e\da\36\75\1a\c0\cc\94\6e\e1\3d\b3\22\a8\5b\e6\ee\4e\4e\4f\f9\ce\c4\cd\55\d2\90\58\59\8d\ff\d3\cd\ba\7a\db\a7\1e\95\01\b0\fb\97\07\48\67\f4\09\cc\08\5e\ed\17\03\e9\1c\d7\8f\53\ad\c4\8a\eb\c3\bf\00\13\5e\c3\f8\df\be\73\b8\4f\0d\01\a1\ac\db\25\82\1b\43\c4\97\7c\be\fb\52\63\85\0f\56\5a\b0\3a\03\f6\12\b8\c8\65\e2\fe\b7\8e\3e\81\33\9f\92\71\b1\44\a3\1b\f2\02\7e\b7\c4\08\ab\e3\ba\43\f8\f3\89\3c\99\a8\f9\3c\7f\6a\be\e7\bd\de\3b\23\3a\5c\8e\b1\ea\1c\57\8f\30\ac\0b\41\ff\42\dc\bf\9b\5a\c4\8b\cc\48\b6\97\38\a7\e4\41\00\28\59\56\6e\0d\c3\fc\53\9d\fe\62\2f\94\38\98\fc\5d\b8\be\0e\35\66\1e\c5\38\a1\9c\89\c6\73\92\57\93\d7\d8\44\67\99\b7\93\7b\13\b9\2e\e9\c3\50\f2\4f\7f\66\0c\ee\e4\e2\9b\b4\83\56\69\fb\b2\54\d3\f4\d6\76\f0\2c\1a\0f\bc\16\9d\2c\90\7f\df\5f\eb\13\6c\0f\86\07\25\06\84\10\a8\d8\88\b8\c5\1e\81\10\ed\83\e1\8d\b4\79\6c\d3\0f\36\4a\49\71\b9\a5\f3\d5\94\16\02\52\27\54\27\45\00\e1\a9\1a\3a\ad\1b\63\7f\4b\8f\a1\f5\d1\1a\05\3d\b1\1a\0b\1a\f1\a9\8c\5a\10\dc\89\b9\f4\8f\69\ae\61\cd\ed\fd\b9\85\a0\6b\8f\0c\a4\0e\8e\48\da\d4\21\3a\d2\2b\f4\eb\84\72\7f\53\b1\0c\84\ab\2d\e6\0e\76\77\c9\fb\e3\e6\5b\90\dc\19\61\1e\51\43\de\80\ac\06\e5\3f\73\c9\39\d8\88\c4\a4\1f\b6\46\be\46\26\fe\b3\92\93\e7\1b\82\89\be\f3\c7\88\8a\33\dd\ed\c4\97\6c\85\6e\70\df\01\07\de\d5\87\0c\9d\9e\8c\eb\73\dd\c5\41\23\8f\f6\30\62\06\64\7b\b7\79\aa\34\af\16\60\13\76\40\3a\e1\64\89\d5\d5\3a\2c\ca\cd\c4\cd\f1\ad\d6\da\a3\34\32\6a\ff\b0\45\b0\85\c0\44\b0\b2\0f\c2\3f\17\2c\03\3d\f3\88\c5\8b\e7\db\dc\20\30\b8\af\1a\01\96\7d\95\ff\f9\28\28\76\87\a9\29\6c\de\04\0e\c6\33\5c\db\d8\7b\40\7b\a7\bb\9e\57\07\79\d4\c8\14\03\5a\32\69\4f\9b\5f\bc\12\43\7f\de\fb\31\93\ac\a5\ec\e8\86\1a\07\e2\e1\c2\4a\4f\f7\c4\c7\e2\61\50\f4\75\e4\9e\35\0a\0d\13\48\c8\41\fe\30\5f\b3\73\46\7a\00\16\71\8c\c4\6b\80\9d\98\4e\9d\1e\55\69\4e\03\b7\49\14\7c\7a\c0\a1\4a\cf\e8\30\49\50\b3\a9\a4\59\15\99\6a\08\1b\43\94\24\29\98\c3\ab\1e\e3\38\17\e6\6d\a0\14\e2\c3\fe\e2\c4\67\34\a7\c8\5a\d6\8b\61\6a\a1\da\ad\03\56\3d\7b\de\00\33\3b\14\b2\49\34\9b\72\45\8e\8c\09\e1\78\99\27\7c\d7\c9\76\2f\e0\17\3b\a1\69\3c\ac\69\0d\d2\0b\db\15\64\e7\48\79\13\8e\b8\04\e4\59\68\f2\4d\4a\1b\d7\d3\1d\ed\d8\37\19\3c\3f\ae\80\89\00\28\82\b7\bd\fa\5a\ad\95\a2\88\19\40\1a\49\3e\4d\4a\ff\0a\08\37\cc\83\ca\5b\4f\03\44\9a\10\f6\ca\ef\8a\43\70\9e\5e\ac\cb\c6\96\2d\01\2a\be\ab\ff\95\8d\29\7b\95\3f\b6\37\03\b4\30\d1\39\73\1f\bc\ad\be\c1\22\d3\3f\02\4f\af\f8\0e\27\da\68\75\ee\04\6e\5a\14\d5\bb\57\0b\23\2d\4d\2a\28\0c\3c\48\54\92\0b\45\c3\7c\94\f4\38\52\d7\7a\a3\39\f7\fb\da\f5\7c\88\dc\be\ab\61\7f\c1\d7\5a\dd\de\a5\47\c2\fb\f3\e0\4b\42\65\27\7a\dc\a0\f3\0b\ac\a3\a6\94\00\00\ac\20\81\00\1a\20\92\01\1e\20\26\20\20\20\21\20\c6\02\30\20\60\01\39\20\52\01\8d\00\7d\01\8f\00\90\00\18\20\19\20\1c\20\1d\20\22\20\13\20\14\20\dc\02\22\21\61\01\3a\20\53\01\9d\00\7e\01\78\01\aa\aa\66\66\24\49\e3\38\c0\80\00\00\e0\80\80\00\f0\80\80\80")
(func (export "input_ptr") (result i32) (i32.const 412112))
(func (export "input_utf8_cap") (result i32) (i32.const 1048576))
(func (export "output_utf8_cap") (result i32) (i32.const 1258298))
;; A code point as UTF-8 bytes in a word, low byte first; their count goes to $ulen.
;; The bits are laid out as four bytes, then the unused leading ones are shifted out.
(func $utf8 (param $v i32) (result i32)
(local $n i32)
(global.set $ulen (local.tee $n
(i32.add (i32.add (i32.add (i32.const 1)
(i32.gt_u (local.get $v) (i32.const 0x7F)))
(i32.gt_u (local.get $v) (i32.const 0x7FF)))
(i32.gt_u (local.get $v) (i32.const 0xFFFF)))))
(if (result i32) (i32.eq (local.get $n) (i32.const 1))
(then (local.get $v))
(else (i32.or
(i32.shr_u
(i32.or (i32.or (i32.or
(i32.shr_u (local.get $v) (i32.const 18))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 12)) (i32.const 0x3F)) (i32.const 8)))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 6)) (i32.const 0x3F)) (i32.const 16)))
(i32.shl (i32.and (local.get $v) (i32.const 0x3F)) (i32.const 24)))
(i32.sub (i32.const 32) (i32.shl (local.get $n) (i32.const 3))))
(i32.load offset=5936 (i32.shl (local.get $n) (i32.const 2)))))))
;; Unpacks one symbol of $nbits bits with an adaptive binary range coder (the LZMA one).
;; ctx holds $nctx4 / 4 contexts. Each has a model entry of 16 bits: a 12-bit probability
;; (stored XOR 0x800, so zeroed memory means one half) above a 4-bit count of its uses.
;; The entries' probabilities are combined by logistic mixing, as in the PAQ compressors:
;; p = squash(sum of weight * stretch(p_i)), stretch(p) = ln(p / (1 - p)), and after the
;; bit is known each weight moves by error * stretch(p_i). $w picks the set of weights.
(func $sym (param $w i32) (param $nctx4 i32) (param $nbits i32) (result i32)
(local $node i32) (local $top i32) (local $k i32) (local $s i32) (local $e i32)
(local $r i32) (local $dot i32) (local $p i32) (local $bit i32)
(local.set $node (i32.const 1))
(local.set $top (i32.shl (i32.const 1) (local.get $nbits)))
(loop $bits
(local.set $dot (i32.const 0))
(local.set $k (i32.const 0))
(loop $vote
(i32.store offset=6000 (local.get $k) (local.tee $s
(i32.and (i32.shr_u
(i32.mul
(i32.add (i32.load offset=5968 (local.get $k)) (i32.mul (local.get $node) (i32.const 0x2545F491)))
(i32.const 0x9E3779B1))
(i32.const 14)) (i32.const -2))))
(i32.store offset=6032 (local.get $k) (local.tee $e
(i32.load16_s offset=30816 (i32.xor
(i32.and (i32.shr_u (i32.load16_u offset=149968 (local.get $s)) (i32.const 3)) (i32.const -2))
(i32.const 0x1000)))))
;; Weights are 16.16 fixed point, stored less 16384 so that zeroed memory is 1/4.
(local.set $dot (i32.add (local.get $dot) (i32.mul (local.get $e)
(i32.add (i32.load offset=6064 (i32.add (local.get $w) (local.get $k))) (i32.const 16384)))))
(br_if $vote (i32.lt_u (local.tee $k (i32.add (local.get $k) (i32.const 4))) (local.get $nctx4))))
;; $p: 12-bit probability that the bit is 1, from 1 to 4095.
(local.set $dot (i32.add (i32.shr_s (local.get $dot) (i32.const 16)) (i32.const 2047)))
(local.set $dot (select (local.get $dot) (i32.const 0) (i32.gt_s (local.get $dot) (i32.const 0))))
(local.set $r (i32.mul (i32.shr_u (global.get $range) (i32.const 12))
(local.tee $p (i32.load16_u offset=22624 (i32.shl
(select (local.get $dot) (i32.const 4094) (i32.lt_u (local.get $dot) (i32.const 4094)))
(i32.const 1))))))
(if (local.tee $bit (i32.lt_u (global.get $code) (local.get $r)))
(then (global.set $range (local.get $r)))
(else
(global.set $code (i32.sub (global.get $code) (local.get $r)))
(global.set $range (i32.sub (global.get $range) (local.get $r)))))
(loop $norm
(if (i32.lt_u (global.get $range) (i32.const 0x1000000)) (then
(global.set $range (i32.shl (global.get $range) (i32.const 8)))
(global.set $code (i32.or (i32.shl (global.get $code) (i32.const 8)) (i32.load8_u (global.get $in))))
(global.set $in (i32.add (global.get $in) (i32.const 1)))
(br $norm))))
;; $p: the error. Move each weight by error * input, and each entry toward the bit
;; just seen by 2 / (2n + 3) after n uses.
(local.set $p (i32.sub (i32.shl (local.get $bit) (i32.const 12)) (local.get $p)))
(local.set $k (i32.const 0))
(loop $learn
(i32.store offset=6064 (local.tee $s (i32.add (local.get $w) (local.get $k)))
(i32.add (i32.load offset=6064 (local.get $s)) (i32.shr_s
(i32.mul (i32.load offset=6032 (local.get $k)) (local.get $p))
(i32.const 11))))
(local.set $r (i32.xor (i32.shr_u
(local.tee $e (i32.load16_u offset=149968 (local.tee $s (i32.load offset=6000 (local.get $k)))))
(i32.const 4)) (i32.const 0x800)))
(local.set $e (i32.and (local.get $e) (i32.const 15)))
(i32.store16 offset=149968 (local.get $s) (i32.or
(i32.shl
(i32.xor
(i32.add (local.get $r) (i32.shr_s
(i32.mul
(i32.sub (i32.shl (local.get $bit) (i32.const 12)) (local.get $r))
(i32.load16_u offset=5936 (i32.shl (local.get $e) (i32.const 1))))
(i32.const 16)))
(i32.const 0x800))
(i32.const 4))
(i32.add (local.get $e) (i32.lt_u (local.get $e) (i32.const 3)))))
(br_if $learn (i32.lt_u (local.tee $k (i32.add (local.get $k) (i32.const 4))) (local.get $nctx4))))
(br_if $bits (i32.lt_u
(local.tee $node (i32.add (i32.shl (local.get $node) (i32.const 1)) (local.get $bit)))
(local.get $top))))
(i32.sub (local.get $node) (local.get $top)))
;; Unpacks the entity list into the lookup tables. Entities are ordered by code point, so
;; a value is a small step from the one before. A name is coded character by character
;; from six contexts: the previous one, two and three characters; a match model that
;; predicts the character that followed the last place the previous two were seen; and
;; two that look at the same position in the previous entity's name, since neighbours
;; in code point order are often named alike (Afr, Bfr; Acy, Bcy; Aacute, Acirc).
(func $init
(local $r i32) (local $cp i32) (local $nl i32) (local $hn i32) (local $d i32) (local $vn i32)
(local $legacy i32) (local $n i32) (local $h i32) (local $mp i32) (local $ml i32) (local $c i32)
(local $ep i32) (local $val i64) (local $key i64)
(local $ps i32) (local $start i32) (local $pc i32) (local $e f64)
;; Empty keys in fast and leg, and the 0xFF half of len_mask, in one fill.
(memory.fill (i32.const 79504) (i32.const 255) (i32.const 70432))
;; squash[x + 2047] = 4096 / (1 + e^(-x / 256)) rounded, for x = -2047..2047, and
;; stretch, its inverse, filled in as squash rises. Both lie in `pos` until unpacking is done.
(local.set $e (f64.const 0x1.732ac33de5528p+11))
(loop $x
(i32.store16 offset=22624 (i32.shl (local.get $n) (i32.const 1)) (local.tee $c
(i32.shr_u (i32.add (i32.trunc_f64_u (f64.div (f64.convert_i32_u (i32.const 8192))
(f64.add (f64.convert_i32_u (i32.const 1)) (local.get $e)))) (i32.const 1)) (i32.const 1))))
(loop $fill
(if (i32.le_u (local.get $h) (local.get $c)) (then
(i32.store16 offset=30816 (i32.shl (local.get $h) (i32.const 1)) (i32.sub (local.get $n) (i32.const 2047)))
(local.set $h (i32.add (local.get $h) (i32.const 1)))
(br $fill))))
(local.set $e (f64.mul (local.get $e) (f64.const 0x1.fe00ffaabffbcp-1)))
(br_if $x (i32.lt_u (local.tee $n (i32.add (local.get $n) (i32.const 1))) (i32.const 4095))))
(local.set $r (i32.const 2125))
(local.set $hn (i32.const 1))
(loop $entity
;; Step from the previous code point: its bit length, then the bits below the top one.
(i32.store (i32.const 5968) (i32.const 1048576))
(if (i32.gt_u (local.tee $d (call $sym (i32.const 0) (i32.const 4) (i32.const 5))) (i32.const 1)) (then
(i32.store (i32.const 5968) (i32.add (i32.const 2097152) (local.get $d)))
(local.set $d (i32.add
(i32.shl (i32.const 1) (local.tee $d (i32.sub (local.get $d) (i32.const 1))))
(call $sym (i32.const 0) (i32.const 4) (local.get $d))))))
(local.set $val (i64.extend_i32_u (call $utf8
(local.tee $cp (i32.add (local.get $cp) (local.get $d))))))
(local.set $vn (global.get $ulen))
;; A few values have a second code point.
(i32.store (i32.const 5968) (i32.add (i32.const 3145728) (i32.eqz (local.get $d))))
(if (call $sym (i32.const 0) (i32.const 4) (i32.const 1)) (then
(i32.store (i32.const 5968) (i32.const 4194304))
(local.set $val (i64.or (local.get $val) (i64.shl
(i64.extend_i32_u (call $utf8 (call $sym (i32.const 0) (i32.const 4) (i32.const 16))))
(i64.extend_i32_u (i32.shl (local.get $vn) (i32.const 3))))))
(local.set $vn (i32.add (local.get $vn) (global.get $ulen)))))
(local.set $val (i64.or (local.get $val)
(i64.shl (i64.extend_i32_u (local.get $vn)) (i64.const 56))))
(i32.store (i32.const 5968) (i32.add (i32.const 5242880) (i32.lt_u (local.get $cp) (i32.const 256))))
(local.set $legacy (call $sym (i32.const 0) (i32.const 4) (i32.const 1)))
;; Names use a 6-bit alphabet: 0 ends the name, then digits, capitals, small letters.
(memory.fill (i32.const 6192) (i32.const 0) (i32.const 40))
(local.set $n (i32.const 0))
(local.set $h (i32.const 0))
(local.set $ml (i32.const 0))
(local.set $ps (local.get $start))
(local.set $start (local.get $hn))
(loop $char
(i32.store (i32.const 5968) (i32.add (i32.const 8388608) (i32.and (local.get $h) (i32.const 63))))
(i32.store (i32.const 5972) (i32.add (i32.const 9437184) (i32.and (local.get $h) (i32.const 4095))))
(i32.store (i32.const 5976) (i32.add (i32.add (i32.const 13631488)
(i32.shl (select (i32.load8_u offset=39072 (local.get $mp)) (i32.const 0) (local.get $ml)) (i32.const 4)))
(local.tee $ep (select (local.get $ml) (i32.const 3) (i32.lt_u (local.get $ml) (i32.const 3))))))
(i32.store (i32.const 5980) (i32.add (i32.const 10485760) (i32.and (local.get $h) (i32.const 0x3FFFF))))
;; $pc: the character at this position in the previous entity's name (or, past its
;; end, whatever follows it in hist).
(i32.store (i32.const 5984) (i32.add (i32.add (i32.const 14680064)
(local.tee $pc (i32.shl (i32.load8_u offset=39072 (i32.add (local.get $ps) (local.get $n))) (i32.const 6))))
(i32.and (local.get $h) (i32.const 63))))
(i32.store (i32.const 5988) (i32.add (i32.add (i32.add (i32.const 17825792) (local.get $pc))
(i32.shl (select (local.get $n) (i32.const 3) (i32.lt_u (local.get $n) (i32.const 3))) (i32.const 2)))
(select (local.get $d) (i32.const 3) (i32.lt_u (local.get $d) (i32.const 3)))))
;; One set of weights for each state of the match model; set 0 is for the fields above.
(local.set $c (call $sym (i32.mul (i32.add (local.get $ep) (i32.const 1)) (i32.const 24))
(i32.const 24) (i32.const 6)))
(if (i32.and (i32.ne (local.get $ml) (i32.const 0))
(i32.eq (i32.load8_u offset=39072 (local.get $mp)) (local.get $c)))
(then
(local.set $ml (i32.add (local.get $ml) (i32.const 1)))
(local.set $mp (i32.add (local.get $mp) (i32.const 1))))
(else (local.set $ml (i32.const 0))))
(i32.store8 offset=39072 (local.get $hn) (local.get $c))
(local.set $hn (i32.add (local.get $hn) (i32.const 1)))
(if (local.get $c) (then
(i32.store8 offset=6192 (local.get $n) (i32.add (local.get $c)
(select (i32.const 47) (select (i32.const 54) (i32.const 60) (i32.lt_u (local.get $c) (i32.const 37)))
(i32.lt_u (local.get $c) (i32.const 11)))))
(local.set $h (i32.or (i32.shl (local.get $h) (i32.const 6)) (local.get $c)))
(if (i32.ge_u (local.tee $n (i32.add (local.get $n) (i32.const 1))) (i32.const 2)) (then
(local.set $c (i32.load16_u offset=14432
(local.tee $ep (i32.shl (i32.and (local.get $h) (i32.const 4095)) (i32.const 1)))))
(if (i32.and (i32.eqz (local.get $ml)) (i32.ne (local.get $c) (i32.const 0))) (then
(local.set $mp (local.get $c))
(local.set $ml (i32.const 1))))
(i32.store16 offset=14432 (local.get $ep) (local.get $hn))))
(br $char))))
(if (i32.le_u (local.get $n) (i32.const 7))
(then
;; fast: the key is the name and its `;`.
(local.set $key (i64.or (i64.load (i32.const 6192))
(i64.shl (i64.const 59) (i64.extend_i32_u (i32.shl (local.get $n) (i32.const 3))))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xA59D054B12F5B905)) (i64.const 52))) (i32.const 4)))
(loop $probe
(if (i64.ne (i64.load offset=79504 (local.get $ep)) (i64.const -1)) (then
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe))))
(i64.store offset=79504 (local.get $ep) (local.get $key))
(i64.store offset=79512 (local.get $ep) (local.get $val))
(if (local.get $legacy) (then
;; leg: the length is part of the key, so a NUL after a shorter name cannot match.
(local.set $key (i64.or (i64.load (i32.const 6192))
(i64.shl (i64.extend_i32_u (local.get $n)) (i64.const 56))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xF880D97D1854E551)) (i64.const 56))) (i32.const 4)))
(loop $probe
(if (i64.ne (i64.load offset=145552 (local.get $ep)) (i64.const -1)) (then
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe))))
(i64.store offset=145552 (local.get $ep) (local.get $key))
(i64.store offset=145560 (local.get $ep) (local.get $val))
(if (i32.lt_u
(i32.load8_u offset=6240 (local.tee $ep (i32.shr_u
(i32.mul (i32.load16_u (i32.const 6192)) (i32.const 0x9E3779B1)) (i32.const 20))))
(local.get $n))
(then (i32.store8 offset=6240 (local.get $ep) (local.get $n)))))))
(else
;; longs: record number $nl (from 1) is at 55168 + 48 * $nl.
(memory.copy
(i32.add (i32.const 55168) (local.tee $ep
(i32.mul (local.tee $nl (i32.add (local.get $nl) (i32.const 1))) (i32.const 48))))
(i32.const 6192) (i32.const 32))
(i64.store offset=55200 (local.get $ep) (local.get $val))
(i32.store offset=55208 (local.get $ep) (local.get $n))
(local.set $ep (i32.wrap_i64 (i64.shr_u (i64.mul
(i64.add
(i64.xor (i64.load (i32.const 6192))
(i64.rotl (i64.load offset=6184 (local.get $n)) (i64.const 29)))
(i64.extend_i32_u (local.get $n)))
(i64.const 0xA0C2995F40498CB3)) (i64.const 53))))
(loop $probe
(if (i32.load16_u offset=10336 (i32.shl (local.get $ep) (i32.const 1))) (then
(local.set $ep (i32.and (i32.add (local.get $ep) (i32.const 1)) (i32.const 2047)))
(br $probe))))
(i32.store16 offset=10336 (i32.shl (local.get $ep) (i32.const 1)) (local.get $nl))))
(br_if $entity (local.tee $r (i32.sub (local.get $r) (i32.const 1))))))
(func (export "render") (param $n i32) (result i64)
(local $size i32) (local $e i32) (local $o i32) (local $base i32) (local $lim i32)
(local $out i32) (local $q i32) (local $i i32) (local $len i32) (local $j i32)
(local $hex i32) (local $p i32) (local $v i32) (local $k i32) (local $ep i32) (local $h i32)
(local $w i64) (local $mm i64) (local $d i64) (local $t i64) (local $letter i64)
(local $x i64) (local $key i64) (local $val i64) (local $kb i64) (local $high i64)
(local $zero v128) (local $amp v128) (local $s0 v128) (local $s1 v128) (local $m0 v128) (local $m1 v128)
;; len_mask is filled by $init, so its first byte says whether the tables exist yet.
(if (i32.eqz (i32.load8_u (i32.const 149904))) (then (call $init)))
(local.set $size (select (local.get $n) (i32.const 1048576) (i32.lt_u (local.get $n) (i32.const 1048576))))
;; 64 zero bytes after the input: nothing stale can be mistaken for part of a reference.
(v128.store offset=412112 (local.get $size) (local.get $zero))
(v128.store offset=412128 (local.get $size) (local.get $zero))
(v128.store offset=412144 (local.get $size) (local.get $zero))
(v128.store offset=412160 (local.get $size) (local.get $zero))
(local.set $amp (i8x16.splat (i32.const 38)))
(local.set $high (i64.const 0x8080808080808080))
;; $e: end of the last reference in the input. $o: bytes of output so far.
(block $done
(loop $window
(br_if $done (i32.ge_u (local.get $base) (local.get $size)))
(local.set $lim (select (i32.add (local.get $base) (i32.const 4096)) (local.get $size)
(i32.gt_u (i32.sub (local.get $size) (local.get $base)) (i32.const 4096))))
;; Stage 1: list the position of every `&` in the window, 64 bytes at a time. The
;; first four positions of a block are written without looking at how many there
;; are; entries past the count are overwritten or ignored.
(local.set $out (i32.const 0))
(loop $scan
(local.set $mm (i64.or (i64.or (i64.or
(i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412112 (local.get $base)) (local.get $amp))))
(i64.shl (i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412128 (local.get $base)) (local.get $amp)))) (i64.const 16)))
(i64.shl (i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412144 (local.get $base)) (local.get $amp)))) (i64.const 32)))
(i64.shl (i64.extend_i32_u (i8x16.bitmask (i8x16.eq (v128.load offset=412160 (local.get $base)) (local.get $amp)))) (i64.const 48))))
(local.set $k (i32.add (local.get $out) (i32.shl (i32.wrap_i64 (i64.popcnt (local.get $mm))) (i32.const 2))))
(i32.store offset=22624 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1))))
(i32.store offset=22628 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1))))
(i32.store offset=22632 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1))))
(i32.store offset=22636 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(if (i64.ne (local.tee $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1)))) (i64.const 0)) (then
(loop $more
(i32.store offset=22640 (local.get $out) (i32.add (local.get $base) (i32.wrap_i64 (i64.ctz (local.get $mm)))))
(local.set $out (i32.add (local.get $out) (i32.const 4)))
(br_if $more (i64.ne (local.tee $mm (i64.and (local.get $mm) (i64.sub (local.get $mm) (i64.const 1)))) (i64.const 0))))))
(local.set $out (local.get $k))
(br_if $scan (i32.lt_u (local.tee $base (i32.add (local.get $base) (i32.const 64))) (local.get $lim))))
;; Stage 2: for each position, copy the text before it and decode the reference.
(local.set $q (i32.const 0))
(if (local.get $out) (then
(loop $ref
;; $i: position of this `&`; it becomes the end of the reference.
(local.set $len (i32.sub (local.tee $i (i32.load offset=22624 (local.get $q))) (local.get $e)))
(local.set $q (i32.add (local.get $q) (i32.const 4)))
(v128.store offset=149968 (local.get $o) (v128.load offset=412112 (local.get $e)))
(v128.store offset=149984 (local.get $o) (v128.load offset=412128 (local.get $e)))
(if (i32.gt_u (local.get $len) (i32.const 32)) (then
(local.set $j (i32.const 32))
(loop $copy
(v128.store offset=149968 (i32.add (local.get $o) (local.get $j))
(v128.load offset=412112 (i32.add (local.get $e) (local.get $j))))
(br_if $copy (i32.lt_u (local.tee $j (i32.add (local.get $j) (i32.const 16))) (local.get $len))))))
(local.set $o (i32.add (local.get $o) (local.get $len)))
;; $w: the 8 bytes after the `&`.
(local.set $w (i64.load offset=412113 (local.get $i)))
(block $next
(block $bare
(block $legacy
(if (i32.eq (i32.and (i32.wrap_i64 (local.get $w)) (i32.const 255)) (i32.const 35)) (then
;; Numeric. Decimal and hexadecimal share one path: classify 8 bytes,
;; take the digits before the first other byte, and fold them pairwise.
(local.set $hex (i32.eq
(i32.or (i32.and (i32.wrap_i64 (i64.shr_u (local.get $w) (i64.const 8))) (i32.const 255)) (i32.const 32))
(i32.const 120)))
(local.set $t (i64.xor
(local.tee $d (i64.load offset=412112
(local.tee $p (i32.add (i32.add (local.get $i) (i32.const 2)) (local.get $hex)))))
(i64.const 0x3030303030303030)))
;; $x: 0x80 in each byte that is a letter a-f or A-F.
(local.set $x (i64.and
(local.tee $key (i64.or (local.get $d) (i64.const 0x2020202020202020)))
(i64.xor (local.get $high) (i64.const -1))))
(local.set $letter (i64.and
(i64.and
(i64.add (local.get $x) (i64.const 0x1F1F1F1F1F1F1F1F))
(i64.xor
(i64.or (i64.add (local.get $x) (i64.const 0x1919191919191919)) (local.get $key))
(i64.const -1)))
(local.get $high)))
;; $t: 0x80 in each byte that is not a digit of this reference.
(if (i64.ne
(local.tee $t (i64.and
(i64.and
(i64.or
(i64.add (i64.and (local.get $t) (i64.xor (local.get $high) (i64.const -1)))
(i64.const 0x7676767676767676))
(local.get $t))
(local.get $high))
(i64.xor
(select (local.get $letter) (i64.const 0) (local.get $hex))
(i64.const -1))))
(i64.const 0))
(then
;; $kb: bits of digits. None: the `&` stands for itself.
(br_if $bare (i64.eqz (local.tee $kb (i64.and (i64.ctz (local.get $t)) (i64.const 56)))))
(local.set $x (i64.shl
(i64.add (i64.and (local.get $d) (i64.const 0x0F0F0F0F0F0F0F0F))
(i64.mul (i64.shr_u (local.get $letter) (i64.const 7)) (i64.const 9)))
(i64.sub (i64.const 64) (local.get $kb))))
(local.set $x (i64.and
(i64.add (i64.mul (local.get $x) (select (i64.const 16) (i64.const 10) (local.get $hex)))
(i64.shr_u (local.get $x) (i64.const 8)))
(i64.const 0x00FF00FF00FF00FF)))
(local.set $x (i64.and
(i64.add (i64.mul (local.get $x) (select (i64.const 256) (i64.const 100) (local.get $hex)))
(i64.shr_u (local.get $x) (i64.const 16)))
(i64.const 0x0000FFFF0000FFFF)))
(local.set $v (i32.wrap_i64
(i64.add (i64.mul (local.get $x) (select (i64.const 65536) (i64.const 10000) (local.get $hex)))
(i64.shr_u (local.get $x) (i64.const 32)))))
(local.set $p (i32.add (local.get $p) (i32.wrap_i64 (i64.shr_u (local.get $kb) (i64.const 3))))))
(else
;; Eight or more digits: one at a time, saturating past U+10FFFF.
(local.set $v (i32.const 0))
(local.set $k (select (i32.const 16) (i32.const 10) (local.get $hex)))
(block $end
(loop $digit
(if (i32.gt_u
(local.tee $h (i32.sub (i32.load8_u offset=412112 (local.get $p)) (i32.const 48)))
(i32.const 9))
(then
(if (i32.lt_u
(local.tee $h (i32.sub (i32.or (i32.load8_u offset=412112 (local.get $p)) (i32.const 32)) (i32.const 87)))
(i32.const 10))
(then (local.set $h (i32.const 16))))))
(br_if $end (i32.ge_u (local.get $h) (local.get $k)))
(if (i32.gt_u
(local.tee $v (i32.add (i32.mul (local.get $v) (local.get $k)) (local.get $h)))
(i32.const 0x10FFFF))
(then (local.set $v (i32.const 0x110000))))
(local.set $p (i32.add (local.get $p) (i32.const 1)))
(br $digit)))))
(local.set $i (i32.add (local.get $p)
(i32.eq (i32.load8_u offset=412112 (local.get $p)) (i32.const 59))))
;; 0x80-0x9F use the Windows-1252 table; 0, surrogates and values past
;; U+10FFFF become U+FFFD.
(if (i32.lt_u (i32.sub (local.get $v) (i32.const 0x80)) (i32.const 0x20))
(then (local.set $v (i32.load16_u offset=5616 (i32.shl (local.get $v) (i32.const 1)))))
(else
(if (i32.or
(i32.ge_u (i32.sub (local.get $v) (i32.const 1)) (i32.const 0x10FFFF))
(i32.lt_u (i32.sub (local.get $v) (i32.const 0xD800)) (i32.const 0x800)))
(then (local.set $v (i32.const 0xFFFD))))))
;; UTF-8, as in $utf8 but in line: a call here would cost the loop its registers.
(local.set $k
(i32.add (i32.add (i32.add (i32.const 1)
(i32.gt_u (local.get $v) (i32.const 0x7F)))
(i32.gt_u (local.get $v) (i32.const 0x7FF)))
(i32.gt_u (local.get $v) (i32.const 0xFFFF))))
(i32.store offset=149968 (local.get $o)
(select
(local.get $v)
(i32.or
(i32.shr_u
(i32.or (i32.or (i32.or
(i32.shr_u (local.get $v) (i32.const 18))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 12)) (i32.const 0x3F)) (i32.const 8)))
(i32.shl (i32.and (i32.shr_u (local.get $v) (i32.const 6)) (i32.const 0x3F)) (i32.const 16)))
(i32.shl (i32.and (local.get $v) (i32.const 0x3F)) (i32.const 24)))
(i32.sub (i32.const 32) (i32.shl (local.get $k) (i32.const 3))))
(i32.load offset=5936 (i32.shl (local.get $k) (i32.const 2))))
(i32.eq (local.get $k) (i32.const 1))))
(local.set $o (i32.add (local.get $o) (local.get $k)))
(br $next)))
;; Named. $t: 0x80 in the first byte of $w that is `;`.
(local.set $t (i64.xor (local.get $w) (i64.const 0x3B3B3B3B3B3B3B3B)))
(if (i64.ne
(local.tee $t (i64.and
(i64.and (i64.sub (local.get $t) (i64.const 0x0101010101010101)) (i64.xor (local.get $t) (i64.const -1)))
(local.get $high)))
(i64.const 0))
(then
;; Up to 7 bytes: the name and its `;` are the key into fast.
(local.set $key (i64.and (local.get $w)
(i64.sub
(i64.shl (i64.const 2) (i64.add (local.tee $kb (i64.and (i64.ctz (local.get $t)) (i64.const 56))) (i64.const 7)))
(i64.const 1))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xA59D054B12F5B905)) (i64.const 52))) (i32.const 4)))
(loop $probe
(if (i64.eq (local.tee $val (i64.load offset=79504 (local.get $ep))) (local.get $key)) (then
(i64.store offset=149968 (local.get $o) (local.tee $val (i64.load offset=79512 (local.get $ep))))
(local.set $o (i32.add (local.get $o) (i32.wrap_i64 (i64.shr_u (local.get $val) (i64.const 56)))))
(local.set $i (i32.add (i32.add (local.get $i) (i32.const 2))
(i32.wrap_i64 (i64.shr_u (local.get $kb) (i64.const 3)))))
(br $next)))
(br_if $legacy (i64.eq (local.get $val) (i64.const -1)))
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe)))
(else
;; No `;` in 8 bytes: a name of 8 to 31 bytes needs its `;` in the next 24.
(local.set $s0 (v128.load offset=412113 (local.get $i)))
(local.set $s1 (v128.load offset=412129 (local.get $i)))
(if (local.tee $h (i32.or
(i8x16.bitmask (i8x16.eq (local.get $s0) (local.tee $m0 (i8x16.splat (i32.const 59)))))
(i32.shl (i8x16.bitmask (i8x16.eq (local.get $s1) (local.get $m0))) (i32.const 16))))
(then
(local.set $len (i32.ctz (local.get $h)))
(local.set $h (i32.wrap_i64 (i64.shr_u (i64.mul
(i64.add
(i64.xor (local.get $w)
(i64.rotl (i64.load offset=412105 (i32.add (local.get $i) (local.get $len))) (i64.const 29)))
(i64.extend_i32_u (local.get $len)))
(i64.const 0xA0C2995F40498CB3)) (i64.const 53))))
;; Byte j of the 32 loaded at len_mask + 32 - len is 0xFF when j < len.
(local.set $m0 (v128.load offset=149904 (local.tee $k (i32.sub (i32.const 32) (local.get $len)))))
(local.set $m1 (v128.load offset=149920 (local.get $k)))
(block $miss
(loop $slot
(br_if $miss (i32.eqz (local.tee $ep
(i32.load16_u offset=10336 (i32.shl (local.get $h) (i32.const 1))))))
(if (i32.and
(i32.eq
(i32.load offset=55208 (local.tee $ep (i32.mul (local.get $ep) (i32.const 48))))
(local.get $len))
(i32.eqz (v128.any_true (v128.or
(v128.xor (v128.and (local.get $s0) (local.get $m0)) (v128.load offset=55168 (local.get $ep)))
(v128.xor (v128.and (local.get $s1) (local.get $m1)) (v128.load offset=55184 (local.get $ep)))))))
(then
(i64.store offset=149968 (local.get $o) (local.tee $val (i64.load offset=55200 (local.get $ep))))
(local.set $o (i32.add (local.get $o) (i32.wrap_i64 (i64.shr_u (local.get $val) (i64.const 56)))))
(local.set $i (i32.add (i32.add (local.get $i) (i32.const 2)) (local.get $len)))
(br $next)))
(local.set $h (i32.and (i32.add (local.get $h) (i32.const 1)) (i32.const 2047)))
(br $slot))))))))
;; Without `;`: the longest legacy name that is a prefix, longest first.
(local.set $k (i32.load8_u offset=6240 (i32.shr_u
(i32.mul (i32.and (i32.wrap_i64 (local.get $w)) (i32.const 0xFFFF)) (i32.const 0x9E3779B1))
(i32.const 20))))
(loop $try
(br_if $bare (i32.lt_u (local.get $k) (i32.const 2)))
(local.set $key (i64.or
(i64.and (local.get $w)
(i64.sub (i64.shl (i64.const 1) (i64.extend_i32_u (i32.shl (local.get $k) (i32.const 3)))) (i64.const 1)))
(i64.shl (i64.extend_i32_u (local.get $k)) (i64.const 56))))
(local.set $ep (i32.shl (i32.wrap_i64 (i64.shr_u
(i64.mul (local.get $key) (i64.const 0xF880D97D1854E551)) (i64.const 56))) (i32.const 4)))
(loop $probe
(if (i64.eq (local.tee $val (i64.load offset=145552 (local.get $ep))) (local.get $key)) (then
(i64.store offset=149968 (local.get $o) (local.tee $val (i64.load offset=145560 (local.get $ep))))
(local.set $o (i32.add (local.get $o) (i32.wrap_i64 (i64.shr_u (local.get $val) (i64.const 56)))))
(local.set $i (i32.add (i32.add (local.get $i) (i32.const 1)) (local.get $k)))
(br $next)))
(if (i64.ne (local.get $val) (i64.const -1)) (then
(local.set $ep (i32.add (local.get $ep) (i32.const 16)))
(br $probe))))
(local.set $k (i32.sub (local.get $k) (i32.const 1)))
(br $try)))
;; Not a reference: the `&` is copied.
(i32.store8 offset=149968 (local.get $o) (i32.const 38))
(local.set $o (i32.add (local.get $o) (i32.const 1)))
(local.set $i (i32.add (local.get $i) (i32.const 1))))
(local.set $e (local.get $i))
(br_if $ref (i32.lt_u (local.get $q) (local.get $out))))))
(br $window)))
;; Without a reference the input is the output.
(if (i32.eqz (local.get $e)) (then
(return (i64.or (i64.const 1770007562289152) (i64.extend_i32_u (local.get $size))))))
;; Copy the text after the last reference.
(local.set $o (i32.sub (local.get $o) (local.get $e)))
(loop $tail
(if (i32.lt_u (local.get $e) (local.get $size)) (then
(v128.store offset=149968 (i32.add (local.get $o) (local.get $e)) (v128.load offset=412112 (local.get $e)))
(local.set $e (i32.add (local.get $e) (i32.const 16)))
(br $tail))))
(i64.or (i64.const 644107655446528) (i64.extend_i32_u (i32.add (local.get $o) (local.get $size))))))
(; pack.py, which produced the packed entity list:
"""Packs the entity list for unescape.wat: entities ordered by code point, coded with an
adaptive binary range coder. Each bit is predicted from several contexts whose predictions
are combined by a small learned mixer (logistic mixing, as in the PAQ compressors).
$sym and $init in unescape.wat mirror Model, Decoder and Coder 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]
# e^(2047 / 256) and e^(-1 / 256), written out so that every platform uses the same bits.
E0, STEP = float.fromhex('0x1.732ac33de5528p+11'), float.fromhex('0x1.fe00ffaabffbcp-1')
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 tables():
"""squash[x + 2047] = 4096 / (1 + e^(-x / 256)) rounded, for x = -2047..2047, and
stretch, its inverse. Only IEEE multiply, add and divide, so every machine agrees."""
squash, stretch, e, pi = [], [0] * 4096, E0, 0
for x in range(-2047, 2048):
v = (int(8192 / (1 + e)) + 1) >> 1
squash.append(v)
while pi <= v:
stretch[pi] = x
pi += 1
e *= STEP
assert pi == 4096 and squash[0] >= 1
return squash, stretch
class Model:
"""Entries are 16 bits: a 12-bit probability (stored XOR 0x800) and a 4-bit count.
Weight set 4 is for the code point fields; 0 to 3 are for name characters, chosen
by how long the match model has been right."""
def __init__(self, bits=17, limit=3, shift=11, w0=16384, sets=5, nmax=6):
self.t = [0] * (1 << bits)
self.bits, self.limit, self.shift, self.w0 = bits, limit, shift, w0
self.squash, self.stretch = tables()
self.w = [[0] * nmax for _ in range(sets)]
def slots(self, ctxs, node):
return [(((c + node * HASH_A) * HASH_B) & M32) >> (32 - self.bits) for c in ctxs]
def predict(self, slots, ws):
"""12-bit probability that the bit is 1, and the inputs it was mixed from."""
st = [self.stretch[(self.t[s] >> 4) ^ 0x800] for s in slots]
dot = sum((w + self.w0) * x for w, x in zip(self.w[ws], st))
assert abs(dot) < 1 << 31 # the unpacker adds these up in 32 bits
dot >>= 16
return self.squash[min(max(dot, -2047), 2047) + 2047], st
def update(self, slots, ws, st, p, bit):
err = (bit << 12) - p
w = self.w[ws]
for k, s in enumerate(slots):
w[k] += (st[k] * err) >> self.shift
assert abs(w[k]) < 1 << 30
e = self.t[s]
q, n = (e >> 4) ^ 0x800, e & 15
q += (((bit << 12) - q) * RATE[n]) >> 16
self.t[s] = (q ^ 0x800) << 4 | (n + (n < self.limit))
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, self.start = [0], [0] * 4096, 0
def sym(self, ctxs, nbits, ws, value=None):
node = 1
for i in range(nbits - 1, -1, -1):
slots = self.m.slots(ctxs, node)
p, st = self.m.predict(slots, ws)
if self.enc:
b = value >> i & 1
self.enc.bit(p, b)
else:
b = self.dec.bit(p)
self.m.update(slots, ws, st, p, 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, 4, d.bit_length() if rec else None)
if nb > 1:
d = (1 << (nb - 1)) + self.sym([2 * K + nb], nb - 1, 4, d - (1 << (nb - 1)) if rec else None)
else:
d = nb
cp += d
second = 0
if self.sym([3 * K + (d == 0)], 1, 4, len(cps) - 1 if rec else None):
second = self.sym([4 * K], 16, 4, cps[1] if rec else None)
leg = self.sym([5 * K + (cp < 256)], 1, 4, 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.
# prev walks the previous entity's name in step with this one.
h, out, mp, ml, prev = 0, '', 0, 0, self.start
self.start = len(self.hist)
for i in range(64):
pc = self.hist[prev + i]
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),
14 * K + pc * 64 + (h & 63), 17 * K + pc * 64 + min(i, 3) * 4 + min(d, 3)]
c = self.sym(ctxs, 6, min(ml, 3), 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__':
blob = pack()
assert unpack(blob, len(ORDER)) == records()
print('round trip ok', len(blob))
;)