TmMolStar/src/mol-util/zip/deflate.ts

/**
 * Copyright (c) 2020 mol* contributors, licensed under MIT, See LICENSE file for more info.
 *
 * @author Alexander Rose <alexander.rose@weirdbyte.de>
 *
 * ported from https://github.com/photopea/UZIP.js/blob/master/UZIP.js
 * MIT License, Copyright (c) 2018 Photopea
 */

import { NumberArray } from '../type-helpers';
import { _hufTree } from './huffman';
import { U, revCodes, makeCodes } from './util';

export function _deflateRaw(data: Uint8Array, out: Uint8Array, opos: number, lvl: number) {
    const opts = [
        /*
            ush good_length; /* reduce lazy search above this match length
            ush max_lazy;    /* do not perform lazy search above this match length
            ush nice_length; /* quit search above this match length
        */
        /*      good lazy nice chain */
        /* 0 */ [ 0,   0,   0,    0, 0], /* store only */
        /* 1 */ [ 4,   4,   8,    4, 0], /* max speed, no lazy matches */
        /* 2 */ [ 4,   5,  16,    8, 0],
        /* 3 */ [ 4,   6,  16,   16, 0],

        /* 4 */ [ 4,  10,  16,   32, 0], /* lazy matches */
        /* 5 */ [ 8,  16,  32,   32, 0],
        /* 6 */ [ 8,  16, 128,  128, 0],
        /* 7 */ [ 8,  32, 128,  256, 0],
        /* 8 */ [32, 128, 258, 1024, 1],
        /* 9 */ [32, 258, 258, 4096, 1] /* max compression */
    ];

    const opt = opts[lvl];

    let i = 0, pos = opos << 3, cvrd = 0;
    const dlen = data.length;

    if(lvl === 0) {
        while(i < dlen) {
            const len = Math.min(0xffff, dlen - i);
            _putsE(out, pos, (i + len === dlen ? 1 : 0));
            pos = _copyExact(data, i, len, out, pos + 8);
            i += len;
        }
        return pos >>> 3;
    }

    const { lits, strt, prev } = U;
    let li = 0, lc = 0, bs = 0, ebits = 0, c = 0, nc = 0;  // last_item, literal_count, block_start
    if(dlen > 2) {
        nc = _hash(data, 0);
        strt[nc] = 0;
    }

    // let nmch = 0
    // let nmci = 0

    for(i = 0; i < dlen; i++)  {
        c = nc;
        //*
        if(i + 1 < dlen - 2) {
            nc = _hash(data, i + 1);
            const ii = ((i + 1) & 0x7fff);
            prev[ii] = strt[nc];
            strt[nc] = ii;
        } // */
        if(cvrd <= i) {
            if((li > 14000 || lc > 26697) && (dlen - i) > 100) {
                if(cvrd < i) {
                    lits[li] = i - cvrd;
                    li += 2;
                    cvrd = i;
                }
                pos = _writeBlock(((i === dlen - 1) || (cvrd === dlen)) ? 1 : 0, lits, li, ebits, data, bs, i - bs, out, pos);
                li = lc = ebits = 0;
                bs = i;
            }

            let mch = 0;
            // if(nmci==i) mch= nmch;  else
            if(i < dlen - 2) {
                mch = _bestMatch(data, i, prev, c, Math.min(opt[2], dlen - i), opt[3]);
            }
            /*
            if(mch!=0 && opt[4]==1 && (mch>>>16)<opt[1] && i+1<dlen-2) {
                nmch = UZIP.F._bestMatch(data, i+1, prev, nc, opt[2], opt[3]);  nmci=i+1;
                //var mch2 = UZIP.F._bestMatch(data, i+2, prev, nnc);  //nmci=i+1;
                if((nmch>>>16)>(mch>>>16)) mch=0;
            }//*/
            // const len = mch>>>16, dst = mch & 0xffff;  // if(i-dst<0) throw "e";
            if(mch !== 0) {
                const len = mch >>> 16, dst = mch & 0xffff;  // if(i-dst<0) throw "e";
                const lgi = _goodIndex(len, U.of0);  U.lhst[257 + lgi]++;
                const dgi = _goodIndex(dst, U.df0);  U.dhst[    dgi]++;  ebits += U.exb[lgi] + U.dxb[dgi];
                lits[li] = (len << 23) | (i - cvrd);  lits[li + 1] = (dst << 16) | (lgi << 8) | dgi;  li += 2;
                cvrd = i + len;
            } else {
                U.lhst[data[i]]++;
            }
            lc++;
        }
    }
    if(bs !== i || data.length === 0) {
        if(cvrd < i) {
            lits[li] = i - cvrd;
            li += 2;
            cvrd = i;
        }
        pos = _writeBlock(1, lits, li, ebits, data, bs, i - bs, out, pos);
        li = 0;
        lc = 0;
        li = lc = ebits = 0;
        bs = i;
    }
    while((pos & 7) !== 0) pos++;
    return pos >>> 3;
}

