Unify the two CRC implementations

[hans]

Summary

David added the JamCRC implementation in r246590. More recently, Eugene added a CRC-32 implementation in r357901, which falls back to zlib's crc32 function if present.

These checksums are essentially the same, so having multiple implementations seems unnecessary. This replaces the CRC-32 implementation with the simpler one from JamCRC, and implements the JamCRC interface in terms of CRC-32 since this means it can use zlib's implementation when available, saving a few bytes and potentially making it faster.

JamCRC took an ArrayRef<char> argument, and CRC-32 took a StringRef. This patch changes it to ArrayRef<uint8_t> which I think is the best choice, and simplifies a few of the callers nicely.

Please take a look!

[thakis]

Nice!

[hans]

Found a call in LLDB too.

[joerg]

Why go back to the large tables for crc32? Just because JamCRC had that bug doesn't mean it should persist.

[hans]

In D68570#1697588, @joerg wrote:

Why go back to the large tables for crc32? Just because JamCRC had that bug doesn't mean it should persist.

Because just using the table is much simpler and we already have it: no need for any run-time initialization and fancy code like call_once. Why do you consider it a bug? Generating a constant table like this at run-time -- again and again for each invocation of the program -- seems less than ideal to me.

[rupprecht]

In D68570#1697633, @hans wrote:

In D68570#1697588, @joerg wrote:

Why go back to the large tables for crc32? Just because JamCRC had that bug doesn't mean it should persist.

Because just using the table is much simpler and we already have it: no need for any run-time initialization and fancy code like call_once. Why do you consider it a bug? Generating a constant table like this at run-time -- again and again for each invocation of the program -- seems less than ideal to me.

Do you have any benchmarks?

A table is simpler in some regards, but also less readable in another sense (what are these random hex values?). Having benchmark results helps settle that debate.

That said, general +1 to removing code complexity/duplication

llvm/lib/Support/CRC.cpp

26–91

Can you leave a comment how this table was generated/how it could be regenerated if needed in the future? And/or a unit test to assert the values are correct?

[thakis]

Also, in practice most clients will build against zlib and not see the tables. +1 to the current approach :)

[mgorny]

I'd personally prefer either the non-table approach or having the tables generated at build time. Given this is only going to be used rarely, I don't think we should clutter the code with big tables.

[hiraditya]

llvm/lib/Support/CRC.cpp

26–91

+1

[ruiu]

llvm/include/llvm/Support/JamCRC.h

45

This is the only place where you pass non-zero value as the first argument, and the way how that value is handled is a little irregular. So how about moving this class to CRC.h and define llvm::crc32 as llvm::crc32(ArrayRef<uint8_t>)?

[hans]

In D68570#1697872, @rupprecht wrote:

In D68570#1697633, @hans wrote:

In D68570#1697588, @joerg wrote:

Why go back to the large tables for crc32? Just because JamCRC had that bug doesn't mean it should persist.

Because just using the table is much simpler and we already have it: no need for any run-time initialization and fancy code like call_once. Why do you consider it a bug? Generating a constant table like this at run-time -- again and again for each invocation of the program -- seems less than ideal to me.

Do you have any benchmarks?

Of what? That generating the table is slower than just using it directly? I'd say no benchmark is needed to conclude that :-)

A table is simpler in some regards, but also less readable in another sense (what are these random hex values?). Having benchmark results helps settle that debate.

It's the standard table for the CRC-32 polynomial. I'll add a comment with some references.

In D68570#1697933, @thakis wrote:

Also, in practice most clients will build against zlib and not see the tables. +1 to the current approach :)

Windows builds will typically not use zlib though, so this code does get used :-)

In D68570#1697940, @mgorny wrote:

I'd personally prefer either the non-table approach or having the tables generated at build time. Given this is only going to be used rarely, I don't think we should clutter the code with big tables.

It's not used rarely, it's used all the time on Windows. Generating the table at build time would be nice in theory, but writing a tablegen and hooking it up in the build system seems like overkill for this.

llvm/include/llvm/Support/JamCRC.h

45

Actually, lldb/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp also passes a non-zero value (from ObjectFileELF::CalculateELFNotesSegmentsCRC32).

But that's not the common case. Let's make an overload for the common case, and moving JamCRC into CRC.h makes sense too.

