1
// Copyright (c) 2017-2025 Cloudflare, Inc.
2
// Licensed under the Apache 2.0 license found in the LICENSE file or at:
3
//     https://opensource.org/licenses/Apache-2.0
4
 
5
#include "crc-impl.h"
6
 
7
#include <array>
8
#include <type_traits>
9
 
10
namespace {
11
constexpr auto crcTableSize = 256;
12
 
13
template <typename T>
14
concept Uint64OrUint32 = std::unsigned_integral<T> && (sizeof(T) == 8 || sizeof(T) == 4);
15
 
16
template <Uint64OrUint32 T>
17
constexpr T reverse(T value) {
18
  if constexpr (sizeof(T) == 4) {
19
    value = ((value & 0xaaaaaaaa) >> 1) | ((value & 0x55555555) << 1);
20
    value = ((value & 0xcccccccc) >> 2) | ((value & 0x33333333) << 2);
21
    value = ((value & 0xf0f0f0f0) >> 4) | ((value & 0x0f0f0f0f) << 4);
22
    value = ((value & 0xff00ff00) >> 8) | ((value & 0x00ff00ff) << 8);
23
    value = (value >> 16) | (value << 16);
24
    return value;
25
  } else {
26
    value = ((value & 0xaaaaaaaaaaaaaaaa) >> 1) | ((value & 0x5555555555555555) << 1);
27
    value = ((value & 0xcccccccccccccccc) >> 2) | ((value & 0x3333333333333333) << 2);
28
    value = ((value & 0xf0f0f0f0f0f0f0f0) >> 4) | ((value & 0x0f0f0f0f0f0f0f0f) << 4);
29
    value = ((value & 0xff00ff00ff00ff00) >> 8) | ((value & 0x00ff00ff00ff00ff) << 8);
30
    value = ((value & 0xffff0000ffff0000) >> 16) | ((value & 0x0000ffff0000ffff) << 16);
31
    value = (value >> 32) | (value << 32);
32
    return value;
33
  }
34
}
35
 
36
template <Uint64OrUint32 T>
37
// NOLINTNEXTLINE(edgeworker-multiple-bool-args)
38
constexpr std::array<T, crcTableSize> gen_crc_table(T polynomial, bool reflectIn, bool reflectOut) {
39
  constexpr auto numIterations = sizeof(polynomial) * 8;  // number of bits in polynomial
40
  auto crcTable = std::array<T, crcTableSize>{};
41
 
42
  for (T byte = 0u; byte < crcTableSize; ++byte) {
43
    T crc = (reflectIn ? (reverse(T(byte)) >> (numIterations - 8)) : byte);
44
 
45
    for (int i = 0; i < numIterations; ++i) {
46
      if (crc & (static_cast<T>(1) << (numIterations - 1))) {
47
        crc = (crc << 1) ^ polynomial;
48
      } else {
49
        crc <<= 1;
50
      }
51
    }
52
 
53
    crcTable[byte] = (reflectOut ? reverse(crc) : crc);
54
  }
55
 
56
  return crcTable;
57
}
58
 
59
#if !(__CRC32__ || __ARM_FEATURE_CRC32)
60
// https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-32-iscsi
61
constexpr auto crc32c_table = gen_crc_table(static_cast<uint32_t>(0x1edc6f41), true, true);
62
#endif
63
// https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat.crc-64-nvme
64
constexpr auto crc64nvme_table =
65
    gen_crc_table(static_cast<uint64_t>(0xad93d23594c93659), true, true);
66
}  // namespace
67
 
68
uint32_t crc32c(uint32_t crc, const uint8_t *data, unsigned int length) {
69
  if (data == nullptr) {
70
    return 0;
71
  }
72
  crc ^= 0xffffffff;
73
#if __CRC32__ || __ARM_FEATURE_CRC32
74
  // Using hardware acceleration, process data in 8-byte chunks. Any remaining bytes are processed
75
  // one-by-one in the main loop.
76
  while (length >= 8) {
77
    // 8-byte unaligned read
78
    uint64_t val = *reinterpret_cast<const uint64_t *>(data);
79
#if __ARM_FEATURE_CRC32
80
    crc = __builtin_arm_crc32cd(crc, val);
81
#else
82
    crc = __builtin_ia32_crc32di(crc, val);
83
#endif
84
    length -= 8;
85
    data += 8;
86
  }
87
#endif
88
 
89
  while (length--) {
90
#if __ARM_FEATURE_CRC32
91
    crc = __builtin_arm_crc32cb(crc, *data++);
92
#elif __CRC32__
93
    crc = __builtin_ia32_crc32qi(crc, *data++);
94
#else
95
    crc = crc32c_table[(crc ^ *data++) & 0xffL] ^ (crc >> 8);
96
#endif
97
  }
98
  return crc ^ 0xffffffff;
99
}
100
 
101
uint64_t crc64nvme(uint64_t crc, const uint8_t *data, unsigned int length) {
102
  if (data == nullptr) {
103
    return 0;
104
  }
105
  crc ^= 0xffffffffffffffff;
106
  while (length--) {
107
    crc = crc64nvme_table[(crc ^ *data++) & 0xffL] ^ (crc >> 8);
108
  }
109
  return crc ^ 0xffffffffffffffff;
110
}