docecc.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526
  1. /*
  2. * ECC algorithm for M-systems disk on chip. We use the excellent Reed
  3. * Solmon code of Phil Karn (karn@ka9q.ampr.org) available under the
  4. * GNU GPL License. The rest is simply to convert the disk on chip
  5. * syndrom into a standard syndom.
  6. *
  7. * Author: Fabrice Bellard (fabrice.bellard@netgem.com)
  8. * Copyright (C) 2000 Netgem S.A.
  9. *
  10. * $Id: docecc.c,v 1.5 2003/05/21 15:15:06 dwmw2 Exp $
  11. *
  12. * This program is free software; you can redistribute it and/or modify
  13. * it under the terms of the GNU General Public License as published by
  14. * the Free Software Foundation; either version 2 of the License, or
  15. * (at your option) any later version.
  16. *
  17. * This program is distributed in the hope that it will be useful,
  18. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  20. * GNU General Public License for more details.
  21. *
  22. * You should have received a copy of the GNU General Public License
  23. * along with this program; if not, write to the Free Software
  24. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  25. */
  26. #include <linux/kernel.h>
  27. #include <linux/module.h>
  28. #include <asm/errno.h>
  29. #include <asm/io.h>
  30. #include <asm/uaccess.h>
  31. #include <linux/miscdevice.h>
  32. #include <linux/pci.h>
  33. #include <linux/delay.h>
  34. #include <linux/slab.h>
  35. #include <linux/sched.h>
  36. #include <linux/init.h>
  37. #include <linux/types.h>
  38. #include <linux/mtd/compatmac.h> /* for min() in older kernels */
  39. #include <linux/mtd/mtd.h>
  40. #include <linux/mtd/doc2000.h>
  41. /* need to undef it (from asm/termbits.h) */
  42. #undef B0
  43. #define MM 10 /* Symbol size in bits */
  44. #define KK (1023-4) /* Number of data symbols per block */
  45. #define B0 510 /* First root of generator polynomial, alpha form */
  46. #define PRIM 1 /* power of alpha used to generate roots of generator poly */
  47. #define NN ((1 << MM) - 1)
  48. typedef unsigned short dtype;
  49. /* 1+x^3+x^10 */
  50. static const int Pp[MM+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 };
  51. /* This defines the type used to store an element of the Galois Field
  52. * used by the code. Make sure this is something larger than a char if
  53. * if anything larger than GF(256) is used.
  54. *
  55. * Note: unsigned char will work up to GF(256) but int seems to run
  56. * faster on the Pentium.
  57. */
  58. typedef int gf;
  59. /* No legal value in index form represents zero, so
  60. * we need a special value for this purpose
  61. */
  62. #define A0 (NN)
  63. /* Compute x % NN, where NN is 2**MM - 1,
  64. * without a slow divide
  65. */
  66. static inline gf
  67. modnn(int x)
  68. {
  69. while (x >= NN) {
  70. x -= NN;
  71. x = (x >> MM) + (x & NN);
  72. }
  73. return x;
  74. }
  75. #define CLEAR(a,n) {\
  76. int ci;\
  77. for(ci=(n)-1;ci >=0;ci--)\
  78. (a)[ci] = 0;\
  79. }
  80. #define COPY(a,b,n) {\
  81. int ci;\
  82. for(ci=(n)-1;ci >=0;ci--)\
  83. (a)[ci] = (b)[ci];\
  84. }
  85. #define COPYDOWN(a,b,n) {\
  86. int ci;\
  87. for(ci=(n)-1;ci >=0;ci--)\
  88. (a)[ci] = (b)[ci];\
  89. }
  90. #define Ldec 1
  91. /* generate GF(2**m) from the irreducible polynomial p(X) in Pp[0]..Pp[m]
  92. lookup tables: index->polynomial form alpha_to[] contains j=alpha**i;
  93. polynomial form -> index form index_of[j=alpha**i] = i
  94. alpha=2 is the primitive element of GF(2**m)
  95. HARI's COMMENT: (4/13/94) alpha_to[] can be used as follows:
  96. Let @ represent the primitive element commonly called "alpha" that
  97. is the root of the primitive polynomial p(x). Then in GF(2^m), for any
  98. 0 <= i <= 2^m-2,
  99. @^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
  100. where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation
  101. of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for
  102. example the polynomial representation of @^5 would be given by the binary
  103. representation of the integer "alpha_to[5]".
  104. Similarily, index_of[] can be used as follows:
  105. As above, let @ represent the primitive element of GF(2^m) that is
  106. the root of the primitive polynomial p(x). In order to find the power
  107. of @ (alpha) that has the polynomial representation
  108. a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
  109. we consider the integer "i" whose binary representation with a(0) being LSB
  110. and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry
  111. "index_of[i]". Now, @^index_of[i] is that element whose polynomial
  112. representation is (a(0),a(1),a(2),...,a(m-1)).
  113. NOTE:
  114. The element alpha_to[2^m-1] = 0 always signifying that the
  115. representation of "@^infinity" = 0 is (0,0,0,...,0).
  116. Similarily, the element index_of[0] = A0 always signifying
  117. that the power of alpha which has the polynomial representation
  118. (0,0,...,0) is "infinity".
  119. */
  120. static void
  121. generate_gf(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1])
  122. {
  123. register int i, mask;
  124. mask = 1;
  125. Alpha_to[MM] = 0;
  126. for (i = 0; i < MM; i++) {
  127. Alpha_to[i] = mask;
  128. Index_of[Alpha_to[i]] = i;
  129. /* If Pp[i] == 1 then, term @^i occurs in poly-repr of @^MM */
  130. if (Pp[i] != 0)
  131. Alpha_to[MM] ^= mask; /* Bit-wise EXOR operation */
  132. mask <<= 1; /* single left-shift */
  133. }
  134. Index_of[Alpha_to[MM]] = MM;
  135. /*
  136. * Have obtained poly-repr of @^MM. Poly-repr of @^(i+1) is given by
  137. * poly-repr of @^i shifted left one-bit and accounting for any @^MM
  138. * term that may occur when poly-repr of @^i is shifted.
  139. */
  140. mask >>= 1;
  141. for (i = MM + 1; i < NN; i++) {
  142. if (Alpha_to[i - 1] >= mask)
  143. Alpha_to[i] = Alpha_to[MM] ^ ((Alpha_to[i - 1] ^ mask) << 1);
  144. else
  145. Alpha_to[i] = Alpha_to[i - 1] << 1;
  146. Index_of[Alpha_to[i]] = i;
  147. }
  148. Index_of[0] = A0;
  149. Alpha_to[NN] = 0;
  150. }
  151. /*
  152. * Performs ERRORS+ERASURES decoding of RS codes. bb[] is the content
  153. * of the feedback shift register after having processed the data and
  154. * the ECC.
  155. *
  156. * Return number of symbols corrected, or -1 if codeword is illegal
  157. * or uncorrectable. If eras_pos is non-null, the detected error locations
  158. * are written back. NOTE! This array must be at least NN-KK elements long.
  159. * The corrected data are written in eras_val[]. They must be xor with the data
  160. * to retrieve the correct data : data[erase_pos[i]] ^= erase_val[i] .
  161. *
  162. * First "no_eras" erasures are declared by the calling program. Then, the
  163. * maximum # of errors correctable is t_after_eras = floor((NN-KK-no_eras)/2).
  164. * If the number of channel errors is not greater than "t_after_eras" the
  165. * transmitted codeword will be recovered. Details of algorithm can be found
  166. * in R. Blahut's "Theory ... of Error-Correcting Codes".
  167. * Warning: the eras_pos[] array must not contain duplicate entries; decoder failure
  168. * will result. The decoder *could* check for this condition, but it would involve
  169. * extra time on every decoding operation.
  170. * */
  171. static int
  172. eras_dec_rs(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1],
  173. gf bb[NN - KK + 1], gf eras_val[NN-KK], int eras_pos[NN-KK],
  174. int no_eras)
  175. {
  176. int deg_lambda, el, deg_omega;
  177. int i, j, r,k;
  178. gf u,q,tmp,num1,num2,den,discr_r;
  179. gf lambda[NN-KK + 1], s[NN-KK + 1]; /* Err+Eras Locator poly
  180. * and syndrome poly */
  181. gf b[NN-KK + 1], t[NN-KK + 1], omega[NN-KK + 1];
  182. gf root[NN-KK], reg[NN-KK + 1], loc[NN-KK];
  183. int syn_error, count;
  184. syn_error = 0;
  185. for(i=0;i<NN-KK;i++)
  186. syn_error |= bb[i];
  187. if (!syn_error) {
  188. /* if remainder is zero, data[] is a codeword and there are no
  189. * errors to correct. So return data[] unmodified
  190. */
  191. count = 0;
  192. goto finish;
  193. }
  194. for(i=1;i<=NN-KK;i++){
  195. s[i] = bb[0];
  196. }
  197. for(j=1;j<NN-KK;j++){
  198. if(bb[j] == 0)
  199. continue;
  200. tmp = Index_of[bb[j]];
  201. for(i=1;i<=NN-KK;i++)
  202. s[i] ^= Alpha_to[modnn(tmp + (B0+i-1)*PRIM*j)];
  203. }
  204. /* undo the feedback register implicit multiplication and convert
  205. syndromes to index form */
  206. for(i=1;i<=NN-KK;i++) {
  207. tmp = Index_of[s[i]];
  208. if (tmp != A0)
  209. tmp = modnn(tmp + 2 * KK * (B0+i-1)*PRIM);
  210. s[i] = tmp;
  211. }
  212. CLEAR(&lambda[1],NN-KK);
  213. lambda[0] = 1;
  214. if (no_eras > 0) {
  215. /* Init lambda to be the erasure locator polynomial */
  216. lambda[1] = Alpha_to[modnn(PRIM * eras_pos[0])];
  217. for (i = 1; i < no_eras; i++) {
  218. u = modnn(PRIM*eras_pos[i]);
  219. for (j = i+1; j > 0; j--) {
  220. tmp = Index_of[lambda[j - 1]];
  221. if(tmp != A0)
  222. lambda[j] ^= Alpha_to[modnn(u + tmp)];
  223. }
  224. }
  225. #if DEBUG >= 1
  226. /* Test code that verifies the erasure locator polynomial just constructed
  227. Needed only for decoder debugging. */
  228. /* find roots of the erasure location polynomial */
  229. for(i=1;i<=no_eras;i++)
  230. reg[i] = Index_of[lambda[i]];
  231. count = 0;
  232. for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) {
  233. q = 1;
  234. for (j = 1; j <= no_eras; j++)
  235. if (reg[j] != A0) {
  236. reg[j] = modnn(reg[j] + j);
  237. q ^= Alpha_to[reg[j]];
  238. }
  239. if (q != 0)
  240. continue;
  241. /* store root and error location number indices */
  242. root[count] = i;
  243. loc[count] = k;
  244. count++;
  245. }
  246. if (count != no_eras) {
  247. printf("\n lambda(x) is WRONG\n");
  248. count = -1;
  249. goto finish;
  250. }
  251. #if DEBUG >= 2
  252. printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n");
  253. for (i = 0; i < count; i++)
  254. printf("%d ", loc[i]);
  255. printf("\n");
  256. #endif
  257. #endif
  258. }
  259. for(i=0;i<NN-KK+1;i++)
  260. b[i] = Index_of[lambda[i]];
  261. /*
  262. * Begin Berlekamp-Massey algorithm to determine error+erasure
  263. * locator polynomial
  264. */
  265. r = no_eras;
  266. el = no_eras;
  267. while (++r <= NN-KK) { /* r is the step number */
  268. /* Compute discrepancy at the r-th step in poly-form */
  269. discr_r = 0;
  270. for (i = 0; i < r; i++){
  271. if ((lambda[i] != 0) && (s[r - i] != A0)) {
  272. discr_r ^= Alpha_to[modnn(Index_of[lambda[i]] + s[r - i])];
  273. }
  274. }
  275. discr_r = Index_of[discr_r]; /* Index form */
  276. if (discr_r == A0) {
  277. /* 2 lines below: B(x) <-- x*B(x) */
  278. COPYDOWN(&b[1],b,NN-KK);
  279. b[0] = A0;
  280. } else {
  281. /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
  282. t[0] = lambda[0];
  283. for (i = 0 ; i < NN-KK; i++) {
  284. if(b[i] != A0)
  285. t[i+1] = lambda[i+1] ^ Alpha_to[modnn(discr_r + b[i])];
  286. else
  287. t[i+1] = lambda[i+1];
  288. }
  289. if (2 * el <= r + no_eras - 1) {
  290. el = r + no_eras - el;
  291. /*
  292. * 2 lines below: B(x) <-- inv(discr_r) *
  293. * lambda(x)
  294. */
  295. for (i = 0; i <= NN-KK; i++)
  296. b[i] = (lambda[i] == 0) ? A0 : modnn(Index_of[lambda[i]] - discr_r + NN);
  297. } else {
  298. /* 2 lines below: B(x) <-- x*B(x) */
  299. COPYDOWN(&b[1],b,NN-KK);
  300. b[0] = A0;
  301. }
  302. COPY(lambda,t,NN-KK+1);
  303. }
  304. }
  305. /* Convert lambda to index form and compute deg(lambda(x)) */
  306. deg_lambda = 0;
  307. for(i=0;i<NN-KK+1;i++){
  308. lambda[i] = Index_of[lambda[i]];
  309. if(lambda[i] != A0)
  310. deg_lambda = i;
  311. }
  312. /*
  313. * Find roots of the error+erasure locator polynomial by Chien
  314. * Search
  315. */
  316. COPY(&reg[1],&lambda[1],NN-KK);
  317. count = 0; /* Number of roots of lambda(x) */
  318. for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) {
  319. q = 1;
  320. for (j = deg_lambda; j > 0; j--){
  321. if (reg[j] != A0) {
  322. reg[j] = modnn(reg[j] + j);
  323. q ^= Alpha_to[reg[j]];
  324. }
  325. }
  326. if (q != 0)
  327. continue;
  328. /* store root (index-form) and error location number */
  329. root[count] = i;
  330. loc[count] = k;
  331. /* If we've already found max possible roots,
  332. * abort the search to save time
  333. */
  334. if(++count == deg_lambda)
  335. break;
  336. }
  337. if (deg_lambda != count) {
  338. /*
  339. * deg(lambda) unequal to number of roots => uncorrectable
  340. * error detected
  341. */
  342. count = -1;
  343. goto finish;
  344. }
  345. /*
  346. * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
  347. * x**(NN-KK)). in index form. Also find deg(omega).
  348. */
  349. deg_omega = 0;
  350. for (i = 0; i < NN-KK;i++){
  351. tmp = 0;
  352. j = (deg_lambda < i) ? deg_lambda : i;
  353. for(;j >= 0; j--){
  354. if ((s[i + 1 - j] != A0) && (lambda[j] != A0))
  355. tmp ^= Alpha_to[modnn(s[i + 1 - j] + lambda[j])];
  356. }
  357. if(tmp != 0)
  358. deg_omega = i;
  359. omega[i] = Index_of[tmp];
  360. }
  361. omega[NN-KK] = A0;
  362. /*
  363. * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
  364. * inv(X(l))**(B0-1) and den = lambda_pr(inv(X(l))) all in poly-form
  365. */
  366. for (j = count-1; j >=0; j--) {
  367. num1 = 0;
  368. for (i = deg_omega; i >= 0; i--) {
  369. if (omega[i] != A0)
  370. num1 ^= Alpha_to[modnn(omega[i] + i * root[j])];
  371. }
  372. num2 = Alpha_to[modnn(root[j] * (B0 - 1) + NN)];
  373. den = 0;
  374. /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
  375. for (i = min(deg_lambda,NN-KK-1) & ~1; i >= 0; i -=2) {
  376. if(lambda[i+1] != A0)
  377. den ^= Alpha_to[modnn(lambda[i+1] + i * root[j])];
  378. }
  379. if (den == 0) {
  380. #if DEBUG >= 1
  381. printf("\n ERROR: denominator = 0\n");
  382. #endif
  383. /* Convert to dual- basis */
  384. count = -1;
  385. goto finish;
  386. }
  387. /* Apply error to data */
  388. if (num1 != 0) {
  389. eras_val[j] = Alpha_to[modnn(Index_of[num1] + Index_of[num2] + NN - Index_of[den])];
  390. } else {
  391. eras_val[j] = 0;
  392. }
  393. }
  394. finish:
  395. for(i=0;i<count;i++)
  396. eras_pos[i] = loc[i];
  397. return count;
  398. }
  399. /***************************************************************************/
  400. /* The DOC specific code begins here */
  401. #define SECTOR_SIZE 512
  402. /* The sector bytes are packed into NB_DATA MM bits words */
  403. #define NB_DATA (((SECTOR_SIZE + 1) * 8 + 6) / MM)
  404. /*
  405. * Correct the errors in 'sector[]' by using 'ecc1[]' which is the
  406. * content of the feedback shift register applyied to the sector and
  407. * the ECC. Return the number of errors corrected (and correct them in
  408. * sector), or -1 if error
  409. */
  410. int doc_decode_ecc(unsigned char sector[SECTOR_SIZE], unsigned char ecc1[6])
  411. {
  412. int parity, i, nb_errors;
  413. gf bb[NN - KK + 1];
  414. gf error_val[NN-KK];
  415. int error_pos[NN-KK], pos, bitpos, index, val;
  416. dtype *Alpha_to, *Index_of;
  417. /* init log and exp tables here to save memory. However, it is slower */
  418. Alpha_to = kmalloc((NN + 1) * sizeof(dtype), GFP_KERNEL);
  419. if (!Alpha_to)
  420. return -1;
  421. Index_of = kmalloc((NN + 1) * sizeof(dtype), GFP_KERNEL);
  422. if (!Index_of) {
  423. kfree(Alpha_to);
  424. return -1;
  425. }
  426. generate_gf(Alpha_to, Index_of);
  427. parity = ecc1[1];
  428. bb[0] = (ecc1[4] & 0xff) | ((ecc1[5] & 0x03) << 8);
  429. bb[1] = ((ecc1[5] & 0xfc) >> 2) | ((ecc1[2] & 0x0f) << 6);
  430. bb[2] = ((ecc1[2] & 0xf0) >> 4) | ((ecc1[3] & 0x3f) << 4);
  431. bb[3] = ((ecc1[3] & 0xc0) >> 6) | ((ecc1[0] & 0xff) << 2);
  432. nb_errors = eras_dec_rs(Alpha_to, Index_of, bb,
  433. error_val, error_pos, 0);
  434. if (nb_errors <= 0)
  435. goto the_end;
  436. /* correct the errors */
  437. for(i=0;i<nb_errors;i++) {
  438. pos = error_pos[i];
  439. if (pos >= NB_DATA && pos < KK) {
  440. nb_errors = -1;
  441. goto the_end;
  442. }
  443. if (pos < NB_DATA) {
  444. /* extract bit position (MSB first) */
  445. pos = 10 * (NB_DATA - 1 - pos) - 6;
  446. /* now correct the following 10 bits. At most two bytes
  447. can be modified since pos is even */
  448. index = (pos >> 3) ^ 1;
  449. bitpos = pos & 7;
  450. if ((index >= 0 && index < SECTOR_SIZE) ||
  451. index == (SECTOR_SIZE + 1)) {
  452. val = error_val[i] >> (2 + bitpos);
  453. parity ^= val;
  454. if (index < SECTOR_SIZE)
  455. sector[index] ^= val;
  456. }
  457. index = ((pos >> 3) + 1) ^ 1;
  458. bitpos = (bitpos + 10) & 7;
  459. if (bitpos == 0)
  460. bitpos = 8;
  461. if ((index >= 0 && index < SECTOR_SIZE) ||
  462. index == (SECTOR_SIZE + 1)) {
  463. val = error_val[i] << (8 - bitpos);
  464. parity ^= val;
  465. if (index < SECTOR_SIZE)
  466. sector[index] ^= val;
  467. }
  468. }
  469. }
  470. /* use parity to test extra errors */
  471. if ((parity & 0xff) != 0)
  472. nb_errors = -1;
  473. the_end:
  474. kfree(Alpha_to);
  475. kfree(Index_of);
  476. return nb_errors;
  477. }
  478. EXPORT_SYMBOL_GPL(doc_decode_ecc);
  479. MODULE_LICENSE("GPL");
  480. MODULE_AUTHOR("Fabrice Bellard <fabrice.bellard@netgem.com>");
  481. MODULE_DESCRIPTION("ECC code for correcting errors detected by DiskOnChip 2000 and Millennium ECC hardware");