uffs_ecc.c

nandflash文件系统源代码

/*
    Copyright (C) 2005-2008  Ricky Zheng <[e-mail]>

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

*/
/**
 * \file uffs_ecc.c
 * \brief ecc maker and correct
 * \author Ricky Zheng, created in 12th Jun, 2005
 */

#include "uffs/uffs_fs.h"
#include "uffs/uffs_config.h"
#include <string.h>

#define PFX "ecc:"

static const unsigned char column_parity_table[] = {
	0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69, 0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00, 
	0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc, 0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95, 
	0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0, 0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99, 
	0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65, 0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c, 
	0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc, 0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5, 
	0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59, 0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30, 
	0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55, 0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c, 
	0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0, 0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9, 
	0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0, 0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9, 
	0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55, 0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c, 
	0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59, 0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30, 
	0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc, 0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5, 
	0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65, 0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c, 
	0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0, 0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99, 
	0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc, 0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95, 
	0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69, 0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00, 
};

static const unsigned bit_counter[16] = {
	/* 0000 */ 0,
	/* 0001 */ 1,
	/* 0010 */ 1,
	/* 0011 */ 2,
	/* 0100 */ 1,
	/* 0101 */ 2,
	/* 0110 */ 2,
	/* 0111 */ 3,
	/* 1000 */ 1,
	/* 1001 */ 2,
	/* 1010 */ 2,
	/* 1011 */ 3,
	/* 1100 */ 2,
	/* 1101 */ 3,
	/* 1110 */ 3,
	/* 1111 */ 4,
};

static int uffs_CountBits(unsigned char x)
{
	return bit_counter[x & 0x0F] + bit_counter[(x & 0xF0) >> 4];
}

int uffs_GetEccSize256(uffs_Device *dev)
{
	dev = dev;
	return 3;
}

int uffs_GetEccSize512(uffs_Device *dev)
{
	dev = dev;
	return 6;
}

int uffs_GetEccSize1K(uffs_Device *dev)
{
	dev = dev;
	return 12;
}

int uffs_GetEccSize2K(uffs_Device *dev)
{
	dev = dev;
	return 24;
}


static void uffs_MakeEccChunk256(uffs_Device *dev, void *data, void *ecc, unsigned int len)
{
	unsigned char *pecc = (unsigned char *)ecc;
	unsigned int i;
	unsigned char *p = (unsigned char *)data;
	unsigned char col_parity = 0;
	unsigned char line_parity = 0;
	unsigned char line_parity_prime = 0;
	unsigned char t;
	unsigned char b;

	dev = dev;

	for(i = 0; i < len; i++)
	{
		b = column_parity_table[*p++];
		col_parity ^= b;

		if(b & 0x01) // odd number of bits in the byte
		{
			line_parity ^= i;
			line_parity_prime ^= ~i;
		}
	}

	for(i = 0; i < 256 - len; i++)
	{
		b = column_parity_table[0];	//always use 0 for the rest data
		col_parity ^= b;

		if(b & 0x01) // odd number of bits in the byte
		{
			line_parity ^= i;
			line_parity_prime ^= ~i;
		}
		
	}	
	pecc[2] = (~col_parity) | 0x03;
	
	t = 0;
	if(line_parity       & 0x80) t |= 0x80;
	if(line_parity_prime & 0x80) t |= 0x40;
	if(line_parity       & 0x40) t |= 0x20;
	if(line_parity_prime & 0x40) t |= 0x10;
	if(line_parity       & 0x20) t |= 0x08;
	if(line_parity_prime & 0x20) t |= 0x04;
	if(line_parity       & 0x10) t |= 0x02;
	if(line_parity_prime & 0x10) t |= 0x01;
	pecc[1] = ~t;
	
	t = 0;
	if(line_parity       & 0x08) t |= 0x80;
	if(line_parity_prime & 0x08) t |= 0x40;
	if(line_parity       & 0x04) t |= 0x20;
	if(line_parity_prime & 0x04) t |= 0x10;
	if(line_parity       & 0x02) t |= 0x08;
	if(line_parity_prime & 0x02) t |= 0x04;
	if(line_parity       & 0x01) t |= 0x02;
	if(line_parity_prime & 0x01) t |= 0x01;
	pecc[0] = ~t;
}

void uffs_MakeEcc256(uffs_Device *dev, void *data, void *ecc)
{
	uffs_MakeEccChunk256(dev, data, ecc, 256 - 3);
}

void uffs_MakeEcc512(uffs_Device *dev, void *data, void *ecc)
{
	uffs_MakeEccChunk256(dev, data, ecc, 256);
	uffs_MakeEccChunk256(dev, (char *)data + 256, (char *)ecc + 3, 256 - 6);
}

void uffs_MakeEcc1K(uffs_Device *dev, void *data, void *ecc)
{
	int i;
	char *p = (char *)data;
	char *pecc = (char *)ecc;

	for (i = 0; i < 3; i++) {
		uffs_MakeEccChunk256(dev, p, pecc, 256);
		p += 256; pecc += 3;
	}
	uffs_MakeEccChunk256(dev, p, pecc, 256 - 12);
}