function _bestMatch(data: Uint8Array, i: number, prev: Uint16Array, c: number, nice: number, chain: number) {
    let ci = (i & 0x7fff), pi = prev[ci];
    // console.log("----", i);
    let dif = ((ci - pi + (1 << 15)) & 0x7fff);
    if(pi === ci || c !== _hash(data, i - dif)) return 0;
    let tl = 0, td = 0;  // top length, top distance
    const dlim = Math.min(0x7fff, i);
    while(dif <= dlim && --chain !== 0 && pi !== ci /* && c==UZIP.F._hash(data,i-dif)*/) {
        if(tl === 0 || (data[i + tl] === data[i + tl - dif])) {
            let cl = _howLong(data, i, dif);
            if(cl > tl) {
                tl = cl;  td = dif;  if(tl >= nice) break;    //*
                if(dif + 2 < cl) cl = dif + 2;
                let maxd = 0; // pi does not point to the start of the word
                for(let j = 0; j < cl - 2; j++) {
                    const ei =  (i - dif + j + (1 << 15)) & 0x7fff;
                    const li = prev[ei];
                    const curd = (ei - li + (1 << 15)) & 0x7fff;
                    if(curd > maxd) {  maxd = curd;  pi = ei; }
                }
            }
        }

        ci = pi;  pi = prev[ci];
        dif += ((ci - pi + (1 << 15)) & 0x7fff);
    }
    return (tl << 16) | td;
}

function _howLong(data: Uint8Array, i: number, dif: number) {
    if(data[i] !== data[i - dif] || data[i + 1] !== data[i + 1 - dif] || data[i + 2] !== data[i + 2 - dif]) return 0;
    const oi = i, l = Math.min(data.length, i + 258);
    i += 3;
    // while(i+4<l && data[i]==data[i-dif] && data[i+1]==data[i+1-dif] && data[i+2]==data[i+2-dif] && data[i+3]==data[i+3-dif]) i+=4;
    while(i < l && data[i] === data[i - dif]) i++;
    return i - oi;
}

function _hash(data: Uint8Array, i: number) {
    return (((data[i] << 8) | data[i + 1]) + (data[i + 2] << 4)) & 0xffff;
    // var hash_shift = 0, hash_mask = 255;
    // var h = data[i+1] % 251;
    // h = (((h << 8) + data[i+2]) % 251);
    // h = (((h << 8) + data[i+2]) % 251);
    // h = ((h<<hash_shift) ^ (c) ) & hash_mask;
    // return h | (data[i]<<8);
    // return (data[i] | (data[i+1]<<8));
}

