1 | /* |
---|---|

2 | * Generic binary BCH encoding/decoding library |

3 | * |

4 | * This program is free software; you can redistribute it and/or modify it |

5 | * under the terms of the GNU General Public License version 2 as published by |

6 | * the Free Software Foundation. |

7 | * |

8 | * This program is distributed in the hope that it will be useful, but WITHOUT |

9 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |

10 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |

11 | * more details. |

12 | * |

13 | * You should have received a copy of the GNU General Public License along with |

14 | * this program; if not, write to the Free Software Foundation, Inc., 51 |

15 | * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |

16 | * |

17 | * Copyright © 2011 Parrot S.A. |

18 | * |

19 | * Author: Ivan Djelic <ivan.djelic@parrot.com> |

20 | * |

21 | * Description: |

22 | * |

23 | * This library provides runtime configurable encoding/decoding of binary |

24 | * Bose-Chaudhuri-Hocquenghem (BCH) codes. |

25 | * |

26 | * Call init_bch to get a pointer to a newly allocated bch_control structure for |

27 | * the given m (Galois field order), t (error correction capability) and |

28 | * (optional) primitive polynomial parameters. |

29 | * |

30 | * Call encode_bch to compute and store ecc parity bytes to a given buffer. |

31 | * Call decode_bch to detect and locate errors in received data. |

32 | * |

33 | * On systems supporting hw BCH features, intermediate results may be provided |

34 | * to decode_bch in order to skip certain steps. See decode_bch() documentation |

35 | * for details. |

36 | * |

37 | * Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of |

38 | * parameters m and t; thus allowing extra compiler optimizations and providing |

39 | * better (up to 2x) encoding performance. Using this option makes sense when |

40 | * (m,t) are fixed and known in advance, e.g. when using BCH error correction |

41 | * on a particular NAND flash device. |

42 | * |

43 | * Algorithmic details: |

44 | * |

45 | * Encoding is performed by processing 32 input bits in parallel, using 4 |

46 | * remainder lookup tables. |

47 | * |

48 | * The final stage of decoding involves the following internal steps: |

49 | * a. Syndrome computation |

50 | * b. Error locator polynomial computation using Berlekamp-Massey algorithm |

51 | * c. Error locator root finding (by far the most expensive step) |

52 | * |

53 | * In this implementation, step c is not performed using the usual Chien search. |

54 | * Instead, an alternative approach described in [1] is used. It consists in |

55 | * factoring the error locator polynomial using the Berlekamp Trace algorithm |

56 | * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial |

57 | * solving techniques [2] are used. The resulting algorithm, called BTZ, yields |

58 | * much better performance than Chien search for usual (m,t) values (typically |

59 | * m >= 13, t < 32, see [1]). |

60 | * |

61 | * [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields |

62 | * of characteristic 2, in: Western European Workshop on Research in Cryptology |

63 | * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear. |

64 | * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over |

65 | * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996. |

66 | */ |

67 | |

68 | #include <linux/kernel.h> |

69 | #include <linux/errno.h> |

70 | #include <linux/init.h> |

71 | #include <linux/module.h> |

72 | #include <linux/slab.h> |

73 | #include <linux/bitops.h> |

74 | #include <asm/byteorder.h> |

75 | #include <linux/bch.h> |

76 | |

77 | #if defined(CONFIG_BCH_CONST_PARAMS) |

78 | #define GF_M(_p) (CONFIG_BCH_CONST_M) |

79 | #define GF_T(_p) (CONFIG_BCH_CONST_T) |

80 | #define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1) |

81 | #define BCH_MAX_M (CONFIG_BCH_CONST_M) |

82 | #define BCH_MAX_T (CONFIG_BCH_CONST_T) |

83 | #else |

84 | #define GF_M(_p) ((_p)->m) |

85 | #define GF_T(_p) ((_p)->t) |

86 | #define GF_N(_p) ((_p)->n) |

87 | #define BCH_MAX_M 15 /* 2KB */ |

88 | #define BCH_MAX_T 64 /* 64 bit correction */ |

89 | #endif |

90 | |

91 | #define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32) |

92 | #define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8) |

93 | |

94 | #define BCH_ECC_MAX_WORDS DIV_ROUND_UP(BCH_MAX_M * BCH_MAX_T, 32) |

95 | |

96 | #ifndef dbg |

97 | #define dbg(_fmt, args...) do {} while (0) |

98 | #endif |

99 | |

100 | /* |

101 | * represent a polynomial over GF(2^m) |

102 | */ |

103 | struct gf_poly { |

104 | unsigned int deg; /* polynomial degree */ |

105 | unsigned int c[0]; /* polynomial terms */ |

106 | }; |

107 | |

108 | /* given its degree, compute a polynomial size in bytes */ |

109 | #define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int)) |

110 | |

111 | /* polynomial of degree 1 */ |

112 | struct gf_poly_deg1 { |

113 | struct gf_poly poly; |

114 | unsigned int c[2]; |

115 | }; |

116 | |

117 | /* |

118 | * same as encode_bch(), but process input data one byte at a time |

119 | */ |

120 | static void encode_bch_unaligned(struct bch_control *bch, |

121 | const unsigned char *data, unsigned int len, |

122 | uint32_t *ecc) |

123 | { |

124 | int i; |

125 | const uint32_t *p; |

126 | const int l = BCH_ECC_WORDS(bch)-1; |

127 | |

128 | while (len--) { |

129 | p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff); |

130 | |

131 | for (i = 0; i < l; i++) |

132 | ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); |

133 | |

134 | ecc[l] = (ecc[l] << 8)^(*p); |

135 | } |

136 | } |

137 | |

138 | /* |

139 | * convert ecc bytes to aligned, zero-padded 32-bit ecc words |

140 | */ |

141 | static void load_ecc8(struct bch_control *bch, uint32_t *dst, |

142 | const uint8_t *src) |

143 | { |

144 | uint8_t pad[4] = {0, 0, 0, 0}; |

145 | unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; |

146 | |

147 | for (i = 0; i < nwords; i++, src += 4) |

148 | dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3]; |

149 | |

150 | memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); |

151 | dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3]; |

152 | } |

153 | |

154 | /* |

155 | * convert 32-bit ecc words to ecc bytes |

156 | */ |

157 | static void store_ecc8(struct bch_control *bch, uint8_t *dst, |

158 | const uint32_t *src) |

