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 sun.nio.ch.DirectBuffer;
29 import java.lang.reflect.Field;
30 import java.nio.ByteBuffer;
31 import java.util.concurrent.RecursiveTask;
32 import java.util.concurrent.ForkJoinPool;
33 import sun.misc.Unsafe;
34
35 /**
36 * A class that can be used to compute the CRC-32 of a data stream.
37 *
38 * <p> Passing a {@code null} argument to a method in this class will cause
39 * a {@link NullPointerException} to be thrown.
40 *
41 * @see Checksum
42 * @author David Connelly
43 */
44 public
45 class CRC32 implements Checksum {
46 private int crc;
47
48 /**
49 * Creates a new CRC32 object.
50 */
51 public CRC32() {
52 }
53
54
55 /**
56 * Updates the CRC-32 checksum with the specified byte (the low
57 * eight bits of the argument b).
58 *
59 * @param b the byte to update the checksum with
60 */
61 public void update(int b) {
62 int c = ~ crc;
63 b = timesXtoThe32[(b ^ c) & 0xFF];
64 b = b ^ (c >>> 8);
65 crc = ~b;
66 }
67
68 /**
69 * Updates the CRC-32 checksum with the specified array of bytes.
70 */
71 public void update(byte[] b, int off, int len) {
72 if (b == null) {
73 throw new NullPointerException();
74 }
75 if (off < 0 || len < 0 || off > b.length - len) {
76 throw new ArrayIndexOutOfBoundsException();
77 }
78
79 if (len < javaCRCIfSmallerThan) {
80 crc = updateBytesSimple(crc, b, off, len);
81 } else {
82 crc = updateBytesFJ(crc, b, off, len);
83 }
84 }
85
86 /**
87 * Updates the CRC-32 checksum with the specified array of bytes.
88 *
89 * @param b the array of bytes to update the checksum with
90 */
91 public void update(byte[] b) {
92 crc = updateBytesFJ(crc, b, 0, b.length);
93 }
94
95 /**
96 * Updates the checksum with the bytes from the specified buffer.
97 *
98 * The checksum is updated using
99 * buffer.{@link java.nio.Buffer#remaining() remaining()}
100 * bytes starting at
101 * buffer.{@link java.nio.Buffer#position() position()}
102 * Upon return, the buffer's position will
103 * be updated to its limit; its limit will not have been changed.
104 *
105 * @param buffer the ByteBuffer to update the checksum with
106 * @since 1.8
107 */
108 public void update(ByteBuffer buffer) {
109 int pos = buffer.position();
110 int limit = buffer.limit();
111 assert (pos <= limit);
112 int rem = limit - pos;
113 if (rem <= 0)
114 return;
115 if (buffer instanceof DirectBuffer) {
116 crc = updateByteBufferFJ(crc, ((DirectBuffer)buffer).address(), pos, rem);
117 } else if (buffer.hasArray()) {
118 crc = updateBytesFJ(crc, buffer.array(), pos + buffer.arrayOffset(), rem);
119 } else {
120 byte[] b = new byte[rem];
121 buffer.get(b);
122 crc = updateBytesFJ(crc, b, 0, b.length);
123 }
124 buffer.position(limit);
125 }
126
127 /**
128 * Resets CRC-32 to initial value.
129 */
130 public void reset() {
131 crc = 0;
132 }
133
134 /**
135 * Returns CRC-32 value.
136 */
137 public long getValue() {
138 return (long)crc & 0xffffffffL;
139 }
140
141 private native static int update(int crc, int b);
142 private native static int updateBytes(int crc, byte[] b, int off, int len);
143
144 private native static int updateByteBuffer(int adler, long addr,
145 int off, int len);
146
147
148 private static int updateBytesSimple(int crc, byte[] b, int off, int len) {
149 int[] a = timesXtoThe32;
150 if (a.length < 256)
151 throw new ArrayIndexOutOfBoundsException();
152 int c = ~crc;
153 for (int i = 0; i < len; i++ ) {
154 int x0 = b[i + off];
155 x0 = a[(x0 ^ c) & 0xFF];
156 c = x0 ^ (c >>> 8);
157 }
158 return ~c;
159 }
160
161 private native static boolean init(int[] timesXtoThe32, boolean try_use_clmul);
162
163 /**
164 * timesXtoThe32[a] = rep(poly(a)*x**32)
165 */
166 static int[] timesXtoThe32;
167
168 /**
169 * powersByLog[i] = rep(x**(2**i))
170 */
171 static final int[] powersByLog = new int[32];
172
173 static final int LOG_PB8_LEN = 8;
174
175 /**
176 * powersBy8[i] = rep(x**(8*i))
177 */
178 static final int[] powersBy8 = new int[1 << LOG_PB8_LEN];
179
180 static final int X_to_the_1 = 0x40000000;
181 static final int X_to_the_0 = 0x80000000;
182
183 /**
184 * Indicates if the clmul instruction is enabled in the native
185 * code; this changes the estimated cost of computing a CRC.
186 */
187 private static boolean clmulEnabled;
188
189 /**
190 * Helpful for deciding whether to use workstealing or not.
191 */
192 private static int fjParallelism = ForkJoinPool.getCommonPoolParallelism();
193
194 /**
195 * Estimated task size below which the fork-join overhead could be too large.
196 * May be modified depending on platform properties.
197 */
198 static int serialIfSmallerThan = 512 * 1024;
199
200 /**
201 * Estimated CRC size below which the JNI overhead is too large.
202 * May be modified depending on platform properties.
203 */
204 static int javaCRCIfSmallerThan = 80;
205
206 static int ARRAY_BYTE_BASE_OFFSET = 0;
207
208 static boolean debug = false;
209
210 static {
211 timesXtoThe32 = new int[256];
212 boolean try_use_clmul =
213 "true".equals(sun.misc.VM.getSavedProperty("sun.zip.clmulSupported"));
214 clmulEnabled = init(timesXtoThe32, try_use_clmul);
215
216 if (clmulEnabled)
217 serialIfSmallerThan *= 2;
218
219 if ("true".equals(sun.misc.VM.getSavedProperty("sun.zip.serialOnly")))
220 fjParallelism = 1;
221
222 powersByLog[0] = X_to_the_1;
223 for (int i = 1; i < powersByLog.length; i++) {
224 int x = powersByLog[i-1];
225 powersByLog[i] = mul(x,x);
226 }
227
228 powersBy8[0] = X_to_the_0;
229 for (int i = 1; i < powersBy8.length; i++) {
230 int x = powersBy8[i-1];
231 powersBy8[i] = mul(x,powersByLog[3]);
232 }
233
234 /* Attempt to do all fork-join splits so that they land on a 16-byte boundary.
235 Even if arrays are only 8-byte aligned, this improves our chances. */
236 try {
237 Field field = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
238 field.setAccessible(true);
239 Unsafe u = (Unsafe) field.get(null);
240 ARRAY_BYTE_BASE_OFFSET = u.ARRAY_BYTE_BASE_OFFSET;
241 } catch (NoSuchFieldException | SecurityException |
242 IllegalArgumentException | IllegalAccessException e) {
243 // It was just an optimization, no need to fail hard.
244 }
245 }
246
247 /* Java implementation of enough GF arithmetic to combine two CRCs for fork/join. */
248
249 /**
250 * Performs a carryless 32x32 into 63 (NOT 64) bit multiply.
251 * Note that the low-order term of the polynomial lands in bit
252 * 62, not 63.
253 *
254 * The Intel pclmulqdq instruction works in much the same way,
255 * except that it is 64 x 64 into 128.
256 */
257 private static long clmul32x32(int a, int b) {
258 long accum = 0;
259 long la = (long) a & 0xffffffffL;
260 long lb = (long) b & 0xffffffffL;
261 while (la != 0) {
262 if (0 != (la & 1))
263 accum ^= lb;
264 la = la >>> 1;
265 lb = lb << 1;
266 }
267 return accum;
268 }
269
270 /**
271 * Converts a 64-bit polynomial into a 32-bit polynomial, modulo P.
272 */
273 static int reduceLongTable(long x) {
274 x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
275 x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
276 x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
277 x = (x >>> 8) ^ (timesXtoThe32[(int)(x & 0xFF)] & 0xffffffffL);
278 return (int) x;
279 }
280
281 /**
282 * Returns polynomial a times b modulo P.
283 * The least (x**0) term of the polynomial is
284 * aligned with the sign bit of the returned int.
285 *
286 * @param a
287 * @param b
288 * @return
289 */
290 static int mul(int a, int b) {
291 long product = clmul32x32(a, b);
292 return reduceLongTable(product << 1);
293 }
294
295 /**
296 * Returns the polynomial for a * x ** 8n, where a
297 * is some other polynomial. n is typically a byte count,
298 * and 8n is the number of bits in n bytes.
299 */
300 static int timesXtoThe8NTable(int a, int n) {
301 if (n == 0)
302 return a;
303 if (n < powersBy8.length) {
304 return mul(a,powersBy8[n]);
305 }
306 int lo = powersBy8.length - 1;
307 int accum = mul(a,powersBy8[n & lo]);
308 n = n >>> LOG_PB8_LEN;
309 int i = LOG_PB8_LEN + 3;
310 while (n != 0) {
311 if (0 != (n & 1))
312 accum = mul(accum,powersByLog[i]);
313 n = n >>> 1;
314 i++;
315 }
316 return accum;
317 }
318
319 static int combine(int prev, int next, int next_length) {
320 // x**(8 * length) * prev + next
321 return next ^ timesXtoThe8NTable(prev, next_length);
322 }
323
324 private static int updateBytesFJ(int crc, byte[] b, int off, int len) {
325 if (fjParallelism < 2 || len < serialIfSmallerThan)
326 return updateBytes(crc, b, off, len);
327 CRCArrayTask cat = new CRCArrayTask(crc, b, off, len);
328 cat.invoke();
329 return cat.join();
330 }
331
332 private static int updateByteBufferFJ(int crc, long addr,
333 int off, int len) {
334 if (fjParallelism < 2 || len < serialIfSmallerThan)
335 return updateByteBuffer(crc, addr, off, len);
336 CRCBufferTask cat = new CRCBufferTask(crc, addr, off, len);
337 cat.invoke();
338 return cat.join();
339 }
340
341 static final class CRCArrayTask extends RecursiveTask<Integer> {
342 final byte[] ba;
343 final int start;
344 final int length;
345 final int crc;
346
347 CRCArrayTask(int crc, byte[] ba, int start, int length) {
348 this.crc = crc;
349 this.ba = ba;
350 this.start = start;
351 this.length = length;
352 }
353
354 @Override
355 protected Integer compute() {
356 if (length < serialIfSmallerThan) {
357 if (length < javaCRCIfSmallerThan) {
358 return updateBytesSimple(crc, ba, start, length);
359 } else {
360 return updateBytes(crc, ba, start, length);
361 }
362 } else {
363 int half = length/2;
364 /* Avoid gratuitous misalignment. */
365 long addr = ARRAY_BYTE_BASE_OFFSET; // Best we can do given limited info.
366 int unaligned = (int) (addr + start + half) & 15;
367 if (half - unaligned >= 32)
368 half -= unaligned;
369 CRCArrayTask task2 = new CRCArrayTask(0, ba, start + half, length - half);
370 task2.fork();
371 CRCArrayTask task1 = new CRCArrayTask(crc, ba, start, half);
372 int result1 = task1.compute();
373 return combine(result1, task2.join(), length - half);
374 }
375 }
376 }
377
378 static final class CRCBufferTask extends RecursiveTask<Integer> {
379 final long addr;
380 final int start;
381 final int length;
382 final int crc;
383
384 CRCBufferTask(int crc, long addr, int start, int length) {
385 this.crc = crc;
386 this.addr = addr;
387 this.start = start;
388 this.length = length;
389 }
390
391 @Override
392 protected Integer compute() {
393 if (length < serialIfSmallerThan) {
394 return updateByteBuffer(crc, addr, start, length);
395 } else {
396 int half = length/2;
397 /* Avoid gratuitous misalignment. */
398 int unaligned = (int) (addr + start + half) & 15;
399 if (half - unaligned >= 32)
400 half -= unaligned;
401 CRCBufferTask task2 = new CRCBufferTask(0, addr, start + half, length - half);
402 task2.fork();
403 CRCBufferTask task1 = new CRCBufferTask(crc, addr, start, half);
404 int result1 = task1.compute();
405 return combine(result1, task2.join(), length - half);
406 }
407 }
408 }
409 }