循環冗餘校驗(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_be());
assert_eq!("0x47F58A", &crc24.to_string());

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

  • crc3gsm
  • crc4itu
  • crc4interlaken
  • crc5epc
  • crc5itu
  • crc5usb
  • crc6cdma2000_a
  • crc6cdma2000_b
  • crc6darc
  • crc6gsm
  • crc6itu
  • crc7
  • crc7umts
  • crc8
  • crc8cdma2000
  • crc8darc
  • crc8dvb_s2
  • crc8ebu
  • crc8icode
  • crc8itu
  • crc8maxim
  • crc8rohc
  • crc8wcdma
  • crc10
  • crc10cdma2000
  • crc10gsm
  • crc11
  • crc12
  • crc12cdma2000
  • crc12gsm
  • crc13bbc
  • crc14darc
  • crc14gsm
  • crc15can
  • crc15mpt1327
  • crc16
  • crc16ccitt_false
  • crc16aug_ccitt
  • crc16cdma2000
  • crc16dds_110
  • crc16dect_r
  • crc16dect_x
  • crc16dnp
  • crc16en_13757
  • crc16genibus
  • crc16maxim
  • crc16mcrf4cc
  • crc16riello
  • crc16t10_dif
  • crc16teledisk
  • crc16tms13157
  • crc16usb
  • crc_a
  • crc16kermit
  • crc16modbus
  • crc16_x25
  • crc16xmodem
  • crc17can
  • crc21can
  • crc24
  • crc24ble
  • crc24flexray_a
  • crc24flexray_b
  • crc24lte_a
  • crc24lte_b
  • crc24os9
  • crc30cdma
  • crc32 (在「mhash」中的名稱為「CRC32B」)
  • crc32mhash (在「mhash」中的名稱為「CRC32」)
  • crc32bzip2
  • crc32c
  • crc32d
  • crc32mpeg2
  • crc32posix
  • crc32q
  • crc32jamcrc
  • crc32xfer
  • crc40gsm
  • crc64
  • crc64iso
  • crc64jones

用法如下:

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(), crc64.get_crc_vec_be());
assert_eq!("0xEC5388479A7C913F", &crc64.to_string());

無堆積的支援

雖然「CRC Any」沒有用到標準函式庫,但是它有用到堆積。如果不想要用要堆積的話,可以關閉預設啟用的特色。Cargo.toml設定檔的寫法如下:

[dependencies.crc-any]
version = "*"
default-features = false

當然,一旦關閉預設啟用的特色,get_crc_vec_beget_crc_vec_le方法就會無法使用。不過如果還是想要讓「CRC Any」能夠回傳Vec結構體卻又不想要有動態記憶體配置的話,可以啟用heapless特色。

[dependencies.crc-any]
version = "*"
default-features = false
features = ["heapless"]

如此一來就能夠使用get_crc_heapless_vec_beget_crc_heapless_vec_le方法了!