Re: [xz-devel] Re: java LZDecoder small improvement

[Brett Okken]

I still need to do more testing across jdk 8 and 15, but initial
returns on this are pretty positive. The repeating byte file is
meaningfully faster than baseline. One of my test files (image1.dcm)
does not improve much from baseline, but the other 2 files do.


diff --git a/src/org/tukaani/xz/lz/LZDecoder.java
b/src/org/tukaani/xz/lz/LZDecoder.java
index 85b2ca1..b062a9d 100644
--- a/src/org/tukaani/xz/lz/LZDecoder.java
+++ b/src/org/tukaani/xz/lz/LZDecoder.java
@@ -12,6 +12,8 @@ package org.tukaani.xz.lz;

 import java.io.DataInputStream;
 import java.io.IOException;
+import java.util.Arrays;
+
 import org.tukaani.xz.ArrayCache;
 import org.tukaani.xz.CorruptedInputException;

@@ -92,14 +94,52 @@ public final class LZDecoder {
         pendingDist = dist;

         int back = pos - dist - 1;
-        if (dist >= pos)
+        if (dist >= pos) {
+            // We won't get here if the dictionary isn't full.
+            assert full == bufSize;
+
+            // The distance wraps around to the end of the cyclic dictionary
+            // buffer. Here we will never copy more than dist + 1 bytes
+            // and so the copying won't repeat from its own output. Thus,
+            // we can always use arraycopy safely.
             back += bufSize;
+            int copySize = Math.min(bufSize - back, left);
+            assert copySize <= dist + 1;
+            System.arraycopy(buf, back, buf, pos, copySize);
+            pos += copySize;
+            back = 0;
+            left -= copySize;
+
+            if (left == 0)
+                return;
+        }
+
+        assert left > 0;
+
+        //the difference between pos and back is how much data is in the source
+        //buffer to be repeated
+        final int delta = pos - back;
+        if (delta < left) {
+            // We are copying more than dist + 1 bytes and thus will partly
+            // copy from our own output.
+            if (delta > 1) {
+                // take the size of data to be repeated, and copy it in loop
+                for (int i=0, j=left/delta; i<j; ++i) {
+                    System.arraycopy(buf, back, buf, pos, delta);
+                    pos += delta;
+                    back += delta;
+                    left -= delta;
+                }
+            } else {
+                //optimize the case of a single byte being repeated
+                Arrays.fill(buf, pos, pos + left, buf[back]);
+                pos += left;
+                left = 0;
+            }
+        }

-        do {
-            buf[pos++] = buf[back++];
-            if (back == bufSize)
-                back = 0;
-        } while (--left > 0);
+        System.arraycopy(buf, back, buf, pos, left);
+        pos += left;

         if (full < pos)
             full = pos;