Commit | Line | Data |
---|---|---|
8aba7848 MCC |
1 | ========================================== |
2 | Reed-Solomon Library Programming Interface | |
3 | ========================================== | |
4 | ||
5 | :Author: Thomas Gleixner | |
6 | ||
7 | Introduction | |
8 | ============ | |
9 | ||
10 | The generic Reed-Solomon Library provides encoding, decoding and error | |
11 | correction functions. | |
12 | ||
13 | Reed-Solomon codes are used in communication and storage applications to | |
14 | ensure data integrity. | |
15 | ||
16 | This documentation is provided for developers who want to utilize the | |
17 | functions provided by the library. | |
18 | ||
19 | Known Bugs And Assumptions | |
20 | ========================== | |
21 | ||
22 | None. | |
23 | ||
24 | Usage | |
25 | ===== | |
26 | ||
27 | This chapter provides examples of how to use the library. | |
28 | ||
29 | Initializing | |
30 | ------------ | |
31 | ||
32 | The init function init_rs returns a pointer to an rs decoder structure, | |
33 | which holds the necessary information for encoding, decoding and error | |
34 | correction with the given polynomial. It either uses an existing | |
35 | matching decoder or creates a new one. On creation all the lookup tables | |
36 | for fast en/decoding are created. The function may take a while, so make | |
37 | sure not to call it in critical code paths. | |
38 | ||
39 | :: | |
40 | ||
41 | /* the Reed Solomon control structure */ | |
42 | static struct rs_control *rs_decoder; | |
43 | ||
44 | /* Symbolsize is 10 (bits) | |
45 | * Primitive polynomial is x^10+x^3+1 | |
46 | * first consecutive root is 0 | |
47 | * primitive element to generate roots = 1 | |
48 | * generator polynomial degree (number of roots) = 6 | |
49 | */ | |
50 | rs_decoder = init_rs (10, 0x409, 0, 1, 6); | |
51 | ||
52 | ||
53 | Encoding | |
54 | -------- | |
55 | ||
56 | The encoder calculates the Reed-Solomon code over the given data length | |
57 | and stores the result in the parity buffer. Note that the parity buffer | |
58 | must be initialized before calling the encoder. | |
59 | ||
60 | The expanded data can be inverted on the fly by providing a non-zero | |
61 | inversion mask. The expanded data is XOR'ed with the mask. This is used | |
62 | e.g. for FLASH ECC, where the all 0xFF is inverted to an all 0x00. The | |
63 | Reed-Solomon code for all 0x00 is all 0x00. The code is inverted before | |
64 | storing to FLASH so it is 0xFF too. This prevents that reading from an | |
65 | erased FLASH results in ECC errors. | |
66 | ||
67 | The databytes are expanded to the given symbol size on the fly. There is | |
68 | no support for encoding continuous bitstreams with a symbol size != 8 at | |
69 | the moment. If it is necessary it should be not a big deal to implement | |
70 | such functionality. | |
71 | ||
72 | :: | |
73 | ||
74 | /* Parity buffer. Size = number of roots */ | |
75 | uint16_t par[6]; | |
76 | /* Initialize the parity buffer */ | |
77 | memset(par, 0, sizeof(par)); | |
78 | /* Encode 512 byte in data8. Store parity in buffer par */ | |
79 | encode_rs8 (rs_decoder, data8, 512, par, 0); | |
80 | ||
81 | ||
82 | Decoding | |
83 | -------- | |
84 | ||
85 | The decoder calculates the syndrome over the given data length and the | |
86 | received parity symbols and corrects errors in the data. | |
87 | ||
88 | If a syndrome is available from a hardware decoder then the syndrome | |
89 | calculation is skipped. | |
90 | ||
91 | The correction of the data buffer can be suppressed by providing a | |
92 | correction pattern buffer and an error location buffer to the decoder. | |
93 | The decoder stores the calculated error location and the correction | |
94 | bitmask in the given buffers. This is useful for hardware decoders which | |
95 | use a weird bit ordering scheme. | |
96 | ||
97 | The databytes are expanded to the given symbol size on the fly. There is | |
98 | no support for decoding continuous bitstreams with a symbolsize != 8 at | |
99 | the moment. If it is necessary it should be not a big deal to implement | |
100 | such functionality. | |
101 | ||
102 | Decoding with syndrome calculation, direct data correction | |
103 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
104 | ||
105 | :: | |
106 | ||
107 | /* Parity buffer. Size = number of roots */ | |
108 | uint16_t par[6]; | |
109 | uint8_t data[512]; | |
110 | int numerr; | |
111 | /* Receive data */ | |
112 | ..... | |
113 | /* Receive parity */ | |
114 | ..... | |
115 | /* Decode 512 byte in data8.*/ | |
116 | numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL); | |
117 | ||
118 | ||
119 | Decoding with syndrome given by hardware decoder, direct data correction | |
120 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
121 | ||
122 | :: | |
123 | ||
124 | /* Parity buffer. Size = number of roots */ | |
125 | uint16_t par[6], syn[6]; | |
126 | uint8_t data[512]; | |
127 | int numerr; | |
128 | /* Receive data */ | |
129 | ..... | |
130 | /* Receive parity */ | |
131 | ..... | |
132 | /* Get syndrome from hardware decoder */ | |
133 | ..... | |
134 | /* Decode 512 byte in data8.*/ | |
135 | numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL); | |
136 | ||
137 | ||
138 | Decoding with syndrome given by hardware decoder, no direct data correction. | |
139 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | |
140 | ||
141 | Note: It's not necessary to give data and received parity to the | |
142 | decoder. | |
143 | ||
144 | :: | |
145 | ||
146 | /* Parity buffer. Size = number of roots */ | |
147 | uint16_t par[6], syn[6], corr[8]; | |
148 | uint8_t data[512]; | |
149 | int numerr, errpos[8]; | |
150 | /* Receive data */ | |
151 | ..... | |
152 | /* Receive parity */ | |
153 | ..... | |
154 | /* Get syndrome from hardware decoder */ | |
155 | ..... | |
156 | /* Decode 512 byte in data8.*/ | |
157 | numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr); | |
158 | for (i = 0; i < numerr; i++) { | |
159 | do_error_correction_in_your_buffer(errpos[i], corr[i]); | |
160 | } | |
161 | ||
162 | ||
163 | Cleanup | |
164 | ------- | |
165 | ||
166 | The function free_rs frees the allocated resources, if the caller is | |
167 | the last user of the decoder. | |
168 | ||
169 | :: | |
170 | ||
171 | /* Release resources */ | |
172 | free_rs(rs_decoder); | |
173 | ||
174 | ||
175 | Structures | |
176 | ========== | |
177 | ||
178 | This chapter contains the autogenerated documentation of the structures | |
179 | which are used in the Reed-Solomon Library and are relevant for a | |
180 | developer. | |
181 | ||
182 | .. kernel-doc:: include/linux/rslib.h | |
183 | :internal: | |
184 | ||
185 | Public Functions Provided | |
186 | ========================= | |
187 | ||
188 | This chapter contains the autogenerated documentation of the | |
189 | Reed-Solomon functions which are exported. | |
190 | ||
191 | .. kernel-doc:: lib/reed_solomon/reed_solomon.c | |
192 | :export: | |
193 | ||
194 | Credits | |
195 | ======= | |
196 | ||
197 | The library code for encoding and decoding was written by Phil Karn. | |
198 | ||
199 | :: | |
200 | ||
201 | Copyright 2002, Phil Karn, KA9Q | |
202 | May be used under the terms of the GNU General Public License (GPL) | |
203 | ||
204 | ||
205 | The wrapper functions and interfaces are written by Thomas Gleixner. | |
206 | ||
207 | Many users have provided bugfixes, improvements and helping hands for | |
208 | testing. Thanks a lot. | |
209 | ||
210 | The following people have contributed to this document: | |
211 | ||
212 | Thomas Gleixner\ tglx@linutronix.de |