boost.png (6897 bytes)頭文件 <boost/crc.hpp>

頭文件 <boost/crc.hpp> 提供了兩個位於 boost 名稱空間(namespace)中的兩個類模板。這些模板定義了一些對象,使用它們可以計算給定數據流的 CRC ——循環冗余碼(校驗)。這個頭文件還提供了一步(一次調用)就可以計算出 CRC 的函數模板。

目錄

  1. 目錄
  2. 頭文件大綱
  3. 基本原理
  4. 背景知識
  5. 理論 CRC 機
  6. 優化的 CRC 機
  7. CRC 機使用方式
  8. CRC 函數
  9. 擴張-CRC 函數
  10. 預定義的 CRC 例子
  11. 參考資料
  12. 榮譽

頭文件大綱

#include <boost/integer.hpp>  // for boost::uint_t
#include <cstddef>            // for std::size_t

namespace boost
{

template < std::size_t Bits >
    class crc_basic;

template < std::size_t Bits, impl_def TruncPoly = 0u,
impl_def InitRem = 0u,
impl_def FinalXor = 0u, bool ReflectIn = false,
bool ReflectRem = false >
class crc_optimal;

template < std::size_t Bits, impl_def TruncPoly,
impl_def InitRem, impl_def FinalXor,
bool ReflectIn, bool ReflectRem >
typename uint_t<Bits>::fast crc( void const *buffer,
std::size_t byte_count );

template < std::size_t Bits, impl_def TruncPoly >
typename uint_t<Bits>::fast augmented_crc( void const *buffer,
std::size_t byte_count,
typename uint_t<Bits>::fast initial_remainder );

template < std::size_t Bits, impl_def TruncPoly >
typename uint_t<Bits>::fast augmented_crc( void const *buffer,
std::size_t byte_count );

typedef crc_optimal<16, 0x8005, 0, 0, true, true> crc_16_type;
typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_type;
typedef crc_optimal<16, 0x8408, 0, 0, true, true> crc_xmodem_type;

typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>
crc_32_type;

}

實現相關的類型 impl_def 代表“可以表示至少 Bits 個位,且可以最快地進行運算的內建無符號整數類型”。

基本原理

常用的特別是在電子通訊中使用的錯誤檢測機制是為數據附加校驗和。數據發送者在發送數據時,把數據的檢驗和一併發送出去,這個檢驗和是對數據流的按 位(bit)運算得出的。接收者收到數據後使用同樣的運算取得檢驗和。如果發現兩個檢驗和不匹配,就可以認為數據在傳輸過程中發生了錯誤。有時候(概率很 小)會發生僅僅檢驗和出錯而導致實際上正確的數據被拒絕的情況。也有可能出現數據中有差錯但是檢驗和不變從而隱藏了錯誤的情況。CRC 是一種常用的為硬件接口和編碼格式提供錯誤檢測的檢驗和類型。

背景知識

CRC 是通過計算一個以2為模的多項式除法的餘數來實現的。作為被除數的是一個冗長的多項式,首先消息前面(earlier)的位(bits)被當作是多項式的最高次係數,然後這個消息被當作是多項式的(二次)係數。一個完整的 CRC 算法中還牽涉到另外一個用作除數的多項式 。除法運算過程中對係數採用以2為模(modulo-2)規則(不進位),運算得出的商被乎略而餘數就是檢驗和。

完整的資料參看 A Painless Guide to CRC Error Detection Algorithms。這裡有一個更清晰的解釋: Easier Said Than Done .

CRC 參數

被截短的多項式

除數多項式比檢驗和(餘數)大一個位(bit)。這個最高位恆為1,所以在描述特定的 CRC 類型時它是被乎略的,從而使得除數和檢驗和可以使用同一個數據類型來表示。

餘數的初始值
在運算過程中 CRC 餘數隨著對數據的逐位處理而變化。餘數的初始值通常是0,但是有些 CRCs 使用其他值來避免“盲點”。所謂的“盲點”是指一個共同(common)的消息位序列不改變特定的中間餘數值。
最後一步 XOR 操作
CRC 餘數在返回給用戶之前,可以通過位異或(bitwise exclusive-or)操作與一個特定的值進行合併。這個特定的值一般是0,也就是說餘數被原封不動地返回給用戶。另一個常用的值是“全1”值(譯者註:即這個值的所有二進制位都是1的),即返回中間餘數的二進制補數(bitwise complement)。
輸入反射
消息的各個位通常以字節為單位提供給 CRC 運算,字節的最高幾位被當作是被除數的高位。一些 CRCs 會在進行 CRC 運算之前“反射”各個位(相對於字節的正中間進行“反射”,比如,字節的第一位和最後一位互換,以此類推)
輸出(餘數)反射
有些 CRCs 會返回中間餘數的“反射”(在進行最終 XOR 操作之前進行)而非餘數本身。

