1 /* 2 * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util.zip; 27 28 import java.nio.ByteBuffer; 29 import sun.nio.ch.DirectBuffer; 30 31 /** 32 * A class that can be used to compute the Adler-32 checksum of a data 33 * stream. An Adler-32 checksum is almost as reliable as a CRC-32 but 34 * can be computed much faster. 35 * 36 * <p> Passing a {@code null} argument to a method in this class will cause 37 * a {@link NullPointerException} to be thrown. 38 * 39 * @see Checksum 40 * @author David Connelly 41 */ 42 public 43 class Adler32 implements Checksum { 44 45 private int adler = 1; 46 47 /** 48 * Creates a new Adler32 object. 49 */ 50 public Adler32() { 51 } 52 53 /** 54 * Updates the checksum with the specified byte (the low eight 55 * bits of the argument b). 56 * 57 * @param b the byte to update the checksum with 58 */ 59 public void update(int b) { 60 adler = update(adler, b); 61 } 62 63 /** 64 * Updates the checksum with the specified array of bytes. 65 */ 66 public void update(byte[] b, int off, int len) { 67 if (b == null) { 68 throw new NullPointerException(); 69 } 70 if (off < 0 || len < 0 || off > b.length - len) { 71 throw new ArrayIndexOutOfBoundsException(); 72 } 73 adler = updateBytes(adler, b, off, len); 74 } 75 76 /** 77 * Updates the checksum with the specified array of bytes. 78 * 79 * @param b the byte array to update the checksum with 80 */ 81 public void update(byte[] b) { 82 adler = updateBytes(adler, b, 0, b.length); 83 } 84 85 86 /** 87 * Updates the checksum with the bytes from the specified buffer. 88 * 89 * The checksum is updated using 90 * buffer.{@link java.nio.Buffer#remaining() remaining()} 91 * bytes starting at 92 * buffer.{@link java.nio.Buffer#position() position()} 93 * Upon return, the buffer's position will be updated to its 94 * limit; its limit will not have been changed. 95 * 96 * @param buffer the ByteBuffer to update the checksum with 97 * @since 1.8 98 */ 99 public void update(ByteBuffer buffer) { 100 int pos = buffer.position(); 101 int limit = buffer.limit(); 102 assert (pos <= limit); 103 int rem = limit - pos; 104 if (rem <= 0) 105 return; 106 if (buffer instanceof DirectBuffer) { 107 adler = updateByteBuffer(adler, ((DirectBuffer)buffer).address(), pos, rem); 108 } else if (buffer.hasArray()) { 109 adler = updateBytes(adler, buffer.array(), pos + buffer.arrayOffset(), rem); 110 } else { 111 byte[] b = new byte[rem]; 112 buffer.get(b); 113 adler = updateBytes(adler, b, 0, b.length); 114 } 115 buffer.position(limit); 116 } 117 118 /** 119 * Resets the checksum to initial value. 120 */ 121 public void reset() { 122 adler = 1; 123 } 124 125 /** 126 * Returns the checksum value. 127 */ 128 public long getValue() { 129 return (long)adler & 0xffffffffL; 130 } 131 132 private native static int update(int adler, int b); 133 private native static int updateBytes(int adler, byte[] b, int off, 134 int len); 135 private native static int updateByteBuffer(int adler, long addr, 136 int off, int len); 137 } | 1 /* 2 * Copyright (c) 1996, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util.zip; 27 28 import java.nio.ByteBuffer; 29 import sun.nio.ch.DirectBuffer; 30 import java.util.concurrent.RecursiveTask; 31 32 /** 33 * A class that can be used to compute the Adler-32 checksum of a data 34 * stream. An Adler-32 checksum is almost as reliable as a CRC-32 but 35 * can be computed much faster. 36 * 37 * <p> Passing a {@code null} argument to a method in this class will cause 38 * a {@link NullPointerException} to be thrown. 39 * 40 * @see Checksum 41 * @author David Connelly 42 */ 43 public 44 class Adler32 implements Checksum { 45 /* 46 * This is a reformulation of the Adler32 calculation that permits recursive 47 * subdivision of the problem, thus allowing both parallelism and faster calculation 48 * byte-at-a-time checksums. 49 * 50 * The Adler calculation is regarded as 51 * taking an input text T of length N = |T|, 52 * and computing two quantities, A(T) and B(T), 53 * where A(T) = 1 + sum_{0 <= i < |T|}(T_i) 54 * and B(T) = |T| + sum_{0 <= i < |T|}((|T| - i) * T_i), 55 * both modulo 65521. 56 * 57 * However, with sufficient algebraic manipulation, one can derive 58 * that A(U||V) = A(U) + A(V) - 1 59 * and B(U||V) = B(U) + B(V) + |V| (A(U) - 1). 60 */ 61 62 /** 63 * The modulo operation can be deferred for MAX_SLOP bytes of input, permitting 64 * faster byte-by-byte Adler computations. 1024 is plenty conservative. 65 */ 66 private final static int MAX_SLOP = 1024; 67 68 /** 69 * For inputs smaller than SERIAL_BELOW fork-join parallelism might 70 * not be profitable. 71 */ 72 private final static int SERIAL_BELOW = 1024 * 1024; 73 74 /** 75 * For inputs smaller than JAVA_ADLER_BELOW JNI overheads make it faster 76 * to compute on the Java side. (This may change as overheads and compiler 77 * quality change). 78 */ 79 private final static int JAVA_ADLER_BELOW = 32; 80 81 private int adler = 1; 82 private int aa = 1; 83 private int bb = 0; 84 private int slop = 0; 85 86 /** 87 * Creates a new Adler32 object. 88 */ 89 public Adler32() { 90 } 91 92 /** 93 * Updates the checksum with the specified byte (the low eight 94 * bits of the argument b). 95 * 96 * @param b the byte to update the checksum with 97 */ 98 public void update(int b) { 99 int la = aa + (b & 0xFF); 100 bb = bb + la; 101 aa = la; 102 slop++; 103 if (slop == MAX_SLOP) { 104 getValueI(); 105 } 106 } 107 108 /** 109 * Updates the checksum with the specified array of bytes. 110 */ 111 public void update(byte[] b, int off, int len) { 112 if (b == null) { 113 throw new NullPointerException(); 114 } 115 if (off < 0 || len < 0 || off > b.length - len) { 116 throw new ArrayIndexOutOfBoundsException(); 117 } 118 if (len < JAVA_ADLER_BELOW) { 119 for (int i = 0; i < len; i++) 120 update(b[i+off]); 121 } else { 122 setValue(updateBytesFJ(getValueI(), b, off, len)); 123 } 124 } 125 126 /** 127 * Updates the checksum with the specified array of bytes. 128 * 129 * @param b the byte array to update the checksum with 130 */ 131 public void update(byte[] b) { 132 if (b.length < JAVA_ADLER_BELOW) { 133 for (int i = 0; i < b.length; i++) 134 update(b[i]); 135 } else { 136 setValue(updateBytesFJ(getValueI(), b, 0, b.length)); 137 } 138 } 139 140 /** 141 * Updates the checksum with the bytes from the specified buffer. 142 * 143 * The checksum is updated using 144 * buffer.{@link java.nio.Buffer#remaining() remaining()} 145 * bytes starting at 146 * buffer.{@link java.nio.Buffer#position() position()} 147 * Upon return, the buffer's position will be updated to its 148 * limit; its limit will not have been changed. 149 * 150 * @param buffer the ByteBuffer to update the checksum with 151 * @since 1.8 152 */ 153 public void update(ByteBuffer buffer) { 154 int pos = buffer.position(); 155 int limit = buffer.limit(); 156 assert (pos <= limit); 157 int rem = limit - pos; 158 if (rem <= 0) 159 return; 160 if (buffer instanceof DirectBuffer) { 161 setValue(updateByteBufferFJ(getValueI(), ((DirectBuffer)buffer).address(), pos, rem)); 162 } else if (buffer.hasArray()) { 163 setValue(updateBytesFJ(getValueI(), buffer.array(), pos + buffer.arrayOffset(), rem)); 164 } else { 165 byte[] b = new byte[rem]; 166 buffer.get(b); 167 setValue(updateBytesFJ(getValueI(), b, 0, b.length)); 168 } 169 buffer.position(limit); 170 } 171 172 /** 173 * Resets the checksum to initial value. 174 */ 175 public void reset() { 176 aa = 1; 177 bb = 0; 178 adler = 1; 179 slop = 0; 180 } 181 182 /** 183 * Returns the checksum value. 184 */ 185 public long getValue() { 186 return getValueI() & 0xffffffffL; 187 } 188 189 private int getValueI() { 190 if (slop > 0) { 191 aa = aa % 65521; 192 bb = bb % 65521; 193 adler = (bb << 16) + aa; 194 slop = 0; 195 } 196 return adler; 197 } 198 199 private void setValue(int newValue) { 200 aa = newValue & 0xffff; 201 bb = newValue >>> 16; 202 adler = newValue; 203 slop = 0; 204 } 205 206 private native static int update(int adler, int b); 207 private native static int updateBytes(int adler, byte[] b, int off, 208 int len); 209 210 private native static int updateByteBuffer(int adler, long addr, 211 int off, int len); 212 213 private static int updateBytesFJ(int adler, byte[] ba, int start, int length) { 214 if (length < SERIAL_BELOW) { 215 return updateBytes(adler, ba, start, length); 216 } 217 AdlerTask w = new AdlerTask(adler, ba, start, length); 218 w.invoke(); 219 return(w.join()); 220 } 221 222 private static int updateByteBufferFJ(int adler, long addr, int start, int length) { 223 if (length < SERIAL_BELOW) { 224 return updateByteBuffer(adler, addr, start, length); 225 } 226 AdlerBufferTask w = new AdlerBufferTask(adler, addr, start, length); 227 w.invoke(); 228 return(w.join()); 229 } 230 231 static int combineAdlers(int prev_adler, int next_adler, int length) { 232 /* that A(U||V) = A(U) + A(V) - 1 233 * and B(U||V) = B(U) + B(V) + |V| (A(U) - 1). 234 */ 235 if (prev_adler == 1) { 236 // Appending to initial checksum 237 return next_adler; 238 } else { 239 int after_a = next_adler & 0xffff; 240 int after_b = next_adler >>> 16; 241 242 int prev_a = prev_adler & 0xffff; 243 int prev_b = prev_adler >>> 16; 244 245 long partial = (long) length * (prev_a + 65520) % 65521; 246 prev_b = (prev_b + after_b + (int) partial) % 65521; 247 prev_a = (prev_a + after_a + 65520) % 65521; 248 return ((prev_b << 16) + prev_a); 249 } 250 } 251 252 static class AdlerTask extends RecursiveTask<Integer> { 253 final int adler; 254 final byte[] ba; 255 final int start; 256 final int length; 257 AdlerTask(int adler, byte[] ba, int start, int length) { 258 this.ba = ba; 259 this.start = start; 260 this.length = length; 261 this.adler = adler; 262 } 263 264 @Override 265 protected Integer compute() { 266 if (length < SERIAL_BELOW) { 267 return updateBytes(adler, ba, start, length); 268 } else { 269 int half = length/2; 270 AdlerTask task2 = new AdlerTask(1, ba, start + half, length - half); 271 task2.fork(); 272 AdlerTask task1 = new AdlerTask(adler, ba, start, half); 273 int result1 = task1.compute(); 274 return combineAdlers(result1, task2.join(), length - half); 275 } 276 } 277 } 278 279 static class AdlerBufferTask extends RecursiveTask<Integer> { 280 final int adler; 281 final long addr; 282 final int start; 283 final int length; 284 AdlerBufferTask(int adler, long addr, int start, int length) { 285 this.addr = addr; 286 this.start = start; 287 this.length = length; 288 this.adler = adler; 289 } 290 291 @Override 292 protected Integer compute() { 293 if (length < SERIAL_BELOW) { 294 return updateByteBuffer(adler, addr, start, length); 295 } else { 296 int half = length/2; 297 AdlerBufferTask task2 = new AdlerBufferTask(1, addr, start + half, length - half); 298 task2.fork(); 299 AdlerBufferTask task1 = new AdlerBufferTask(adler, addr, start, half); 300 int result1 = task1.compute(); 301 return combineAdlers(result1, task2.join(), length - half); 302 } 303 } 304 } 305 } |