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 sun.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 1.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 }