159 | { |

160 | uint8_t pad[4]; |

161 | unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; |

162 | |

163 | for (i = 0; i < nwords; i++) { |

164 | *dst++ = (src[i] >> 24); |

165 | *dst++ = (src[i] >> 16) & 0xff; |

166 | *dst++ = (src[i] >> 8) & 0xff; |

167 | *dst++ = (src[i] >> 0) & 0xff; |

168 | } |

169 | pad[0] = (src[nwords] >> 24); |

170 | pad[1] = (src[nwords] >> 16) & 0xff; |

171 | pad[2] = (src[nwords] >> 8) & 0xff; |

172 | pad[3] = (src[nwords] >> 0) & 0xff; |

173 | memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); |

174 | } |

175 | |

176 | /** |

177 | * encode_bch - calculate BCH ecc parity of data |

178 | * @bch: BCH control structure |

179 | * @data: data to encode |

180 | * @len: data length in bytes |

181 | * @ecc: ecc parity data, must be initialized by caller |

182 | * |

183 | * The @ecc parity array is used both as input and output parameter, in order to |

184 | * allow incremental computations. It should be of the size indicated by member |

185 | * @ecc_bytes of @bch, and should be initialized to 0 before the first call. |

186 | * |

187 | * The exact number of computed ecc parity bits is given by member @ecc_bits of |

188 | * @bch; it may be less than m*t for large values of t. |

189 | */ |

190 | void encode_bch(struct bch_control *bch, const uint8_t *data, |

191 | unsigned int len, uint8_t *ecc) |

192 | { |

193 | const unsigned int l = BCH_ECC_WORDS(bch)-1; |

194 | unsigned int i, mlen; |

195 | unsigned long m; |

196 | uint32_t w, r[BCH_ECC_MAX_WORDS]; |

197 | const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r); |

198 | const uint32_t * const tab0 = bch->mod8_tab; |

199 | const uint32_t * const tab1 = tab0 + 256*(l+1); |

200 | const uint32_t * const tab2 = tab1 + 256*(l+1); |

201 | const uint32_t * const tab3 = tab2 + 256*(l+1); |

202 | const uint32_t *pdata, *p0, *p1, *p2, *p3; |

203 | |

204 | if (WARN_ON(r_bytes > sizeof(r))) |

205 | return; |

206 | |

207 | if (ecc) { |

208 | /* load ecc parity bytes into internal 32-bit buffer */ |

209 | load_ecc8(bch, bch->ecc_buf, ecc); |

210 | } else { |

211 | memset(bch->ecc_buf, 0, r_bytes); |

212 | } |

213 | |

214 | /* process first unaligned data bytes */ |

215 | m = ((unsigned long)data) & 3; |

216 | if (m) { |

217 | mlen = (len < (4-m)) ? len : 4-m; |

218 | encode_bch_unaligned(bch, data, mlen, bch->ecc_buf); |

219 | data += mlen; |

220 | len -= mlen; |

221 | } |

222 | |

223 | /* process 32-bit aligned data words */ |

224 | pdata = (uint32_t *)data; |

225 | mlen = len/4; |

226 | data += 4*mlen; |

227 | len -= 4*mlen; |

228 | memcpy(r, bch->ecc_buf, r_bytes); |

229 | |

230 | /* |

231 | * split each 32-bit word into 4 polynomials of weight 8 as follows: |

232 | * |

233 | * 31 ...24 23 ...16 15 ... 8 7 ... 0 |

234 | * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt |

235 | * tttttttt mod g = r0 (precomputed) |

236 | * zzzzzzzz 00000000 mod g = r1 (precomputed) |

237 | * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) |

238 | * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) |

239 | * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 |

240 | */ |

241 | while (mlen--) { |

242 | /* input data is read in big-endian format */ |

243 | w = r[0]^cpu_to_be32(*pdata++); |

244 | p0 = tab0 + (l+1)*((w >> 0) & 0xff); |

245 | p1 = tab1 + (l+1)*((w >> 8) & 0xff); |

246 | p2 = tab2 + (l+1)*((w >> 16) & 0xff); |

247 | p3 = tab3 + (l+1)*((w >> 24) & 0xff); |

248 | |

249 | for (i = 0; i < l; i++) |

250 | r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; |

251 | |

252 | r[l] = p0[l]^p1[l]^p2[l]^p3[l]; |

253 | } |

254 | memcpy(bch->ecc_buf, r, r_bytes); |

255 | |

256 | /* process last unaligned bytes */ |

257 | if (len) |

258 | encode_bch_unaligned(bch, data, len, bch->ecc_buf); |

259 | |

260 | /* store ecc parity bytes into original parity buffer */ |

261 | if (ecc) |

262 | store_ecc8(bch, ecc, bch->ecc_buf); |

263 | } |

264 | EXPORT_SYMBOL_GPL(encode_bch); |

265 | |

266 | static inline int modulo(struct bch_control *bch, unsigned int v) |

267 | { |

268 | const unsigned int n = GF_N(bch); |

269 | while (v >= n) { |

270 | v -= n; |

271 | v = (v & n) + (v >> GF_M(bch)); |

272 | } |

273 | return v; |

274 | } |

275 | |

276 | /* |

277 | * shorter and faster modulo function, only works when v < 2N. |

278 | */ |

279 | static inline int mod_s(struct bch_control *bch, unsigned int v) |

280 | { |

281 | const unsigned int n = GF_N(bch); |

282 | return (v < n) ? v : v-n; |

283 | } |

284 | |

285 | static inline int deg(unsigned int poly) |

286 | { |

287 | /* polynomial degree is the most-significant bit index */ |

288 | return fls(poly)-1; |

289 | } |

290 | |

291 | static inline int parity(unsigned int x) |

292 | { |

293 | /* |

294 | * public domain code snippet, lifted from |

295 | * http://www-graphics.stanford.edu/~seander/bithacks.html |

296 | */ |

297 | x ^= x >> 1; |

298 | x ^= x >> 2; |

299 | x = (x & 0x11111111U) * 0x11111111U; |

300 | return (x >> 28) & 1; |

301 | } |

302 | |

303 | /* Galois field basic operations: multiply, divide, inverse, etc. */ |

304 | |

305 | static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, |

306 | unsigned int b) |

307 | { |

308 | return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ |

309 | bch->a_log_tab[b])] : 0; |

310 | } |

311 | |

312 | static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) |

313 | { |

314 | return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; |

315 | } |

316 | |

317 | static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, |

318 | unsigned int b) |

319 | { |

320 | return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ |

321 | GF_N(bch)-bch->a_log_tab[b])] : 0; |

322 | } |

323 | |

324 | static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) |

325 | { |

326 | return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; |

327 | } |

328 | |

329 | static inline unsigned int a_pow(struct bch_control *bch, int i) |

330 | { |

331 | return bch->a_pow_tab[modulo(bch, i)]; |

332 | } |

333 | |

