[Support] Implement zlib independent crc32 computation

[evgeny777]

Summary

The .gnu_debuglink section contains CRC32 checksum of debug information file. When LLVM is compiled without zlib support this checksum is completely ignored, which is error prone. This patch implements simple CRC32 calculation algorithm.

[lebedev.ri]

include/llvm/Support/CRC.h

22 ↗

(On Diff #192260)

I'm not sure if oss-fuzz builds llvm with zlib or not, but if it does,
this is a *great* fuzzing target, to cross-check with the zlib output.

[grimar]

lib/DebugInfo/Symbolize/Symbolize.cpp

167 ↗

(On Diff #192260)

What about always using non-zlib implementation?

[evgeny777]

include/llvm/Support/CRC.h

22 ↗

(On Diff #192260)

LLVM_ENABLE_ZLIB is ON by default, so whether LLVM is built with zlib support or not depends on HAVE_ZLIB_H.
Are you suggesting something like llvm-crc32-fuzzer?

lib/DebugInfo/Symbolize/Symbolize.cpp

167 ↗

(On Diff #192260)

zlib implementation is most likely faster, especially with -DBYFOUR. Also somebody may be using llvm::zlib::crc32

[lebedev.ri]

include/llvm/Support/CRC.h

22 ↗

(On Diff #192260)

I guess this is a question of naming. I'd say:
llvm-crc32-fuzzer would be one to simply run this code only.
llvm-llvmcrc32-vs-zlibcrc32-fuzzer would run this code, the equivalent zlib code, and assert that they returned the same.

[joerg]

I'd recomment copying the version from libarchive (https://github.com/libarchive/libarchive/blob/master/libarchive/archive_crc32.h):

• don't bother with the 1KB table in both binary and source, just recompute it on the first use.
• at least in the past unrolling the inner loop somewhat helped a lot

I wouldn't really fuzz test this, just build a set of test vector and be done.

[evgeny777]

don't bother with the 1KB table in both binary and source, just recompute it on the first use

Is single threaded usage guaranteed?

[mgorny]

Is there really any good case to build LLVM without zlib? Maybe it'd be better to just require zlib unconditionally (or mark building it really unsupported) rather than bundling extra algorithms that will be used only conditionally (until someone mistakenly uses it unconditionally, and LLVM would start using different CRC32 impls in different places) like this.

[grimar]

In D59816#1442964, @mgorny wrote:

Is there really any good case to build LLVM without zlib?

ZLib is still unavailable for windows builds afaik.

[joerg]

In D59816#1442909, @evgeny777 wrote:

don't bother with the 1KB table in both binary and source, just recompute it on the first use

Is single threaded usage guaranteed?

It doesn't matter, at most a single memory fence is necessary.

[aprantl]

lib/Support/CMakeLists.txt

78 ↗

(On Diff #192260)

Shouldn't this be only conditionally compiled if zlib isn't available? It seems wrong to have the lookup table twice.

[evgeny777]

It doesn't matter, at most a single memory fence is necessary.

Yep. However, you don't have it in your code. The volatile int crc_tbl_inited prevents compiler optimizations but doesn't prevent out-of-order execution as far as I know.

[evgeny777]

@aprantl

Shouldn't this be only conditionally compiled if zlib isn't available?

How about putting the call to zlib::crc32 inside getCRC32 and using getCRC32 from Symbolize.cpp and other places?

[evgeny777]

New implementation taken from libarchive (dynamic crc table)

[joerg]

lib/Support/CRC.cpp

21 ↗

(On Diff #192423)

A reference in the commit message is good enough.

23 ↗

(On Diff #192423)

You can just use llvm::call_once for the init.

27 ↗

(On Diff #192423)

I'd prefer to add the U for the constant here and below as they don't fit into the normal integer range.

44 ↗

(On Diff #192423)

uint8_t or at least unsigned char would still be better here.

[evgeny777]

Addressed review comments

[aprantl]

I still feel this code should be in an #ifndef HAVE_ZLIB with the #else branch forwarding the call into zlib.

[evgeny777]

Addressed comments

[aprantl]

include/llvm/Support/CRC.h

21 ↗

(On Diff #193854)

///

[aprantl]

include/llvm/Support/CRC.h

22 ↗

(On Diff #193854)

Why not just call this llvm::crc32()?

llvm/trunk/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 {
+/// zlib independent CRC32 calculation.
+uint32_t crc32(uint32_t CRC, StringRef S);
+} // end namespace llvm
+
+#endif

llvm/trunk/lib/DebugInfo/Symbolize/Symbolize.cpp

 #include "llvm/BinaryFormat/COFF.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/PDB/PDB.h"
 #include "llvm/DebugInfo/PDB/PDBContext.h"
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Object/MachO.h"
 #include "llvm/Object/MachOUniversal.h"
+#include "llvm/Support/CRC.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
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 !zlib::isAvailable() || CRCHash == zlib::crc32(MB.get()->getBuffer());
+  return CRCHash == crc32(0, 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/trunk/lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   BuryPointer.cpp
   CachePruning.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
   CodeGenCoverage.cpp
   CommandLine.cpp
   Compression.cpp
+  CRC.cpp
   ConvertUTF.cpp
   ConvertUTFWrapper.cpp
   CrashRecoveryContext.cpp
   DataExtractor.cpp
   Debug.cpp
   DebugCounter.cpp
   DeltaAlgorithm.cpp
   DAGDeltaAlgorithm.cpp

llvm/trunk/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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/CRC.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;
+  };
+
+  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();
+  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);
+  }
+  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());
+}
+#endif

llvm/trunk/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   CachePruningTest.cpp
   CrashRecoveryTest.cpp
   Casting.cpp
   CheckedArithmeticTest.cpp
   Chrono.cpp
   CommandLineTest.cpp
   CompressionTest.cpp
   ConvertUTFTest.cpp
+  CRCTest.cpp
   DataExtractorTest.cpp
   DebugTest.cpp
   DebugCounterTest.cpp
   DJBTest.cpp
   EndianStreamTest.cpp
   EndianTest.cpp
   ErrnoTest.cpp
   ErrorOrTest.cpp

llvm/trunk/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 "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")));
+  // 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")));
+}
+
+} // end anonymous namespace