使用 C++14 constexpr 模板在编译期生成 CRC 表

LH_Mouse

关于 CRC 的算法优化可以看这个： http://www.relisoft.com/science/CrcOptim.html

原文提供的是正序（权较大位向权较小位方向）的 CRC 计算，而这里使用的是反序（权较小位向权较大位方向）。
原文的 CRC 余数的初始值是 0；此处以 -1 为初始值，计算完成后进行按位反。

为了优化 CRC 算法我们需要对问题中使用的 CRC 余数生成一个静态表，这个表有 256 个元素，对应每个八元组所有可能的值。

一个朴素的算法如下：

1. // g++ crc32.cpp -std=c++14 -masm=intel
   
2. #include <array>
   
3. #include <type_traits>
   
4. #include <utility>
   
5. #include <cstdint>
   
6. #include <cstddef>
   
7. 
   
8. namespace crc32 {
   
9. 
   
10. namespace impl {
    
11.     std::array<std::uint32_t, 256> create_table(std::uint32_t divisor) noexcept {
    
12.         std::array<std::uint32_t, 256> table;
    
13.         for(std::uint32_t i = 0; i < 256; ++i){
    
14.             auto reg = i;
    
15.             for(unsigned j = 0; j < 8; ++j){
    
16.                 const bool lsb = reg & 1;  // ①
    
17.                 reg >>= 1;         // ②
    
18.                 if(lsb){
    
19.                     reg ^= divisor;
    
20.                 }
    
21.             }
    
22.             table[i] = reg;
    
23.         }
    
24.         return table;
    
25.     }
    
26.    
    
27.     // 按照 IEEE 802.3 描述的算法，除数为 0xEDB88320。
    
28.     const auto table = create_table(0xEDB88320);
    
29. }
    
30. 
    
31. std::uint32_t get(const void *data, std::size_t size) noexcept {
    
32.     auto reg = static_cast<std::uint32_t>(-1);
    
33.     for(std::size_t i = 0; i < size; ++i){
    
34.         const unsigned by = static_cast<const std::uint8_t *>(data)[i];
    
35.         reg = impl::table[(reg ^ by) & 0xFF] ^ (reg >> 8);
    
36.     }
    
37.     return ~reg;
    
38. }
    
39. 
    
40. }
    
41. 
    
42. #include <cstdio>
    
43. 
    
44. int main(){
    
45.     constexpr char s[] = "hello world!";
    
46.     std::printf("crc32(%s) = %08lX\n", s, (unsigned long)crc32::get(s, sizeof(s) - 1));
    
47. }
    

复制代码

在以上的算法中我们注意到一个问题：在 ① 处判定 reg 的 least significant bit 之后我们在 ② 处立即进行了移位操作。
如果你有一些 x86 的汇编基础，应该会记得在 x86 上移位指令将移出的位直接移入 CF。因此我们可以在这里使用汇编书写，结果甚至比用 C++ 更短：

1. // 命名空间 impl 以外的内容无改动，此处略。
   
2. // g++ crc32.cpp -std=c++14 -masm=intel
   
3. namespace impl {
   
4.     std::array<std::uint32_t, 256> create_table(std::uint32_t divisor) noexcept {
   
5.         std::array<std::uint32_t, 256> table;
   
6.         for(std::uint32_t i = 0; i < 256; ++i){
   
7.             auto reg = i;
   
8.             for(unsigned j = 0; j < 8; ++j){
   
9.                 __asm__(
   
10.                     "shr %0, 1 \n"
    
11.                     "sbb eax, eax \n"
    
12.                     "and eax, %1 \n"
    
13.                     "xor %0, eax \n"
    
14.                     : "+r"(reg) : "r"(divisor) : "ax"
    
15.                 );
    
16.             }
    
17.             table[i] = reg;
    
18.         }
    
19.         return table;
    
20.     }
    
21.    
    
22.     // 按照 IEEE 802.3 描述的算法，除数为 0xEDB88320。
    
23.     const auto table = create_table(0xEDB88320);
    
24. }
    

复制代码

然而在多数用例中，我们只追求 CRC 算法的效率和确定性，而对其具体的除数并不关心。
需要指出的是，通常说的 CRC32 正是上面 IEEE 802.3 描述的算法，即“位反-CRC-位反”的变换，其除数为 0xEDB88320。

为了在此情况下免去动态生成 CRC 表的过程，我们可以预先算好一张表并保存下来。然而这样做可维护性太差了。相反，我们可以使用 C++14 的模板在编译期生成这样的一张表。

上面生成表的过程是对一个数组遍历并填充的过程，而其中每个元素的值都仅仅和除数与其下标有关，与其他元素无关。

首先，我们定义一个（数学上的）函数，该函数使用除数和下标生成一个元素。这个函数应当与上面的内层循环具有等价的形式。
因此该模板应当递归调用自身 8 次，并（以某种形式）返回一个值。这个递归可以很容易地用类模板的偏特化加以终止：

1. namespace impl {
   
2.     // 按照 IEEE 802.3 描述的算法，除数为 0xEDB88320。
   
3.     template<unsigned round, std::uint32_t reg>
   
4.     struct generator {
   
5.         static constexpr std::uint32_t value = generator<round + 1, (reg >> 1) ^ ((reg & 1) ? 0xEDB88320 : 0)>::value;
   
6.     };
   
7.     template<std::uint32_t reg>
   
8.     struct generator<8, reg> {
   
9.         static constexpr std::uint32_t value = reg;
   
10.     };
    
11. }
    

复制代码

这样对于一个下标为 index 的元素，其值为 generator<0, index>::value。

然后，我们在编译期创建一个大小为 256 的数组，该数组中的每一项都是使用上述模板生成的。
于是问题演变为，如何在编译期生成一个 0, 1, 2, ..., 255 的序列，并对每一项加以变换。

生成整数序列可以使用 std::make_index_sequence 实现，而对每一项加以变换则可以推导其模板参数并展开。

于是这里就存在两种解法：

① 使用函数模板推导的解法：

1. namespace impl {
   
2.     template<std::size_t ...indices>
   
3.     constexpr std::array<std::uint32_t, sizeof...(indices)> generate(std::index_sequence<indices...>) noexcept {
   
4.         return { generator<0, indices>::value... };
   
5.     }
   
6. 
   
7.     constexpr auto table = generate(std::make_index_sequence<256>());
   
8. }
   

复制代码

② 使用类模板偏特化推导的解法：

1. namespace impl {
   
2.     template<typename sequence>
   
3.     struct generated_table;
   
4. 
   
5.     template<std::size_t ...indices>
   
6.     struct generated_table<std::index_sequence<indices...>> {
   
7.         std::array<std::uint32_t, sizeof...(indices)> a = {{ generator<0, indices>::value... }};
   
8.     };
   
9. 
   
10.     constexpr auto table = generated_table<decltype(std::make_index_sequence<256>())>{ }.a;
    
11. }
    

复制代码

完整的使用函数模板的解法可以参见附件。

卖个萌 ><。

nadesico19

前排膜拜编译期

iyzsong

写个单独的程序输出个数组不好么
不要打我

妹妹的胖次

iyzsong 发表于 2016-1-22 12:10
写个单独的程序输出个数组不好么
不要打我

说的很有道理啊（

LYP

前排支持大猫

岩川黑鬼

iyzsong 发表于 2016-1-22 12:10
写个单独的程序输出个数组不好么
不要打我

理由在文章里讲过了。
能自启动的东西不是更好看些么？

moecmks

AT&T格式内嵌汇编的语法/局部寻址/没有naked关键字一直让我很纠结，话说for 循环变量在没有引用的情况下削减至0比较有优势吧·~

LH_Mouse

moecmks 发表于 2016-1-23 14:56
AT&T格式内嵌汇编的语法/局部寻址/没有naked关键字一直让我很纠结，话说for 循环变量在没有引用的情况下削 ...

编译的时候指定 -masm=intel 就可以用 intel 语法了。