334 | static inline int a_log(struct bch_control *bch, unsigned int x) |

335 | { |

336 | return bch->a_log_tab[x]; |

337 | } |

338 | |

339 | static inline int a_ilog(struct bch_control *bch, unsigned int x) |

340 | { |

341 | return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); |

342 | } |

343 | |

344 | /* |

345 | * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t |

346 | */ |

347 | static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, |

348 | unsigned int *syn) |

349 | { |

350 | int i, j, s; |

351 | unsigned int m; |

352 | uint32_t poly; |

353 | const int t = GF_T(bch); |

354 | |

355 | s = bch->ecc_bits; |

356 | |

357 | /* make sure extra bits in last ecc word are cleared */ |

358 | m = ((unsigned int)s) & 31; |

359 | if (m) |

360 | ecc[s/32] &= ~((1u << (32-m))-1); |

361 | memset(syn, 0, 2*t*sizeof(*syn)); |

362 | |

363 | /* compute v(a^j) for j=1 .. 2t-1 */ |

364 | do { |

365 | poly = *ecc++; |

366 | s -= 32; |

367 | while (poly) { |

368 | i = deg(poly); |

369 | for (j = 0; j < 2*t; j += 2) |

370 | syn[j] ^= a_pow(bch, (j+1)*(i+s)); |

371 | |

372 | poly ^= (1 << i); |

373 | } |

374 | } while (s > 0); |

375 | |

376 | /* v(a^(2j)) = v(a^j)^2 */ |

377 | for (j = 0; j < t; j++) |

378 | syn[2*j+1] = gf_sqr(bch, syn[j]); |

379 | } |

380 | |

381 | static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) |

382 | { |

383 | memcpy(dst, src, GF_POLY_SZ(src->deg)); |

384 | } |

385 | |

386 | static int compute_error_locator_polynomial(struct bch_control *bch, |

387 | const unsigned int *syn) |

388 | { |

389 | const unsigned int t = GF_T(bch); |

390 | const unsigned int n = GF_N(bch); |

391 | unsigned int i, j, tmp, l, pd = 1, d = syn[0]; |

392 | struct gf_poly *elp = bch->elp; |

393 | struct gf_poly *pelp = bch->poly_2t[0]; |

394 | struct gf_poly *elp_copy = bch->poly_2t[1]; |

395 | int k, pp = -1; |

396 | |

397 | memset(pelp, 0, GF_POLY_SZ(2*t)); |

398 | memset(elp, 0, GF_POLY_SZ(2*t)); |

399 | |

400 | pelp->deg = 0; |

401 | pelp->c[0] = 1; |

402 | elp->deg = 0; |

403 | elp->c[0] = 1; |

404 | |

405 | /* use simplified binary Berlekamp-Massey algorithm */ |

406 | for (i = 0; (i < t) && (elp->deg <= t); i++) { |

407 | if (d) { |

408 | k = 2*i-pp; |

409 | gf_poly_copy(elp_copy, elp); |

410 | /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ |

411 | tmp = a_log(bch, d)+n-a_log(bch, pd); |

412 | for (j = 0; j <= pelp->deg; j++) { |

413 | if (pelp->c[j]) { |

414 | l = a_log(bch, pelp->c[j]); |

415 | elp->c[j+k] ^= a_pow(bch, tmp+l); |

416 | } |

417 | } |

418 | /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ |

419 | tmp = pelp->deg+k; |

420 | if (tmp > elp->deg) { |

421 | elp->deg = tmp; |

422 | gf_poly_copy(pelp, elp_copy); |

423 | pd = d; |

424 | pp = 2*i; |

425 | } |

426 | } |

427 | /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ |

428 | if (i < t-1) { |

429 | d = syn[2*i+2]; |

430 | for (j = 1; j <= elp->deg; j++) |

431 | d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); |

432 | } |

433 | } |

434 | dbg("elp=%s\n", gf_poly_str(elp)); |

435 | return (elp->deg > t) ? -1 : (int)elp->deg; |

436 | } |

437 | |

438 | /* |

439 | * solve a m x m linear system in GF(2) with an expected number of solutions, |

440 | * and return the number of found solutions |

441 | */ |

442 | static int solve_linear_system(struct bch_control *bch, unsigned int *rows, |

443 | unsigned int *sol, int nsol) |

444 | { |

445 | const int m = GF_M(bch); |

446 | unsigned int tmp, mask; |

447 | int rem, c, r, p, k, param[BCH_MAX_M]; |

448 | |

449 | k = 0; |

450 | mask = 1 << m; |

451 | |

452 | /* Gaussian elimination */ |

453 | for (c = 0; c < m; c++) { |

454 | rem = 0; |

455 | p = c-k; |

456 | /* find suitable row for elimination */ |

457 | for (r = p; r < m; r++) { |

458 | if (rows[r] & mask) { |

459 | if (r != p) { |

460 | tmp = rows[r]; |

461 | rows[r] = rows[p]; |

462 | rows[p] = tmp; |

463 | } |

464 | rem = r+1; |

465 | break; |

466 | } |

467 | } |

468 | if (rem) { |

469 | /* perform elimination on remaining rows */ |

470 | tmp = rows[p]; |

471 | for (r = rem; r < m; r++) { |

472 | if (rows[r] & mask) |

473 | rows[r] ^= tmp; |

474 | } |

475 | } else { |

476 | /* elimination not needed, store defective row index */ |

477 | param[k++] = c; |

478 | } |

479 | mask >>= 1; |

480 | } |

481 | /* rewrite system, inserting fake parameter rows */ |

482 | if (k > 0) { |

483 | p = k; |

484 | for (r = m-1; r >= 0; r--) { |

485 | if ((r > m-1-k) && rows[r]) |

486 | /* system has no solution */ |

487 | return 0; |

488 | |

489 | rows[r] = (p && (r == param[p-1])) ? |

490 | p--, 1u << (m-r) : rows[r-p]; |

491 | } |

492 | } |

493 | |

494 | if (nsol != (1 << k)) |

495 | /* unexpected number of solutions */ |

496 | return 0; |

497 | |

498 | for (p = 0; p < nsol; p++) { |

499 | /* set parameters for p-th solution */ |

500 | for (c = 0; c < k; c++) |

501 | rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1); |

502 | |

503 | /* compute unique solution */ |

504 | tmp = 0; |

505 | for (r = m-1; r >= 0; r--) { |

506 | mask = rows[r] & (tmp|1); |

507 | tmp |= parity(mask) << (m-r); |

508 | } |

509 | sol[p] = tmp >> 1; |

510 | } |

511 | return nsol; |

512 | } |

513 | |

