Create "changset" of two bytearrays

Question

I have some binary data. I will change over time, some bytes get added here and there, some get changed. Overall most of the bytearray remains the same.

Is there any library, preferably Actionscript 3, that generats a "changeset" (is there a better name for this?) out of two bytearrays. Also it should let me apply a changeset to a bytearray and return the resulting new bytearray.

Does this make sense? I was not sure how to formulate my problem best.

EDIT for Clarification:

What i want is something that only emits changes, thus making the "changeset" as small as possible. So if only 1KB of a 1MB Binary have changed, the changeset should be a bytearray of about 1KB size.

EDIT:

Basically i need an AS3 Version of http://www.daemonology.net/bsdiff/ i think

Matthias · Answer 1 · 2012-07-26T20:42:33.950

I do not know any AS3 library for that but if I understood you right, coding this from scratch isn't as hard or time-consuming as you might think. Here is my (naive) approach on that. Maybe this already fits your needs.

Example output

example output

Code

package {
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.utils.ByteArray;

    public class Main extends Sprite {

        public function Main():void {
            if (stage)
                init();
            else
                addEventListener(Event.ADDED_TO_STAGE, init);
        }


        private function createDiff(original:ByteArray, comparedTo:ByteArray):ByteArray {
            var diff:ByteArray = new ByteArray();
            var length:uint = Math.min(original.length, comparedTo.length);
            original.position = 0;
            comparedTo.position = 0;
            for (var i:int = 0; i < length; i++) {
                var byteOriginal:int = original.readByte();
                var byteComparedTo:int = comparedTo.readByte();
                if (byteOriginal != byteComparedTo) {
                    diff.writeByte(byteComparedTo - byteOriginal);
                }
                else {
                    diff.writeByte(0);
                }
            }
            diff.compress();
            return diff;
        }

        private function applyDiff(original:ByteArray, diff:ByteArray):ByteArray {
            var result:ByteArray = new ByteArray();
            diff.uncompress();
            original.position = 0;
            diff.position = 0;
            var length:uint = Math.min(original.length, diff.length);
            for (var i:uint = 0; i < length; i++) {
                var byteOriginal:int = original.readByte();
                var byteDiff:int = diff.readByte();
                result.writeByte(byteOriginal + byteDiff);
            }
            return result;
        }

        private function init(e:Event = null):void {
            removeEventListener(Event.ADDED_TO_STAGE, init);
            // generate one random byte array and a slightly different variant
            var length:uint = 128;
            var a:ByteArray = new ByteArray();
            var b:ByteArray = new ByteArray();
            for (var i:int = 0; i < length; i++) {
                var value:int;
                value = 127 - Math.floor(Math.random() * 256);
                a.writeByte(value);
                if (value > 64) {
                    value = 127 - Math.floor(Math.random() * 256);
                }
                b.writeByte(value);
            }
            // create a diff and apply it to the original byte array for verification
            var diff:ByteArray = createDiff(a, b);
            var result:ByteArray = applyDiff(a, diff);
            // trace the byte arrays
            a.position = 0;
            b.position = 0;
            diff.position = 0;
            result.position = 0;
            var outputA:String = "";
            var outputB:String = "";
            var outputDiff:String = "";
            var outputResult:String = "";
            for (var k:int = 0; k < length; k++) {
                outputA += a.readByte() + "\t";
                outputB += b.readByte() + "\t";
                outputDiff += diff.readByte() + "\t";
                outputResult += result.readByte() + "\t";
            }
            trace("1st: \t" + outputA);
            trace("2nd: \t" + outputB);
            trace("diff:\t" + outputDiff);
            trace("test:\t" + outputResult);
        }

    }

}

thanks for your help. But what i want is something that only emits changes, thus making the "changeset" as small as possible. So if only 1KB of a 1MB Binary have changed, the changeset should be a bitearray of about 1KB size. — TobiHeidi, Jul 26 '12 at 17:47
@TobiHeidi Use `compress()` on the diff ByteArray. You could also save only the changes in a `Dictionary` and then write it to a ByteArray but this would add even more overhead. I will update my code. — Matthias, Jul 26 '12 at 20:33
this will not help. Example: I got an 1 MB file and just insert a random byte on position 7. Every other byte moves on step further. The resulting changset will not shrink from compress() call [unless the original bytearrays would shrink from a compress() call, but i wont as it is zipped already]. — TobiHeidi, Jul 27 '12 at 08:27
i am think about porting http://www.daemonology.net/bsdiff/ to as3 as this should be exactly what i need. Too bad i have very little python knowledge — TobiHeidi, Jul 27 '12 at 08:28

Create "changset" of two bytearrays

1 Answers1

Example output

Code