src/share/classes/java/util/zip/CRC32.java

*** 1,7 ****
  /*
!  * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
--- 1,7 ----
  /*
!  * Copyright (c) 1996, 2013, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
*** 23,34 ****
   * questions.
   */
  
  package java.util.zip;
  
- import java.nio.ByteBuffer;
  import sun.nio.ch.DirectBuffer;
  
  /**
   * A class that can be used to compute the CRC-32 of a data stream.
   *
   * <p> Passing a {@code null} argument to a method in this class will cause
--- 23,38 ----
   * questions.
   */
  
  package java.util.zip;
  
  import sun.nio.ch.DirectBuffer;
+ import java.lang.reflect.Field;
+ import java.nio.ByteBuffer;
+ import java.util.concurrent.RecursiveTask;
+ import java.util.concurrent.ForkJoinPool;
+ import sun.misc.Unsafe;
  
  /**
   * A class that can be used to compute the CRC-32 of a data stream.
   *
   * <p> Passing a {@code null} argument to a method in this class will cause
*** 53,63 ****
       * eight bits of the argument b).
       *
       * @param b the byte to update the checksum with
       */
      public void update(int b) {
!         crc = update(crc, b);
      }
  
      /**
       * Updates the CRC-32 checksum with the specified array of bytes.
       */
--- 57,70 ----
       * eight bits of the argument b).
       *
       * @param b the byte to update the checksum with
       */
      public void update(int b) {
!         int c = ~ crc;
!         b = timesXtoThe32[(b ^ c) & 0xFF];
!         b = b ^ (c >>> 8);
!         crc = ~b;
      }
  
      /**
       * Updates the CRC-32 checksum with the specified array of bytes.
       */
*** 66,85 ****
              throw new NullPointerException();
          }
          if (off < 0 || len < 0 || off > b.length - len) {
              throw new ArrayIndexOutOfBoundsException();
          }