514 | /* |

515 | * this function builds and solves a linear system for finding roots of a degree |

516 | * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m). |

517 | */ |

518 | static int find_affine4_roots(struct bch_control *bch, unsigned int a, |

519 | unsigned int b, unsigned int c, |

520 | unsigned int *roots) |

521 | { |

522 | int i, j, k; |

523 | const int m = GF_M(bch); |

524 | unsigned int mask = 0xff, t, rows[16] = {0,}; |

525 | |

526 | j = a_log(bch, b); |

527 | k = a_log(bch, a); |

528 | rows[0] = c; |

529 | |

530 | /* buid linear system to solve X^4+aX^2+bX+c = 0 */ |

531 | for (i = 0; i < m; i++) { |

532 | rows[i+1] = bch->a_pow_tab[4*i]^ |

533 | (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ |

534 | (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); |

535 | j++; |

536 | k += 2; |

537 | } |

538 | /* |

539 | * transpose 16x16 matrix before passing it to linear solver |

540 | * warning: this code assumes m < 16 |

541 | */ |

542 | for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) { |

543 | for (k = 0; k < 16; k = (k+j+1) & ~j) { |

544 | t = ((rows[k] >> j)^rows[k+j]) & mask; |

545 | rows[k] ^= (t << j); |

546 | rows[k+j] ^= t; |

547 | } |

548 | } |

549 | return solve_linear_system(bch, rows, roots, 4); |

550 | } |

551 | |

552 | /* |

553 | * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r)) |

554 | */ |

555 | static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, |

556 | unsigned int *roots) |

557 | { |

558 | int n = 0; |

559 | |

560 | if (poly->c[0]) |

561 | /* poly[X] = bX+c with c!=0, root=c/b */ |

562 | roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ |

563 | bch->a_log_tab[poly->c[1]]); |

564 | return n; |

565 | } |

566 | |

567 | /* |

568 | * compute roots of a degree 2 polynomial over GF(2^m) |

569 | */ |

570 | static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, |

571 | unsigned int *roots) |

572 | { |

573 | int n = 0, i, l0, l1, l2; |

574 | unsigned int u, v, r; |

575 | |

576 | if (poly->c[0] && poly->c[1]) { |

577 | |

578 | l0 = bch->a_log_tab[poly->c[0]]; |

579 | l1 = bch->a_log_tab[poly->c[1]]; |

580 | l2 = bch->a_log_tab[poly->c[2]]; |

581 | |

582 | /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */ |

583 | u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1)); |

584 | /* |

585 | * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): |

586 | * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) = |

587 | * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u) |

588 | * i.e. r and r+1 are roots iff Tr(u)=0 |

589 | */ |

590 | r = 0; |

591 | v = u; |

592 | while (v) { |

593 | i = deg(v); |

594 | r ^= bch->xi_tab[i]; |

595 | v ^= (1 << i); |

596 | } |

597 | /* verify root */ |

598 | if ((gf_sqr(bch, r)^r) == u) { |

599 | /* reverse z=a/bX transformation and compute log(1/r) */ |

600 | roots[n++] = modulo(bch, 2*GF_N(bch)-l1- |

601 | bch->a_log_tab[r]+l2); |

602 | roots[n++] = modulo(bch, 2*GF_N(bch)-l1- |

603 | bch->a_log_tab[r^1]+l2); |

604 | } |

605 | } |

606 | return n; |

607 | } |

608 | |

609 | /* |

610 | * compute roots of a degree 3 polynomial over GF(2^m) |

611 | */ |

612 | static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, |

613 | unsigned int *roots) |

614 | { |

615 | int i, n = 0; |

616 | unsigned int a, b, c, a2, b2, c2, e3, tmp[4]; |

617 | |

618 | if (poly->c[0]) { |

619 | /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */ |

620 | e3 = poly->c[3]; |

621 | c2 = gf_div(bch, poly->c[0], e3); |

622 | b2 = gf_div(bch, poly->c[1], e3); |

623 | a2 = gf_div(bch, poly->c[2], e3); |

624 | |

625 | /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */ |

626 | c = gf_mul(bch, a2, c2); /* c = a2c2 */ |

627 | b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */ |

628 | a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */ |

629 | |

630 | /* find the 4 roots of this affine polynomial */ |

631 | if (find_affine4_roots(bch, a, b, c, tmp) == 4) { |

632 | /* remove a2 from final list of roots */ |

633 | for (i = 0; i < 4; i++) { |

634 | if (tmp[i] != a2) |

635 | roots[n++] = a_ilog(bch, tmp[i]); |

636 | } |

637 | } |

638 | } |

639 | return n; |

640 | } |

641 | |

642 | /* |

643 | * compute roots of a degree 4 polynomial over GF(2^m) |

644 | */ |

645 | static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, |

646 | unsigned int *roots) |

647 | { |

648 | int i, l, n = 0; |

649 | unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4; |

650 | |

651 | if (poly->c[0] == 0) |

652 | return 0; |

653 | |

654 | /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */ |

655 | e4 = poly->c[4]; |

656 | d = gf_div(bch, poly->c[0], e4); |

657 | c = gf_div(bch, poly->c[1], e4); |

658 | b = gf_div(bch, poly->c[2], e4); |

659 | a = gf_div(bch, poly->c[3], e4); |

660 | |

661 | /* use Y=1/X transformation to get an affine polynomial */ |

662 | if (a) { |

663 | /* first, eliminate cX by using z=X+e with ae^2+c=0 */ |

664 | if (c) { |

665 | /* compute e such that e^2 = c/a */ |

666 | f = gf_div(bch, c, a); |

667 | l = a_log(bch, f); |

668 | l += (l & 1) ? GF_N(bch) : 0; |

669 | e = a_pow(bch, l/2); |

670 | /* |

671 | * use transformation z=X+e: |

672 | * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d |

673 | * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d |

674 | * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d |

675 | * z^4 + az^3 + b'z^2 + d' |

676 | */ |

677 | d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d; |

678 | b = gf_mul(bch, a, e)^b; |

679 | } |

680 | /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */ |

681 | if (d == 0) |

682 | /* assume all roots have multiplicity 1 */ |

683 | return 0; |

684 | |

685 | c2 = gf_inv(bch, d); |

686 | b2 = gf_div(bch, a, d); |

687 | a2 = gf_div(bch, b, d); |

688 | } else { |

689 | /* polynomial is already affine */ |

690 | c2 = d; |

691 | b2 = c; |

692 | a2 = b; |

693 | } |

694 | /* find the 4 roots of this affine polynomial */ |

695 | if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) { |

696 | for (i = 0; i < 4; i++) { |

697 | /* post-process roots (reverse transformations) */ |

698 | f = a ? gf_inv(bch, roots[i]) : roots[i]; |

699 | roots[i] = a_ilog(bch, f^e); |

700 | } |

701 | n = 4; |

702 | } |

