基于BSV的高性能并行CRC硬件電路生成器設計

[ ]01、引 言

循環冗余校驗碼，即Cyclic Redundancy Check (CRC), 是一種在各種通信系統中廣泛應用的檢錯機制。CRC算法的工作原理和哈希函數類似，具體來說，其對任意長度的數據計算出一段唯一的標識（校驗和）, 然后根據這個標識來判斷該數據在傳輸過程中是否發生變化。

CRC檢錯碼在實際生活中有著廣泛的應用，諸如網絡通信，存儲系統等場景下都需要CRC來保證數據傳輸的正確性。而不同的應用場景往往需要采用不同的CRC配置參數，同時對計算的性能也有不同的需求。例如，在基于Ethernet協議的網絡傳輸中需要采用IEEE802-3協議所規定的CRC參數，同時需要高吞吐率的CRC實現以和網絡帶寬相匹配。

對于一個具體的通信系統，CRC既可以通過軟件編程也可以硬件電路的形態來實現。相較于網絡上豐富的軟件庫，開源的CRC硬件實現卻相對落后，尤其是面向高性能的應用場景。例如，下述鏈接都提供了參數可配置的CRC硬件電路生成器，但這些實現方式都是直接將CRC算法映射到組合邏輯電路上，這往往會導致較長的組合邏輯延時進而降低電路的整體工作頻率，無法滿足高吞吐率的需求。

而另外一些開源的電路實現雖然引入了流水線技術對時序進行優化，但其實現只針對某一特定的CRC配置參數，應用場景相對有限：

• Pipelined Implementation

針對現有CRC開源硬件實現的不足，blue-crc項目基于Bluespec SystemVerilog硬件描述語言實現了一個參數可配置同時滿足高吞吐率需求的CRC硬件電路生成器。blue-crc在架構和功能上的具體特點包括:

• 支持完整的CRC配置參數包括：polynominal (生成多項式)，initial_value (初始CRC值)，finalXor (與輸出CRC值異或)， reverseInput (是否翻轉每個輸入字節的比特順序)，reverseOutput (是否翻轉輸出CRC結果的比特順序);
• 標準I/O接口: 輸入端支持AxiStream協議 (位寬可配置), 輸出端基于valid-ready握手機制傳輸CRC校驗和;
• 并行計算+流水線: 每個周期可處理多個字節數據，在Xilinx xcvu9p FPGA上可達到500MHz的運行頻率;
• 高吞吐率: 在256-bit輸入數據總線的配置下吞吐率可達128Gb/s;
• 計算模式: 支持發送端CRC生成和接收CRC檢測兩種不同的計算模式

下文將分別從算法和架構兩個方面介紹blue-crc背后的實現原理及其具體的使用方式。

02、算法原理

CRC計算的定義

生成CRC校驗和本質上是在計算基于多項式的模2除法。將原始數據每個比特所確定的多項式除以一個通信雙方規定好的生成多項式，得到的余數即為校驗和。生成CRC校驗值算法的詳細定義如下:對于m-bit原始數據

可以表示為如下多項式:

若需要生成n-bit的CRC校驗值, 則通信雙方需要規定一個 (n+1)-bit的生成多項式:

則原始數據的CRC校驗值為多項式A(x)乘上x^n 后除以G(x)得到的余數，具體表達式為：

生成的CRC校驗值附加在原始數據的尾部后傳輸至接收端, 即實際發出的數據為

基于CRC的生成原理，數據接收端可以采用兩種不同的方式完成校驗: 1) 提取出附加在發送數據尾部的校驗值后生成新的CRC校驗值，將該值與提取出的進行比較，如果二者相同則表明數據在傳輸過程中沒有出錯；2）由于校驗值為除法運算中得到的余數，這就意味著附加上檢驗值后的發送數據可被生成多項式整除，因此也可以直接對接收數據進行模2除法，若得到的余數為0則表明數據傳輸成功。

在基于多項式的模2算術運算中，變量的取值范圍只有0和1，且運算過程不存在進位或借位。因此，加減法都可以視為異或運算, 而乘除法可以由加減法構成，因此實際上也等同于一系列的異或運算。下圖展示了一個具體的模2除法取余數計算CRC校驗和的例子，其中原始數據為101001，生成多項式為1101。由該例子可見，模2除法的運算法則和普通的除法類似，不同點在于模2除法用異或操作替換了減法且不存在借位。

