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 of 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 an
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 */
98static struct rs_control *rs_decoder;
99
100/* Symbolsize is 10 (bits)
101 * Primitive polynomial is x^10+x^3+1
102 * first consecutive root is 0
103 * primitive element to generate roots = 1
104 * generator polynomial degree (number of roots) = 6
105 */
106rs_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 prevents 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 */
136uint16_t par[6];
137/* Initialize the parity buffer */
138memset(par, 0, sizeof(par));
139/* Encode 512 byte in data8. Store parity in buffer par */
140encode_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 */
176uint16_t par[6];
177uint8_t  data[512];
178int numerr;
179/* Receive data */
180.....
181/* Receive parity */
182.....
183/* Decode 512 byte in data8.*/
184numerr = 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 */
194uint16_t par[6], syn[6];
195uint8_t  data[512];
196int numerr;
197/* Receive data */
198.....
199/* Receive parity */
200.....
201/* Get syndrome from hardware decoder */
202.....
203/* Decode 512 byte in data8.*/
204numerr = 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 */
217uint16_t par[6], syn[6], corr[8];
218uint8_t  data[512];
219int numerr, errpos[8];
220/* Receive data */
221.....
222/* Receive parity */
223.....
224/* Get syndrome from hardware decoder */
225.....
226/* Decode 512 byte in data8.*/
227numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr);
228for (i = 0; i &lt; 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 */
242free_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>
290