703 | return n; |

704 | } |

705 | |

706 | /* |

707 | * build monic, log-based representation of a polynomial |

708 | */ |

709 | static void gf_poly_logrep(struct bch_control *bch, |

710 | const struct gf_poly *a, int *rep) |

711 | { |

712 | int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); |

713 | |

714 | /* represent 0 values with -1; warning, rep[d] is not set to 1 */ |

715 | for (i = 0; i < d; i++) |

716 | rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1; |

717 | } |

718 | |

719 | /* |

720 | * compute polynomial Euclidean division remainder in GF(2^m)[X] |

721 | */ |

722 | static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, |

723 | const struct gf_poly *b, int *rep) |

724 | { |

725 | int la, p, m; |

726 | unsigned int i, j, *c = a->c; |

727 | const unsigned int d = b->deg; |

728 | |

729 | if (a->deg < d) |

730 | return; |

731 | |

732 | /* reuse or compute log representation of denominator */ |

733 | if (!rep) { |

734 | rep = bch->cache; |

735 | gf_poly_logrep(bch, b, rep); |

736 | } |

737 | |

738 | for (j = a->deg; j >= d; j--) { |

739 | if (c[j]) { |

740 | la = a_log(bch, c[j]); |

741 | p = j-d; |

742 | for (i = 0; i < d; i++, p++) { |

743 | m = rep[i]; |

744 | if (m >= 0) |

745 | c[p] ^= bch->a_pow_tab[mod_s(bch, |

746 | m+la)]; |

747 | } |

748 | } |

749 | } |

750 | a->deg = d-1; |

751 | while (!c[a->deg] && a->deg) |

752 | a->deg--; |

753 | } |

754 | |

755 | /* |

756 | * compute polynomial Euclidean division quotient in GF(2^m)[X] |

757 | */ |

758 | static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, |

759 | const struct gf_poly *b, struct gf_poly *q) |

760 | { |

761 | if (a->deg >= b->deg) { |

762 | q->deg = a->deg-b->deg; |

763 | /* compute a mod b (modifies a) */ |

764 | gf_poly_mod(bch, a, b, NULL); |

765 | /* quotient is stored in upper part of polynomial a */ |

766 | memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); |

767 | } else { |

768 | q->deg = 0; |

769 | q->c[0] = 0; |

770 | } |

771 | } |

772 | |

773 | /* |

774 | * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X] |

775 | */ |

776 | static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, |

777 | struct gf_poly *b) |

778 | { |

779 | struct gf_poly *tmp; |

780 | |

781 | dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b)); |

782 | |

783 | if (a->deg < b->deg) { |

784 | tmp = b; |

785 | b = a; |

786 | a = tmp; |

787 | } |

788 | |

789 | while (b->deg > 0) { |

790 | gf_poly_mod(bch, a, b, NULL); |

791 | tmp = b; |

792 | b = a; |

793 | a = tmp; |

794 | } |

795 | |

796 | dbg("%s\n", gf_poly_str(a)); |

797 | |

798 | return a; |

799 | } |

800 | |

801 | /* |

802 | * Given a polynomial f and an integer k, compute Tr(a^kX) mod f |

803 | * This is used in Berlekamp Trace algorithm for splitting polynomials |

804 | */ |

805 | static void compute_trace_bk_mod(struct bch_control *bch, int k, |

806 | const struct gf_poly *f, struct gf_poly *z, |

807 | struct gf_poly *out) |

808 | { |

809 | const int m = GF_M(bch); |

810 | int i, j; |

811 | |

812 | /* z contains z^2j mod f */ |

813 | z->deg = 1; |

814 | z->c[0] = 0; |

815 | z->c[1] = bch->a_pow_tab[k]; |

816 | |

817 | out->deg = 0; |

818 | memset(out, 0, GF_POLY_SZ(f->deg)); |

819 | |

820 | /* compute f log representation only once */ |

821 | gf_poly_logrep(bch, f, bch->cache); |

822 | |

823 | for (i = 0; i < m; i++) { |

824 | /* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */ |

825 | for (j = z->deg; j >= 0; j--) { |

826 | out->c[j] ^= z->c[j]; |

827 | z->c[2*j] = gf_sqr(bch, z->c[j]); |

828 | z->c[2*j+1] = 0; |

829 | } |

830 | if (z->deg > out->deg) |

831 | out->deg = z->deg; |

832 | |

833 | if (i < m-1) { |

834 | z->deg *= 2; |

835 | /* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */ |

836 | gf_poly_mod(bch, z, f, bch->cache); |

837 | } |

838 | } |

839 | while (!out->c[out->deg] && out->deg) |

840 | out->deg--; |

841 | |

842 | dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out)); |

843 | } |

844 | |

845 | /* |

846 | * factor a polynomial using Berlekamp Trace algorithm (BTA) |

847 | */ |

848 | static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f, |

849 | struct gf_poly **g, struct gf_poly **h) |

850 | { |

851 | struct gf_poly *f2 = bch->poly_2t[0]; |

852 | struct gf_poly *q = bch->poly_2t[1]; |

853 | struct gf_poly *tk = bch->poly_2t[2]; |

854 | struct gf_poly *z = bch->poly_2t[3]; |

855 | struct gf_poly *gcd; |

856 | |

857 | dbg("factoring %s...\n", gf_poly_str(f)); |

858 | |

859 | *g = f; |

860 | *h = NULL; |

861 | |

862 | /* tk = Tr(a^k.X) mod f */ |

863 | compute_trace_bk_mod(bch, k, f, z, tk); |

864 | |

865 | if (tk->deg > 0) { |

866 | /* compute g = gcd(f, tk) (destructive operation) */ |

867 | gf_poly_copy(f2, f); |

868 | gcd = gf_poly_gcd(bch, f2, tk); |

869 | if (gcd->deg < f->deg) { |

870 | /* compute h=f/gcd(f,tk); this will modify f and q */ |

871 | gf_poly_div(bch, f, gcd, q); |

872 | /* store g and h in-place (clobbering f) */ |

873 | *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly; |

874 | gf_poly_copy(*g, gcd); |

875 | gf_poly_copy(*h, q); |

876 | } |

877 | } |

878 | } |

879 | |

880 | /* |

881 | * find roots of a polynomial, using BTZ algorithm; see the beginning of this |

882 | * file for details |

883 | */ |

884 | static int find_poly_roots(struct bch_control *bch, unsigned int k, |

885 | struct gf_poly *poly, unsigned int *roots) |