從另外一個角度理解，模二除法取余數的過程實際上是逐位地對原始數據進行縮減: 當輸入數據的最高位為1時，原始數據和除數左對齊異或后移除最高位，得到下一輪縮減的輸入；當最高位為0時，直接移除最高位得到下一輪縮減的輸入。不斷重復上述縮減步驟直至輸入數據的位寬小于除數位寬，該輸入值即為所求余數。根據上述取模步驟，可以很容易地將CRC算法映射到基于線性負反饋移位寄存器 (LFSR) 結構的硬件上，一種具體的實現如下圖所示, 其對應的生成多項式為11011。原始數據從最高位開始逐位從Din輸入，當所有數據都傳入后，寄存器中的值即為所要求的校驗和。

上圖展示的電路結構是一種非常經典的CRC算法的硬件實現方式，其可以用極小的面積和功耗生成校驗值，但由于每個周期只能處理1-bit輸入數據，其很難達到較高的吞吐率。為了提升CRC校驗電路的計算性能，很多面向硬件的CRC并行算法被提出。blue-crc項目的實現主要參考了論文[1]和[2]中提出的并行算法和電路架構, 并在此基礎上進一步優化流水線結構以提升工作頻率，同時提供了參數可配置的設計以及標準的輸入輸出接口。

并行算法

blue-crc項目所采用的并行算法主要是建立在模2除法(取余)運算的兩個定理之上，這兩個定理分別是（備注:下文所列公式中的算術運算都是在模2域下完成，即加減法都等同于異或運算）:

1. 若多項式

則

由定理1可知, 對于任意長度的輸入數據, 都可以將其拆分成若干小段，每小段數據的CRC校驗值可以獨立地并行計算，然后通過異或操作將所有校驗值累加在一起，即可得到完整數據對應的CRC校驗值。在blue-crc的實現中，每小段數據Ai(x)的長度為8-bit, 設原始數據A(x)的總長度為8n-bit, 則:

根據定理1，我們可以并行地計算每個輸入字節Ai(x)的校驗值

，然后將每個字節對應的校驗和累加在一起就可得到完整數據的校驗和，即

對于每個輸入字節的CRC校驗和的計算，除了依照算法實現對應的硬件電路， 另一種更加高效的方式是: 提前計算好8-bit數所有可能值對應的CRC輸出并制作成硬件查找表，當電路運行時，以輸入數據為地址從查找表中取出對應的表項即可得到校驗和。若輸入原始數據有n個字節，則需要制作n張長度為

的查找表，其中第

張查找表的第x個表項的值即為

的CRC校驗和。

雖然有了定理1我們可以在一個周期內并行處理多個字節數據，但基于此還不能夠完成CRC的硬件實現。在實際電路中數據總線的位寬是有限的，對于較長的輸入數據，需要根據總線位寬將其分成多個幀并分配到多個周期進行傳輸。因此，我們還需要基于定理2累加不同周期計算得到的CRC校驗值進而獲得最終結果。

在blue-crc的實現中，數據以大端字節序進行傳輸，即高位數據先傳入進行處理, 假設輸入數據總線位寬為256-bit, 當前周期輸入數據對應的多項式為A(x), 該周期之前已經輸入的數據為A'(x), 每個周期我們除了計算CRC[A(x)]，還需要將該值累加到已經計算好的中間校驗和CRC[A'(x)]上，得到數據

的校驗和。根據定理1和2，可以推導出累加的計算公式如下:

