[CODE] Hamming Block Code ECC for Nand Flash
/*
* File: nand_ecc.c
* Version: 1.0
* Function: To emulate the Hamming Code ECC for Nand Flash Error Check and Correct
*
* Author: Crifan
* Mail: [email protected]
*
*/
#include <stdio.h>
//#include "nand_ecc.h"
/*
This Application Purpose:
1.emulate to genereta the one page data : 256 bytes data
2. calc its ecc
3.manually change 1 bit data, renew calc the new ecc
4. check ecc to get the result: 1 bit error.
*/
#define NAF_PAGE_SIZE (256)
#define NAF_PAGE_BITS (8) /* 2^8=256 */
#define DATA_CHANGE_ROW 17
#define DATA_CHANGE_COL 5
#define DATA_CHANGE_BIT_NUM (7) /* bit to change, 0~7*/
#define NAF_ECC_BYTES (3) /* ecc size, 24 bits */
#define NAF_BIT_NUM_WHEN_1BIT_ERR (11) /* 1’s number when 1 bit err */
//#define BIT(i) (BIT##i)
#define BIT(i) (1<<i)
#define GET_BIT(x, i) ((x & BIT(i)) >> i)
#define NAF_LINE_PARITY(x) ( GET_BIT(x, 0)^GET_BIT(x, 1)^GET_BIT(x, 2)^GET_BIT(x, 3)^
GET_BIT(x, 4)^GET_BIT(x, 5)^GET_BIT(x, 6)^GET_BIT(x, 7))
#define CP_NR 6
#define LP_NR 16
/*
Col:
P4=D7(+)D6(+)D5(+)D4 P4`=D3(+)D2(+)D1(+)D0
P2=D7(+)D6(+)D3(+)D2 P2`=D5(+)D4(+)D1(+)D0
P1=D7(+)D5(+)D3(+)D1 P1`=D6(+)D4(+)D2(+)D0
Row:
P8 = bit7(+)bit6(+)bit5(+)bit4(+)bit3(+)bit2(+)bit1(+)bit0(+)P8
…
*/
unsigned char naf_pre_calc_table[NAF_PAGE_SIZE];
/* generate the column pre-calculted table */
void naf_gen_col_and_row_table(void)
{
int i = 0;
unsigned char x= 0, data = 0;
for(i = 0; i < NAF_PAGE_SIZE; i ++)
{
x = i;
data = 0;
/* calc for CP/col */
if(GET_BIT(x, 0)^GET_BIT(x, 2)^GET_BIT(x, 4)^GET_BIT(x, 6))
data |= BIT(0);
//printf("data=0x02xn", data);
if(GET_BIT(x, 1)^GET_BIT(x, 3)^GET_BIT(x, 5)^GET_BIT(x, 7))
data |= BIT(1);
//printf("data=0x02xn", data);
if(GET_BIT(x, 0)^GET_BIT(x, 1)^GET_BIT(x, 4)^GET_BIT(x, 5))
data |= BIT(2);
//printf("data=0x02xn", data);
if(GET_BIT(x, 2)^GET_BIT(x, 3)^GET_BIT(x, 6)^GET_BIT(x, 7))
data |= BIT(3);
//printf("data=0x02xn", data);
if(GET_BIT(x, 0)^GET_BIT(x, 1)^GET_BIT(x, 2)^GET_BIT(x, 3))
data |= BIT(4);
//printf("data=0x02xn", data);
if(GET_BIT(x, 4)^GET_BIT(x, 5)^GET_BIT(x, 6)^GET_BIT(x, 7))
data |= BIT(5);
//printf("data=0x02xn", data);
/* calc for LP/row */
if(GET_BIT(x, 0)^GET_BIT(x, 1)^GET_BIT(x, 2)^GET_BIT(x, 3)^GET_BIT(x, 4)^GET_BIT(x, 5)^GET_BIT(x, 6)^GET_BIT(x, 7))
data |= BIT(6);
//printf("data=0x02xn", data);
naf_pre_calc_table[i] = data;
}
}
/* Calculate Hamming Code ECC value*/
void naf_calc_ecc(const unsigned char *pageBuf, unsigned char *ecc)
{
unsigned char CP[CP_NR];
unsigned char LP[LP_NR];
unsigned char x;
int lineNum;
int i, j;
int biti;
/* calc ecc */
memset(CP, 0x00, sizeof(CP));
memset(LP, 0x00, sizeof(LP));
for(i = 0; i < NAF_PAGE_SIZE; i++)
{
x = pageBuf[i];
/* row/line */
#if 0
if(0==i%2)
LP[0] = NAF_LINE_PARITY(x)^LP[0];
if(1==i%2)
LP[1] = NAF_LINE_PARITY(x)^LP[1];
if(0==i%4 || 1==i%4)
LP[2] = NAF_LINE_PARITY(x)^LP[2];
if(2==i%4 || 3==i%4)
LP[3] = NAF_LINE_PARITY(x)^LP[3];
if(0==i%8 || 1==i%8 || 2==i%8 || 3==i%8)
LP[4] = NAF_LINE_PARITY(x)^LP[4];
if(4==i%8 || 5==i%8 || 6==i%8 || 7==i%8)
LP[5] = NAF_LINE_PARITY(x)^LP[5];
if(i%16< 8)
LP[6] = NAF_LINE_PARITY(x)^LP[6];
if(i%16>=8)
LP[7] = NAF_LINE_PARITY(x)^LP[7];
if(i%32< 16)
LP[8] = NAF_LINE_PARITY(x)^LP[8];
if(i%32>=16)
LP[9] = NAF_LINE_PARITY(x)^LP[9];
if(i%64< 32)
LP[10] = NAF_LINE_PARITY(x)^LP[10];
if(i%64>=32)
LP[11] = NAF_LINE_PARITY(x)^LP[11];
#else
for(j = 0; j < NAF_PAGE_BITS; j++)
{
biti = BIT(j+1);
lineNum = 2*j;
//printf("bit%d=0x%xn", j , biti);
if(i%biti < (biti/2))
LP[lineNum] = NAF_LINE_PARITY(x)^LP[lineNum];
if(i%biti >= (biti/2))
LP[lineNum+1] = NAF_LINE_PARITY(x)^LP[lineNum+1];
}
#endif
/* column */
CP[0] = GET_BIT(x, 0)^GET_BIT(x, 2)^GET_BIT(x, 4)^GET_BIT(x, 6)^CP[0];
CP[1] = GET_BIT(x, 1)^GET_BIT(x, 3)^GET_BIT(x, 5)^GET_BIT(x, 7)^CP[1];
CP[2] = GET_BIT(x, 0)^GET_BIT(x, 1)^GET_BIT(x, 4)^GET_BIT(x, 5)^CP[2];
CP[3] = GET_BIT(x, 2)^GET_BIT(x, 3)^GET_BIT(x, 6)^GET_BIT(x, 7)^CP[3];
CP[4] = GET_BIT(x, 0)^GET_BIT(x, 1)^GET_BIT(x, 2)^GET_BIT(x, 3)^CP[4];
CP[5] = GET_BIT(x, 4)^GET_BIT(x, 5)^GET_BIT(x, 6)^GET_BIT(x, 7)^CP[5];
}
#if 0
x = page[0];
printf("x=0x%xn", x);
printf("bit0=0x%xn", GET_BIT(x, 0));
printf("bit1=0x%xn", GET_BIT(x, 1));
printf("bit2=0x%xn", GET_BIT(x, 2));
printf("bit3=0x%xn", GET_BIT(x, 3));
printf("bit4=0x%xn", GET_BIT(x, 4));
printf("bit5=0x%xn", GET_BIT(x, 5));
printf("bit6=0x%xn", GET_BIT(x, 6));
printf("bit6=0x%xn", GET_BIT(x, 7));
//CP[0] = GET_BIT(x, 0)^GET_BIT(x, 2)^GET_BIT(x, 4)^GET_BIT(x, 6)^CP[0];
CP[0] = GET_BIT(x, 0)^GET_BIT(x, 2);
CP[1] = GET_BIT(x, 1)^GET_BIT(x, 3)^GET_BIT(x, 5)^GET_BIT(x, 7)^CP[1];
#endif
#if 0
for(j = 0; j < NAF_PAGE_BITS; j++)
{
biti = BIT(j+1);
printf("bit%d=%dn", j , biti);
}
#endif
#if 0
printf("n");
for(i = 0; i < CP_NR; i++)
printf("CP%d=0x%xn", i, CP[i]);
printf("n");
for(i = 0; i < LP_NR; i++)
printf("LP%d=0x%xn", i, LP[i]);
#endif
/* compose them
Figure 4. Parity Generation for a 256 Byte Input
ECC Bit7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
Ecc0(1) LP07 LP06 LP05 LP04 LP03 LP02 LP01 LP00
Ecc1(2) LP15 LP14 LP13 LP12 LP11 LP10 LP09 LP08
Ecc2(3) CP5 CP4 CP3 CP2 CP1 CP0 1 1
Note: 1. The first Byte, Ecc0, contains line parity bits LP0 – LP07.
2. The second Byte, Ecc1, contains line parity bits LP08 – LP15.
3. The third Byte, Ecc2, contains column parity bits CP0 – CP5, plus two "1" for Bit 0 and Bit 1.
*/
memset(ecc, 0x00, sizeof(ecc));
/* ECC0 */
for(i = 0; i < 8; i++)
{
//printf("%d<<%d=%dn", LP[i], i, LP[i]<<i);
ecc[0] |= LP[i] << i;
}
//printf("n");
/* ECC1 */
for(i = 0; i < 8; i++)
{
//printf("%d<<%d=%dn", LP[i+8], i, LP[i+8]<<i);
ecc[1] |= LP[i+8] << i;
}
//printf("n");
/* ECC2 */
for(i = 0; i < 6; i++)
{
//printf("%d<<%d=%dn", CP[i], i, CP[i]<<(i+2));
ecc[2] |= CP[i] << (i+2);
}
//printf("n");
printf("necc1=%d=0x%xn", ecc[0], ecc[0]);
printf("ecc2=%d=0x%xn", ecc[1], ecc[1]);
printf("ecc3=%d=0x%xn", ecc[2], ecc[2]);
}
int naf_calc_bit1_num(unsigned int value)
{
int bit1Num = 0;
int i;
int len;
len = sizeof(unsigned int)* 8;
for(i =0; i < len; i++)
{
if(BIT(i)&value)
bit1Num++;
}
//printf("len=%d,Value=%d=0x%x, bit1 number=%dn", len, value, value, bit1Num);
return bit1Num;
}
#define NAF_ERR_NONE (0)
#define NAF_ERR_PARM (-1)
#define NAF_ERR_1BIT_DATA (-2)
#define NAF_ERR_1BIT_ECC (-3)
#define NAF_ERR_UNKNOWN (-4)
int naf_check_ecc(unsigned char ecc1[NAF_ECC_BYTES], unsigned char ecc2[NAF_ECC_BYTES])
{
int i, arrSize;
unsigned char cmp;
int noneZeroBits = 0;
arrSize = sizeof(ecc1);
if(arrSize != sizeof(ecc2))
return NAF_ERR_PARM;
for(i = 0; i < arrSize; i++)
{
cmp = (ecc1[i]^ecc2[i]);
if(0!=cmp)
{
//printf("XOR ecc[%d]=0x%xn", i, cmp);
noneZeroBits +=naf_calc_bit1_num((unsigned int )cmp);
}
}
if(0==noneZeroBits)
return NAF_ERR_NONE;
else
if(1==noneZeroBits)
return NAF_ERR_1BIT_ECC;
else
if(NAF_BIT_NUM_WHEN_1BIT_ERR==noneZeroBits)
return NAF_ERR_1BIT_DATA;
else
return NAF_ERR_UNKNOWN;
}
#define DATA_6BIT_MASK (0x3F)
#define DATA_8BIT_MASK (0xFF)
#if 0
/* clear num bits from bit position: start_bit */
int naf_mask_out_bit(int value, int start_bit, int num )
{
int i;
int len;
len = sizeof(int)*8;
for(i =start_bit; i < start_bit+num && i < len; i++)
value &= ~ (BIT(i));
return value;
}
#endif
/* max support 32 bit long */
int naf_calc_bit_pos(int value, int toltalBitsNr, int stat_bit)
{
int bit_pos, j, biti;
/* initial */
bit_pos = stat_bit;
//printf("Searching path:n");
for(j = toltalBitsNr/2; j > 0 ; j–)
{
biti = BIT(j*2-1);
if(value & biti)
{
/* must in high part of current level*/
//bit_pos -= BIT(j-1);
}
else
{
/* must in low part of current level*/
bit_pos -= BIT(j-1);
}
//printf("pos=%dn", bit_pos);
}
return bit_pos;
}
/* calc the err data position */
void naf_calc_row_col(unsigned char ecc1[NAF_ECC_BYTES], unsigned char ecc2[NAF_ECC_BYTES], int *row, int*col)
{
unsigned char CP[CP_NR];
unsigned char LP[LP_NR];
unsigned char xorValue[NAF_ECC_BYTES];
unsigned int biti;
int j;
int prevSelect;
unsigned char mask;
int bit_pos;
int rowValue, colValue;
xorValue[0] = ecc1[0]^ecc2[0];
xorValue[1] = ecc1[1]^ecc2[1];
xorValue[2] = ecc1[2]^ecc2[2];
rowValue = xorValue[0] | (xorValue[1] << 8);
colValue = (xorValue[2]>> 2);
printf("xor[1]=%d=0x%x ", xorValue[0], xorValue[0]);
printf("xor[2]=%d=0x%x ", xorValue[1], xorValue[1]);
printf("xor[3]=%d=0x%xn", xorValue[2], xorValue[2]);
*col = naf_calc_bit_pos(colValue, CP_NR, 7);
*row = naf_calc_bit_pos(rowValue, LP_NR, 255);
}
int main(void)
{
int i;
int row, col;
unsigned char page[NAF_PAGE_SIZE];
unsigned char ecc[NAF_ECC_BYTES];
unsigned char ecc_new[NAF_ECC_BYTES];
int noneZeroBits = 0;
int xor;
int row_calc, col_calc;
unsigned char newVal;
printf("This is Hamming Block Code ECC for Nand Flash:n");
printf("The emulated page data is :n");
printf("——————————————————————–n ");
printf("row\col ", i);
for(i = 0; i < 8; i++ )
{
printf("[%d]t", i);
}
printf("n ");
for(i = 0; i < NAF_PAGE_SIZE; i++ )
{
row = i/8;
if(0 ==i%8)
{
printf("[%d]t", row);
}
page[i] = random(i);
printf("%dt", page[i]);
if(0 ==(i+1)%8)
{
printf("n ");
}
}
naf_calc_ecc(page, ecc);
printf("n——————————————————————–n");
#if 0
/*1 bit ECC demo */
ecc[0] ^= (1<<5);
#else
/* 1bit data demo */
row = DATA_CHANGE_ROW;
col = DATA_CHANGE_COL;
newVal = page[row*8+col] ^(1<<DATA_CHANGE_BIT_NUM);
printf("Now manually change the data:row=%d,col=%dnold=%d=0x%x, new=%d=0x%xn",
row,col, page[row*8+col], page[row*8+col], newVal, newVal);
printf("Manually change positon in Hamming Block: Row=%d, Col=%dn", row*8+col, DATA_CHANGE_BIT_NUM);
page[row*8+col] = newVal;
#endif
naf_calc_ecc(page, ecc_new);
noneZeroBits = naf_check_ecc(ecc, ecc_new);
printf("ECC Check Result:");
if(NAF_ERR_NONE ==noneZeroBits)
{
printf("Data verified OK.n");
}
else
if(NAF_ERR_1BIT_DATA == noneZeroBits)
{
printf("1 Bit Data err.n");
printf("oldEcc=0x%x, 0x%x, 0x%x, newEcc=0x%x, 0x%x, 0x%x.n", ecc[0], ecc[1], ecc[2], ecc_new[0], ecc_new[1], ecc_new[2]);
naf_calc_row_col(ecc, ecc_new, &row_calc, &col_calc);
printf("Find out the Err data occur in :n");
printf("row=%d ", row_calc);
printf("col=%dn", col_calc);
}
else
if(NAF_ERR_1BIT_ECC == noneZeroBits)
{
printf("1 Bit ECC err.n");
}
//printf("test1=0x%xn", naf_mask_out_bit(0xFF, 4, 2));
#if 0
naf_gen_col_and_row_table();
printf("Pre-calculated column ECC table:n");
for(i = 0; i < NAF_PAGE_SIZE; i++)
{
if(0==i%16)
printf("n");
printf("0x%02x, ", naf_pre_calc_table[i]);
}
#endif
return 0;
}