diff options
Diffstat (limited to 'data/extensions/uBlock0@raymondhill.net/js/wasm/biditrie.wat')
| -rw-r--r-- | data/extensions/uBlock0@raymondhill.net/js/wasm/biditrie.wat | 728 |
1 files changed, 728 insertions, 0 deletions
diff --git a/data/extensions/uBlock0@raymondhill.net/js/wasm/biditrie.wat b/data/extensions/uBlock0@raymondhill.net/js/wasm/biditrie.wat new file mode 100644 index 0000000..7a77500 --- /dev/null +++ b/data/extensions/uBlock0@raymondhill.net/js/wasm/biditrie.wat @@ -0,0 +1,728 @@ +;; +;; uBlock Origin - a comprehensive, efficient content blocker +;; Copyright (C) 2019-present Raymond Hill +;; +;; This program is free software: you can redistribute it and/or modify +;; it under the terms of the GNU General Public License as published by +;; the Free Software Foundation, either version 3 of the License, or +;; (at your option) any later version. +;; +;; This program is distributed in the hope that it will be useful, +;; but WITHOUT ANY WARRANTY; without even the implied warranty of +;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +;; GNU General Public License for more details. +;; +;; You should have received a copy of the GNU General Public License +;; along with this program. If not, see {http://www.gnu.org/licenses/}. +;; +;; Home: https://github.com/gorhill/uBlock +;; File: biditrie.wat +;; Description: WebAssembly code used by src/js/biditrie.js +;; How to compile: See README.md in this directory. + +(module +;; +;; module start +;; + +(memory (import "imports" "memory") 1) +(func $extraHandler (import "imports" "extraHandler") (param i32 i32 i32) (result i32)) + +;; Trie container +;; +;; Memory layout, byte offset: +;; const HAYSTACK_START = 0; +;; const HAYSTACK_SIZE = 8192; // i32 / i8 +;; const HAYSTACK_SIZE_SLOT = HAYSTACK_SIZE >>> 2; // 2048 / 8192 +;; const TRIE0_SLOT = HAYSTACK_SIZE_SLOT + 1; // 2049 / 8196 +;; const TRIE1_SLOT = HAYSTACK_SIZE_SLOT + 2; // 2050 / 8200 +;; const CHAR0_SLOT = HAYSTACK_SIZE_SLOT + 3; // 2051 / 8204 +;; const CHAR1_SLOT = HAYSTACK_SIZE_SLOT + 4; // 2052 / 8208 +;; const RESULT_L_SLOT = HAYSTACK_SIZE_SLOT + 5; // 2053 / 8212 +;; const RESULT_R_SLOT = HAYSTACK_SIZE_SLOT + 6; // 2054 / 8216 +;; const RESULT_IU_SLOT = HAYSTACK_SIZE_SLOT + 7; // 2055 / 8220 +;; const TRIE0_START = HAYSTACK_SIZE_SLOT + 8 << 2; // 8224 +;; + +;; +;; Public functions +;; + +;; +;; unsigned int matches(icell, ai) +;; +;; Test whether the trie at icell matches the haystack content at position ai. +;; +(func (export "matches") + (param $icell i32) ;; start offset in haystack + (param $ai i32) ;; offset in haystack + (result i32) ;; result: 0 = no match, 1 = match + (local $char0 i32) + (local $aR i32) + (local $al i32) + (local $bl i32) + (local $x i32) + (local $y i32) + ;; trie index is a uint32 offset, need to convert to uint8 offset + local.get $icell + i32.const 2 + i32.shl + local.set $icell + ;; const buf32 = this.buf32; + ;; const buf8 = this.buf8; + ;; const char0 = buf32[CHAR0_SLOT]; + i32.const 8204 + i32.load align=4 + local.set $char0 + ;; const aR = buf32[HAYSTACK_SIZE_SLOT]; + i32.const 8192 + i32.load align=4 + local.set $aR + ;; let al = ai; + local.get $ai + local.set $al + block $matchFound + block $matchNotFound + ;; for (;;) { + loop $mainLoop + ;; x = buf8[al]; + local.get $al + i32.load8_u + local.set $x + ;; al += 1; + local.get $al + i32.const 1 + i32.add + local.set $al + ;; // find matching segment + ;; for (;;) { + block $nextSegment loop $findSegment + ;; y = buf32[icell+SEGMENT_INFO]; + local.get $icell + i32.load offset=8 align=4 + local.tee $y + ;; bl = char0 + (y & 0x00FFFFFF); + i32.const 0x00FFFFFF + i32.and + local.get $char0 + i32.add + local.tee $bl + ;; if ( buf8[bl] === x ) { + i32.load8_u + local.get $x + i32.eq + if + ;; y = (y >>> 24) - 1; + local.get $y + i32.const 24 + i32.shr_u + i32.const 1 + i32.sub + local.tee $y + ;; if ( n !== 0 ) { + if + ;; x = al + y; + local.get $y + local.get $al + i32.add + local.tee $x + ;; if ( x > aR ) { return 0; } + local.get $aR + i32.gt_u + br_if $matchNotFound + ;; for (;;) { + loop + ;; bl += 1; + local.get $bl + i32.const 1 + i32.add + local.tee $bl + ;; if ( buf8[bl] !== buf8[al] ) { return 0; } + i32.load8_u + local.get $al + i32.load8_u + i32.ne + br_if $matchNotFound + ;; al += 1; + local.get $al + i32.const 1 + i32.add + local.tee $al + ;; if ( al === x ) { break; } + local.get $x + i32.ne + br_if 0 + end + ;; } + end + br $nextSegment + end + ;; icell = buf32[icell+CELL_OR]; + local.get $icell + i32.load offset=4 align=4 + i32.const 2 + i32.shl + local.tee $icell + ;; if ( icell === 0 ) { return 0; } + i32.eqz + br_if $matchNotFound + br $findSegment + ;; } + end end + ;; // next segment + ;; icell = buf32[icell+CELL_AND]; + local.get $icell + i32.load align=4 + i32.const 2 + i32.shl + local.tee $icell + ;; const x = buf32[icell+BCELL_EXTRA]; + i32.load offset=8 align=4 + local.tee $x + ;; if ( x <= BCELL_EXTRA_MAX ) { + i32.const 0x00FFFFFF + i32.le_u + if + ;; if ( x !== 0 && this.matchesExtra(ai, al, x) !== 0 ) { + ;; return 1; + ;; } + local.get $x + if + local.get $ai + local.get $al + local.get $x + call $matchesExtra + br_if $matchFound + end + ;; x = buf32[icell+BCELL_ALT_AND]; + local.get $icell + i32.load offset=4 align=4 + i32.const 2 + i32.shl + local.tee $x + ;; if ( x !== 0 && this.matchesLeft(x, ai, al) !== 0 ) { + if + local.get $x + local.get $ai + local.get $al + call $matchesLeft + br_if $matchFound + ;; } + end + ;; icell = buf32[icell+BCELL_NEXT_AND]; + local.get $icell + i32.load align=4 + i32.const 2 + i32.shl + local.tee $icell + ;; if ( icell === 0 ) { return 0; } + i32.eqz + br_if $matchNotFound + ;; } + end + ;; if ( al === aR ) { return 0; } + local.get $al + local.get $aR + i32.ne + br_if $mainLoop + ;; } + end ;; $mainLoop + end ;; $matchNotFound + i32.const 0 + return + end ;; $matchFound + i32.const 1 + return +) + +;; +;; unsigned int matchesLeft(icell, ar, r) +;; +;; Test whether the trie at icell matches the haystack content at position ai. +;; +(func $matchesLeft + (param $icell i32) ;; start offset in haystack + (param $ar i32) ;; offset of where to start in haystack + (param $r i32) ;; right bound of match so far + (result i32) ;; result: 0 = no match, 1 = match + (local $char0 i32) + (local $bl i32) + (local $br i32) + (local $x i32) + (local $y i32) + ;; const buf32 = this.buf32; + ;; const buf8 = this.buf8; + ;; const char0 = buf32[CHAR0_SLOT]; + i32.const 8204 + i32.load align=4 + local.set $char0 + block $matchFound + block $matchNotFound + ;; for (;;) { + loop $mainLoop + ;; if ( ar === 0 ) { return 0; } + local.get $ar + i32.eqz + br_if $matchNotFound + ;; ar -= 1; + local.get $ar + i32.const 1 + i32.sub + local.tee $ar + ;; x = buf8[ar]; + i32.load8_u + local.set $x + ;; // find matching segment + ;; for (;;) { + block $nextSegment loop $findSegment + ;; y = buf32[icell+SEGMENT_INFO]; + local.get $icell + i32.load offset=8 align=4 + local.tee $y + ;; br = char0 + (y & 0x00FFFFFF); + i32.const 0x00FFFFFF + i32.and + local.get $char0 + i32.add + local.tee $br + ;; y = (y >>> 24) - 1; + local.get $y + i32.const 24 + i32.shr_u + i32.const 1 + i32.sub + local.tee $y + ;; br += y; + i32.add + local.tee $br + ;; if ( buf8[br] === x ) { + i32.load8_u + local.get $x + i32.eq + if + ;; // all characters in segment must match + ;; if ( y !== 0 ) { + local.get $y + if + ;; x = ar - y; + local.get $ar + local.get $y + i32.sub + local.tee $x + ;; if ( x < 0 ) { return 0; } + i32.const 0 + i32.lt_s + br_if $matchNotFound + ;; for (;;) { + loop + ;; ar -= 1; br -= 1; + ;; if ( buf8[ar] !== buf8[br] ) { return 0; } + local.get $ar + i32.const 1 + i32.sub + local.tee $ar + i32.load8_u + local.get $br + i32.const 1 + i32.sub + local.tee $br + i32.load8_u + i32.ne + br_if $matchNotFound + ;; if ( ar === x ) { break; } + local.get $ar + local.get $x + i32.ne + br_if 0 + end + ;; } + end + br $nextSegment + end + ;; icell = buf32[icell+CELL_OR]; + local.get $icell + i32.load offset=4 align=4 + i32.const 2 + i32.shl + local.tee $icell + ;; if ( icell === 0 ) { return 0; } + i32.eqz + br_if $matchNotFound + br $findSegment + ;; } + end end + ;; // next segment + ;; icell = buf32[icell+CELL_AND]; + local.get $icell + i32.load align=4 + i32.const 2 + i32.shl + local.tee $icell + ;; const x = buf32[icell+BCELL_EXTRA]; + i32.load offset=8 align=4 + local.tee $x + ;; if ( x <= BCELL_EXTRA_MAX ) { + i32.const 0x00FFFFFF + i32.le_u + if + ;; if ( x !== 0 && this.matchesExtra(ar, r, x) !== 0 ) { + ;; return 1; + ;; } + local.get $x + if + local.get $ar + local.get $r + local.get $x + call $matchesExtra + br_if $matchFound + end + ;; icell = buf32[icell+BCELL_NEXT_AND]; + local.get $icell + i32.load align=4 + i32.const 2 + i32.shl + local.tee $icell + ;; if ( icell === 0 ) { return 0; } + i32.eqz + br_if $matchNotFound + ;; } + end + br $mainLoop + ;; } + end ;; $mainLoop + end ;; $matchNotFound + i32.const 0 + return + end ;; $matchFound + i32.const 1 + return +) + +;; +;; int matchExtra(l, r, ix) +;; +;; Test whether extra handler returns a match. +;; +(func $matchesExtra + (param $l i32) ;; left bound of match so far + (param $r i32) ;; right bound of match so far + (param $ix i32) ;; extra token + (result i32) ;; result: 0 = no match, 1 = match + (local $iu i32) ;; filter unit + block $fail + block $succeed + ;; if ( ix !== 1 ) { + ;; const iu = this.extraHandler(l, r, ix); + ;; if ( iu === 0 ) { return 0; } + local.get $ix + i32.const 1 + i32.ne + if + local.get $l + local.get $r + local.get $ix + call $extraHandler + local.tee $iu + i32.eqz + br_if $fail + ;; } else { + ;; iu = -1; + else + i32.const -1 + local.set $iu + ;; } + end + ;; this.buf32[RESULT_IU_SLOT] = iu; + i32.const 8220 + local.get $iu + i32.store align=4 + ;; this.buf32[RESULT_L_SLOT] = l; + i32.const 8212 + local.get $l + i32.store align=4 + ;; this.buf32[RESULT_R_SLOT] = r; + i32.const 8216 + local.get $r + i32.store align=4 + end ;; $succeed + i32.const 1 + return + end ;; $fail + i32.const 0 +) + +;; +;; unsigned int startsWith(haystackLeft, haystackRight, needleLeft, needleLen) +;; +;; Test whether the string at needleOffset and of length needleLen matches +;; the haystack at offset haystackOffset. +;; +(func (export "startsWith") + (param $haystackLeft i32) ;; start offset in haystack + (param $haystackRight i32) ;; end offset in haystack + (param $needleLeft i32) ;; start of needle in character buffer + (param $needleLen i32) ;; number of characters to match + (result i32) ;; result: 0 = no match, 1 = match + (local $needleRight i32) + block $fail + block $succeed + ;; + ;; if ( haystackLeft < 0 || (haystackLeft + needleLen) > haystackRight ) { + ;; return 0; + ;; } + local.get $haystackLeft + i32.const 0 + i32.lt_s + br_if $fail + local.get $haystackLeft + local.get $needleLen + i32.add + local.get $haystackRight + i32.gt_u + br_if $fail + ;; const charCodes = this.buf8; + ;; needleLeft += this.buf32[CHAR0_SLOT]; + local.get $needleLeft + i32.const 8204 ;; CHAR0_SLOT memory address + i32.load align=4 ;; CHAR0 memory address + i32.add ;; needle memory address + local.tee $needleLeft + ;; const needleRight = needleLeft + needleLen; + local.get $needleLen + i32.add + local.set $needleRight + ;; while ( charCodes[haystackLeft] === charCodes[needleLeft] ) { + loop $compare + local.get $haystackLeft + i32.load8_u + local.get $needleLeft + i32.load8_u + i32.ne + br_if $fail + ;; needleLeft += 1; + local.get $needleLeft + i32.const 1 + i32.add + local.tee $needleLeft + ;; if ( needleLeft === needleRight ) { return 1; } + local.get $needleRight + i32.eq + br_if $succeed + ;; haystackLeft += 1; + i32.const 1 + local.get $haystackLeft + i32.add + local.set $haystackLeft + br $compare + end + ;; } + ;; return 1; + end ;; $succeed + i32.const 1 + return + ;; return 0; + end ;; $fail + i32.const 0 +) + +;; +;; int indexOf(haystackLeft, haystackEnd, needleLeft, needleLen) +;; +;; Test whether the string at needleOffset and of length needleLen is found in +;; the haystack at or to the left of haystackLeft, but not farther than +;; haystackEnd. +;; +(func (export "indexOf") + (param $haystackLeft i32) ;; start offset in haystack + (param $haystackEnd i32) ;; end offset in haystack + (param $needleLeft i32) ;; start of needle in character buffer + (param $needleLen i32) ;; number of characters to match + (result i32) ;; result: index of match, -1 = no match + (local $needleRight i32) + (local $i i32) + (local $j i32) + (local $c0 i32) + block $fail + block $succeed + ;; if ( needleLen === 0 ) { return haystackLeft; } + local.get $needleLen + i32.eqz + br_if $succeed + ;; haystackEnd -= needleLen; + local.get $haystackEnd + local.get $needleLen + i32.sub + local.tee $haystackEnd + ;; if ( haystackEnd < haystackLeft ) { return -1; } + local.get $haystackLeft + i32.lt_s + br_if $fail + ;; needleLeft += this.buf32[CHAR0_SLOT]; + local.get $needleLeft + i32.const 8204 ;; CHAR0_SLOT memory address + i32.load align=4 ;; CHAR0 memory address + i32.add ;; needle memory address + local.tee $needleLeft + ;; const needleRight = needleLeft + needleLen; + local.get $needleLen + i32.add + local.set $needleRight + ;; const charCodes = this.buf8; + ;; for (;;) { + loop $mainLoop + ;; let i = haystackLeft; + ;; let j = needleLeft; + local.get $haystackLeft + local.set $i + local.get $needleLeft + local.set $j + ;; while ( charCodes[i] === charCodes[j] ) { + block $breakMatchChars loop $matchChars + local.get $i + i32.load8_u + local.get $j + i32.load8_u + i32.ne + br_if $breakMatchChars + ;; j += 1; + local.get $j + i32.const 1 + i32.add + local.tee $j + ;; if ( j === needleRight ) { return haystackLeft; } + local.get $needleRight + i32.eq + br_if $succeed + ;; i += 1; + local.get $i + i32.const 1 + i32.add + local.set $i + br $matchChars + ;; } + end end + ;; haystackLeft += 1; + local.get $haystackLeft + i32.const 1 + i32.add + local.tee $haystackLeft + ;; if ( haystackLeft > haystackEnd ) { break; } + local.get $haystackEnd + i32.gt_u + br_if $fail + br $mainLoop + ;; } + end + end ;; $succeed + local.get $haystackLeft + return + end ;; $fail + ;; return -1; + i32.const -1 +) + +;; +;; int lastIndexOf(haystackBeg, haystackEnd, needleLeft, needleLen) +;; +;; Test whether the string at needleOffset and of length needleLen is found in +;; the haystack at or to the right of haystackBeg, but not farther than +;; haystackEnd. +;; +(func (export "lastIndexOf") + (param $haystackBeg i32) ;; start offset in haystack + (param $haystackEnd i32) ;; end offset in haystack + (param $needleLeft i32) ;; start of needle in character buffer + (param $needleLen i32) ;; number of characters to match + (result i32) ;; result: index of match, -1 = no match + (local $haystackLeft i32) + (local $needleRight i32) + (local $i i32) + (local $j i32) + (local $c0 i32) + ;; if ( needleLen === 0 ) { return haystackBeg; } + local.get $needleLen + i32.eqz + if + local.get $haystackBeg + return + end + block $fail + block $succeed + ;; let haystackLeft = haystackEnd - needleLen; + local.get $haystackEnd + local.get $needleLen + i32.sub + local.tee $haystackLeft + ;; if ( haystackLeft < haystackBeg ) { return -1; } + local.get $haystackBeg + i32.lt_s + br_if $fail + ;; needleLeft += this.buf32[CHAR0_SLOT]; + local.get $needleLeft + i32.const 8204 ;; CHAR0_SLOT memory address + i32.load align=4 ;; CHAR0 memory address + i32.add ;; needle memory address + local.tee $needleLeft + ;; const needleRight = needleLeft + needleLen; + local.get $needleLen + i32.add + local.set $needleRight + ;; const charCodes = this.buf8; + ;; for (;;) { + loop $mainLoop + ;; let i = haystackLeft; + ;; let j = needleLeft; + local.get $haystackLeft + local.set $i + local.get $needleLeft + local.set $j + ;; while ( charCodes[i] === charCodes[j] ) { + block $breakMatchChars loop $matchChars + local.get $i + i32.load8_u + local.get $j + i32.load8_u + i32.ne + br_if $breakMatchChars + ;; j += 1; + local.get $j + i32.const 1 + i32.add + local.tee $j + ;; if ( j === needleRight ) { return haystackLeft; } + local.get $needleRight + i32.eq + br_if $succeed + ;; i += 1; + local.get $i + i32.const 1 + i32.add + local.set $i + br $matchChars + ;; } + end end + ;; if ( haystackLeft === haystackBeg ) { break; } + ;; haystackLeft -= 1; + local.get $haystackLeft + local.get $haystackBeg + i32.eq + br_if $fail + local.get $haystackLeft + i32.const 1 + i32.sub + local.set $haystackLeft + br $mainLoop + ;; } + end + end ;; $succeed + local.get $haystackLeft + return + end ;; $fail + ;; return -1; + i32.const -1 +) + +;; +;; module end +;; +) |