理論 CRC 機

template < std::size_t Bits >
class boost::crc_basic
{
public:
// Type
typedef implementation_defined value_type;

// Constant reflecting template parameter
static std::size_t const bit_count = Bits;

// Constructor
explicit crc_basic( value_type truncated_polynominal,
value_type initial_remainder = 0, value_type final_xor_value = 0,
bool reflect_input = false, bool reflect_remainder = false );

// Internal Operations
value_type get_truncated_polynominal() const;
value_type get_initial_remainder() const;
value_type get_final_xor_value() const;
bool get_reflect_input() const;
bool get_reflect_remainder() const;

value_type get_interim_remainder() const;
void reset( value_type new_rem );
void reset();

// External Operations
void process_bit( bool bit );
void process_bits( unsigned char bits, std::size_t bit_count );
void process_byte( unsigned char byte );
void process_block( void const *bytes_begin, void const *bytes_end );
void process_bytes( void const *buffer, std::size_t byte_count );

value_type checksum() const;

};

value_type是一個最小 Bits 位大小的內建數字類型。這個類型應該是 boost::uint_t<Bits>::least,具體細節參看 documentation for integer type selection.

這個算法慢,因為它完全按照理論逐位進行運算。它沒有經過優化。大部分的 CRC 參數都是在運行時以構造函數參數的形式提供,所以這個算法也浪費空間。

優化的 CRC 機

template < std::size_t Bits, impl_def TruncPoly,
impl_def InitRem, impl_def FinalXor,
bool ReflectIn, bool ReflectRem >
class boost::crc_optimal
{
public:
// Type
typedef implementation_defined value_type;

// Constants reflecting template parameters
static std::size_t const bit_count = Bits;
static value_type const truncated_polynominal = TruncPoly;
static value_type const initial_remainder = InitRem;
static value_type const final_xor_value = FinalXor;
static bool const reflect_input = ReflectIn;
static bool const reflect_remainder = ReflectRem;

// Constructor
explicit crc_optimal( value_type init_rem = InitRem );

// Internal Operations
value_type get_truncated_polynominal() const;
value_type get_initial_remainder() const;
value_type get_final_xor_value() const;
bool get_reflect_input() const;
bool get_reflect_remainder() const;

value_type get_interim_remainder() const;
void reset( value_type new_rem = InitRem );

// External Operations
void process_byte( unsigned char byte );
void process_block( void const *bytes_begin, void const *bytes_end );
void process_bytes( void const *buffer, std::size_t byte_count );

value_type checksum() const;

// Operators
void operator ()( unsigned char byte );
value_type operator ()() const;

};

value_type 是可以被最快速操縱的少 Bits 位大小內建數字類型。這個類型應該是 boost::uint_t<Bits>::fast。具體細節參看 integer type selection documentation。模板參數 TruncPolyInitRemFinalXor 也是這個類型。

這個算法為了達到實用的目標使用了盡可能多的優化所以運算速度快。所有的 CRC 參數都在編譯期以模板參數的形式提供。它在參數傳遞時使用整個字節(byte)而非單個位(bit)為單位。在使用某個特定種類(位數、除數多項式和輸入反射狀態)的第一個對像時,這個算法會預先計算出一張中間 CRC 值到字節值的對應表(以供後來創建的同類型的對象直接查詢,以提高運算速度)。

用法

這兩個類模板在 CRC 參數如何提供方面使用不同的策略。它們都使用 CRC 中的位數作為第一個模板參數。理論 CRC 機類模板只有這一個模板參數,所有其他的 CRC 參數都是通過構造函數輸入的,而在優化的 CRC 機類模板中所有的 CRC 參數都從模板參數中獲得,並且它的實例對像通常都是默認構造。在運行時,CRC 參數可以通過調用如下方法來查看:et_truncated_polynominal、 get_initial_remainderget_final_xor_valueget_reflect_inputget_reflect_remainder。快速 CRC 機也為它的 CRC 參數提供了編譯期常量。

get_interim_remainder 方法返回 CRC 餘數的初始狀態值。它代表未反射過的最後一次除法運算的餘數。保存中間餘數 、其他 CRC 參數和字節流的當前處理位置就可以“凍結” 一個CRC 運算過程。使用舊 CRC 機的大部分參數來構造一個新的 CRC 機並使用“凍結”的餘數作為新 CRC 機的中間餘數,就可以“解凍”這個過程,並正常進行後繼運算了。快速 CRC 機為此目的實現了一個只接收一個參數(中間餘數)的特殊的構造函數(取代了 CRC 餘數的初始值)。