llvm/lib/Support/CRC.cpp

26–91

I'm adding a comment with references for how the algorithm and the table works. There is already a unit test in llvm/unittests/Support/CRCTest.cpp

[hans]

Adding comments, moving JamCRC into CRC.h, and adding a one-parameter crc32 overload.

[mgorny]

Doesn't winapi provide some method of computing crc32?

[hans]

In D68570#1699278, @mgorny wrote:

Doesn't winapi provide some method of computing crc32?

Not that I'm aware.

[rupprecht]

In D68570#1699204, @hans wrote:

In D68570#1697872, @rupprecht wrote:

Do you have any benchmarks?

Of what? That generating the table is slower than just using it directly? I'd say no benchmark is needed to conclude that :-)

There is also the cost of code complexity to consider. Sure, the table generation goes away, but does that even show up on any benchmark/real world usage of this? Nobody's exercising the table generation code. People are either check-summing once (in which case, it doesn't matter as much if it's slow, because it happens once) or check-summing 1000 times (in which case the one-time table generation is probably not the CRC bottleneck). If there's no performance win, is it worth the potential code complexity of an opaque hex array over constructing it with an algorithm that can be inspected?

FWIW I'm still in favor of this patch, and the objcopy part that Herald added me for LGTM. Addressing my comments would help me understand this code but feel free to ignore if I'm the only one that feels this way.

llvm/lib/Support/CRC.cpp

26–91

From what I can tell:

• This algorithm makes use of one byte from this table per byte in the input array
• The table has 256 entries
• The test only includes "The quick brown fox jumps over the lazy dog" and "123456789" (43 total values if I'm counting correctly)

There's no way that test sufficiently tests that all 256 values here are correct. Maybe check summing a very large (>100k) buffer would give confidence that -- probably -- all values are being used.

I think the unit test is sufficient for testing a generated table because it's hard to mess up the generation in a way that only affects some values. However with a hard-coded table, it's much more likely that a single value here could be wrong due to mechanical issues (e.g. accidentally changing a character in the process of formatting it).

29–37

I'd personally find keeping this as a comment to be more useful in understanding how the table is generated than digging up papers

[majnemer]

LGTM

[rnk]

Maybe a dumb idea: can we compute the table with constexpr evaluation? You could set up a constexpr function that returns a struct that wraps the array, and then the body of the function would construct the array imperatively as the old initialization code did. Set up a constexpr global with an initializer that calls the function.

If not all compilers support this, we could instead use static_assert to check that the table is correct under an #ifdef __clang__, or whatever conditions apply.

One possible drawback of this approach is compile time. If that ends up mattering, it could be ifdef EXPENSIVE_CHECKS or something awful like that.

Another drawback is that I have seen MSVC accept globals marked constexpr, but then sometimes they get dynamic initializers anyway. The static_assert approach might be safer.

[hans]

In D68570#1700024, @rupprecht wrote:

In D68570#1699204, @hans wrote:

In D68570#1697872, @rupprecht wrote:

Do you have any benchmarks?

Of what? That generating the table is slower than just using it directly? I'd say no benchmark is needed to conclude that :-)

There is also the cost of code complexity to consider. Sure, the table generation goes away, but does that even show up on any benchmark/real world usage of this? Nobody's exercising the table generation code. People are either check-summing once (in which case, it doesn't matter as much if it's slow, because it happens once) or check-summing 1000 times (in which case the one-time table generation is probably not the CRC bottleneck). If there's no performance win, is it worth the potential code complexity of an opaque hex array over constructing it with an algorithm that can be inspected?

You're right that it probably doesn't matter much, it's more the principle that it's wasteful to compute it at runtime.

I think maybe our disagreement comes from that I actually see including the table directly as *less* code complexity than the way we currently generate it. It's a code pattern for computing CRC-32. If you search the web for how to compute CRC-32, this table shows up. Some specs even define CRC-32 in terms of the table (e.g. https://docs.microsoft.com/en-us/openspecs/office_protocols/ms-abs/06966aa2-70da-4bf9-8448-3355f277cd77).

I think the code to generate the table (and to use it) is just as opaque. Where did the current code come from? It's from https://github.com/libarchive/libarchive/blob/master/libarchive/archive_crc32.h How did it work? There are no comments.

It's a fancy algorithm and there's no way around reading some external sources to figure out how it works. Using the pre-computed table directly removes some unnecessary work and in my opinion it's clearer than the previous code.

FWIW I'm still in favor of this patch, and the objcopy part that Herald added me for LGTM. Addressing my comments would help me understand this code but feel free to ignore if I'm the only one that feels this way.

I appreciate your comments and I hope I've addressed them satisfactorily.

In D68570#1700080, @rnk wrote:

Maybe a dumb idea: can we compute the table with constexpr evaluation? You could set up a constexpr function that returns a struct that wraps the array, and then the body of the function would construct the array imperatively as the old initialization code did. Set up a constexpr global with an initializer that calls the function.

This sounds fun, but I don't think it would be a step towards less code complexity :-)

If not all compilers support this, we could instead use static_assert to check that the table is correct under an #ifdef __clang__, or whatever conditions apply.

One possible drawback of this approach is compile time. If that ends up mattering, it could be ifdef EXPENSIVE_CHECKS or something awful like that.

Another drawback is that I have seen MSVC accept globals marked constexpr, but then sometimes they get dynamic initializers anyway. The static_assert approach might be safer.

I've extended the unit test to exercise the whole table. That should give us the benefit of static_assert'ing that it's correct, without the code complexity or compile time.

llvm/lib/Support/CRC.cpp

26–91

That's a fair point. I've added a test that exercises the whole table.

29–37

But to understand this code, one would need to dig up papers too.

[hans]

Extend unit test; clang-format.

lld/COFF/PDB.cpp

static pdb::SectionContrib createSectionContrib(const Chunk *c, uint32_t modi) {
   sc.ISect = os ? os->sectionIndex : llvm::pdb::kInvalidStreamIndex;
   sc.Off = c && os ? c->getRVA() - os->getRVA() : 0;
   sc.Size = c ? c->getSize() : -1;
   if (auto *secChunk = dyn_cast_or_null<SectionChunk>(c)) {
     sc.Characteristics = secChunk->header->Characteristics;
     sc.Imod = secChunk->file->moduleDBI->getModuleIndex();
     ArrayRef<uint8_t> contents = secChunk->getContents();
     JamCRC crc(0);
-    ArrayRef<char> charContents = makeArrayRef(
-        reinterpret_cast<const char *>(contents.data()), contents.size());
-    crc.update(charContents);
+    crc.update(contents);
     sc.DataCrc = crc.getCRC();
   } else {
     sc.Characteristics = os ? os->header.Characteristics : 0;
     sc.Imod = modi;
   }
   sc.RelocCrc = 0; // FIXME
 
   return sc;

llvm/include/llvm/Support/CRC.h

 //===-- llvm/Support/CRC.h - Cyclic Redundancy Check-------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains basic functions for calculating Cyclic Redundancy Check
 // or CRC.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_CRC_H
 #define LLVM_SUPPORT_CRC_H
 
-#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
+template <typename T> class ArrayRef;
+
 /// zlib independent CRC32 calculation.
-uint32_t crc32(uint32_t CRC, StringRef S);
+uint32_t crc32(uint32_t CRC, ArrayRef<uint8_t> Data);
 } // end namespace llvm
 
 #endif

llvm/include/llvm/Support/JamCRC.h

 //   Width  : 32
 //   Poly   : 04C11DB7
 //   Init   : FFFFFFFF
 //   RefIn  : True
 //   RefOut : True
 //   XorOut : 00000000
 //   Check  : 340BC6D9 (result of CRC for "123456789")
 //
+// In other words, this is the same as CRC-32, except that XorOut is 0 instead
+// of FFFFFFFF.
+//
 // N.B.  We permit flexibility of the "Init" value.  Some consumers of this need
 //       it to be zero.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_JAMCRC_H
 #define LLVM_SUPPORT_JAMCRC_H
 
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/CRC.h"
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
-template <typename T> class ArrayRef;
 
 class JamCRC {
 public:
   JamCRC(uint32_t Init = 0xFFFFFFFFU) : CRC(Init) {}
 
   // Update the CRC calculation with Data.
-  void update(ArrayRef<char> Data);
+  void update(ArrayRef<uint8_t> Data) {
+    CRC ^= 0xFFFFFFFFU; // Undo CRC-32 Init.
+    CRC = llvm::crc32(CRC, Data);
+    CRC ^= 0xFFFFFFFFU; // Undo CRC-32 XorOut.
+  }
 
   uint32_t getCRC() const { return CRC; }
 
 private:
   uint32_t CRC;
 };
 } // End of namespace llvm
 
 #endif

