linux/Documentation/DocBook/librs.tmpl
<<
>>
Prefs
   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
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.