reset 方法使用給定的值來重置 CRC 餘數的初始狀態。如果沒有提供值,初始餘數被賦值為對像創建時指定的餘數初始值。餘數必須是未經反射過的。當一個 CRC 計算過程結束後,調用 reset方法可以重用這個對象進行下一個新的計算過程。

構造完成之後,兩個 CRC 機已同樣的方式運作。提取當前 CRC 值和給 CRC 機提供新數據是在不同的操作中完成的。下表列出了這些操作。

正規 CRC 操作正規 CRC 操作正規 CRC 操作正規 CRC 操作正規 CRC 操作
操作 描述
void process_bit( bool bit ); 把一個位(bit)作為數據傳遞給 CRC 機,更新中間 CRC。只在慢速 CRC 機中定義。
void process_bits( unsigned char bits, std::size_t bit_count ); bits 中最低的 bit_count 個位(從最重要的位算起)應用 process_bit。如果 bit_count 超過了每個字節的位數,結果未定義。只在慢速 CRC 機中定義。
void process_byte( unsigned char byte ); byte 中的所有位應用 process_bit。如果不需要反射,這些位以從最重要到最不重要的順序依次提供;否則以相反的順序提供。
void process_block( void const *bytes_begin, void const *bytes_end ); 對給定的從 bytes_begin 開始,到 bytes_end 結束的內存塊應用 process_byte。各個字節依上述順序處理。
void process_bytes( void const *buffer, std::size_t byte_count ); 對給定的從 buffer 開始的長度為 byte_count 字節的內存塊應用 process_byte。各個字節依升序處理。
value_type checksum() const; 返回到目前為止所有傳遞過去的數據的 CRC 檢驗和,這個值可能經過了餘數反射和異或運算。
void operator ()( unsigned char byte ); 調用 process_byte。有了這個方法,就可以把 CRC 機對像當作一個(有狀態的)函數對像來使用。只在快速 CRC 機中定義。
value_type operator ()() const; 調用 checksum。有了這個這個方法,就可以把 CRC 機對像當作一個發生器(generator)函數對像來使用。只在快速 CRC 機中定義。

你可以像這樣來使用:

#include <boost/crc.hpp>      // for boost::crc_basic, boost::crc_optimal
#include <boost/cstdint.hpp>  // for boost::uint16_t

#include <algorithm>  // for std::for_each
#include <cassert>    // for assert
#include <cstddef>    // for std::size_t
#include <iostream>   // for std::cout
#include <ostream>    // for std::endl


// Main function
int
main ()
{
    // This is "123456789" in ASCII
    unsigned char const  data[] = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
     0x38, 0x39 };
    std::size_t const    data_len = sizeof( data ) / sizeof( data[0] );

    // The expected CRC for the given data
    boost::uint16_t const  expected = 0x29B1;

    // Simulate CRC-CCITT
    boost::crc_basic<16>  crc_ccitt1( 0x1021, 0xFFFF, 0, false, false );
    crc_ccitt1.process_bytes( data, data_len );
    assert( crc_ccitt1.checksum() == expected );

    // Repeat with the optimal version (assuming a 16-bit type exists)
    boost::crc_optimal<16, 0x1021, 0xFFFF, 0, false, false>  crc_ccitt2;
    crc_ccitt2 = std::for_each( data, data + data_len, crc_ccitt2 );
    assert( crc_ccitt2() == expected );

    std::cout << "All tests passed." << std::endl;
    return 0;
}
  

CRC 函數

template < std::size_t Bits, impl_def TruncPoly,
impl_def InitRem, impl_def FinalXor,
bool ReflectIn, bool ReflectRem >
typename boost::uint_t<Bits>::fast
boost::crc( void const *buffer, std::size_t byte_count );

boost::crc 函數模板可以計算一個給定的數據塊的 CRC 值。這個數據塊從地址 buffer 開始,長度為 byte_count 字節。CRC 參數通過模板參數傳遞,和優化的 CRC 機 (看這裡)等同。實際上優化的 CRC 機就是用來實現這個函數的。

擴張-CRC 函數

template < std::size_t Bits, impl_def TruncPoly >
typename boost::uint_t<Bits>::fast
boost::augmented_crc( void const *buffer, std::size_t byte_count,
typename boost::uint_t<Bits>::fast initial_remainder );

template < std::size_t Bits, impl_def TruncPoly >
typename boost::uint_t<Bits>::fast
boost::augmented_crc( void const *buffer, std::size_t byte_count );

