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