huffman

{

    // Chars '+' and '/' replaced by '-' and '_' to avoid the increasing of the encoded text when
    // encoded to URI component.
    const intToBase64 = ('ABCDEFGHIJKLMNOPQRSTUVWXYZ'
        + 'abcdefghijklmnopqrstuvwxyz'
        + '0123456789-_').split('');
    const base64ToInt = {};

    const bin6LEToBase64 = {};
    const base64ToBin6LE = {};
    intToBase64.forEach((char, value) => {
        base64ToInt[char] = value;
        let bin = value.toString(2);
        bin = '0'.repeat(6 - bin.length) + bin;
        bin = bin.split('');
        bin.reverse();
        bin = bin.join('');
        bin6LEToBase64[bin] = char;
        base64ToBin6LE[char] = bin;
    });

    const bytesToBase64 = bytes => {
        let res = '';
        const {length} = bytes;
        for (let i=3; i<=length; i+=3) {
            const a = bytes[i - 3];
            const b = bytes[i - 2];
            const c = bytes[i - 1];
            const int24 = a | (b << 8) | (c << 16);
            res += intToBase64[int24 & 63];
            res += intToBase64[(int24 >> 6) & 63];
            res += intToBase64[(int24 >> 12) & 63];
            res += intToBase64[(int24 >> 18) & 63];
        }
        const left = length % 3;
        let int = 0;
        for (let i=length-left, shift=0; i<length; ++i, shift+=8) {
            int |= bytes[i] << shift;
        }
        const nBits = left*8;
        for (let i=0; i<nBits; i+=6) {
            res += intToBase64[(int >> i) & 63];
        }
        return res;
    };

    const base64ToBytes = (base64, bytes) => {
        if (bytes === undefined) bytes = [];
        const {length} = base64;
        let j = 0;
        for (let i=4; i<=length; i+=4) {
            const a = base64ToInt[base64.charAt(i - 4)];
            const b = base64ToInt[base64.charAt(i - 3)];
            const c = base64ToInt[base64.charAt(i - 2)];
            const d = base64ToInt[base64.charAt(i - 1)];
            const int24 = a | (b << 6) | (c << 12) | (d << 18);
            bytes[j++] = int24 & 0xff;
            bytes[j++] = (int24 >> 8) & 0xff;
            bytes[j++] = (int24 >> 16) & 0xff;
        }
        const left = length%4;
        let int = 0;
        for (let i=length-left, shift=0; i<length; ++i, shift+=6) {
            int |= base64ToInt[base64.charAt(i)] << shift;
        }
        const nBits = left*6;
        for (let i=8; i<=nBits; i+=8) {
            bytes[j++] = (int >> (i - 8)) & 0xff;
        }
        return bytes;
    };

    const binaryStringToBase64 = string => {
        const {length} = string;
        let res = '';
        for (let i=6; i<=length; i+=6) {
            const bin = string.substr(i - 6, 6);
            res += bin6LEToBase64[bin];
        }
        const left = string.substr(length - length%6);
        if (left !== '') {
            res += bin6LEToBase64[left + '0'.repeat(6 - left.length)];
        }
        return res;
    };

    const base64ToBinaryString = base64 => {
        const {length} = base64;
        let res = '';
        for (let i=0; i<length; ++i) {
            res += base64ToBin6LE[base64.charAt(i)];
        }
        return res;
    };

    const stringToUtf8Bytes = (str, bytes = []) => {
        const n = str.length;
        let j = 0;
        for (let i=0; i<n; ++i) {
            const code = str.charCodeAt(i);
            if (code < (1 << 7)) {
                bytes[j++] = code;
            } else if (code < (1 << 11)) {
                bytes[j++] = 0b11000000 | (code >> 6);
                bytes[j++] = 0b10000000 | code & 0b00111111;
            } else {
                bytes[j++] = 0b11100000 | (code >> 12);
                bytes[j++] = 0b10000000 | (code >> 6) & 0b00111111;
                bytes[j++] = 0b10000000 | code & 0b00111111;
            }
        }
        return bytes;
    };

    const utf8BytesToString = bytes => {
        let res = '';
        const n = bytes.length;
        for (let i=0; i<n;) {
            let byte = bytes[i++];
            if ((byte & 0b10000000) === 0b10000000) {
                if ((byte & 0b11100000) === 0b11000000) {
                    byte = (byte & 0b00011111) << 6;
                    byte |= bytes[i++] & 0b00111111;
                } else {
                    byte = (byte & 0b00001111) << 12;
                    byte |= (bytes[i++] & 0b00111111) << 6;
                    byte |= bytes[i++] & 0b00111111;
                }
            }
            res += String.fromCharCode(byte);
        }
        return res;
    };

    const countFrequency = array => {
        const map = {};
        const nodes = [];
        const {length} = array;
        const string = typeof array === 'string';
        for (let i=length; i!==0;) {
            const value = string? array.charCodeAt(--i): array[--i];
            const node = map[value];
            if (node !== undefined) {
                ++ node.n;
            } else {
                const node = {n: 1, value};
                map[value] = node;
                nodes.push(node);
            }
        }
        return nodes;
    };

    const heapMoveUp = (heap, node, index) => {
        const {n} = node;
        while (index !== 0) {
            const parent_index = (index - 1) >> 1;
            const parent = heap[parent_index];
            if (parent.n <= n) break;
            heap[index] = parent;
            index = parent_index;
        }
        heap[index] = node;
    };

    const fixHeap = heap => {
        const {length} = heap;
        for (let i=1; i<length; ++i) {
            heapMoveUp(heap, heap[i], i);
        }
    };

    const heapMoveDown = (heap, node, index, length) => {
        const {n} = node;
        for (;;) {
            const i0 = (index << 1)|1;
            if (i0 >= length) break;
            const i1 = i0 + 1;
            if (i1 >= length) {
                const child = heap[i0];
                if (child.n >= n) break;
                heap[index] = child;
                index = i0;
                break;
            }
            const c0 = heap[i0];
            const c1 = heap[i1];
            const n0 = c0.n;
            const n1 = c1.n;
            if (n0 <= n1) {
                if (n0 >= n) break;
                heap[index] = c0;
                index = i0;
                continue;
            }
            if (n1 >= n) break;
            heap[index] = c1;
            index = i1;
        }
        heap[index] = node;
    };

    const heapPop = (heap, length) => {
        const res = heap[0];
        const node = heap[--length];
        heapMoveDown(heap, node, 0, length);
        return res;
    };

    const heapPush = (heap, node, length) => {
        heap[length] = node;
        heapMoveUp(heap, node, length);
    };

    const createTree = heap => {
        let {length} = heap;
        if (length === 0) {
            heap.push({value: 0, n: 0}, {value: 1, n: 0});
            length = 2;
        } else if (length === 1) {
            const node = heap[0];
            heap.push({value: node.value^1, n: 0});
            length = 2;
        }
        while (length > 1) {
            const a = heapPop(heap, length--);
            const b = heapPop(heap, length--);
            const node = {a, b, n: a.n + b.n};
            heapPush(heap, node, length++);
        }
        return heap[0];
    };

    const stringifyTree = ({value, a, b}) => {
        if (a == null) {
            return value;
        }
        return `{${stringifyTree(a)};${stringifyTree(b)}}`;
    };

    const encodeTree = tree => {
        const levels = [];
        let allChars = '';
        const addNode = (node, level) => {
            const {value, a, b} = node;
            levels[level] = (levels[level] || '') + ((value !== undefined)|0);
            if (value === undefined) {
                addNode(a, level + 1);
                addNode(b, level + 1);
            } else {
                allChars += String.fromCharCode(value);
            }
        };
        addNode(tree, 0);
        const structure = binaryStringToBase64(levels.join('').substr(1));
        const chars = bytesToBase64(stringToUtf8Bytes(allChars));
        return `${structure}.${chars}`;
    };

    const mapTreeForward = tree => {
        const map = {};
        const mapNode = ({a, b, value}, bin) => {
            if (value === undefined) {
                mapNode(a, bin + '0');
                mapNode(b, bin + '1');
            } else {
                map[value] = bin;
            }
        };
        mapNode(tree, '');
        return map;
    };

    const mapTreeBackward = tree => {
        const map = {};
        const mapNode = ({a, b, value}, bin) => {
            if (value === undefined) {
                mapNode(a, bin + '0');
                mapNode(b, bin + '1');
            } else {
                map[bin] = String.fromCharCode(value);
            }
        };
        mapNode(tree, '');
        return map;
    };

    const decodeTree = string => {
        const [structure, chars] = string.split('.');
        const bin = base64ToBinaryString(structure);
        const nBits = bin.length;
        const root = {a: null, b: null};
        const queue = [root];
        for (let i=0; i<nBits; ++i) {
            let node = {a: null, b: null};
            let parent = queue[0];
            if (parent.a === null) {
                parent.a = node;
            } else {
                parent.b = node;
                queue.splice(0, 1);
            }
            const bit = bin.charAt(i);
            if (bit === '0') {
                queue.push(node);
            } else if (bit !== '1') {
                throw 'Invalid huffman tree';
            }
            if (queue.length === 0) {
                break;
            }
        }
        const allChars = utf8BytesToString(base64ToBytes(chars));
        let index = 0;
        const addValue = node => {
            const {a, b} = node;
            if (a) {
                addValue(a);
                addValue(b);
            } else {
                const value = allChars.charCodeAt(index++);
                if (isNaN(value)) {
                    throw 'Incomplete character list';
                }
                node.value = value;
            }
        };
        addValue(root);
        return root;
    };

    const encodeSize = size => {
        return bytesToBase64([size&0xff, (size >> 8)&0xff, (size >> 16)&0xff]);
    };

    const decodeSize = base64 => {
        const [a, b, c] = base64ToBytes(base64);
        return a | (b << 8) | (c << 8);
    };

    const encodeText = (text, map) => {
        const {length} = text;
        let res = '';
        let buffer = '';
        for (let i=0; i<length;) {
            for (let j=0; i<length && j<100; ++i, ++j) {
                buffer += map[text.charCodeAt(i)];
            }
            const bLen = buffer.length;
            const left = bLen%6;
            const flushed = bLen - left;
            res += binaryStringToBase64(buffer.substr(0, flushed));
            buffer = buffer.substr(flushed);
        }
        res += binaryStringToBase64(buffer);
        return encodeSize(length) + '.' + res;
    };

    const decodeText = (base64, textSize, map) => {
        const {length} = base64;
        let buffer = '';
        let text = '', i;
        for (i=0; i < length && text.length < textSize;) {
            const size = Math.min(length - i, 100);
            buffer += base64ToBinaryString(base64.substr(i, size));
            i += size;
            const bLen = buffer.length;
            let n = 0;
            let bin = '';
            for (let j=0; j<bLen; ++j) {
                bin += buffer.charAt(j);
                const value = map[bin];
                if (value !== undefined) {
                    text += value;
                    if (text.length >= textSize) break;
                    n += bin.length;
                    bin = '';
                }
            }
            buffer = buffer.substr(n);
        }
        if (i !== length || text.length !== textSize) {
            throw 'Invalid content';
        }
        return text;
    };

    const compress = text => {
        const heap = countFrequency(text);
        fixHeap(heap);
        const tree = createTree(heap);
        const forwardMap = mapTreeForward(tree);
        const head = encodeTree(tree);
        const body = encodeText(text, forwardMap);
        return head + '.' + body;
    };

    const decompress = compressed => {
        compressed = compressed.split('.');
        if (compressed.length !== 4) {
            throw 'Invalid format';
        }
        const [a, b, c, d] = compressed;
        const tree = decodeTree(a + '.' + b);
        const backwardMap = mapTreeBackward(tree);
        const size = decodeSize(c);
        if (typeof size !== 'number' || isNaN(size)) {
            throw 'Invalid size';
        }
        return decodeText(d, size, backwardMap);
    };

    window.huffman = {compress, decompress};

}