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 @SuppressWarnings("deprecation") // Unsafe.{getInt, getLong} 208 private static int updateBytes(int crc, byte[] b, int off, int end) { 209 210 // Do only byte reads for arrays so short they can't be aligned 211 // or if bytes are stored with a larger witdh than one byte.,% 212 if (end - off >= 8 && Unsafe.ARRAY_BYTE_INDEX_SCALE == 1) { 213 214 // align on 8 bytes 215 int alignLength 216 = (8 - ((Unsafe.ARRAY_BYTE_BASE_OFFSET + off) & 0x7)) & 0x7; 217 for (int alignEnd = off + alignLength; off < alignEnd; off++) { 218 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF]; 219 } 220 221 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { 222 crc = Integer.reverseBytes(crc); 223 } 224 225 // slicing-by-8 226 for (; off < (end - Long.BYTES); off += Long.BYTES) { 227 int firstHalf; 228 int secondHalf; 229 if (Unsafe.ADDRESS_SIZE == 4) { 230 // On 32 bit platforms read two ints instead of a single 64bit long 231 firstHalf = UNSAFE.getInt(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off); 232 secondHalf = UNSAFE.getInt(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off 233 + Integer.BYTES); 234 } else { 235 long value = UNSAFE.getLong(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off); 236 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { 237 firstHalf = (int) value; 238 secondHalf = (int) (value >>> 32); 239 } else { // ByteOrder.BIG_ENDIAN 240 firstHalf = (int) (value >>> 32); 241 secondHalf = (int) value; 242 } 243 } 244 crc ^= firstHalf; 245 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { 246 crc = byteTable7[crc & 0xFF] 247 ^ byteTable6[(crc >>> 8) & 0xFF] 248 ^ byteTable5[(crc >>> 16) & 0xFF] 249 ^ byteTable4[crc >>> 24] 250 ^ byteTable3[secondHalf & 0xFF] 251 ^ byteTable2[(secondHalf >>> 8) & 0xFF] 252 ^ byteTable1[(secondHalf >>> 16) & 0xFF] 253 ^ byteTable0[secondHalf >>> 24]; 254 } else { // ByteOrder.BIG_ENDIAN 255 crc = byteTable0[secondHalf & 0xFF] 256 ^ byteTable1[(secondHalf >>> 8) & 0xFF] 257 ^ byteTable2[(secondHalf >>> 16) & 0xFF] 258 ^ byteTable3[secondHalf >>> 24] 259 ^ byteTable4[crc & 0xFF] 260 ^ byteTable5[(crc >>> 8) & 0xFF] 261 ^ byteTable6[(crc >>> 16) & 0xFF] 262 ^ byteTable7[crc >>> 24]; 263 } 264 } 265 266 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { 267 crc = Integer.reverseBytes(crc); 268 } 269 } 270 271 // Tail 272 for (; off < end; off++) { 273 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF]; 274 } 275 276 return crc; 277 } 278 279 /** 280 * Updates the CRC-32C checksum reading from the specified address. 281 */ 282 private static int updateDirectByteBuffer(int crc, long address, 283 int off, int end) { 284 285 // Do only byte reads for arrays so short they can't be aligned 286 if (end - off >= 8) { 287 288 // align on 8 bytes 289 int alignLength = (8 - (int) ((address + off) & 0x7)) & 0x7; 290 for (int alignEnd = off + alignLength; off < alignEnd; off++) { 291 crc = (crc >>> 8) 292 ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF]; 293 } 294 295 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { 296 crc = Integer.reverseBytes(crc); 297 } 298 299 // slicing-by-8 300 for (; off <= (end - Long.BYTES); off += Long.BYTES) { 301 // Always reading two ints as reading a long followed by 302 // shifting and casting was slower. 303 int firstHalf = UNSAFE.getInt(address + off); 304 int secondHalf = UNSAFE.getInt(address + off + Integer.BYTES); 305 crc ^= firstHalf; 306 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { 307 crc = byteTable7[crc & 0xFF] 308 ^ byteTable6[(crc >>> 8) & 0xFF] 309 ^ byteTable5[(crc >>> 16) & 0xFF] 310 ^ byteTable4[crc >>> 24] 311 ^ byteTable3[secondHalf & 0xFF] 312 ^ byteTable2[(secondHalf >>> 8) & 0xFF] 313 ^ byteTable1[(secondHalf >>> 16) & 0xFF] 314 ^ byteTable0[secondHalf >>> 24]; 315 } else { // ByteOrder.BIG_ENDIAN 316 crc = byteTable0[secondHalf & 0xFF] 317 ^ byteTable1[(secondHalf >>> 8) & 0xFF] 318 ^ byteTable2[(secondHalf >>> 16) & 0xFF] 319 ^ byteTable3[secondHalf >>> 24] 320 ^ byteTable4[crc & 0xFF] 321 ^ byteTable5[(crc >>> 8) & 0xFF] 322 ^ byteTable6[(crc >>> 16) & 0xFF] 323 ^ byteTable7[crc >>> 24]; 324 } 325 } 326 327 if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { 328 crc = Integer.reverseBytes(crc); 329 } 330 } 331 332 // Tail 333 for (; off < end; off++) { 334 crc = (crc >>> 8) 335 ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF]; 336 } 337 338 return crc; 339 } 340 }