即需要將中間校驗和CRC[A'(x)]左移256-bit，對其再次計算CRC校驗值后和CRC[A(x)]相加。同樣我們可以通過硬件查找表的方式完成這里校驗和的計算。

實際CRC的計算中原始數據的長度并不一定都是256-bit的整數倍，因此在處理最后一幀輸入時不能直接使用上面的公式進行累加。我們需要動態地計算每個數據包最后一幀的有效數據的寬度，設寬度為m, 則可以采用如下公式進行累加:

03、電路架構與性能

架構設計

基于上述并行算法，CRC硬件電路的架構設計如下圖所示。為了提升吞吐率，電路設計時將CRC算法需要的組合邏輯實現劃分成了八級單向傳遞的流水線, 其中前五級流水線計算每個周期輸入數據的CRC校驗和并累加到CRC中間值上，后三級流水線用于處理最后一幀數據非對齊（數據位寬非總線位寬的整數倍）情況下CRC校驗值的累加。每一級流水線的完成的具體功能如下:

• Stage-1: 對AXI-Stream總線輸入數據進行預處理，包括大小端轉換、根據CRC配置參數reverse_input調換比特順序、根據AXI-Stream總線tkeep字段計算數據總線上有效的字節數（用于處理數據長度非總線位寬整數倍的情況）；
• Stage-2: 對于數據長度非總線位寬整數倍的情況，需要對最后一幀數據進行移位和下一級的查找表對齊；
• Stage-3: 從查找表中取出輸入數據每個字節對應的CRC校驗值；
• Stage-4: 通過樹狀結構將各個字節的CRC值進行異或合并得到該周期輸入數據對應的CRC校驗和；
• Stage-5: 根據上文提到的定理2，將輸入數據CRC校驗和累加到中間校驗和之上。最后一幀輸入數據（有效數據位寬可能小于總線位寬）需要特殊的處理，因此不在該流水級直接進行累加，需要將中間CRC值和上一級傳來的CRC校驗和傳遞到后續流水級進行處理;
• 中計算的最后一幀數據的實際有效位寬對中間CRC值進行移位和下一級的查找表對齊;

• 中計算的最后一幀數據的實際有效位寬對中間CRC值進行移位和下一級的查找表對齊;
• Stage-7: 從查找表中取出中間CRC值移位后對應的校驗和;
• Stage-8: 將上一級的查找表輸出和Stage-5傳遞來的最后一幀輸入數據的CRC校驗和通過樹狀結構進行異或合并得到全部數據的校驗和

性能與面積

CRC硬件電路的實際性能和資源開銷與具體的配置參數有關。大部分情況下，硬件電路的吞吐率隨輸入總線數據位寬增大而提升，硬件資源開銷則同時和總線寬度以及CRC校驗和寬度有關。以IEEE 802-3協議規定的32位CRC校驗和為例，其在256位輸入總線位寬的配置下，可在Xilinx xcvu9p FPGA器件上達到500MHz的工作頻率，總吞吐率達128Gb/s，實際的硬件資源開銷如下。

相較于其他硬件實現方式，blue-crc主要關注于計算性能上的提升，因此在硬件資源上的開銷相對較大。其中最主要的開銷來源于用于實現CRC計算的查找表，其容量大小隨數據總線位寬以及校驗和位寬的增大而增大，具體的查找表容量的計算方式如下（設總線字節寬度為m, CRC校驗和字節寬度為n）:

對于上文提到的IEEE 802-3協議規定的 32-bit CRC校驗，在256-bit輸入總線位寬的配置下，理論上所需的查找表容量為36KB.

04、使用指南

本文的最后一部分將介紹blue-crc項目的使用指南，包括CRC電路的配置參數、輸入輸出接口、面向BlueSpec SystemVerilog的使用接口，以及面向Verilog的使用接口。

配置參數

在blue-crc中，CRC硬件電路完整的配置參數如下表所示:

輸入輸出接口

在blue-crc項目中，CRC硬件電路基于AXI-Stream總線協議接收上游模塊傳入的數據，校驗和輸出端口采用valid-ready握手機制和下游模塊進行交互。電路頂層模塊生成的Verilog端口如下:

module mkCrcRawAxiStreamCustom(    input CLK,    input RST_N,        input s_axis_tvalid,    input s_axis_tdata,    input s_axis_tkeep,    input s_axis_tlast,    input s_axis_tuser,    output s_axis_tready,        output m_crc_stream_data,    output m_crc_stream_valid,    input  m_crc_stream_ready);

發起CRC計算時原始數據需要按照大端字節序進行傳輸，即高位字節需要優先傳輸。假設CRC電路輸入AXI-Stream總線數據位寬為32-bit (4-byte), 若要傳輸80-bit (10-byte)的數據，那么每一幀需要傳輸的內容如下圖所示:

BSV使用接口

blue-crc項目基于Bluespec SystemVerilog硬件描述語言實現，因此對于使用BSV的設計者，可以直接通過實例化的方式使用CRC模塊。詳細的使用步驟如下:

1. 獲取blue-crc源碼: blue-crc使用了blue-wrapper項目提供的AXI-Stream接口，克隆時需要加上--recursive選項獲得這部分代碼:

git clone --recursive https://github.com/datenlord/blue-crc.git

2. 在代碼中導入所需模塊:

import CrcDefines :: *;import CrcAxiStream :: *;import AxiStreamTypes :: *;

3. 確定CRC配置參數:CrcConfig結構體封裝了電路的各項配置參數, CrcConfig結構體的定義如下, 其中每個字段的具體含義可參考前文列出的表格。其中，revInput和revOutput字段為IsReverseBitOrder枚舉類型，可選取值包括BIT_ORDER_REVERSE 和 BIT_ORDER_NOT_REVERSE; crcMode字段為CrcMode枚舉類型, 可選取值包括CRC_MODE_RECV和CRC_MODE_SEND。

typedef struct {    Bit#(crcWidth) polynominal;    Bit#(crcWidth) initVal;    Bit#(crcWidth) finalXor;    IsReverseBitOrder revInput;    IsReverseBitOrder revOutput;    String memFilePrefix;    CrcMode crcMode;} CrcConfig#(numeric type crcWidth) deriving(Eq, FShow);typedef enum {    CRC_MODE_RECV,    CRC_MODE_SEND} CrcMode deriving(Eq, FShow);typedef enum {    BIT_ORDER_REVERSE,    BIT_ORDER_NOT_REVERSE} IsReverseBitOrder deriving(Eq, FShow);

4. 實例化mkCrcAxiStream模塊: 頂層模塊接口CrcAxiStream的定義如下，數據的輸入和輸出分別由Get和Put接口實現

typedef Bit#(width) CrcResult#(numeric type width);typedef Get#(CrcResult#(crcWidth)) CrcResultGet#(numeric type crcWidth);typedef Put#(AxiStream#(keepWidth, AXIS_USER_WIDTH)) AxiStreamPut#(numeric type keepWidth);interface CrcAxiStream#(numeric type crcWidth, numeric type axiKeepWidth);    interface AxiStreamPut#(axiKeepWidth) crcReq;    interface CrcResultGet#(crcWidth) crcResp;endinterface

以IEEE 802-3協議中規定的32-bit CRC為例，若要實現輸入位寬為256-bit的CRC校驗值生成電路，則實例化碼如下:

CrcConfig#(32) conf = CrcConfig {    polynominal: 32'h04C11DB7,    initVal    : 32'hFFFFFFFF,    finalXor   : 32'hFFFFFFFF,    revInput   : BIT_ORDER_REVERSE,    revOutput  : BIT_ORDER_REVERSE,    memFilePrefix: "mem_tab",    crcMode: CRC_MODE_SEND};CrcAxiStream#(32, 256) crc < - mkCrcAxiStream(conf);

5. 生成查找表文件: 查找表文件的生成腳本為scripts/gen_crc_tab.py, 使用該腳本前需要先配置.json格式的CRC配置文件，該文件的內容需要和BSV代碼中的配置一致:

{    "crc_width": 32,    "axi_keep_width": 32,    "polynomial": "0x04C11DB7",    "init_value": "0xFFFFFFFF",    "final_xor": "0xFFFFFFFF",    "reverse_input": true,    "reverse_output": true,    "mem_file_prefix": "crc_tab",    "crc_mode": "CRC_MODE_SEND"}

配置好.json文件后，使用python執行該腳本（需要傳入.json配置文件路徑和輸出文件路徑）:

python3 gen_crc_tab.py JSON文件路徑 文件輸出路徑

6. 編譯項目時需要在編譯選項中加入blue-crc源代碼的路徑, 假設blue-crc的根目錄為$(ROOT), 則需要在編譯選項中加上:

bsc -p +:$(BLUE_CRC)/src:$(ROOT)/lib/blue-wrapper/src

Verilog使用接口

雖然blue-crc項目基于BSV實現，但同時也提供了生成可配的Verilog代碼的腳本scripts/gen_crc.py。該腳本需要在blue-crc項目的根目錄下執行，同時需要傳入.json格式的CRC配置文件（具體文件格式見上文）:

python3 scripts/gen_crc.py JSON配置文件 [Verilog生成路徑] [查找表生成路徑]

若在執行腳本時沒有配置Verilog代碼和查找表文件生成路徑，那么這些文件會默認生成到根目錄下的verilog文件夾。生成Verilog代碼需要使用到BSV編譯器，因此在執行腳本前還需要保證已經安裝并配置好該編譯工具。