From 437aa565e2656776a7104aaacd792fe789ea8b2d Mon Sep 17 00:00:00 2001 From: Ivan Djelic Date: Fri, 11 Mar 2011 11:05:32 +0100 Subject: lib: add shared BCH ECC library MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This is a new software BCH encoding/decoding library, similar to the shared Reed-Solomon library. Binary BCH (Bose-Chaudhuri-Hocquenghem) codes are widely used to correct errors in NAND flash devices requiring more than 1-bit ecc correction; they are generally better suited for NAND flash than RS codes because NAND bit errors do not occur in bursts. Latest SLC NAND devices typically require at least 4-bit ecc protection per 512 bytes block. This library provides software encoding/decoding, but may also be used with ASIC/SoC hardware BCH engines to perform error correction. It is being currently used for this purpose on an OMAP3630 board (4bit/8bit HW BCH). It has also been used to decode raw dumps of NAND devices with on-die BCH ecc engines (e.g. Micron 4bit ecc SLC devices). Latest NAND devices (including SLC) can exhibit high error rates (typically a dozen or more bitflips per hour during stress tests); in order to minimize the performance impact of error correction, this library implements recently developed algorithms for fast polynomial root finding (see bch.c header for details) instead of the traditional exhaustive Chien root search; a few performance figures are provided below: Platform: arm926ejs @ 468 MHz, 32 KiB icache, 16 KiB dcache BCH ecc : 4-bit per 512 bytes Encoding average throughput: 250 Mbits/s Error correction time (compared with Chien search): average worst average (Chien) worst (Chien) ---------------------------------------------------------- 1 bit 8.5 µs 11 µs 200 µs 383 µs 2 bit 9.7 µs 12.5 µs 477 µs 728 µs 3 bit 18.1 µs 20.6 µs 758 µs 1010 µs 4 bit 19.5 µs 23 µs 1028 µs 1280 µs In the above figures, "worst" is meant in terms of error pattern, not in terms of cache miss / page faults effects (not taken into account here). The library has been extensively tested on the following platforms: x86, x86_64, arm926ejs, omap3630, qemu-ppc64, qemu-mips. Signed-off-by: Ivan Djelic Signed-off-by: David Woodhouse --- lib/Kconfig | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) (limited to 'lib/Kconfig') diff --git a/lib/Kconfig b/lib/Kconfig index 0ee67e08ad3e..b9fef78ed04f 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -154,6 +154,45 @@ config REED_SOLOMON_ENC16 config REED_SOLOMON_DEC16 boolean +# +# BCH support is selected if needed +# +config BCH + tristate + +config BCH_CONST_PARAMS + boolean + help + Drivers may select this option to force specific constant + values for parameters 'm' (Galois field order) and 't' + (error correction capability). Those specific values must + be set by declaring default values for symbols BCH_CONST_M + and BCH_CONST_T. + Doing so will enable extra compiler optimizations, + improving encoding and decoding performance up to 2x for + usual (m,t) values (typically such that m*t < 200). + When this option is selected, the BCH library supports + only a single (m,t) configuration. This is mainly useful + for NAND flash board drivers requiring known, fixed BCH + parameters. + +config BCH_CONST_M + int + range 5 15 + help + Constant value for Galois field order 'm'. If 'k' is the + number of data bits to protect, 'm' should be chosen such + that (k + m*t) <= 2**m - 1. + Drivers should declare a default value for this symbol if + they select option BCH_CONST_PARAMS. + +config BCH_CONST_T + int + help + Constant value for error correction capability in bits 't'. + Drivers should declare a default value for this symbol if + they select option BCH_CONST_PARAMS. + # # Textsearch support is select'ed if needed # -- cgit v1.2.3