llvm/lib/DebugInfo/PDB/Native/Hash.cpp

uint32_t pdb::hashStringV2(StringRef Str) {
   }
 
   return Hash * 1664525U + 1013904223U;
 }
 
 // Corresponds to `SigForPbCb` in langapi/shared/crc32.h.
 uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) {
   JamCRC JC(/*Init=*/0U);
-  JC.update(makeArrayRef<char>(reinterpret_cast<const char *>(Buf.data()),
-                               Buf.size()));
+  JC.update(Buf);
   return JC.getCRC();
 }

llvm/lib/DebugInfo/PDB/Native/PDBFileBuilder.cpp

Error PDBFileBuilder::finalizeMsfLayout() {
   if (Info) {
     if (auto EC = Info->finalizeMsfLayout())
       return EC;
   }
 
   if (!InjectedSources.empty()) {
     for (const auto &IS : InjectedSources) {
       JamCRC CRC(0);
-      CRC.update(makeArrayRef(IS.Content->getBufferStart(),
-                              IS.Content->getBufferSize()));
+      CRC.update(arrayRefFromStringRef(IS.Content->getBuffer()));
 
       SrcHeaderBlockEntry Entry;
       ::memset(&Entry, 0, sizeof(SrcHeaderBlockEntry));
       Entry.Size = sizeof(SrcHeaderBlockEntry);
       Entry.FileSize = IS.Content->getBufferSize();
       Entry.FileNI = IS.NameIndex;
       Entry.VFileNI = IS.VNameIndex;
       Entry.ObjNI = 1;

llvm/lib/DebugInfo/PDB/Native/TpiHashing.cpp

case LF_UDT_MOD_SRC_LINE:
     return getSourceLineHash<UdtModSourceLineRecord>(Rec);
 
   default:
     break;
   }
 
   // Run CRC32 over the bytes. This corresponds to `hashBufv8`.
   JamCRC JC(/*Init=*/0U);
-  ArrayRef<char> Bytes(reinterpret_cast<const char *>(Rec.data().data()),
-                       Rec.data().size());
-  JC.update(Bytes);
+  JC.update(Rec.data());
   return JC.getCRC();
 }

llvm/lib/DebugInfo/Symbolize/Symbolize.cpp

std::string getDarwinDWARFResourceForPath(
   return ResourceName.str();
 }
 
 bool checkFileCRC(StringRef Path, uint32_t CRCHash) {
   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
       MemoryBuffer::getFileOrSTDIN(Path);
   if (!MB)
     return false;
-  return CRCHash == llvm::crc32(0, MB.get()->getBuffer());
+  return CRCHash == llvm::crc32(0, arrayRefFromStringRef(MB.get()->getBuffer()));
 }
 
 bool findDebugBinary(const std::string &OrigPath,
                      const std::string &DebuglinkName, uint32_t CRCHash,
                      const std::string &FallbackDebugPath,
                      std::string &Result) {
   SmallString<16> OrigDir(OrigPath);
   llvm::sys::path::remove_filename(OrigDir);

llvm/lib/MC/WinCOFFObjectWriter.cpp

uint32_t WinCOFFObjectWriter::writeSectionContents(MCAssembler &Asm,
   Asm.writeSectionData(VecOS, &MCSec, Layout);
 
   // Write the section contents to the object file.
   W.OS << Buf;
 
   // Calculate our CRC with an initial value of '0', this is not how
   // JamCRC is specified but it aligns with the expected output.
   JamCRC JC(/*Init=*/0);
-  JC.update(Buf);
+  JC.update(makeArrayRef(reinterpret_cast<uint8_t*>(Buf.data()), Buf.size()));
   return JC.getCRC();
 }
 
 void WinCOFFObjectWriter::writeSection(MCAssembler &Asm,
                                        const MCAsmLayout &Layout,
                                        const COFFSection &Sec,
                                        const MCSection &MCSec) {
   if (Sec.Number == -1)

llvm/lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   FormatVariadic.cpp
   GlobPattern.cpp
   GraphWriter.cpp
   Hashing.cpp
   InitLLVM.cpp
   IntEqClasses.cpp
   IntervalMap.cpp
   ItaniumManglingCanonicalizer.cpp
-  JamCRC.cpp
   JSON.cpp
   KnownBits.cpp
   LEB128.cpp
   LineIterator.cpp
   Locale.cpp
   LockFileManager.cpp
   LowLevelType.cpp
   ManagedStatic.cpp

llvm/lib/Support/CRC.cpp

 //===--- CRC.cpp - Cyclic Redundancy Check implementation -----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-//  This file implements llvm::crc32 function.
+// This file implements llvm::crc32 function.
 //
+// The implementation technique is the one mentioned in:
+// D. V. Sarwate. 1988. Computation of cyclic redundancy checks via table
+// look-up. Commun. ACM 31, 8 (August 1988)
+//
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/CRC.h"
+
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Config/config.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/Support/Threading.h"
-#include <array>
 
 using namespace llvm;
 
 #if LLVM_ENABLE_ZLIB == 0 || !HAVE_ZLIB_H
-using CRC32Table = std::array<uint32_t, 256>;
 
-static void initCRC32Table(CRC32Table *Tbl) {
-  auto Shuffle = [](uint32_t V) {
-    return (V & 1) ? (V >> 1) ^ 0xEDB88320U : V >> 1;
-  };
+static const uint32_t CRCTable[256] = {
+    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
+    0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
+    0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
+    0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
+    0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
+    0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
+    0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
+    0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
+    0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
+    0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
+    0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
+    0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
+    0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
+    0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
+    0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
+    0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
+    0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
+    0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
+    0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
+    0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
+    0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
+    0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
+    0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
+    0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
+    0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
+    0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
+    0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
+    0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
+    0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
+    0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
+    0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
+    0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
+    0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
+    0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
+    0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
+    0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
+    0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
+    0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
+    0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
+    0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
+    0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
+    0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
+    0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 
-  for (size_t I = 0; I < Tbl->size(); ++I) {
-    uint32_t V = Shuffle(I);
-    V = Shuffle(V);
-    V = Shuffle(V);
-    V = Shuffle(V);
-    V = Shuffle(V);
-    V = Shuffle(V);
-    V = Shuffle(V);
-    (*Tbl)[I] = Shuffle(V);
-  }
-}
-
-uint32_t llvm::crc32(uint32_t CRC, StringRef S) {
-  static llvm::once_flag InitFlag;
-  static CRC32Table Tbl;
-  llvm::call_once(InitFlag, initCRC32Table, &Tbl);
-
-  const uint8_t *P = reinterpret_cast<const uint8_t *>(S.data());
-  size_t Len = S.size();
+uint32_t llvm::crc32(uint32_t CRC, ArrayRef<uint8_t> Data) {
   CRC ^= 0xFFFFFFFFU;
-  for (; Len >= 8; Len -= 8) {
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
+  for (uint8_t Byte : Data) {
+    int TableIdx = (CRC ^ Byte) & 0xff;
+    CRC = CRCTable[TableIdx] ^ (CRC >> 8);
   }
-  while (Len--)
-    CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
   return CRC ^ 0xFFFFFFFFU;
 }
 #else
 #include <zlib.h>
-uint32_t llvm::crc32(uint32_t CRC, StringRef S) {
-  return ::crc32(CRC, (const Bytef *)S.data(), S.size());
+uint32_t llvm::crc32(uint32_t CRC, ArrayRef<uint8_t> Data) {
+  return ::crc32(CRC, (const Bytef *)Data.data(), Data.size());
 }
 #endif

llvm/lib/Support/JamCRC.cpp

-//===-- JamCRC.cpp - Cyclic Redundancy Check --------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains an implementation of JamCRC.
-//
-//===----------------------------------------------------------------------===//
-//
-// The implementation technique is the one mentioned in:
-// D. V. Sarwate. 1988. Computation of cyclic redundancy checks via table
-// look-up. Commun. ACM 31, 8 (August 1988)
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Support/JamCRC.h"
-#include "llvm/ADT/ArrayRef.h"
-
-using namespace llvm;
-
-static const uint32_t CRCTable[256] = {
-    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
-    0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
-    0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
-    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
-    0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
-    0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
-    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
-    0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
-    0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
-    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
-    0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
-    0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
-    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
-    0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
-    0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
-    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
-    0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
-    0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
-    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
-    0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
-    0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
-    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
-    0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
-    0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
-    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
-    0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
-    0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
-    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
-    0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
-    0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
-    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
-    0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
-    0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
-    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
-    0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
-    0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
-    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
-    0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
-    0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
-    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
-    0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
-    0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
-    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
-    0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
-    0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
-    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
-    0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
-    0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
-    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
-    0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
-    0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
-    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
-    0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
-    0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
-    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
-    0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
-    0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
-    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
-    0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
-    0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
-    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
-    0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
-    0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
-    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
-};
-
-void JamCRC::update(ArrayRef<char> Data) {
-  for (char Byte : Data) {
-    int TableIdx = (CRC ^ Byte) & 0xff;
-    CRC = CRCTable[TableIdx] ^ (CRC >> 8);
-  }
-}

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 };
 
 } // end anonymous namespace
 
 // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
 // value of each BB in the CFG. The higher 32 bits record the number of edges.
 template <class Edge, class BBInfo>
 void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() {
-  std::vector<char> Indexes;
+  std::vector<uint8_t> Indexes;
   JamCRC JC;
   for (auto &BB : F) {
     const Instruction *TI = BB.getTerminator();
     for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
       BasicBlock *Succ = TI->getSuccessor(I);
       auto BI = findBBInfo(Succ);
       if (BI == nullptr)
         continue;
       uint32_t Index = BI->Index;
       for (int J = 0; J < 4; J++)
-        Indexes.push_back((char)(Index >> (J * 8)));
+        Indexes.push_back((uint8_t)(Index >> (J * 8)));
     }
   }
   JC.update(Indexes);
 
   // Hash format for context sensitive profile. Reserve 4 bits for other
   // information.
   FunctionHash = (uint64_t)SIVisitor.getNumOfSelectInsts() << 56 |
                  (uint64_t)ValueSites[IPVK_IndirectCallTarget].size() << 48 |

llvm/tools/llvm-objcopy/COFF/COFFObjcopy.cpp

 #include "CopyConfig.h"
 #include "Object.h"
 #include "Reader.h"
 #include "Writer.h"
 #include "llvm-objcopy.h"
 
 #include "llvm/Object/Binary.h"
 #include "llvm/Object/COFF.h"
+#include "llvm/Support/CRC.h"
 #include "llvm/Support/Errc.h"
-#include "llvm/Support/JamCRC.h"
 #include "llvm/Support/Path.h"
 #include <cassert>
 
 namespace llvm {
 namespace objcopy {
 namespace coff {
 
 using namespace object;
 using namespace COFF;
 
 static bool isDebugSection(const Section &Sec) {
   return Sec.Name.startswith(".debug");
 }
 
 static uint64_t getNextRVA(const Object &Obj) {
   if (Obj.getSections().empty())
     return 0;
   const Section &Last = Obj.getSections().back();
   return alignTo(Last.Header.VirtualAddress + Last.Header.VirtualSize,
                  Obj.IsPE ? Obj.PeHeader.SectionAlignment : 1);
 }
 
-static uint32_t getCRC32(StringRef Data) {
-  JamCRC CRC;
-  CRC.update(ArrayRef<char>(Data.data(), Data.size()));
-  // The CRC32 value needs to be complemented because the JamCRC dosn't
-  // finalize the CRC32 value. It also dosn't negate the initial CRC32 value
-  // but it starts by default at 0xFFFFFFFF which is the complement of zero.
-  return ~CRC.getCRC();
-}
-
 static std::vector<uint8_t> createGnuDebugLinkSectionContents(StringRef File) {
   ErrorOr<std::unique_ptr<MemoryBuffer>> LinkTargetOrErr =
       MemoryBuffer::getFile(File);
   if (!LinkTargetOrErr)
     error("'" + File + "': " + LinkTargetOrErr.getError().message());
   auto LinkTarget = std::move(*LinkTargetOrErr);
-  uint32_t CRC32 = getCRC32(LinkTarget->getBuffer());
+  uint32_t CRC32 =
+      llvm::crc32(0, arrayRefFromStringRef(LinkTarget->getBuffer()));
 
   StringRef FileName = sys::path::filename(File);
   size_t CRCPos = alignTo(FileName.size() + 1, 4);
   std::vector<uint8_t> Data(CRCPos + 4);
   memcpy(Data.data(), FileName.data(), FileName.size());
   support::endian::write32le(Data.data() + CRCPos, CRC32);
   return Data;
 }

llvm/tools/llvm-objcopy/CopyConfig.cpp

 //===- CopyConfig.cpp -----------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "CopyConfig.h"
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
+#include "llvm/Support/CRC.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Errc.h"
-#include "llvm/Support/JamCRC.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/StringSaver.h"
 #include <memory>
 
 namespace llvm {
 namespace objcopy {
 
 namespace {
Expected<DriverConfig> parseObjcopyOptions(ArrayRef<const char *> ArgsArr) {
   // become invalidated and get rejected. We can avoid recalculating the
   // checksum for every target file inside an archive by precomputing the CRC
   // here. This prevents a significant amount of I/O.
   if (!Config.AddGnuDebugLink.empty()) {
     auto DebugOrErr = MemoryBuffer::getFile(Config.AddGnuDebugLink);
     if (!DebugOrErr)
       return createFileError(Config.AddGnuDebugLink, DebugOrErr.getError());
     auto Debug = std::move(*DebugOrErr);
-    JamCRC CRC;
-    CRC.update(
-        ArrayRef<char>(Debug->getBuffer().data(), Debug->getBuffer().size()));
-    // The CRC32 value needs to be complemented because the JamCRC doesn't
-    // finalize the CRC32 value.
-    Config.GnuDebugLinkCRC32 = ~CRC.getCRC();
+    Config.GnuDebugLinkCRC32 =
+        llvm::crc32(0, arrayRefFromStringRef(Debug->getBuffer()));
   }
   Config.BuildIdLinkDir = InputArgs.getLastArgValue(OBJCOPY_build_id_link_dir);
   if (InputArgs.hasArg(OBJCOPY_build_id_link_input))
     Config.BuildIdLinkInput =
         InputArgs.getLastArgValue(OBJCOPY_build_id_link_input);
   if (InputArgs.hasArg(OBJCOPY_build_id_link_output))
     Config.BuildIdLinkOutput =
         InputArgs.getLastArgValue(OBJCOPY_build_id_link_output);

llvm/unittests/Support/CRCTest.cpp

 //===- llvm/unittest/Support/CRCTest.cpp - CRC tests ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements unit tests for CRC calculation functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/CRC.h"
+#include "llvm/ADT/StringExtras.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 TEST(CRCTest, CRC32) {
   EXPECT_EQ(0x414FA339U,
-            llvm::crc32(
-                0, StringRef("The quick brown fox jumps over the lazy dog")));
+            llvm::crc32(0, arrayRefFromStringRef(
+                               "The quick brown fox jumps over the lazy dog")));
   // CRC-32/ISO-HDLC test vector
   // http://reveng.sourceforge.net/crc-catalogue/17plus.htm#crc.cat.crc-32c
-  EXPECT_EQ(0xCBF43926U, llvm::crc32(0, StringRef("123456789")));
+  EXPECT_EQ(0xCBF43926U, llvm::crc32(0, arrayRefFromStringRef("123456789")));
 }
 
 } // end anonymous namespace

llvm/utils/gn/secondary/llvm/lib/Support/BUILD.gn

sources = [
     "GlobPattern.cpp",
     "GraphWriter.cpp",
     "Hashing.cpp",
     "InitLLVM.cpp",
     "IntEqClasses.cpp",
     "IntervalMap.cpp",
     "ItaniumManglingCanonicalizer.cpp",
     "JSON.cpp",
-    "JamCRC.cpp",
     "KnownBits.cpp",
     "LEB128.cpp",
     "LineIterator.cpp",
     "Locale.cpp",
     "LockFileManager.cpp",
     "LowLevelType.cpp",
     "MD5.cpp",
     "ManagedStatic.cpp",