function _writeBlock(BFINAL: number, lits: Uint32Array, li: number, ebits: number, data: Uint8Array, o0: number, l0: number, out: Uint8Array, pos: number) {
    U.lhst[256]++;
    const [ ML, MD, MH, numl, numd, numh, lset, dset ] = getTrees();

    const cstSize = (((pos + 3) & 7) === 0 ? 0 : 8 - ((pos + 3) & 7)) + 32 + (l0 << 3);
    const fxdSize = ebits + contSize(U.fltree, U.lhst) + contSize(U.fdtree, U.dhst);
    let dynSize = ebits + contSize(U.ltree, U.lhst) + contSize(U.dtree, U.dhst);
    dynSize += 14 + 3 * numh + contSize(U.itree, U.ihst) + (U.ihst[16] * 2 + U.ihst[17] * 3 + U.ihst[18] * 7);

    for(let j = 0; j < 286; j++) U.lhst[j] = 0;
    for(let j = 0; j < 30; j++) U.dhst[j] = 0;
    for(let j = 0; j < 19; j++) U.ihst[j] = 0;

    const BTYPE = (cstSize < fxdSize && cstSize < dynSize) ? 0 : ( fxdSize < dynSize ? 1 : 2 );
    _putsF(out, pos, BFINAL);
    _putsF(out, pos + 1, BTYPE);
    pos += 3;

    // let opos = pos;
    if(BTYPE === 0) {
        while((pos & 7) !== 0) pos++;
        pos = _copyExact(data, o0, l0, out, pos);
    } else {
        let ltree: number[], dtree: number[];
        if(BTYPE === 1) {
            ltree = U.fltree;  dtree = U.fdtree;
        } else if(BTYPE === 2) {
            makeCodes(U.ltree, ML);  revCodes(U.ltree, ML);
            makeCodes(U.dtree, MD);  revCodes(U.dtree, MD);
            makeCodes(U.itree, MH);  revCodes(U.itree, MH);

            ltree = U.ltree;  dtree = U.dtree;

            _putsE(out, pos, numl - 257);  pos += 5;  // 286
            _putsE(out, pos, numd -  1);  pos += 5;  // 30
            _putsE(out, pos, numh -  4);  pos += 4;  // 19

            for(let i = 0; i < numh; i++) _putsE(out, pos + i * 3, U.itree[(U.ordr[i] << 1) + 1]);
            pos += 3 * numh;
            pos = _codeTiny(lset, U.itree, out, pos);
            pos = _codeTiny(dset, U.itree, out, pos);
        } else {
            throw new Error(`unknown BTYPE ${BTYPE}`);
        }

        let off = o0;
        for(let si = 0; si < li; si += 2) {
            const qb = lits[si], len = (qb >>> 23), end = off + (qb & ((1 << 23) - 1));
            while(off < end) pos = _writeLit(data[off++], ltree, out, pos);

            if(len !== 0) {
                const qc = lits[si + 1], dst = (qc >> 16), lgi = (qc >> 8) & 255, dgi = (qc & 255);
                pos = _writeLit(257 + lgi, ltree, out, pos);
                _putsE(out, pos, len - U.of0[lgi]);  pos += U.exb[lgi];

                pos = _writeLit(dgi, dtree, out, pos);
                _putsF(out, pos, dst - U.df0[dgi]);  pos += U.dxb[dgi];  off += len;
            }
        }
        pos = _writeLit(256, ltree, out, pos);
    }
    // console.log(pos-opos, fxdSize, dynSize, cstSize);
    return pos;
}

function _copyExact(data: Uint8Array, off: number, len: number, out: Uint8Array, pos: number) {
    let p8 = (pos >>> 3);
    out[p8] = (len);
    out[p8 + 1] = (len >>> 8);
    out[p8 + 2] = 255 - out[p8];
    out[p8 + 3] = 255 - out[p8 + 1];
    p8 += 4;
    out.set(new Uint8Array(data.buffer, off, len), p8);
    // for(var i=0; i<len; i++) out[p8+i]=data[off+i];
    return pos + ((len + 4) << 3);
}