886 | { |

887 | int cnt; |

888 | struct gf_poly *f1, *f2; |

889 | |

890 | switch (poly->deg) { |

891 | /* handle low degree polynomials with ad hoc techniques */ |

892 | case 1: |

893 | cnt = find_poly_deg1_roots(bch, poly, roots); |

894 | break; |

895 | case 2: |

896 | cnt = find_poly_deg2_roots(bch, poly, roots); |

897 | break; |

898 | case 3: |

899 | cnt = find_poly_deg3_roots(bch, poly, roots); |

900 | break; |

901 | case 4: |

902 | cnt = find_poly_deg4_roots(bch, poly, roots); |

903 | break; |

904 | default: |

905 | /* factor polynomial using Berlekamp Trace Algorithm (BTA) */ |

906 | cnt = 0; |

907 | if (poly->deg && (k <= GF_M(bch))) { |

908 | factor_polynomial(bch, k, poly, &f1, &f2); |

909 | if (f1) |

910 | cnt += find_poly_roots(bch, k+1, f1, roots); |

911 | if (f2) |

912 | cnt += find_poly_roots(bch, k+1, f2, roots+cnt); |

913 | } |

914 | break; |

915 | } |

916 | return cnt; |

917 | } |

918 | |

919 | #if defined(USE_CHIEN_SEARCH) |

920 | /* |

921 | * exhaustive root search (Chien) implementation - not used, included only for |

922 | * reference/comparison tests |

923 | */ |

924 | static int chien_search(struct bch_control *bch, unsigned int len, |

925 | struct gf_poly *p, unsigned int *roots) |

926 | { |

927 | int m; |

928 | unsigned int i, j, syn, syn0, count = 0; |

929 | const unsigned int k = 8*len+bch->ecc_bits; |

930 | |

931 | /* use a log-based representation of polynomial */ |

932 | gf_poly_logrep(bch, p, bch->cache); |

933 | bch->cache[p->deg] = 0; |

934 | syn0 = gf_div(bch, p->c[0], p->c[p->deg]); |

935 | |

936 | for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) { |

937 | /* compute elp(a^i) */ |

938 | for (j = 1, syn = syn0; j <= p->deg; j++) { |

939 | m = bch->cache[j]; |

940 | if (m >= 0) |

941 | syn ^= a_pow(bch, m+j*i); |

942 | } |

943 | if (syn == 0) { |

944 | roots[count++] = GF_N(bch)-i; |

945 | if (count == p->deg) |

946 | break; |

947 | } |

948 | } |

949 | return (count == p->deg) ? count : 0; |

950 | } |

951 | #define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc) |

952 | #endif /* USE_CHIEN_SEARCH */ |

953 | |

954 | /** |

955 | * decode_bch - decode received codeword and find bit error locations |

956 | * @bch: BCH control structure |

957 | * @data: received data, ignored if @calc_ecc is provided |

958 | * @len: data length in bytes, must always be provided |

959 | * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc |

960 | * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data |

961 | * @syn: hw computed syndrome data (if NULL, syndrome is calculated) |

962 | * @errloc: output array of error locations |

963 | * |

964 | * Returns: |

965 | * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if |

966 | * invalid parameters were provided |

967 | * |

968 | * Depending on the available hw BCH support and the need to compute @calc_ecc |

969 | * separately (using encode_bch()), this function should be called with one of |

970 | * the following parameter configurations - |

971 | * |

972 | * by providing @data and @recv_ecc only: |

973 | * decode_bch(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc) |

974 | * |

975 | * by providing @recv_ecc and @calc_ecc: |

976 | * decode_bch(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc) |

977 | * |

978 | * by providing ecc = recv_ecc XOR calc_ecc: |

979 | * decode_bch(@bch, NULL, @len, NULL, ecc, NULL, @errloc) |

980 | * |

981 | * by providing syndrome results @syn: |

982 | * decode_bch(@bch, NULL, @len, NULL, NULL, @syn, @errloc) |

983 | * |

984 | * Once decode_bch() has successfully returned with a positive value, error |

985 | * locations returned in array @errloc should be interpreted as follows - |

986 | * |

987 | * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for |

988 | * data correction) |

989 | * |

990 | * if (errloc[n] < 8*len), then n-th error is located in data and can be |

991 | * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8); |

992 | * |

993 | * Note that this function does not perform any data correction by itself, it |

994 | * merely indicates error locations. |

995 | */ |

996 | int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len, |

997 | const uint8_t *recv_ecc, const uint8_t *calc_ecc, |

998 | const unsigned int *syn, unsigned int *errloc) |

999 | { |

1000 | const unsigned int ecc_words = BCH_ECC_WORDS(bch); |

1001 | unsigned int nbits; |

1002 | int i, err, nroots; |

1003 | uint32_t sum; |

1004 | |

1005 | /* sanity check: make sure data length can be handled */ |

1006 | if (8*len > (bch->n-bch->ecc_bits)) |

1007 | return -EINVAL; |

1008 | |

1009 | /* if caller does not provide syndromes, compute them */ |

1010 | if (!syn) { |

1011 | if (!calc_ecc) { |

1012 | /* compute received data ecc into an internal buffer */ |

1013 | if (!data || !recv_ecc) |

1014 | return -EINVAL; |

1015 | encode_bch(bch, data, len, NULL); |

1016 | } else { |

1017 | /* load provided calculated ecc */ |

1018 | load_ecc8(bch, bch->ecc_buf, calc_ecc); |

1019 | } |

1020 | /* load received ecc or assume it was XORed in calc_ecc */ |

1021 | if (recv_ecc) { |

1022 | load_ecc8(bch, bch->ecc_buf2, recv_ecc); |

1023 | /* XOR received and calculated ecc */ |

1024 | for (i = 0, sum = 0; i < (int)ecc_words; i++) { |

1025 | bch->ecc_buf[i] ^= bch->ecc_buf2[i]; |

1026 | sum |= bch->ecc_buf[i]; |

1027 | } |

1028 | if (!sum) |

1029 | /* no error found */ |

1030 | return 0; |

1031 | } |

1032 | compute_syndromes(bch, bch->ecc_buf, bch->syn); |

1033 | syn = bch->syn; |

1034 | } |

1035 | |

1036 | err = compute_error_locator_polynomial(bch, syn); |

1037 | if (err > 0) { |

1038 | nroots = find_poly_roots(bch, 1, bch->elp, errloc); |

1039 | if (err != nroots) |

1040 | err = -1; |

1041 | } |

1042 | if (err > 0) { |

1043 | /* post-process raw error locations for easier correction */ |

1044 | nbits = (len*8)+bch->ecc_bits; |

1045 | for (i = 0; i < err; i++) { |

1046 | if (errloc[i] >= nbits) { |

1047 | err = -1; |

1048 | break; |

1049 | } |

1050 | errloc[i] = nbits-1-errloc[i]; |

1051 | errloc[i] = (errloc[i] & ~7)|(7-(errloc[i] & 7)); |

1052 | } |

1053 | } |

1054 | return (err >= 0) ? err : -EBADMSG; |

1055 | } |