所有其他 CRC 計算函數或類模板在工作時都假定直接從消息中的第一個位開始運算。這兩個 boost::augmented_crc 函數模板不同,它們會把一個新的消息位移進(shift into)餘數寄存器,同時把餘數寄存器的最高位移出(shift out),而其他的函數或類模板是通過位異或運算把當前消息位合併到一個獨立餘數的最高位上的。這個新的計算方式意味著在實際的消息位被處理之前,初始餘數值的各個位已經被處理過了。這樣導致的結果是必須在傳遞實際的消息位給 CRC 機之後再傳遞足夠多個(餘數寄存器的大小)0 才能提取處真正的 CRC 值。

這兩個版本的函數的模板參數都是 CRC 的大小(Bits)和截短的多項式(TruncPoly)。帶兩個參數的版本以 0 作為 initial_remainder 調用帶三個參數的版本。兩個版本都是對從地址 buffer 開始,長度為 byte_count 的數據進行運算。

這些函數在 CRC 數據直接跟在消息數據之後的情況下有用。首先,設置 CRC 所在的幾個字節為 0。然後對“擴張後的(augmented)”消息(附加了 CRC 的消息數據)使用 augmented_crc 並把結果賦值給 CRC。在接收方校驗收到的數據時,要麼對“未擴張的(unaugmented)”消息使用 augmented_crc(當然,使用和發送時一樣的參數)並檢查結果是否和 CRC 相等;要麼對“擴張的”消息使用 augmented_crc 並檢查結果是否為 0。注意,CRC 必須保存在最重要的字節裡(大尾)。

CRC 數據中的中斷可以這樣處理:把前一個數據塊的 augmented_crc 結果作為 initial_remainder 來對下一個數據塊調用 augmented_crc。記住,實際的 CRC 只能在提供“擴張的”數據之後才能確定。原因是這個方法在其最底層使用已 2 為模的多項式除法,且最終 XOR 和反射都不能使用。

注意,對於相同的 CRC 系統,augmented 方法的初始餘數值和 unaugmented 方法的不一樣。有個常見的例外是 0;如果 augmented-CRC 算法使用 0 作為初始餘數,對應的 unaugmented-CRC 算法也將使用 0 作為初始餘數。給定一個 augmented-CRC 算法的初始餘數,處理沒有任何消息數據的 0 值 CRC 數據所得到的結果和 unaugmented-CRC 算法的初始餘數是相等的。比如:

#include <boost/crc.hpp>      // for boost::crc_basic, boost::augmented_crc
#include <boost/cstdint.hpp>  // for boost::uint16_t

#include <cassert>    // for assert
#include <iostream>   // for std::cout
#include <ostream>    // for std::endl


// Main function
int
main ()
{
    using boost::uint16_t;
    using boost::augmented_crc;

    uint16_t        data[6] = { 2, 4, 31, 67, 98, 0 };
    uint16_t const  init_rem = 0x123;

    uint16_t  crc1 = augmented_crc<16, 0x8005>( data, sizeof(data), init_rem );

    uint16_t const  zero = 0;
    uint16_t const  new_init_rem = augmented_crc<16, 0x8005>( &zero, sizeof(zero) );

    boost::crc_basic<16>  crc2( 0x8005, new_init_rem );
    crc2.process_block( data, &data[5] );  // don't include CRC
    assert( crc2.checksum() == crc1 );

    std::cout << "All tests passed." << std::endl;
    return 0;
}
  

預定義的 CRC 例子

這裡有四種 CRC 類型,代表了一些常用的 CRC 算法。比如,boost::crc_32_type 可以用來實現 PKZip 標準。注意,從一般意義上講,這個庫注重的是 CRC 的實現而非“良好的” CRC 參數的選擇。

常用 CRCs
算法 示例協議
crc_16_type BISYNCH, ARC
crc_ccitt_type designated by CCITT (Comité Consultatif International Télégraphique et Téléphonique)
crc_xmodem_type XMODEM
crc_32_type PKZip, AUTODIN II, Ethernet, FDDI

參考資料

Credits 榮譽

Contributors 貢獻者

Michael Barr (mbarr@netrino.com)
Wrote Easier Said Than Done, a less-confusing guide to implementing CRC algorithms. (Originally published as "Slow and Steady Never Lost the Race" in the January 2000 issue of Embedded Systems Programming, pages 37–46.)
Daryle Walker
Started the library and contributed the theoretical and optimal CRC computation class templates and the CRC computing function template. Contributed crc_test.cpp and crc_example.cpp.
Ross N. Williams
Wrote A Painless Guide to CRC Error Detection Algorithms, a definitive source of CRC information.

Acknowledgements 鳴謝

For giving advice on compiler/C++ compliance, implementation, interface, algorithms, and bug reports:

History 歷史

15 Jun 2003, Daryle Walker
加入例程
14 May 2001, Daryle Walker
初始版本

Revised: 15 June 2003

Copyright 2001, 2003 Daryle Walker. Use, modification, and distribution are subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.)