/*
    Interesting facts:
    - decompressed block can have bytes, which do not occur in a Huffman tree (copied from the previous block by reference)
*/

function getTrees() {
    const ML = _hufTree(U.lhst, U.ltree, 15);
    const MD = _hufTree(U.dhst, U.dtree, 15);
    const lset: number[] = [];
    const numl = _lenCodes(U.ltree, lset);
    const dset: number[] = [];
    const numd = _lenCodes(U.dtree, dset);
    for(let i = 0; i < lset.length; i += 2) U.ihst[lset[i]]++;
    for(let i = 0; i < dset.length; i += 2) U.ihst[dset[i]]++;
    const MH = _hufTree(U.ihst, U.itree,  7);
    let numh = 19;
    while(numh > 4 && U.itree[(U.ordr[numh - 1] << 1) + 1] === 0) numh--;
    return [ML, MD, MH, numl, numd, numh, lset, dset] as const;
}

function contSize(tree: number[], hst: NumberArray) {
    let s = 0;
    for(let i = 0; i < hst.length; i++) s += hst[i] * tree[(i << 1) + 1];
    return s;
}

function _codeTiny(set: number[], tree: number[], out: Uint8Array, pos: number) {
    for(let i = 0; i < set.length; i += 2) {
        const l = set[i], rst = set[i + 1];  // console.log(l, pos, tree[(l<<1)+1]);
        pos = _writeLit(l, tree, out, pos);
        const rsl = l === 16 ? 2 : (l === 17 ? 3 : 7);
        if(l > 15) {
            _putsE(out, pos, rst);
            pos += rsl;
        }
    }
    return pos;
}


function _lenCodes(tree: number[], set: number[]) {
    let len = tree.length;
    while(len !== 2 && tree[len - 1] === 0) len -= 2;  // when no distances, keep one code with length 0
    for(let i = 0; i < len; i += 2) {
        const l = tree[i + 1], nxt = (i + 3 < len ? tree[i + 3] : -1),  nnxt = (i + 5 < len ? tree[i + 5] : -1),  prv = (i === 0 ? -1 : tree[i - 1]);
        if(l === 0 && nxt === l && nnxt === l) {
            let lz = i + 5;
            while(lz + 2 < len && tree[lz + 2] === l) lz += 2;
            const zc = Math.min((lz + 1 - i) >>> 1, 138);
            if(zc < 11) set.push(17, zc - 3);
            else set.push(18, zc - 11);
            i += zc * 2 - 2;
        } else if(l === prv && nxt === l && nnxt === l) {
            let lz = i + 5;
            while(lz + 2 < len && tree[lz + 2] === l) lz += 2;
            const zc = Math.min((lz + 1 - i) >>> 1, 6);
            set.push(16, zc - 3);
            i += zc * 2 - 2;
        } else {
            set.push(l, 0);
        }
    }
    return len >>> 1;
}

function _goodIndex(v: number, arr: number[]) {
    let i = 0;
    if(arr[i | 16] <= v) i |= 16;
    if(arr[i | 8] <= v) i |= 8;
    if(arr[i | 4] <= v) i |= 4;
    if(arr[i | 2] <= v) i |= 2;
    if(arr[i | 1] <= v) i |= 1;
    return i;
}

function _writeLit(ch: number, ltree: number[], out: Uint8Array, pos: number) {
    _putsF(out, pos, ltree[ch << 1]);
    return pos + ltree[(ch << 1) + 1];
}

function _putsE(dt: NumberArray, pos: number, val: number) {
    val = val << (pos & 7);
    const o = (pos >>> 3);
    dt[o] |= val;
    dt[o + 1] |= (val >>> 8);
}

function _putsF(dt: NumberArray, pos: number, val: number) {
    val = val << (pos & 7);
    const o = (pos >>> 3);
    dt[o] |= val;
    dt[o + 1] |= (val >>> 8);
    dt[o + 2] |= (val >>> 16);
}