summaryrefslogtreecommitdiff
path: root/lib/reed_solomon/reed_solomon.c
AgeCommit message (Collapse)AuthorFilesLines
2019-06-26rslib: Update documentationFerdinand Blomqvist1-4/+8
The decoder returns the number of corrected symbols, not bits. The caller provided syndrome must be in index form. Signed-off-by: Ferdinand Blomqvist <ferdinand.blomqvist@gmail.com> Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Link: https://lkml.kernel.org/r/20190620141039.9874-7-ferdinand.blomqvist@gmail.com
2018-07-10reed_solomon: Fix kernel-docMatthew Wilcox1-1/+1
The current doc build warns: ./lib/reed_solomon/reed_solomon.c:287: WARNING: Unknown target name: "gfp". This is because it misinterprets the "GFP_" that is part of the description. Change the description to avoid the problem. Signed-off-by: Matthew Wilcox <willy@infradead.org> Acked-by: Kees Cook <keescook@chromium.org> Signed-off-by: Jonathan Corbet <corbet@lwn.net>
2018-06-12treewide: kmalloc() -> kmalloc_array()Kees Cook1-3/+3
The kmalloc() function has a 2-factor argument form, kmalloc_array(). This patch replaces cases of: kmalloc(a * b, gfp) with: kmalloc_array(a * b, gfp) as well as handling cases of: kmalloc(a * b * c, gfp) with: kmalloc(array3_size(a, b, c), gfp) as it's slightly less ugly than: kmalloc_array(array_size(a, b), c, gfp) This does, however, attempt to ignore constant size factors like: kmalloc(4 * 1024, gfp) though any constants defined via macros get caught up in the conversion. Any factors with a sizeof() of "unsigned char", "char", and "u8" were dropped, since they're redundant. The tools/ directory was manually excluded, since it has its own implementation of kmalloc(). The Coccinelle script used for this was: // Fix redundant parens around sizeof(). @@ type TYPE; expression THING, E; @@ ( kmalloc( - (sizeof(TYPE)) * E + sizeof(TYPE) * E , ...) | kmalloc( - (sizeof(THING)) * E + sizeof(THING) * E , ...) ) // Drop single-byte sizes and redundant parens. @@ expression COUNT; typedef u8; typedef __u8; @@ ( kmalloc( - sizeof(u8) * (COUNT) + COUNT , ...) | kmalloc( - sizeof(__u8) * (COUNT) + COUNT , ...) | kmalloc( - sizeof(char) * (COUNT) + COUNT , ...) | kmalloc( - sizeof(unsigned char) * (COUNT) + COUNT , ...) | kmalloc( - sizeof(u8) * COUNT + COUNT , ...) | kmalloc( - sizeof(__u8) * COUNT + COUNT , ...) | kmalloc( - sizeof(char) * COUNT + COUNT , ...) | kmalloc( - sizeof(unsigned char) * COUNT + COUNT , ...) ) // 2-factor product with sizeof(type/expression) and identifier or constant. @@ type TYPE; expression THING; identifier COUNT_ID; constant COUNT_CONST; @@ ( - kmalloc + kmalloc_array ( - sizeof(TYPE) * (COUNT_ID) + COUNT_ID, sizeof(TYPE) , ...) | - kmalloc + kmalloc_array ( - sizeof(TYPE) * COUNT_ID + COUNT_ID, sizeof(TYPE) , ...) | - kmalloc + kmalloc_array ( - sizeof(TYPE) * (COUNT_CONST) + COUNT_CONST, sizeof(TYPE) , ...) | - kmalloc + kmalloc_array ( - sizeof(TYPE) * COUNT_CONST + COUNT_CONST, sizeof(TYPE) , ...) | - kmalloc + kmalloc_array ( - sizeof(THING) * (COUNT_ID) + COUNT_ID, sizeof(THING) , ...) | - kmalloc + kmalloc_array ( - sizeof(THING) * COUNT_ID + COUNT_ID, sizeof(THING) , ...) | - kmalloc + kmalloc_array ( - sizeof(THING) * (COUNT_CONST) + COUNT_CONST, sizeof(THING) , ...) | - kmalloc + kmalloc_array ( - sizeof(THING) * COUNT_CONST + COUNT_CONST, sizeof(THING) , ...) ) // 2-factor product, only identifiers. @@ identifier SIZE, COUNT; @@ - kmalloc + kmalloc_array ( - SIZE * COUNT + COUNT, SIZE , ...) // 3-factor product with 1 sizeof(type) or sizeof(expression), with // redundant parens removed. @@ expression THING; identifier STRIDE, COUNT; type TYPE; @@ ( kmalloc( - sizeof(TYPE) * (COUNT) * (STRIDE) + array3_size(COUNT, STRIDE, sizeof(TYPE)) , ...) | kmalloc( - sizeof(TYPE) * (COUNT) * STRIDE + array3_size(COUNT, STRIDE, sizeof(TYPE)) , ...) | kmalloc( - sizeof(TYPE) * COUNT * (STRIDE) + array3_size(COUNT, STRIDE, sizeof(TYPE)) , ...) | kmalloc( - sizeof(TYPE) * COUNT * STRIDE + array3_size(COUNT, STRIDE, sizeof(TYPE)) , ...) | kmalloc( - sizeof(THING) * (COUNT) * (STRIDE) + array3_size(COUNT, STRIDE, sizeof(THING)) , ...) | kmalloc( - sizeof(THING) * (COUNT) * STRIDE + array3_size(COUNT, STRIDE, sizeof(THING)) , ...) | kmalloc( - sizeof(THING) * COUNT * (STRIDE) + array3_size(COUNT, STRIDE, sizeof(THING)) , ...) | kmalloc( - sizeof(THING) * COUNT * STRIDE + array3_size(COUNT, STRIDE, sizeof(THING)) , ...) ) // 3-factor product with 2 sizeof(variable), with redundant parens removed. @@ expression THING1, THING2; identifier COUNT; type TYPE1, TYPE2; @@ ( kmalloc( - sizeof(TYPE1) * sizeof(TYPE2) * COUNT + array3_size(COUNT, sizeof(TYPE1), sizeof(TYPE2)) , ...) | kmalloc( - sizeof(TYPE1) * sizeof(THING2) * (COUNT) + array3_size(COUNT, sizeof(TYPE1), sizeof(TYPE2)) , ...) | kmalloc( - sizeof(THING1) * sizeof(THING2) * COUNT + array3_size(COUNT, sizeof(THING1), sizeof(THING2)) , ...) | kmalloc( - sizeof(THING1) * sizeof(THING2) * (COUNT) + array3_size(COUNT, sizeof(THING1), sizeof(THING2)) , ...) | kmalloc( - sizeof(TYPE1) * sizeof(THING2) * COUNT + array3_size(COUNT, sizeof(TYPE1), sizeof(THING2)) , ...) | kmalloc( - sizeof(TYPE1) * sizeof(THING2) * (COUNT) + array3_size(COUNT, sizeof(TYPE1), sizeof(THING2)) , ...) ) // 3-factor product, only identifiers, with redundant parens removed. @@ identifier STRIDE, SIZE, COUNT; @@ ( kmalloc( - (COUNT) * STRIDE * SIZE + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - COUNT * (STRIDE) * SIZE + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - COUNT * STRIDE * (SIZE) + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - (COUNT) * (STRIDE) * SIZE + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - COUNT * (STRIDE) * (SIZE) + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - (COUNT) * STRIDE * (SIZE) + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - (COUNT) * (STRIDE) * (SIZE) + array3_size(COUNT, STRIDE, SIZE) , ...) | kmalloc( - COUNT * STRIDE * SIZE + array3_size(COUNT, STRIDE, SIZE) , ...) ) // Any remaining multi-factor products, first at least 3-factor products, // when they're not all constants... @@ expression E1, E2, E3; constant C1, C2, C3; @@ ( kmalloc(C1 * C2 * C3, ...) | kmalloc( - (E1) * E2 * E3 + array3_size(E1, E2, E3) , ...) | kmalloc( - (E1) * (E2) * E3 + array3_size(E1, E2, E3) , ...) | kmalloc( - (E1) * (E2) * (E3) + array3_size(E1, E2, E3) , ...) | kmalloc( - E1 * E2 * E3 + array3_size(E1, E2, E3) , ...) ) // And then all remaining 2 factors products when they're not all constants, // keeping sizeof() as the second factor argument. @@ expression THING, E1, E2; type TYPE; constant C1, C2, C3; @@ ( kmalloc(sizeof(THING) * C2, ...) | kmalloc(sizeof(TYPE) * C2, ...) | kmalloc(C1 * C2 * C3, ...) | kmalloc(C1 * C2, ...) | - kmalloc + kmalloc_array ( - sizeof(TYPE) * (E2) + E2, sizeof(TYPE) , ...) | - kmalloc + kmalloc_array ( - sizeof(TYPE) * E2 + E2, sizeof(TYPE) , ...) | - kmalloc + kmalloc_array ( - sizeof(THING) * (E2) + E2, sizeof(THING) , ...) | - kmalloc + kmalloc_array ( - sizeof(THING) * E2 + E2, sizeof(THING) , ...) | - kmalloc + kmalloc_array ( - (E1) * E2 + E1, E2 , ...) | - kmalloc + kmalloc_array ( - (E1) * (E2) + E1, E2 , ...) | - kmalloc + kmalloc_array ( - E1 * E2 + E1, E2 , ...) ) Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Allocate decoder buffers to avoid VLAsThomas Gleixner1-1/+30
To get rid of the variable length arrays on stack in the RS decoder it's necessary to allocate the decoder buffers per control structure instance. All usage sites have been checked for potential parallel decoder usage and fixed where necessary. Kees confirmed that the pstore decoding is strictly single threaded so there should be no surprises. Allocate them in the rs control structure sized depending on the number of roots for the chosen codec and adapt the decoder code to make use of them. Document the fact that decode operations based on a particular rs control instance cannot run in parallel and the caller has to ensure that as it's not possible to provide a proper locking construct which fits all use cases. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Acked-by: Kees Cook <keescook@chromium.org> Cc: Boris Brezillon <boris.brezillon@free-electrons.com> Cc: Tony Luck <tony.luck@intel.com> Cc: Segher Boessenkool <segher@kernel.crashing.org> Cc: Kernel Hardening <kernel-hardening@lists.openwall.com> Cc: Richard Weinberger <richard@nod.at> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Anton Vorontsov <anton@enomsg.org> Cc: Colin Cross <ccross@android.com> Cc: Andrew Morton <akpm@linuxfoundation.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Alasdair Kergon <agk@redhat.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Split rs control structThomas Gleixner1-58/+77
The decoder library uses variable length arrays on stack. To get rid of them it would be simple to allocate fixed length arrays on stack, but those might become rather large. The other solution is to allocate the buffers in the rs control structure, but this cannot be done as long as the structure can be shared by several users. Sharing is desired because the RS polynom tables are large and initialization is time consuming. To solve this split the codec information out of the control structure and have a pointer to a shared codec in it. Instantiate the control structure for each user, create a new codec if no shareable is avaiable yet. Adjust all affected usage sites to the new scheme. This allows to add per instance decoder buffers to the control structure later on. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Acked-by: Boris Brezillon <boris.brezillon@bootlin.com> Cc: Tony Luck <tony.luck@intel.com> Cc: Kees Cook <keescook@chromium.org> Cc: Segher Boessenkool <segher@kernel.crashing.org> Cc: Kernel Hardening <kernel-hardening@lists.openwall.com> Cc: Richard Weinberger <richard@nod.at> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Anton Vorontsov <anton@enomsg.org> Cc: Colin Cross <ccross@android.com> Cc: Andrew Morton <akpm@linuxfoundation.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Alasdair Kergon <agk@redhat.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Simplify error pathThomas Gleixner1-11/+6
The four error path labels in rs_init() can be reduced to one by allocating the struct with kzalloc so the pointers in the struct are NULL and can be unconditionally handed in to kfree() because they either point to an allocation or are NULL. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Remove GPL boilerplateThomas Gleixner1-4/+0
Now that SPDX identifiers are in place, remove the GPL boiler plate text. Leave the notices which document that Phil Karn granted permission in place (encode/decode source code). The modified files are code written for the kernel by me. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Reviewed-by: Kate Stewart <kstewart@linuxfoundation.org> Reviewed-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: Boris Brezillon <boris.brezillon@free-electrons.com> Cc: Tony Luck <tony.luck@intel.com> Cc: Kees Cook <keescook@chromium.org> Cc: Segher Boessenkool <segher@kernel.crashing.org> Cc: Kernel Hardening <kernel-hardening@lists.openwall.com> Cc: Richard Weinberger <richard@nod.at> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Anton Vorontsov <anton@enomsg.org> Cc: Colin Cross <ccross@android.com> Cc: Andrew Morton <akpm@linuxfoundation.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Alasdair Kergon <agk@redhat.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Add SPDX identifiersThomas Gleixner1-0/+1
The Reed-Solomon library is based on code from Phil Karn who granted permission to import it into the kernel under the GPL V2. See commit 15b5423757a7 ("Shared Reed-Solomon ECC library") in the history git tree at: git://git.kernel.org/pub/scm/linux/kernel/git/tglx/history.git ... The encoder/decoder code is lifted from the GPL'd userspace RS-library written by Phil Karn. I modified/wrapped it to provide the different functions which we need in the MTD/NAND code. ... Signed-Off-By: Thomas Gleixner <tglx@linutronix.de> Signed-Off-By: David Woodhouse <dwmw2@infradead.org> "No objections at all. Just keep the authorship notices." -- Phil Karn Add the proper SPDX identifiers according to Documentation/process/license-rules.rst. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Reviewed-by: Kate Stewart <kstewart@linuxfoundation.org> Reviewed-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: Boris Brezillon <boris.brezillon@free-electrons.com> Cc: Tony Luck <tony.luck@intel.com> Cc: Kees Cook <keescook@chromium.org> Cc: Segher Boessenkool <segher@kernel.crashing.org> Cc: Kernel Hardening <kernel-hardening@lists.openwall.com> Cc: Richard Weinberger <richard@nod.at> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Anton Vorontsov <anton@enomsg.org> Cc: Colin Cross <ccross@android.com> Cc: Andrew Morton <akpm@linuxfoundation.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Alasdair Kergon <agk@redhat.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Cleanup top level commentsThomas Gleixner1-8/+1
File references and stale CVS ids are really not useful. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Cc: Boris Brezillon <boris.brezillon@free-electrons.com> Cc: Tony Luck <tony.luck@intel.com> Cc: Kees Cook <keescook@chromium.org> Cc: Segher Boessenkool <segher@kernel.crashing.org> Cc: Kernel Hardening <kernel-hardening@lists.openwall.com> Cc: Richard Weinberger <richard@nod.at> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Anton Vorontsov <anton@enomsg.org> Cc: Colin Cross <ccross@android.com> Cc: Andrew Morton <akpm@linuxfoundation.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Alasdair Kergon <agk@redhat.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Cleanup whitespace damageThomas Gleixner1-6/+6
Instead of mixing the whitespace cleanup into functional changes, mop it up first. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Cc: Boris Brezillon <boris.brezillon@free-electrons.com> Cc: Tony Luck <tony.luck@intel.com> Cc: Kees Cook <keescook@chromium.org> Cc: Segher Boessenkool <segher@kernel.crashing.org> Cc: Kernel Hardening <kernel-hardening@lists.openwall.com> Cc: Richard Weinberger <richard@nod.at> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Anton Vorontsov <anton@enomsg.org> Cc: Colin Cross <ccross@android.com> Cc: Andrew Morton <akpm@linuxfoundation.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Alasdair Kergon <agk@redhat.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2018-04-24rslib: Add GFP aware init functionThomas Gleixner1-20/+23
The rslib usage in dm/verity_fec is broken because init_rs() can nest in GFP_NOIO mempool allocations as init_rs() is invoked from the mempool alloc callback. Provide a variant which takes gfp_t flags as argument. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Cc: Mike Snitzer <snitzer@redhat.com> Cc: Alasdair Kergon <agk@redhat.com> Cc: Neil Brown <neilb@suse.com> Signed-off-by: Kees Cook <keescook@chromium.org>
2008-04-18lib: Remove unnecessary inclusions of asm/semaphore.hMatthew Wilcox1-1/+0
reed_solomon doesn't use any of the functionality promised by asm/semaphore.h. Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
2007-10-20[MTD] [NAND] Replace -1 with -EBADMSG in nand error correction codeJörn Engel1-0/+2
Magic numerical values are just bad style. Particularly so when undocumented. Signed-off-by: Jörn Engel <joern@logfs.org> Signed-off-by: David Woodhouse <dwmw2@infradead.org>
2007-05-02[RSLIB] Support non-canonical GF representationsSegher Boessenkool1-15/+69
For the CAFÉ NAND controller, we need to support non-canonical representations of the Galois field. Allow the caller to provide its own function for generating the field, and CAFÉ can use rslib instead of its own implementation. Signed-off-by: Segher Boessenkool <segher@kernel.crashing.org> Signed-off-by: David Woodhouse <dwmw2@infradead.org>
2006-10-03fix file specification in commentsUwe Zeisberger1-1/+1
Many files include the filename at the beginning, serveral used a wrong one. Signed-off-by: Uwe Zeisberger <Uwe_Zeisberger@digi.com> Signed-off-by: Adrian Bunk <bunk@stusta.de>
2006-06-25[PATCH] reed-solomon: fix kernel-doc commentsRandy Dunlap1-9/+2
Fix kernel-doc formatting in Reed-Solomon code. Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-03-23[PATCH] sem2mutex: kernel/Arjan van de Ven1-5/+6
Semaphore to mutex conversion. The conversion was generated via scripts, and the result was validated automatically via a script as well. Signed-off-by: Arjan van de Ven <arjan@infradead.org> Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-11-07[LIB] reed_solomon: Clean up trailing white spacesThomas Gleixner1-32/+32
2005-04-16Linux-2.6.12-rc2v2.6.12-rc2Linus Torvalds1-0/+335
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!
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-30 05:56:09 +0000