CRC原理
基本概念
CRC(Cyclic Redundancy Check)中文名是循环冗余校验,其计算简单,被广泛应用于数据校验,具有很强的检错能力。
数学原理
CRC算法是已GF(2)多项式为数学基础的,这个不是很难理解,说白了其实就是在玩异或运算。这篇博文对其中的数学讲的很通俗易懂,推荐大家可以参考下。
源码实现
leveldb
中对于crc32实现还是非常简单的,核心在于一个Extend()
函数。
uint32_t Extend(uint32_t crc, const char* buf, size_t size) {
const uint8_t *p = reinterpret_cast<const uint8_t *>(buf);
const uint8_t *e = p + size;
uint32_t l = crc ^ 0xffffffffu;
#define STEP1 do { \
int c = (l & 0xff) ^ *p++; \
l = table0_[c] ^ (l >> 8); \
} while (0)
#define STEP4 do { \
uint32_t c = l ^ LE_LOAD32(p); \
p += 4; \
l = table3_[c & 0xff] ^ \
table2_[(c >> 8) & 0xff] ^ \
table1_[(c >> 16) & 0xff] ^ \
table0_[c >> 24]; \
} while (0)
// Point x at first 4-byte aligned byte in string. This might be
// just past the end of the string.
const uintptr_t pval = reinterpret_cast<uintptr_t>(p);
const uint8_t* x = reinterpret_cast<const uint8_t*>(((pval + 3) >> 2) << 2);
if (x <= e) {
// Process bytes until finished or p is 4-byte aligned
while (p != x) {
STEP1;
}
}
// Process bytes 16 at a time
while ((e-p) >= 16) {
STEP4; STEP4; STEP4; STEP4;
}
// Process bytes 4 at a time
while ((e-p) >= 4) {
STEP4;
}
// Process the last few bytes
while (p != e) {
STEP1;
}
#undef STEP4
#undef STEP1
return l ^ 0xffffffffu;
}
实现的比较简洁,关键处也有代码注释,如果你明白了CRC的原理,相信读懂这份代码应该没有什么困难。细读这份代码时还是学习了一个新技巧
#define STEP1 do { \
int c = (l & 0xff) ^ *p++; \
l = table0_[c] ^ (l >> 8); \
} while (0)
#define STEP4 do { \
uint32_t c = l ^ LE_LOAD32(p); \
p += 4; \
l = table3_[c & 0xff] ^ \
table2_[(c >> 8) & 0xff] ^ \
table1_[(c >> 16) & 0xff] ^ \
table0_[c >> 24]; \
} while (0)
在宏定义的时候为何给他套上一个do{...}while(0)
,刚开始非常疑惑,这层嵌套的价值在何处,按理来说在这份代码中,将这种宏定义直接改成这样就行
#define STEP1 int c = (l & 0xff) ^ *p++; \
l = table0_[c] ^ (l >> 8) \
#define STEP4 uint32_t c = l ^ LE_LOAD32(p); \
p += 4; \
l = table3_[c & 0xff] ^ \
table2_[(c >> 8) & 0xff] ^ \
table1_[(c >> 16) & 0xff] ^ \
table0_[c >> 24] \
的确这样可以(针对crc32c.cc
)中而言。
但是考虑这样的宏定义在下面这种情况的结果
#define FOO(x) foo(x); bar(x)
if (condition)
FOO(x);
else // syntax error here
...;
即便你加上大括号,也无济于事,like this:
#define FOO(x) { foo(x); bar(x); }
除非你改写语句成下面这种语句
if (condition)
FOO(x)
else
...
没有分号结尾,你能忍?作为一个忠实的CPP党是不能忍的。所以如果你套上一个do{...}while(0)
,看起来就舒服多了。==这篇好像和crc32没太多关系了....不管了反正这些东西都是在看crc32上学到的==