void uffs_MakeEcc2K(uffs_Device *dev, void *data, void *ecc)
{
	int i;
	char *p = (char *)data;
	char *pecc = (char *)ecc;

	for (i = 0; i < 7; i++) {
		uffs_MakeEccChunk256(dev, p, pecc, 256);
		p += 256; pecc += 3;
	}
	uffs_MakeEccChunk256(dev, p, pecc, 256 - 24);
}

static int uffs_EccCorrectChunk256(uffs_Device *dev, void *data, void *read_ecc, const void *test_ecc, int errtop)
{
	unsigned char d0, d1, d2; // deltas 
	unsigned char *p = (unsigned char *)data;
	unsigned char *pread_ecc = (unsigned char *)read_ecc, *ptest_ecc = (unsigned char *)test_ecc;

	dev = dev;
	
	d0 = pread_ecc[0] ^ ptest_ecc[0];
	d1 = pread_ecc[1] ^ ptest_ecc[1];
	d2 = pread_ecc[2] ^ ptest_ecc[2];
	
	if((d0 | d1 | d2) == 0)
	{
		return 0;
	}
	
	if( ((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
	    ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
	    ((d2 ^ (d2 >> 1)) & 0x54) == 0x54)
	{
		// Single bit (recoverable) error in data

		int byte;
		int bit;
		
		bit = byte = 0;
		
		
		if(d1 & 0x80) byte |= 0x80;
		if(d1 & 0x20) byte |= 0x40;
		if(d1 & 0x08) byte |= 0x20;
		if(d1 & 0x02) byte |= 0x10;
		if(d0 & 0x80) byte |= 0x08;
		if(d0 & 0x20) byte |= 0x04;
		if(d0 & 0x08) byte |= 0x02;
		if(d0 & 0x02) byte |= 0x01;

		if(d2 & 0x80) bit |= 0x04;
		if(d2 & 0x20) bit |= 0x02;
		if(d2 & 0x08) bit |= 0x01;

		if (byte >= errtop) return -1;

		p[byte] ^= (1 << bit);
		
		return 1;
	}
	
	if((uffs_CountBits(d0)+uffs_CountBits(d1)+uffs_CountBits(d2)) == 1)
	{
		// Reccoverable error in ecc
		
		pread_ecc[0] = ptest_ecc[0];
		pread_ecc[1] = ptest_ecc[1];
		pread_ecc[2] = ptest_ecc[2];
		
		return 1;
	}
	
	// Unrecoverable error
	return -1;
}

/** 
 * return:   0 -- no error
 *			-1 -- can not be correct
 *			>0 -- how many bits corrected
 */
int uffs_EccCorrect256(uffs_Device *dev, void *data, void *read_ecc, const void *test_ecc)
{
	return uffs_EccCorrectChunk256(dev, data, read_ecc, test_ecc, 256 - 3);
}

/** 
 * return:   0 -- no error
 *			-1 -- can not be correct
 *			>0 -- how many bits corrected
 */
int uffs_EccCorrect512(uffs_Device *dev, void *data, void *read_ecc, const void *test_ecc)
{
	int ret1, ret2;

	ret1 = uffs_EccCorrectChunk256(dev, data, read_ecc, test_ecc, 256);
	if (ret1 < 0) return ret1;

	ret2 = uffs_EccCorrectChunk256(dev, (char *)data + 256, (char *)read_ecc + 3, (const char *)test_ecc + 3, 250);
	if (ret2 < 0) return ret2;

	return ret1 + ret2;
}

/** 
 * return:   0 -- no error
 *			-1 -- can not be correct
 *			>0 -- how many bits corrected
 */
int uffs_EccCorrect1K(uffs_Device *dev, void *data, void *read_ecc, const void *test_ecc)
{
	int ret[4];
	int i;
	char *p = (char *)data;
	char *pecc = (char *)read_ecc;
	const char *ptecc = (const char *)test_ecc;

	for (i = 0; i < 3; i++) {
		ret[i] = uffs_EccCorrectChunk256(dev, p, pecc, ptecc, 256);
		if (ret[i] < 0) return ret[i];
		p += 256; pecc += 3; ptecc += 3;
	}
	ret[i] = uffs_EccCorrectChunk256(dev, p, pecc, ptecc, 256 - 12); //last chunk
	if (ret[i] < 0) return ret[i];

	return ret[0] + ret[1] + ret[2] + ret[3];
}

/** 
 * return:   0 -- no error
 *			-1 -- can not be correct
 *			>0 -- how many bits corrected
 */
int uffs_EccCorrect2K(uffs_Device *dev, void *data, void *read_ecc, const void *test_ecc)
{
	int ret[8];
	int i;
	char *p = (char *)data;
	char *pecc = (char *)read_ecc;
	const char *ptecc = (const char *)test_ecc;

	for (i = 0; i < 7; i++) {
		ret[i] = uffs_EccCorrectChunk256(dev, p, pecc, ptecc, 256);
		if (ret[i] < 0) return ret[i];
		p += 256; pecc += 3; ptecc += 3;
	}
	ret[i] = uffs_EccCorrectChunk256(dev, p, pecc, ptecc, 256 - 24); //last chunk
	if (ret[i] < 0) return ret[i];

	return ret[0] + ret[1] + ret[2] + ret[3] + ret[4] + ret[5] + ret[6] + ret[7];
}