JS diff

// usage:
// var diff = new customdiff();
// data1 = data1.split('\n');
// data2 = data2.split('\n');
// var diffs = diff._diff(data1, data2);


var customdiff = function() {


};

customdiff.prototype._diff = function(src, dest) {
    // src, dest are arrays of comparable
    var srcDiffs = {};
    var destDiffs = {};

    var downVector = [];
    var upVector = [];

    this._lcs(src, 0, src.length, srcDiffs, dest, 0, dest.length, destDiffs, downVector, upVector);
    console.log(srcDiffs);
    console.log(destDiffs);


    var diffs = this._parseDiffs(src, srcDiffs, dest, destDiffs);
    console.log(diffs);
    return diffs;
};


customdiff.prototype._lcs = function(src, srcLower, srcUpper, srcDiffs, dest, destLower, destUpper, destDiffs, downVector, upVector) {
    while (srcLower < srcUpper && destLower < destUpper && src[srcLower] == dest[destLower]) {
        srcLower++;
        destLower++;
    }

    while (srcLower < srcUpper && destLower < destUpper && src[srcUpper-1] == dest[destUpper-1]) {
        srcUpper--;
        destUpper--;
    }

    if (srcLower == srcUpper) {
        while(destLower < destUpper) {
            destDiffs[destLower++] = true;
        }
    }
    else if (destLower == destUpper) {
        while (srcLower < srcUpper) {
            srcDiffs[srcLower++] = true;
        }
    }  
	else {
	    var smsrd = this._sms(src, srcLower, srcUpper, dest, destLower, destUpper, downVector, upVector);
	    
	    this._lcs(src, srcLower, smsrd.x, srcDiffs, dest, destLower, smsrd.y, destDiffs, downVector, upVector);
	    this._lcs(src, smsrd.x, srcUpper, srcDiffs, dest, smsrd.y, destUpper, destDiffs, downVector, upVector);
	}		
};



customdiff.prototype._sms = function(src, srcLower, srcUpper, dest, destLower, destUpper, downVector, upVector) {
    var ret = {};

    var max = src.length + dest.length + 1;
    var downK = srcLower - destLower;
    var upK = srcUpper - destUpper;

    var delta = (srcUpper - srcLower) - (destUpper - destLower); ;
    var oddDelta = (delta & 1) != 0;

    var downOffset = max - downK;
    var upOffset = max - upK;

    var maxD = Math.floor((srcUpper - srcLower + destUpper - destLower) / 2) + 1;

    downVector[downOffset + downK + 1] = srcLower;
    upVector[upOffset + upK - 1] = srcUpper;

    for (var d = 0; d <= maxD; d++) {
        for (var k = downK - d; k <= downK + d; k += 2) {
            var x, y;
            if (k == downK - d) {
                x = downVector[downOffset + k + 1];
            }
            else {
                x = downVector[downOffset + k - 1] + 1;
                if ((k < downK + d) && (downVector[downOffset + k + 1] >= x)) {
                    x = downVector[downOffset + k + 1];
                }
            }
            y = x - k;

            while ((x < srcUpper) && (y < destUpper) && (src[x] == dest[y])) {
                x++;
                y++;
            }
            downVector[downOffset + k] = x;

            if (oddDelta && (upK - d < k) && (k < upK + d)) {
                if (upVector[upOffset + k] <= downVector[downOffset + k]) {
                    ret.x = downVector[downOffset + k];
                    ret.y = downVector[downOffset + k] - k;
                    return ret;
                }
            }
        }

        for (var k = upK - d; k <= upK + d; k += 2) {
            var x, y;
            if (k == upK + d) {
                x = upVector[upOffset + k - 1];
            }
            else {
                x = upVector[upOffset + k + 1] - 1;
                if ((k > upK - d) && (upVector[upOffset + k - 1] < x)) {
                    x = upVector[upOffset + k - 1];
                }
            }
            y = x - k;

            while ((x > srcLower) && (y > destLower) && (src[x - 1] == dest[y - 1])) {
                x--;
                y--;
            }
            upVector[upOffset + k] = x;

            if (!oddDelta && (downK - d <= k) && (k <= downK + d)) {
                if (upVector[upOffset + k] <= downVector[downOffset + k]) {
                    ret.x = downVector[downOffset + k];
                    ret.y = downVector[downOffset + k] - k;
                    return ret;
                }
            }
        }
    }
};

customdiff.prototype._parseDiffs = function(src, srcDiffs, dest, destDiffs) {
    var diffs = [];
    var srcLine = 0;
    var destLine = 0;
    while (srcLine < src.length || destLine < dest.length) {
        if ((srcLine < src.length) && (srcDiffs[srcLine] == null)
            && (destLine < dest.length) && (destDiffs[destLine] == null)) {
            srcLine++;
            destLine++;
        }
        else {
            var srcStart = srcLine;
            var destStart = destLine;

            while (srcLine < src.length && (destLine >= dest.length || srcDiffs[srcLine] == true)) {
                srcLine++;
            }

            while (destLine < dest.length && (srcLine >= src.length || destDiffs[destLine] == true)) {
                destLine++;
            }

            if ((srcStart < srcLine) || (destStart < destLine)) {
                var diff = {};
                diff.srcStart = srcStart;
                diff.destStart = destStart;
                diff.srcDeleted = srcLine - srcStart;
                diff.destInserted = destLine - destStart;
                diffs.push(diff);
            }
        }
    }

    return diffs;
};