Implementation of PyBuffer.copyFrom dealing correctly with overlap.

jeff5 · jeff5 · commit 1351c1d1e6b7 · 2016-06-26T22:04:50.000+01:00
Fixes regression in test_memoryview due to recent refactoring. JUnit
test provided explicitly for copyFrom() sliced versions of self.
diff --git a/src/org/python/core/buffer/Base1DBuffer.java b/src/org/python/core/buffer/Base1DBuffer.java
@@ -77,7 +77,7 @@ protected int calcGreatestIndex() {
         } else if (stride > 0) {
             return index0 + (shape[0] - 1) * stride;
         } else {
-            return index0 - 1;
+            return index0;
         }
     }
 
diff --git a/src/org/python/core/buffer/BaseArrayBuffer.java b/src/org/python/core/buffer/BaseArrayBuffer.java
@@ -113,6 +113,23 @@ public void copyTo(int srcIndex, byte[] dest, int destPos, int count)
     @Override
     public void copyFrom(byte[] src, int srcPos, int destIndex, int count)
             throws IndexOutOfBoundsException, PyException {
+        copyFrom(src, srcPos, 1, destIndex, count);
+    }
+
+    /**
+     * Generalisation of {@link PyBuffer#copyFrom(byte[], int, int, int)} to allow a stride within
+     * the source array.
+     *
+     * @param src source byte array
+     * @param srcPos byte-index location in source of first byte to copy
+     * @param srcStride byte-index increment from one item to the next
+     * @param destIndex starting item-index in the destination (i.e. <code>this</code>)
+     * @param count number of items to copy in
+     * @throws IndexOutOfBoundsException if access out of bounds in source or destination
+     * @throws PyException (TypeError) if read-only buffer
+     */
+    protected void copyFrom(byte[] src, int srcPos, int srcStride, int destIndex, int count)
+            throws IndexOutOfBoundsException, PyException {
 
         checkWritable();
 
@@ -123,16 +140,19 @@ public void copyFrom(byte[] src, int srcPos, int destIndex, int count)
             int skip = stride - itemsize;
             int d = byteIndex(destIndex);
 
+            int srcSkip = srcStride - itemsize;
+
             // Strategy depends on whether items are laid end-to-end or there are gaps
-            if (skip == 0) {
+            if (skip == 0 && srcSkip == 0) {
                 // Straight copy of contiguous bytes
                 System.arraycopy(src, srcPos, storage, d, count * itemsize);
             } else {
-                // Non-contiguous copy: single byte items
                 int limit = d + count * stride, s = srcPos;
                 if (itemsize == 1) {
+                    // Non-contiguous copy: single byte items
                     for (; d != limit; d += stride) {
-                        storage[d] = src[s++];
+                        storage[d] = src[s];
+                        s += srcStride;
                     }
                 } else {
                     // Non-contiguous copy: itemsize bytes then skip to next item
@@ -141,6 +161,7 @@ public void copyFrom(byte[] src, int srcPos, int destIndex, int count)
                         while (d < t) {
                             storage[d++] = src[s++];
                         }
+                        s += srcSkip;
                     }
                 }
             }
@@ -149,56 +170,41 @@ public void copyFrom(byte[] src, int srcPos, int destIndex, int count)
 
     @Override
     public void copyFrom(PyBuffer src) throws IndexOutOfBoundsException, PyException {
-        if (src instanceof BaseArrayBuffer) {
+        if (src instanceof BaseArrayBuffer && !this.overlaps((BaseArrayBuffer)src)) {
+            // We can do this efficiently, copying between arrays.
             copyFromArrayBuffer((BaseArrayBuffer)src);
         } else {
             super.copyFrom(src);
         }
     }
 
+    private boolean overlaps(BaseArrayBuffer src) {
+        if (src.storage != this.storage) {
+            return false;
+        } else {
+            int low = calcLeastIndex(), high = calcGreatestIndex();
+            int srcLow = src.calcLeastIndex(), srcHigh = src.calcGreatestIndex();
+            return (srcHigh >= low && high >= srcLow);
+        }
+    }
+
     private void copyFromArrayBuffer(BaseArrayBuffer src) throws IndexOutOfBoundsException,
             PyException {
 
-        checkWritable();
         src.checkDimension(1);
 
         int itemsize = getItemsize();
         int count = getSize();
 
-        // Block operation if different item or overall size (permit reshape)
+        // Block operation if different item or overall size
         if (src.getItemsize() != itemsize || src.getSize() != count) {
             throw differentStructure();
         }
 
-        for (int i = 0; i < count; i++) {
-            int s = src.byteIndex(i), d = byteIndex(i);
-            for (int j = 0; j < itemsize; j++) {
-                storage[d++] = src.byteAtImpl(s++);
-            }
-        }
+        // We depend on the striding copyFrom() acting directly on the source storage
+        copyFrom(src.storage, src.index0, src.strides[0], 0, count);
     }
 
-    /**
-     * Copy blocks of bytes, equally spaced in the source array, to locations equally spaced in the
-     * destination array, which may be the same array. The byte at
-     * <code>src[srcPos+k*srcStride+j]</code> will be copied to
-     * <code>dst[dstPos+k*dstStride+j]</code> for <code>0&le;k&lt;count</code> and
-     * <code>0&le;j&lt;size</code>. When the source and destination are the same array, the method
-     * deals correctly with the risk that a byte gets written under the alias <code>dst[x]</code>
-     * before it should have been copied referenced as <code>src[y]</code>.
-     *
-     * @param size of the blocks of bytes
-     * @param src the source array
-     * @param srcPos the position of the first block in the source
-     * @param srcStride the interval between the start of each block in the source
-     * @param dst the destination array
-     * @param dstPos the position of the first block in the destination
-     * @param dstStride the interval between the start of each block in the destination
-     * @param count the number of blocks to copy
-     */
-    private static void slicedArrayCopy(int size, byte[] src, int srcPos, int srcStride,
-            byte[] dst, int dstPos, int dstStride, int count) {}
-
     @Override
     protected ByteBuffer getNIOByteBufferImpl() {
         // The buffer spans the whole storage, which may include data not in the view
diff --git a/src/org/python/core/buffer/BaseBuffer.java b/src/org/python/core/buffer/BaseBuffer.java
@@ -536,18 +536,21 @@ public void copyFrom(PyBuffer src) throws IndexOutOfBoundsException, PyException
 
         int itemsize = getItemsize();
         int count = getSize();
+        int byteLen = src.getLen();
 
         // Block operation if different item or overall size (permit reshape)
-        if (src.getItemsize() != itemsize || src.getLen() != count * itemsize) {
+        if (src.getItemsize() != itemsize || byteLen != count * itemsize) {
             throw differentStructure();
         }
 
-        // XXX Re-think this using ByteBuffer when the API provides a byteIndex() method
-        assert itemsize == 1;
-        // XXX This only moves the first byte of each item
-        for (int i = 0; i < count; i++) {
-            storeAt(src.byteAt(i), i);
-        }
+        /*
+         * It is not possible in general to know that this and src do not share storage. There is
+         * always a risk of incorrect results if we do not go via an intermediate byte array.
+         * Sub-classes may be able to avoid this.
+         */
+        byte[] t = new byte[byteLen];
+        src.copyTo(t, 0);
+        this.copyFrom(t, 0, 0, count);
     }
 
     @Override
diff --git a/src/org/python/core/buffer/BaseNIOBuffer.java b/src/org/python/core/buffer/BaseNIOBuffer.java
@@ -221,61 +221,6 @@ protected void copyFrom(ByteBuffer src, int dstIndex, int count)
         }
     }
 
-    /**
-     * {@inheritDoc}
-     * <p>
-     * The default implementation in <code>BaseNIOBuffer</code> deals with the general
-     * one-dimensional case.
-     */
-    @Override
-    public void copyFrom(PyBuffer src) throws IndexOutOfBoundsException, PyException {
-
-        int length = getLen();
-        int itemsize = getItemsize();
-
-        // Valid operation only if writable and same length and itemsize
-        checkWritable();
-        if (src.getLen() != length || src.getItemsize() != itemsize) {
-            throw differentStructure();
-        }
-
-        if (length > 0) {
-            // Pick up attributes necessary to choose an efficient copy strategy
-            int stride = getStrides()[0];
-            int skip = stride - itemsize;
-
-            ByteBuffer dst = getNIOByteBuffer();
-
-            // Strategy depends on whether destination items are laid end-to-end or there are gaps
-            if (skip == 0) {
-                // Straight copy to contiguous bytes
-                for (int i = 0; i < length; i++) {
-                    dst.put(src.byteAt(i));
-                }
-
-            } else if (itemsize == 1) {
-                // Non-contiguous copy: single byte items
-                int pos = dst.position();
-                for (int i = 0; i < length; i++) {
-                    dst.put(pos, src.byteAt(i));
-                    pos += stride;
-                }
-
-            } else {
-                // Non-contiguous copy: each time, and itemsize > 1
-                int pos = dst.position();
-                int s = 0;
-                for (int i = 0; i < length; i++) {
-                    for (int j = 0; j < itemsize; j++) {
-                        dst.put(pos++, src.byteAt(s++));
-                    }
-                    pos += skip;
-                }
-            }
-        }
-
-    }
-
     @Override
     protected ByteBuffer getNIOByteBufferImpl() {
         return storage.duplicate();
diff --git a/tests/java/org/python/core/PyBufferTest.java b/tests/java/org/python/core/PyBufferTest.java

Original file line number	Diff line number	Diff line change
`@@ -77,7 +77,7 @@ protected int calcGreatestIndex() {`
`77`	`77`	`} else if (stride > 0) {`
`78`	`78`	`return index0 + (shape[0] - 1) * stride;`
`79`	`79`	`} else {`
`80`		`- return index0 - 1;`
	`80`	`+ return index0;`
`81`	`81`	`}`
`82`	`82`	`}`
`83`	`83`