Reed-Solomon Library Programming Interface

Reed-Solomon library 소개

Reed-Solomon Library programming interface (Reed-Solomon Library Programming Interface)

저자: Thomas Gleixner

소개 (Introduction)

Generic Reed-Solomon Library는 encoding, decoding, error correction 함수를 제공합니다.

Reed-Solomon code는 통신 및 storage application에서 data integrity를 보장하기 위해 사용합니다.

이 문서는 library가 제공하는 함수를 활용하려는 developer를 위한 것입니다.

알려진 bug와 사용법

알려진 bug와 가정 (Known Bugs And Assumptions)

없습니다.

사용법 (Usage)

이 장에서는 library를 사용하는 방법을 예제로 설명합니다.

decoder 초기화

초기화 (Initializing)

초기화 함수 `init_rs`는 지정한 polynomial로 encoding, decoding, error correction을 수행하는 데 필요한 정보를 보관하는 `rs` decoder structure pointer를 반환합니다. 일치하는 기존 decoder가 있으면 재사용하고, 없으면 새로 만듭니다.

새 decoder를 만들 때 빠른 encoding과 decoding에 필요한 모든 lookup table도 생성합니다. 함수 실행에 시간이 걸릴 수 있으므로 critical code path에서 호출하지 않도록 해야 합니다.

/* 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 encoding

Encoding

Encoder는 주어진 data length에 대한 Reed-Solomon code를 계산해 parity buffer에 저장합니다. Encoder를 호출하기 전에 parity buffer를 반드시 초기화해야 합니다.

0이 아닌 inversion mask를 전달하면 확장된 data를 처리 중에 바로 반전할 수 있습니다. 확장 data와 mask를 XOR합니다. 예를 들어 FLASH ECC에서는 전부 0xFF인 값을 전부 0x00으로 반전합니다. 전부 0x00인 data의 Reed-Solomon code도 전부 0x00입니다. Code를 FLASH에 저장하기 전에 다시 반전하면 code도 0xFF가 되므로, 지워진 FLASH를 읽을 때 ECC error가 발생하는 일을 방지합니다.

Data byte는 처리 중에 지정된 symbol size로 확장됩니다. 현재 symbol size가 8이 아닌 continuous bitstream encoding은 지원하지 않습니다. 필요하다면 이 기능을 구현하는 일은 어렵지 않을 것입니다.

/* 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);

decoding 동작

Decoding

Decoder는 주어진 data length와 수신한 parity symbol로 syndrome을 계산하고 data의 error를 수정합니다.

Hardware decoder가 syndrome을 제공하면 syndrome 계산 단계를 건너뜁니다.

Correction pattern buffer와 error location buffer를 decoder에 전달하면 data buffer를 직접 수정하지 않도록 할 수 있습니다. Decoder는 계산한 error location과 correction bitmask를 제공된 buffer에 저장합니다. 이는 특이한 bit ordering scheme을 쓰는 hardware decoder에 유용합니다.

Data byte는 처리 중에 지정된 symbol size로 확장됩니다. 현재 symbol size가 8이 아닌 continuous bitstream decoding은 지원하지 않으며, 필요하다면 해당 기능을 어렵지 않게 구현할 수 있습니다.

syndrome 계산과 직접 data 수정

Syndrome을 계산하면서 data를 직접 수정하는 decoding 예제입니다.

/* 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);

hardware syndrome과 직접 data 수정

Hardware decoder가 제공한 syndrome을 사용하면서 data를 직접 수정하는 decoding 예제입니다.

/* 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);

hardware syndrome과 correction pattern

Hardware decoder가 제공한 syndrome을 사용하고 data를 직접 수정하지 않는 decoding 예제입니다.

/* 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]);
}

decoder resource 정리

정리 (Cleanup)

Caller가 decoder의 마지막 user라면 `free_rs` 함수가 할당된 resource를 해제합니다.

/* Release resources */
free_rs(rs_decoder);

structure와 공개 함수

Structure (Structures)

이 장에는 Reed-Solomon Library에서 사용하며 developer에게 관련 있는 structure의 자동 생성 문서가 들어 있습니다.

.. kernel-doc:: include/linux/rslib.h
   :internal:

제공되는 공개 함수 (Public Functions Provided)

이 장에는 export된 Reed-Solomon 함수의 자동 생성 문서가 들어 있습니다.

.. kernel-doc:: lib/reed_solomon/reed_solomon.c
   :export:

기여자

기여자 (Credits)

Encoding 및 decoding library code는 Phil Karn이 작성했습니다.

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

Wrapper function과 interface는 Thomas Gleixner가 작성했습니다.

많은 user가 bugfix, 개선 사항, test 지원을 제공했습니다. 깊이 감사드립니다.

이 문서에는 Thomas Gleixner <[email protected]>가 기여했습니다.