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