!         crc = updateBytes(crc, b, off, len);
      }
  
      /**
       * Updates the CRC-32 checksum with the specified array of bytes.
       *
       * @param b the array of bytes to update the checksum with
       */
      public void update(byte[] b) {
!         crc = updateBytes(crc, b, 0, b.length);
      }
  
      /**
       * Updates the checksum with the bytes from the specified buffer.
       *
--- 73,97 ----
              throw new NullPointerException();
          }
          if (off < 0 || len < 0 || off > b.length - len) {
              throw new ArrayIndexOutOfBoundsException();
          }
! 
!         if (len < javaCRCIfSmallerThan) {
!             crc = updateBytesSimple(crc, b, off, len);
!         } else {
!             crc = updateBytesFJ(crc, b, off, len);
!         }
      }
  
      /**
       * Updates the CRC-32 checksum with the specified array of bytes.
       *
       * @param b the array of bytes to update the checksum with
       */
      public void update(byte[] b) {
!         crc = updateBytesFJ(crc, b, 0, b.length);
      }
  
      /**
       * Updates the checksum with the bytes from the specified buffer.
       *
*** 99,115 ****
          assert (pos <= limit);
          int rem = limit - pos;
          if (rem <= 0)
              return;
          if (buffer instanceof DirectBuffer) {
!             crc = updateByteBuffer(crc, ((DirectBuffer)buffer).address(), pos, rem);
          } else if (buffer.hasArray()) {
!             crc = updateBytes(crc, buffer.array(), pos + buffer.arrayOffset(), rem);
          } else {
              byte[] b = new byte[rem];
              buffer.get(b);
!             crc = updateBytes(crc, b, 0, b.length);
          }
          buffer.position(limit);
      }
  
      /**
--- 111,127 ----
          assert (pos <= limit);
          int rem = limit - pos;
          if (rem <= 0)
              return;
          if (buffer instanceof DirectBuffer) {
!             crc = updateByteBufferFJ(crc, ((DirectBuffer)buffer).address(), pos, rem);
          } else if (buffer.hasArray()) {
!             crc = updateBytesFJ(crc, buffer.array(), pos + buffer.arrayOffset(), rem);
          } else {
              byte[] b = new byte[rem];
              buffer.get(b);
!             crc = updateBytesFJ(crc, b, 0, b.length);
          }
          buffer.position(limit);
      }
  
      /**
*** 129,134 ****
--- 141,409 ----
      private native static int update(int crc, int b);
      private native static int updateBytes(int crc, byte[] b, int off, int len);
  
      private native static int updateByteBuffer(int adler, long addr,
                                                 int off, int len);
+ 
+ 
+     private static int updateBytesSimple(int crc, byte[] b, int off, int len) {
+         int[] a = timesXtoThe32;
+         if (a.length < 256)
+             throw new ArrayIndexOutOfBoundsException();
+         int c = ~crc;
+         for (int i = 0; i < len; i++ ) {
+             int x0 = b[i + off];
+             x0 = a[(x0 ^ c) & 0xFF];
+             c = x0 ^ (c >>> 8);
+         }
+         return ~c;
+     }
+ 
+     private native static boolean init(int[] timesXtoThe32, boolean try_use_clmul);
+ 
+     /**
+      * timesXtoThe32[a] = rep(poly(a)*x**32)
+      */
+     static int[] timesXtoThe32;
+ 
+     /**
+      * powersByLog[i] = rep(x**(2**i))
+      */
+     static final int[] powersByLog = new int[32];
+ 
+     static final int LOG_PB8_LEN = 8;
+ 
+     /**
+      * powersBy8[i] = rep(x**(8*i))
+      */
+     static final int[] powersBy8 = new int[1 << LOG_PB8_LEN];
+ 
+     static final int X_to_the_1 = 0x40000000;
+     static final int X_to_the_0 = 0x80000000;
+ 
+     /**
+      * Indicates if the clmul instruction is enabled in the native
+      * code; this changes the estimated cost of computing a CRC.
+      */
+     private static boolean clmulEnabled;
+ 
+     /**
+      * Helpful for deciding whether to use workstealing or not.
+      */
+     private static int fjParallelism = ForkJoinPool.getCommonPoolParallelism();
+ 
+     /**
+      * Estimated task size below which the fork-join overhead could be too large.
+      * May be modified depending on platform properties.
+      */
+     static int serialIfSmallerThan = 512 * 1024;
+ 
+     /**
+      * Estimated CRC size below which the JNI overhead is too large.
+      * May be modified depending on platform properties.
+      */
+     static int javaCRCIfSmallerThan = 80;
+ 
+     static int ARRAY_BYTE_BASE_OFFSET = 0;
+ 
+     static boolean debug = false;
+ 
+     static {
+       timesXtoThe32 = new int[256];
+       boolean try_use_clmul =
+            "true".equals(sun.misc.VM.getSavedProperty("sun.zip.clmulSupported"));
+       clmulEnabled = init(timesXtoThe32, try_use_clmul);
+ 
+       if (clmulEnabled)
+           serialIfSmallerThan *= 2;
+ 
+       if ("true".equals(sun.misc.VM.getSavedProperty("sun.zip.serialOnly")))
+           fjParallelism = 1;
+ 
+       powersByLog[0] = X_to_the_1;
+       for (int i = 1; i < powersByLog.length; i++) {
+           int x = powersByLog[i-1];
+           powersByLog[i] = mul(x,x);
+       }
+ 
+       powersBy8[0] = X_to_the_0;
+       for (int i = 1; i < powersBy8.length; i++) {
+           int x = powersBy8[i-1];
+           powersBy8[i] = mul(x,powersByLog[3]);
+       }
+ 
+       /* Attempt to do all fork-join splits so that they land on a 16-byte boundary.
+          Even if arrays are only 8-byte aligned, this improves our chances. */
+       try {
+           Field field = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
+           field.setAccessible(true);
+           Unsafe u = (Unsafe) field.get(null);
+           ARRAY_BYTE_BASE_OFFSET = u.ARRAY_BYTE_BASE_OFFSET;
+       } catch (NoSuchFieldException | SecurityException |
+               IllegalArgumentException | IllegalAccessException e) {
+           // It was just an optimization, no need to fail hard.
+       }
+     }
+ 
+     /* Java implementation of enough GF arithmetic to combine two CRCs for fork/join. */
+ 
+     /**
+      * Performs a carryless 32x32 into 63 (NOT 64) bit multiply.
+      * Note that the low-order term of the polynomial lands in bit
+      * 62, not 63.
+      *
+      * The Intel pclmulqdq instruction works in much the same way,
+      * except that it is 64 x 64 into 128.
+      */
+     private static long clmul32x32(int a, int b) {
+         long accum = 0;
+         long la = (long) a & 0xffffffffL;
+         long lb = (long) b & 0xffffffffL;
+         while (la != 0) {
+             if (0 != (la & 1))
+                 accum ^= lb;
+             la = la >>> 1;
+         lb = lb << 1;
+         }
+         return accum;
+     }
+ 
+     /**
+      * Converts a 64-bit polynomial into a 32-bit polynomial, modulo P.
+      */
+     static int reduceLongTable(long x) {
+         x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
+         x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
+         x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
+         x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
+         return (int) x;
+     }
+ 
+    /**
+      * Returns polynomial a times b modulo P.
+      * The least (x**0) term of the polynomial is
+      * aligned with the sign bit of the returned int.
+      *
+      * @param a
+      * @param b
+      * @return
+      */
+     static int mul(int a, int b) {
+         long product = clmul32x32(a, b);
+         return reduceLongTable(product << 1);
+     }
+ 
+     /**
+      * Returns the polynomial for a * x ** 8n, where a
+      * is some other polynomial.  n is typically a byte count,
+      * and 8n is the number of bits in n bytes.
+      */
+     static int timesXtoThe8NTable(int a, int n) {
+         if (n == 0)
+             return a;
+         if (n < powersBy8.length) {
+             return mul(a,powersBy8[n]);
+         }
+         int lo = powersBy8.length - 1;
+         int accum = mul(a,powersBy8[n & lo]);
+         n = n >>> LOG_PB8_LEN;
+         int i = LOG_PB8_LEN + 3;
+         while (n != 0) {
+             if (0 != (n & 1))
+                 accum = mul(accum,powersByLog[i]);
+             n = n >>> 1;
+             i++;
+         }
+         return accum;
+     }
+ 
+     static int combine(int prev, int next, int next_length) {
+         // x**(8 * length) * prev + next
+         return next ^ timesXtoThe8NTable(prev, next_length);
+     }
+ 
+     private static int updateBytesFJ(int crc, byte[] b, int off, int len) {
+         if (fjParallelism < 2 || len < serialIfSmallerThan)
+             return updateBytes(crc, b, off, len);
+         CRCArrayTask cat = new CRCArrayTask(crc, b, off, len);
+         cat.invoke();
+         return cat.join();
+     }
+ 
+     private static int updateByteBufferFJ(int crc, long addr,
+                                                int off, int len) {
+         if (fjParallelism < 2 || len < serialIfSmallerThan)
+             return updateByteBuffer(crc, addr, off, len);
+         CRCBufferTask cat = new CRCBufferTask(crc, addr, off, len);
+         cat.invoke();
+         return cat.join();
+     }
+ 
+     static final class CRCArrayTask extends RecursiveTask<Integer> {
+         final byte[] ba;
+         final int start;
+         final int length;
+         final int crc;
+ 
+         CRCArrayTask(int crc, byte[] ba, int start, int length) {
+             this.crc = crc;
+             this.ba = ba;
+             this.start = start;
+             this.length = length;
+         }
+ 
+         @Override
+         protected Integer compute() {
+             if (length < serialIfSmallerThan) {
+                 if (length < javaCRCIfSmallerThan) {
+                     return updateBytesSimple(crc, ba, start, length);
+                 } else {
+                     return updateBytes(crc, ba, start, length);
+                 }
+             } else {
+                 int half = length/2;
+                 /* Avoid gratuitous misalignment. */
+                 long addr = ARRAY_BYTE_BASE_OFFSET; // Best we can do given limited info.
+                 int unaligned = (int) (addr + start + half) & 15;
+                 if (half - unaligned >= 32)
+                     half -= unaligned;
+                 CRCArrayTask task2 = new CRCArrayTask(0, ba, start + half, length - half);
+                 task2.fork();
+                 CRCArrayTask task1 = new CRCArrayTask(crc, ba, start, half);
+                 int result1 = task1.compute();
+                 return combine(result1, task2.join(), length - half);
+             }
+         }
+     }
+ 
+     static final class CRCBufferTask extends RecursiveTask<Integer> {
+         final long addr;
+         final int start;
+         final int length;
+         final int crc;
+ 
+         CRCBufferTask(int crc, long addr, int start, int length) {
+             this.crc = crc;
+             this.addr = addr;
+             this.start = start;
+             this.length = length;
+         }
+ 
+         @Override
+         protected Integer compute() {
+             if (length < serialIfSmallerThan) {
+                 return updateByteBuffer(crc, addr, start, length);
+             } else {
+                 int half = length/2;
+                 /* Avoid gratuitous misalignment. */
+                 int unaligned = (int) (addr + start + half) & 15;
+                 if (half - unaligned >= 32)
+                     half -= unaligned;
+                 CRCBufferTask task2 = new CRCBufferTask(0, addr, start + half, length - half);
+                 task2.fork();
+                 CRCBufferTask task1 = new CRCBufferTask(crc, addr, start, half);
+                 int result1 = task1.compute();
+                 return combine(result1, task2.join(), length - half);
+             }
+         }
+     }
  }