0001 ==========================================
0002 Reed-Solomon Library Programming Interface
0003 ==========================================
0004
0005 :Author: Thomas Gleixner
0006
0007 Introduction
0008 ============
0009
0010 The generic Reed-Solomon Library provides encoding, decoding and error
0011 correction functions.
0012
0013 Reed-Solomon codes are used in communication and storage applications to
0014 ensure data integrity.
0015
0016 This documentation is provided for developers who want to utilize the
0017 functions provided by the library.
0018
0019 Known Bugs And Assumptions
0020 ==========================
0021
0022 None.
0023
0024 Usage
0025 =====
0026
0027 This chapter provides examples of how to use the library.
0028
0029 Initializing
0030 ------------
0031
0032 The init function init_rs returns a pointer to an rs decoder structure,
0033 which holds the necessary information for encoding, decoding and error
0034 correction with the given polynomial. It either uses an existing
0035 matching decoder or creates a new one. On creation all the lookup tables
0036 for fast en/decoding are created. The function may take a while, so make
0037 sure not to call it in critical code paths.
0038
0039 ::
0040
0041 /* the Reed Solomon control structure */
0042 static struct rs_control *rs_decoder;
0043
0044 /* Symbolsize is 10 (bits)
0045 * Primitive polynomial is x^10+x^3+1
0046 * first consecutive root is 0
0047 * primitive element to generate roots = 1
0048 * generator polynomial degree (number of roots) = 6
0049 */
0050 rs_decoder = init_rs (10, 0x409, 0, 1, 6);
0051
0052
0053 Encoding
0054 --------
0055
0056 The encoder calculates the Reed-Solomon code over the given data length
0057 and stores the result in the parity buffer. Note that the parity buffer
0058 must be initialized before calling the encoder.
0059
0060 The expanded data can be inverted on the fly by providing a non-zero
0061 inversion mask. The expanded data is XOR'ed with the mask. This is used
0062 e.g. for FLASH ECC, where the all 0xFF is inverted to an all 0x00. The
0063 Reed-Solomon code for all 0x00 is all 0x00. The code is inverted before
0064 storing to FLASH so it is 0xFF too. This prevents that reading from an
0065 erased FLASH results in ECC errors.
0066
0067 The databytes are expanded to the given symbol size on the fly. There is
0068 no support for encoding continuous bitstreams with a symbol size != 8 at
0069 the moment. If it is necessary it should be not a big deal to implement
0070 such functionality.
0071
0072 ::
0073
0074 /* Parity buffer. Size = number of roots */
0075 uint16_t par[6];
0076 /* Initialize the parity buffer */
0077 memset(par, 0, sizeof(par));
0078 /* Encode 512 byte in data8. Store parity in buffer par */
0079 encode_rs8 (rs_decoder, data8, 512, par, 0);
0080
0081
0082 Decoding
0083 --------
0084
0085 The decoder calculates the syndrome over the given data length and the
0086 received parity symbols and corrects errors in the data.
0087
0088 If a syndrome is available from a hardware decoder then the syndrome
0089 calculation is skipped.
0090
0091 The correction of the data buffer can be suppressed by providing a
0092 correction pattern buffer and an error location buffer to the decoder.
0093 The decoder stores the calculated error location and the correction
0094 bitmask in the given buffers. This is useful for hardware decoders which
0095 use a weird bit ordering scheme.
0096
0097 The databytes are expanded to the given symbol size on the fly. There is
0098 no support for decoding continuous bitstreams with a symbolsize != 8 at
0099 the moment. If it is necessary it should be not a big deal to implement
0100 such functionality.
0101
0102 Decoding with syndrome calculation, direct data correction
0103 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0104
0105 ::
0106
0107 /* Parity buffer. Size = number of roots */
0108 uint16_t par[6];
0109 uint8_t data[512];
0110 int numerr;
0111 /* Receive data */
0112 .....
0113 /* Receive parity */
0114 .....
0115 /* Decode 512 byte in data8.*/
0116 numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL);
0117
0118
0119 Decoding with syndrome given by hardware decoder, direct data correction
0120 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0121
0122 ::
0123
0124 /* Parity buffer. Size = number of roots */
0125 uint16_t par[6], syn[6];
0126 uint8_t data[512];
0127 int numerr;
0128 /* Receive data */
0129 .....
0130 /* Receive parity */
0131 .....
0132 /* Get syndrome from hardware decoder */
0133 .....
0134 /* Decode 512 byte in data8.*/
0135 numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL);
0136
0137
0138 Decoding with syndrome given by hardware decoder, no direct data correction.
0139 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0140
0141 Note: It's not necessary to give data and received parity to the
0142 decoder.
0143
0144 ::
0145
0146 /* Parity buffer. Size = number of roots */
0147 uint16_t par[6], syn[6], corr[8];
0148 uint8_t data[512];
0149 int numerr, errpos[8];
0150 /* Receive data */
0151 .....
0152 /* Receive parity */
0153 .....
0154 /* Get syndrome from hardware decoder */
0155 .....
0156 /* Decode 512 byte in data8.*/
0157 numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr);
0158 for (i = 0; i < numerr; i++) {
0159 do_error_correction_in_your_buffer(errpos[i], corr[i]);
0160 }
0161
0162
0163 Cleanup
0164 -------
0165
0166 The function free_rs frees the allocated resources, if the caller is
0167 the last user of the decoder.
0168
0169 ::
0170
0171 /* Release resources */
0172 free_rs(rs_decoder);
0173
0174
0175 Structures
0176 ==========
0177
0178 This chapter contains the autogenerated documentation of the structures
0179 which are used in the Reed-Solomon Library and are relevant for a
0180 developer.
0181
0182 .. kernel-doc:: include/linux/rslib.h
0183 :internal:
0184
0185 Public Functions Provided
0186 =========================
0187
0188 This chapter contains the autogenerated documentation of the
0189 Reed-Solomon functions which are exported.
0190
0191 .. kernel-doc:: lib/reed_solomon/reed_solomon.c
0192 :export:
0193
0194 Credits
0195 =======
0196
0197 The library code for encoding and decoding was written by Phil Karn.
0198
0199 ::
0200
0201 Copyright 2002, Phil Karn, KA9Q
0202 May be used under the terms of the GNU General Public License (GPL)
0203
0204
0205 The wrapper functions and interfaces are written by Thomas Gleixner.
0206
0207 Many users have provided bugfixes, improvements and helping hands for
0208 testing. Thanks a lot.
0209
0210 The following people have contributed to this document:
0211
0212 Thomas Gleixner\ tglx@linutronix.de
