Reed-Solomon 庫程式設計介面

作者:

Thomas Gleixner

引言

通用 Reed-Solomon 庫提供編碼、解碼和糾錯功能。

Reed-Solomon 碼在通訊和儲存應用中用於確保資料完整性。

本文件旨在為希望利用該庫提供功能的開發者提供參考。

已知 Bug 和假設

無。

用法

本章提供瞭如何使用該庫的示例。

初始化

初始化函式 init_rs 返回一個指向 rs 解碼器結構的指標，該結構包含使用給定多項式進行編碼、解碼和糾錯所需的資訊。它要麼使用一個現有的匹配解碼器，要麼建立一個新的。建立時會生成所有用於快速編碼/解碼的查詢表。該函式可能需要一些時間，因此請確保不要在關鍵程式碼路徑中呼叫它。

/* the Reed Solomon control structure */
static struct rs_control *rs_decoder;

/* Symbolsize is 10 (bits)
 * Primitive polynomial is x^10+x^3+1
 * first consecutive root is 0
 * primitive element to generate roots = 1
 * generator polynomial degree (number of roots) = 6
 */
rs_decoder = init_rs (10, 0x409, 0, 1, 6);

編碼

編碼器根據給定的資料長度計算 Reed-Solomon 碼，並將結果儲存在奇偶校驗緩衝區中。請注意，在呼叫編碼器之前，必須初始化奇偶校驗緩衝區。

透過提供非零反轉掩碼，可以即時反轉擴充套件資料。擴充套件資料與掩碼進行異或操作。例如，這用於 FLASH ECC，其中全 0xFF 會反轉為全 0x00。全 0x00 的 Reed-Solomon 碼也是全 0x00。在儲存到 FLASH 之前，程式碼也會被反轉為 0xFF。這可以防止從擦除的 FLASH 讀取時出現 ECC 錯誤。

資料位元組會即時擴充套件到給定的符號大小。目前不支援編碼符號大小不等於 8 的連續位元流。如果需要，實現此功能應該不是什麼大問題。

/* Parity buffer. Size = number of roots */
uint16_t par[6];
/* Initialize the parity buffer */
memset(par, 0, sizeof(par));
/* Encode 512 byte in data8. Store parity in buffer par */
encode_rs8 (rs_decoder, data8, 512, par, 0);

解碼

解碼器根據給定的資料長度和接收到的奇偶校驗符號計算伴隨式，並糾正資料中的錯誤。

如果硬體解碼器提供了伴隨式，則跳過伴隨式計算。

透過向解碼器提供糾正模式緩衝區和錯誤位置緩衝區，可以抑制資料緩衝區的糾正操作。解碼器將計算出的錯誤位置和糾正位掩碼儲存在給定的緩衝區中。這對於使用奇怪位序方案的硬體解碼器很有用。

資料位元組會即時擴充套件到給定的符號大小。目前不支援解碼符號大小不等於 8 的連續位元流。如果需要，實現此功能應該不是什麼大問題。

帶伴隨式計算的解碼，直接資料糾正

/* Parity buffer. Size = number of roots */
uint16_t par[6];
uint8_t  data[512];
int numerr;
/* Receive data */
.....
/* Receive parity */
.....
/* Decode 512 byte in data8.*/
numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL);

硬體解碼器提供伴隨式的解碼，直接資料糾正

/* Parity buffer. Size = number of roots */
uint16_t par[6], syn[6];
uint8_t  data[512];
int numerr;
/* Receive data */
.....
/* Receive parity */
.....
/* Get syndrome from hardware decoder */
.....
/* Decode 512 byte in data8.*/
numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL);

硬體解碼器提供伴隨式的解碼，不直接資料糾正。

注意：無需向解碼器提供資料和接收到的奇偶校驗。

/* Parity buffer. Size = number of roots */
uint16_t par[6], syn[6], corr[8];
uint8_t  data[512];
int numerr, errpos[8];
/* Receive data */
.....
/* Receive parity */
.....
/* Get syndrome from hardware decoder */
.....
/* Decode 512 byte in data8.*/
numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr);
for (i = 0; i < numerr; i++) {
    do_error_correction_in_your_buffer(errpos[i], corr[i]);
}

清理

如果呼叫方是解碼器的最後一個使用者，free_rs 函式會釋放已分配的資源。

/* Release resources */
free_rs(rs_decoder);

結構體

本章包含 Reed-Solomon 庫中使用的與開發者相關的結構體的自動生成文件。

struct rs_codec

RS 編解碼器資料

定義:

struct rs_codec {
    int mm;
    int nn;
    uint16_t *alpha_to;
    uint16_t *index_of;
    uint16_t *genpoly;
    int nroots;
    int fcr;
    int prim;
    int iprim;
    int gfpoly;
    int (*gffunc)(int);
    int users;
    struct list_head list;
};

成員

mm

每符號位數

nn

每塊符號數（= (1<<mm)-1）

alpha_to

對數查詢表

index_of

反對數查詢表

genpoly

生成多項式

nroots

生成根數量 = 奇偶校驗符號數量

fcr

第一個連續根，索引形式

prim

原語元素，索引形式

iprim

1 的第 prim 根，索引形式

gfpoly

原語生成多項式

gffunc

如果是非規範表示，用於生成欄位的函式

users

此結構體的使用者

list

RS 編解碼器列表的列表條目

struct rs_control

每例項 RS 控制結構

定義:

struct rs_control {
    struct rs_codec *codec;
    uint16_t buffers[];
};

成員

codec

此例項使用的編解碼器

buffers

呼叫 decode_rs() 時使用的內部暫存緩衝區

struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, int nroots)

建立並初始化一個 RS 控制結構

引數

int symsize

符號大小（位數）

int gfpoly

擴充套件伽羅瓦域生成多項式係數，其中第 0 個係數在低位。該多項式必須是本原的；

int fcr

RS 碼生成多項式的第一個連續根，以索引形式表示

int prim

生成多項式根的原語元素

int nroots

RS 碼生成多項式度數（根的數量）

描述

分配使用 GFP_KERNEL。

提供的公共函式

本章包含 Reed-Solomon 匯出函式的自動生成文件。

void free_rs(struct rs_control *rs)

釋放 RS 控制結構

引數

struct rs_control *rs

不再被呼叫方使用的控制結構

描述

釋放控制結構。如果 rs 是相關編解碼器的最後一個使用者，也釋放該編解碼器。

struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim, int nroots, gfp_t gfp)

建立並初始化一個 RS 控制結構

引數

int symsize

符號大小（位數）

int gfpoly

擴充套件伽羅瓦域生成多項式係數，其中第 0 個係數在低位。該多項式必須是本原的；

int fcr

RS 碼生成多項式的第一個連續根，以索引形式表示

int prim

生成多項式根的原語元素

int nroots

RS 碼生成多項式度數（根的數量）

gfp_t gfp

記憶體分配標誌。

struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int), int fcr, int prim, int nroots)

為非規範表示欄位分配 RS 控制結構

引數

int symsize

符號大小（位數）

int (*gffunc)(int)

指向生成下一個欄位元素的函式指標，如果給定 0，則為乘法單位元素。如果 gfpoly 為 0，則代替 gfpoly 使用。

int fcr

RS 碼生成多項式的第一個連續根，以索引形式表示

int prim

生成多項式根的原語元素

int nroots

RS 碼生成多項式度數（根的數量）

int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par, uint16_t invmsk)

計算資料值（8 位資料寬度）的奇偶校驗

引數

struct rs_control *rsc

RS 控制結構

uint8_t *data

給定型別的資料欄位

int len

資料長度

uint16_t *par

奇偶校驗資料，必須由呼叫方初始化（通常全為 0）

uint16_t invmsk

反轉資料掩碼（將與資料進行異或操作）

奇偶校驗使用 uint16_t 資料型別，以支援符號大小大於 8。呼叫程式碼必須自行處理伴隨式結果的編碼以進行儲存。

int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len, uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, uint16_t *corr)

解碼碼字（8 位資料寬度）

引數

struct rs_control *rsc

RS 控制結構

uint8_t *data

給定型別的資料欄位

uint16_t *par

接收到的奇偶校驗資料欄位

int len

資料長度

uint16_t *s

伴隨式資料欄位，必須為索引形式（如果為 NULL，則計算伴隨式）

int no_eras

擦除次數

int *eras_pos

擦除位置，可以為 NULL

uint16_t invmsk

反轉資料掩碼（將與資料進行異或操作，而不是與奇偶校驗進行！）

uint16_t *corr

用於在 eras_pos 上儲存糾正位掩碼的緩衝區

伴隨式和奇偶校驗使用 uint16_t 資料型別，以支援符號大小大於 8。呼叫此程式碼之前，呼叫程式碼必須處理伴隨式結果和接收到的奇偶校驗的解碼。

注意

rs_control 結構體 rsc 包含用於

解碼的緩衝區，因此呼叫方必須確保解碼器呼叫是序列化的。

返回糾正的符號數量，對於無法糾正的錯誤則返回 -EBADMSG。此計數包含奇偶校驗中的錯誤。

int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par, uint16_t invmsk)

計算資料值（16 位資料寬度）的奇偶校驗

引數

struct rs_control *rsc

RS 控制結構

uint16_t *data

給定型別的資料欄位

int len

資料長度

uint16_t *par

奇偶校驗資料，必須由呼叫方初始化（通常全為 0）

uint16_t invmsk

反轉資料掩碼（將與資料進行異或操作，而不是與奇偶校驗進行！）

資料陣列中的每個欄位最多包含符號大小的有效資料位。

int decode_rs16(struct rs_control *rsc, uint16_t *par, int len, uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, uint16_t *corr)

解碼碼字（16 位資料寬度）

引數

struct rs_control *rsc

RS 控制結構

uint16_t *data

給定型別的資料欄位

uint16_t *par

接收到的奇偶校驗資料欄位

int len

資料長度

uint16_t *s

伴隨式資料欄位，必須為索引形式（如果為 NULL，則計算伴隨式）

int no_eras

擦除次數

int *eras_pos

擦除位置，可以為 NULL

uint16_t invmsk

反轉資料掩碼（將與資料進行異或操作，而不是與奇偶校驗進行！）

uint16_t *corr

用於在 eras_pos 上儲存糾正位掩碼的緩衝區

資料陣列中的每個欄位最多包含符號大小的有效資料位。

注意

rs_control 結構體 rsc 包含用於

解碼的緩衝區，因此呼叫方必須確保解碼器呼叫是序列化的。

返回糾正的符號數量，對於無法糾正的錯誤則返回 -EBADMSG。此計數包含奇偶校驗中的錯誤。

致謝

編解碼庫程式碼由 Phil Karn 編寫。

Copyright 2002, Phil Karn, KA9Q
May be used under the terms of the GNU General Public License (GPL)

包裝函式和介面由 Thomas Gleixner 編寫。

許多使用者為測試提供了錯誤修復、改進和幫助。非常感謝。

以下人員對此文件做出了貢獻

Thomas Gleixnertglx@linutronix.de