path: root/data/extensions/uBlock0@raymondhill.net/lib/lz4/lz4-block-codec.wat

;;
;; lz4-block-codec.wat: a WebAssembly implementation of LZ4 block format codec
;; Copyright (C) 2018 Raymond Hill
;;
;; BSD-2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
;;
;; Redistribution and use in source and binary forms, with or without
;; modification, are permitted provided that the following conditions are
;; met:
;; 
;;   1. Redistributions of source code must retain the above copyright
;; notice, this list of conditions and the following disclaimer.
;; 
;;   2. Redistributions in binary form must reproduce the above
;; copyright notice, this list of conditions and the following disclaimer
;; in the documentation and/or other materials provided with the
;; distribution.
;; 
;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
;; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
;; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
;; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
;;
;; Home: https://github.com/gorhill/lz4-wasm
;;
;; I used the same license as the one picked by creator of LZ4 out of respect
;; for his creation, see https://lz4.github.io/lz4/
;;

(module
;;
;; module start
;;

;; (func $log (import "imports" "log") (param i32 i32 i32))

(memory (export "memory") 1)

;;
;; Public functions
;;

;;
;; Return an offset to the first byte of usable linear memory.
;; Might be useful in the future to reserve memory space for whatever purpose,
;; like config variables, etc.
;;
(func $getLinearMemoryOffset (export "getLinearMemoryOffset") 
    (result i32)
    i32.const 0
)

;;
;; unsigned int lz4BlockEncodeBound()
;;
;; Return the maximum size of the output buffer holding the compressed data.
;;
;; Reference implementation:
;; https://github.com/lz4/lz4/blob/dev/lib/lz4.h#L156
;;
(func (export "lz4BlockEncodeBound")
    (param $ilen i32)
    (result i32)
    local.get $ilen
    i32.const 0x7E000000
    i32.gt_u
    if
        i32.const 0
        return
    end
    local.get $ilen
    local.get $ilen
    i32.const 255
    i32.div_u
    i32.add
    i32.const 16
    i32.add
)

;;
;; unsigned int lz4BlockEncode(
;;     unsigned int inPtr,
;;     unsigned int ilen,
;;     unsigned int outPtr
;; )
;;
;; https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L651
;;
;; The implementation below is modified from the reference one.
;; 
;; - There is no skip adjustment for repeated failure to find a match.
;; 
;; - All configurable values are hard-coded to match the generic version
;;   of the compressor.
;;
;; Note the size of the input block is NOT encoded in the output buffer, it
;; is for the caller to figure how they will save that information on
;; their side. At this point it is probably a trivial amount of work to
;; implement the LZ4 frame format, which encode the content size, but this
;; is for another day.
;;
(func $lz4BlockEncode (export "lz4BlockEncode")
    (param $inPtr i32)                  ;; pointer to start of input buffer
    (param $ilen i32)                   ;; size of input buffer
    (param $outPtr i32)                 ;; pointer to start of output buffer
    (result i32)
    (local $hashPtrBeg i32)             ;; start of hash buffer
    (local $hashPtr i32)                ;; current hash entry
    (local $anchorPtr i32)              ;; anchor position in input
    (local $inPtrEnd1 i32)              ;; point in input at which match-finding must cease
    (local $inPtrEnd2 i32)              ;; point in input at which match-length finding must cease
    (local $inPtrEnd i32)               ;; point to end of input
    (local $outPtrBeg i32)              ;; start of output buffer
    (local $refPtr i32)                 ;; start of match in input
    (local $seq32 i32)                  ;; 4-byte value from current input position
    (local $llen i32)                   ;; length of found literals
    (local $moffset i32)                ;; offset to found match from current input position
    (local $mlen i32)                   ;; length of found match
    local.get $ilen                     ;; empty input = empty output
    i32.const 0x7E000000                ;; max input size: 0x7E000000
    i32.gt_u
    if
        i32.const 0
        return
    end
    local.get $ilen                     ;; "blocks < 13 bytes cannot be compressed"
    i32.const 13
    i32.lt_u
    if
        i32.const 0
        return
    end
    call $getLinearMemoryOffset         ;; hash table is at start of usable memory
    local.set $hashPtrBeg
    local.get $inPtr
    local.tee $anchorPtr
    local.get $ilen
    i32.add
    local.tee $inPtrEnd
    i32.const -5                        ;; "The last 5 bytes are always literals."
    i32.add
    local.tee $inPtrEnd2
    i32.const -7                        ;; "The last match must start at least 12 bytes before end of block"
    i32.add
    local.set $inPtrEnd1
    local.get $outPtr
    local.set $outPtrBeg
    ;;
    ;; sequence processing loop
    ;;
    block $noMoreSequence loop $nextSequence
        local.get $inPtr
        local.get $inPtrEnd1
        i32.ge_u                        ;; 5 or less bytes left?
        br_if $noMoreSequence
        local.get $inPtr                ;; first sequence of 3 bytes before match-finding loop
        i32.load8_u
        i32.const 8
        i32.shl
        local.get $inPtr
        i32.load8_u offset=1
        i32.const 16
        i32.shl
        i32.or
        local.get $inPtr
        i32.load8_u offset=2
        i32.const 24
        i32.shl
        i32.or
        local.set $seq32
        ;;
        ;; match-finding loop
        ;;
        loop $findMatch block $noMatchFound
            local.get $inPtr
            local.get $inPtrEnd2
            i32.gt_u                    ;; less than 12 bytes left?
            br_if $noMoreSequence
            local.get $seq32            ;; update last byte of current sequence
            i32.const 8
            i32.shr_u
            local.get $inPtr
            i32.load8_u offset=3
            i32.const 24
            i32.shl
            i32.or
            local.tee $seq32
            i32.const 0x9E3779B1        ;; compute 16-bit hash
            i32.mul
            i32.const 16
            i32.shr_u                   ;; hash value is at top of stack
            i32.const 2                 ;; lookup refPtr at hash entry
            i32.shl
            local.get $hashPtrBeg
            i32.add
            local.tee $hashPtr
            i32.load
            local.set $refPtr
            local.get $hashPtr          ;; update hash entry with inPtr
            local.get $inPtr
            i32.store
            local.get $inPtr
            local.get $refPtr
            i32.sub
            local.tee $moffset          ;; remember match offset, we will need it in case of match
            i32.const 0xFFFF
            i32.gt_s                    ;; match offset > 65535 = unusable match
            br_if $noMatchFound
            ;;
            ;; confirm match: different sequences can yield same hash
            ;; compare-branch each byte to potentially save memory read ops
            ;;
            local.get $seq32            ;; byte 0
            i32.const 0xFF
            i32.and
            local.get $refPtr
            i32.load8_u
            i32.ne                      ;; refPtr[0] !== inPtr[0]
            br_if $noMatchFound
            local.get $seq32            ;; byte 1
            i32.const 8
            i32.shr_u
            i32.const 0xFF
            i32.and
            local.get $refPtr
            i32.load8_u offset=1
            i32.ne
            br_if $noMatchFound         ;; refPtr[1] !== inPtr[1]
            local.get $seq32            ;; byte 2
            i32.const 16
            i32.shr_u
            i32.const 0xFF
            i32.and
            local.get $refPtr
            i32.load8_u offset=2
            i32.ne                      ;; refPtr[2] !== inPtr[2]
            br_if $noMatchFound
            local.get $seq32            ;; byte 3
            i32.const 24
            i32.shr_u
            i32.const 0xFF
            i32.and
            local.get $refPtr
            i32.load8_u offset=3
            i32.ne                      ;; refPtr[3] !== inPtr[3]
            br_if $noMatchFound
            ;;
            ;; a valid match has been found at this point
            ;;
            local.get $inPtr            ;; compute length of literals
            local.get $anchorPtr
            i32.sub
            local.set $llen
            local.get $inPtr            ;; find match length
            i32.const 4                 ;; skip over confirmed 4-byte match
            i32.add
            local.set $inPtr
            local.get $refPtr
            i32.const 4
            i32.add
            local.tee $mlen             ;; remember refPtr to later compute match length
            local.set $refPtr
            block $endOfMatch loop      ;; scan input buffer until match ends
                local.get $inPtr
                local.get $inPtrEnd2
                i32.ge_u
                br_if $endOfMatch
                local.get $inPtr
                i32.load8_u
                local.get $refPtr
                i32.load8_u
                i32.ne
                br_if $endOfMatch
                local.get $inPtr
                i32.const 1
                i32.add
                local.set $inPtr
                local.get $refPtr
                i32.const 1
                i32.add
                local.set $refPtr
                br 0
            end end $endOfMatch
            ;; encode token
            local.get $outPtr           ;; output token
            local.get $llen
            local.get $refPtr
            local.get $mlen
            i32.sub
            local.tee $mlen
            call $writeToken
            local.get $outPtr
            i32.const 1
            i32.add
            local.set $outPtr
            local.get $llen             ;; encode/write length of literals if needed
            i32.const 15
            i32.ge_s
            if
                local.get $outPtr
                local.get $llen
                call $writeLength
                local.set $outPtr
            end
            ;; copy literals
            local.get $outPtr
            local.get $anchorPtr
            local.get $llen
            call $copy
            local.get $outPtr
            local.get $llen
            i32.add
            local.set $outPtr
            ;; encode match offset
            local.get $outPtr
            local.get $moffset
            i32.store8
            local.get $outPtr
            local.get $moffset
            i32.const 8
            i32.shr_u
            i32.store8 offset=1
            local.get $outPtr
            i32.const 2
            i32.add
            local.set $outPtr
            local.get $mlen             ;; encode/write length of match if needed
            i32.const 15
            i32.ge_s
            if
                local.get $outPtr
                local.get $mlen
                call $writeLength
                local.set $outPtr
            end
            local.get $inPtr            ;; advance anchor to current position
            local.set $anchorPtr
            br $nextSequence
        end $noMatchFound
        local.get $inPtr                ;; no match found: advance to next byte
        i32.const 1
        i32.add
        local.set $inPtr
        br $findMatch end               ;; match offset > 65535 = unusable match
    end end $noMoreSequence
    ;;
    ;; generate last (match-less) sequence if compression succeeded
    ;;
    local.get $outPtr
    local.get $outPtrBeg
    i32.eq
    if
        i32.const 0
        return
    end
    local.get $outPtr
    local.get $inPtrEnd
    local.get $anchorPtr
    i32.sub
    local.tee $llen
    i32.const 0
    call $writeToken
    local.get $outPtr
    i32.const 1
    i32.add
    local.set $outPtr
    local.get $llen
    i32.const 15
    i32.ge_u
    if
        local.get $outPtr
        local.get $llen
        call $writeLength
        local.set $outPtr
    end
    local.get $outPtr
    local.get $anchorPtr
    local.get $llen
    call $copy
    local.get $outPtr                   ;; return number of written bytes
    local.get $llen
    i32.add
    local.get $outPtrBeg
    i32.sub
)

;;
;; unsigned int lz4BlockDecode(
;;     unsigned int inPtr,
;;     unsigned int ilen
;;     unsigned int outPtr
;; )
;;
;; Reference:
;; https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md
;;
(func (export "lz4BlockDecode")
    (param $inPtr0 i32)                 ;; start of input buffer
    (param $ilen i32)                   ;; length of input buffer
    (param $outPtr0 i32)                ;; start of output buffer
    (result i32)
    (local $inPtr i32)                  ;; current position in input buffer
    (local $inPtrEnd i32)               ;; end of input buffer
    (local $outPtr i32)                 ;; current position in output buffer
    (local $matchPtr i32)               ;; position of current match
    (local $token i32)                  ;; sequence token
    (local $clen i32)                   ;; number of bytes to copy 
    (local $_ i32)                      ;; general purpose variable
    local.get $ilen                     ;; if ( ilen == 0 ) { return 0; }
    i32.eqz
    if
        i32.const 0
        return
    end
    local.get $inPtr0
    local.tee $inPtr                    ;; current position in input buffer
    local.get $ilen
    i32.add
    local.set $inPtrEnd
    local.get $outPtr0                  ;; start of output buffer
    local.set $outPtr                   ;; current position in output buffer
    block $noMoreSequence loop          ;; iterate through all sequences
        local.get $inPtr
        local.get $inPtrEnd
        i32.ge_u
        br_if $noMoreSequence           ;; break when nothing left to read in input buffer
        local.get $inPtr                ;; read token -- consume one byte
        i32.load8_u
        local.get $inPtr
        i32.const 1
        i32.add
        local.set $inPtr
        local.tee $token                ;; extract length of literals from token
        i32.const 4
        i32.shr_u
        local.tee $clen                 ;; consume extra length bytes if present
        i32.eqz
        if else
            local.get $clen
            i32.const 15
            i32.eq
            if loop
                local.get $inPtr
                i32.load8_u
                local.get $inPtr
                i32.const 1
                i32.add
                local.set $inPtr
                local.tee $_
                local.get $clen
                i32.add
                local.set $clen
                local.get $_
                i32.const 255
                i32.eq
                br_if 0
            end end
            local.get $outPtr           ;; copy literals to output buffer
            local.get $inPtr
            local.get $clen
            call $copy
            local.get $outPtr           ;; advance output buffer pointer past copy
            local.get $clen
            i32.add
            local.set $outPtr
            local.get $clen             ;; advance input buffer pointer past literals
            local.get $inPtr
            i32.add
            local.tee $inPtr
            local.get $inPtrEnd         ;; exit if this is the last sequence
            i32.eq
            br_if $noMoreSequence
        end
        local.get $outPtr               ;; read match offset
        local.get $inPtr
        i32.load8_u
        local.get $inPtr
        i32.load8_u offset=1
        i32.const 8
        i32.shl
        i32.or
        i32.sub
        local.tee $matchPtr
        local.get $outPtr               ;; match position can't be outside input buffer bounds
        i32.eq
        br_if $noMoreSequence
        local.get $matchPtr
        local.get $inPtrEnd
        i32.lt_u
        br_if $noMoreSequence
        local.get $inPtr                ;; advance input pointer past match offset bytes
        i32.const 2
        i32.add
        local.set $inPtr
        local.get $token                ;; extract length of match from token
        i32.const 15
        i32.and
        i32.const 4
        i32.add
        local.tee $clen
        i32.const 19                    ;; consume extra length bytes if present
        i32.eq
        if loop
            local.get $inPtr
            i32.load8_u
            local.get $inPtr
            i32.const 1
            i32.add
            local.set $inPtr
            local.tee $_
            local.get $clen
            i32.add
            local.set $clen
            local.get $_
            i32.const 255
            i32.eq
            br_if 0
        end end
        local.get $outPtr               ;; copy match to output buffer
        local.get $matchPtr
        local.get $clen
        call $copy
        local.get $clen                 ;; advance output buffer pointer past copy
        local.get $outPtr
        i32.add
        local.set $outPtr
        br 0
    end end $noMoreSequence
    local.get $outPtr                   ;; return number of written bytes
    local.get $outPtr0
    i32.sub
)

;;
;; Private functions
;;

;;
;; Encode a sequence token
;;
;; Reference documentation:
;; https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md
;;
(func $writeToken
    (param $outPtr i32)
    (param $llen i32)
    (param $mlen i32)
    local.get $outPtr
    local.get $llen
    i32.const 15
    local.get $llen
    i32.const 15
    i32.lt_u
    select
    i32.const 4
    i32.shl
    local.get $mlen
    i32.const 15
    local.get $mlen
    i32.const 15
    i32.lt_u
    select
    i32.or
    i32.store8
)

;;
;; Encode and output length bytes. The return value is the pointer following
;; the last byte written.
;;
;; Reference documentation:
;; https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md
;;
(func $writeLength
    (param $outPtr i32)
    (param $len i32)
    (result i32)
    local.get $len
    i32.const 15
    i32.sub
    local.set $len
    loop
        local.get $outPtr
        local.get $len
        i32.const 255
        local.get $len
        i32.const 255
        i32.lt_u
        select
        i32.store8
        local.get $outPtr
        i32.const 1
        i32.add
        local.set $outPtr
        local.get $len
        i32.const 255
        i32.sub
        local.tee $len
        i32.const 0
        i32.ge_s
        br_if 0
    end
    local.get $outPtr
)

;;
;; Copy n bytes from source to destination.
;;
;; It is overlap-safe only from left-to-right -- which is only what is
;; required in the current module.
;;
(func $copy
    (param $dst i32)
    (param $src i32)
    (param $len i32)
    block $lessThan8 loop
        local.get $len
        i32.const 8
        i32.lt_u
        br_if $lessThan8
        local.get $dst
        local.get $src
        i32.load8_u
        i32.store8
        local.get $dst
        local.get $src
        i32.load8_u offset=1
        i32.store8 offset=1
        local.get $dst
        local.get $src
        i32.load8_u offset=2
        i32.store8 offset=2
        local.get $dst
        local.get $src
        i32.load8_u offset=3
        i32.store8 offset=3
        local.get $dst
        local.get $src
        i32.load8_u offset=4
        i32.store8 offset=4
        local.get $dst
        local.get $src
        i32.load8_u offset=5
        i32.store8 offset=5
        local.get $dst
        local.get $src
        i32.load8_u offset=6
        i32.store8 offset=6
        local.get $dst
        local.get $src
        i32.load8_u offset=7
        i32.store8 offset=7
        local.get $dst
        i32.const 8
        i32.add
        local.set $dst
        local.get $src
        i32.const 8
        i32.add
        local.set $src
        local.get $len
        i32.const -8
        i32.add
        local.set $len
        br 0
    end end $lessThan8
    local.get $len
    i32.const 4
    i32.ge_u
    if
        local.get $dst
        local.get $src
        i32.load8_u
        i32.store8
        local.get $dst
        local.get $src
        i32.load8_u offset=1
        i32.store8 offset=1
        local.get $dst
        local.get $src
        i32.load8_u offset=2
        i32.store8 offset=2
        local.get $dst
        local.get $src
        i32.load8_u offset=3
        i32.store8 offset=3
        local.get $dst
        i32.const 4
        i32.add
        local.set $dst
        local.get $src
        i32.const 4
        i32.add
        local.set $src
        local.get $len
        i32.const -4
        i32.add
        local.set $len
    end
    local.get $len
    i32.const 2
    i32.ge_u
    if
        local.get $dst
        local.get $src
        i32.load8_u
        i32.store8
        local.get $dst
        local.get $src
        i32.load8_u offset=1
        i32.store8 offset=1
        local.get $dst
        i32.const 2
        i32.add
        local.set $dst
        local.get $src
        i32.const 2
        i32.add
        local.set $src
        local.get $len
        i32.const -2
        i32.add
        local.set $len
    end
    local.get $len
    i32.eqz
    if else
        local.get $dst
        local.get $src
        i32.load8_u
        i32.store8
    end
)

;;
;; module end
;;
)