[xz-devel] improve java delta performance

[Brett Okken]

These changes reduce the time of DeltaEncoder by ~65% and DeltaDecoder
by ~40%, assuming using arrays that are several KB in size.

diff --git a/src/org/tukaani/xz/delta/DeltaCoder.java 
b/src/org/tukaani/xz/delta/DeltaCoder.java
index d94eb66..ccb702d 100644xz/delta/DeltaCoder.java b/src/org/tukaani/xz/delt
--- a/src/org/tukaani/xz/delta/DeltaCoder.java
+++ b/src/org/tukaani/xz/delta/DeltaCoder.java
@@ -12,16 +12,15 @@ package org.tukaani.xz.delta;
 abstract class DeltaCoder {
     static final int DISTANCE_MIN = 1;
     static final int DISTANCE_MAX = 256;
-    static final int DISTANCE_MASK = DISTANCE_MAX - 1;

     final int distance;
-    final byte[] history = new byte[DISTANCE_MAX];
-    int pos = 0;
+    final byte[] history;

     DeltaCoder(int distance) {
         if (distance < DISTANCE_MIN || distance > DISTANCE_MAX)
-            throw new IllegalArgumentException();
+            throw new IllegalArgumentException("invalid distance: " + 
distance);

         this.distance = distance;
+        this.history = new byte[distance];
     }
 }


diff --git a/src/org/tukaani/xz/delta/DeltaDecoder.java 
b/src/org/tukaani/xz/delta/DeltaDecoder.java
index 154cbf3..d0bce28 100644
--- a/src/org/tukaani/xz/delta/DeltaDecoder.java
+++ b/src/org/tukaani/xz/delta/DeltaDecoder.java
@@ -15,10 +15,26 @@ public class DeltaDecoder extends DeltaCoder {
     }

     public void decode(byte[] buf, int off, int len) {
-        int end = off + len;
-        for (int i = off; i < end; ++i) {
-            buf[i] += history[(distance + pos) & DISTANCE_MASK];
-            history[pos-- & DISTANCE_MASK] = buf[i];
+        int i=0;
+        // first process from history buffer
+        for (int j = Math.min(len, distance); i < j; ++i) {
+            buf[off + i] += history[i];
+        }
+
+        // then process rest just within buf
+        for ( ; i<len; ++i) {
+            buf[off + i] += buf[off + i - distance];
+        }
+
+        // finally, populate the history buffer
+        if (len >= distance) {
+            System.arraycopy(buf, off + len - distance, history, 0, distance);
+        } else {
+            assert i == len;
+            // copy from end of buffer to beginning
+            System.arraycopy(history, i, history, 0, distance - i);
+            // now copy all of in to the end of the buffer
+            System.arraycopy(buf, off, history, distance - i, len);
         }
     }
 }


diff --git a/src/org/tukaani/xz/delta/DeltaEncoder.java 
b/src/org/tukaani/xz/delta/DeltaEncoder.java
index 17accce..ae8688e 100644
--- a/src/org/tukaani/xz/delta/DeltaEncoder.java
+++ b/src/org/tukaani/xz/delta/DeltaEncoder.java
@@ -15,10 +15,28 @@ public class DeltaEncoder extends DeltaCoder {
     }

     public void encode(byte[] in, int in_off, int len, byte[] out) {
-        for (int i = 0; i < len; ++i) {
-            byte tmp = history[(distance + pos) & DISTANCE_MASK];
-            history[pos-- & DISTANCE_MASK] = in[in_off + i];
-            out[i] = (byte)(in[in_off + i] - tmp);
+        int i=0;
+        // first deal with comparisons to the history buffer
+        for (int j=Math.min(len, distance); i<j; ++i) {
+            out[i] = (byte) (in[in_off + i] - history[i]);
+        }
+        // now fill the history buffer with the final (distance) bytes in 
source
+        if (len >= distance) {
+            System.arraycopy(in, in_off + len - distance, history, 0, 
distance);
+        } else {
+            assert i == len;
+            // copy from end of history buffer to beginning
+            System.arraycopy(history, i, history, 0, distance - i);
+            // now copy all of "in" to end of history buffer
+            System.arraycopy(in, in_off, history, distance - i, len);
+        }
+
+        for ( ; i < len; ++i) {
+            out[i] = (byte) (in[in_off + i] - in[in_off + i - distance]);
         }
     }
 }