1056 | EXPORT_SYMBOL_GPL(decode_bch); |

1057 | |

1058 | /* |

1059 | * generate Galois field lookup tables |

1060 | */ |

1061 | static int build_gf_tables(struct bch_control *bch, unsigned int poly) |

1062 | { |

1063 | unsigned int i, x = 1; |

1064 | const unsigned int k = 1 << deg(poly); |

1065 | |

1066 | /* primitive polynomial must be of degree m */ |

1067 | if (k != (1u << GF_M(bch))) |

1068 | return -1; |

1069 | |

1070 | for (i = 0; i < GF_N(bch); i++) { |

1071 | bch->a_pow_tab[i] = x; |

1072 | bch->a_log_tab[x] = i; |

1073 | if (i && (x == 1)) |

1074 | /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */ |

1075 | return -1; |

1076 | x <<= 1; |

1077 | if (x & k) |

1078 | x ^= poly; |

1079 | } |

1080 | bch->a_pow_tab[GF_N(bch)] = 1; |

1081 | bch->a_log_tab[0] = 0; |

1082 | |

1083 | return 0; |

1084 | } |

1085 | |

1086 | /* |

1087 | * compute generator polynomial remainder tables for fast encoding |

1088 | */ |

1089 | static void build_mod8_tables(struct bch_control *bch, const uint32_t *g) |

1090 | { |

1091 | int i, j, b, d; |

1092 | uint32_t data, hi, lo, *tab; |

1093 | const int l = BCH_ECC_WORDS(bch); |

1094 | const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32); |

1095 | const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32); |

1096 | |

1097 | memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab)); |

1098 | |

1099 | for (i = 0; i < 256; i++) { |

1100 | /* p(X)=i is a small polynomial of weight <= 8 */ |

1101 | for (b = 0; b < 4; b++) { |

1102 | /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */ |

1103 | tab = bch->mod8_tab + (b*256+i)*l; |

1104 | data = i << (8*b); |

1105 | while (data) { |

1106 | d = deg(data); |

1107 | /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */ |

1108 | data ^= g[0] >> (31-d); |

1109 | for (j = 0; j < ecclen; j++) { |

1110 | hi = (d < 31) ? g[j] << (d+1) : 0; |

1111 | lo = (j+1 < plen) ? |

1112 | g[j+1] >> (31-d) : 0; |

1113 | tab[j] ^= hi|lo; |

1114 | } |

1115 | } |

1116 | } |

1117 | } |

1118 | } |

1119 | |

1120 | /* |

1121 | * build a base for factoring degree 2 polynomials |

1122 | */ |

1123 | static int build_deg2_base(struct bch_control *bch) |

1124 | { |

1125 | const int m = GF_M(bch); |

1126 | int i, j, r; |

1127 | unsigned int sum, x, y, remaining, ak = 0, xi[BCH_MAX_M]; |

1128 | |

1129 | /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */ |

1130 | for (i = 0; i < m; i++) { |

1131 | for (j = 0, sum = 0; j < m; j++) |

1132 | sum ^= a_pow(bch, i*(1 << j)); |

1133 | |

1134 | if (sum) { |

1135 | ak = bch->a_pow_tab[i]; |

1136 | break; |

1137 | } |

1138 | } |

1139 | /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */ |

1140 | remaining = m; |

1141 | memset(xi, 0, sizeof(xi)); |

1142 | |

1143 | for (x = 0; (x <= GF_N(bch)) && remaining; x++) { |

1144 | y = gf_sqr(bch, x)^x; |

1145 | for (i = 0; i < 2; i++) { |

1146 | r = a_log(bch, y); |

1147 | if (y && (r < m) && !xi[r]) { |

1148 | bch->xi_tab[r] = x; |

1149 | xi[r] = 1; |

1150 | remaining--; |

1151 | dbg("x%d = %x\n", r, x); |

1152 | break; |

1153 | } |

1154 | y ^= ak; |

1155 | } |

1156 | } |

1157 | /* should not happen but check anyway */ |

1158 | return remaining ? -1 : 0; |

1159 | } |

1160 | |

1161 | static void *bch_alloc(size_t size, int *err) |

1162 | { |

1163 | void *ptr; |

1164 | |

1165 | ptr = kmalloc(size, GFP_KERNEL); |

1166 | if (ptr == NULL) |

1167 | *err = 1; |

1168 | return ptr; |

1169 | } |

1170 | |

1171 | /* |

1172 | * compute generator polynomial for given (m,t) parameters. |

1173 | */ |

1174 | static uint32_t *compute_generator_polynomial(struct bch_control *bch) |

1175 | { |

1176 | const unsigned int m = GF_M(bch); |

1177 | const unsigned int t = GF_T(bch); |

1178 | int n, err = 0; |

1179 | unsigned int i, j, nbits, r, word, *roots; |

1180 | struct gf_poly *g; |

1181 | uint32_t *genpoly; |

1182 | |

1183 | g = bch_alloc(GF_POLY_SZ(m*t), &err); |

1184 | roots = bch_alloc((bch->n+1)*sizeof(*roots), &err); |

1185 | genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err); |

1186 | |

1187 | if (err) { |

1188 | kfree(genpoly); |

1189 | genpoly = NULL; |

1190 | goto finish; |

1191 | } |

1192 | |

1193 | /* enumerate all roots of g(X) */ |

1194 | memset(roots , 0, (bch->n+1)*sizeof(*roots)); |

1195 | for (i = 0; i < t; i++) { |

1196 | for (j = 0, r = 2*i+1; j < m; j++) { |

1197 | roots[r] = 1; |

1198 | r = mod_s(bch, 2*r); |

1199 | } |

1200 | } |

1201 | /* build generator polynomial g(X) */ |

1202 | g->deg = 0; |

1203 | g->c[0] = 1; |

1204 | for (i = 0; i < GF_N(bch); i++) { |

1205 | if (roots[i]) { |

1206 | /* multiply g(X) by (X+root) */ |

1207 | r = bch->a_pow_tab[i]; |

1208 | g->c[g->deg+1] = 1; |

1209 | for (j = g->deg; j > 0; j--) |

1210 | g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1]; |

1211 | |

1212 | g->c[0] = gf_mul(bch, g->c[0], r); |

1213 | g->deg++; |

1214 | } |

