超级版主
RA2DIY 特别行政区行政长官
 
- 威望
- 4
- 经验
- 486
- 贡献
- 3
|
本帖最后由 LH_Mouse 于 2016-1-22 15:31 编辑
关于 CRC 的算法优化可以看这个: http://www.relisoft.com/science/CrcOptim.html
原文提供的是正序(权较大位向权较小位方向)的 CRC 计算,而这里使用的是反序(权较小位向权较大位方向)。
原文的 CRC 余数的初始值是 0;此处以 -1 为初始值,计算完成后进行按位反。
为了优化 CRC 算法我们需要对问题中使用的 CRC 余数生成一个静态表,这个表有 256 个元素,对应每个八元组所有可能的值。
一个朴素的算法如下:
- // g++ crc32.cpp -std=c++14 -masm=intel
- #include <array>
- #include <type_traits>
- #include <utility>
- #include <cstdint>
- #include <cstddef>
- namespace crc32 {
- namespace impl {
- std::array<std::uint32_t, 256> create_table(std::uint32_t divisor) noexcept {
- std::array<std::uint32_t, 256> table;
- for(std::uint32_t i = 0; i < 256; ++i){
- auto reg = i;
- for(unsigned j = 0; j < 8; ++j){
- const bool lsb = reg & 1; // ①
- reg >>= 1; // ②
- if(lsb){
- reg ^= divisor;
- }
- }
- table[i] = reg;
- }
- return table;
- }
-
- // 按照 IEEE 802.3 描述的算法,除数为 0xEDB88320。
- const auto table = create_table(0xEDB88320);
- }
- std::uint32_t get(const void *data, std::size_t size) noexcept {
- auto reg = static_cast<std::uint32_t>(-1);
- for(std::size_t i = 0; i < size; ++i){
- const unsigned by = static_cast<const std::uint8_t *>(data)[i];
- reg = impl::table[(reg ^ by) & 0xFF] ^ (reg >> 8);
- }
- return ~reg;
- }
- }
- #include <cstdio>
- int main(){
- constexpr char s[] = "hello world!";
- std::printf("crc32(%s) = %08lX\n", s, (unsigned long)crc32::get(s, sizeof(s) - 1));
- }
复制代码
在以上的算法中我们注意到一个问题:在 ① 处判定 reg 的 least significant bit 之后我们在 ② 处立即进行了移位操作。
如果你有一些 x86 的汇编基础,应该会记得在 x86 上移位指令将移出的位直接移入 CF。因此我们可以在这里使用汇编书写,结果甚至比用 C++ 更短:
- // 命名空间 impl 以外的内容无改动,此处略。
- // g++ crc32.cpp -std=c++14 -masm=intel
- namespace impl {
- std::array<std::uint32_t, 256> create_table(std::uint32_t divisor) noexcept {
- std::array<std::uint32_t, 256> table;
- for(std::uint32_t i = 0; i < 256; ++i){
- auto reg = i;
- for(unsigned j = 0; j < 8; ++j){
- __asm__(
- "shr %0, 1 \n"
- "sbb eax, eax \n"
- "and eax, %1 \n"
- "xor %0, eax \n"
- : "+r"(reg) : "r"(divisor) : "ax"
- );
- }
- table[i] = reg;
- }
- return table;
- }
-
- // 按照 IEEE 802.3 描述的算法,除数为 0xEDB88320。
- const auto table = create_table(0xEDB88320);
- }
复制代码
然而在多数用例中,我们只追求 CRC 算法的效率和确定性,而对其具体的除数并不关心。
需要指出的是,通常说的 CRC32 正是上面 IEEE 802.3 描述的算法,即“位反-CRC-位反”的变换,其除数为 0xEDB88320。
为了在此情况下免去动态生成 CRC 表的过程,我们可以预先算好一张表并保存下来。然而这样做可维护性太差了。相反,我们可以使用 C++14 的模板在编译期生成这样的一张表。
上面生成表的过程是对一个数组遍历并填充的过程,而其中每个元素的值都仅仅和除数与其下标有关,与其他元素无关。
首先,我们定义一个(数学上的)函数,该函数使用除数和下标生成一个元素。这个函数应当与上面的内层循环具有等价的形式。
因此该模板应当递归调用自身 8 次,并(以某种形式)返回一个值。这个递归可以很容易地用类模板的偏特化加以终止:
- namespace impl {
- // 按照 IEEE 802.3 描述的算法,除数为 0xEDB88320。
- template<unsigned round, std::uint32_t reg>
- struct generator {
- static constexpr std::uint32_t value = generator<round + 1, (reg >> 1) ^ ((reg & 1) ? 0xEDB88320 : 0)>::value;
- };
- template<std::uint32_t reg>
- struct generator<8, reg> {
- static constexpr std::uint32_t value = reg;
- };
- }
复制代码
这样对于一个下标为 index 的元素,其值为 generator<0, index>::value。
然后,我们在编译期创建一个大小为 256 的数组,该数组中的每一项都是使用上述模板生成的。
于是问题演变为,如何在编译期生成一个 0, 1, 2, ..., 255 的序列,并对每一项加以变换。
生成整数序列可以使用 std::make_index_sequence 实现,而对每一项加以变换则可以推导其模板参数并展开。
于是这里就存在两种解法:
① 使用函数模板推导的解法:
- namespace impl {
- template<std::size_t ...indices>
- constexpr std::array<std::uint32_t, sizeof...(indices)> generate(std::index_sequence<indices...>) noexcept {
- return { generator<0, indices>::value... };
- }
- constexpr auto table = generate(std::make_index_sequence<256>());
- }
复制代码
② 使用类模板偏特化推导的解法:
- namespace impl {
- template<typename sequence>
- struct generated_table;
- template<std::size_t ...indices>
- struct generated_table<std::index_sequence<indices...>> {
- std::array<std::uint32_t, sizeof...(indices)> a = {{ generator<0, indices>::value... }};
- };
- constexpr auto table = generated_table<decltype(std::make_index_sequence<256>())>{ }.a;
- }
复制代码
完整的使用函数模板的解法可以参见附件。
卖个萌 ><。
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
评分
-
查看全部评分
|