From 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 16 Apr 2005 15:20:36 -0700 Subject: Linux-2.6.12-rc2 Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip! --- Documentation/DocBook/librs.tmpl | 289 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 289 insertions(+) create mode 100644 Documentation/DocBook/librs.tmpl (limited to 'Documentation/DocBook/librs.tmpl') diff --git a/Documentation/DocBook/librs.tmpl b/Documentation/DocBook/librs.tmpl new file mode 100644 index 00000000000..3ff39bafc00 --- /dev/null +++ b/Documentation/DocBook/librs.tmpl @@ -0,0 +1,289 @@ + + + + + + Reed-Solomon Library Programming Interface + + + + Thomas + Gleixner + +
+ tglx@linutronix.de +
+ + + + + + 2004 + Thomas Gleixner + + + + + This documentation is free software; you can redistribute + it and/or modify it under the terms of the GNU General Public + License version 2 as published by the Free Software Foundation. + + + + This program is distributed in the hope that it will be + useful, but WITHOUT ANY WARRANTY; without even the implied + warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the GNU General Public License for more details. + + + + You should have received a copy of the GNU General Public + License along with this program; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, + MA 02111-1307 USA + + + + For more details see the file COPYING in the source + distribution of Linux. + + + + + + + + Introduction + + The generic Reed-Solomon Library provides encoding, decoding + and error correction functions. + + + Reed-Solomon codes are used in communication and storage + applications to ensure data integrity. + + + This documentation is provided for developers who want to utilize + the functions provided by the library. + + + + + Known Bugs And Assumptions + + None. + + + + + Usage + + This chapter provides examples how to use the library. + + + Initializing + + The init function init_rs returns a pointer to a + rs decoder structure, which holds the necessary + information for encoding, decoding and error correction + with the given polynomial. It either uses an existing + matching decoder or creates a new one. On creation all + the lookup tables for fast en/decoding are created. + The function may take a while, so make sure not to + call it in critical code paths. + + +/* the Reed Solomon control structure */ +static struct rs_control *rs_decoder; + +/* Symbolsize is 10 (bits) + * Primitve polynomial is x^10+x^3+1 + * first consecutive root is 0 + * primitve element to generate roots = 1 + * generator polinomial degree (number of roots) = 6 + */ +rs_decoder = init_rs (10, 0x409, 0, 1, 6); + + + + Encoding + + The encoder calculates the Reed-Solomon code over + the given data length and stores the result in + the parity buffer. Note that the parity buffer must + be initialized before calling the encoder. + + + The expanded data can be inverted on the fly by + providing a non zero inversion mask. The expanded data is + XOR'ed with the mask. This is used e.g. for FLASH + ECC, where the all 0xFF is inverted to an all 0x00. + The Reed-Solomon code for all 0x00 is all 0x00. The + code is inverted before storing to FLASH so it is 0xFF + too. This prevent's that reading from an erased FLASH + results in ECC errors. + + + The databytes are expanded to the given symbol size + on the fly. There is no support for encoding continuous + bitstreams with a symbol size != 8 at the moment. If + it is necessary it should be not a big deal to implement + such functionality. + + +/* Parity buffer. Size = number of roots */ +uint16_t par[6]; +/* Initialize the parity buffer */ +memset(par, 0, sizeof(par)); +/* Encode 512 byte in data8. Store parity in buffer par */ +encode_rs8 (rs_decoder, data8, 512, par, 0); + + + + Decoding + + The decoder calculates the syndrome over + the given data length and the received parity symbols + and corrects errors in the data. + + + If a syndrome is available from a hardware decoder + then the syndrome calculation is skipped. + + + The correction of the data buffer can be suppressed + by providing a correction pattern buffer and an error + location buffer to the decoder. The decoder stores the + calculated error location and the correction bitmask + in the given buffers. This is useful for hardware + decoders which use a weird bit ordering scheme. + + + The databytes are expanded to the given symbol size + on the fly. There is no support for decoding continuous + bitstreams with a symbolsize != 8 at the moment. If + it is necessary it should be not a big deal to implement + such functionality. + + + + + Decoding with syndrome calculation, direct data correction + + +/* Parity buffer. Size = number of roots */ +uint16_t par[6]; +uint8_t data[512]; +int numerr; +/* Receive data */ +..... +/* Receive parity */ +..... +/* Decode 512 byte in data8.*/ +numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL); + + + + + + Decoding with syndrome given by hardware decoder, direct data correction + + +/* Parity buffer. Size = number of roots */ +uint16_t par[6], syn[6]; +uint8_t data[512]; +int numerr; +/* Receive data */ +..... +/* Receive parity */ +..... +/* Get syndrome from hardware decoder */ +..... +/* Decode 512 byte in data8.*/ +numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL); + + + + + + Decoding with syndrome given by hardware decoder, no direct data correction. + + + Note: It's not necessary to give data and received parity to the decoder. + + +/* Parity buffer. Size = number of roots */ +uint16_t par[6], syn[6], corr[8]; +uint8_t data[512]; +int numerr, errpos[8]; +/* Receive data */ +..... +/* Receive parity */ +..... +/* Get syndrome from hardware decoder */ +..... +/* Decode 512 byte in data8.*/ +numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr); +for (i = 0; i < numerr; i++) { + do_error_correction_in_your_buffer(errpos[i], corr[i]); +} + + + + + Cleanup + + The function free_rs frees the allocated resources, + if the caller is the last user of the decoder. + + +/* Release resources */ +free_rs(rs_decoder); + + + + + + + Structures + + This chapter contains the autogenerated documentation of the structures which are + used in the Reed-Solomon Library and are relevant for a developer. + +!Iinclude/linux/rslib.h + + + + Public Functions Provided + + This chapter contains the autogenerated documentation of the Reed-Solomon functions + which are exported. + +!Elib/reed_solomon/reed_solomon.c + + + + Credits + + The library code for encoding and decoding was written by Phil Karn. + + + Copyright 2002, Phil Karn, KA9Q + May be used under the terms of the GNU General Public License (GPL) + + + The wrapper functions and interfaces are written by Thomas Gleixner + + + Many users have provided bugfixes, improvements and helping hands for testing. + Thanks a lot. + + + The following people have contributed to this document: + + + Thomas Gleixnertglx@linutronix.de + + + -- cgit v1.2.3