add missing macros and declarations
[mw/micromonitor-lm32.git] / umon_main / target / common / ecc.c
1 /* ecc.c:
2  * This code is an implementation of the discussion and pseudo-code
3  * of Application Note 1823 from STMicroelectronics titled:
4  *
5  * "Error correction code in single level cell NAND Flash memories"
6  *
7  * dated July 2007.
8  *
9  * Note:
10  * I found with the original code that I was not able to successfully
11  * detect/correct single bit errors in the 512-byte packets if the error
12  * was in upper 256 bytes of the packet.  After some investigation I made
13  * two changes to the code (see tags CHANGE_1 and CHANGE_2 below).
14  * Referring to the line tagged CHANGE_1, this was "if (i & 0xa0)" in
15  * the pseudo code.  Referring to the line tagged CHANGE_2, this is an
16  * addition to pull in the next bit of the byte address out of the third
17  * byte of the ECC code.  
18  *
19  * I've tested this pretty heavily using the STANDALONE build for this 
20  * and it has passed completely for 256 and 512 byte packets.  Obviously,
21  * without these changes, it did not pass.
22  *
23  *      General notice:
24  *      This code is part of a boot-monitor package developed as a generic base
25  *      platform for embedded system designs.  As such, it is likely to be
26  *      distributed to various projects beyond the control of the original
27  *      author.  Please notify the author of any enhancements made or bugs found
28  *      so that all may benefit from the changes.  In addition, notification back
29  *      to the author will allow the new user to pick up changes that may have
30  *      been made by other users after this version of the code was distributed.
31  *
32  *      Note1: the majority of this code was edited with 4-space tabs.
33  *      Note2: as more and more contributions are accepted, the term "author"
34  *                 is becoming a mis-representation of credit.
35  *
36  *      Original author:        Ed Sutter
37  *      Email:                          esutter@lucent.com
38  *      Phone:                          908-582-2351
39  */
40 #ifdef STANDALONE
41 #include <stdio.h>
42 #include <string.h>
43 #include <fcntl.h>
44 #include <sys/stat.h>
45 #include "genlib.h"
46 #endif
47
48 typedef unsigned char uchar;
49
50 int bit_addr, byte_addr;
51
52 /* ecc_gen():
53  * Calculate a  3-byte ECC based on either 256 or 512 bytes of incoming
54  * data.  Return void because this will never return an error.
55  */
56 void
57 ecc_gen(int dsize, uchar *data, uchar *ecc_code)
58 {
59         int i;
60
61         char cp0, cp1, cp2, cp3, cp4, cp5;
62         char b7, b6, b5, b4, b3, b2, b1, b0;
63         char lp0, lp1, lp2, lp3, lp4, lp5, lp6, lp7, lp8, lp9;
64         char lp10, lp11, lp12, lp13, lp14, lp15, lp16, lp17;
65
66         cp0 = cp1 = cp2 = cp3 = cp4 = cp5 = 0;
67         lp0 = lp1 = lp2 = lp3 = lp4 = lp5 = lp6 = lp7 = lp8 = lp9 = 0;
68         lp10 = lp11 = lp12 = lp13 = lp14 = lp15 = lp16 = lp17 = 0;
69
70         for(i=0;i<dsize;i++) {
71                 b0 = (*data & 0x01);
72                 b1 = ((*data & 0x02) >> 1);
73                 b2 = ((*data & 0x04) >> 2);
74                 b3 = ((*data & 0x08) >> 3);
75                 b4 = ((*data & 0x10) >> 4);
76                 b5 = ((*data & 0x20) >> 5);
77                 b6 = ((*data & 0x40) >> 6);
78                 b7 = ((*data & 0x80) >> 7);
79                 data++;
80
81                 if (i & 0x01) 
82                         lp1 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp1;
83                 else
84                         lp0 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp0;
85                 
86                 if (i & 0x02) 
87                         lp3 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp3;
88                 else 
89                         lp2 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp2;
90                 
91                 if (i & 0x04) 
92                         lp5 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp5;
93                 else
94                         lp4 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp4;
95                 
96                 if (i & 0x08)
97                         lp7 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp7;
98                 else
99                         lp6 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp6;
100                 
101                 if (i & 0x10)
102                         lp9 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp9;
103                 else
104                         lp8 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp8;
105                 
106                 if (i & 0x20)
107                         lp11 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp11;
108                 else
109                         lp10 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp10;
110                 
111                 if (i & 0x40)
112                         lp13 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp13;
113                 else
114                         lp12 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp12;
115                 
116                 if (i & 0x80)
117                         lp15 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp15;
118                 else
119                         lp14 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp14;
120                 
121                 if (dsize == 512) {
122                         if (i & 0x100)  /* CHANGE_1 (note at top of file) */
123                                 lp17 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp17;
124                         else
125                                 lp16 = b7 ^ b6 ^ b5 ^ b4 ^ b3 ^ b2 ^ b1 ^ b0 ^ lp16;
126                 }
127                 
128                 cp0 = b6 ^ b4 ^ b2 ^ b0 ^ cp0;
129                 cp1 = b7 ^ b5 ^ b3 ^ b1 ^ cp1;
130                 cp2 = b5 ^ b4 ^ b1 ^ b0 ^ cp2;
131                 cp3 = b7 ^ b6 ^ b3 ^ b2 ^ cp3;
132                 cp4 = b3 ^ b2 ^ b1 ^ b0 ^ cp4;
133                 cp5 = b7 ^ b6 ^ b5 ^ b4 ^ cp5;
134         }
135
136         ecc_code[0] = ((lp7 << 7) | (lp6 << 6) | (lp5 << 5) | (lp4 << 4) |
137                                         (lp3 << 3) | (lp2 << 2) | (lp1 << 1) | lp0);
138         ecc_code[1] = ((lp15 << 7) | (lp14 << 6) | (lp13 << 5) | (lp12 << 4) |
139                                         (lp11 << 3) | (lp10 << 2) | (lp9 << 1) | lp8);
140         ecc_code[2] = ((cp5 << 7) | (cp4 << 6) | (cp3 << 5) | (cp2 << 4) |
141                                         (cp1 << 3) | (cp0 << 2) | (lp17 << 1) | lp16);
142 }
143
144 /* ecc_check():
145  * Detect and correct a 1-bit error; where:
146  *    'stored_ecc' is the ECC stored in the NAND flash memory
147  *    'new_ecc'    is the ECC code generated on the data page read
148  *
149  * Return:
150  *       0 if no error
151  *       1 if exactly 1 error (the error is corrected in the data)
152  *  -2 if the error is in the ECC itself
153  *  -1 if the error is not correctable
154  */
155 int
156 ecc_check(int dsize, uchar *data, uchar *stored_ecc, uchar *new_ecc)
157 {
158         uchar mask;
159         int i, j, btot;
160         ushort ecc_xor[3];
161
162         ecc_xor[0] = stored_ecc[0] ^ new_ecc[0];
163         ecc_xor[1] = stored_ecc[1] ^ new_ecc[1];
164         ecc_xor[2] = stored_ecc[2] ^ new_ecc[2];
165
166         if ((ecc_xor[0] == 0) && (ecc_xor[1] == 0) && (ecc_xor[2] == 0))
167                 return(0);      /* No errors */
168
169         btot = 0;
170         for(i=0;i<3;i++) {
171                 mask = 0x80;
172
173                 for(j=0;j<8;j++) {
174                         if (ecc_xor[i] & mask)
175                                 btot++;
176                         mask >>= 1;
177                 }
178         }
179
180 //      printf("ecc_xor: %02x %02x %02x; btot=%d\n",
181 //              ecc_xor[0],ecc_xor[1],ecc_xor[2],btot);
182
183         if (((dsize == 256) && (btot == 11)) ||
184                 ((dsize == 512) && (btot == 12))) {
185
186                 bit_addr = (((ecc_xor[2] >> 3) & 0x01) |
187                                         ((ecc_xor[2] >> 4) & 0x02) |
188                                         ((ecc_xor[2] >> 5) & 0x04));
189
190                 byte_addr =
191                                 (((ecc_xor[0] >> 1) & 0x01) |
192                                  ((ecc_xor[0] >> 2) & 0x02) |
193                                  ((ecc_xor[0] >> 3) & 0x04) |
194                                  ((ecc_xor[0] >> 4) & 0x08) |
195                                  ((ecc_xor[1] << 3) & 0x10) |
196                                  ((ecc_xor[1] << 2) & 0x20) |
197                                  ((ecc_xor[1] << 1) & 0x40) |
198                                   (ecc_xor[1] & 0x80));
199
200                 if (dsize == 512)       /* CHANGE_2 (see note at top of file) */
201                         byte_addr |= ((ecc_xor[2] << 7) & 0x100);
202
203 //              printf("Error: bit %d of byte %d\n",bit_addr, byte_addr);
204                 data[byte_addr] = data[byte_addr] ^ (1 << bit_addr);
205                 return(1);
206         }
207         else if (btot == 1) {
208                 stored_ecc[0] = new_ecc[0];
209                 return(-2);     /* Error in ECC */
210         }
211         else {
212                 return(-1);     /* Uncorrectable error in data */
213         }
214 }
215
216 #ifdef STANDALONE
217 /* main():
218  * This main() code simply demonstrates the use of the two above functions.
219  * In a real system, the data and calculated ecc would have been written
220  * to NAND.  At some time later, the data and ecc would be read back out
221  * and verified by passing the data, the written ecc and the new ecc to
222  * ecc_check()...
223  * To simulate this, we pass the content of a file to ecc_gen() to generate
224  * the inititial ecc (as would have been stored in NAND with the data).  Then
225  * we toggle one bit in the buffer and send it to ecc_gen() a second time
226  * (as would have been done if the data was read back out of NAND some time
227  * later).  After reading the data and calculating the second ecc, the
228  * ecc_check() function is called with the data, the original ecc and the
229  * new ecc.  It determines if there was an error, and if possible, makes
230  * the correction.
231  */
232 int
233 main(int argc, char *argv[])
234 {
235         struct stat     fstat;
236         char            *fname;
237         uchar           buf[512], cpy[512], ecc1[3], ecc2[3];
238         int                     fd, size, rc, bytenum, bitnum;
239
240         if (argc != 3) {
241                 fprintf(stderr,"Usage: %s {filename} {256|512}\n",argv[0]);
242                 exit(1);
243         }
244         fname = argv[1];
245         size = atoi(argv[2]);
246
247         if ((size != 256) && (size != 512)) {
248                 fprintf(stderr,"Error: size must be 256 or 512\n");
249                 exit(1);
250         }
251
252         if ((fd = open(fname,O_RDONLY | O_BINARY)) == -1) {
253                 perror(fname);
254                 exit(1);
255         }
256
257         if (stat(fname,&fstat) == -1) {
258                 perror(fname);
259                 return(1);
260         }
261         if (fstat.st_size < size) {
262                 fprintf(stderr,"File isn't %d bytes in size\n",size);
263                 exit(1);
264         }
265
266         if (read(fd,(char *)buf,size) != size) {
267                 perror("read");
268                 exit(1);
269         }
270         close(fd);
271         memcpy(cpy,buf,size);
272
273         ecc_gen(size, buf, ecc1);
274
275         for(bytenum=0;bytenum<size;bytenum++) {
276                 if (memcmp(buf,cpy,size) != 0) {
277                         printf("CMP %d %d\n",bitnum,bytenum);
278                         exit(1);
279                 }
280                 for(bitnum=0;bitnum<8;bitnum++) {
281                         /* Insert an error:
282                          */
283                         if (buf[bytenum] & (1 << bitnum))
284                                 buf[bytenum] &= ~(1 << bitnum);
285                         else
286                                 buf[bytenum] |= (1 << bitnum);
287
288                         /* Compute ecc2 (with the error):
289                          */
290                         ecc_gen(size, buf, ecc2);
291
292                         /* Find the error:
293                          */
294                         rc = ecc_check(size,buf, ecc1, ecc2);
295                         if (rc != 1) { 
296                                 printf("NOPE %d %d\n", bitnum,bytenum);
297                                 exit(1);
298                         }
299                         if (bit_addr != bitnum) {
300                                 printf("BIT__ERR %d %d\n", bit_addr,bitnum);
301                                 exit(1);
302                         }
303                         if (byte_addr != bytenum) {
304                                 printf("BYTE_ERR %d %d\n", byte_addr,bytenum);
305                                 exit(1);
306                         }
307                 }
308         }
309         exit(0);
310 }
311 #endif