437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 2) * Generic binary BCH encoding/decoding library
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 3) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 4) * This program is free software; you can redistribute it and/or modify it
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 5) * under the terms of the GNU General Public License version 2 as published by
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 6) * the Free Software Foundation.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 7) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 8) * This program is distributed in the hope that it will be useful, but WITHOUT
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 9) * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 10) * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 11) * more details.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 12) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 13) * You should have received a copy of the GNU General Public License along with
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 14) * this program; if not, write to the Free Software Foundation, Inc., 51
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 15) * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 16) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 17) * Copyright © 2011 Parrot S.A.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 18) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 19) * Author: Ivan Djelic <ivan.djelic@parrot.com>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 20) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 21) * Description:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 22) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 23) * This library provides runtime configurable encoding/decoding of binary
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 24) * Bose-Chaudhuri-Hocquenghem (BCH) codes.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 25) *
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 26) * Call bch_init to get a pointer to a newly allocated bch_control structure for
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 27) * the given m (Galois field order), t (error correction capability) and
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 28) * (optional) primitive polynomial parameters.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 29) *
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 30) * Call bch_encode to compute and store ecc parity bytes to a given buffer.
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 31) * Call bch_decode to detect and locate errors in received data.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 32) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 33) * On systems supporting hw BCH features, intermediate results may be provided
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 34) * to bch_decode in order to skip certain steps. See bch_decode() documentation
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 35) * for details.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 36) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 37) * Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 38) * parameters m and t; thus allowing extra compiler optimizations and providing
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 39) * better (up to 2x) encoding performance. Using this option makes sense when
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 40) * (m,t) are fixed and known in advance, e.g. when using BCH error correction
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 41) * on a particular NAND flash device.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 42) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 43) * Algorithmic details:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 44) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 45) * Encoding is performed by processing 32 input bits in parallel, using 4
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 46) * remainder lookup tables.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 47) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 48) * The final stage of decoding involves the following internal steps:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 49) * a. Syndrome computation
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 50) * b. Error locator polynomial computation using Berlekamp-Massey algorithm
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 51) * c. Error locator root finding (by far the most expensive step)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 52) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 53) * In this implementation, step c is not performed using the usual Chien search.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 54) * Instead, an alternative approach described in [1] is used. It consists in
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 55) * factoring the error locator polynomial using the Berlekamp Trace algorithm
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 56) * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 57) * solving techniques [2] are used. The resulting algorithm, called BTZ, yields
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 58) * much better performance than Chien search for usual (m,t) values (typically
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 59) * m >= 13, t < 32, see [1]).
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 60) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 61) * [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 62) * of characteristic 2, in: Western European Workshop on Research in Cryptology
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 63) * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 64) * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 65) * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 66) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 67)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 68) #include <linux/kernel.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 69) #include <linux/errno.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 70) #include <linux/init.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 71) #include <linux/module.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 72) #include <linux/slab.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 73) #include <linux/bitops.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 74) #include <asm/byteorder.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 75) #include <linux/bch.h>
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 76)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 77) #if defined(CONFIG_BCH_CONST_PARAMS)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 78) #define GF_M(_p) (CONFIG_BCH_CONST_M)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 79) #define GF_T(_p) (CONFIG_BCH_CONST_T)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 80) #define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1)
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 81) #define BCH_MAX_M (CONFIG_BCH_CONST_M)
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 82) #define BCH_MAX_T (CONFIG_BCH_CONST_T)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 83) #else
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 84) #define GF_M(_p) ((_p)->m)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 85) #define GF_T(_p) ((_p)->t)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 86) #define GF_N(_p) ((_p)->n)
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 87) #define BCH_MAX_M 15 /* 2KB */
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 88) #define BCH_MAX_T 64 /* 64 bit correction */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 89) #endif
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 90)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 91) #define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 92) #define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 93)
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 94) #define BCH_ECC_MAX_WORDS DIV_ROUND_UP(BCH_MAX_M * BCH_MAX_T, 32)
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 95)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 96) #ifndef dbg
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 97) #define dbg(_fmt, args...) do {} while (0)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 98) #endif
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 99)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 100) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 101) * represent a polynomial over GF(2^m)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 102) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 103) struct gf_poly {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 104) unsigned int deg; /* polynomial degree */
a44ce51370264 (Gustavo A. R. Silva 2020-04-06 20:09:57 -0700 105) unsigned int c[]; /* polynomial terms */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 106) };
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 107)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 108) /* given its degree, compute a polynomial size in bytes */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 109) #define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 110)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 111) /* polynomial of degree 1 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 112) struct gf_poly_deg1 {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 113) struct gf_poly poly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 114) unsigned int c[2];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 115) };
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 116)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 117) static u8 swap_bits_table[] = {
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 118) 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 119) 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 120) 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 121) 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 122) 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 123) 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 124) 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 125) 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 126) 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 127) 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 128) 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 129) 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 130) 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 131) 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 132) 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 133) 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 134) 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 135) 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 136) 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 137) 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 138) 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 139) 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 140) 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 141) 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 142) 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 143) 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 144) 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 145) 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 146) 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 147) 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 148) 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 149) 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 150) };
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 151)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 152) static u8 swap_bits(struct bch_control *bch, u8 in)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 153) {
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 154) if (!bch->swap_bits)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 155) return in;
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 156)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 157) return swap_bits_table[in];
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 158) }
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 159)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 160) /*
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 161) * same as bch_encode(), but process input data one byte at a time
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 162) */
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 163) static void bch_encode_unaligned(struct bch_control *bch,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 164) const unsigned char *data, unsigned int len,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 165) uint32_t *ecc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 166) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 167) int i;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 168) const uint32_t *p;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 169) const int l = BCH_ECC_WORDS(bch)-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 170)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 171) while (len--) {
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 172) u8 tmp = swap_bits(bch, *data++);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 173)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 174) p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 175)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 176) for (i = 0; i < l; i++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 177) ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 178)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 179) ecc[l] = (ecc[l] << 8)^(*p);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 180) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 181) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 182)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 183) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 184) * convert ecc bytes to aligned, zero-padded 32-bit ecc words
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 185) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 186) static void load_ecc8(struct bch_control *bch, uint32_t *dst,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 187) const uint8_t *src)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 188) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 189) uint8_t pad[4] = {0, 0, 0, 0};
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 190) unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 191)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 192) for (i = 0; i < nwords; i++, src += 4)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 193) dst[i] = ((u32)swap_bits(bch, src[0]) << 24) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 194) ((u32)swap_bits(bch, src[1]) << 16) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 195) ((u32)swap_bits(bch, src[2]) << 8) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 196) swap_bits(bch, src[3]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 197)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 198) memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 199) dst[nwords] = ((u32)swap_bits(bch, pad[0]) << 24) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 200) ((u32)swap_bits(bch, pad[1]) << 16) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 201) ((u32)swap_bits(bch, pad[2]) << 8) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 202) swap_bits(bch, pad[3]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 203) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 204)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 205) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 206) * convert 32-bit ecc words to ecc bytes
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 207) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 208) static void store_ecc8(struct bch_control *bch, uint8_t *dst,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 209) const uint32_t *src)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 210) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 211) uint8_t pad[4];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 212) unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 213)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 214) for (i = 0; i < nwords; i++) {
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 215) *dst++ = swap_bits(bch, src[i] >> 24);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 216) *dst++ = swap_bits(bch, src[i] >> 16);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 217) *dst++ = swap_bits(bch, src[i] >> 8);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 218) *dst++ = swap_bits(bch, src[i]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 219) }
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 220) pad[0] = swap_bits(bch, src[nwords] >> 24);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 221) pad[1] = swap_bits(bch, src[nwords] >> 16);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 222) pad[2] = swap_bits(bch, src[nwords] >> 8);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 223) pad[3] = swap_bits(bch, src[nwords]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 224) memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 225) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 226)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 227) /**
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 228) * bch_encode - calculate BCH ecc parity of data
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 229) * @bch: BCH control structure
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 230) * @data: data to encode
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 231) * @len: data length in bytes
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 232) * @ecc: ecc parity data, must be initialized by caller
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 233) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 234) * The @ecc parity array is used both as input and output parameter, in order to
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 235) * allow incremental computations. It should be of the size indicated by member
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 236) * @ecc_bytes of @bch, and should be initialized to 0 before the first call.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 237) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 238) * The exact number of computed ecc parity bits is given by member @ecc_bits of
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 239) * @bch; it may be less than m*t for large values of t.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 240) */
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 241) void bch_encode(struct bch_control *bch, const uint8_t *data,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 242) unsigned int len, uint8_t *ecc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 243) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 244) const unsigned int l = BCH_ECC_WORDS(bch)-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 245) unsigned int i, mlen;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 246) unsigned long m;
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 247) uint32_t w, r[BCH_ECC_MAX_WORDS];
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 248) const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 249) const uint32_t * const tab0 = bch->mod8_tab;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 250) const uint32_t * const tab1 = tab0 + 256*(l+1);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 251) const uint32_t * const tab2 = tab1 + 256*(l+1);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 252) const uint32_t * const tab3 = tab2 + 256*(l+1);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 253) const uint32_t *pdata, *p0, *p1, *p2, *p3;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 254)
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 255) if (WARN_ON(r_bytes > sizeof(r)))
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 256) return;
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 257)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 258) if (ecc) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 259) /* load ecc parity bytes into internal 32-bit buffer */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 260) load_ecc8(bch, bch->ecc_buf, ecc);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 261) } else {
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 262) memset(bch->ecc_buf, 0, r_bytes);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 263) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 264)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 265) /* process first unaligned data bytes */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 266) m = ((unsigned long)data) & 3;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 267) if (m) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 268) mlen = (len < (4-m)) ? len : 4-m;
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 269) bch_encode_unaligned(bch, data, mlen, bch->ecc_buf);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 270) data += mlen;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 271) len -= mlen;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 272) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 273)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 274) /* process 32-bit aligned data words */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 275) pdata = (uint32_t *)data;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 276) mlen = len/4;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 277) data += 4*mlen;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 278) len -= 4*mlen;
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 279) memcpy(r, bch->ecc_buf, r_bytes);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 280)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 281) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 282) * split each 32-bit word into 4 polynomials of weight 8 as follows:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 283) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 284) * 31 ...24 23 ...16 15 ... 8 7 ... 0
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 285) * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 286) * tttttttt mod g = r0 (precomputed)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 287) * zzzzzzzz 00000000 mod g = r1 (precomputed)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 288) * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 289) * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 290) * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 291) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 292) while (mlen--) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 293) /* input data is read in big-endian format */
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 294) w = cpu_to_be32(*pdata++);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 295) if (bch->swap_bits)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 296) w = (u32)swap_bits(bch, w) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 297) ((u32)swap_bits(bch, w >> 8) << 8) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 298) ((u32)swap_bits(bch, w >> 16) << 16) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 299) ((u32)swap_bits(bch, w >> 24) << 24);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 300) w ^= r[0];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 301) p0 = tab0 + (l+1)*((w >> 0) & 0xff);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 302) p1 = tab1 + (l+1)*((w >> 8) & 0xff);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 303) p2 = tab2 + (l+1)*((w >> 16) & 0xff);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 304) p3 = tab3 + (l+1)*((w >> 24) & 0xff);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 305)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 306) for (i = 0; i < l; i++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 307) r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 308)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 309) r[l] = p0[l]^p1[l]^p2[l]^p3[l];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 310) }
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 311) memcpy(bch->ecc_buf, r, r_bytes);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 312)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 313) /* process last unaligned bytes */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 314) if (len)
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 315) bch_encode_unaligned(bch, data, len, bch->ecc_buf);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 316)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 317) /* store ecc parity bytes into original parity buffer */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 318) if (ecc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 319) store_ecc8(bch, ecc, bch->ecc_buf);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 320) }
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 321) EXPORT_SYMBOL_GPL(bch_encode);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 322)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 323) static inline int modulo(struct bch_control *bch, unsigned int v)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 324) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 325) const unsigned int n = GF_N(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 326) while (v >= n) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 327) v -= n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 328) v = (v & n) + (v >> GF_M(bch));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 329) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 330) return v;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 331) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 332)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 333) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 334) * shorter and faster modulo function, only works when v < 2N.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 335) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 336) static inline int mod_s(struct bch_control *bch, unsigned int v)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 337) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 338) const unsigned int n = GF_N(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 339) return (v < n) ? v : v-n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 340) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 341)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 342) static inline int deg(unsigned int poly)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 343) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 344) /* polynomial degree is the most-significant bit index */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 345) return fls(poly)-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 346) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 347)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 348) static inline int parity(unsigned int x)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 349) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 350) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 351) * public domain code snippet, lifted from
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 352) * http://www-graphics.stanford.edu/~seander/bithacks.html
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 353) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 354) x ^= x >> 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 355) x ^= x >> 2;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 356) x = (x & 0x11111111U) * 0x11111111U;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 357) return (x >> 28) & 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 358) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 359)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 360) /* Galois field basic operations: multiply, divide, inverse, etc. */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 361)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 362) static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 363) unsigned int b)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 364) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 365) return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 366) bch->a_log_tab[b])] : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 367) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 368)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 369) static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 370) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 371) return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 372) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 373)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 374) static inline unsigned int gf_div(struct bch_control *bch, unsigned int a,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 375) unsigned int b)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 376) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 377) return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 378) GF_N(bch)-bch->a_log_tab[b])] : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 379) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 380)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 381) static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 382) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 383) return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 384) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 385)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 386) static inline unsigned int a_pow(struct bch_control *bch, int i)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 387) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 388) return bch->a_pow_tab[modulo(bch, i)];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 389) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 390)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 391) static inline int a_log(struct bch_control *bch, unsigned int x)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 392) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 393) return bch->a_log_tab[x];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 394) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 395)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 396) static inline int a_ilog(struct bch_control *bch, unsigned int x)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 397) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 398) return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 399) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 400)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 401) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 402) * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 403) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 404) static void compute_syndromes(struct bch_control *bch, uint32_t *ecc,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 405) unsigned int *syn)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 406) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 407) int i, j, s;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 408) unsigned int m;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 409) uint32_t poly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 410) const int t = GF_T(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 411)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 412) s = bch->ecc_bits;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 413)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 414) /* make sure extra bits in last ecc word are cleared */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 415) m = ((unsigned int)s) & 31;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 416) if (m)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 417) ecc[s/32] &= ~((1u << (32-m))-1);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 418) memset(syn, 0, 2*t*sizeof(*syn));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 419)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 420) /* compute v(a^j) for j=1 .. 2t-1 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 421) do {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 422) poly = *ecc++;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 423) s -= 32;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 424) while (poly) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 425) i = deg(poly);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 426) for (j = 0; j < 2*t; j += 2)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 427) syn[j] ^= a_pow(bch, (j+1)*(i+s));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 428)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 429) poly ^= (1 << i);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 430) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 431) } while (s > 0);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 432)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 433) /* v(a^(2j)) = v(a^j)^2 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 434) for (j = 0; j < t; j++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 435) syn[2*j+1] = gf_sqr(bch, syn[j]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 436) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 437)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 438) static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 439) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 440) memcpy(dst, src, GF_POLY_SZ(src->deg));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 441) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 442)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 443) static int compute_error_locator_polynomial(struct bch_control *bch,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 444) const unsigned int *syn)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 445) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 446) const unsigned int t = GF_T(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 447) const unsigned int n = GF_N(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 448) unsigned int i, j, tmp, l, pd = 1, d = syn[0];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 449) struct gf_poly *elp = bch->elp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 450) struct gf_poly *pelp = bch->poly_2t[0];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 451) struct gf_poly *elp_copy = bch->poly_2t[1];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 452) int k, pp = -1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 453)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 454) memset(pelp, 0, GF_POLY_SZ(2*t));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 455) memset(elp, 0, GF_POLY_SZ(2*t));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 456)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 457) pelp->deg = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 458) pelp->c[0] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 459) elp->deg = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 460) elp->c[0] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 461)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 462) /* use simplified binary Berlekamp-Massey algorithm */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 463) for (i = 0; (i < t) && (elp->deg <= t); i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 464) if (d) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 465) k = 2*i-pp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 466) gf_poly_copy(elp_copy, elp);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 467) /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 468) tmp = a_log(bch, d)+n-a_log(bch, pd);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 469) for (j = 0; j <= pelp->deg; j++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 470) if (pelp->c[j]) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 471) l = a_log(bch, pelp->c[j]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 472) elp->c[j+k] ^= a_pow(bch, tmp+l);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 473) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 474) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 475) /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 476) tmp = pelp->deg+k;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 477) if (tmp > elp->deg) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 478) elp->deg = tmp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 479) gf_poly_copy(pelp, elp_copy);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 480) pd = d;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 481) pp = 2*i;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 482) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 483) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 484) /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 485) if (i < t-1) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 486) d = syn[2*i+2];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 487) for (j = 1; j <= elp->deg; j++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 488) d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 489) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 490) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 491) dbg("elp=%s\n", gf_poly_str(elp));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 492) return (elp->deg > t) ? -1 : (int)elp->deg;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 493) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 494)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 495) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 496) * solve a m x m linear system in GF(2) with an expected number of solutions,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 497) * and return the number of found solutions
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 498) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 499) static int solve_linear_system(struct bch_control *bch, unsigned int *rows,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 500) unsigned int *sol, int nsol)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 501) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 502) const int m = GF_M(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 503) unsigned int tmp, mask;
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 504) int rem, c, r, p, k, param[BCH_MAX_M];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 505)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 506) k = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 507) mask = 1 << m;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 508)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 509) /* Gaussian elimination */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 510) for (c = 0; c < m; c++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 511) rem = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 512) p = c-k;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 513) /* find suitable row for elimination */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 514) for (r = p; r < m; r++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 515) if (rows[r] & mask) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 516) if (r != p) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 517) tmp = rows[r];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 518) rows[r] = rows[p];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 519) rows[p] = tmp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 520) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 521) rem = r+1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 522) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 523) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 524) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 525) if (rem) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 526) /* perform elimination on remaining rows */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 527) tmp = rows[p];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 528) for (r = rem; r < m; r++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 529) if (rows[r] & mask)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 530) rows[r] ^= tmp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 531) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 532) } else {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 533) /* elimination not needed, store defective row index */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 534) param[k++] = c;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 535) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 536) mask >>= 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 537) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 538) /* rewrite system, inserting fake parameter rows */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 539) if (k > 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 540) p = k;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 541) for (r = m-1; r >= 0; r--) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 542) if ((r > m-1-k) && rows[r])
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 543) /* system has no solution */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 544) return 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 545)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 546) rows[r] = (p && (r == param[p-1])) ?
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 547) p--, 1u << (m-r) : rows[r-p];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 548) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 549) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 550)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 551) if (nsol != (1 << k))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 552) /* unexpected number of solutions */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 553) return 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 554)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 555) for (p = 0; p < nsol; p++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 556) /* set parameters for p-th solution */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 557) for (c = 0; c < k; c++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 558) rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 559)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 560) /* compute unique solution */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 561) tmp = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 562) for (r = m-1; r >= 0; r--) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 563) mask = rows[r] & (tmp|1);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 564) tmp |= parity(mask) << (m-r);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 565) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 566) sol[p] = tmp >> 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 567) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 568) return nsol;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 569) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 570)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 571) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 572) * this function builds and solves a linear system for finding roots of a degree
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 573) * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m).
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 574) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 575) static int find_affine4_roots(struct bch_control *bch, unsigned int a,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 576) unsigned int b, unsigned int c,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 577) unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 578) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 579) int i, j, k;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 580) const int m = GF_M(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 581) unsigned int mask = 0xff, t, rows[16] = {0,};
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 582)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 583) j = a_log(bch, b);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 584) k = a_log(bch, a);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 585) rows[0] = c;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 586)
0523c6922e8bd (Bhaskar Chowdhury 2021-05-06 18:03:25 -0700 587) /* build linear system to solve X^4+aX^2+bX+c = 0 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 588) for (i = 0; i < m; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 589) rows[i+1] = bch->a_pow_tab[4*i]^
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 590) (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 591) (b ? bch->a_pow_tab[mod_s(bch, j)] : 0);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 592) j++;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 593) k += 2;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 594) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 595) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 596) * transpose 16x16 matrix before passing it to linear solver
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 597) * warning: this code assumes m < 16
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 598) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 599) for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 600) for (k = 0; k < 16; k = (k+j+1) & ~j) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 601) t = ((rows[k] >> j)^rows[k+j]) & mask;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 602) rows[k] ^= (t << j);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 603) rows[k+j] ^= t;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 604) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 605) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 606) return solve_linear_system(bch, rows, roots, 4);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 607) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 608)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 609) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 610) * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 611) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 612) static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 613) unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 614) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 615) int n = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 616)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 617) if (poly->c[0])
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 618) /* poly[X] = bX+c with c!=0, root=c/b */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 619) roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 620) bch->a_log_tab[poly->c[1]]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 621) return n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 622) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 623)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 624) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 625) * compute roots of a degree 2 polynomial over GF(2^m)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 626) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 627) static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 628) unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 629) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 630) int n = 0, i, l0, l1, l2;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 631) unsigned int u, v, r;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 632)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 633) if (poly->c[0] && poly->c[1]) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 634)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 635) l0 = bch->a_log_tab[poly->c[0]];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 636) l1 = bch->a_log_tab[poly->c[1]];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 637) l2 = bch->a_log_tab[poly->c[2]];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 638)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 639) /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 640) u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 641) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 642) * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi):
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 643) * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) =
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 644) * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 645) * i.e. r and r+1 are roots iff Tr(u)=0
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 646) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 647) r = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 648) v = u;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 649) while (v) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 650) i = deg(v);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 651) r ^= bch->xi_tab[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 652) v ^= (1 << i);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 653) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 654) /* verify root */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 655) if ((gf_sqr(bch, r)^r) == u) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 656) /* reverse z=a/bX transformation and compute log(1/r) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 657) roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 658) bch->a_log_tab[r]+l2);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 659) roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 660) bch->a_log_tab[r^1]+l2);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 661) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 662) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 663) return n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 664) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 665)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 666) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 667) * compute roots of a degree 3 polynomial over GF(2^m)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 668) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 669) static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 670) unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 671) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 672) int i, n = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 673) unsigned int a, b, c, a2, b2, c2, e3, tmp[4];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 674)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 675) if (poly->c[0]) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 676) /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 677) e3 = poly->c[3];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 678) c2 = gf_div(bch, poly->c[0], e3);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 679) b2 = gf_div(bch, poly->c[1], e3);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 680) a2 = gf_div(bch, poly->c[2], e3);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 681)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 682) /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 683) c = gf_mul(bch, a2, c2); /* c = a2c2 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 684) b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 685) a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 686)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 687) /* find the 4 roots of this affine polynomial */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 688) if (find_affine4_roots(bch, a, b, c, tmp) == 4) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 689) /* remove a2 from final list of roots */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 690) for (i = 0; i < 4; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 691) if (tmp[i] != a2)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 692) roots[n++] = a_ilog(bch, tmp[i]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 693) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 694) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 695) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 696) return n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 697) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 698)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 699) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 700) * compute roots of a degree 4 polynomial over GF(2^m)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 701) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 702) static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 703) unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 704) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 705) int i, l, n = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 706) unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 707)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 708) if (poly->c[0] == 0)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 709) return 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 710)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 711) /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 712) e4 = poly->c[4];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 713) d = gf_div(bch, poly->c[0], e4);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 714) c = gf_div(bch, poly->c[1], e4);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 715) b = gf_div(bch, poly->c[2], e4);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 716) a = gf_div(bch, poly->c[3], e4);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 717)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 718) /* use Y=1/X transformation to get an affine polynomial */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 719) if (a) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 720) /* first, eliminate cX by using z=X+e with ae^2+c=0 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 721) if (c) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 722) /* compute e such that e^2 = c/a */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 723) f = gf_div(bch, c, a);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 724) l = a_log(bch, f);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 725) l += (l & 1) ? GF_N(bch) : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 726) e = a_pow(bch, l/2);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 727) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 728) * use transformation z=X+e:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 729) * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 730) * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 731) * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 732) * z^4 + az^3 + b'z^2 + d'
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 733) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 734) d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 735) b = gf_mul(bch, a, e)^b;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 736) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 737) /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 738) if (d == 0)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 739) /* assume all roots have multiplicity 1 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 740) return 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 741)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 742) c2 = gf_inv(bch, d);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 743) b2 = gf_div(bch, a, d);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 744) a2 = gf_div(bch, b, d);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 745) } else {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 746) /* polynomial is already affine */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 747) c2 = d;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 748) b2 = c;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 749) a2 = b;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 750) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 751) /* find the 4 roots of this affine polynomial */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 752) if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 753) for (i = 0; i < 4; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 754) /* post-process roots (reverse transformations) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 755) f = a ? gf_inv(bch, roots[i]) : roots[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 756) roots[i] = a_ilog(bch, f^e);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 757) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 758) n = 4;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 759) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 760) return n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 761) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 762)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 763) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 764) * build monic, log-based representation of a polynomial
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 765) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 766) static void gf_poly_logrep(struct bch_control *bch,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 767) const struct gf_poly *a, int *rep)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 768) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 769) int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 770)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 771) /* represent 0 values with -1; warning, rep[d] is not set to 1 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 772) for (i = 0; i < d; i++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 773) rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 774) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 775)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 776) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 777) * compute polynomial Euclidean division remainder in GF(2^m)[X]
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 778) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 779) static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 780) const struct gf_poly *b, int *rep)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 781) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 782) int la, p, m;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 783) unsigned int i, j, *c = a->c;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 784) const unsigned int d = b->deg;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 785)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 786) if (a->deg < d)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 787) return;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 788)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 789) /* reuse or compute log representation of denominator */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 790) if (!rep) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 791) rep = bch->cache;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 792) gf_poly_logrep(bch, b, rep);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 793) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 794)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 795) for (j = a->deg; j >= d; j--) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 796) if (c[j]) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 797) la = a_log(bch, c[j]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 798) p = j-d;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 799) for (i = 0; i < d; i++, p++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 800) m = rep[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 801) if (m >= 0)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 802) c[p] ^= bch->a_pow_tab[mod_s(bch,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 803) m+la)];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 804) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 805) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 806) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 807) a->deg = d-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 808) while (!c[a->deg] && a->deg)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 809) a->deg--;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 810) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 811)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 812) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 813) * compute polynomial Euclidean division quotient in GF(2^m)[X]
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 814) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 815) static void gf_poly_div(struct bch_control *bch, struct gf_poly *a,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 816) const struct gf_poly *b, struct gf_poly *q)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 817) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 818) if (a->deg >= b->deg) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 819) q->deg = a->deg-b->deg;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 820) /* compute a mod b (modifies a) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 821) gf_poly_mod(bch, a, b, NULL);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 822) /* quotient is stored in upper part of polynomial a */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 823) memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 824) } else {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 825) q->deg = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 826) q->c[0] = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 827) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 828) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 829)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 830) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 831) * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X]
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 832) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 833) static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 834) struct gf_poly *b)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 835) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 836) struct gf_poly *tmp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 837)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 838) dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 839)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 840) if (a->deg < b->deg) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 841) tmp = b;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 842) b = a;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 843) a = tmp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 844) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 845)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 846) while (b->deg > 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 847) gf_poly_mod(bch, a, b, NULL);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 848) tmp = b;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 849) b = a;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 850) a = tmp;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 851) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 852)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 853) dbg("%s\n", gf_poly_str(a));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 854)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 855) return a;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 856) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 857)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 858) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 859) * Given a polynomial f and an integer k, compute Tr(a^kX) mod f
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 860) * This is used in Berlekamp Trace algorithm for splitting polynomials
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 861) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 862) static void compute_trace_bk_mod(struct bch_control *bch, int k,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 863) const struct gf_poly *f, struct gf_poly *z,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 864) struct gf_poly *out)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 865) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 866) const int m = GF_M(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 867) int i, j;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 868)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 869) /* z contains z^2j mod f */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 870) z->deg = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 871) z->c[0] = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 872) z->c[1] = bch->a_pow_tab[k];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 873)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 874) out->deg = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 875) memset(out, 0, GF_POLY_SZ(f->deg));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 876)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 877) /* compute f log representation only once */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 878) gf_poly_logrep(bch, f, bch->cache);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 879)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 880) for (i = 0; i < m; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 881) /* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 882) for (j = z->deg; j >= 0; j--) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 883) out->c[j] ^= z->c[j];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 884) z->c[2*j] = gf_sqr(bch, z->c[j]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 885) z->c[2*j+1] = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 886) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 887) if (z->deg > out->deg)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 888) out->deg = z->deg;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 889)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 890) if (i < m-1) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 891) z->deg *= 2;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 892) /* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 893) gf_poly_mod(bch, z, f, bch->cache);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 894) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 895) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 896) while (!out->c[out->deg] && out->deg)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 897) out->deg--;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 898)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 899) dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 900) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 901)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 902) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 903) * factor a polynomial using Berlekamp Trace algorithm (BTA)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 904) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 905) static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 906) struct gf_poly **g, struct gf_poly **h)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 907) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 908) struct gf_poly *f2 = bch->poly_2t[0];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 909) struct gf_poly *q = bch->poly_2t[1];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 910) struct gf_poly *tk = bch->poly_2t[2];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 911) struct gf_poly *z = bch->poly_2t[3];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 912) struct gf_poly *gcd;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 913)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 914) dbg("factoring %s...\n", gf_poly_str(f));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 915)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 916) *g = f;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 917) *h = NULL;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 918)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 919) /* tk = Tr(a^k.X) mod f */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 920) compute_trace_bk_mod(bch, k, f, z, tk);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 921)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 922) if (tk->deg > 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 923) /* compute g = gcd(f, tk) (destructive operation) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 924) gf_poly_copy(f2, f);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 925) gcd = gf_poly_gcd(bch, f2, tk);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 926) if (gcd->deg < f->deg) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 927) /* compute h=f/gcd(f,tk); this will modify f and q */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 928) gf_poly_div(bch, f, gcd, q);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 929) /* store g and h in-place (clobbering f) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 930) *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 931) gf_poly_copy(*g, gcd);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 932) gf_poly_copy(*h, q);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 933) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 934) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 935) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 936)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 937) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 938) * find roots of a polynomial, using BTZ algorithm; see the beginning of this
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 939) * file for details
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 940) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 941) static int find_poly_roots(struct bch_control *bch, unsigned int k,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 942) struct gf_poly *poly, unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 943) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 944) int cnt;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 945) struct gf_poly *f1, *f2;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 946)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 947) switch (poly->deg) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 948) /* handle low degree polynomials with ad hoc techniques */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 949) case 1:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 950) cnt = find_poly_deg1_roots(bch, poly, roots);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 951) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 952) case 2:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 953) cnt = find_poly_deg2_roots(bch, poly, roots);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 954) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 955) case 3:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 956) cnt = find_poly_deg3_roots(bch, poly, roots);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 957) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 958) case 4:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 959) cnt = find_poly_deg4_roots(bch, poly, roots);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 960) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 961) default:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 962) /* factor polynomial using Berlekamp Trace Algorithm (BTA) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 963) cnt = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 964) if (poly->deg && (k <= GF_M(bch))) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 965) factor_polynomial(bch, k, poly, &f1, &f2);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 966) if (f1)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 967) cnt += find_poly_roots(bch, k+1, f1, roots);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 968) if (f2)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 969) cnt += find_poly_roots(bch, k+1, f2, roots+cnt);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 970) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 971) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 972) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 973) return cnt;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 974) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 975)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 976) #if defined(USE_CHIEN_SEARCH)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 977) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 978) * exhaustive root search (Chien) implementation - not used, included only for
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 979) * reference/comparison tests
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 980) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 981) static int chien_search(struct bch_control *bch, unsigned int len,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 982) struct gf_poly *p, unsigned int *roots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 983) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 984) int m;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 985) unsigned int i, j, syn, syn0, count = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 986) const unsigned int k = 8*len+bch->ecc_bits;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 987)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 988) /* use a log-based representation of polynomial */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 989) gf_poly_logrep(bch, p, bch->cache);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 990) bch->cache[p->deg] = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 991) syn0 = gf_div(bch, p->c[0], p->c[p->deg]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 992)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 993) for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 994) /* compute elp(a^i) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 995) for (j = 1, syn = syn0; j <= p->deg; j++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 996) m = bch->cache[j];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 997) if (m >= 0)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 998) syn ^= a_pow(bch, m+j*i);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 999) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1000) if (syn == 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1001) roots[count++] = GF_N(bch)-i;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1002) if (count == p->deg)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1003) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1004) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1005) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1006) return (count == p->deg) ? count : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1007) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1008) #define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1009) #endif /* USE_CHIEN_SEARCH */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1010)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1011) /**
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1012) * bch_decode - decode received codeword and find bit error locations
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1013) * @bch: BCH control structure
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1014) * @data: received data, ignored if @calc_ecc is provided
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1015) * @len: data length in bytes, must always be provided
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1016) * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1017) * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1018) * @syn: hw computed syndrome data (if NULL, syndrome is calculated)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1019) * @errloc: output array of error locations
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1020) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1021) * Returns:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1022) * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1023) * invalid parameters were provided
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1024) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1025) * Depending on the available hw BCH support and the need to compute @calc_ecc
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1026) * separately (using bch_encode()), this function should be called with one of
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1027) * the following parameter configurations -
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1028) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1029) * by providing @data and @recv_ecc only:
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1030) * bch_decode(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1031) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1032) * by providing @recv_ecc and @calc_ecc:
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1033) * bch_decode(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1034) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1035) * by providing ecc = recv_ecc XOR calc_ecc:
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1036) * bch_decode(@bch, NULL, @len, NULL, ecc, NULL, @errloc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1037) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1038) * by providing syndrome results @syn:
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1039) * bch_decode(@bch, NULL, @len, NULL, NULL, @syn, @errloc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1040) *
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1041) * Once bch_decode() has successfully returned with a positive value, error
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1042) * locations returned in array @errloc should be interpreted as follows -
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1043) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1044) * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1045) * data correction)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1046) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1047) * if (errloc[n] < 8*len), then n-th error is located in data and can be
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1048) * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1049) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1050) * Note that this function does not perform any data correction by itself, it
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1051) * merely indicates error locations.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1052) */
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1053) int bch_decode(struct bch_control *bch, const uint8_t *data, unsigned int len,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1054) const uint8_t *recv_ecc, const uint8_t *calc_ecc,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1055) const unsigned int *syn, unsigned int *errloc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1056) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1057) const unsigned int ecc_words = BCH_ECC_WORDS(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1058) unsigned int nbits;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1059) int i, err, nroots;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1060) uint32_t sum;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1061)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1062) /* sanity check: make sure data length can be handled */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1063) if (8*len > (bch->n-bch->ecc_bits))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1064) return -EINVAL;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1065)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1066) /* if caller does not provide syndromes, compute them */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1067) if (!syn) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1068) if (!calc_ecc) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1069) /* compute received data ecc into an internal buffer */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1070) if (!data || !recv_ecc)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1071) return -EINVAL;
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1072) bch_encode(bch, data, len, NULL);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1073) } else {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1074) /* load provided calculated ecc */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1075) load_ecc8(bch, bch->ecc_buf, calc_ecc);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1076) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1077) /* load received ecc or assume it was XORed in calc_ecc */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1078) if (recv_ecc) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1079) load_ecc8(bch, bch->ecc_buf2, recv_ecc);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1080) /* XOR received and calculated ecc */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1081) for (i = 0, sum = 0; i < (int)ecc_words; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1082) bch->ecc_buf[i] ^= bch->ecc_buf2[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1083) sum |= bch->ecc_buf[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1084) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1085) if (!sum)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1086) /* no error found */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1087) return 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1088) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1089) compute_syndromes(bch, bch->ecc_buf, bch->syn);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1090) syn = bch->syn;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1091) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1092)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1093) err = compute_error_locator_polynomial(bch, syn);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1094) if (err > 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1095) nroots = find_poly_roots(bch, 1, bch->elp, errloc);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1096) if (err != nroots)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1097) err = -1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1098) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1099) if (err > 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1100) /* post-process raw error locations for easier correction */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1101) nbits = (len*8)+bch->ecc_bits;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1102) for (i = 0; i < err; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1103) if (errloc[i] >= nbits) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1104) err = -1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1105) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1106) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1107) errloc[i] = nbits-1-errloc[i];
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1108) if (!bch->swap_bits)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1109) errloc[i] = (errloc[i] & ~7) |
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1110) (7-(errloc[i] & 7));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1111) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1112) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1113) return (err >= 0) ? err : -EBADMSG;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1114) }
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1115) EXPORT_SYMBOL_GPL(bch_decode);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1116)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1117) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1118) * generate Galois field lookup tables
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1119) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1120) static int build_gf_tables(struct bch_control *bch, unsigned int poly)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1121) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1122) unsigned int i, x = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1123) const unsigned int k = 1 << deg(poly);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1124)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1125) /* primitive polynomial must be of degree m */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1126) if (k != (1u << GF_M(bch)))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1127) return -1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1128)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1129) for (i = 0; i < GF_N(bch); i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1130) bch->a_pow_tab[i] = x;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1131) bch->a_log_tab[x] = i;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1132) if (i && (x == 1))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1133) /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1134) return -1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1135) x <<= 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1136) if (x & k)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1137) x ^= poly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1138) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1139) bch->a_pow_tab[GF_N(bch)] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1140) bch->a_log_tab[0] = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1141)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1142) return 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1143) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1144)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1145) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1146) * compute generator polynomial remainder tables for fast encoding
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1147) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1148) static void build_mod8_tables(struct bch_control *bch, const uint32_t *g)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1149) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1150) int i, j, b, d;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1151) uint32_t data, hi, lo, *tab;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1152) const int l = BCH_ECC_WORDS(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1153) const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1154) const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1155)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1156) memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1157)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1158) for (i = 0; i < 256; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1159) /* p(X)=i is a small polynomial of weight <= 8 */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1160) for (b = 0; b < 4; b++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1161) /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1162) tab = bch->mod8_tab + (b*256+i)*l;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1163) data = i << (8*b);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1164) while (data) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1165) d = deg(data);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1166) /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1167) data ^= g[0] >> (31-d);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1168) for (j = 0; j < ecclen; j++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1169) hi = (d < 31) ? g[j] << (d+1) : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1170) lo = (j+1 < plen) ?
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1171) g[j+1] >> (31-d) : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1172) tab[j] ^= hi|lo;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1173) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1174) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1175) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1176) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1177) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1178)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1179) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1180) * build a base for factoring degree 2 polynomials
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1181) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1182) static int build_deg2_base(struct bch_control *bch)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1183) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1184) const int m = GF_M(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1185) int i, j, r;
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 1186) unsigned int sum, x, y, remaining, ak = 0, xi[BCH_MAX_M];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1187)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1188) /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1189) for (i = 0; i < m; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1190) for (j = 0, sum = 0; j < m; j++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1191) sum ^= a_pow(bch, i*(1 << j));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1192)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1193) if (sum) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1194) ak = bch->a_pow_tab[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1195) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1196) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1197) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1198) /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1199) remaining = m;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1200) memset(xi, 0, sizeof(xi));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1201)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1202) for (x = 0; (x <= GF_N(bch)) && remaining; x++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1203) y = gf_sqr(bch, x)^x;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1204) for (i = 0; i < 2; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1205) r = a_log(bch, y);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1206) if (y && (r < m) && !xi[r]) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1207) bch->xi_tab[r] = x;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1208) xi[r] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1209) remaining--;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1210) dbg("x%d = %x\n", r, x);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1211) break;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1212) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1213) y ^= ak;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1214) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1215) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1216) /* should not happen but check anyway */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1217) return remaining ? -1 : 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1218) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1219)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1220) static void *bch_alloc(size_t size, int *err)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1221) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1222) void *ptr;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1223)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1224) ptr = kmalloc(size, GFP_KERNEL);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1225) if (ptr == NULL)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1226) *err = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1227) return ptr;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1228) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1229)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1230) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1231) * compute generator polynomial for given (m,t) parameters.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1232) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1233) static uint32_t *compute_generator_polynomial(struct bch_control *bch)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1234) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1235) const unsigned int m = GF_M(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1236) const unsigned int t = GF_T(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1237) int n, err = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1238) unsigned int i, j, nbits, r, word, *roots;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1239) struct gf_poly *g;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1240) uint32_t *genpoly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1241)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1242) g = bch_alloc(GF_POLY_SZ(m*t), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1243) roots = bch_alloc((bch->n+1)*sizeof(*roots), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1244) genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1245)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1246) if (err) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1247) kfree(genpoly);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1248) genpoly = NULL;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1249) goto finish;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1250) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1251)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1252) /* enumerate all roots of g(X) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1253) memset(roots , 0, (bch->n+1)*sizeof(*roots));
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1254) for (i = 0; i < t; i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1255) for (j = 0, r = 2*i+1; j < m; j++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1256) roots[r] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1257) r = mod_s(bch, 2*r);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1258) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1259) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1260) /* build generator polynomial g(X) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1261) g->deg = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1262) g->c[0] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1263) for (i = 0; i < GF_N(bch); i++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1264) if (roots[i]) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1265) /* multiply g(X) by (X+root) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1266) r = bch->a_pow_tab[i];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1267) g->c[g->deg+1] = 1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1268) for (j = g->deg; j > 0; j--)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1269) g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1270)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1271) g->c[0] = gf_mul(bch, g->c[0], r);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1272) g->deg++;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1273) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1274) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1275) /* store left-justified binary representation of g(X) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1276) n = g->deg+1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1277) i = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1278)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1279) while (n > 0) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1280) nbits = (n > 32) ? 32 : n;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1281) for (j = 0, word = 0; j < nbits; j++) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1282) if (g->c[n-1-j])
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1283) word |= 1u << (31-j);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1284) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1285) genpoly[i++] = word;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1286) n -= nbits;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1287) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1288) bch->ecc_bits = g->deg;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1289)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1290) finish:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1291) kfree(g);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1292) kfree(roots);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1293)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1294) return genpoly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1295) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1296)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1297) /**
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1298) * bch_init - initialize a BCH encoder/decoder
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1299) * @m: Galois field order, should be in the range 5-15
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1300) * @t: maximum error correction capability, in bits
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1301) * @prim_poly: user-provided primitive polynomial (or 0 to use default)
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1302) * @swap_bits: swap bits within data and syndrome bytes
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1303) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1304) * Returns:
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1305) * a newly allocated BCH control structure if successful, NULL otherwise
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1306) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1307) * This initialization can take some time, as lookup tables are built for fast
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1308) * encoding/decoding; make sure not to call this function from a time critical
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1309) * path. Usually, bch_init() should be called on module/driver init and
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1310) * bch_free() should be called to release memory on exit.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1311) *
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1312) * You may provide your own primitive polynomial of degree @m in argument
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1313) * @prim_poly, or let bch_init() use its default polynomial.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1314) *
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1315) * Once bch_init() has successfully returned a pointer to a newly allocated
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1316) * BCH control structure, ecc length in bytes is given by member @ecc_bytes of
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1317) * the structure.
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1318) */
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1319) struct bch_control *bch_init(int m, int t, unsigned int prim_poly,
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1320) bool swap_bits)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1321) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1322) int err = 0;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1323) unsigned int i, words;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1324) uint32_t *genpoly;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1325) struct bch_control *bch = NULL;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1326)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1327) const int min_m = 5;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1328)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1329) /* default primitive polynomials */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1330) static const unsigned int prim_poly_tab[] = {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1331) 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1332) 0x402b, 0x8003,
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1333) };
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1334)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1335) #if defined(CONFIG_BCH_CONST_PARAMS)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1336) if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1337) printk(KERN_ERR "bch encoder/decoder was configured to support "
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1338) "parameters m=%d, t=%d only!\n",
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1339) CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1340) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1341) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1342) #endif
02361bc778885 (Kees Cook 2018-05-31 11:45:25 -0700 1343) if ((m < min_m) || (m > BCH_MAX_M))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1344) /*
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1345) * values of m greater than 15 are not currently supported;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1346) * supporting m > 15 would require changing table base type
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1347) * (uint16_t) and a small patch in matrix transposition
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1348) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1349) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1350)
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1351) if (t > BCH_MAX_T)
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1352) /*
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1353) * we can support larger than 64 bits if necessary, at the
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1354) * cost of higher stack usage.
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1355) */
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1356) goto fail;
f0fe77f601c3d (Arnd Bergmann 2018-10-11 13:06:17 +0200 1357)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1358) /* sanity checks */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1359) if ((t < 1) || (m*t >= ((1 << m)-1)))
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1360) /* invalid t value */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1361) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1362)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1363) /* select a primitive polynomial for generating GF(2^m) */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1364) if (prim_poly == 0)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1365) prim_poly = prim_poly_tab[m-min_m];
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1366)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1367) bch = kzalloc(sizeof(*bch), GFP_KERNEL);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1368) if (bch == NULL)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1369) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1370)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1371) bch->m = m;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1372) bch->t = t;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1373) bch->n = (1 << m)-1;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1374) words = DIV_ROUND_UP(m*t, 32);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1375) bch->ecc_bytes = DIV_ROUND_UP(m*t, 8);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1376) bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1377) bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1378) bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1379) bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1380) bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1381) bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1382) bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1383) bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1384) bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err);
1759279ad138c (Miquel Raynal 2020-05-19 09:45:43 +0200 1385) bch->swap_bits = swap_bits;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1386)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1387) for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1388) bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1389)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1390) if (err)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1391) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1392)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1393) err = build_gf_tables(bch, prim_poly);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1394) if (err)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1395) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1396)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1397) /* use generator polynomial for computing encoding tables */
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1398) genpoly = compute_generator_polynomial(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1399) if (genpoly == NULL)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1400) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1401)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1402) build_mod8_tables(bch, genpoly);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1403) kfree(genpoly);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1404)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1405) err = build_deg2_base(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1406) if (err)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1407) goto fail;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1408)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1409) return bch;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1410)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1411) fail:
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1412) bch_free(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1413) return NULL;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1414) }
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1415) EXPORT_SYMBOL_GPL(bch_init);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1416)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1417) /**
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1418) * bch_free - free the BCH control structure
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1419) * @bch: BCH control structure to release
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1420) */
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1421) void bch_free(struct bch_control *bch)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1422) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1423) unsigned int i;
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1424)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1425) if (bch) {
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1426) kfree(bch->a_pow_tab);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1427) kfree(bch->a_log_tab);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1428) kfree(bch->mod8_tab);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1429) kfree(bch->ecc_buf);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1430) kfree(bch->ecc_buf2);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1431) kfree(bch->xi_tab);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1432) kfree(bch->syn);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1433) kfree(bch->cache);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1434) kfree(bch->elp);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1435)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1436) for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1437) kfree(bch->poly_2t[i]);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1438)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1439) kfree(bch);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1440) }
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1441) }
c8ae3f744ddca (Miquel Raynal 2020-05-19 09:45:42 +0200 1442) EXPORT_SYMBOL_GPL(bch_free);
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1443)
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1444) MODULE_LICENSE("GPL");
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1445) MODULE_AUTHOR("Ivan Djelic <ivan.djelic@parrot.com>");
437aa565e2656 (Ivan Djelic 2011-03-11 11:05:32 +0100 1446) MODULE_DESCRIPTION("Binary BCH encoder/decoder");
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags