使用长整型（64位）进行CRC校验和

Question

我已经检查了不同的CRC64实现。例如，这个、这个和这个。所有这些实现的问题是它们使用字节处理数据。然而，在64位系统上，我希望使用long（8字节）来处理数据。这样，我需要迭代的次数就会更少。例如，对于128字节的数据，使用一个byte，我需要迭代128次，而使用long，我只需要迭代16次。

是否有任何使用long甚至比字节更大的字长的CRC64实现？这些方案能够修改以实现这一点吗？

- pythonic

---

如果SSE可用，GCC很可能会展开您的循环甚至在可能的情况下使用128位XMM寄存器。因此，在您盲目优化代码之前，请检查您的编译器正在做什么。 - user405725

是的，但计算是循环的，我认为无法进行向量化处理。 - pythonic

在试图比编译器更聪明之前，请检查它的智能程度。GCC执行许多循环分析，其中一些我确定你从未听说过。它可以（实际上，在某些情况下确实会）甚至对于循环计算进行展开。我不是说它在你的情况下这样做，但你必须在进行自己的优化之前进行检查。 - user405725

过早地进行优化是带来大量麻烦的根源。请确保您真正需要更高的性能，并且现有的性能已经达到最优，然后再考虑进行优化。 - Perry

Answer 1

CRC校验使用了一种技巧，避免需要逐位处理数据：它使用了一个查找表，使其可以同时处理多个比特位。

同时处理n个比特位需要一个大小为2^n的查找表。你提供的实现每次读取1字节（8位），因此它们都使用了大小为256 == 2^8的查找表。

要同时处理64位，则需要使用大小为2^64的查找表，这是不可行的。这就是为什么常见的CRC实现每次只处理1字节的原因。

虽然使用一个65536项的数组可以同时处理2字节，但由于使用更多的CPU高速缓存内存，这很可能会产生负面的性能影响。

- interjay

---

顺便问一下，你知道查找表在硬件实现中是否也被使用吗？ - user405725

@Vlad 我不太了解硬件实现。 - interjay

@VladLazarenko：有一些硬件实现与串行通信相连，以与波特率相同的速度运行，逐位处理每个位，因此不需要查找表。 - quamrana