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 * <P>
34 * A class that can be used to compute the CRC-32C of a data stream.</P>
35 *
36 * <P>
37 * CRC-32C is defined in <a href="http://tools.ietf.org/html/rfc3720">IETF RFC
38 * 3720</a>: Internet Small Computer Systems Interface (iSCSI).</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.</P>
43 *
44 * @see Checksum
45 * @since 1.9
46 */
47 public class CRC32C implements Checksum {
48
49 /**
50 * Calculated CRC-32C value
51 */
52 private int crc = 0xFFFFFFFF;
53
54 // CRC-32C Polynom
55 private final static int CRC32C_POLY = 0x1EDC6F41;
56
57 /**
58 * This CRC-32C implementation uses the 'slicing-by-8' algorithm described
59 * in the paper "A Systematic Approach to Building High Performance
60 * Software-Based CRC Generators" by Michael E. Kounavis and Frank L. Berry,
61 * Intel Research and Development
62 */
63 private transient final static Unsafe UNSAFE = Unsafe.getUnsafe();
64 private transient final static ByteOrder ENDIAN = ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN)
65 ? ByteOrder.BIG_ENDIAN : ByteOrder.LITTLE_ENDIAN;
66
67 // Lookup tables
68 private transient final static int[][] byteTables = new int[8][256];
69 private transient final static int[] byteTable;
70 private transient final static int[] byteTable0 = byteTables[0];
71 private transient final static int[] byteTable1 = byteTables[1];
72 private transient final static int[] byteTable2 = byteTables[2];
73 private transient final static int[] byteTable3 = byteTables[3];
74 private transient final static int[] byteTable4 = byteTables[4];
75 private transient final static int[] byteTable5 = byteTables[5];
76 private transient final static int[] byteTable6 = byteTables[6];
77 private transient final static int[] byteTable7 = byteTables[7];
78
79 static {
80 // Generate lookup tables
81 for (int index = 0; index < byteTables[0].length; index++) {
82 int r = reflect(index);
83 for (int i = 0; i < Byte.SIZE; i++) {
84 if ((r & 0x080000000) != 0) {
85 r = (r << 1) ^ CRC32C_POLY;
86 } else {
87 r <<= 1;
88 }
89 }
90 byteTables[0][index] = reflect(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 (ENDIAN == 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] = swap32(table[index]);
110 }
111 }
112 }
113 }
114
115 /**
116 * Creates a new CRC32C object.
117 */
118 public CRC32C() {
119 }
120
121 /**
122 * Updates the CRC-32C checksum with the specified byte (the low eight bits
123 * of the argument b).
124 *
125 * @param b the byte to update the checksum with
126 */
127 @Override
128 public void update(int b) {
129 crc = (crc >>> 8) ^ byteTable[(crc ^ (b & 0xFF)) & 0xFF];
130 }
131
132 /**
133 * Updates the CRC-32C checksum with the specified array of bytes.
134 *
135 * @throws ArrayIndexOutOfBoundsException if {@code off} is negative, or
136 * {@code len} is negative, or {@code off+len} is greater than the length of
137 * the array {@code b}
138 *
139 * @param b the byte array to update the checksum with
140 * @param off the start offset of the data
141 * @param len the number of bytes to use for the update
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 + len) > b.length) {
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 using
158 * buffer.{@link java.nio.Buffer#remaining() remaining()} bytes starting at
159 * buffer.{@link java.nio.Buffer#position() position()} Upon return, the
160 * buffer's position will be updated to its limit; its limit will not have
161 * been changed.
162 *
163 * @param buffer the ByteBuffer to update the checksum with
164 */
165 @Override
166 public void update(ByteBuffer buffer) {
167 int pos = buffer.position();
168 int limit = buffer.limit();
169 assert (pos <= limit);
170 int rem = limit - pos;
171 if (rem <= 0) {
172 return;
173 }
174
175 if (buffer instanceof DirectBuffer) {
176 crc = updateDirectByteBuffer(crc, ((DirectBuffer) buffer).address(), pos, limit);
177 } else if (buffer.hasArray()) {
178 crc = updateBytes(crc, buffer.array(), pos + buffer.arrayOffset(), limit + buffer.arrayOffset());
179 } else {
180 byte[] b = new byte[rem];
181 buffer.get(b);
182 crc = updateBytes(crc, b, 0, b.length);
183 }
184 buffer.position(limit);
185 }
186
187 /**
188 * Resets CRC-32C to initial value.
189 */
190 @Override
191 public void reset() {
192 crc = 0xFFFFFFFF;
193 }
194
195 /**
196 * Returns CRC-32C value.
197 */
198 @Override
199 public long getValue() {
200 return (~crc) & 0xFFFFFFFFL;
201 }
202
203 /**
204 * Updates the CRC-32C checksum with the specified array of bytes.
205 */
206 private static int updateBytes(int crc, byte[] b, int off, int end) {
207
208 if (end - off >= 8) {
209
210 // align on 8 bytes
211 int alignLength = (8 - ((Unsafe.ARRAY_BYTE_BASE_OFFSET + off) & 0x7)) & 0x7;
212 for (int alignEnd = off + alignLength; off < alignEnd; off++) {
213 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF];
214 }
215
216 if (ENDIAN == ByteOrder.BIG_ENDIAN) {
217 crc = swap32(crc);
218 }
219
220 // slicing-by-8
221 for (; off < (end - Unsafe.ARRAY_LONG_INDEX_SCALE); off += Unsafe.ARRAY_LONG_INDEX_SCALE) {
222 int firstHalf;
223 int secondHalf;
224 if (Unsafe.ADDRESS_SIZE == 4) {
225 // On 32 bit platforms read two ints instead of a single 64bit long
226 firstHalf = UNSAFE.getInt(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
227 secondHalf = UNSAFE.getInt(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off + Unsafe.ARRAY_INT_INDEX_SCALE);
228 } else {
229 long value = UNSAFE.getLong(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
230 if (ENDIAN == ByteOrder.LITTLE_ENDIAN) {
231 firstHalf = (int) (value & 0xFFFFFFFF);
232 secondHalf = (int) (value >>> 32);
233 } else { // ByteOrder.BIG_ENDIAN
234 firstHalf = (int) (value >>> 32);
235 secondHalf = (int) (value & 0xFFFFFFFF);
236 }
237 }
238 crc ^= firstHalf;
239 if (ENDIAN == ByteOrder.LITTLE_ENDIAN) {
240 crc = byteTable7[crc & 0xFF]
241 ^ byteTable6[(crc >>> 8) & 0xFF]
242 ^ byteTable5[(crc >>> 16) & 0xFF]
243 ^ byteTable4[crc >>> 24]
244 ^ byteTable3[secondHalf & 0xFF]
245 ^ byteTable2[(secondHalf >>> 8) & 0xFF]
246 ^ byteTable1[(secondHalf >>> 16) & 0xFF]
247 ^ byteTable0[secondHalf >>> 24];
248 } else { // ByteOrder.BIG_ENDIAN
249 crc = byteTable0[secondHalf & 0xFF]
250 ^ byteTable1[(secondHalf >>> 8) & 0xFF]
251 ^ byteTable2[(secondHalf >>> 16) & 0xFF]
252 ^ byteTable3[secondHalf >>> 24]
253 ^ byteTable4[crc & 0xFF]
254 ^ byteTable5[(crc >>> 8) & 0xFF]
255 ^ byteTable6[(crc >>> 16) & 0xFF]
256 ^ byteTable7[crc >>> 24];
257 }
258 }
259
260 if (ENDIAN == ByteOrder.BIG_ENDIAN) {
261 crc = swap32(crc);
262 }
263 }
264
265 // Tail
266 for (; off < end; off++) {
267 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF];
268 }
269
270 return crc;
271 }
272
273 /**
274 * Updates the CRC-32C checksum reading from the specified address.
275 */
276 private static int updateDirectByteBuffer(int crc, long address, int off, int end) {
277
278 if (end - off >= 8) {
279
280 // align on 8 bytes
281 int alignLength = (8 - (int) ((address + off) & 0x7)) & 0x7;
282 for (int alignEnd = off + alignLength; off < alignEnd; off++) {
283 crc = (crc >>> 8) ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
284 }
285
286 if (ENDIAN == ByteOrder.BIG_ENDIAN) {
287 crc = swap32(crc);
288 }
289
290 // slicing-by-8
291 for (; off < (end - Unsafe.ARRAY_LONG_INDEX_SCALE); off += Unsafe.ARRAY_LONG_INDEX_SCALE) {
292 int firstHalf = UNSAFE.getInt(address + off);
293 int secondHalf = UNSAFE.getInt(address + off + Unsafe.ARRAY_INT_INDEX_SCALE);
294 crc ^= firstHalf;
295 if (ENDIAN == ByteOrder.LITTLE_ENDIAN) {
296 crc = byteTable7[crc & 0xFF]
297 ^ byteTable6[(crc >>> 8) & 0xFF]
298 ^ byteTable5[(crc >>> 16) & 0xFF]
299 ^ byteTable4[crc >>> 24]
300 ^ byteTable3[secondHalf & 0xFF]
301 ^ byteTable2[(secondHalf >>> 8) & 0xFF]
302 ^ byteTable1[(secondHalf >>> 16) & 0xFF]
303 ^ byteTable0[secondHalf >>> 24];
304 } else { // ByteOrder.BIG_ENDIAN
305 crc = byteTable0[secondHalf & 0xFF]
306 ^ byteTable1[(secondHalf >>> 8) & 0xFF]
307 ^ byteTable2[(secondHalf >>> 16) & 0xFF]
308 ^ byteTable3[secondHalf >>> 24]
309 ^ byteTable4[crc & 0xFF]
310 ^ byteTable5[(crc >>> 8) & 0xFF]
311 ^ byteTable6[(crc >>> 16) & 0xFF]
312 ^ byteTable7[crc >>> 24];
313 }
314 }
315
316 if (ENDIAN == ByteOrder.BIG_ENDIAN) {
317 crc = swap32(crc);
318 }
319 }
320
321 // Tail
322 for (; off < end; off++) {
323 crc = (crc >>> 8) ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
324 }
325
326 return crc;
327 }
328
329 /**
330 * Swap the bytes in a 32 bit quantity.
331 */
332 private static int swap32(int value) {
333 return ((value >>> 24) + ((value >>> 8) & 0xFF00) + ((value & 0xFF00) << 8) + (value << 24));
334 }
335
336 /**
337 * Reflect a 32 bit quantity.
338 */
339 private static int reflect(int b) {
340 return (((b >>> 31) & 0x000000001)
341 | ((b >>> 29) & 0x000000002)
342 | ((b >>> 27) & 0x000000004)
343 | ((b >>> 25) & 0x000000008)
344 | ((b >>> 23) & 0x000000010)
345 | ((b >>> 21) & 0x000000020)
346 | ((b >>> 19) & 0x000000040)
347 | ((b >>> 17) & 0x000000080)
348 | ((b >>> 15) & 0x000000100)
349 | ((b >>> 13) & 0x000000200)
350 | ((b >>> 11) & 0x000000400)
351 | ((b >>> 9) & 0x000000800)
352 | ((b >>> 7) & 0x000001000)
353 | ((b >>> 5) & 0x000002000)
354 | ((b >>> 3) & 0x000004000)
355 | ((b >>> 1) & 0x000008000)
356 | ((b << 1) & 0x000010000)
357 | ((b << 3) & 0x000020000)
358 | ((b << 5) & 0x000040000)
359 | ((b << 7) & 0x000080000)
360 | ((b << 9) & 0x000100000)
361 | ((b << 11) & 0x000200000)
362 | ((b << 13) & 0x000400000)
363 | ((b << 15) & 0x000800000)
364 | ((b << 17) & 0x001000000)
365 | ((b << 19) & 0x002000000)
366 | ((b << 21) & 0x004000000)
367 | ((b << 23) & 0x008000000)
368 | ((b << 25) & 0x010000000)
369 | ((b << 27) & 0x020000000)
370 | ((b << 29) & 0x040000000)
371 | ((b << 31) & 0x080000000));
372 }
373 }