src/share/classes/java/util/zip/Adler32.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File
jdk Cdiff src/share/classes/java/util/zip/Adler32.java
src/share/classes/java/util/zip/Adler32.java
Print this page
*** 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
*** 25,34 ****
--- 25,35 ----
package java.util.zip;
import java.nio.ByteBuffer;
import sun.nio.ch.DirectBuffer;
+ import java.util.concurrent.RecursiveTask;
/**
* A class that can be used to compute the Adler-32 checksum of a data
* stream. An Adler-32 checksum is almost as reliable as a CRC-32 but
* can be computed much faster.
*** 39,50 ****
--- 40,89 ----
* @see Checksum
* @author David Connelly
*/
public
class Adler32 implements Checksum {
+ /*
+ * This is a reformulation of the Adler32 calculation that permits recursive
+ * subdivision of the problem, thus allowing both parallelism and faster calculation
+ * byte-at-a-time checksums.
+ *
+ * The Adler calculation is regarded as
+ * taking an input text T of length N = |T|,
+ * and computing two quantities, A(T) and B(T),
+ * where A(T) = 1 + sum_{0 <= i < |T|}(T_i)
+ * and B(T) = |T| + sum_{0 <= i < |T|}((|T| - i) * T_i),
+ * both modulo 65521.
+ *
+ * However, with sufficient algebraic manipulation, one can derive
+ * that A(U||V) = A(U) + A(V) - 1
+ * and B(U||V) = B(U) + B(V) + |V| (A(U) - 1).
+ */
+
+ /**
+ * The modulo operation can be deferred for MAX_SLOP bytes of input, permitting
+ * faster byte-by-byte Adler computations. 1024 is plenty conservative.
+ */
+ private final static int MAX_SLOP = 1024;
+
+ /**
+ * For inputs smaller than SERIAL_BELOW fork-join parallelism might
+ * not be profitable.
+ */
+ private final static int SERIAL_BELOW = 1024 * 1024;
+
+ /**
+ * For inputs smaller than JAVA_ADLER_BELOW JNI overheads make it faster
+ * to compute on the Java side. (This may change as overheads and compiler
+ * quality change).
+ */
+ private final static int JAVA_ADLER_BELOW = 32;
private int adler = 1;
+ private int aa = 1;
+ private int bb = 0;
+ private int slop = 0;
/**
* Creates a new Adler32 object.
*/
public Adler32() {
*** 55,65 ****
* bits of the argument b).
*
* @param b the byte to update the checksum with
*/
public void update(int b) {
! adler = update(adler, b);
}
/**
* Updates the checksum with the specified array of bytes.
*/
--- 94,110 ----
* bits of the argument b).
*
* @param b the byte to update the checksum with
*/
public void update(int b) {
! int la = aa + (b & 0xFF);
! bb = bb + la;
! aa = la;
! slop++;
! if (slop == MAX_SLOP) {
! getValueI();
! }
}
/**
* Updates the checksum with the specified array of bytes.
*/
*** 68,89 ****
throw new NullPointerException();
}
if (off < 0 || len < 0 || off > b.length - len) {
throw new ArrayIndexOutOfBoundsException();
}
! adler = updateBytes(adler, b, off, len);
}
/**
* Updates the checksum with the specified array of bytes.
*
* @param b the byte array to update the checksum with
*/
public void update(byte[] b) {
! adler = updateBytes(adler, b, 0, b.length);
}
-
/**
* Updates the checksum with the bytes from the specified buffer.
*
* The checksum is updated using
--- 113,143 ----
throw new NullPointerException();
}
if (off < 0 || len < 0 || off > b.length - len) {
throw new ArrayIndexOutOfBoundsException();
}
! if (len < JAVA_ADLER_BELOW) {
! for (int i = 0; i < len; i++)
! update(b[i+off]);
! } else {
! setValue(updateBytesFJ(getValueI(), b, off, len));
! }
}
/**
* Updates the checksum with the specified array of bytes.
*
* @param b the byte array to update the checksum with
*/
public void update(byte[] b) {
! if (b.length < JAVA_ADLER_BELOW) {
! for (int i = 0; i < b.length; i++)
! update(b[i]);
! } else {
! setValue(updateBytesFJ(getValueI(), b, 0, b.length));
! }
}
/**
* Updates the checksum with the bytes from the specified buffer.
*
* The checksum is updated using
*** 102,137 ****
assert (pos <= limit);
int rem = limit - pos;
if (rem <= 0)
return;
if (buffer instanceof DirectBuffer) {
! adler = updateByteBuffer(adler, ((DirectBuffer)buffer).address(), pos, rem);
} else if (buffer.hasArray()) {
! adler = updateBytes(adler, buffer.array(), pos + buffer.arrayOffset(), rem);
} else {
byte[] b = new byte[rem];
buffer.get(b);
! adler = updateBytes(adler, b, 0, b.length);
}
buffer.position(limit);
}
/**
* Resets the checksum to initial value.
*/
public void reset() {
adler = 1;
}
/**
* Returns the checksum value.
*/
public long getValue() {
! return (long)adler & 0xffffffffL;
}
private native static int update(int adler, int b);
private native static int updateBytes(int adler, byte[] b, int off,
int len);
private native static int updateByteBuffer(int adler, long addr,
int off, int len);
}
--- 156,305 ----
assert (pos <= limit);
int rem = limit - pos;
if (rem <= 0)
return;
if (buffer instanceof DirectBuffer) {
! setValue(updateByteBufferFJ(getValueI(), ((DirectBuffer)buffer).address(), pos, rem));
} else if (buffer.hasArray()) {
! setValue(updateBytesFJ(getValueI(), buffer.array(), pos + buffer.arrayOffset(), rem));
} else {
byte[] b = new byte[rem];
buffer.get(b);
! setValue(updateBytesFJ(getValueI(), b, 0, b.length));
}
buffer.position(limit);
}
/**
* Resets the checksum to initial value.
*/
public void reset() {
+ aa = 1;
+ bb = 0;
adler = 1;
+ slop = 0;
}
/**
* Returns the checksum value.
*/
public long getValue() {
! return getValueI() & 0xffffffffL;
! }
!
! private int getValueI() {
! if (slop > 0) {
! aa = aa % 65521;
! bb = bb % 65521;
! adler = (bb << 16) + aa;
! slop = 0;
! }
! return adler;
! }
!
! private void setValue(int newValue) {
! aa = newValue & 0xffff;
! bb = newValue >>> 16;
! adler = newValue;
! slop = 0;
}
private native static int update(int adler, int b);
private native static int updateBytes(int adler, byte[] b, int off,
int len);
+
private native static int updateByteBuffer(int adler, long addr,
int off, int len);
+
+ private static int updateBytesFJ(int adler, byte[] ba, int start, int length) {
+ if (length < SERIAL_BELOW) {
+ return updateBytes(adler, ba, start, length);
+ }
+ AdlerTask w = new AdlerTask(adler, ba, start, length);
+ w.invoke();
+ return(w.join());
+ }
+
+ private static int updateByteBufferFJ(int adler, long addr, int start, int length) {
+ if (length < SERIAL_BELOW) {
+ return updateByteBuffer(adler, addr, start, length);
+ }
+ AdlerBufferTask w = new AdlerBufferTask(adler, addr, start, length);
+ w.invoke();
+ return(w.join());
+ }
+
+ static int combineAdlers(int prev_adler, int next_adler, int length) {
+ /* that A(U||V) = A(U) + A(V) - 1
+ * and B(U||V) = B(U) + B(V) + |V| (A(U) - 1).
+ */
+ if (prev_adler == 1) {
+ // Appending to initial checksum
+ return next_adler;
+ } else {
+ int after_a = next_adler & 0xffff;
+ int after_b = next_adler >>> 16;
+
+ int prev_a = prev_adler & 0xffff;
+ int prev_b = prev_adler >>> 16;
+
+ long partial = (long) length * (prev_a + 65520) % 65521;
+ prev_b = (prev_b + after_b + (int) partial) % 65521;
+ prev_a = (prev_a + after_a + 65520) % 65521;
+ return ((prev_b << 16) + prev_a);
+ }
+ }
+
+ static class AdlerTask extends RecursiveTask<Integer> {
+ final int adler;
+ final byte[] ba;
+ final int start;
+ final int length;
+ AdlerTask(int adler, byte[] ba, int start, int length) {
+ this.ba = ba;
+ this.start = start;
+ this.length = length;
+ this.adler = adler;
+ }
+
+ @Override
+ protected Integer compute() {
+ if (length < SERIAL_BELOW) {
+ return updateBytes(adler, ba, start, length);
+ } else {
+ int half = length/2;
+ AdlerTask task2 = new AdlerTask(1, ba, start + half, length - half);
+ task2.fork();
+ AdlerTask task1 = new AdlerTask(adler, ba, start, half);
+ int result1 = task1.compute();
+ return combineAdlers(result1, task2.join(), length - half);
+ }
+ }
+ }
+
+ static class AdlerBufferTask extends RecursiveTask<Integer> {
+ final int adler;
+ final long addr;
+ final int start;
+ final int length;
+ AdlerBufferTask(int adler, long addr, int start, int length) {
+ this.addr = addr;
+ this.start = start;
+ this.length = length;
+ this.adler = adler;
+ }
+
+ @Override
+ protected Integer compute() {
+ if (length < SERIAL_BELOW) {
+ return updateByteBuffer(adler, addr, start, length);
+ } else {
+ int half = length/2;
+ AdlerBufferTask task2 = new AdlerBufferTask(1, addr, start + half, length - half);
+ task2.fork();
+ AdlerBufferTask task1 = new AdlerBufferTask(adler, addr, start, half);
+ int result1 = task1.compute();
+ return combineAdlers(result1, task2.join(), length - half);
+ }
+ }
+ }
}
src/share/classes/java/util/zip/Adler32.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File