循環冗餘校驗(CRC, Cyclic Redundancy Check)是一種簡單快速的雜湊函數,可以藉由比對資料傳輸或是儲存前後的循環冗餘校驗碼,檢測其是否有錯誤發生。能夠橫跨各領域應用的Rust程式語言,會有很大的機會需要使用CRC進行一些計算。可惜的是,Rust程式語言的標準函式庫並沒有提供CRC的演算法。那麼如果要使用Rust程式語言來計算CRC,該怎麼做比較好呢?



首先我們需要知道CRC演算法,實際上分了許多不同版本的函數,如8位元的CRC8、16位元的CRC16、32位元的CRC32、64位元的CRC64,CRC的位元數愈高,雜湊出來的數值碰撞機率自然會比較低,但會需要更多的時間去運算。但是CRC也不完全是使用位元數量去做變化,很有可能會遇到同樣的資料,A函式庫算出來的CRC32和B函式庫算出來的CRC32結果不同的情形。舉例來說,請看以下的PHP程式:

<?php
	header('Content-Type: text/plain');
	$data = 'test';
	$crc1 = dechex(crc32($data));
	$crc2 = bin2hex(mhash(MHASH_CRC32, $data));
	$crc3 = bin2hex(mhash(MHASH_CRC32B, $data));
	echo $crc1, ', ', $crc2, ', ', $crc3;
?>

執行結果為:

d87f7e0c, accf8b33, d87f7e0c

不曉得大家有沒有發現?同樣都是CRC32,字串「test」在上面程式中似乎可以算出「d87f7e0c16」和「accf8b3316」這兩種結果。這是由於除了CRC的位元數量之外,還有其他變數在影響著CRC演算法的計算結果。

大體來說,若不包含準備進行CRC計算的資料的話,會影響CRC演算法結果的變數共有五個,分別是「位元數量」、「多項式」、「起始值」、「終止XOR值」和「是否反射」。

藉由調控這五個變數,可以衍生出各種版本的CRC雜湊函數,於是會細分成CRC8-ATM、CRC8-CDMA、CRC16-CCITT、CRC32-IEEE、CRC32-C、CRC64-ECMA、CRC64-ISO等等十分雜亂的CRC函數名稱。

順帶一提,「mhash」函式庫的「CRC32」函數算是比較特別的,並沒有其他常見的CRC函式庫可以算出跟「mhash」函式庫一樣的結果。於是在乎這點的程式設計師多半就會使用比較標準的「CRC32B」去計算CRC校驗和,以求在不同的平台上也能一致。但也是有沒發現到或是不在乎這個問題的程式設計師依舊使用mhash函式庫的「CRC32」函數,導致與其他系統串接時雙方可能都會有一些障礙。

CRC Any

「CRC Any」是筆者開發的套件,可以使用「位元數量」、「多項式」、「起始值」、「終止XOR值」和「是否反射」這五個變數來控制CRC的輸出結果,實現出任意版本的CRC演算法。

Crates.io

https://crates.io/crates/crc-any

Cargo.toml

crc-any = "*"

使用方法

使用「use」關鍵字來將「crc-any」這個crate底下的「CRC」結構體給引用到當前的程式範圍下。「CRC」結構體提供了「create_crc」關聯函數,能夠透過參數傳入CRC演算法使用的「位元數量」、「多項式」、「起始值」、「終止XOR值」和「是否反射」這五個變數,來建立出該CRC演算法的「CRC」結構實體。「CRC」結構實體則擁有「digest」方法,可以讀取要計算出CRC雜湊值的資料。資料可以分割成很多段,依序透過幾次呼叫「digest」方法來傳入。在計算CRC雜湊的過程中可以使用「get_crc」、「get_crc_array」或「get_crc_vec」方法來取得當前的CRC雜湊結果。

舉例來說,以下程式可以計算「hello」的CRC24雜湊值:

extern crate crc_any;

use crc_any::CRC;

let mut crc24 = CRC::create_crc(0x0000000000864cfb, 24, 0x0000000000b704ce, 0x0000000000000000, false);

crc24.digest(b"hello");

assert_eq!([71, 245, 138].to_vec(), crc24.get_crc_vec());

當然,如果每次要計算CRC都要輸入「位元數量」、「多項式」、「起始值」、「終止XOR值」和「是否反射」這五個變數,實在是很麻煩。「CRC」結構實體有提供數個常見的CRC函數,可直接被呼叫使用,效能也會稍微比使用「create_crc」關聯函數還要好一點點。列表如下:

  • crc8(crc8atm)
  • crc8cdma
  • crc16(crc16ibm)
  • crc16ccitt(crcccitt)
  • crc32(crc32ieee,在「mhash」中的名稱為「CRC32B」)
  • crc32mhash(在「mhash」中的名稱為「CRC32」)
  • crc32c
  • crc64(crc64ecma)
  • crc64iso

用法如下:

extern crate crc_any;

use crc_any::CRC;

let mut crc64ecma = CRC::crc64ecma();

crc64ecma.digest(b"hello");

assert_eq!([236, 83, 136, 71, 154, 124, 145, 63].to_vec(), crc64ecma.get_crc_vec());