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