lib/Support/CRC.cpp

   1 //===--- CRC.cpp - Cyclic Redundancy Check implementation -----------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements llvm::crc32 function.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Support/CRC.h"
  14 #include "llvm/Config/config.h"
  15 #include "llvm/ADT/StringRef.h"
  16 #include "llvm/Support/Threading.h"
  17 #include <array>
  18
  19 using namespace llvm;
  20
  21 #if LLVM_ENABLE_ZLIB == 0 || !HAVE_ZLIB_H
  22 using CRC32Table = std::array<uint32_t, 256>;
  23
  24 static void initCRC32Table(CRC32Table *Tbl) {
  25   auto Shuffle = [](uint32_t V) {
  26     return (V & 1) ? (V >> 1) ^ 0xEDB88320U : V >> 1;
  27   };
  28
  29   for (size_t I = 0; I < Tbl->size(); ++I) {
  30     uint32_t V = Shuffle(I);
  31     V = Shuffle(V);
  32     V = Shuffle(V);
  33     V = Shuffle(V);
  34     V = Shuffle(V);
  35     V = Shuffle(V);
  36     V = Shuffle(V);
  37     (*Tbl)[I] = Shuffle(V);
  38   }
  39 }
  40
  41 uint32_t llvm::crc32(uint32_t CRC, StringRef S) {
  42   static llvm::once_flag InitFlag;
  43   static CRC32Table Tbl;
  44   llvm::call_once(InitFlag, initCRC32Table, &Tbl);
  45
  46   const uint8_t *P = reinterpret_cast<const uint8_t *>(S.data());
  47   size_t Len = S.size();
  48   CRC ^= 0xFFFFFFFFU;
  49   for (; Len >= 8; Len -= 8) {
  50     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  51     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  52     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  53     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  54     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  55     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  56     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  57     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  58   }
  59   while (Len--)
  60     CRC = Tbl[(CRC ^ *P++) & 0xFF] ^ (CRC >> 8);
  61   return CRC ^ 0xFFFFFFFFU;
  62 }
  63 #else
  64 #include <zlib.h>
  65 uint32_t llvm::crc32(uint32_t CRC, StringRef S) {
  66   return ::crc32(CRC, (const Bytef *)S.data(), S.size());
  67 }
  68 #endif