Documentation/DocBook/librs.tmpl

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