CRC原理

基本概念

CRC(Cyclic Redundancy Check)中文名是循環(huán)冗余校驗,其計算簡單，被廣泛應(yīng)用于數(shù)據(jù)校驗，具有很強的檢錯能力。

數(shù)學(xué)原理

CRC算法是已GF(2)多項式為數(shù)學(xué)基礎(chǔ)的，這個不是很難理解，說白了其實就是在玩異或運算。這篇博文對其中的數(shù)學(xué)講的很通俗易懂，推薦大家可以參考下。

源碼實現(xiàn)

leveldb中對于crc32實現(xiàn)還是非常簡單的，核心在于一個Extend()函數(shù)。

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;
}

實現(xiàn)的比較簡潔，關(guān)鍵處也有代碼注釋，如果你明白了CRC的原理，相信讀懂這份代碼應(yīng)該沒有什么困難。細(xì)讀這份代碼時還是學(xué)習(xí)了一個新技巧

#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)中而言。
但是考慮這樣的宏定義在下面這種情況的結(jié)果

#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
    ...

沒有分號結(jié)尾，你能忍？作為一個忠實的CPP黨是不能忍的。所以如果你套上一個do{...}while(0)，看起來就舒服多了。==這篇好像和crc32沒太多關(guān)系了....不管了反正這些東西都是在看crc32上學(xué)到的==