From c7519dbf6f4b4408229d279d799c938ffdd06f21 Mon Sep 17 00:00:00 2001 From: Jarkko Lavinen Date: Mon, 14 Feb 2011 16:16:09 +0200 Subject: mtd_blkdevs: Add background processing support Add a new background method into mtd_blktrans_ops, add background support into mtd_blktrans_thread(), and add mtd_blktrans_cease_background(). If the mtd blktrans dev has the background support, the thread will call background function when the request queue becomes empty. The background operation may run as long as needs to until mtd_blktrans_cease_background() tells to stop. Signed-off-by: Jarkko Lavinen Tested-by: Artem Bityutskiy Signed-off-by: David Woodhouse --- include/linux/mtd/blktrans.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'include') diff --git a/include/linux/mtd/blktrans.h b/include/linux/mtd/blktrans.h index 26529ebd59cc..66bec4bf2b0a 100644 --- a/include/linux/mtd/blktrans.h +++ b/include/linux/mtd/blktrans.h @@ -62,6 +62,7 @@ struct mtd_blktrans_ops { unsigned long block, char *buffer); int (*discard)(struct mtd_blktrans_dev *dev, unsigned long block, unsigned nr_blocks); + void (*background)(struct mtd_blktrans_dev *dev); /* Block layer ioctls */ int (*getgeo)(struct mtd_blktrans_dev *dev, struct hd_geometry *geo); @@ -85,6 +86,7 @@ extern int register_mtd_blktrans(struct mtd_blktrans_ops *tr); extern int deregister_mtd_blktrans(struct mtd_blktrans_ops *tr); extern int add_mtd_blktrans_dev(struct mtd_blktrans_dev *dev); extern int del_mtd_blktrans_dev(struct mtd_blktrans_dev *dev); +extern int mtd_blktrans_cease_background(struct mtd_blktrans_dev *dev); #endif /* __MTD_TRANS_H__ */ -- cgit v1.2.3 From dcfb81d61da1367e52f7f7e3ceff0d0044c3c7ee Mon Sep 17 00:00:00 2001 From: David Griego Date: Tue, 30 Nov 2010 15:32:05 +0530 Subject: mtd: NOR flash driver for OMAP-L137/AM17x OMAP-L137/AM17x has limited number of dedicated EMIFA address pins, enough to interface directly to an SDRAM. If a device such as an asynchronous flash needs to be attached to the EMIFA, then either GPIO pins or a chip select may be used to control the flash device's upper address lines. This patch adds support for the NOR flash on the OMAP-L137/ AM17x user interface daughter board using the latch-addr-flash MTD mapping driver which allows flashes to be partially physically addressed. The upper address lines are set by a board specific code which is a separate patch. Signed-off-by: David Griego Signed-off-by: Aleksey Makarov Signed-off-by: Sergei Shtylyov Signed-off-by: Savinay Dharmappa Signed-off-by: Artem Bityutskiy Signed-off-by: David Woodhouse --- drivers/mtd/maps/Kconfig | 9 ++ drivers/mtd/maps/Makefile | 1 + drivers/mtd/maps/latch-addr-flash.c | 272 +++++++++++++++++++++++++++++++++++ include/linux/mtd/latch-addr-flash.h | 29 ++++ 4 files changed, 311 insertions(+) create mode 100644 drivers/mtd/maps/latch-addr-flash.c create mode 100644 include/linux/mtd/latch-addr-flash.h (limited to 'include') diff --git a/drivers/mtd/maps/Kconfig b/drivers/mtd/maps/Kconfig index 803072a71ed7..44b1f46458ca 100644 --- a/drivers/mtd/maps/Kconfig +++ b/drivers/mtd/maps/Kconfig @@ -552,4 +552,13 @@ config MTD_PISMO When built as a module, it will be called pismo.ko +config MTD_LATCH_ADDR + tristate "Latch-assisted Flash Chip Support" + depends on MTD_COMPLEX_MAPPINGS + help + Map driver which allows flashes to be partially physically addressed + and have the upper address lines set by a board specific code. + + If compiled as a module, it will be called latch-addr-flash. + endmenu diff --git a/drivers/mtd/maps/Makefile b/drivers/mtd/maps/Makefile index c7869c7a6b18..08533bd5cba7 100644 --- a/drivers/mtd/maps/Makefile +++ b/drivers/mtd/maps/Makefile @@ -59,3 +59,4 @@ obj-$(CONFIG_MTD_RBTX4939) += rbtx4939-flash.o obj-$(CONFIG_MTD_VMU) += vmu-flash.o obj-$(CONFIG_MTD_GPIO_ADDR) += gpio-addr-flash.o obj-$(CONFIG_MTD_BCM963XX) += bcm963xx-flash.o +obj-$(CONFIG_MTD_LATCH_ADDR) += latch-addr-flash.o diff --git a/drivers/mtd/maps/latch-addr-flash.c b/drivers/mtd/maps/latch-addr-flash.c new file mode 100644 index 000000000000..ee2548085334 --- /dev/null +++ b/drivers/mtd/maps/latch-addr-flash.c @@ -0,0 +1,272 @@ +/* + * Interface for NOR flash driver whose high address lines are latched + * + * Copyright © 2000 Nicolas Pitre + * Copyright © 2005-2008 Analog Devices Inc. + * Copyright © 2008 MontaVista Software, Inc. + * + * This file is licensed under the terms of the GNU General Public License + * version 2. This program is licensed "as is" without any warranty of any + * kind, whether express or implied. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define DRIVER_NAME "latch-addr-flash" + +struct latch_addr_flash_info { + struct mtd_info *mtd; + struct map_info map; + struct resource *res; + + void (*set_window)(unsigned long offset, void *data); + void *data; + + /* cache; could be found out of res */ + unsigned long win_mask; + + int nr_parts; + struct mtd_partition *parts; + + spinlock_t lock; +}; + +static map_word lf_read(struct map_info *map, unsigned long ofs) +{ + struct latch_addr_flash_info *info; + map_word datum; + + info = (struct latch_addr_flash_info *)map->map_priv_1; + + spin_lock(&info->lock); + + info->set_window(ofs, info->data); + datum = inline_map_read(map, info->win_mask & ofs); + + spin_unlock(&info->lock); + + return datum; +} + +static void lf_write(struct map_info *map, map_word datum, unsigned long ofs) +{ + struct latch_addr_flash_info *info; + + info = (struct latch_addr_flash_info *)map->map_priv_1; + + spin_lock(&info->lock); + + info->set_window(ofs, info->data); + inline_map_write(map, datum, info->win_mask & ofs); + + spin_unlock(&info->lock); +} + +static void lf_copy_from(struct map_info *map, void *to, + unsigned long from, ssize_t len) +{ + struct latch_addr_flash_info *info = + (struct latch_addr_flash_info *) map->map_priv_1; + unsigned n; + + while (len > 0) { + n = info->win_mask + 1 - (from & info->win_mask); + if (n > len) + n = len; + + spin_lock(&info->lock); + + info->set_window(from, info->data); + memcpy_fromio(to, map->virt + (from & info->win_mask), n); + + spin_unlock(&info->lock); + + to += n; + from += n; + len -= n; + } +} + +static char *rom_probe_types[] = { "cfi_probe", NULL }; + +static char *part_probe_types[] = { "cmdlinepart", NULL }; + +static int latch_addr_flash_remove(struct platform_device *dev) +{ + struct latch_addr_flash_info *info; + struct latch_addr_flash_data *latch_addr_data; + + info = platform_get_drvdata(dev); + if (info == NULL) + return 0; + platform_set_drvdata(dev, NULL); + + latch_addr_data = dev->dev.platform_data; + + if (info->mtd != NULL) { + if (mtd_has_partitions()) { + if (info->nr_parts) { + del_mtd_partitions(info->mtd); + kfree(info->parts); + } else if (latch_addr_data->nr_parts) { + del_mtd_partitions(info->mtd); + } else { + del_mtd_device(info->mtd); + } + } else { + del_mtd_device(info->mtd); + } + map_destroy(info->mtd); + } + + if (info->map.virt != NULL) + iounmap(info->map.virt); + + if (info->res != NULL) + release_mem_region(info->res->start, resource_size(info->res)); + + kfree(info); + + if (latch_addr_data->done) + latch_addr_data->done(latch_addr_data->data); + + return 0; +} + +static int __devinit latch_addr_flash_probe(struct platform_device *dev) +{ + struct latch_addr_flash_data *latch_addr_data; + struct latch_addr_flash_info *info; + resource_size_t win_base = dev->resource->start; + resource_size_t win_size = resource_size(dev->resource); + char **probe_type; + int chipsel; + int err; + + latch_addr_data = dev->dev.platform_data; + if (latch_addr_data == NULL) + return -ENODEV; + + pr_notice("latch-addr platform flash device: %#llx byte " + "window at %#.8llx\n", + (unsigned long long)win_size, (unsigned long long)win_base); + + chipsel = dev->id; + + if (latch_addr_data->init) { + err = latch_addr_data->init(latch_addr_data->data, chipsel); + if (err != 0) + return err; + } + + info = kzalloc(sizeof(struct latch_addr_flash_info), GFP_KERNEL); + if (info == NULL) { + err = -ENOMEM; + goto done; + } + + platform_set_drvdata(dev, info); + + info->res = request_mem_region(win_base, win_size, DRIVER_NAME); + if (info->res == NULL) { + dev_err(&dev->dev, "Could not reserve memory region\n"); + err = -EBUSY; + goto free_info; + } + + info->map.name = DRIVER_NAME; + info->map.size = latch_addr_data->size; + info->map.bankwidth = latch_addr_data->width; + + info->map.phys = NO_XIP; + info->map.virt = ioremap(win_base, win_size); + if (!info->map.virt) { + err = -ENOMEM; + goto free_res; + } + + info->map.map_priv_1 = (unsigned long)info; + + info->map.read = lf_read; + info->map.copy_from = lf_copy_from; + info->map.write = lf_write; + info->set_window = latch_addr_data->set_window; + info->data = latch_addr_data->data; + info->win_mask = win_size - 1; + + spin_lock_init(&info->lock); + + for (probe_type = rom_probe_types; !info->mtd && *probe_type; + probe_type++) + info->mtd = do_map_probe(*probe_type, &info->map); + + if (info->mtd == NULL) { + dev_err(&dev->dev, "map_probe failed\n"); + err = -ENODEV; + goto iounmap; + } + info->mtd->owner = THIS_MODULE; + + if (mtd_has_partitions()) { + + err = parse_mtd_partitions(info->mtd, + (const char **)part_probe_types, + &info->parts, 0); + if (err > 0) { + add_mtd_partitions(info->mtd, info->parts, err); + return 0; + } + if (latch_addr_data->nr_parts) { + pr_notice("Using latch-addr-flash partition information\n"); + add_mtd_partitions(info->mtd, latch_addr_data->parts, + latch_addr_data->nr_parts); + return 0; + } + } + add_mtd_device(info->mtd); + return 0; + +iounmap: + iounmap(info->map.virt); +free_res: + release_mem_region(info->res->start, resource_size(info->res)); +free_info: + kfree(info); +done: + if (latch_addr_data->done) + latch_addr_data->done(latch_addr_data->data); + return err; +} + +static struct platform_driver latch_addr_flash_driver = { + .probe = latch_addr_flash_probe, + .remove = __devexit_p(latch_addr_flash_remove), + .driver = { + .name = DRIVER_NAME, + }, +}; + +static int __init latch_addr_flash_init(void) +{ + return platform_driver_register(&latch_addr_flash_driver); +} +module_init(latch_addr_flash_init); + +static void __exit latch_addr_flash_exit(void) +{ + platform_driver_unregister(&latch_addr_flash_driver); +} +module_exit(latch_addr_flash_exit); + +MODULE_AUTHOR("David Griego "); +MODULE_DESCRIPTION("MTD map driver for flashes addressed physically with upper " + "address lines being set board specifically"); +MODULE_LICENSE("GPL v2"); diff --git a/include/linux/mtd/latch-addr-flash.h b/include/linux/mtd/latch-addr-flash.h new file mode 100644 index 000000000000..e94b8e128074 --- /dev/null +++ b/include/linux/mtd/latch-addr-flash.h @@ -0,0 +1,29 @@ +/* + * Interface for NOR flash driver whose high address lines are latched + * + * Copyright © 2008 MontaVista Software, Inc. + * + * This file is licensed under the terms of the GNU General Public License + * version 2. This program is licensed "as is" without any warranty of any + * kind, whether express or implied. + */ +#ifndef __LATCH_ADDR_FLASH__ +#define __LATCH_ADDR_FLASH__ + +struct map_info; +struct mtd_partition; + +struct latch_addr_flash_data { + unsigned int width; + unsigned int size; + + int (*init)(void *data, int cs); + void (*done)(void *data); + void (*set_window)(unsigned long offset, void *data); + void *data; + + unsigned int nr_parts; + struct mtd_partition *parts; +}; + +#endif -- cgit v1.2.3 From b3dcfd35244e1cb8dc8dfa5c05013b133dbb437a Mon Sep 17 00:00:00 2001 From: Roman Tereshonkov Date: Thu, 17 Feb 2011 13:44:41 +0200 Subject: mtd: onenand: add new option to control initial onenand unlocking A new option ONENAND_SKIP_INITIAL_UNLOCKING is added. This allows to disable initial onenand unlocking when the driver is initialized. Signed-off-by: Roman Tereshonkov Signed-off-by: Artem Bityutskiy Signed-off-by: David Woodhouse --- drivers/mtd/onenand/onenand_base.c | 3 ++- include/linux/mtd/onenand.h | 1 + 2 files changed, 3 insertions(+), 1 deletion(-) (limited to 'include') diff --git a/drivers/mtd/onenand/onenand_base.c b/drivers/mtd/onenand/onenand_base.c index 4205b9423b89..56a8b2005bda 100644 --- a/drivers/mtd/onenand/onenand_base.c +++ b/drivers/mtd/onenand/onenand_base.c @@ -4085,7 +4085,8 @@ int onenand_scan(struct mtd_info *mtd, int maxchips) mtd->writebufsize = mtd->writesize; /* Unlock whole block */ - this->unlock_all(mtd); + if (!(this->options & ONENAND_SKIP_INITIAL_UNLOCKING)) + this->unlock_all(mtd); ret = this->scan_bbt(mtd); if ((!FLEXONENAND(this)) || ret) diff --git a/include/linux/mtd/onenand.h b/include/linux/mtd/onenand.h index ae418e41d8f5..52b6f187bf49 100644 --- a/include/linux/mtd/onenand.h +++ b/include/linux/mtd/onenand.h @@ -198,6 +198,7 @@ struct onenand_chip { #define ONENAND_SKIP_UNLOCK_CHECK (0x0100) #define ONENAND_PAGEBUF_ALLOC (0x1000) #define ONENAND_OOBBUF_ALLOC (0x2000) +#define ONENAND_SKIP_INITIAL_UNLOCKING (0x4000) #define ONENAND_IS_4KB_PAGE(this) \ (this->options & ONENAND_HAS_4KB_PAGE) -- cgit v1.2.3 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 --- include/linux/bch.h | 79 +++ lib/Kconfig | 39 ++ lib/Makefile | 1 + lib/bch.c | 1368 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 1487 insertions(+) create mode 100644 include/linux/bch.h create mode 100644 lib/bch.c (limited to 'include') diff --git a/include/linux/bch.h b/include/linux/bch.h new file mode 100644 index 000000000000..295b4ef153bb --- /dev/null +++ b/include/linux/bch.h @@ -0,0 +1,79 @@ +/* + * Generic binary BCH encoding/decoding library + * + * This program 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., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Copyright © 2011 Parrot S.A. + * + * Author: Ivan Djelic + * + * Description: + * + * This library provides runtime configurable encoding/decoding of binary + * Bose-Chaudhuri-Hocquenghem (BCH) codes. +*/ +#ifndef _BCH_H +#define _BCH_H + +#include + +/** + * struct bch_control - BCH control structure + * @m: Galois field order + * @n: maximum codeword size in bits (= 2^m-1) + * @t: error correction capability in bits + * @ecc_bits: ecc exact size in bits, i.e. generator polynomial degree (<=m*t) + * @ecc_bytes: ecc max size (m*t bits) in bytes + * @a_pow_tab: Galois field GF(2^m) exponentiation lookup table + * @a_log_tab: Galois field GF(2^m) log lookup table + * @mod8_tab: remainder generator polynomial lookup tables + * @ecc_buf: ecc parity words buffer + * @ecc_buf2: ecc parity words buffer + * @xi_tab: GF(2^m) base for solving degree 2 polynomial roots + * @syn: syndrome buffer + * @cache: log-based polynomial representation buffer + * @elp: error locator polynomial + * @poly_2t: temporary polynomials of degree 2t + */ +struct bch_control { + unsigned int m; + unsigned int n; + unsigned int t; + unsigned int ecc_bits; + unsigned int ecc_bytes; +/* private: */ + uint16_t *a_pow_tab; + uint16_t *a_log_tab; + uint32_t *mod8_tab; + uint32_t *ecc_buf; + uint32_t *ecc_buf2; + unsigned int *xi_tab; + unsigned int *syn; + int *cache; + struct gf_poly *elp; + struct gf_poly *poly_2t[4]; +}; + +struct bch_control *init_bch(int m, int t, unsigned int prim_poly); + +void free_bch(struct bch_control *bch); + +void encode_bch(struct bch_control *bch, const uint8_t *data, + unsigned int len, uint8_t *ecc); + +int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len, + const uint8_t *recv_ecc, const uint8_t *calc_ecc, + const unsigned int *syn, unsigned int *errloc); + +#endif /* _BCH_H */ 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 # diff --git a/lib/Makefile b/lib/Makefile index cbb774f7d41d..0544c814d827 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -67,6 +67,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ +obj-$(CONFIG_BCH) += bch.o obj-$(CONFIG_LZO_COMPRESS) += lzo/ obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ obj-$(CONFIG_XZ_DEC) += xz/ diff --git a/lib/bch.c b/lib/bch.c new file mode 100644 index 000000000000..bc89dfe4d1b3 --- /dev/null +++ b/lib/bch.c @@ -0,0 +1,1368 @@ +/* + * Generic binary BCH encoding/decoding library + * + * This program 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., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Copyright © 2011 Parrot S.A. + * + * Author: Ivan Djelic + * + * Description: + * + * This library provides runtime configurable encoding/decoding of binary + * Bose-Chaudhuri-Hocquenghem (BCH) codes. + * + * Call init_bch to get a pointer to a newly allocated bch_control structure for + * the given m (Galois field order), t (error correction capability) and + * (optional) primitive polynomial parameters. + * + * Call encode_bch to compute and store ecc parity bytes to a given buffer. + * Call decode_bch to detect and locate errors in received data. + * + * On systems supporting hw BCH features, intermediate results may be provided + * to decode_bch in order to skip certain steps. See decode_bch() documentation + * for details. + * + * Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of + * parameters m and t; thus allowing extra compiler optimizations and providing + * better (up to 2x) encoding performance. Using this option makes sense when + * (m,t) are fixed and known in advance, e.g. when using BCH error correction + * on a particular NAND flash device. + * + * Algorithmic details: + * + * Encoding is performed by processing 32 input bits in parallel, using 4 + * remainder lookup tables. + * + * The final stage of decoding involves the following internal steps: + * a. Syndrome computation + * b. Error locator polynomial computation using Berlekamp-Massey algorithm + * c. Error locator root finding (by far the most expensive step) + * + * In this implementation, step c is not performed using the usual Chien search. + * Instead, an alternative approach described in [1] is used. It consists in + * factoring the error locator polynomial using the Berlekamp Trace algorithm + * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial + * solving techniques [2] are used. The resulting algorithm, called BTZ, yields + * much better performance than Chien search for usual (m,t) values (typically + * m >= 13, t < 32, see [1]). + * + * [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields + * of characteristic 2, in: Western European Workshop on Research in Cryptology + * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear. + * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over + * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996. + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#if defined(CONFIG_BCH_CONST_PARAMS) +#define GF_M(_p) (CONFIG_BCH_CONST_M) +#define GF_T(_p) (CONFIG_BCH_CONST_T) +#define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1) +#else +#define GF_M(_p) ((_p)->m) +#define GF_T(_p) ((_p)->t) +#define GF_N(_p) ((_p)->n) +#endif + +#define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32) +#define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8) + +#ifndef dbg +#define dbg(_fmt, args...) do {} while (0) +#endif + +/* + * represent a polynomial over GF(2^m) + */ +struct gf_poly { + unsigned int deg; /* polynomial degree */ + unsigned int c[0]; /* polynomial terms */ +}; + +/* given its degree, compute a polynomial size in bytes */ +#define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int)) + +/* polynomial of degree 1 */ +struct gf_poly_deg1 { + struct gf_poly poly; + unsigned int c[2]; +}; + +/* + * same as encode_bch(), but process input data one byte at a time + */ +static void encode_bch_unaligned(struct bch_control *bch, + const unsigned char *data, unsigned int len, + uint32_t *ecc) +{ + int i; + const uint32_t *p; + const int l = BCH_ECC_WORDS(bch)-1; + + while (len--) { + p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff); + + for (i = 0; i < l; i++) + ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); + + ecc[l] = (ecc[l] << 8)^(*p); + } +} + +/* + * convert ecc bytes to aligned, zero-padded 32-bit ecc words + */ +static void load_ecc8(struct bch_control *bch, uint32_t *dst, + const uint8_t *src) +{ + uint8_t pad[4] = {0, 0, 0, 0}; + unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; + + for (i = 0; i < nwords; i++, src += 4) + dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3]; + + memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); + dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3]; +} + +/* + * convert 32-bit ecc words to ecc bytes + */ +static void store_ecc8(struct bch_control *bch, uint8_t *dst, + const uint32_t *src) +{ + uint8_t pad[4]; + unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; + + for (i = 0; i < nwords; i++) { + *dst++ = (src[i] >> 24); + *dst++ = (src[i] >> 16) & 0xff; + *dst++ = (src[i] >> 8) & 0xff; + *dst++ = (src[i] >> 0) & 0xff; + } + pad[0] = (src[nwords] >> 24); + pad[1] = (src[nwords] >> 16) & 0xff; + pad[2] = (src[nwords] >> 8) & 0xff; + pad[3] = (src[nwords] >> 0) & 0xff; + memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); +} + +/** + * encode_bch - calculate BCH ecc parity of data + * @bch: BCH control structure + * @data: data to encode + * @len: data length in bytes + * @ecc: ecc parity data, must be initialized by caller + * + * The @ecc parity array is used both as input and output parameter, in order to + * allow incremental computations. It should be of the size indicated by member + * @ecc_bytes of @bch, and should be initialized to 0 before the first call. + * + * The exact number of computed ecc parity bits is given by member @ecc_bits of + * @bch; it may be less than m*t for large values of t. + */ +void encode_bch(struct bch_control *bch, const uint8_t *data, + unsigned int len, uint8_t *ecc) +{ + const unsigned int l = BCH_ECC_WORDS(bch)-1; + unsigned int i, mlen; + unsigned long m; + uint32_t w, r[l+1]; + const uint32_t * const tab0 = bch->mod8_tab; + const uint32_t * const tab1 = tab0 + 256*(l+1); + const uint32_t * const tab2 = tab1 + 256*(l+1); + const uint32_t * const tab3 = tab2 + 256*(l+1); + const uint32_t *pdata, *p0, *p1, *p2, *p3; + + if (ecc) { + /* load ecc parity bytes into internal 32-bit buffer */ + load_ecc8(bch, bch->ecc_buf, ecc); + } else { + memset(bch->ecc_buf, 0, sizeof(r)); + } + + /* process first unaligned data bytes */ + m = ((unsigned long)data) & 3; + if (m) { + mlen = (len < (4-m)) ? len : 4-m; + encode_bch_unaligned(bch, data, mlen, bch->ecc_buf); + data += mlen; + len -= mlen; + } + + /* process 32-bit aligned data words */ + pdata = (uint32_t *)data; + mlen = len/4; + data += 4*mlen; + len -= 4*mlen; + memcpy(r, bch->ecc_buf, sizeof(r)); + + /* + * split each 32-bit word into 4 polynomials of weight 8 as follows: + * + * 31 ...24 23 ...16 15 ... 8 7 ... 0 + * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt + * tttttttt mod g = r0 (precomputed) + * zzzzzzzz 00000000 mod g = r1 (precomputed) + * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) + * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) + * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 + */ + while (mlen--) { + /* input data is read in big-endian format */ + w = r[0]^cpu_to_be32(*pdata++); + p0 = tab0 + (l+1)*((w >> 0) & 0xff); + p1 = tab1 + (l+1)*((w >> 8) & 0xff); + p2 = tab2 + (l+1)*((w >> 16) & 0xff); + p3 = tab3 + (l+1)*((w >> 24) & 0xff); + + for (i = 0; i < l; i++) + r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; + + r[l] = p0[l]^p1[l]^p2[l]^p3[l]; + } + memcpy(bch->ecc_buf, r, sizeof(r)); + + /* process last unaligned bytes */ + if (len) + encode_bch_unaligned(bch, data, len, bch->ecc_buf); + + /* store ecc parity bytes into original parity buffer */ + if (ecc) + store_ecc8(bch, ecc, bch->ecc_buf); +} +EXPORT_SYMBOL_GPL(encode_bch); + +static inline int modulo(struct bch_control *bch, unsigned int v) +{ + const unsigned int n = GF_N(bch); + while (v >= n) { + v -= n; + v = (v & n) + (v >> GF_M(bch)); + } + return v; +} + +/* + * shorter and faster modulo function, only works when v < 2N. + */ +static inline int mod_s(struct bch_control *bch, unsigned int v) +{ + const unsigned int n = GF_N(bch); + return (v < n) ? v : v-n; +} + +static inline int deg(unsigned int poly) +{ + /* polynomial degree is the most-significant bit index */ + return fls(poly)-1; +} + +static inline int parity(unsigned int x) +{ + /* + * public domain code snippet, lifted from + * http://www-graphics.stanford.edu/~seander/bithacks.html + */ + x ^= x >> 1; + x ^= x >> 2; + x = (x & 0x11111111U) * 0x11111111U; + return (x >> 28) & 1; +} + +/* Galois field basic operations: multiply, divide, inverse, etc. */ + +static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, + unsigned int b) +{ + return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ + bch->a_log_tab[b])] : 0; +} + +static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) +{ + return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; +} + +static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, + unsigned int b) +{ + return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ + GF_N(bch)-bch->a_log_tab[b])] : 0; +} + +static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) +{ + return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; +} + +static inline unsigned int a_pow(struct bch_control *bch, int i) +{ + return bch->a_pow_tab[modulo(bch, i)]; +} + +static inline int a_log(struct bch_control *bch, unsigned int x) +{ + return bch->a_log_tab[x]; +} + +static inline int a_ilog(struct bch_control *bch, unsigned int x) +{ + return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); +} + +/* + * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t + */ +static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, + unsigned int *syn) +{ + int i, j, s; + unsigned int m; + uint32_t poly; + const int t = GF_T(bch); + + s = bch->ecc_bits; + + /* make sure extra bits in last ecc word are cleared */ + m = ((unsigned int)s) & 31; + if (m) + ecc[s/32] &= ~((1u << (32-m))-1); + memset(syn, 0, 2*t*sizeof(*syn)); + + /* compute v(a^j) for j=1 .. 2t-1 */ + do { + poly = *ecc++; + s -= 32; + while (poly) { + i = deg(poly); + for (j = 0; j < 2*t; j += 2) + syn[j] ^= a_pow(bch, (j+1)*(i+s)); + + poly ^= (1 << i); + } + } while (s > 0); + + /* v(a^(2j)) = v(a^j)^2 */ + for (j = 0; j < t; j++) + syn[2*j+1] = gf_sqr(bch, syn[j]); +} + +static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) +{ + memcpy(dst, src, GF_POLY_SZ(src->deg)); +} + +static int compute_error_locator_polynomial(struct bch_control *bch, + const unsigned int *syn) +{ + const unsigned int t = GF_T(bch); + const unsigned int n = GF_N(bch); + unsigned int i, j, tmp, l, pd = 1, d = syn[0]; + struct gf_poly *elp = bch->elp; + struct gf_poly *pelp = bch->poly_2t[0]; + struct gf_poly *elp_copy = bch->poly_2t[1]; + int k, pp = -1; + + memset(pelp, 0, GF_POLY_SZ(2*t)); + memset(elp, 0, GF_POLY_SZ(2*t)); + + pelp->deg = 0; + pelp->c[0] = 1; + elp->deg = 0; + elp->c[0] = 1; + + /* use simplified binary Berlekamp-Massey algorithm */ + for (i = 0; (i < t) && (elp->deg <= t); i++) { + if (d) { + k = 2*i-pp; + gf_poly_copy(elp_copy, elp); + /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ + tmp = a_log(bch, d)+n-a_log(bch, pd); + for (j = 0; j <= pelp->deg; j++) { + if (pelp->c[j]) { + l = a_log(bch, pelp->c[j]); + elp->c[j+k] ^= a_pow(bch, tmp+l); + } + } + /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ + tmp = pelp->deg+k; + if (tmp > elp->deg) { + elp->deg = tmp; + gf_poly_copy(pelp, elp_copy); + pd = d; + pp = 2*i; + } + } + /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ + if (i < t-1) { + d = syn[2*i+2]; + for (j = 1; j <= elp->deg; j++) + d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); + } + } + dbg("elp=%s\n", gf_poly_str(elp)); + return (elp->deg > t) ? -1 : (int)elp->deg; +} + +/* + * solve a m x m linear system in GF(2) with an expected number of solutions, + * and return the number of found solutions + */ +static int solve_linear_system(struct bch_control *bch, unsigned int *rows, + unsigned int *sol, int nsol) +{ + const int m = GF_M(bch); + unsigned int tmp, mask; + int rem, c, r, p, k, param[m]; + + k = 0; + mask = 1 << m; + + /* Gaussian elimination */ + for (c = 0; c < m; c++) { + rem = 0; + p = c-k; + /* find suitable row for elimination */ + for (r = p; r < m; r++) { + if (rows[r] & mask) { + if (r != p) { + tmp = rows[r]; + rows[r] = rows[p]; + rows[p] = tmp; + } + rem = r+1; + break; + } + } + if (rem) { + /* perform elimination on remaining rows */ + tmp = rows[p]; + for (r = rem; r < m; r++) { + if (rows[r] & mask) + rows[r] ^= tmp; + } + } else { + /* elimination not needed, store defective row index */ + param[k++] = c; + } + mask >>= 1; + } + /* rewrite system, inserting fake parameter rows */ + if (k > 0) { + p = k; + for (r = m-1; r >= 0; r--) { + if ((r > m-1-k) && rows[r]) + /* system has no solution */ + return 0; + + rows[r] = (p && (r == param[p-1])) ? + p--, 1u << (m-r) : rows[r-p]; + } + } + + if (nsol != (1 << k)) + /* unexpected number of solutions */ + return 0; + + for (p = 0; p < nsol; p++) { + /* set parameters for p-th solution */ + for (c = 0; c < k; c++) + rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1); + + /* compute unique solution */ + tmp = 0; + for (r = m-1; r >= 0; r--) { + mask = rows[r] & (tmp|1); + tmp |= parity(mask) << (m-r); + } + sol[p] = tmp >> 1; + } + return nsol; +} + +/* + * this function builds and solves a linear system for finding roots of a degree + * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m). + */ +static int find_affine4_roots(struct bch_control *bch, unsigned int a, + unsigned int b, unsigned int c, + unsigned int *roots) +{ + int i, j, k; + const int m = GF_M(bch); + unsigned int mask = 0xff, t, rows[16] = {0,}; + + j = a_log(bch, b); + k = a_log(bch, a); + rows[0] = c; + + /* buid linear system to solve X^4+aX^2+bX+c = 0 */ + for (i = 0; i < m; i++) { + rows[i+1] = bch->a_pow_tab[4*i]^ + (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ + (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); + j++; + k += 2; + } + /* + * transpose 16x16 matrix before passing it to linear solver + * warning: this code assumes m < 16 + */ + for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) { + for (k = 0; k < 16; k = (k+j+1) & ~j) { + t = ((rows[k] >> j)^rows[k+j]) & mask; + rows[k] ^= (t << j); + rows[k+j] ^= t; + } + } + return solve_linear_system(bch, rows, roots, 4); +} + +/* + * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r)) + */ +static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int n = 0; + + if (poly->c[0]) + /* poly[X] = bX+c with c!=0, root=c/b */ + roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ + bch->a_log_tab[poly->c[1]]); + return n; +} + +/* + * compute roots of a degree 2 polynomial over GF(2^m) + */ +static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int n = 0, i, l0, l1, l2; + unsigned int u, v, r; + + if (poly->c[0] && poly->c[1]) { + + l0 = bch->a_log_tab[poly->c[0]]; + l1 = bch->a_log_tab[poly->c[1]]; + l2 = bch->a_log_tab[poly->c[2]]; + + /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */ + u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1)); + /* + * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): + * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) = + * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u) + * i.e. r and r+1 are roots iff Tr(u)=0 + */ + r = 0; + v = u; + while (v) { + i = deg(v); + r ^= bch->xi_tab[i]; + v ^= (1 << i); + } + /* verify root */ + if ((gf_sqr(bch, r)^r) == u) { + /* reverse z=a/bX transformation and compute log(1/r) */ + roots[n++] = modulo(bch, 2*GF_N(bch)-l1- + bch->a_log_tab[r]+l2); + roots[n++] = modulo(bch, 2*GF_N(bch)-l1- + bch->a_log_tab[r^1]+l2); + } + } + return n; +} + +/* + * compute roots of a degree 3 polynomial over GF(2^m) + */ +static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int i, n = 0; + unsigned int a, b, c, a2, b2, c2, e3, tmp[4]; + + if (poly->c[0]) { + /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */ + e3 = poly->c[3]; + c2 = gf_div(bch, poly->c[0], e3); + b2 = gf_div(bch, poly->c[1], e3); + a2 = gf_div(bch, poly->c[2], e3); + + /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */ + c = gf_mul(bch, a2, c2); /* c = a2c2 */ + b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */ + a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */ + + /* find the 4 roots of this affine polynomial */ + if (find_affine4_roots(bch, a, b, c, tmp) == 4) { + /* remove a2 from final list of roots */ + for (i = 0; i < 4; i++) { + if (tmp[i] != a2) + roots[n++] = a_ilog(bch, tmp[i]); + } + } + } + return n; +} + +/* + * compute roots of a degree 4 polynomial over GF(2^m) + */ +static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int i, l, n = 0; + unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4; + + if (poly->c[0] == 0) + return 0; + + /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */ + e4 = poly->c[4]; + d = gf_div(bch, poly->c[0], e4); + c = gf_div(bch, poly->c[1], e4); + b = gf_div(bch, poly->c[2], e4); + a = gf_div(bch, poly->c[3], e4); + + /* use Y=1/X transformation to get an affine polynomial */ + if (a) { + /* first, eliminate cX by using z=X+e with ae^2+c=0 */ + if (c) { + /* compute e such that e^2 = c/a */ + f = gf_div(bch, c, a); + l = a_log(bch, f); + l += (l & 1) ? GF_N(bch) : 0; + e = a_pow(bch, l/2); + /* + * use transformation z=X+e: + * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d + * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d + * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d + * z^4 + az^3 + b'z^2 + d' + */ + d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d; + b = gf_mul(bch, a, e)^b; + } + /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */ + if (d == 0) + /* assume all roots have multiplicity 1 */ + return 0; + + c2 = gf_inv(bch, d); + b2 = gf_div(bch, a, d); + a2 = gf_div(bch, b, d); + } else { + /* polynomial is already affine */ + c2 = d; + b2 = c; + a2 = b; + } + /* find the 4 roots of this affine polynomial */ + if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) { + for (i = 0; i < 4; i++) { + /* post-process roots (reverse transformations) */ + f = a ? gf_inv(bch, roots[i]) : roots[i]; + roots[i] = a_ilog(bch, f^e); + } + n = 4; + } + return n; +} + +/* + * build monic, log-based representation of a polynomial + */ +static void gf_poly_logrep(struct bch_control *bch, + const struct gf_poly *a, int *rep) +{ + int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); + + /* represent 0 values with -1; warning, rep[d] is not set to 1 */ + for (i = 0; i < d; i++) + rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1; +} + +/* + * compute polynomial Euclidean division remainder in GF(2^m)[X] + */ +static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, + const struct gf_poly *b, int *rep) +{ + int la, p, m; + unsigned int i, j, *c = a->c; + const unsigned int d = b->deg; + + if (a->deg < d) + return; + + /* reuse or compute log representation of denominator */ + if (!rep) { + rep = bch->cache; + gf_poly_logrep(bch, b, rep); + } + + for (j = a->deg; j >= d; j--) { + if (c[j]) { + la = a_log(bch, c[j]); + p = j-d; + for (i = 0; i < d; i++, p++) { + m = rep[i]; + if (m >= 0) + c[p] ^= bch->a_pow_tab[mod_s(bch, + m+la)]; + } + } + } + a->deg = d-1; + while (!c[a->deg] && a->deg) + a->deg--; +} + +/* + * compute polynomial Euclidean division quotient in GF(2^m)[X] + */ +static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, + const struct gf_poly *b, struct gf_poly *q) +{ + if (a->deg >= b->deg) { + q->deg = a->deg-b->deg; + /* compute a mod b (modifies a) */ + gf_poly_mod(bch, a, b, NULL); + /* quotient is stored in upper part of polynomial a */ + memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); + } else { + q->deg = 0; + q->c[0] = 0; + } +} + +/* + * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X] + */ +static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, + struct gf_poly *b) +{ + struct gf_poly *tmp; + + dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b)); + + if (a->deg < b->deg) { + tmp = b; + b = a; + a = tmp; + } + + while (b->deg > 0) { + gf_poly_mod(bch, a, b, NULL); + tmp = b; + b = a; + a = tmp; + } + + dbg("%s\n", gf_poly_str(a)); + + return a; +} + +/* + * Given a polynomial f and an integer k, compute Tr(a^kX) mod f + * This is used in Berlekamp Trace algorithm for splitting polynomials + */ +static void compute_trace_bk_mod(struct bch_control *bch, int k, + const struct gf_poly *f, struct gf_poly *z, + struct gf_poly *out) +{ + const int m = GF_M(bch); + int i, j; + + /* z contains z^2j mod f */ + z->deg = 1; + z->c[0] = 0; + z->c[1] = bch->a_pow_tab[k]; + + out->deg = 0; + memset(out, 0, GF_POLY_SZ(f->deg)); + + /* compute f log representation only once */ + gf_poly_logrep(bch, f, bch->cache); + + for (i = 0; i < m; i++) { + /* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */ + for (j = z->deg; j >= 0; j--) { + out->c[j] ^= z->c[j]; + z->c[2*j] = gf_sqr(bch, z->c[j]); + z->c[2*j+1] = 0; + } + if (z->deg > out->deg) + out->deg = z->deg; + + if (i < m-1) { + z->deg *= 2; + /* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */ + gf_poly_mod(bch, z, f, bch->cache); + } + } + while (!out->c[out->deg] && out->deg) + out->deg--; + + dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out)); +} + +/* + * factor a polynomial using Berlekamp Trace algorithm (BTA) + */ +static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f, + struct gf_poly **g, struct gf_poly **h) +{ + struct gf_poly *f2 = bch->poly_2t[0]; + struct gf_poly *q = bch->poly_2t[1]; + struct gf_poly *tk = bch->poly_2t[2]; + struct gf_poly *z = bch->poly_2t[3]; + struct gf_poly *gcd; + + dbg("factoring %s...\n", gf_poly_str(f)); + + *g = f; + *h = NULL; + + /* tk = Tr(a^k.X) mod f */ + compute_trace_bk_mod(bch, k, f, z, tk); + + if (tk->deg > 0) { + /* compute g = gcd(f, tk) (destructive operation) */ + gf_poly_copy(f2, f); + gcd = gf_poly_gcd(bch, f2, tk); + if (gcd->deg < f->deg) { + /* compute h=f/gcd(f,tk); this will modify f and q */ + gf_poly_div(bch, f, gcd, q); + /* store g and h in-place (clobbering f) */ + *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly; + gf_poly_copy(*g, gcd); + gf_poly_copy(*h, q); + } + } +} + +/* + * find roots of a polynomial, using BTZ algorithm; see the beginning of this + * file for details + */ +static int find_poly_roots(struct bch_control *bch, unsigned int k, + struct gf_poly *poly, unsigned int *roots) +{ + int cnt; + struct gf_poly *f1, *f2; + + switch (poly->deg) { + /* handle low degree polynomials with ad hoc techniques */ + case 1: + cnt = find_poly_deg1_roots(bch, poly, roots); + break; + case 2: + cnt = find_poly_deg2_roots(bch, poly, roots); + break; + case 3: + cnt = find_poly_deg3_roots(bch, poly, roots); + break; + case 4: + cnt = find_poly_deg4_roots(bch, poly, roots); + break; + default: + /* factor polynomial using Berlekamp Trace Algorithm (BTA) */ + cnt = 0; + if (poly->deg && (k <= GF_M(bch))) { + factor_polynomial(bch, k, poly, &f1, &f2); + if (f1) + cnt += find_poly_roots(bch, k+1, f1, roots); + if (f2) + cnt += find_poly_roots(bch, k+1, f2, roots+cnt); + } + break; + } + return cnt; +} + +#if defined(USE_CHIEN_SEARCH) +/* + * exhaustive root search (Chien) implementation - not used, included only for + * reference/comparison tests + */ +static int chien_search(struct bch_control *bch, unsigned int len, + struct gf_poly *p, unsigned int *roots) +{ + int m; + unsigned int i, j, syn, syn0, count = 0; + const unsigned int k = 8*len+bch->ecc_bits; + + /* use a log-based representation of polynomial */ + gf_poly_logrep(bch, p, bch->cache); + bch->cache[p->deg] = 0; + syn0 = gf_div(bch, p->c[0], p->c[p->deg]); + + for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) { + /* compute elp(a^i) */ + for (j = 1, syn = syn0; j <= p->deg; j++) { + m = bch->cache[j]; + if (m >= 0) + syn ^= a_pow(bch, m+j*i); + } + if (syn == 0) { + roots[count++] = GF_N(bch)-i; + if (count == p->deg) + break; + } + } + return (count == p->deg) ? count : 0; +} +#define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc) +#endif /* USE_CHIEN_SEARCH */ + +/** + * decode_bch - decode received codeword and find bit error locations + * @bch: BCH control structure + * @data: received data, ignored if @calc_ecc is provided + * @len: data length in bytes, must always be provided + * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc + * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data + * @syn: hw computed syndrome data (if NULL, syndrome is calculated) + * @errloc: output array of error locations + * + * Returns: + * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if + * invalid parameters were provided + * + * Depending on the available hw BCH support and the need to compute @calc_ecc + * separately (using encode_bch()), this function should be called with one of + * the following parameter configurations - + * + * by providing @data and @recv_ecc only: + * decode_bch(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc) + * + * by providing @recv_ecc and @calc_ecc: + * decode_bch(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc) + * + * by providing ecc = recv_ecc XOR calc_ecc: + * decode_bch(@bch, NULL, @len, NULL, ecc, NULL, @errloc) + * + * by providing syndrome results @syn: + * decode_bch(@bch, NULL, @len, NULL, NULL, @syn, @errloc) + * + * Once decode_bch() has successfully returned with a positive value, error + * locations returned in array @errloc should be interpreted as follows - + * + * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for + * data correction) + * + * if (errloc[n] < 8*len), then n-th error is located in data and can be + * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8); + * + * Note that this function does not perform any data correction by itself, it + * merely indicates error locations. + */ +int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len, + const uint8_t *recv_ecc, const uint8_t *calc_ecc, + const unsigned int *syn, unsigned int *errloc) +{ + const unsigned int ecc_words = BCH_ECC_WORDS(bch); + unsigned int nbits; + int i, err, nroots; + uint32_t sum; + + /* sanity check: make sure data length can be handled */ + if (8*len > (bch->n-bch->ecc_bits)) + return -EINVAL; + + /* if caller does not provide syndromes, compute them */ + if (!syn) { + if (!calc_ecc) { + /* compute received data ecc into an internal buffer */ + if (!data || !recv_ecc) + return -EINVAL; + encode_bch(bch, data, len, NULL); + } else { + /* load provided calculated ecc */ + load_ecc8(bch, bch->ecc_buf, calc_ecc); + } + /* load received ecc or assume it was XORed in calc_ecc */ + if (recv_ecc) { + load_ecc8(bch, bch->ecc_buf2, recv_ecc); + /* XOR received and calculated ecc */ + for (i = 0, sum = 0; i < (int)ecc_words; i++) { + bch->ecc_buf[i] ^= bch->ecc_buf2[i]; + sum |= bch->ecc_buf[i]; + } + if (!sum) + /* no error found */ + return 0; + } + compute_syndromes(bch, bch->ecc_buf, bch->syn); + syn = bch->syn; + } + + err = compute_error_locator_polynomial(bch, syn); + if (err > 0) { + nroots = find_poly_roots(bch, 1, bch->elp, errloc); + if (err != nroots) + err = -1; + } + if (err > 0) { + /* post-process raw error locations for easier correction */ + nbits = (len*8)+bch->ecc_bits; + for (i = 0; i < err; i++) { + if (errloc[i] >= nbits) { + err = -1; + break; + } + errloc[i] = nbits-1-errloc[i]; + errloc[i] = (errloc[i] & ~7)|(7-(errloc[i] & 7)); + } + } + return (err >= 0) ? err : -EBADMSG; +} +EXPORT_SYMBOL_GPL(decode_bch); + +/* + * generate Galois field lookup tables + */ +static int build_gf_tables(struct bch_control *bch, unsigned int poly) +{ + unsigned int i, x = 1; + const unsigned int k = 1 << deg(poly); + + /* primitive polynomial must be of degree m */ + if (k != (1u << GF_M(bch))) + return -1; + + for (i = 0; i < GF_N(bch); i++) { + bch->a_pow_tab[i] = x; + bch->a_log_tab[x] = i; + if (i && (x == 1)) + /* polynomial is not primitive (a^i=1 with 0a_pow_tab[GF_N(bch)] = 1; + bch->a_log_tab[0] = 0; + + return 0; +} + +/* + * compute generator polynomial remainder tables for fast encoding + */ +static void build_mod8_tables(struct bch_control *bch, const uint32_t *g) +{ + int i, j, b, d; + uint32_t data, hi, lo, *tab; + const int l = BCH_ECC_WORDS(bch); + const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32); + const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32); + + memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab)); + + for (i = 0; i < 256; i++) { + /* p(X)=i is a small polynomial of weight <= 8 */ + for (b = 0; b < 4; b++) { + /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */ + tab = bch->mod8_tab + (b*256+i)*l; + data = i << (8*b); + while (data) { + d = deg(data); + /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */ + data ^= g[0] >> (31-d); + for (j = 0; j < ecclen; j++) { + hi = (d < 31) ? g[j] << (d+1) : 0; + lo = (j+1 < plen) ? + g[j+1] >> (31-d) : 0; + tab[j] ^= hi|lo; + } + } + } + } +} + +/* + * build a base for factoring degree 2 polynomials + */ +static int build_deg2_base(struct bch_control *bch) +{ + const int m = GF_M(bch); + int i, j, r; + unsigned int sum, x, y, remaining, ak = 0, xi[m]; + + /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */ + for (i = 0; i < m; i++) { + for (j = 0, sum = 0; j < m; j++) + sum ^= a_pow(bch, i*(1 << j)); + + if (sum) { + ak = bch->a_pow_tab[i]; + break; + } + } + /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */ + remaining = m; + memset(xi, 0, sizeof(xi)); + + for (x = 0; (x <= GF_N(bch)) && remaining; x++) { + y = gf_sqr(bch, x)^x; + for (i = 0; i < 2; i++) { + r = a_log(bch, y); + if (y && (r < m) && !xi[r]) { + bch->xi_tab[r] = x; + xi[r] = 1; + remaining--; + dbg("x%d = %x\n", r, x); + break; + } + y ^= ak; + } + } + /* should not happen but check anyway */ + return remaining ? -1 : 0; +} + +static void *bch_alloc(size_t size, int *err) +{ + void *ptr; + + ptr = kmalloc(size, GFP_KERNEL); + if (ptr == NULL) + *err = 1; + return ptr; +} + +/* + * compute generator polynomial for given (m,t) parameters. + */ +static uint32_t *compute_generator_polynomial(struct bch_control *bch) +{ + const unsigned int m = GF_M(bch); + const unsigned int t = GF_T(bch); + int n, err = 0; + unsigned int i, j, nbits, r, word, *roots; + struct gf_poly *g; + uint32_t *genpoly; + + g = bch_alloc(GF_POLY_SZ(m*t), &err); + roots = bch_alloc((bch->n+1)*sizeof(*roots), &err); + genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err); + + if (err) { + kfree(genpoly); + genpoly = NULL; + goto finish; + } + + /* enumerate all roots of g(X) */ + memset(roots , 0, (bch->n+1)*sizeof(*roots)); + for (i = 0; i < t; i++) { + for (j = 0, r = 2*i+1; j < m; j++) { + roots[r] = 1; + r = mod_s(bch, 2*r); + } + } + /* build generator polynomial g(X) */ + g->deg = 0; + g->c[0] = 1; + for (i = 0; i < GF_N(bch); i++) { + if (roots[i]) { + /* multiply g(X) by (X+root) */ + r = bch->a_pow_tab[i]; + g->c[g->deg+1] = 1; + for (j = g->deg; j > 0; j--) + g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1]; + + g->c[0] = gf_mul(bch, g->c[0], r); + g->deg++; + } + } + /* store left-justified binary representation of g(X) */ + n = g->deg+1; + i = 0; + + while (n > 0) { + nbits = (n > 32) ? 32 : n; + for (j = 0, word = 0; j < nbits; j++) { + if (g->c[n-1-j]) + word |= 1u << (31-j); + } + genpoly[i++] = word; + n -= nbits; + } + bch->ecc_bits = g->deg; + +finish: + kfree(g); + kfree(roots); + + return genpoly; +} + +/** + * init_bch - initialize a BCH encoder/decoder + * @m: Galois field order, should be in the range 5-15 + * @t: maximum error correction capability, in bits + * @prim_poly: user-provided primitive polynomial (or 0 to use default) + * + * Returns: + * a newly allocated BCH control structure if successful, NULL otherwise + * + * This initialization can take some time, as lookup tables are built for fast + * encoding/decoding; make sure not to call this function from a time critical + * path. Usually, init_bch() should be called on module/driver init and + * free_bch() should be called to release memory on exit. + * + * You may provide your own primitive polynomial of degree @m in argument + * @prim_poly, or let init_bch() use its default polynomial. + * + * Once init_bch() has successfully returned a pointer to a newly allocated + * BCH control structure, ecc length in bytes is given by member @ecc_bytes of + * the structure. + */ +struct bch_control *init_bch(int m, int t, unsigned int prim_poly) +{ + int err = 0; + unsigned int i, words; + uint32_t *genpoly; + struct bch_control *bch = NULL; + + const int min_m = 5; + const int max_m = 15; + + /* default primitive polynomials */ + static const unsigned int prim_poly_tab[] = { + 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b, + 0x402b, 0x8003, + }; + +#if defined(CONFIG_BCH_CONST_PARAMS) + if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) { + printk(KERN_ERR "bch encoder/decoder was configured to support " + "parameters m=%d, t=%d only!\n", + CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T); + goto fail; + } +#endif + if ((m < min_m) || (m > max_m)) + /* + * values of m greater than 15 are not currently supported; + * supporting m > 15 would require changing table base type + * (uint16_t) and a small patch in matrix transposition + */ + goto fail; + + /* sanity checks */ + if ((t < 1) || (m*t >= ((1 << m)-1))) + /* invalid t value */ + goto fail; + + /* select a primitive polynomial for generating GF(2^m) */ + if (prim_poly == 0) + prim_poly = prim_poly_tab[m-min_m]; + + bch = kzalloc(sizeof(*bch), GFP_KERNEL); + if (bch == NULL) + goto fail; + + bch->m = m; + bch->t = t; + bch->n = (1 << m)-1; + words = DIV_ROUND_UP(m*t, 32); + bch->ecc_bytes = DIV_ROUND_UP(m*t, 8); + bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err); + bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err); + bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err); + bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err); + bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err); + bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err); + bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err); + bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err); + bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err); + + for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) + bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err); + + if (err) + goto fail; + + err = build_gf_tables(bch, prim_poly); + if (err) + goto fail; + + /* use generator polynomial for computing encoding tables */ + genpoly = compute_generator_polynomial(bch); + if (genpoly == NULL) + goto fail; + + build_mod8_tables(bch, genpoly); + kfree(genpoly); + + err = build_deg2_base(bch); + if (err) + goto fail; + + return bch; + +fail: + free_bch(bch); + return NULL; +} +EXPORT_SYMBOL_GPL(init_bch); + +/** + * free_bch - free the BCH control structure + * @bch: BCH control structure to release + */ +void free_bch(struct bch_control *bch) +{ + unsigned int i; + + if (bch) { + kfree(bch->a_pow_tab); + kfree(bch->a_log_tab); + kfree(bch->mod8_tab); + kfree(bch->ecc_buf); + kfree(bch->ecc_buf2); + kfree(bch->xi_tab); + kfree(bch->syn); + kfree(bch->cache); + kfree(bch->elp); + + for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) + kfree(bch->poly_2t[i]); + + kfree(bch); + } +} +EXPORT_SYMBOL_GPL(free_bch); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Ivan Djelic "); +MODULE_DESCRIPTION("Binary BCH encoder/decoder"); -- cgit v1.2.3 From 1065cda8a1a57d0d3bfccdce1a655a84439d24e0 Mon Sep 17 00:00:00 2001 From: Steffen Sledz Date: Thu, 10 Mar 2011 09:05:12 +0100 Subject: mtd: cfi: add support for AMIC flashes (e.g. A29L160AT) Signed-off-by: Steffen Sledz Signed-off-by: David Woodhouse --- drivers/mtd/chips/cfi_cmdset_0002.c | 1 + include/linux/mtd/cfi.h | 1 + 2 files changed, 2 insertions(+) (limited to 'include') diff --git a/drivers/mtd/chips/cfi_cmdset_0002.c b/drivers/mtd/chips/cfi_cmdset_0002.c index 7e9c4e9c274a..f9a5331e9445 100644 --- a/drivers/mtd/chips/cfi_cmdset_0002.c +++ b/drivers/mtd/chips/cfi_cmdset_0002.c @@ -349,6 +349,7 @@ static struct cfi_fixup cfi_fixup_table[] = { { CFI_MFR_ATMEL, CFI_ID_ANY, fixup_convert_atmel_pri }, #ifdef AMD_BOOTLOC_BUG { CFI_MFR_AMD, CFI_ID_ANY, fixup_amd_bootblock }, + { CFI_MFR_AMIC, CFI_ID_ANY, fixup_amd_bootblock }, { CFI_MFR_MACRONIX, CFI_ID_ANY, fixup_amd_bootblock }, #endif { CFI_MFR_AMD, 0x0050, fixup_use_secsi }, diff --git a/include/linux/mtd/cfi.h b/include/linux/mtd/cfi.h index a9baee6864af..0d823f2dd667 100644 --- a/include/linux/mtd/cfi.h +++ b/include/linux/mtd/cfi.h @@ -535,6 +535,7 @@ struct cfi_fixup { #define CFI_MFR_CONTINUATION 0x007F #define CFI_MFR_AMD 0x0001 +#define CFI_MFR_AMIC 0x0037 #define CFI_MFR_ATMEL 0x001F #define CFI_MFR_EON 0x001C #define CFI_MFR_FUJITSU 0x0004 -- cgit v1.2.3 From 193bd40026443835e1b96c79d5efe559d01509ae Mon Sep 17 00:00:00 2001 From: Ivan Djelic Date: Fri, 11 Mar 2011 11:05:33 +0100 Subject: mtd: nand: add software BCH ECC support This patch adds software BCH ECC support to mtd, in order to handle recent NAND device ecc requirements (4 bits or more). It does so by adding a new ecc mode (NAND_ECC_SOFT_BCH) for use by board drivers, and a new Kconfig option to enable BCH support. It relies on the generic BCH library introduced in a previous patch. When a board driver uses mode NAND_ECC_SOFT_BCH, it should also set fields chip->ecc.size and chip->ecc.bytes to select BCH ecc data size and required error correction capability. See nand_bch_init() documentation for details. It has been tested on the following platforms using mtd-utils, UBI and UBIFS: x86 (with nandsim), arm926ejs. Signed-off-by: Ivan Djelic Signed-off-by: David Woodhouse --- drivers/mtd/nand/Kconfig | 15 +++ drivers/mtd/nand/Makefile | 1 + drivers/mtd/nand/nand_base.c | 40 ++++++- drivers/mtd/nand/nand_bch.c | 243 +++++++++++++++++++++++++++++++++++++++++++ include/linux/mtd/nand.h | 3 + include/linux/mtd/nand_bch.h | 72 +++++++++++++ 6 files changed, 373 insertions(+), 1 deletion(-) create mode 100644 drivers/mtd/nand/nand_bch.c create mode 100644 include/linux/mtd/nand_bch.h (limited to 'include') diff --git a/drivers/mtd/nand/Kconfig b/drivers/mtd/nand/Kconfig index c89592239bc7..78205ac2b10f 100644 --- a/drivers/mtd/nand/Kconfig +++ b/drivers/mtd/nand/Kconfig @@ -31,6 +31,21 @@ config MTD_NAND_VERIFY_WRITE device thinks the write was successful, a bit could have been flipped accidentally due to device wear or something else. +config MTD_NAND_BCH + tristate + select BCH + depends on MTD_NAND_ECC_BCH + default MTD_NAND + +config MTD_NAND_ECC_BCH + bool "Support software BCH ECC" + default n + help + This enables support for software BCH error correction. Binary BCH + codes are more powerful and cpu intensive than traditional Hamming + ECC codes. They are used with NAND devices requiring more than 1 bit + of error correction. + config MTD_SM_COMMON tristate default n diff --git a/drivers/mtd/nand/Makefile b/drivers/mtd/nand/Makefile index 8ad6faec72cb..5745d831168e 100644 --- a/drivers/mtd/nand/Makefile +++ b/drivers/mtd/nand/Makefile @@ -4,6 +4,7 @@ obj-$(CONFIG_MTD_NAND) += nand.o obj-$(CONFIG_MTD_NAND_ECC) += nand_ecc.o +obj-$(CONFIG_MTD_NAND_BCH) += nand_bch.o obj-$(CONFIG_MTD_NAND_IDS) += nand_ids.o obj-$(CONFIG_MTD_SM_COMMON) += sm_common.o diff --git a/drivers/mtd/nand/nand_base.c b/drivers/mtd/nand/nand_base.c index da7604050347..85cfc061d41c 100644 --- a/drivers/mtd/nand/nand_base.c +++ b/drivers/mtd/nand/nand_base.c @@ -42,6 +42,7 @@ #include #include #include +#include #include #include #include @@ -3248,7 +3249,7 @@ int nand_scan_tail(struct mtd_info *mtd) /* * If no default placement scheme is given, select an appropriate one */ - if (!chip->ecc.layout) { + if (!chip->ecc.layout && (chip->ecc.mode != NAND_ECC_SOFT_BCH)) { switch (mtd->oobsize) { case 8: chip->ecc.layout = &nand_oob_8; @@ -3351,6 +3352,40 @@ int nand_scan_tail(struct mtd_info *mtd) chip->ecc.bytes = 3; break; + case NAND_ECC_SOFT_BCH: + if (!mtd_nand_has_bch()) { + printk(KERN_WARNING "CONFIG_MTD_ECC_BCH not enabled\n"); + BUG(); + } + chip->ecc.calculate = nand_bch_calculate_ecc; + chip->ecc.correct = nand_bch_correct_data; + chip->ecc.read_page = nand_read_page_swecc; + chip->ecc.read_subpage = nand_read_subpage; + chip->ecc.write_page = nand_write_page_swecc; + chip->ecc.read_page_raw = nand_read_page_raw; + chip->ecc.write_page_raw = nand_write_page_raw; + chip->ecc.read_oob = nand_read_oob_std; + chip->ecc.write_oob = nand_write_oob_std; + /* + * Board driver should supply ecc.size and ecc.bytes values to + * select how many bits are correctable; see nand_bch_init() + * for details. + * Otherwise, default to 4 bits for large page devices + */ + if (!chip->ecc.size && (mtd->oobsize >= 64)) { + chip->ecc.size = 512; + chip->ecc.bytes = 7; + } + chip->ecc.priv = nand_bch_init(mtd, + chip->ecc.size, + chip->ecc.bytes, + &chip->ecc.layout); + if (!chip->ecc.priv) { + printk(KERN_WARNING "BCH ECC initialization failed!\n"); + BUG(); + } + break; + case NAND_ECC_NONE: printk(KERN_WARNING "NAND_ECC_NONE selected by board driver. " "This is not recommended !!\n"); @@ -3501,6 +3536,9 @@ void nand_release(struct mtd_info *mtd) { struct nand_chip *chip = mtd->priv; + if (chip->ecc.mode == NAND_ECC_SOFT_BCH) + nand_bch_free((struct nand_bch_control *)chip->ecc.priv); + #ifdef CONFIG_MTD_PARTITIONS /* Deregister partitions */ del_mtd_partitions(mtd); diff --git a/drivers/mtd/nand/nand_bch.c b/drivers/mtd/nand/nand_bch.c new file mode 100644 index 000000000000..0f931e757116 --- /dev/null +++ b/drivers/mtd/nand/nand_bch.c @@ -0,0 +1,243 @@ +/* + * This file provides ECC correction for more than 1 bit per block of data, + * using binary BCH codes. It relies on the generic BCH library lib/bch.c. + * + * Copyright © 2011 Ivan Djelic + * + * This file is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2 or (at your option) any + * later version. + * + * This file 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 file; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/** + * struct nand_bch_control - private NAND BCH control structure + * @bch: BCH control structure + * @ecclayout: private ecc layout for this BCH configuration + * @errloc: error location array + * @eccmask: XOR ecc mask, allows erased pages to be decoded as valid + */ +struct nand_bch_control { + struct bch_control *bch; + struct nand_ecclayout ecclayout; + unsigned int *errloc; + unsigned char *eccmask; +}; + +/** + * nand_bch_calculate_ecc - [NAND Interface] Calculate ECC for data block + * @mtd: MTD block structure + * @buf: input buffer with raw data + * @code: output buffer with ECC + */ +int nand_bch_calculate_ecc(struct mtd_info *mtd, const unsigned char *buf, + unsigned char *code) +{ + const struct nand_chip *chip = mtd->priv; + struct nand_bch_control *nbc = chip->ecc.priv; + unsigned int i; + + memset(code, 0, chip->ecc.bytes); + encode_bch(nbc->bch, buf, chip->ecc.size, code); + + /* apply mask so that an erased page is a valid codeword */ + for (i = 0; i < chip->ecc.bytes; i++) + code[i] ^= nbc->eccmask[i]; + + return 0; +} +EXPORT_SYMBOL(nand_bch_calculate_ecc); + +/** + * nand_bch_correct_data - [NAND Interface] Detect and correct bit error(s) + * @mtd: MTD block structure + * @buf: raw data read from the chip + * @read_ecc: ECC from the chip + * @calc_ecc: the ECC calculated from raw data + * + * Detect and correct bit errors for a data byte block + */ +int nand_bch_correct_data(struct mtd_info *mtd, unsigned char *buf, + unsigned char *read_ecc, unsigned char *calc_ecc) +{ + const struct nand_chip *chip = mtd->priv; + struct nand_bch_control *nbc = chip->ecc.priv; + unsigned int *errloc = nbc->errloc; + int i, count; + + count = decode_bch(nbc->bch, NULL, chip->ecc.size, read_ecc, calc_ecc, + NULL, errloc); + if (count > 0) { + for (i = 0; i < count; i++) { + if (errloc[i] < (chip->ecc.size*8)) + /* error is located in data, correct it */ + buf[errloc[i] >> 3] ^= (1 << (errloc[i] & 7)); + /* else error in ecc, no action needed */ + + DEBUG(MTD_DEBUG_LEVEL0, "%s: corrected bitflip %u\n", + __func__, errloc[i]); + } + } else if (count < 0) { + printk(KERN_ERR "ecc unrecoverable error\n"); + count = -1; + } + return count; +} +EXPORT_SYMBOL(nand_bch_correct_data); + +/** + * nand_bch_init - [NAND Interface] Initialize NAND BCH error correction + * @mtd: MTD block structure + * @eccsize: ecc block size in bytes + * @eccbytes: ecc length in bytes + * @ecclayout: output default layout + * + * Returns: + * a pointer to a new NAND BCH control structure, or NULL upon failure + * + * Initialize NAND BCH error correction. Parameters @eccsize and @eccbytes + * are used to compute BCH parameters m (Galois field order) and t (error + * correction capability). @eccbytes should be equal to the number of bytes + * required to store m*t bits, where m is such that 2^m-1 > @eccsize*8. + * + * Example: to configure 4 bit correction per 512 bytes, you should pass + * @eccsize = 512 (thus, m=13 is the smallest integer such that 2^m-1 > 512*8) + * @eccbytes = 7 (7 bytes are required to store m*t = 13*4 = 52 bits) + */ +struct nand_bch_control * +nand_bch_init(struct mtd_info *mtd, unsigned int eccsize, unsigned int eccbytes, + struct nand_ecclayout **ecclayout) +{ + unsigned int m, t, eccsteps, i; + struct nand_ecclayout *layout; + struct nand_bch_control *nbc = NULL; + unsigned char *erased_page; + + if (!eccsize || !eccbytes) { + printk(KERN_WARNING "ecc parameters not supplied\n"); + goto fail; + } + + m = fls(1+8*eccsize); + t = (eccbytes*8)/m; + + nbc = kzalloc(sizeof(*nbc), GFP_KERNEL); + if (!nbc) + goto fail; + + nbc->bch = init_bch(m, t, 0); + if (!nbc->bch) + goto fail; + + /* verify that eccbytes has the expected value */ + if (nbc->bch->ecc_bytes != eccbytes) { + printk(KERN_WARNING "invalid eccbytes %u, should be %u\n", + eccbytes, nbc->bch->ecc_bytes); + goto fail; + } + + eccsteps = mtd->writesize/eccsize; + + /* if no ecc placement scheme was provided, build one */ + if (!*ecclayout) { + + /* handle large page devices only */ + if (mtd->oobsize < 64) { + printk(KERN_WARNING "must provide an oob scheme for " + "oobsize %d\n", mtd->oobsize); + goto fail; + } + + layout = &nbc->ecclayout; + layout->eccbytes = eccsteps*eccbytes; + + /* reserve 2 bytes for bad block marker */ + if (layout->eccbytes+2 > mtd->oobsize) { + printk(KERN_WARNING "no suitable oob scheme available " + "for oobsize %d eccbytes %u\n", mtd->oobsize, + eccbytes); + goto fail; + } + /* put ecc bytes at oob tail */ + for (i = 0; i < layout->eccbytes; i++) + layout->eccpos[i] = mtd->oobsize-layout->eccbytes+i; + + layout->oobfree[0].offset = 2; + layout->oobfree[0].length = mtd->oobsize-2-layout->eccbytes; + + *ecclayout = layout; + } + + /* sanity checks */ + if (8*(eccsize+eccbytes) >= (1 << m)) { + printk(KERN_WARNING "eccsize %u is too large\n", eccsize); + goto fail; + } + if ((*ecclayout)->eccbytes != (eccsteps*eccbytes)) { + printk(KERN_WARNING "invalid ecc layout\n"); + goto fail; + } + + nbc->eccmask = kmalloc(eccbytes, GFP_KERNEL); + nbc->errloc = kmalloc(t*sizeof(*nbc->errloc), GFP_KERNEL); + if (!nbc->eccmask || !nbc->errloc) + goto fail; + /* + * compute and store the inverted ecc of an erased ecc block + */ + erased_page = kmalloc(eccsize, GFP_KERNEL); + if (!erased_page) + goto fail; + + memset(erased_page, 0xff, eccsize); + memset(nbc->eccmask, 0, eccbytes); + encode_bch(nbc->bch, erased_page, eccsize, nbc->eccmask); + kfree(erased_page); + + for (i = 0; i < eccbytes; i++) + nbc->eccmask[i] ^= 0xff; + + return nbc; +fail: + nand_bch_free(nbc); + return NULL; +} +EXPORT_SYMBOL(nand_bch_init); + +/** + * nand_bch_free - [NAND Interface] Release NAND BCH ECC resources + * @nbc: NAND BCH control structure + */ +void nand_bch_free(struct nand_bch_control *nbc) +{ + if (nbc) { + free_bch(nbc->bch); + kfree(nbc->errloc); + kfree(nbc->eccmask); + kfree(nbc); + } +} +EXPORT_SYMBOL(nand_bch_free); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Ivan Djelic "); +MODULE_DESCRIPTION("NAND software BCH ECC support"); diff --git a/include/linux/mtd/nand.h b/include/linux/mtd/nand.h index 1f489b247a29..ae67ef56a8f5 100644 --- a/include/linux/mtd/nand.h +++ b/include/linux/mtd/nand.h @@ -140,6 +140,7 @@ typedef enum { NAND_ECC_HW, NAND_ECC_HW_SYNDROME, NAND_ECC_HW_OOB_FIRST, + NAND_ECC_SOFT_BCH, } nand_ecc_modes_t; /* @@ -339,6 +340,7 @@ struct nand_hw_control { * @prepad: padding information for syndrome based ecc generators * @postpad: padding information for syndrome based ecc generators * @layout: ECC layout control struct pointer + * @priv: pointer to private ecc control data * @hwctl: function to control hardware ecc generator. Must only * be provided if an hardware ECC is available * @calculate: function for ecc calculation or readback from ecc hardware @@ -362,6 +364,7 @@ struct nand_ecc_ctrl { int prepad; int postpad; struct nand_ecclayout *layout; + void *priv; void (*hwctl)(struct mtd_info *mtd, int mode); int (*calculate)(struct mtd_info *mtd, const uint8_t *dat, uint8_t *ecc_code); diff --git a/include/linux/mtd/nand_bch.h b/include/linux/mtd/nand_bch.h new file mode 100644 index 000000000000..74acf5367556 --- /dev/null +++ b/include/linux/mtd/nand_bch.h @@ -0,0 +1,72 @@ +/* + * Copyright © 2011 Ivan Djelic + * + * This program 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 file is the header for the NAND BCH ECC implementation. + */ + +#ifndef __MTD_NAND_BCH_H__ +#define __MTD_NAND_BCH_H__ + +struct mtd_info; +struct nand_bch_control; + +#if defined(CONFIG_MTD_NAND_ECC_BCH) + +static inline int mtd_nand_has_bch(void) { return 1; } + +/* + * Calculate BCH ecc code + */ +int nand_bch_calculate_ecc(struct mtd_info *mtd, const u_char *dat, + u_char *ecc_code); + +/* + * Detect and correct bit errors + */ +int nand_bch_correct_data(struct mtd_info *mtd, u_char *dat, u_char *read_ecc, + u_char *calc_ecc); +/* + * Initialize BCH encoder/decoder + */ +struct nand_bch_control * +nand_bch_init(struct mtd_info *mtd, unsigned int eccsize, + unsigned int eccbytes, struct nand_ecclayout **ecclayout); +/* + * Release BCH encoder/decoder resources + */ +void nand_bch_free(struct nand_bch_control *nbc); + +#else /* !CONFIG_MTD_NAND_ECC_BCH */ + +static inline int mtd_nand_has_bch(void) { return 0; } + +static inline int +nand_bch_calculate_ecc(struct mtd_info *mtd, const u_char *dat, + u_char *ecc_code) +{ + return -1; +} + +static inline int +nand_bch_correct_data(struct mtd_info *mtd, unsigned char *buf, + unsigned char *read_ecc, unsigned char *calc_ecc) +{ + return -1; +} + +static inline struct nand_bch_control * +nand_bch_init(struct mtd_info *mtd, unsigned int eccsize, + unsigned int eccbytes, struct nand_ecclayout **ecclayout) +{ + return NULL; +} + +static inline void nand_bch_free(struct nand_bch_control *nbc) {} + +#endif /* CONFIG_MTD_NAND_ECC_BCH */ + +#endif /* __MTD_NAND_BCH_H__ */ -- cgit v1.2.3