1215 | } |

1216 | /* store left-justified binary representation of g(X) */ |

1217 | n = g->deg+1; |

1218 | i = 0; |

1219 | |

1220 | while (n > 0) { |

1221 | nbits = (n > 32) ? 32 : n; |

1222 | for (j = 0, word = 0; j < nbits; j++) { |

1223 | if (g->c[n-1-j]) |

1224 | word |= 1u << (31-j); |

1225 | } |

1226 | genpoly[i++] = word; |

1227 | n -= nbits; |

1228 | } |

1229 | bch->ecc_bits = g->deg; |

1230 | |

1231 | finish: |

1232 | kfree(g); |

1233 | kfree(roots); |

1234 | |

1235 | return genpoly; |

1236 | } |

1237 | |

1238 | /** |

1239 | * init_bch - initialize a BCH encoder/decoder |

1240 | * @m: Galois field order, should be in the range 5-15 |

1241 | * @t: maximum error correction capability, in bits |

1242 | * @prim_poly: user-provided primitive polynomial (or 0 to use default) |

1243 | * |

1244 | * Returns: |

1245 | * a newly allocated BCH control structure if successful, NULL otherwise |

1246 | * |

1247 | * This initialization can take some time, as lookup tables are built for fast |

1248 | * encoding/decoding; make sure not to call this function from a time critical |

1249 | * path. Usually, init_bch() should be called on module/driver init and |

1250 | * free_bch() should be called to release memory on exit. |

1251 | * |

1252 | * You may provide your own primitive polynomial of degree @m in argument |

1253 | * @prim_poly, or let init_bch() use its default polynomial. |

1254 | * |

1255 | * Once init_bch() has successfully returned a pointer to a newly allocated |

1256 | * BCH control structure, ecc length in bytes is given by member @ecc_bytes of |

1257 | * the structure. |

1258 | */ |

1259 | struct bch_control *init_bch(int m, int t, unsigned int prim_poly) |

1260 | { |

1261 | int err = 0; |

1262 | unsigned int i, words; |

1263 | uint32_t *genpoly; |

1264 | struct bch_control *bch = NULL; |

1265 | |

1266 | const int min_m = 5; |

1267 | |

1268 | /* default primitive polynomials */ |

1269 | static const unsigned int prim_poly_tab[] = { |

1270 | 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b, |

1271 | 0x402b, 0x8003, |

1272 | }; |

1273 | |

1274 | #if defined(CONFIG_BCH_CONST_PARAMS) |

1275 | if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) { |

1276 | printk(KERN_ERR "bch encoder/decoder was configured to support " |

1277 | "parameters m=%d, t=%d only!\n", |

1278 | CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T); |

1279 | goto fail; |

1280 | } |

1281 | #endif |

1282 | if ((m < min_m) || (m > BCH_MAX_M)) |

1283 | /* |

1284 | * values of m greater than 15 are not currently supported; |

1285 | * supporting m > 15 would require changing table base type |

1286 | * (uint16_t) and a small patch in matrix transposition |

1287 | */ |

1288 | goto fail; |

1289 | |

1290 | if (t > BCH_MAX_T) |

1291 | /* |

1292 | * we can support larger than 64 bits if necessary, at the |

1293 | * cost of higher stack usage. |

1294 | */ |

1295 | goto fail; |

1296 | |

1297 | /* sanity checks */ |

1298 | if ((t < 1) || (m*t >= ((1 << m)-1))) |

1299 | /* invalid t value */ |

1300 | goto fail; |

1301 | |

1302 | /* select a primitive polynomial for generating GF(2^m) */ |

1303 | if (prim_poly == 0) |

1304 | prim_poly = prim_poly_tab[m-min_m]; |

1305 | |

1306 | bch = kzalloc(sizeof(*bch), GFP_KERNEL); |

1307 | if (bch == NULL) |

1308 | goto fail; |

1309 | |

1310 | bch->m = m; |

1311 | bch->t = t; |

1312 | bch->n = (1 << m)-1; |

1313 | words = DIV_ROUND_UP(m*t, 32); |

1314 | bch->ecc_bytes = DIV_ROUND_UP(m*t, 8); |

1315 | bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err); |

1316 | bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err); |

1317 | bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err); |

1318 | bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err); |

1319 | bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err); |

1320 | bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err); |

1321 | bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err); |

1322 | bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err); |

1323 | bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err); |

1324 | |

1325 | for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) |

1326 | bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err); |

1327 | |

1328 | if (err) |

1329 | goto fail; |

1330 | |

1331 | err = build_gf_tables(bch, prim_poly); |

1332 | if (err) |

1333 | goto fail; |

1334 | |

1335 | /* use generator polynomial for computing encoding tables */ |

1336 | genpoly = compute_generator_polynomial(bch); |

1337 | if (genpoly == NULL) |

1338 | goto fail; |

1339 | |

1340 | build_mod8_tables(bch, genpoly); |

1341 | kfree(genpoly); |

1342 | |

1343 | err = build_deg2_base(bch); |

1344 | if (err) |

1345 | goto fail; |

1346 | |

1347 | return bch; |

1348 | |

1349 | fail: |

1350 | free_bch(bch); |

1351 | return NULL; |

1352 | } |

1353 | EXPORT_SYMBOL_GPL(init_bch); |

1354 | |

1355 | /** |

1356 | * free_bch - free the BCH control structure |

1357 | * @bch: BCH control structure to release |

1358 | */ |

1359 | void free_bch(struct bch_control *bch) |

1360 | { |

1361 | unsigned int i; |

1362 | |

1363 | if (bch) { |

1364 | kfree(bch->a_pow_tab); |

1365 | kfree(bch->a_log_tab); |

1366 | kfree(bch->mod8_tab); |

1367 | kfree(bch->ecc_buf); |

1368 | kfree(bch->ecc_buf2); |

1369 | kfree(bch->xi_tab); |

1370 | kfree(bch->syn); |

1371 | kfree(bch->cache); |

1372 | kfree(bch->elp); |

1373 | |

1374 | for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) |

1375 | kfree(bch->poly_2t[i]); |

1376 | |

1377 | kfree(bch); |

1378 | } |

1379 | } |

1380 | EXPORT_SYMBOL_GPL(free_bch); |

1381 | |

1382 | MODULE_LICENSE("GPL"); |

1383 | MODULE_AUTHOR("Ivan Djelic <ivan.djelic@parrot.com>"); |

1384 | MODULE_DESCRIPTION("Binary BCH encoder/decoder"); |

1385 |