设为首页收藏本站

ISO/IEC C++ China Unofficial

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 862|回复: 8

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

[复制链接]

10

主题

108

帖子

465

积分

超级版主

RA2DIY 特别行政区行政长官

Rank: 8Rank: 8

威望
4
经验
346
贡献
3
发表于 2016-1-22 11:04:30 | 显示全部楼层 |阅读模式
本帖最后由 LH_Mouse 于 2016-1-22 15:31 编辑

关于 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. namespace crc32 {

  8. namespace impl {
  9.     std::array<std::uint32_t, 256> create_table(std::uint32_t divisor) noexcept {
  10.         std::array<std::uint32_t, 256> table;
  11.         for(std::uint32_t i = 0; i < 256; ++i){
  12.             auto reg = i;
  13.             for(unsigned j = 0; j < 8; ++j){
  14.                 const bool lsb = reg & 1;  // ①
  15.                 reg >>= 1;         // ②
  16.                 if(lsb){
  17.                     reg ^= divisor;
  18.                 }
  19.             }
  20.             table[i] = reg;
  21.         }
  22.         return table;
  23.     }
  24.    
  25.     // 按照 IEEE 802.3 描述的算法,除数为 0xEDB88320。
  26.     const auto table = create_table(0xEDB88320);
  27. }

  28. std::uint32_t get(const void *data, std::size_t size) noexcept {
  29.     auto reg = static_cast<std::uint32_t>(-1);
  30.     for(std::size_t i = 0; i < size; ++i){
  31.         const unsigned by = static_cast<const std::uint8_t *>(data)[i];
  32.         reg = impl::table[(reg ^ by) & 0xFF] ^ (reg >> 8);
  33.     }
  34.     return ~reg;
  35. }

  36. }

  37. #include <cstdio>

  38. int main(){
  39.     constexpr char s[] = "hello world!";
  40.     std::printf("crc32(%s) = %08lX\n", s, (unsigned long)crc32::get(s, sizeof(s) - 1));
  41. }
复制代码


在以上的算法中我们注意到一个问题:在 ① 处判定 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.     constexpr auto table = generate(std::make_index_sequence<256>());
  7. }
复制代码


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

  1. namespace impl {
  2.     template<typename sequence>
  3.     struct generated_table;

  4.     template<std::size_t ...indices>
  5.     struct generated_table<std::index_sequence<indices...>> {
  6.         std::array<std::uint32_t, sizeof...(indices)> a = {{ generator<0, indices>::value... }};
  7.     };

  8.     constexpr auto table = generated_table<decltype(std::make_index_sequence<256>())>{ }.a;
  9. }
复制代码


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

卖个萌 ><。


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

评分

参与人数 1威望 +3 贡献 +3 收起 理由
岩川黑鬼 + 3 + 3 看着帅。

查看全部评分

We will prevail!! www.lhmouse.com
回复

使用道具 举报

8

主题

64

帖子

269

积分

超级版主

Rank: 8Rank: 8

威望
12
经验
169
贡献
12
发表于 2016-1-22 11:26:50 | 显示全部楼层
前排膜拜编译期
回复 支持 反对

使用道具 举报

1

主题

16

帖子

142

积分

注册会员

Rank: 2

威望
0
经验
126
贡献
0
发表于 2016-1-22 12:10:10 | 显示全部楼层
写个单独的程序输出个数组不好么
不要打我
回复 支持 反对

使用道具 举报

0

主题

2

帖子

33

积分

新手上路

Rank: 1

威望
0
经验
31
贡献
0
发表于 2016-1-22 13:00:23 | 显示全部楼层
iyzsong 发表于 2016-1-22 12:10
写个单独的程序输出个数组不好么
不要打我

说的很有道理啊(
肥希肥希肥~
回复 支持 反对

使用道具 举报

0

主题

10

帖子

45

积分

新手上路

Rank: 1

威望
1
经验
32
贡献
1
发表于 2016-1-22 21:07:25 | 显示全部楼层
前排支持大猫
回复 支持 反对

使用道具 举报

3

主题

20

帖子

202

积分

超级版主

mikonmikonmi

Rank: 8Rank: 8

威望
4
经验
170
贡献
4
发表于 2016-1-23 14:13:37 | 显示全部楼层
iyzsong 发表于 2016-1-22 12:10
写个单独的程序输出个数组不好么
不要打我

理由在文章里讲过了。
能自启动的东西不是更好看些么?
沿海征收头GAY骨
回复 支持 反对

使用道具 举报

3

主题

74

帖子

283

积分

中级会员

Rank: 3Rank: 3

威望
9
经验
182
贡献
9
发表于 2016-1-23 14:56:09 | 显示全部楼层
AT&T格式内嵌汇编的语法/局部寻址/没有naked关键字一直让我很纠结,话说for 循环变量在没有引用的情况下削减至0比较有优势吧·~
#if !idppc
/*
** float q_rsqrt( float number )
*/
float Q_rsqrt( float number )
{
        long i;
        float x2
回复 支持 反对

使用道具 举报

10

主题

108

帖子

465

积分

超级版主

RA2DIY 特别行政区行政长官

Rank: 8Rank: 8

威望
4
经验
346
贡献
3
 楼主| 发表于 2016-1-23 18:43:16 | 显示全部楼层
moecmks 发表于 2016-1-23 14:56
AT&T格式内嵌汇编的语法/局部寻址/没有naked关键字一直让我很纠结,话说for 循环变量在没有引用的情况下削 ...

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

点评

谢谢0v0  发表于 2016-1-25 10:56
We will prevail!! www.lhmouse.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|ISO/IEC C++ China Unofficial    

GMT+8, 2017-8-19 07:46 , Processed in 0.062335 second(s), 30 queries , Xcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表