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