1 /*
2 * Copyright (c) 2014, 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 package java.util.zip;
26
27 import java.nio.ByteBuffer;
28 import java.nio.ByteOrder;
29
30 import jdk.internal.HotSpotIntrinsicCandidate;
31 import jdk.internal.misc.Unsafe;
32 import sun.nio.ch.DirectBuffer;
33
34 /**
35 * A class that can be used to compute the CRC-32C of a data stream.
36 *
37 * <p>
38 * CRC-32C is defined in <a href="http://www.ietf.org/rfc/rfc3720.txt">RFC
39 * 3720</a>: Internet Small Computer Systems Interface (iSCSI).
40 * </p>
41 *
42 * <p>
43 * Passing a {@code null} argument to a method in this class will cause a
44 * {@link NullPointerException} to be thrown.
45 * </p>
46 *
47 * @since 9
48 */
49 public final class CRC32C implements Checksum {
50
51 /*
52 * This CRC-32C implementation uses the 'slicing-by-8' algorithm described
53 * in the paper "A Systematic Approach to Building High Performance
54 * Software-Based CRC Generators" by Michael E. Kounavis and Frank L. Berry,
55 * Intel Research and Development
56 */
57
58 /**
59 * CRC-32C Polynomial
60 */
61 private static final int CRC32C_POLY = 0x1EDC6F41;
62 private static final int REVERSED_CRC32C_POLY = Integer.reverse(CRC32C_POLY);
63
64 private static final Unsafe UNSAFE = Unsafe.getUnsafe();
65
66 // Lookup tables
67 // Lookup table for single byte calculations
68 private static final int[] byteTable;
69 // Lookup tables for bulk operations in 'slicing-by-8' algorithm
70 private static final int[][] byteTables = new int[8][256];
71 private static final int[] byteTable0 = byteTables[0];
72 private static final int[] byteTable1 = byteTables[1];
73 private static final int[] byteTable2 = byteTables[2];
74 private static final int[] byteTable3 = byteTables[3];
75 private static final int[] byteTable4 = byteTables[4];
76 private static final int[] byteTable5 = byteTables[5];
77 private static final int[] byteTable6 = byteTables[6];
78 private static final int[] byteTable7 = byteTables[7];
79
80 static {
81 // Generate lookup tables
82 // High-order polynomial term stored in LSB of r.
83 for (int index = 0; index < byteTables[0].length; index++) {
84 int r = index;
85 for (int i = 0; i < Byte.SIZE; i++) {
86 if ((r & 1) != 0) {
87 r = (r >>> 1) ^ REVERSED_CRC32C_POLY;
88 } else {
89 r >>>= 1;
90 }
91 }
92 byteTables[0][index] = r;
93 }
94
95 for (int index = 0; index < byteTables[0].length; index++) {
96 int r = byteTables[0][index];
97
98 for (int k = 1; k < byteTables.length; k++) {
99 r = byteTables[0][r & 0xFF] ^ (r >>> 8);
100 byteTables[k][index] = r;
101 }
102 }
103
104 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
105 byteTable = byteTables[0];
106 } else { // ByteOrder.BIG_ENDIAN
107 byteTable = new int[byteTable0.length];
108 System.arraycopy(byteTable0, 0, byteTable, 0, byteTable0.length);
109 for (int[] table : byteTables) {
110 for (int index = 0; index < table.length; index++) {
111 table[index] = Integer.reverseBytes(table[index]);
112 }
113 }
114 }
115 }
116
117 /**
118 * Calculated CRC-32C value
119 */
120 private int crc = 0xFFFFFFFF;
121
122 /**
123 * Creates a new CRC32C object.
124 */
125 public CRC32C() {
126 }
127
128 /**
129 * Updates the CRC-32C checksum with the specified byte (the low eight bits
130 * of the argument b).
131 */
132 @Override
133 public void update(int b) {
134 crc = (crc >>> 8) ^ byteTable[(crc ^ (b & 0xFF)) & 0xFF];
135 }
136
137 /**
138 * Updates the CRC-32C checksum with the specified array of bytes.
139 *
140 * @throws ArrayIndexOutOfBoundsException
141 * if {@code off} is negative, or {@code len} is negative, or
142 * {@code off+len} is negative or greater than the length of
143 * the array {@code b}.
144 */
145 @Override
146 public void update(byte[] b, int off, int len) {
147 if (b == null) {
148 throw new NullPointerException();
149 }
150 if (off < 0 || len < 0 || off > b.length - len) {
151 throw new ArrayIndexOutOfBoundsException();
152 }
153 crc = updateBytes(crc, b, off, (off + len));
154 }
155
156 /**
157 * Updates the CRC-32C checksum with the bytes from the specified buffer.
158 *
159 * The checksum is updated with the remaining bytes in the buffer, starting
160 * at the buffer's position. Upon return, the buffer's position will be
161 * updated to its limit; its limit will not have been changed.
162 */
163 @Override
164 public void update(ByteBuffer buffer) {
165 int pos = buffer.position();
166 int limit = buffer.limit();
167 assert (pos <= limit);
168 int rem = limit - pos;
169 if (rem <= 0) {
170 return;
171 }
172
173 if (buffer instanceof DirectBuffer) {
174 crc = updateDirectByteBuffer(crc, ((DirectBuffer) buffer).address(),
175 pos, limit);
176 } else if (buffer.hasArray()) {
177 crc = updateBytes(crc, buffer.array(), pos + buffer.arrayOffset(),
178 limit + buffer.arrayOffset());
179 } else {
180 byte[] b = new byte[Math.min(buffer.remaining(), 4096)];
181 while (buffer.hasRemaining()) {
182 int length = Math.min(buffer.remaining(), b.length);
183 buffer.get(b, 0, length);
184 update(b, 0, length);
185 }
186 }
187 buffer.position(limit);
188 }
189
190 /**
191 * Resets CRC-32C to initial value.
192 */
193 @Override
194 public void reset() {
195 crc = 0xFFFFFFFF;
196 }
197
198 /**
199 * Returns CRC-32C value.
200 */
201 @Override
202 public long getValue() {
203 return (~crc) & 0xFFFFFFFFL;
204 }
205
206 /**
207 * Updates the CRC-32C checksum with the specified array of bytes.
208 */
209 @HotSpotIntrinsicCandidate
210 private static int updateBytes(int crc, byte[] b, int off, int end) {
211
212 // Do only byte reads for arrays so short they can't be aligned
213 // or if bytes are stored with a larger witdh than one byte.,%
214 if (end - off >= 8 && Unsafe.ARRAY_BYTE_INDEX_SCALE == 1) {
215
216 // align on 8 bytes
217 int alignLength
218 = (8 - ((Unsafe.ARRAY_BYTE_BASE_OFFSET + off) & 0x7)) & 0x7;
219 for (int alignEnd = off + alignLength; off < alignEnd; off++) {
220 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF];
221 }
222
223 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
224 crc = Integer.reverseBytes(crc);
225 }
226
227 // slicing-by-8
228 for (; off < (end - Long.BYTES); off += Long.BYTES) {
229 int firstHalf;
230 int secondHalf;
231 if (Unsafe.ADDRESS_SIZE == 4) {
232 // On 32 bit platforms read two ints instead of a single 64bit long
233 firstHalf = UNSAFE.getInt(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
234 secondHalf = UNSAFE.getInt(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off
235 + Integer.BYTES);
236 } else {
237 long value = UNSAFE.getLong(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
238 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
239 firstHalf = (int) value;
240 secondHalf = (int) (value >>> 32);
241 } else { // ByteOrder.BIG_ENDIAN
242 firstHalf = (int) (value >>> 32);
243 secondHalf = (int) value;
244 }
245 }
246 crc ^= firstHalf;
247 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
248 crc = byteTable7[crc & 0xFF]
249 ^ byteTable6[(crc >>> 8) & 0xFF]
250 ^ byteTable5[(crc >>> 16) & 0xFF]
251 ^ byteTable4[crc >>> 24]
252 ^ byteTable3[secondHalf & 0xFF]
253 ^ byteTable2[(secondHalf >>> 8) & 0xFF]
254 ^ byteTable1[(secondHalf >>> 16) & 0xFF]
255 ^ byteTable0[secondHalf >>> 24];
256 } else { // ByteOrder.BIG_ENDIAN
257 crc = byteTable0[secondHalf & 0xFF]
258 ^ byteTable1[(secondHalf >>> 8) & 0xFF]
259 ^ byteTable2[(secondHalf >>> 16) & 0xFF]
260 ^ byteTable3[secondHalf >>> 24]
261 ^ byteTable4[crc & 0xFF]
262 ^ byteTable5[(crc >>> 8) & 0xFF]
263 ^ byteTable6[(crc >>> 16) & 0xFF]
264 ^ byteTable7[crc >>> 24];
265 }
266 }
267
268 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
269 crc = Integer.reverseBytes(crc);
270 }
271 }
272
273 // Tail
274 for (; off < end; off++) {
275 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF];
276 }
277
278 return crc;
279 }
280
281 /**
282 * Updates the CRC-32C checksum reading from the specified address.
283 */
284 @HotSpotIntrinsicCandidate
285 private static int updateDirectByteBuffer(int crc, long address,
286 int off, int end) {
287
288 // Do only byte reads for arrays so short they can't be aligned
289 if (end - off >= 8) {
290
291 // align on 8 bytes
292 int alignLength = (8 - (int) ((address + off) & 0x7)) & 0x7;
293 for (int alignEnd = off + alignLength; off < alignEnd; off++) {
294 crc = (crc >>> 8)
295 ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
296 }
297
298 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
299 crc = Integer.reverseBytes(crc);
300 }
301
302 // slicing-by-8
303 for (; off <= (end - Long.BYTES); off += Long.BYTES) {
304 // Always reading two ints as reading a long followed by
305 // shifting and casting was slower.
306 int firstHalf = UNSAFE.getInt(address + off);
307 int secondHalf = UNSAFE.getInt(address + off + Integer.BYTES);
308 crc ^= firstHalf;
309 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
310 crc = byteTable7[crc & 0xFF]
311 ^ byteTable6[(crc >>> 8) & 0xFF]
312 ^ byteTable5[(crc >>> 16) & 0xFF]
313 ^ byteTable4[crc >>> 24]
314 ^ byteTable3[secondHalf & 0xFF]
315 ^ byteTable2[(secondHalf >>> 8) & 0xFF]
316 ^ byteTable1[(secondHalf >>> 16) & 0xFF]
317 ^ byteTable0[secondHalf >>> 24];
318 } else { // ByteOrder.BIG_ENDIAN
319 crc = byteTable0[secondHalf & 0xFF]
320 ^ byteTable1[(secondHalf >>> 8) & 0xFF]
321 ^ byteTable2[(secondHalf >>> 16) & 0xFF]
322 ^ byteTable3[secondHalf >>> 24]
323 ^ byteTable4[crc & 0xFF]
324 ^ byteTable5[(crc >>> 8) & 0xFF]
325 ^ byteTable6[(crc >>> 16) & 0xFF]
326 ^ byteTable7[crc >>> 24];
327 }
328 }
329
330 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
331 crc = Integer.reverseBytes(crc);
332 }
333 }
334
335 // Tail
336 for (; off < end; off++) {
337 crc = (crc >>> 8)
338 ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
339 }
340
341 return crc;
342 }
343 }