Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | <?xml version="1.0" encoding="UTF-8"?> |
2 | <!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.1.2//EN" | |
3 | "http://www.oasis-open.org/docbook/xml/4.1.2/docbookx.dtd" []> | |
4 | ||
5 | <book id="Reed-Solomon-Library-Guide"> | |
6 | <bookinfo> | |
7 | <title>Reed-Solomon Library Programming Interface</title> | |
8 | ||
9 | <authorgroup> | |
10 | <author> | |
11 | <firstname>Thomas</firstname> | |
12 | <surname>Gleixner</surname> | |
13 | <affiliation> | |
14 | <address> | |
15 | <email>tglx@linutronix.de</email> | |
16 | </address> | |
17 | </affiliation> | |
18 | </author> | |
19 | </authorgroup> | |
20 | ||
21 | <copyright> | |
22 | <year>2004</year> | |
23 | <holder>Thomas Gleixner</holder> | |
24 | </copyright> | |
25 | ||
26 | <legalnotice> | |
27 | <para> | |
28 | This documentation is free software; you can redistribute | |
29 | it and/or modify it under the terms of the GNU General Public | |
30 | License version 2 as published by the Free Software Foundation. | |
31 | </para> | |
32 | ||
33 | <para> | |
34 | This program is distributed in the hope that it will be | |
35 | useful, but WITHOUT ANY WARRANTY; without even the implied | |
36 | warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
37 | See the GNU General Public License for more details. | |
38 | </para> | |
39 | ||
40 | <para> | |
41 | You should have received a copy of the GNU General Public | |
42 | License along with this program; if not, write to the Free | |
43 | Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, | |
44 | MA 02111-1307 USA | |
45 | </para> | |
46 | ||
47 | <para> | |
48 | For more details see the file COPYING in the source | |
49 | distribution of Linux. | |
50 | </para> | |
51 | </legalnotice> | |
52 | </bookinfo> | |
53 | ||
54 | <toc></toc> | |
55 | ||
56 | <chapter id="intro"> | |
57 | <title>Introduction</title> | |
58 | <para> | |
59 | The generic Reed-Solomon Library provides encoding, decoding | |
60 | and error correction functions. | |
61 | </para> | |
62 | <para> | |
63 | Reed-Solomon codes are used in communication and storage | |
64 | applications to ensure data integrity. | |
65 | </para> | |
66 | <para> | |
67 | This documentation is provided for developers who want to utilize | |
68 | the functions provided by the library. | |
69 | </para> | |
70 | </chapter> | |
71 | ||
72 | <chapter id="bugs"> | |
73 | <title>Known Bugs And Assumptions</title> | |
74 | <para> | |
75 | None. | |
76 | </para> | |
77 | </chapter> | |
78 | ||
79 | <chapter id="usage"> | |
80 | <title>Usage</title> | |
81 | <para> | |
82 | This chapter provides examples how to use the library. | |
83 | </para> | |
84 | <sect1> | |
85 | <title>Initializing</title> | |
86 | <para> | |
87 | The init function init_rs returns a pointer to a | |
88 | rs decoder structure, which holds the necessary | |
89 | information for encoding, decoding and error correction | |
90 | with the given polynomial. It either uses an existing | |
91 | matching decoder or creates a new one. On creation all | |
92 | the lookup tables for fast en/decoding are created. | |
93 | The function may take a while, so make sure not to | |
94 | call it in critical code paths. | |
95 | </para> | |
96 | <programlisting> | |
97 | /* the Reed Solomon control structure */ | |
98 | static struct rs_control *rs_decoder; | |
99 | ||
100 | /* Symbolsize is 10 (bits) | |
101 | * Primitve polynomial is x^10+x^3+1 | |
102 | * first consecutive root is 0 | |
103 | * primitve element to generate roots = 1 | |
104 | * generator polinomial degree (number of roots) = 6 | |
105 | */ | |
106 | rs_decoder = init_rs (10, 0x409, 0, 1, 6); | |
107 | </programlisting> | |
108 | </sect1> | |
109 | <sect1> | |
110 | <title>Encoding</title> | |
111 | <para> | |
112 | The encoder calculates the Reed-Solomon code over | |
113 | the given data length and stores the result in | |
114 | the parity buffer. Note that the parity buffer must | |
115 | be initialized before calling the encoder. | |
116 | </para> | |
117 | <para> | |
118 | The expanded data can be inverted on the fly by | |
119 | providing a non zero inversion mask. The expanded data is | |
120 | XOR'ed with the mask. This is used e.g. for FLASH | |
121 | ECC, where the all 0xFF is inverted to an all 0x00. | |
122 | The Reed-Solomon code for all 0x00 is all 0x00. The | |
123 | code is inverted before storing to FLASH so it is 0xFF | |
124 | too. This prevent's that reading from an erased FLASH | |
125 | results in ECC errors. | |
126 | </para> | |
127 | <para> | |
128 | The databytes are expanded to the given symbol size | |
129 | on the fly. There is no support for encoding continuous | |
130 | bitstreams with a symbol size != 8 at the moment. If | |
131 | it is necessary it should be not a big deal to implement | |
132 | such functionality. | |
133 | </para> | |
134 | <programlisting> | |
135 | /* Parity buffer. Size = number of roots */ | |
136 | uint16_t par[6]; | |
137 | /* Initialize the parity buffer */ | |
138 | memset(par, 0, sizeof(par)); | |
139 | /* Encode 512 byte in data8. Store parity in buffer par */ | |
140 | encode_rs8 (rs_decoder, data8, 512, par, 0); | |
141 | </programlisting> | |
142 | </sect1> | |
143 | <sect1> | |
144 | <title>Decoding</title> | |
145 | <para> | |
146 | The decoder calculates the syndrome over | |
147 | the given data length and the received parity symbols | |
148 | and corrects errors in the data. | |
149 | </para> | |
150 | <para> | |
151 | If a syndrome is available from a hardware decoder | |
152 | then the syndrome calculation is skipped. | |
153 | </para> | |
154 | <para> | |
155 | The correction of the data buffer can be suppressed | |
156 | by providing a correction pattern buffer and an error | |
157 | location buffer to the decoder. The decoder stores the | |
158 | calculated error location and the correction bitmask | |
159 | in the given buffers. This is useful for hardware | |
160 | decoders which use a weird bit ordering scheme. | |
161 | </para> | |
162 | <para> | |
163 | The databytes are expanded to the given symbol size | |
164 | on the fly. There is no support for decoding continuous | |
165 | bitstreams with a symbolsize != 8 at the moment. If | |
166 | it is necessary it should be not a big deal to implement | |
167 | such functionality. | |
168 | </para> | |
169 | ||
170 | <sect2> | |
171 | <title> | |
172 | Decoding with syndrome calculation, direct data correction | |
173 | </title> | |
174 | <programlisting> | |
175 | /* Parity buffer. Size = number of roots */ | |
176 | uint16_t par[6]; | |
177 | uint8_t data[512]; | |
178 | int numerr; | |
179 | /* Receive data */ | |
180 | ..... | |
181 | /* Receive parity */ | |
182 | ..... | |
183 | /* Decode 512 byte in data8.*/ | |
184 | numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL); | |
185 | </programlisting> | |
186 | </sect2> | |
187 | ||
188 | <sect2> | |
189 | <title> | |
190 | Decoding with syndrome given by hardware decoder, direct data correction | |
191 | </title> | |
192 | <programlisting> | |
193 | /* Parity buffer. Size = number of roots */ | |
194 | uint16_t par[6], syn[6]; | |
195 | uint8_t data[512]; | |
196 | int numerr; | |
197 | /* Receive data */ | |
198 | ..... | |
199 | /* Receive parity */ | |
200 | ..... | |
201 | /* Get syndrome from hardware decoder */ | |
202 | ..... | |
203 | /* Decode 512 byte in data8.*/ | |
204 | numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL); | |
205 | </programlisting> | |
206 | </sect2> | |
207 | ||
208 | <sect2> | |
209 | <title> | |
210 | Decoding with syndrome given by hardware decoder, no direct data correction. | |
211 | </title> | |
212 | <para> | |
213 | Note: It's not necessary to give data and received parity to the decoder. | |
214 | </para> | |
215 | <programlisting> | |
216 | /* Parity buffer. Size = number of roots */ | |
217 | uint16_t par[6], syn[6], corr[8]; | |
218 | uint8_t data[512]; | |
219 | int numerr, errpos[8]; | |
220 | /* Receive data */ | |
221 | ..... | |
222 | /* Receive parity */ | |
223 | ..... | |
224 | /* Get syndrome from hardware decoder */ | |
225 | ..... | |
226 | /* Decode 512 byte in data8.*/ | |
227 | numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr); | |
228 | for (i = 0; i < numerr; i++) { | |
229 | do_error_correction_in_your_buffer(errpos[i], corr[i]); | |
230 | } | |
231 | </programlisting> | |
232 | </sect2> | |
233 | </sect1> | |
234 | <sect1> | |
235 | <title>Cleanup</title> | |
236 | <para> | |
237 | The function free_rs frees the allocated resources, | |
238 | if the caller is the last user of the decoder. | |
239 | </para> | |
240 | <programlisting> | |
241 | /* Release resources */ | |
242 | free_rs(rs_decoder); | |
243 | </programlisting> | |
244 | </sect1> | |
245 | ||
246 | </chapter> | |
247 | ||
248 | <chapter id="structs"> | |
249 | <title>Structures</title> | |
250 | <para> | |
251 | This chapter contains the autogenerated documentation of the structures which are | |
252 | used in the Reed-Solomon Library and are relevant for a developer. | |
253 | </para> | |
254 | !Iinclude/linux/rslib.h | |
255 | </chapter> | |
256 | ||
257 | <chapter id="pubfunctions"> | |
258 | <title>Public Functions Provided</title> | |
259 | <para> | |
260 | This chapter contains the autogenerated documentation of the Reed-Solomon functions | |
261 | which are exported. | |
262 | </para> | |
263 | !Elib/reed_solomon/reed_solomon.c | |
264 | </chapter> | |
265 | ||
266 | <chapter id="credits"> | |
267 | <title>Credits</title> | |
268 | <para> | |
269 | The library code for encoding and decoding was written by Phil Karn. | |
270 | </para> | |
271 | <programlisting> | |
272 | Copyright 2002, Phil Karn, KA9Q | |
273 | May be used under the terms of the GNU General Public License (GPL) | |
274 | </programlisting> | |
275 | <para> | |
276 | The wrapper functions and interfaces are written by Thomas Gleixner | |
277 | </para> | |
278 | <para> | |
279 | Many users have provided bugfixes, improvements and helping hands for testing. | |
280 | Thanks a lot. | |
281 | </para> | |
282 | <para> | |
283 | The following people have contributed to this document: | |
284 | </para> | |
285 | <para> | |
286 | Thomas Gleixner<email>tglx@linutronix.de</email> | |
287 | </para> | |
288 | </chapter> | |
289 | </book> |