dead_code_elimination.js

/*
code
{
    char: string,
    cho: number,
    jung: number,
    jong: number,
    eliminate: boolean
}
*/

/*
code space
[
    [code, code, code, ...],
    [code, code, code, ...],
    [code, code, code, ...],
    ...
]
width: number
height: number
toString: function
*/

/*
vector
{
    x: number,
    y: number
}
null means no change
NaN means reflection
*/

/*
coord
{
    x: number,
    y: number,
    dx: number,
    dy: number
}
*/

var entryPoint = {x: 0, y: 0};
var initialVector = {x: 0, y: 1};

function charToCode(char) {
    var charCode = char.charCodeAt();
    var code = {char: char, cho: -1, jung: -1, jong: -1, eliminate: false};
    if (checkMeaningless(char))
        return code;
    charCode -= 0xAC00;
    code.cho = parseInt(charCode / 588);
    code.jung = parseInt(charCode / 28) % 21;
    code.jong = charCode % 28;
    return code;
}

function checkMeaningless(char) {
    var charCode = char.charCodeAt();
    return charCode < 0xAC00 || charCode > 0xD7A3;
}

function stringToCodeSpace(string) {
    var codeSpace = string.split(/\n|\r\n/g);
    var width = 0;
    codeSpace = codeSpace.map(function (line) {
        var codeLine = [];
        var length = line.length;
        if (width < length)
            width = length;
        for (var i = 0; i < length; ++i)
            codeLine.push(charToCode(line.charAt(i)));
        return codeLine;
    });
    codeSpace.width = width;
    codeSpace.height = codeSpace.length;
    codeSpace.toString = function (blankChar) {
        if (!blankChar)
            blankChar = '\u3147';
        var string = codeSpace.map(function (codeLine) {
            return codeLine.map(function (code) {
                return (code && !code.eliminate) ? code.char : blankChar;
            }).join('');
        }).join('\n');
        return string;
    }
    return codeSpace;
}

function getVector(code) {
    if (!code)
        return {x: null, y: null};
    switch (code.jung) {
    case 0:
        return {x: 1, y: 0};
    case 2:
        return {x: 2, y: 0};
    case 4:
        return {x: -1, y: 0};
    case 6:
        return {x: -2, y: 0};
    case 8:
        return {x: 0, y: -1};
    case 12:
        return {x: 0, y: -2};
    case 13:
        return {x: 0, y: 1};
    case 17:
        return {x: 0, y: 2};
    case 18:
        return {x: null, y: NaN};
    case 19:
        return {x: NaN, y: NaN};
    case 20:
        return {x: NaN, y: null};
    default:
        return {x: null, y: null};
    }
}

function seekNext(codeSpace, x, y, dx, dy) {
    var result = [];
    var width = codeSpace.width;
    var height = codeSpace.height;
    var code = codeSpace[y][x];
    if (!code)
        return result;
    var vector = getVector(code);
    if (vector.x === null)
        vector.x = dx;
    else if (isNaN(vector.x))
        vector.x = -dx;
    if (vector.y === null)
        vector.y = dy;
    else if (isNaN(vector.y))
        vector.y = -dy;
    function seek(x, y, dx, dy) {
        var wrap = false;
        while (true) {
            if (x >= width)
                x = 0;
            else if (x < 0)
                x = width - 1;
            if (y >= height)
                y = 0;
            else if (y < 0)
                y = height - 1;
            var code = codeSpace[y][x];
            if (code && code.jung !== -1) {
                result.push({x: x, y: y, dx: dx, dy: dy});
                return;
            }
            x += dx;
            y += dy;
            if (x >= width || x < 0 || y >= height || y < 0) {
                if (wrap)
                    return;
                else
                    wrap = true;
            }
        }
    }
    switch (code.cho) {
    case 2: case 3: case 4: case 5: case 6:
    case 8: case 10: case 12: case 14: case 16:
    case 17:
        seek(x + vector.x, y + vector.y, vector.x, vector.y);
        seek(x - vector.x, y - vector.y, -vector.x, -vector.y);
        break;
    case 18:
        break;
    default:
        seek(x + vector.x, y + vector.y, vector.x, vector.y);
        break;
    }
    return result;
}

function eliminateDeadCode(string, blankChar) {
    var callStack = [];
    function saveAliveCode(codeSpace, x, y, dx, dy) {
        seekNext(codeSpace, x, y, dx, dy).forEach(function (coord) {
            var code = codeSpace[coord.y][coord.x];
            if (!(code && code.eliminate))
                return;
            code.eliminate = false;
            var dx = coord.dx;
            var dy = coord.dy;
            var direction = Math.abs(dx) > Math.abs(dy);
            var horizontal = true;
            var vertical = false;
            switch (code.jung) {
            case 18:
                if (direction == vertical)
                    return;
                break;
            case 19:
                return;
            case 20:
                if (direction == horizontal)
                    return;
                break;
            }
            callStack.push([codeSpace, coord.x, coord.y, dx, dy]);
        });
    }
    var codeSpace = stringToCodeSpace(string);
    codeSpace.forEach(function (codeLine) {
        codeLine.forEach(function (code) {
            code.eliminate = true;
        });
    });
    var entryCode = codeSpace[entryPoint.y][entryPoint.x];
    if (entryCode)
        entryCode.eliminate = false;
    callStack.push([codeSpace,
                    entryPoint.x, entryPoint.y,
                    initialVector.x, initialVector.y]);
    while (callStack.length)
        saveAliveCode.apply(null, callStack.pop());
    return codeSpace.toString(blankChar);
}

function eliminateMeaninglessLine(string) { // vertical compress
    var lines = string.split(/\n|\r\n/g);
    var result;
    var i, j;
    var linesLength = lines.length;
    var halfLinesLength = linesLength >> 1;
    for (i = 0; i < linesLength; ++i) {
        var line = lines[i];
        for (j = 0; j < line.length; ++j) {
            if (!checkMeaningless(line.charAt(j))) {
                line.meaningless = false;
                break;
            }
        }
        line.meaningless = true;
    }
    result = [];
    for (i = 0; i < halfLinesLength; ++i) {
        var first = lines[i * 2];
        var second = lines[i * 2 + 1];
        if (first.meaningless && second && second.meaningless)
            continue;
        result.push(first, second);
    }
    return result.join('\n');
}