1*0b57cec5SDimitry Andric //===--- CRC.cpp - Cyclic Redundancy Check implementation -----------------===//
2*0b57cec5SDimitry Andric //
3*0b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*0b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5*0b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*0b57cec5SDimitry Andric //
7*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
8*0b57cec5SDimitry Andric //
9*0b57cec5SDimitry Andric // This file contains implementations of CRC functions.
10*0b57cec5SDimitry Andric //
11*0b57cec5SDimitry Andric // The implementation technique is the one mentioned in:
12*0b57cec5SDimitry Andric // D. V. Sarwate. 1988. Computation of cyclic redundancy checks via table
13*0b57cec5SDimitry Andric // look-up. Commun. ACM 31, 8 (August 1988)
14*0b57cec5SDimitry Andric //
15*0b57cec5SDimitry Andric // See also Ross N. Williams "A Painless Guide to CRC Error Detection
16*0b57cec5SDimitry Andric // Algorithms" (https://zlib.net/crc_v3.txt) or Hacker's Delight (2nd ed.)
17*0b57cec5SDimitry Andric // Chapter 14 (Figure 14-7 in particular) for how the algorithm works.
18*0b57cec5SDimitry Andric //
19*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
20*0b57cec5SDimitry Andric
21*0b57cec5SDimitry Andric #include "llvm/Support/CRC.h"
22*0b57cec5SDimitry Andric
23*0b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h"
24*0b57cec5SDimitry Andric #include "llvm/Config/config.h"
25*0b57cec5SDimitry Andric
26*0b57cec5SDimitry Andric using namespace llvm;
27*0b57cec5SDimitry Andric
28*0b57cec5SDimitry Andric #if !LLVM_ENABLE_ZLIB
29*0b57cec5SDimitry Andric
30*0b57cec5SDimitry Andric static const uint32_t CRCTable[256] = {
31*0b57cec5SDimitry Andric 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
32*0b57cec5SDimitry Andric 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
33*0b57cec5SDimitry Andric 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
34*0b57cec5SDimitry Andric 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
35*0b57cec5SDimitry Andric 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
36*0b57cec5SDimitry Andric 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
37*0b57cec5SDimitry Andric 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
38*0b57cec5SDimitry Andric 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
39*0b57cec5SDimitry Andric 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
40*0b57cec5SDimitry Andric 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
41*0b57cec5SDimitry Andric 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
42*0b57cec5SDimitry Andric 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
43*0b57cec5SDimitry Andric 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
44*0b57cec5SDimitry Andric 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
45*0b57cec5SDimitry Andric 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
46*0b57cec5SDimitry Andric 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
47*0b57cec5SDimitry Andric 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
48*0b57cec5SDimitry Andric 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
49*0b57cec5SDimitry Andric 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
50*0b57cec5SDimitry Andric 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
51*0b57cec5SDimitry Andric 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
52*0b57cec5SDimitry Andric 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
53*0b57cec5SDimitry Andric 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
54*0b57cec5SDimitry Andric 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
55*0b57cec5SDimitry Andric 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
56*0b57cec5SDimitry Andric 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
57*0b57cec5SDimitry Andric 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
58*0b57cec5SDimitry Andric 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
59*0b57cec5SDimitry Andric 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
60*0b57cec5SDimitry Andric 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
61*0b57cec5SDimitry Andric 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
62*0b57cec5SDimitry Andric 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
63*0b57cec5SDimitry Andric 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
64*0b57cec5SDimitry Andric 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
65*0b57cec5SDimitry Andric 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
66*0b57cec5SDimitry Andric 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
67*0b57cec5SDimitry Andric 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
68*0b57cec5SDimitry Andric 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
69 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
70 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
71 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
72 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
73 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d};
74
crc32(uint32_t CRC,ArrayRef<uint8_t> Data)75 uint32_t llvm::crc32(uint32_t CRC, ArrayRef<uint8_t> Data) {
76 CRC ^= 0xFFFFFFFFU;
77 for (uint8_t Byte : Data) {
78 int TableIdx = (CRC ^ Byte) & 0xff;
79 CRC = CRCTable[TableIdx] ^ (CRC >> 8);
80 }
81 return CRC ^ 0xFFFFFFFFU;
82 }
83
84 #else
85
86 #include <zlib.h>
crc32(uint32_t CRC,ArrayRef<uint8_t> Data)87 uint32_t llvm::crc32(uint32_t CRC, ArrayRef<uint8_t> Data) {
88 // Zlib's crc32() only takes a 32-bit length, so we have to iterate for larger
89 // sizes. One could use crc32_z() instead, but that's a recent (2017) addition
90 // and may not be available on all systems.
91 do {
92 ArrayRef<uint8_t> Slice = Data.take_front(UINT32_MAX);
93 CRC = ::crc32(CRC, (const Bytef *)Slice.data(), (uInt)Slice.size());
94 Data = Data.drop_front(Slice.size());
95 } while (Data.size() > 0);
96 return CRC;
97 }
98
99 #endif
100
crc32(ArrayRef<uint8_t> Data)101 uint32_t llvm::crc32(ArrayRef<uint8_t> Data) { return crc32(0, Data); }
102
update(ArrayRef<uint8_t> Data)103 void JamCRC::update(ArrayRef<uint8_t> Data) {
104 CRC ^= 0xFFFFFFFFU; // Undo CRC-32 Init.
105 CRC = crc32(CRC, Data);
106 CRC ^= 0xFFFFFFFFU; // Undo CRC-32 XorOut.
107 }
108