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