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